Taming verification hardness: an efficient algorithm for testing subgraph isomorphism
The DOI matches its Crossref record; 28 of the 29 references it cites were found in a registry or an index.
Abstract
Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering -and- verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Although there are graph-based approaches that are potentially less vulnerable to such attacks, they are not feasible in practice [24] due to the NP nature of determining subgraph isomorphism [25,29,45].”
From Detecting Automatic Software Plagiarism via Token Sequence Normalization (2024) · cites this paper as [45]
Citations
Cites
(1979) · Cited by 43,841
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277 · cited 4×
“Comparing to the well adopted Ullman’s algorithm [13], QuickSI achieves up to 1-4 orders of magnitude speed-up.”
MethodInfluentialData Structures and Algorithms
(2003) · Series on software engineering and knowledge engineering · doi:10.1142/9789812791245 · Cited by 2,117
gSpan: graph-based substructure pattern mining
Yan, X., & Han, J. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1184038 · Cited by 2,013 · cited 1×
“To overcome this problem, some recent work uses more complex and selective sub-structures as index features, mean-while adopt data mining techniques [15, 19] to improve performance and to reduce index size.”
MethodAn Automatic Method for Solving Discrete Programming Problems
Land, A. H., & Doig, A. G. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_5 · Cited by 1,988
An Automatic Method of Solving Discrete Programming Problems
Land, A. H., & Doig, A. G. (1960) · Econometrica · doi:10.2307/1910129 · Cited by 1,942
Data Structures and Algorithms
Wirth, N. (1984) · Scientific American · doi:10.1038/scientificamerican0984-60 · Cited by 1,418
Proceedings 2001 IEEE International Conference on Data Mining
(2001) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989492 · Cited by 768
Proceedings of the International Conference on Very Large Data Bases
Kerr, D. S. (1975) · ACM eBooks · Cited by 701
Graph indexing: a frequent structure-based approach
Yan, X., Yu, P. S., & Han, J. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007607 · Cited by 637 · cited 10×
“De-fault real dataset is a subset containing 10K graphs, which is firstly used in [16] and can be downloaded from http://www. xifengyan.net/software.htm .”
BackgroundMethodInfluentialFortney, J. P. (2020) · Discrete Mathematics for Computer Science · doi:10.1201/9781003091479-1 · Cited by 428
Substructure similarity search in graph databases
Yan, X., Yu, P. S., & Han, J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066244 · Cited by 314 · cited 1×
“Authors of gIndex also extend the framework and propose a structural filtering algorithm called Grafil to support approximate graph queries [17].”
MethodClosure-Tree: An Index Structure for Graph Queries
He, H., & Singh, A. K. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.37 · Cited by 293 · cited 3×
“More recently, He and Singh propose a clustering-based index called Closure-tree to support both subgraph queries and similarity queries [9].”
BackgroundMethodFg-index: towards verification-free query processing on graph databases
Cheng, J., Ke, Y., Ng, W., & Lu, A. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247574 · Cited by 265 · cited 10×
“In [4], Cheng et al. propose a new paradigm, FG-Index, with the aim to use index only to process a subgraph containment query; that is, verification free.”
BackgroundMethodInfluentialGraph indexing: tree + delta <= graph
Zhao, P., Yu, J. X., & Yu, P. S. (2007) · Very Large Data Bases · Cited by 260
Self-citationEfficient matching and indexing of graph models in content-based retrieval
Berretti, S., Del Bimbo, A., & Vicario, E. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.954600 · Cited by 225 · cited 1×
“[3] propose a metric indexing schema for contentbased image retrieval.”
BackgroundGraphGrep: A fast and universal method for querying graphs
Giugno, R., & Shasha, D. (2003) · Object recognition supported by user interaction for service robots · doi:10.1109/icpr.2002.1048250 · Cited by 225 · cited 2×
“Shasha et al. [8] pro-0 Graph-Grep enumerates all paths within a threshold length as index features.”
BackgroundData structures and algorithms
Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983) · CERN Document Server (European Organization for Nuclear Research) · Cited by 214
TreePi: A Novel Graph Indexing Method
Zhang, S., Hu, M., & Yang, J. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.368955 · Cited by 191 · cited 5×
“Two recent techniques, TreePi [18] and (Tree+∆) [20] try to index frequent and discriminative subtrees rather than subgraphs, as trees can be manipulated efficiently while preserving most structural information of the original graphs.”
BackgroundMethodInfluentialGraph Database Indexing Using Structured Graph Decomposition
Williams, D. W., Huan, J., & Wang, W. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.368956 · Cited by 164 · cited 1×
“Williams et al. [14] develop a tree-structured index based on graph decomposition for graphs with limited sizes.”
BackgroundGString: A Novel Approach for Efficient Search in Graph Databases
Jiang, H., Wang, H., Yu, P. S., & Zhou, S. (2007) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2007.367902 · Cited by 158 · cited 1×
“There are other literatures related to graph queries on spe-cific graph databases. gString [10] is developed on chemical compound databases.”
BackgroundA decision tree approach to graph and subgraph isomorphism detection
Messmer, B., & Horst Bunke, A. (1999) · Pattern Recognition · doi:10.1016/s0031-3203(98)90142-x · Cited by 151 · cited 1×
“In the category of non-feature-based index, Messmer et al. propose novel clutering-structured mechanism and decision-tree approach for indexing graphs for isomorphism and sub-graph isomorphism [12].”
BackgroundA novel spectral coding in a large graph database
Zou, L., Chen, L., Yu, J. X., & Lu, Y. (2008) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/1353343.1353369 · Cited by 145 · cited 1×
“And a novel spectral graph coding technique named GCoding is proposed for the sub-graph search problem in [21].”
MethodSelf-citationCanonical forms for labelled trees and their applications in frequent subtree mining
Chi, Y., Yang, Y., & Muntz, R. R. (2004) · Knowledge and Information Systems · doi:10.1007/s10115-004-0180-7 · Cited by 102 · cited 1×
“On the other hand, computing a canonical form of trees can be done in O ( deg max k log k ) [5], where k and deg max are the number of vertices and the maximal vertex degree in the tree, respectively.”
MethodGraph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
Arvind, V., & Köbler, J. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46541-3_36 · Cited by 41 · cited 1×
“It is well known that the graph isomorphism problem is open [2]; there is no polynomial algorithm developed nor proof of NP-complete.”
BackgroundFast Frequent Free Tree Mining in Graph Databases
Zhao, P., & Yu, J. X. (2007) · World Wide Web · doi:10.1007/s11280-007-0031-z · Cited by 17
Self-citation(1990)
Research works printed but not linked: 2
- 10.5555/646514.695831 · doi:10.5555/646514.695831
- 10.5555/2993947.2993981 · doi:10.5555/2993947.2993981
Cited by
Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases
Han, W.-S., Lee, J., & Lee, J.-H. (2013) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2463676.2465300 · Cited by 467
“In contrast, in those query/data sets, QuickSI [12] often outperforms more recent competitors, such as GraphQL and SPath, when it chooses a good matching order.”
BackgroundMethodInfluentialOn graph query optimization in large networks
Zhao, P., & Han, J. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920887 · Cited by 427
Efficient Subgraph Matching by Postponing Cartesian Products
Bi, F., Chang, L., Lin, X., Qin, L., & Zhang, W. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2915236 · Cited by 395
Self-citationAn in-depth comparison of subgraph isomorphism algorithms in graph databases
Lee, J., Han, W.-S., Kasperovičs, R., & Lee, J.-H. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2535568.2448946 · Cited by 345
“The AIDS dataset was used in [11].”
BackgroundMethodInfluentialCECI: Compact Embedding Cluster Index for Scalable Subgraph Matching
Bhattarai, B. D., Liu, H., & Huang, H. H. (2019) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3299869.3300086 · Cited by 222
Metadata
- Authors
- Shang, H., Zhang, Y., Lin, X., & Yu, J. X.
- Affiliations
- UNSW Sydney (AU)
- Chinese University of Hong Kong (HK)
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2008-08
- Volume
- 1
- Issue
- 1
- Pages
- 364-375
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2140840007
- Cited by
- 401
- References
- 29
- Citations by year
- 2026: 13 · 2025: 29 · 2024: 32 · 2023: 22 · 2022: 28 · 2021: 38 · 2020: 25 · 2019: 27 · 2018: 24 · 2017: 24 · 2016: 23 · 2015: 24 · 2014: 18 · 2013: 15 · 2012: 23
- FWCI
- 17.28
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Proceedings of the VLDB Endowment (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- subgraph isomorphism, graph retrieval, NP-hardness, scalability, query graph
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.