Patent ID: 11868916
Assignee: SNAP INC.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 11:
12. A system comprising:
a memory on which is stored social graph information indicating a baseline social graph that models relationships and attributes of multiple users of a social network application, the baseline social graph comprising:
nodes representing respective users of the social network application;
links representing established relationships between the users of the social network application, each link extending between a corresponding pair of nodes; and
labels associated with the nodes, each label being associated with one or more of the nodes to indicate a corresponding attribute of the one or more associated nodes;

a graph refinement engine comprising one or more computer processors configured to perform an automated refinement operation in which a refined social graph is constructed by augmenting the baseline social graph with predicted links and with inferred labels, the refinement operation comprising:
defining a graph smoothness objective expression having cumulative terms comprising:
a label propagation objective function indicative of label similarity, the label propagation objective function being a function, at least in part, of link closeness; and
a graph construction objective function indicative of link closeness between respective nodes, wherein link closeness is indicative of path-wise proximity of respective nodes, the graph construction objective function being a function, at least in part, of label similarity; and

based at least in part on the objective expression, optimizing the graph smoothness objective expression by performing iterative operations of alternately:
in a label inference iteration, inferring labels using the graph construction objective function and based at least in part on predicted links generated in a previous link prediction iteration; and
in a link prediction iteration, predicting links using the graph construction objective function and based at least in part on inferred labels generated in a previous label inference iteration; and

a recommendation engine comprising one or more computing devices configured to perform automated operations comprising:
generating a recommendation for a particular one of the users based at least in part on automated analysis of the refined social graph; and
causing display of the recommendation on a user device associated with the particular user.