Multi-stage filtering for recommended user connections on online social networks

• US 10,313,456 B2
• Filed: 11/30/2016
• Issued: 06/04/2019
• Est. Priority Date: 11/30/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Ma, Xingyu, Ma, Tin Shing, Yang, Xiaofan
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US15/365,532
• Publication Number:
  US 20180150464A1
• Time in Patent Office: 916 Days
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/53 using third party service providers
• CPC Class Codes: H04L 67/55 Push-based network services

Abstract

In one embodiment, a method includes identifying a first set of candidate-users. Each candidate-user corresponds to a second user within a threshold degree of separation of a first user within a social graph. The method includes filtering, using a first-stage filtering model, the first set of candidate-users to generate a second set of candidate-users using edge-features. The method includes filtering, using a second-stage filtering model, the second set of candidate-users to generate a third-set of candidate-users using the edge-features and user-features. The method includes ranking, using a user-engagement model, the third set of candidate-users using a feature superset based on a probability of the first user connecting with the respective candidate-user. The method includes sending, to a client system of the first user, instructions for generating a suggested-friends interface for display. The suggested-friends interface includes candidate-users from the third set of candidate-users having a ranking greater than a threshold rank.

Claims

1. A method comprising:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first node corresponding to a first user associated with an online social network; and

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

identifying, for the first user, a first set of candidate-users from the plurality of second users, wherein each candidate-user corresponds to a second user within a threshold degree of separation of the first user within the social graph;

filtering, using a first-stage filtering model, the first set of candidate-users to generate a second set of candidate-users, wherein the first-stage filtering model filters the candidate-users based on one or more edge-features;

filtering, using a second-stage filtering model, the second set of candidate-users to generate a third-set of candidate-users, wherein the second-stage filtering model filters the candidate-users based on the one or more edge-features and one or more user-features;

ranking, using a user-engagement model, the third set of candidate-users based on a feature superset, wherein the user-engagement model ranks the candidate-users based on a calculated probability of the first user connecting with the respective candidate-user; and

sending, to a client system of the first user, instructions for generating a suggested-friends interface for display to the first user, wherein the suggested-friends interface comprises one or more candidate-users from the third set of candidate-users having a ranking greater than a threshold rank.

2. The method of claim 1, wherein the threshold degree of separation is two, and wherein each candidate-user in the first set of candidate-users corresponds to a second node connected by a friend-type edge to an intervening node that it connected by a friend-type edge to the first node.

3. The method of claim 1, wherein one or more edges of the plurality of edges is an inferred connection, each inferred connection being derived based on one or more of:

contact information imported from an external system associated with one or more users of the online social network;

communication information associated with one or more users of the online social network;

login information associated with one or more users of the online social network;

or

social-graph information associated with one or more users of the online social network.

4. The method of claim 1, wherein one or more of the first-stage filtering model, the second-stage filtering model, or the user-engagement model is a machine-learning model generated based on an analysis of user interactions and connections with prior suggested friends.

5. The method of claim 4, wherein the machine-learning model is a gradient boosted decision tree model.

6. The method of claim 1, wherein the one or more edge-features comprise information associated with each particular pair of users, the information comprising one or more of:

a social-graph affinity of each user in the pair of users with respect to the other user;

an age of one or more edges connecting nodes corresponding to each user in the pair of users;

or

a level of engagement of each user in the pair of users with respect to the other user.

7. The method of claim 1, wherein the feature superset comprises:

edge-features and user-features used during the first-stage filtering or the second-stage filtering; and

a plurality of additional features not used during the first-stage filtering or the second-stage filtering.

8. The method of claim 7, wherein the pair of users includes:

the first user; and

a user corresponding to an intervening node.

9. The method of claim 7, wherein the pair of users includes:

a user corresponding to an intervening node; and

a candidate-user.

10. The method of claim 1, wherein the one or more user-features comprise information associated with a particular user, wherein the information comprises:

demographic information associated with the particular user;

an age of the particular user'"'"'s account on the online social network;

an amount of time since the particular user last accessed the online social network;

a number of friend requests sent by the particular user;

a number of friend requests received by the particular user;

a number of friend requests rejected by the particular user;

a number of pending friend requests associated with the particular user;

a friend request acceptance rate associated with the particular user;

a friend request rejection rate associated with the particular user;

or

an average pending time of friend requests associated with the particular user.

11. The method of claim 10, wherein the second-stage filtering model filters the candidate-users based on one or more user-features by comparing information associated with the first user to information associated with each of the candidate-users in the second set of candidate-users.

12. The method of claim 7, wherein the pair of users includes:

the first user; and

a candidate-user.

13. The method of claim 1, wherein the instructions for generating the suggested-friends interface are sent to a native application associated with the online social network on the client system of the first user.

14. The method of claim 1, wherein the instructions for generating the suggested-friends interface are sent to a browser client on the client system of the first user.

15. The method of claim 1, further comprising receiving a request from the first user to generate the suggested-friends interface, wherein the instructions for generating the suggested-friends interface are sent responsive to the request.

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

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first node corresponding to a first user associated with an online social network; and

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

identify, for the first user, a first set of candidate-users from the plurality of second users, wherein each candidate-user corresponds to a second user within a threshold degree of separation of the first user within the social graph;

filter, using a first-stage filtering model, the first set of candidate-users to generate a second set of candidate-users, wherein the first-stage filtering model filters the candidate-users based on one or more edge-features;

filter, using a second-stage filtering model, the second set of candidate-users to generate a third-set of candidate-users, wherein the second-stage filtering model filters the candidate-users based on the one or more edge-features and one or more user-features;

rank, using a user-engagement model, the third set of candidate-users based on a feature superset, wherein the user-engagement model ranks the candidate-users based on a calculated probability of the first user connecting with the respective candidate-user; and

send, to a client system of the first user, instructions for generating a suggested-friends interface for display to the first user, wherein the suggested-friends interface comprises one or more candidate-users from the third set of candidate-users having a ranking greater than a threshold rank.

17. A system comprising:

one or more processors; and

a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first node corresponding to a first user associated with an online social network; and

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

identify, for the first user, a first set of candidate-users from the plurality of second users, wherein each candidate-user corresponds to a second user within a threshold degree of separation of the first user within the social graph;

filter, using a first-stage filtering model, the first set of candidate-users to generate a second set of candidate-users, wherein the first-stage filtering model filters the candidate-users based on one or more edge-features;

filter, using a second-stage filtering model, the second set of candidate-users to generate a third-set of candidate-users, wherein the second-stage filtering model filters the candidate-users based on the one or more edge-features and one or more user-features;

rank, using a user-engagement model, the third set of candidate-users based on a feature superset, wherein the user-engagement model ranks the candidate-users based on a calculated probability of the first user connecting with the respective candidate-user; and

send, to a client system of the first user, instructions for generating a suggested-friends interface for display to the first user, wherein the suggested-friends interface comprises one or more candidate-users from the third set of candidate-users having a ranking greater than a threshold rank.