Graph querying, graph motif mining and the discovery of clusters
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 4, 5, 6)
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. - View Dependent Claims (8, 9, 10, 11, 12)
verifying each level-n sub-isomorphic subgraph for exact subgraph isomorphism.
-
Specification