2008 · 127 citations · 19 references
ComputingComputer ScienceData MiningData StructuresDatabasesCoding TheoryData CompressionGraph AnalyticsGraph MiningGraph TheoryLossy Data CompressionGraph EmbeddingsGraph IndexingGraph Representation LearningSpectral Graph AlgorithmsSpectral Graph Learning
Retrieving related graphs containing a query graph from a large graph database is a key issue in many graph-based applications, such as drug discovery and structural pattern recognition. Because sub-graph isomorphism is a NP-complete problem [4], we have to employ a filter-and-verification framework to speed up the search efficiency, that is, using an effective and efficient pruning strategy to filter out the false positives (graphs that are not possible in the results) as many as possible first, then validating the remaining candidates by subgraph isomorphism checking. In this paper, we propose a novel filtering method, a spectral encoding method, i.e. GCoding. Specifically, we assign a signature to each vertex based on its local structures. Then, we generate a spectral graph code by combining all vertex signatures in a graph. Based on spectral graph codes, we derive a necessary condition for sub-graph isomorphism. Then we propose two pruning rules for sub-graph search problem, and prove that they satisfy the no-false-negative requirement (no dismissal in answers). Since graph codes are in numerical space, we take this advantage and conduct efficient filtering over graph codes. Extensive experiments show that GCoding outperforms existing counterpart methods. 1.
19
An Algorithm for Subgraph Isomorphism
J. R. Ullmann · Journal of the ACM · 1976 · 2.3K citations · Full text
gSpan: graph-based substructure pattern mining
Xifeng Yan, Jiawei Han · 2003 · 2K citations
M. Kuramochi, George Karypis · 2002 · 1.1K citations · Full text
Xifeng Yan, Philip S. Yu, Jiawei Han · 2004 · 635 citations