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
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
Items 201–300 of 494
Subgraph Matching: A New Decomposition Based Approach
Li, Q., Yu, J. X., & He, Z. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3749646.3749693 · Cited by 10
“To select a good matching order, various heuristics based on prioritizing dense nodes in the pattern graph and nodes with infrequent labels have been proposed [5, 18, 19, 28, 29, 37, 42, 45, 47].”
Self-citationContinuous multi-query optimization for subgraph matching over dynamic graphs
Wang, X., Zhang, Q., Guo, D., & Zhao, X. H. (2022) · Semantic Web · doi:10.3233/sw-212864 · Cited by 10
“While this problem is NP-hard, in recent years, many algorithm have been proposed to solve it in a reasonable time for real datasets, such as VF2 [4], GraphQL [11], TurBOiSO [10], QuickSI [26].”
BackgroundgSWORD: GPU-accelerated Sampling for Subgraph Counting
Ye, C., Li, Y., Sun, S., & Guo, W. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3639288 · Cited by 10
Top-K Graph Pattern Matching: A Twig Query Approach
Zeng, X., Cheng, J., Yu, J. X., & Feng, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32281-5_28 · Cited by 10
Self-citationOn isomorphic matching of large disk-resident graphs using an XQuery engine
Rivero, C. R., & Jamil, H. M. (2014) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2014.6818296 · Cited by 10
“QuickSI [11] relies on the concept of QI-Sequence, which is a sequence that represents a rooted spanning tree for the input query graph.”
MethodEfficient Probabilistic Supergraph Search
Zhang, W., Lin, X., Zhang, Y., Zhu, K., & Zhu, G. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2499201 · Cited by 10
Self-citationA privacy policy conflict detection method for multi-owner privacy data protection
Ren, Y., Cheng, F., Peng, Z., Huang, X., & Song, W. (2010) · Electronic Commerce Research · doi:10.1007/s10660-010-9067-8 · Cited by 10
Mining Weighted Frequent Sub-graphs with Weight and Support Affinities
Lee, G., & Yun, U. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-35455-7_21 · Cited by 10
“Accordingly, researchers with an interest for graph mining have been increased, and a variety of studies for graph mining have been proposed continually, such as [1, 10, 11, 12, 15].”
BackgroundCarletti, V. (2016) · HAL · Cited by 10
Detecting Automatic Software Plagiarism via Token Sequence Normalization
Sağlam, T., Brödel, M., Schmid, L., & Hahner, S. (2024) · Proceedings of the IEEE/ACM 46th International Conference on Software Engineering · doi:10.1145/3597503.3639192 · Cited by 9
Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach
Guo, Q., Yang, J., Zhang, W., Wang, H., Zhang, Y., & Lin, X. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3742728.3742758 · Cited by 9
Self-citationChatGraph: Chat with Your Graphs
Peng, Y., Lin, S., Chen, Q., Wang, S., Xu, L., Ren, X., Li, Y., & Xu, J. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00424 · Cited by 9
“Traditional approaches to interact with graph data include the declarative language ( e.g. , SPARQL [1] and GraphQL [2]) and the clicking-and-dragging interface ( e.g. , GBLENDER [3] and CATAPULT [4]).”
Towards a Converged Relational-Graph Optimization Framework
Lou, Y., Lai, L., Lyu, B., Yang, Y., Zhou, X., Yu, W., Zhang, Y., & Zhou, J. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3698828 · Cited by 9
Self-citationZou, Q., & Lu, C. (2022) · IEEE Access · doi:10.1109/access.2022.3155520 · Cited by 9
“For examples, the Spath algorithm proposed by Shang et al. [26] improves the ability and efficiency of screening candidate nodes by introducing the nearest distance centered on nodes as a constraint.”
MethodHyGraph: a subgraph isomorphism algorithm for efficiently querying big graph databases
Asiler, M., Yazıcı, A., & George, R. (2022) · Journal Of Big Data · doi:10.1186/s40537-022-00589-0 · Cited by 9
“VF2 [14], VF3 [15], QuickSI [16], GADDI [17], GraphQL [18], SPath [19] belong to this type of”
BackgroundInfluentialChiSeL: graph similarity search using chi-squared statistics in large probabilistic graphs
Agarwal, S., Dutta, S., & Bhattacharya, A. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3401960.3401964 · Cited by 9
An Experimental Evaluation of a Bounded Expansion Algorithmic PipelinePreprint
O’Brien, M. P., & Sullivan, B. D. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1712.06690 · Cited by 9
“Other subclasses of algorithms have focused on indexing graph databases [21, 11] or creating data structures for parallel computation [23].”
BackgroundTowards Efficient Simulation-Based Constrained Temporal Graph Pattern Matching
Zhang, T., Cai, X., Chen, L., Yang, Z., Gao, Y., Cao, B., & Fan, J. (2022) · World Wide Web · doi:10.1007/s11280-024-01259-2 · Cited by 8
Continuous matching of evolving patterns over dynamic graph data
Zhang, Q., Guo, D., Zhao, X. H., & Wang, X. (2021) · World Wide Web · doi:10.1007/s11280-020-00860-5 · Cited by 8
“QuickSI [12] proposes to generate a matching order based on the infrequent-labels first strategy.”
BackgroundMethodInfluentialGStar: an efficient framework for answering top-k star queries on billion-node knowledge graphs
Jin, J., Luo, J., Khemmarat, S., Dong, F., & Gao, L. (2018) · World Wide Web · doi:10.1007/s11280-018-0611-0 · Cited by 8
Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs
Shan, X., Jia, C., Ding, L., Ding, X., & Song, B. (2019) · Information · doi:10.3390/info10020061 · Cited by 8
Scalable Pattern Matching in Metadata Graphs via Constraint Checking
Reza, T. A., Halawa, H. H., Ripeanu, M., Sanders, G., & Pearce, R. (2021) · ACM Transactions on Parallel Computing · doi:10.1145/3434391 · Cited by 8
“(i) First, the traditionally used graph exploration techniques [Han et al. 2014; P. Cordella et al. 2004; Shang et al. 2008; Ullmann 1976] generally attempt to enumerate all matches through explicit search.”
BackgroundMethodSubstructure similarity search for engineering service-based systems
Wu, J., Guo, X. L., Yang, G., Wu, S., & Wu, J. (2020) · Journal of Systems and Software · doi:10.1016/j.jss.2020.110569 · Cited by 8
Compressed feature-based filtering and verification approach for subgraph search
Gouda, K., & Hassaan, M. (2013) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/2452376.2452411 · Cited by 8
“FG-Index and SwiftIndex are based on feature selection, whereas CT-Index exhaustively enumerates trees and cycles of limited size.”
BackgroundMethodInfluentialApproximating the minimum hub cover problem on planar graphs
Yelbay, B., Birbil, Ş. İ., Bülbül, K., & Jamil, H. M. (2015) · Optimization Letters · doi:10.1007/s11590-015-0876-5 · Cited by 8
“Among these, we have studies applying index-based searching [14,16], graph decomposition methods [9] and using new data structures and graph representations keeping topological data [19].”
MethodCompact Neighborhood Index for Subgraph Queries in Massive GraphsPreprint
Nabti, C., Mecharnia, T., Boukhetta, S. E., Seba, H., & Amrouche, K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.05547 · Cited by 8
“The experimental results show that our approach is efficient and scalable.”
BackgroundMethodKnowledge graph reasoning and its applications: A pathway towards neural symbolic AI
Liu, L. (2024) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 8
A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]
Jiang, H., Pandey, S., & Liu, H. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3771791 · Cited by 7
Enhanced subgraph matching for large graphs using candidate region-based decomposition and ordering
Ansari, Z. A., Parwez, M. A., Thoker, I. R., & Jahiruddin (2023) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2023.101694 · Cited by 7
“To address the restrictions of only considering vertices and edges, SPath (Zhao and Han, 2010) algorithm offers to generate a matching order based on the infrequent-paths first technique (Shang et al., 2008).”
InfluentialFASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs
Su, X., Lin, Y., & Zou, L. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00163 · Cited by 7
LaSaS: an Aggregated Search based Graph Matching Approach
Echbarthi, G., & Kheddouci, H. (2017) · Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering · doi:10.18293/seke2017-046 · Cited by 7
“Exact subgraph matching finds exact answers to the query via graph isomorphism [7], [6].”
BackgroundSupergraph Search in Graph Databases via Hierarchical Feature-Tree
Lyu, B., Qin, L., Lin, X., Chang, L., & Yu, J. X. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2833124 · Cited by 7
“Existing algorithms include Ullmann [20], VF2 [21], gIndex [1], TreePi [22], Tree+d [3], Fg-index [2], GString [4], QuickSI [5], GraphQL [23], TurboIso [24], etc.”
BackgroundMethodSelf-citationHybrid search plan generation for generalized graph pattern matching
Barkowsky, M., & Giese, H. (2020) · Journal of Logical and Algebraic Methods in Programming · doi:10.1016/j.jlamp.2020.100563 · Cited by 7
GRAPES-DD: exploiting decision diagrams for index-driven search in biological graph databases
Licheri, N., Bonnici, V., Beccuti, M., & Giugno, R. (2021) · BMC Bioinformatics · doi:10.1186/s12859-021-04129-0 · Cited by 7
Finding patterns in an unknown graph
Stern, R., Kalech, M., & Felner, A. (2012) · AI Communications · doi:10.3233/aic-2012-0532 · Cited by 7
“fective in practice [49], as well as more efficient algo-”
BackgroundJamil, H. M. (2012) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2012.49 · Cited by 7
“For example, the well known VFLib [9], [10] and Ullmann’s algorithm [11] represent edges as adjacency matrices, GraphQL [12] represents graphs as XML documents, IsoSearch [13], [14] uses a predicate representation for edges, and QuickSI [15] uses a linked data structure to represent graphs.”
MethodGpSense: A GPU-Friendly Method for Commonsense Subgraph Matching in Massively Parallel Architectures
Tran, H.-N., & Cambria, E. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-75477-2_39 · Cited by 7
“We evaluate the performance of GpSense in comparison with state-of-the-art subgraph matching algorithms, including VF2 [8], QuickSI (QSI) [22], GraphQL (GQL) [12] and TurboISO [9].”
MethodA novel subgraph querying method based on paths and spectra
Zhu, L., Yao, Y., Wang, Y., Hei, X., Zhao, Q., Ji, W., & Yao, Q. (2018) · Neural Computing and Applications · doi:10.1007/s00521-018-3837-y · Cited by 7
“There are some data mining-based methods, such as gIndex [13], FGIndex [15], TreePi [16], Tree ? Delta [17] and QuickSI [18].”
Methodprague: A Practical Framework for Blending Visual Subgraph Query Formulation and Query Processing
Jin, C., Bhowmick, S. S., Choi, B. K. K., & Zhou, S. (n.d.) · Cited by 7
D2Match: Leveraging Deep Learning and Degeneracy for Subgraph MatchingPreprint
Liu, X., Zhang, L., Sun, J., Yang, Y., & Yang, H. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.06380 · Cited by 7
“To alleviate the computational cost, researchers have employed approximate techniques to seek inexact solutions (Mongiov`ı et al., 2010; Yan et al., 2005; Shang et al., 2008), which yield suboptimal matchings.”
BB-Graph: A Subgraph Isomorphism Algorithm for Efficiently Querying Big Graph DatabasesPreprint
Asiler, M., & Yazıcı, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.06654 · Cited by 7
“VF2 [14], QuickSI [15], GADDI [16], GraphQL [17], SPath [18] belong to this type of algorithms.”
BackgroundInfluentialFast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach
Yu, K., Wang, K., Long, C., Lakshmanan, L. V. S., & Cheng, R. C. K. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3725404 · Cited by 6
Consistent Subgraph Matching over Large Graphs
Yuan, Y., Ma, D., Zhang, A., & Wang, G. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00235 · Cited by 6
Yang, X. (2023) · IntechOpen eBooks · doi:10.5772/intechopen.112232 · Cited by 6
Yazıcı, A., & Taşkomaz, E. (2024) · Information Systems · doi:10.1016/j.is.2024.102401 · Cited by 6
VF2-PS: Parallel and Scalable Subgraph Monomorphism in Arachne
Dindoost, M., Rodriguez, O. A., Bagchi, S., Pauliuchenka, P., Du, Z., & Bader, D. A. (2024) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec62836.2024.10938454 · Cited by 6
Improving Distribued Subgraph Matching Algorithm on Timely Dataflow
Lai, Z., Yang, Z., & Lai, L. (2019) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2019.000-2 · Cited by 6
“Subsequent algorithms such as VF2 [13], QuickSI [33], TurboISO [18] and CFL [6] are developed to further improve the performance by designing better pruning rules and/or indexing structures.”
MethodEfficient access methods for very large distributed graph databases
Luaces, D., Viqueira, J. R. R., Cotos, J. M., & Flores, J. C. (2021) · Information Sciences · doi:10.1016/j.ins.2021.05.047 · Cited by 6
Nabhan, A. R., & Sarkar, I. N. (2013) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2013.10.011 · Cited by 6
“Modeling this probability value directly can be hard, mainly because: (1) it is a computationally non-trivial task to determine if two graph instances are equal using the graph isomorphism test [19,41]; and (2) due to the data sparseness problem (it is usually hard to find more than one isomorphic instance of the same…”
BackgroundTwo parallel versions of VF3: Performance analysis on a wide database of graphs
Carletti, V., Foggia, P., Percannella, G., Ritrovato, P., & Vento, M. (2021) · Pattern Recognition Letters · doi:10.1016/j.patrec.2021.03.018 · Cited by 6
GNN-based Anchor Embedding for Efficient Exact Subgraph MatchingPreprint
Yang, B. T., Zou, Z., & Ye, J. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.00031 · Cited by 6
GCSM: GPU-Accelerated Continuous Subgraph Matching for Large Graphs
Wei, Y., & Jiang, P. (2024) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps57955.2024.00097 · Cited by 5
Envisage: Towards Expressive Visual Graph Querying
Wen, X., Fu, Q., Han, S., Guo, Y., Liu, J. K., & Wang, Y. (2025) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2025.3634234 · Cited by 5
“Many graph databases integrate these techniques [22,23,46,47,50,65], with GraphQL [23] improving efficiency through local pruning and global refinement.”
HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs
Zhang, L., Zhang, Z., Wang, G., Yuan, Y., Zhao, S., & Xu, J. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3203856 · Cited by 5
“The QuickSI algorithm [30] considers to match the vertices with the infrequent”
MethodBenson, R. L., Yadavalli, S. S., & Stamatakis, M. (2023) · The Journal of Physical Chemistry A · doi:10.1021/acs.jpca.3c05581 · Cited by 5
“82 For systems with adsorbate lateral interactions, another key component of the simulation is calculating the lattice state-dependent activation energies using eqs 3 and 4.”
BackgroundMethodAn Efficient Index-Based Algorithm for Exact Subgraph Isomorphism on Bipartite Graphs
Koca, M. B., & Sevilgen, F. E. (2024) · Scientific Research Communications · doi:10.52460/src.2024.005 · Cited by 5
Experimental Clarification of Some Issues in Subgraph Isomorphism Algorithms
Ren, X., Wang, J., Franciscus, N., & Stantić, B. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-75420-8_7 · Cited by 5
Efficient parallel edge-centric approach for relaxed graph pattern matching
Bouhenni, S., Yahiaoui, S., Nouali‐Taboudjemat, N., & Kheddouci, H. (2021) · The Journal of Supercomputing · doi:10.1007/s11227-021-03938-7 · Cited by 5
Xian, Z., Xiao, G., Duan, M., Chen, Y., & Li, K. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3217825 · Cited by 5
“It enumerates all results by searching the data graph G, such as RI [12], QuickSI [19], VF2++ [20], etc.”
MethodFast processing of graph queries on a large database of small and medium-sized data graphs
Pal, D., Rao, P. R., Slavov, V., & Katib, A. (2016) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2016.04.002 · Cited by 5
“Previous approaches commonly leverage frequent pattern mining to extract features from graphs (e.g., trees, subgraphs) for indexing (e.g., gIndex [49], Tree+∆ [56], QuickSI [39], FG-index [12, 13]).”
InfluentialA Lattice-based Graph Index for Subgraph Search.
Yuan, D., & Mitra, P. (2011) · International Workshop on the Web and Databases · Cited by 5
A Graph Matching Approach Based on Aggregated Search
Echbarthi, G., & Kheddouci, H. (2017) · International Conference on Signal-Image Technology & Internet-Based Systems (SITIS) · doi:10.1109/sitis.2017.68 · Cited by 5
“Exact subgraph matching finds exact answers to the query via graph isomorphism [7], [6].”
BackgroundSecure and Reliable Data Outsourcing in Cloud Computing
Cao, N. (2012) · Digital WPI · Cited by 5
An Efficient Approach for Mining Frequent Sub-graphs with Support Affinities
Lee, G., & Yun, U. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32645-5_66 · Cited by 5
Large Scale Graph Matching(LSGM): Techniques, Tools, Applications and Challenges
Mahmood, A., Farooq, H., & Ferzund, J. (2017) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2017.080465 · Cited by 5
“5) O(mn5) QuickSi[32] 2008 Swift Indexing Exact In-Memory O(SEQq + g) Polynomial GADDI[33] 2009 NH-Indexing Exact In-Memory O(n(2)) O(n(3)) DistanceJoin[34] 2009 Frequent Subgraph Inexact In-Memory O(n) O(n)”
BackgroundEfficient Supergraph Search Using Graph Coding
Shun, I. M. A. I., & Inokuchi, A. (2019) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2019edp7011 · Cited by 5
“To do so, we use canonical codes to represent graphs in the database [9], [17].”
BackgroundMethodEnhancing Investigative Pattern Detection via Inexact Matching and Graph Databases
Muramudalige, S. R., Hung, B. W. K., Jayasumana, A. P., Ray, I., & Klausen, J. (2021) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2021.3073145 · Cited by 5
“Matching order strategies and effective pruning rules are further enhanced in VF2 [35], QuickSI [36], and GADDI [37].”
BackgroundTrade-offs Computing Minimum Hub Cover toward Optimized Graph Query ProcessingPreprint
Yelbay, B., Birbil, Ş. İ., Bülbül, K., & Jamil, H. M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.1626 · Cited by 5
“Techniques such as GraphQL [3], QuickSI [4] and earlier research such as VFLib [5] and Ullmann [6] fall in the former category while TALE [7], and SAPPER [8] are representative of the latter.”
MethodMitigating Automated Obfuscation Attacks on Software Plagiarism Detection Systems
Sağlam, T. (2025) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000179018 · Cited by 5
Subgraph Isomorphism Search In Massive Graph Data
Nabti, C. E. (2017) · theses.fr (ABES) · doi:10.70675/4436eb34zd9d8z4df2zb413zaa402e87331c · Cited by 5
“For instance, in [33], authors implements five algorithms VF2 [41], QuickSI[45], GraphQL [25], GADDI [55], and SPath [57] in a common framework.”
InfluentialHuan, C., Zhang, H., Liu, Y., Chen, L., Wang, X., Jiang, Y., Ma, S., & Wu, Y. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00082 · Cited by 4
“Current solutions for handling topological constraints fall into two main categories: 1) Algorithm-level approaches, such as QuickSI [30], VF2++ [31], Circinus [32], and CECI [33], and 2) System-level approaches, such as GraphPi [27] and GraphZero [34].”
InfluentialOptMatch: An Efficient and Generic Neural Network-Assisted Subgraph Matching Approach
Hou, W., Zhao, X., & Tang, B. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00304 · Cited by 4
RSM: Reinforced Subgraph Matching Framework with Fine-grained Operation based Search Plan
Li, Z., Dou, Y., Li, Y., Chen, X., & Zhang, C. (2025) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3701551.3703516 · Cited by 4
VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality
Agarwal, S., Dutta, S., & Bhattacharya, A. (2021) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3459637.3482217 · Cited by 4
“Since graph isomorphism is quasi-polynomial [4] and subgraph isomorphism is NP-complete [12], earlier works on exact graph matching such as Swift-Index [42], VF2 [13, 26], PathBlast [28], SAGA [47], IsoRank [44] and GraphGrep [20] to name a few, explored pruning and indexing techniques.”
BackgroundMethodStable Subgraph Isomorphism Search in Temporal Networks
Zhang, Q., Li, R.-H., Qin, H., Wang, G., Zhang, Z., & Yuan, Y. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3175800 · Cited by 4
“QuickSI [24] created a matching order based on an infre-quent-labels first strategy.”
MethodInfluentialWings: Efficient Online Multiple Graph Pattern Matching
Jiang, G., Zhao, Y., Li, Y., Liu, Z., Jin, T., Zheng, W., Li, B., & Cheng, J. S.-C. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00260 · Cited by 4
ArcMatch: high-performance subgraph matching for labeled graphs by exploiting edge domains
Bonnici, V., Grasso, R., Micale, G., Maria, A. D., Shasha, D. E., Pulvirenti, A., & Giugno, R. (2024) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-024-01061-8 · Cited by 4
Subgraph Matching with Diversity Handling and Its Applications to PCB Placement
Chen, C., Lin, H., Su, M., He, H., Chen, J., & Zhu, Z. (2024) · International Symposium of Electronics Design Automation (ISEDA) · doi:10.1109/iseda62518.2024.10617495 · Cited by 4
“For example, CFL Match [2], VF series algorithms [5] [4] [3], TurboISO [7], GraphQL [8], QuickSI [12], SPath [14], DAF [6], L2G [1], etc.”
MethodAccurate Sampling-Based Cardinality Estimation for Complex Graph Queries
Hu, P., & Motik, B. (2024) · ACM Transactions on Database Systems · doi:10.1145/3689209 · Cited by 4
Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention
Nguyen, Q. D., Nguyen, T. T., Jo, J. H., Poux, F., Anirban, S., & Quan, T. (2024) · IEEE Access · doi:10.1109/access.2024.3458050 · Cited by 4
“• QuickSI [10] employs QI-Sequence to constrain the search space, determining order based on feature frequencies.”
BackgroundMethodInfluentialUnified-memory-based hybrid processing for partition-oriented subgraph matching on GPU
Chen, J., Wang, Q., Gu, Y., Li, C., & Yu, G. (2021) · World Wide Web · doi:10.1007/s11280-021-00952-w · Cited by 4
“VF2 [2] and QuickSI [28] propose the joining order selection method to improve the performance.”
MethodEfficiently Computing Homomorphic Matches of Hybrid Pattern Queries on Large Graphs
Wu, X., Theodoratos, D., Skoutas, D., & Lan, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-27520-4_20 · Cited by 4
A Novel Approach for Subgraph Isomorphism Problem on Bipartite Graphs
Koca, M. B., & Sevilgen, F. E. (2019) · Signal Processing and Communications Applications Conference (SIU) · doi:10.1109/siu.2019.8806332 · Cited by 4
“Ullmann’ın algoritmasının; VF2 [5], QuickSI [6], GraphQL [7], Turboiso [8] gibi birçok varyasyonu geliştirilmiş ve yayımlanmıştır.”
Partition-Oriented Subgraph Matching on GPU
Chen, J., Gu, Y., Wang, Q., Li, C., & Yu, G. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-60259-8_5 · Cited by 4
Similar Supergraph Search Based on Graph Edit Distance
Yamada, M., & Inokuchi, A. (2021) · Algorithms · doi:10.3390/a14080225 · Cited by 4
Efficient algorithms for supergraph query processing on graph databases
Zhang, S., Gao, X., Wu, W., Li, J., & Gao, H. (2009) · Journal of Combinatorial Optimization · doi:10.1007/s10878-009-9221-1 · Cited by 4
Robust Cardinality Estimation for Subgraph Isomorphism Queries on Property Graphs
Paradies, M., Vasilyeva, E., Mocan, A., & Lehner, W. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-41576-5_14 · Cited by 4
Multidisciplinary model transformation through simplified intermediate representations
Cole, B. F., & Dinkel, K. (2016) · IEEE Aerospace Conference (AERO) · doi:10.1109/aero.2016.7500656 · Cited by 4
“That exemplar is then compared to the full model to extract uses of the pattern using the Quick Subgraph Isomorphism algorithm [8].”
MethodAnswering Subgraph Queries over Large Graphs
Zheng, W., Zou, L., & Zhao, D. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23535-1_34 · Cited by 4
“Most of these algorithms utilize the paths, trees or subgraphs to construct the indexes [18,13,22,20].”
MethodA Survey and Experimental Analysis of Distributed Subgraph MatchingPreprint
Lai, L., Qing, Z., Yang, Z., Jin, X., Lai, Z., Wang, R., Hao, K., Lin, X., Qin, L., Zhang, W., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.11518 · Cited by 4
“[48] used the spanning tree of the query graph to filter infeasible results.”
MethodSelf-citationHierarchy-Aware Neural Subgraph Matching With Enhanced Similarity Measure
Liu, Z., Liu, N., Chen, Y., He, J., Jia, M., & Li, D. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3583003 · Cited by 3
“Require:”
Matcha: A Language and Compiler for Backtracking-Based Subgraph Matching
Wei, Y., Hu, L., & Jiang, P. (2025) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps64566.2025.00105 · Cited by 3
“Most of these algorithms are implemented on CPU, while some recent systems utilize GPU to accelerate computation [9], [14], [24], [25], [32], [34].”
Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings
Ye, Y., Lian, X., Zhang, N., & Chen, M. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3769774 · Cited by 3
Neural Graph Navigation for Intelligent Subgraph Matching
Ying, Y., Dai, Y., Li, W., Huang, W., Wang, R., Zheng, T., Wang, Y., Yuan, H., & Song, M. (2026) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v40i19.38654 · Cited by 3
Structure Guided Retrieval-Augmented Generation for Factual Queries
Xie, M., Zhang, X., Li, Y., & Lv, C. (2026) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2026.acl-long.1873 · Cited by 3
SLF: A passive parallelization of subgraph isomorphism
Liang, W., Dong, W., & Yuan, M. (2022) · Information Sciences · doi:10.1016/j.ins.2022.12.033 · Cited by 3
DGSM: A GPU-Based Subgraph Isomorphism framework with DFS exploration
Han, W., Holmes, C., & Wu, B. (2022) · IEEE/ACM Redefining Scalability for Diversely Heterogeneous Architectures Workshop (RSDHA) · doi:10.1109/rsdha56811.2022.00006 · Cited by 3
“VF2 and QuickSI [16] are two typical systems in the former category.”
BackgroundMethodTemporal Multi-Query Subgraph Matching in Cybersecurity
Lu, M., Zhang, Q., & Zhu, X. (2025) · Technologies · doi:10.3390/technologies13080335 · Cited by 3
Path-Centric Cardinality Estimation for Subgraph Matching
Wang, Z., Yin, Q., & Lai, L. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3746405.3746428 · Cited by 3
“We use three well-established datasets and workloads: LDBC [2], IMDB [25], and AIDS [38].”
RDF pattern matching using sortable views
Chong, Z., Chen, H. H., Zhang, Z., Shu, H., Qi, G., & Zhou, A. (2012) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2396761.2396804 · Cited by 3
“Serialization for matching also appears in other work [21], targeted at reducing the space of candidate matchings.”
Background
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.