Identification of low-quality place-entities on online social networks

1. A method comprising:

by the one or more computing devices of an online social network, accessing a social graph of the online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising:

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

by the one or more computing devices, generating a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein:

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

by the one or more computing devices, assigning, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

by the one or more computing devices, calculating, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.

2. The method of claim 1 , wherein the initial quality-score for each place-entity node represents a measure of quality of the place-entity node.

3. The method of claim 1 , wherein the initial quality-score for each place-entity node is based at least in part on social-networking interactions represented by the one or more edges connected to the place-entity node.

4. The method of claim 3 , wherein the social-networking interactions comprise check-ins, likes, comments, views, or reviews of a place-entity corresponding to the place-entity node.

5. The method of claim 1 , further comprising:

if the final quality-score for the place-entity node is above a threshold quality-score, then identifying the place-entity node as a valid place-entity node;

else identifying the place-entity node as a junk place-entity node.

6. The method of claim 1 , further comprising removing from the heterogeneous graph each place-entity node having a final quality-score below a threshold quality-score.

7. The method of claim 1 , further comprising:

receiving, from a client system of a user of the online social network, a search query associated with a particular place-entity node in the heterogeneous graph, the particular place-entity node being associated with a particular canonical place-entity node; and

sending, to the client system, a response to the search query, wherein:

if the particular place-entity node has a final quality-score less than a threshold quality-score, then the response comprises a reference to the particular canonical place-entity node;

else the response comprises a reference to the particular place-entity node.

8. The method of claim 1 , further comprising:

receiving, from a client system of a user of the online social network, a search query;

identifying a plurality of place-entity nodes matching the search query;

ranking the identified place-entity nodes based on final quality-scores associated with the identified place-entity nodes; and

sending, to the client system of the user, a search-results page comprising references to each place-entity node having a ranking greater than a threshold ranking.

9. The method of claim 8 , further comprising:

determining that the user has a social-graph affinity with respect to one of the identified place-entity nodes, wherein the social-graph affinity is greater than a threshold affinity; and

boosting a ranking of the particular identified place-entity nodes based on the user having the social-graph affinity with respect to the particular identified place-entity node.

10. The method of claim 1 , wherein the plurality of n-grams comprises only unigrams and bigrams.

11. The method of claim 1 , wherein iteratively propagating the initial quality-scores through the heterogeneous graph comprises performing a label-propagation process on the heterogeneous graph.

12. The method of claim 1 , wherein iteratively propagating the initial quality-scores through the heterogeneous graph comprises an iterative propagation process, each iteration of the propagation process comprising:

calculating, for each n-gram node connected to one or more place-entity nodes having an associated quality-score, an n-gram-node score based on the associated quality-scores of the place-entity nodes connected to the n-gram node;

calculating, for each user node connected to one or more place-entity nodes, a user-node score based on the associated quality-scores of the place-entity nodes connected to the user node;

calculating, for each place-entity node, an updated quality-score based on:

the n-gram-node scores associated with the n-gram nodes connected to the place-entity node; and

the user-node scores associated with the user nodes connected to the place-entity node; and

if the updated quality-scores associated with the place-entity nodes of the heterogeneous graph have converged, then exiting the iterative propagation process and using the updated quality-scores as the final quality-scores, else performing another iteration of the propagation process.

13. The method of claim 12 , wherein calculating the n-gram-node score comprises averaging the quality-scores associated with the place-entity nodes connected to the n-gram node.

14. The method of claim 12 , wherein calculating the updated quality-score comprises determining a weighted average value of:

the n-gram-node scores associated with the n-gram nodes connected to the place-entity node; and

the user-node scores associated with the user nodes connected to the place-entity node.

15. The method of claim 14 , wherein calculating the updated quality-score further comprises multiplying each of the n-gram-node scores and user-node scores by a respective weighting factor.

16. The method of claim 12 , wherein the updated quality-scores associated with the place-entity nodes have converged when the sum of updated quality-scores, n-gram-node scores, and user-nodes for the heterogeneous graph changes between two iterations by a value less than a threshold value.

17. The method of claim 1 , wherein assigning the initial quality-score to the first set of place-entity nodes comprises:

assigning a maximum quality-score if a place-entity node is a known valid place-entity node; and

assigning a minimum quality-score if a place-entity node is a known junk place-entity node.

18. The method of claim 17 , wherein the final quality-scores range between the maximum and minimum quality scores, inclusive.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access a social graph of an online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising:

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

generate a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein:

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

assign, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

calculate, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.

20. A system comprising: one or more processors; and a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:

access a social graph of an online social network, the social graph comprising a plurality of entity nodes and a plurality of edges connecting the entity nodes, each edge between two nodes establishing a single degree of separation between them, the plurality of entity nodes comprising:

a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity being associated with a particular geographic location, each place-entity having a place name comprising one or more n-grams; and

a plurality of user nodes corresponding to a plurality of users of the online social network, respectively;

generate a heterogeneous graph based on the social graph, the heterogeneous graph comprising the plurality of nodes and edges of the social graph and further comprising a plurality of n-gram nodes corresponding to a plurality of n-grams, respectively, wherein:

each place-entity node is connected by one or more edges to one or more respective n-gram nodes, each n-gram node corresponding to an n-gram within the place name of the place-entity; and

each place-entity node is connected by one or more edges to one or more user nodes, each edge between a user node and a place-entity node representing a social-networking interaction by the user corresponding to the user node with the place-entity corresponding to the place-entity node;

assign, for each place-entity node of a first set of place-entity nodes within the heterogeneous graph, an initial quality-score to the place-entity node;

calculate, for each place-entity node of the heterogeneous graph, a final quality-score for the place-entity node based on the initial quality-scores of the first set of place-entity nodes, wherein the final quality-scores are calculated by iteratively propagating the initial quality-scores through the place-entity nodes, n-gram nodes, and user nodes of the heterogeneous graph until the sum of the quality-scores associated with the place-entity nodes, user nodes, and n-gram nodes reach convergence.