Graph querying, graph motif mining and the discovery of clusters

• US 7,933,915 B2
• Filed: 02/27/2007
• Issued: 04/26/2011
• Est. Priority Date: 02/27/2006
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: He, Huahai, Singh, Ambuj Kumar
• Primary Examiner(s): Kim; Charles
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/711,326
• Publication Number:
  US 20070239694A1
• Time in Patent Office: 1,519 Days
• Field of Search: None
• US Class Current: 707/760
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method for analyzing, querying, and mining graph databases using subgraph and similarity querying. An index structure, known as a closure tree, is defined for topological summarization of a set of graphs. In addition, a significance model is created in which the graphs are transformed into histograms of primitive components. Finally, connected substructures or clusters, comprising paths or trees, are detected in networks found in the graph databases using a random walk technique and a repeated random walk technique.

Claims

1. A computer-implemented method for conducting a database graph query, comprising:

(a) obtaining a first database graph and a second database graph, wherein the first database graph and second database graph each have two or more vertices and one or more edges;

(b) mapping the first database graph to the second database graph, wherein;

(i) each vertex in the first database graph has a corresponding vertex in the second database graph; and

(ii) each edge in the first database graph has a corresponding edge in the second database graph;

wherein the mapping step (b) comprises;

(1) computing an initial similarity matrix for the first database graph and the second database graph, wherein each entry of the similarity matrix represents a weight similarity of each vertex of the first database graph to each vertex of the second database graph;

(2) creating a priority queue comprised of vertex pairs based on the weight similarity, wherein each vertex pair comprises a vertex from the first database graph and a most similar vertex from the second database graph based on the weight similarity;

(3) processing the priority queue by;

(i) marking a first vertex pair in the priority queue as matched;

(ii) assigning a higher similarity weight to unmatched vertex pairs that are neighbors to the first vertex pair;

(iii) repeating steps (3)(i) and (3)(ii) for each subsequent vertex pair in the priority queue until all vertices in the first database graph have been marked as matched;

(c) creating a graph closure tree comprised of a union of the first database graph and the second database graph based on the mapping, wherein each node of the graph closure tree comprises a graph closure of the node'"'"'s children and each child of a leaf node comprises a database graph; and

(d) conducting a graph query based on the graph closure tree.

2. The method of claim 1, wherein the mapping comprises extending the first database graph by creating dummy vertices and dummy edges wherein every vertex and every edge of first database graph has a corresponding element in the second database graph.

3. The method of claim 1, wherein the graph closure tree comprises:

a set of closure vertices, wherein each vertex comprises a union of attribute values of each vertex of the first database graph and each corresponding vertex of the second database graph; and

a set of closure edges, wherein each edge comprises a union of attribute values of each edge of the first database graph and each corresponding edge of the second database graph.

4. The method of claim 1, wherein the mapping comprises constructing a bipartite graph between the first database graph and the second database graph, wherein:

a first partition of the bipartite graph comprises vertices from the first database graph;

a second partition of the bipartite graph comprises vertices from the second database graph;

edges of the bipartite graph are formed by connecting the vertices from the first database graph to the vertices in the second database graph; and

defining the mapping as a maximum similarity for each edge and vertex of the bipartite graph.

5. The method of claim 1, wherein the database graph query comprises a subgraph query, wherein the subgraph query comprising determining if a subgraph is sub-isomorphic by:

(a) for each vertex u of the first database graph G1, defining a level-n adjacent subgraph, wherein the level-n adjacent subgraph contains all vertices reachable from the vertex u within a distance of n;

(b) constructing a bipartite graph B for G1 and the second database graph G2, wherein;

(i) vertex sets of the bipartite graph are vertex sets of G1 and G2;

(ii) for any two vertices u ε

G1, v ε

G2, if u is level-n pseudo compatible to v, then (u,v) comprises an edge of B, wherein vertex u is called level-n pseudo compatible to v if a level-n adjacent subgraph of u is level-n sub-isomorphic to that of v, wherein G1 is called level-n sub-isomorphic if every vertex in G1 is matched to a vertex in G2.

6. The method of claim 5, wherein the database graph query comprises.

pruning nodes of the graph closure tree based on the subgraph sub-isomorphism;

and

verifying each level-n sub-isomorphic subgraph for exact subgraph isomorphism.

7. A computer-implemented apparatus for conducting a database graph query, comprising:

(a) means for obtaining a first database graph and a second database graph, wherein the first database graph and second database graph each have two or more vertices and one or more edges;

(b) means for mapping the first database graph to the second database graph, wherein;

(i) each vertex in the first database graph has a corresponding vertex in the second database graph; and

(ii) each edge in the first database graph has a corresponding edge in the second database graph;

wherein the means for mapping (b) comprises;

(1) computing an initial similarity matrix for the first database graph and the second database graph, wherein each entry of the similarity matrix represents a weight similarity of each vertex of the first database graph to each vertex of the second database graph;

(2) creating a priority queue comprised of vertex pairs based on the weight similarity, wherein each vertex pair comprises a vertex from the first database graph and a most similar vertex from the second database graph based on the weight similarity;

(3) processing the priority queue by;

(i) marking a first vertex pair in the priority queue as matched;

(ii) assigning a higher similarity weight to unmatched vertex pairs that are neighbors to the first vertex pair;

(iii) repeating steps (3)(i) and (3)(ii) for each subsequent vertex pair in the priority queue until all vertices in the first database graph have been marked as matched;

(c) means for creating a graph closure tree comprised of a union of the first database graph and the second database graph based on the mapping, wherein each node of the graph closure tree comprises a graph closure of the node'"'"'s children and each child of a leaf node comprises a database graph; and

(d) means for conducting a graph query based on the graph closure tree.

8. The apparatus of claim 7, wherein the means for mapping comprises extending the first database graph by creating dummy vertices and dummy edges wherein every vertex and every edge of first database graph has a corresponding element in the second database graph.

9. The apparatus of claim 7, wherein the graph closure tree comprises:

a set of closure vertices, wherein each vertex comprises a union of attribute values of each vertex of the first database graph and each corresponding vertex of the second database graph; and

a set of closure edges, wherein each edge comprises a union of attribute values of each edge of the first database graph and each corresponding edge of the second database graph.

10. The apparatus of claim 7, wherein the means for mapping comprises constructing a bipartite graph between the first database graph and the second database graph, wherein:

a first partition of the bipartite graph comprises vertices from the first database graph;

a second partition of the bipartite graph comprises vertices from the second database graph;

edges of the bipartite graph are formed by connecting the vertices from the first database graph to the vertices in the second database graph; and

defining the mapping as a maximum similarity for each edge and vertex of the bipartite graph.

11. The apparatus of claim 7, wherein the database graph query comprises a subgraph query, wherein the subgraph query comprising determining if a subgraph is sub-isomorphic by:

(a) for each vertex u of the first database graph G1, defining a level-n adjacent subgraph, wherein the level-n adjacent subgraph contains all vertices reachable from the vertex u within a distance of n;

(b) constructing a bipartite graph B for G1 and the second database graph G2, wherein;

(i) vertex sets of the bipartite graph are vertex sets of G1 and G2;

(ii) for any two vertices u ε

G1, v ε

G2, if u is level-n pseudo compatible to v, then (u,v) comprises an edge of B, wherein vertex u is called level-n pseudo compatible to v if a level-n adjacent subgraph of u is level-n sub-isomorphic to that of v, wherein G1 is called level-n sub-isomorphic if every vertex in G1 is matched to a vertex in G2.

12. The apparatus of claim 11, wherein the database graph query comprises.

pruning nodes of the graph closure tree based on the subgraph sub-isomorphism;

and

verifying each level-n sub-isomorphic subgraph for exact subgraph isomorphism.