Systems and methods for recommending relationships within a graph database

Patent metadata

Field	Value
Publication number	US-10318583-B2
Application number	US-201414212222-A
Country	US
Kind code	B2
Filing date	Mar 14, 2014
Priority date	Mar 15, 2013
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

Systems and methods for relationship recommendations systems in accordance with embodiments of the invention are illustrated. In one embodiment, a relationship recommendation server system includes a processor wherein a relationship recommendation program configures the processor to obtain a graph database including a set of nodes including node attribute data and a set of edges including edge attribute data and describing relationships between nodes in the set of nodes, determine a set of motif data, where the motif data describes at least one subgraph including a subset of the nodes and a subset of the edges within the graph database, obtain a search node, generate additional edges between the search node and a subset of the nodes within the graph database, where the additional edges form subgraphs including the search node that are isomorphic to a subset of the motif data, and recommend relationships based on the generated additional edges.

First claim

What is claimed is:

1. A relationship recommendation server system, comprising:
a processor; and
a memory connected to the processor and configured to store a relationship recommendation program;
wherein the relationship recommendation program provides recommendations for collaborative relationships by directing the processor to:
obtain a graph database, where:
the graph database comprises a set of nodes comprising node attribute data and a set of edges comprising edge attribute data; and
edges in the set of edges describe relationships between nodes in the set of nodes;

determine a set of motif data by:
determining a set of subgraphs of the graph database, a subgraph of the set of subgraphs comprising at least two nodes and at least one edge within the graph database, the at least one edge connecting the at least two nodes;
identifying a subset of the set of subgraphs based on a set of similarity scores and a frequency of matching subgraphs exceeding a threshold, wherein a match is decided using a similarity score based on node attribute data of the at least two nodes and edge attribute data of the at least one edge, and the subgraphs of the identified subset representing beneficial relationship patterns, wherein a beneficial relationship pattern indicates that nodes with certain node attributes have a relationship that yields a pattern of success, the success being dependent on the relationship; and
utilizing the identified subset of subgraphs as the motif data;

obtain a search node n;
determine a subset of motif data using an evaluation function ƒ* defined as
ƒ*( S i )=ƒ( S i ) Z ( S i ),

where ƒ(S i ) maps subgraph S i to a productivity metric, and Z(S i ) represents a statistical significance of S i ;

generate additional edges between the search node n and a subset of the nodes within the graph database, where the additional edges form new subgraphs comprising the search node n that are isomorphic to the subset of the motif data, wherein the additional edges are generated based on node and edge attribute data;
rank the new subgraphs using a ranking function rank n defined as
rank n ( u )=Σ i ƒ*( S i u )/ d ( S i u ,S i ),

where u represents a node distinct from search node n, S i u represents a set of subgraphs including S i and the new subgraphs, and d(S i u ,S i ) represents a similarity score for isomorphic subgraphs S i u and S i ;

and
recommend relationships based on the generated additional edges and similarity of the subgraphs resulting from the generated additional edges to beneficial relationship patterns.

2. The relationship recommendation server system of claim 1 , wherein the relationship recommendation application further configures the processor to augment the graph database by incorporating a portion of the additional edges into the set of edges.

3. The relationship recommendation system of claim 1 , wherein:
the relationship recommendation server system further comprises a network interface connected to the processor and configured to communicate via a network; and
the relationship recommendation application further configures the processor to obtain source data using the network interface, where the source data describes a collaborative environment comprising a set of entities and a set of relationships describing the relationships between the entities in the set of entities.

4. The relationship recommendation server system of claim 3 , wherein the relationship recommendation application further configures the processor to generate the graph database based on the obtained source data by:
generating a set of node data based on the set of entities in the source data;
generating a set of edge data based on the set of relationships in the source data, where an edge in the set of edge data comprises a relationship between nodes in the set of node data; and
creating a graph database comprising the set of node data and the set of edge data.

5. The relationship recommendation server system of claim 3 , wherein the relationship recommendation application further configures the processor to augment the graph database based on the obtained source data by:
generating a set of additional node data based on the set of entities in the source data;
generating a set of additional edge data based on the set of relationships in the source data, where an edge in the set of additional edge data comprises a relationship between nodes; and
incorporating the set of additional node data and the set of additional edge data into the obtained graph database.

6. The relationship recommendation server system of claim 1 , wherein the threshold value is based on the statistical significance of the occurrence of the subset of the set of subgraphs within the graph database.

7. The relationship recommendation server system of claim 1 , wherein the relationship recommendation application configures the processor to identify a subset of the set of subgraphs occurring with a frequency exceeding a threshold value by:
calculating the frequency with which the subgraphs in the set of subgraphs occur within the graph database;
calculating the frequency with which the subgraphs in the set of subgraphs occur within a training graph database separate from the graph database; and
determining the statistical significance of the subgraphs in the set of subgraphs based on the frequency with which the subgraphs occur within the graph database, the training graph database, and the standard deviation of the occurrences.

8. The relationship recommendation server system of claim 1 , wherein the relationship recommendation application configures the processor to:
identify subgraphs within the graph database that are isomorphic to the motif data; and
include the isomorphic subgraphs within the motif data.

9. The relationship recommendation server system of claim 8 , wherein the relationship recommendation application configures the processor to identify subgraphs isomorphic to a piece of motif data by:
generating isomorphic node data based on the attributes of the nodes within the subgraph;
generating isomorphic edge data based on the attributes of the edge within the subgraph;
generating isomorphic motif node data based on the attributes of the nodes within the piece of motif data;
generating isomorphic motif edge data based on the attributes of the edges within the piece of motif data; and
generating an isomorphic similarity score for the subgraphs relative to the piece of motif data based on the isomorphic node data, the isomorphic edge data, the isomorphic motif node data, and the isomorphic motif edge data.

10. The relationship recommendation server system of claim 9 , wherein the identification of a subgraph included in the set of subgraphs is based on the isomorphic similarity score and a statistical significance of the subgraph within the graph database.

11. The relationship recommendation server system of claim 1 , wherein the relationship recommendation application further configures the processor to:
recommend those relationships corresponding to the additional edges forming subgraphs that have a rank exceeding a threshold value.

12. The relationship recommendation server system of claim 11 , wherein the relationship recommendation application configures the processor to rank a subgraph based on the attributes of the set of node data and the attributes of the set of edge data for the set of node data and the set of edge data in the subgraph.

13. The relationship recommendation server system of claim 11 , wherein the recommended relationship corresponds to the subgraph having the highest

Assignees

• Univ Stanford
• Univ Leland Stanford Junior

Inventors

• Feinberg Evan
• Clancy Julien

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title