Social graph refinement

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.

A non-transitory computer readable storage medium having stored thereon instructions for causing a machine, when executing the instructions, to perform operations comprising:

• accessing a baseline social graph modeling 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;
• dynamically refining the baseline social graph by augmenting the baseline social graph with predicted links and with inferred labels, thereby constructing a refined social graph, 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;
• 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.