Substructure similarity search in graph databases

By Xifeng Yan, Philip S. Yu, Jiawei Han. 2005

363 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “Metrics such as Graph Edit Distance (GED) Bunke (1983) and Maximum Common Subgraph (MCS) Bunke & Shearer (1998) have been widely adopted in graph database search Yan et al. (2005); Liang & Zhao (2017), are well-defined and general to any domain.”
Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, methodology): “Metrics such as Graph Edit Distance (GED) [Bunke, 1983] and Maximum Common Subgraph (MCS) [Bunke and Shearer, 1998] have been widely adopted in graph database search [Yan et al., 2005; Liang and Zhao, 2017], are well-defined and general to any domain.”
A survey of frequent subgraph mining algorithms (2012, background): “Yan et al. (2005a) indicated that relational pattern mining has three features which serve to diﬀerentiate it from general purpose frequent subgraph mining: (i) the data has distinct vertex labels, (ii) the data comprises very large graphs, and (iii) a focus on frequent patterns with certain…”
Taming verification hardness: an efficient algorithm for testing subgraph isomorphism (2008, methodology): “Authors of gIndex also extend the framework and propose a structural ﬁltering algorithm called Graﬁl to support approximate graph queries [17].”
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach (2017, background): “There has been a rich literature in the modeling and computation of similarity between graphs, such as graph edit distances [15], [21], [32], maximum common subgraphs [23], [9], edge/feature misses [31], [38], [33], [30], graph alignment [25], and graph kernels [19].”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, background): “…computations deﬁned over graph structured data are employed in a wide variety of ﬁelds, from the analysis of molecules for computational biology and chemistry (Gilmer et al., 2017; Yan et al., 2005), to the analysis of knowledge graphs or graph structured parses for natural language understanding.”
Efficient Subgraph Matching on Billion Node Graphs (2012, background): “To avoid excessive joins, another approach is to ﬁnd frequent subgraphs, or frequently queried subgraphs, and index these frequent structures [28].”
Why is Tanimoto index an appropriate choice for fingerprint-based similarity calculations? (2015, methodology): “These metrics are not defined in the same, purely mathematical manner as the other six, rather in an algorithmic approach, which is explained in detail in references [24,25] (Table 2).”
Closure-Tree: An Index Structure for Graph Queries (2006, background): “In a subsequent paper, the authors have extended their idea to partial matches of given queries [12].”
Frequent pattern mining: current status and future directions (2007, methodology): “Taking frequent patterns as features, new strategies to perform structural similarity search were developed such as Graﬁl (Yan et al. 2005) and PIS (Yan et al. 2006).”
GADDI: distance index based subgraph matching in biological networks (2009, background): “As a result, graph database research has attracted a large amount of attention from the database and data mining communities, such as subgraph search in a database of multiple graphs [5, 23, 38, 46, 51, 52, 53, 16], approximate subgraph matching [17, 40, 44, 47, 48, 11], frequent subgraph mining [21”
TALE: A Tool for Approximate Large Graph Matching (2008, methodology): “Grafil [20] and PIS [21] are both built on top of the exact subgraph matching method GIndex.”