Prediction of Next Place Visits on Online Social Networks

Abstract

In one embodiment, a method includes accessing a place-entities graph comprising a plurality of place-entity nodes, in which each place-entity node representing a place-entity corresponding to a particular geographic location, and identifying a place-entity cluster within the place-entities graph. The place-entity cluster comprises a plurality of place-entity nodes corresponding to a plurality of place-entities corresponding to the same geographic location. The method includes accessing embeddings representing the plurality of place-entities corresponding to the place-entity cluster. Each embedding is a point in a d-dimensional embedding space. The method includes calculating, using a machine-learning model, a cluster-quality score of the place-entity cluster based on the embeddings. The cluster-quality score represents a probability that the place-entities correspond to a valid geographic location. The method further includes identifying the place-entities as corresponding to an invalid geographic location based on a determining that the cluster-quality score is less than a threshold cluster-quality score.

What is claimed is: 
     
         1 . A method, comprising, by one or more computer systems of an online social network:
 accessing a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity corresponding to a particular geographic location, each edge between two nodes establishing a single degree of separation between them;   identifying a place-entity cluster within the place-entities graph, wherein the place-entity cluster comprises a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity corresponding to the same geographic location;   accessing a plurality of embeddings representing the plurality of place-entities corresponding to the place-entity cluster, respectively, wherein each embedding is a point in a d-dimensional embedding space;   calculating, using a machine-learning model, a cluster-quality score of the place-entity cluster based on the plurality of embeddings representing the place-entities corresponding to the place-entity cluster, wherein the cluster-quality score represents a probability that the place-entities corresponding to the place-entity cluster correspond to a valid geographic location; and   identifying the place-entities corresponding to the place-entity cluster as corresponding to an invalid geographic location based on a determining that the cluster-quality score is less than a threshold cluster-quality score.   
     
     
         2 . The method of  claim 1 , wherein each place-entity cluster comprises place-entity nodes having duplication-values with respect to a canonical place-entity node in the place-entity cluster above a threshold duplication-value. 
     
     
         3 . The method of  claim 1 , further comprising, for each place-entity of the plurality of place-entities, generating the embedding representing the place-entity. 
     
     
         4 . The method of  claim 3 , wherein, for each place-entity, the embedding representing the place-entity was generated based at least in part on one or more of a source of information associated with the place-entity, a date of information associated with the place-entity, an accuracy of attributes of the place-entity, a number of photos associated with the place-entity, an amount of content associated with the place-entity, a recency-value associated with the content or photos, or a number of social signals associated with the place-entity. 
     
     
         5 . The method of  claim 4 , wherein the source of information associated with at least one place-entity is a user of the online social network or a third-party system. 
     
     
         6 . The method of  claim 1 , further comprising:
 receiving, from a client system associated with a user, a query comprising one or more n-grams;   identifying one or more place-entities matching at least a portion of the query, wherein the identified place-entities comprise at least one place-entity corresponding to the place-entity cluster;   calculating, for each identified place-entity, a relevance score;   ranking the identified place-entities based at least in part on their respective relevance scores, wherein each identified place-entity corresponding to the place-entity cluster is ranked lower than each identified place-entity not corresponding to the place-entity cluster; and   sending, to the client system responsive to the query, instructions for presenting a search-results page, the search-results page comprising one or more search results corresponding to the one or more identified place-entities, respectively, wherein the search-results page displays the search results ordered by the rank of the corresponding identified place-entities.   
     
     
         7 . The method of  claim 1 , further comprising:
 receiving, from a client system associated with a user, a query comprising one or more n-grams;   identifying one or more place-entities matching at least a portion of the query, wherein the identified place-entities comprise at least one place-entity corresponding to the place-entity cluster; and   sending, to the client system responsive to the query, instructions for presenting a search-results page, the search-results page comprising one or more search results corresponding to the one or more identified place-entities, respectively, wherein each search result corresponds to an identified place-entity that does not correspond to the place-entity cluster.   
     
     
         8 . The method of  claim 1 , further comprising calculating, for each place-entity, an entity-quality score of the place-entity. 
     
     
         9 . The method of  claim 8 , wherein each embedding representing a place-entity was generated based at least in part on whether the place-entity has an entity-quality score less than a threshold entity-quality score. 
     
     
         10 . A system, comprising:
 one or more non-transitory computer-readable storage media including instructions; and   one or more processors coupled to the one or more non-transitory storage media, the one or more processors configured to execute the instructions to:
 access a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity corresponding to a particular geographic location, each edge between two nodes establishing a single degree of separation between them; 
 identify a place-entity cluster within the place-entities graph, wherein the place-entity cluster comprises a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity corresponding to the same geographic location; 
 access a plurality of embeddings representing the plurality of place-entities corresponding to the place-entity cluster, respectively, wherein each embedding is a point in a d-dimensional embedding space; 
 calculate, using a machine-learning model, a cluster-quality score of the place-entity cluster based on the plurality of embeddings representing the place-entities corresponding to the place-entity cluster, wherein the cluster-quality score represents a probability that the place-entities corresponding to the place-entity cluster correspond to a valid geographic location; and 
 identify the place-entities corresponding to the place-entity cluster as corresponding to an invalid geographic location based on a determining that the cluster-quality score is less than a threshold cluster-quality score. 
   
     
     
         11 . The system of  claim 10 , wherein each place-entity cluster comprises place-entity nodes having duplication-values with respect to a canonical place-entity node in the place-entity cluster above a threshold duplication-value. 
     
     
         12 . The system of  claim 10 , wherein the instructions further comprise instructions to, for each place-entity of the plurality of place-entities, generate the embedding representing the place-entity. 
     
     
         13 . The system of  claim 12 , wherein, for each place-entity, the embedding representing the place-entity was generated based at least in part on one or more of a source of information associated with the place-entity, a date of information associated with the place-entity, an accuracy of attributes of the place-entity, a number of photos associated with the place-entity, an amount of content associated with the place-entity, a recency-value associated with the content or photos, or a number of social signals associated with the place-entity. 
     
     
         14 . The system of  claim 13 , wherein the source of information associated with at least one place-entity is a user of the online social network or a third-party system. 
     
     
         15 . The system of  claim 10 , wherein the instructions further comprise instructions to:
 receive, from a client system associated with a user, a query comprising one or more n-grams;   identify one or more place-entities matching at least a portion of the query, wherein the identified place-entities comprise at least one place-entity corresponding to the place-entity cluster;   calculate, for each identified place-entity, a relevance score;   rank the identified place-entities based at least in part on their respective relevance scores, wherein each identified place-entity corresponding to the place-entity cluster is ranked lower than each identified place-entity not corresponding to the place-entity cluster; and   send, to the client system responsive to the query, instructions for presenting a search-results page, the search-results page comprising one or more search results corresponding to the one or more identified place-entities, respectively, wherein the search-results page displays the search results ordered by the rank of the corresponding identified place-entities.   
     
     
         16 . The system of  claim 10 , wherein the instructions further comprise instructions to:
 receive, from a client system associated with a user, a query comprising one or more n-grams;   identify one or more place-entities matching at least a portion of the query, wherein the identified place-entities comprise at least one place-entity corresponding to the place-entity cluster; and   send, to the client system responsive to the query, instructions for presenting a search-results page, the search-results page comprising one or more search results corresponding to the one or more identified place-entities, respectively, wherein each search result corresponds to an identified place-entity that does not correspond to the place-entity cluster.   
     
     
         17 . The system of  claim 10 , wherein the instructions further comprise instructions to calculate, for each place-entity, an entity-quality score of the place-entity. 
     
     
         18 . The system of  claim 17 , wherein each embedding representing a place-entity was generated based at least in part on whether the place-entity has an entity-quality score less than a threshold entity-quality score. 
     
     
         19 . A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the one or more processors to:
 access a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity corresponding to a particular geographic location, each edge between two nodes establishing a single degree of separation between them;   identify a place-entity cluster within the place-entities graph, wherein the place-entity cluster comprises a plurality of place-entity nodes corresponding to a plurality of place-entities, respectively, each place-entity corresponding to the same geographic location;