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 101–200 of 494
Graph similarity search on large uncertain graph databases
Yuan, Y., Wang, G., Chen, L., & Wang, H. (2014) · The VLDB Journal · doi:10.1007/s00778-014-0373-y · Cited by 32
“To control feature number [38,48], we also define the discriminative measure as: dis( f ) = |{D f ′ | f ′ ⊆iso f }|/|D f |, where D f is the list of uncertain graphs g s.”
BackgroundPrivacy and efficiency guaranteed social subgraph matching
Huang, K., Hu, H., Zhou, S., Guan, J., Ye, Q., & Zhou, X. (2021) · The VLDB Journal · doi:10.1007/s00778-021-00706-0 · Cited by 31
“In addition, our subgraph matching problem is NP-Hard since it involves subgraph isomorphism testing, which is a classical NP-Hard problem [32,57,58].”
BackgroundView-based Explanations for Graph Neural Networks
Chen, T., Qiu, D., Wu, Y., Khan, A., Ke, X., & Gao, Y. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3639295 · Cited by 31
Scalable subgraph enumeration in MapReduce: a cost-oriented approach
Lai, L., Qin, L., Lin, X., & Chang, L. (2017) · The VLDB Journal · doi:10.1007/s00778-017-0459-4 · Cited by 30
“[33] proposed an algorithm to search fromnodeswith infrequent labels in order to utilize the filtering power as early as possible.”
MethodSelf-citationToward continuous pattern detection over evolving large graph with snapshot isolation
Gao, J., Zhou, C., & Yu, J. X. (2015) · The VLDB Journal · doi:10.1007/s00778-015-0416-z · Cited by 29
“Many other methods [24,33] are proposed to optimize the method with different join order and pruning strategies.”
MethodSelf-citationBig Graph Analyses: From Queries to Dependencies and Association Rules
Fan, W., & Hu, C. (2017) · Data Science and Engineering · doi:10.1007/s41019-016-0025-x · Cited by 29
“Contract anytime algorithms have been explored for (a) budgeted search such as bounded-cost planning [64, 66, 108] under a user-specified budget and (b) graph search via subgraph isomorphism, to find intermediate answers within the budget, either by assigning dynamically maintained budgets and costs to nodes during th…”
BackgroundSubgraph Matching on Multiplex Networks
Moorman, J. D., Tu, T. K., Chen, Q., He, X., & Bertozzi, A. L. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3056329 · Cited by 29
“Examples of graph indexing approaches include GraphQL [25], SPath [72], GADDI [71], QuickSI [55], TurboISO [24], BoostISO [52], CFL-Match [6], and CNI-Match [45].”
MethodA survey of continuous subgraph matching for dynamic graphs
Wang, X., Zhang, Q., Guo, D., & Zhao, X. H. (2022) · Knowledge and Information Systems · doi:10.1007/s10115-022-01753-x · Cited by 28
“…Youhuan Li et al. [48] compared the time efficiency and space efficiency between Timing algorithm, SJ-tree, and three other state-of-art static subgraph matching algorithms which were performed on the affected area window by window, including QuickSI [63], Turbo ISO [34], and Boost ISO [61].”
BackgroundMethodBICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification
Choi, Y.-Y., Park, K., & Kim, H. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3598581.3598591 · Cited by 27
“Many subgraph matching algorithms [4, 5, 8, 9, 14, 15, 17, 28, 40, 43, 49, 50] are based on the backtracking framework.”
BackgroundMethodOptimal enumeration: efficient top-k tree matching
Chang, L., Lin, X., Zhang, W., Yu, J. X., Zhang, Y., & Qin, L. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2735479.2735486 · Cited by 27
“Comprehensive empirical studies demonstrate that our techniques may improve the existing techniques by orders of magnitude.”
MethodSelf-citationQuerying massive graph data: A compress and search approach
Nabti, C., & Seba, H. (2017) · Future Generation Computer Systems · doi:10.1016/j.future.2017.04.005 · Cited by 27
Learned sketch for subgraph counting: a holistic approach
Zhao, K., Yu, J. X., Li, Q., Zhang, H., & Rong, Y. (2023) · The VLDB Journal · doi:10.1007/s00778-023-00781-5 · Cited by 26
“A recent analysis for state-of-the-art in-memory algorithms [7,10,11,13,42,80] can be found in [86].”
BackgroundMethodSelf-citationA hybrid reproducing graph kernel based on information entropy
Xu, L., Jiang, X., Bai, L., Xiao, J., & Luo, B. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2017.07.025 · Cited by 26
Inves: Incremental Partitioning-Based Verification for Graph Similarity Search
Kim, J., Choi, D.-H., & Li, C. (2019) · Movebank · doi:10.5441/002/edbt.2019.21 · Cited by 26
“Since sequential scanning of indexed partitions was very slow, we implemented an index access method by modifying the SwiftIndex [16].”
BackgroundMethodFast Gunrock Subgraph Matching (GSM) on GPUsPreprint
Wang, L., & Owens, J. D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.01527 · Cited by 26
Comparing performance of graph matching algorithms on huge graphs
Carletti, V., Foggia, P., Greco, A., Saggese, A., & Vento, M. (2018) · Pattern Recognition Letters · doi:10.1016/j.patrec.2018.06.025 · Cited by 25
Large-scale graph processing systems: a survey
Liu, N., Li, D., Zhang, Y., & Li, X. (2020) · Frontiers of Information Technology & Electronic Engineering · doi:10.1631/fitee.1900127 · Cited by 25
“VF2, QuickSI (Shang et al., 2008), TurboISO (Han et al., 2013a), and BoostISO (Ren and Wang, 2015) are typical exact algorithms.”
BackgroundSelf-citationEfficient Team Formation in Social Networks based on Constrained Pattern Graph
Kou, Y., Shen, D., Snell, Q. O., Li, D., Nie, T., Yu, G., & Ma, S. (2020) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde48307.2020.00082 · Cited by 25
“A cost model is proposed in [7] to estimate the matching cost based on a matching order of nodes ( u 1 , …, u n ) (as in (1)).”
BackgroundMethodInfluentialDryadic: Flexible and Fast Graph Pattern Matching at Scale
Mawhirter, D., Reinehr, S., Han, W., Fields, N., Claver, M., Holmes, C., McClurg, J., Liu, T., & Wu, B. (2021) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1109/pact52795.2021.00028 · Cited by 25
“A number of studies examine the backtracking algorithm, optimizing the matching orders to improve performance [10], [41], [56], [31].”
Network motif discovery: A GPU approach
Lin, W., Xiao, X., Xie, X., & Li, X.-L. (2015) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2015.7113337 · Cited by 25
PruneJuice: Pruning Trillion-edge Graphs to a Precise Pattern-Matching Solution
Reza, T. A., Ripeanu, M., Tripoul, N., Sanders, G., & Pearce, R. (2018) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2018.00024 · Cited by 24
“The well-known Ullmann’s algorithm [5] and its extensions (in terms of join order and pruning strategies), e.g., VF2 [11] and QuickSI [51], belong to the family of tree-search based algorithms.”
BackgroundSUFF: Accelerating Subgraph Matching with Historical Data
Jian, X., Li, Z., & Chen, L. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3587136.3587144 · Cited by 24
“For example, in QuickSI the order is decided based on an infrequent-edge-first manner, and CFL uses a path-based ordering method.”
MethodInfluentialRobust Collaborative Perception without External Localization and Clock Devices
Lei, Z., Ni, Z., Han, R., Tang, S., Feng, C., Chen, S., & Wang, Y. (2024) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra57147.2024.10610635 · Cited by 24
“Algorithms like VF2[21], QuickSI[22], VF2x[23], VF2 Plus[24], and VF3[25] employ feasibility functions and depth-first search for graph isomorphism challenges, although they have limitations with graphs of varying node numbers.”
MethodNewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs
Li, Z., Li, Y., Chen, X., Zou, L., Li, Y., Yang, X., & Jiang, H. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00257 · Cited by 23
“Most existing subgraph matching work are over static graphs [8]–[10], [12], [15], [17]–[21], [24], [50], [52]–[54].”
BackgroundScalable supergraph search in large graph databases
Lyu, B., Qin, L., Lin, X., Chang, L., & Yu, J. X. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498237 · Cited by 23
“Given a query-graph Q, subgraph search [8] [13] [16] [23] [25] [30] finds all data-graphs that contain Q in the graph database, while supergraph search [6] [7] [24] [29] [31] retrieves all data-graphs that are contained in Q in the graph database.”
MethodSelf-citationCP-index: on the efficient indexing of large graphs
Xie, Y., & Yu, P. S. (2011) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2063576.2063835 · Cited by 23
“Although there have been several methods proposed to solve this mining bottleneck such as summarization of database graphs, the frequent subgraphs thus generated as indexing features are still unsatisfactory because the feature set is in general not only inadequate or de.cient for the large…”
MethodQuerying Web-Scale Knowledge Graphs Through Effective Pruning of Search Space
Jin, J., Luo, J., Khemmarat, S., & Gao, L. (2017) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2017.2665478 · Cited by 23
“QuickSI [14] $ GE [9] $ $ $ Ness [6] $ $ NeMa [7] $ a $ GraB-Index $ $ GraB $ $ $ $”
MethodSubgraph Isomorphism in Temporal NetworksPreprint
Redmond, U., & Cunningham, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.02174 · Cited by 24
“A filtering-and-verification approach was presented (Shang et al., 2008).”
Subgraph matching over graph federation
Yuan, Y., Ma, D., Wen, Z., Zhang, Z., & Wang, G. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3494124.3494129 · Cited by 22
“The neighbors or degrees of each node are encoded as indices in [46].”
BackgroundDualIso: An Algorithm for Subgraph Pattern Matching on Very Large Labeled Graphs
Saltz, M., Jain, A., Kothari, A., Fard, A. M. Z., Miller, J. A., & Ramaswamy, L. M. (2014) · IEEE International Congress on Big Data (BigData Congress) · doi:10.1109/bigdata.congress.2014.79 · Cited by 22
“The authors give an experimental comparison between five recent algorithms in a unified framework: VF2 [10] GraphQL [5], QuickSI [6], SPath [7], and GADDI [9].”
MethodShared Memory Parallel Subgraph Enumeration
Kimmig, R., Meyerhenke, H., & Strash, D. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.133 · Cited by 22
Structure-Preserving Subgraph Query Services
Fan, Z., Choi, B. K. K., Chen, Q., Xu, J., Hu, H., & Bhowmick, S. S. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2399292 · Cited by 22
“We used two real-world benchmark datasets namely Aids (A) and PubChem (P) from [15], which are widely used in [5], [14], [16], [23], [29], [33], [36], [39].”
BackgroundMethodInfluentialTowards GPU-Based Common-Sense Reasoning: Using Fast Subgraph Matching
Tran, H.-N., Cambria, E., & Hussain, A. (2016) · Cognitive Computation · doi:10.1007/s12559-016-9418-4 · Cited by 21
“We evaluate the performance of GpSense in comparison with state-of-the-art subgraph matching algorithms, including VF2 [9], QuickSI (QSI) [24], GraphQL (GQL) [13] and TurboISO [10].”
MethodIVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices
Jiang, Z., Zhang, S., Hou, X., Yuan, M., & You, H. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00321 · Cited by 20
Making pattern queries bounded in big graphs
Cao, Y., Fan, W., Huai, J., & Huang, R. (2015) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2015.7113281 · Cited by 20
“2”
Asymmetric structure-preserving subgraph queries for large graphs
Fan, Z., Choi, B. K. K., Xu, J., & Bhowmick, S. S. (2015) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2015.7113296 · Cited by 20
“, VF2 [8], QuickSI [26] and Turbo iso [14]) have been proposed to enhance performance significantly.”
BackgroundInfluentialNetMatchStar: an enhanced Cytoscape network querying app
Rinnone, F., Micale, G., Bonnici, V., Bader, G. D., Shasha, D. E., Ferro, A., Pulvirenti, A., & Giugno, R. (2015) · F1000Research · doi:10.12688/f1000research.6656.1 · Cited by 20
Parallelizing Recursive Backtracking Based Subgraph Matching on a Single Machine
Sun, S., & Luo, Q. (2018) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/padsw.2018.8644869 · Cited by 20
“The subgraph matching problem is NP-hard [16], and a variety of sequential algorithms [4], [6], [8], [9], [22], [24], [28] have been proposed to solve this problem.”
BackgroundMethodIterative Graph Feature Mining for Graph Indexing
Yuan, D., Mitra, P., Yu, H., & Giles, C. L. (2012) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2012.11 · Cited by 20
“Experiments show that our feature mining algorithm is 5 times faster than the popular graph indexing algorithm gIndex, and that features mined by our iterative algorithm have a better filtering rate for the subgraph search problem.”
MethodPruneJuice: pruning trillion-edge graphs to a precise pattern-matching solution
Reza, T. A., Ripeanu, M., Tripoul, N., Sanders, G., & Pearce, R. (2018) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.5555/3291656.3291684 · Cited by 19
Spatial and temporal constrained ranked retrieval over videos
Chen, Y., Koudas, N., Yu, X., & Yu, Z. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3551793.3551865 · Cited by 19
“Such works mainly target large graphs [11, 38], where the number of nodes is relatively large and the degree of each node varies, which can be used as the filter condition or part of the query constraints [38], or complex graphs that can be further decomposed into basic structures [22] or subgraphs [45].”
BackgroundTime-Constrained Graph Pattern Matching in a Large Temporal Graph
Xu, Y., Huang, J., Liu, A., Li, Z., Yin, H., & Zhao, L. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63579-8_9 · Cited by 19
Efficient Subgraph Skyline Search Over Large Graphs
Zheng, W., Zou, L., Lian, X., Hong, L., & Zhao, D. (2014) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2661829.2662037 · Cited by 19
“Then, we verify each candidate data graph by employing the subgraph isomorphism algorithm, such as Ulluman [20], VF2 [4], and QuickSI [14].”
MethodMining and indexing graphs for supergraph search
Yuan, D., Mitra, P., & Giles, C. L. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2536206.2536211 · Cited by 19
“Graphs are commonly serialized to a list of tuples, each of which represents one edge [16, 12, 20].”
BackgroundIndexing and mining topological patterns for drug discovery
Ranu, S., & Singh, A. K. (2012) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/2247596.2247666 · Cited by 19
“Interestingly, majority of the techniques fall under the general framework of fragment-based indexing [2, 8, 18, 19, 24, 28, 29].”
BackgroundUpdating Graph Indices with a One-Pass Algorithm
Yuan, D., Mitra, P., Yu, H., & Giles, C. L. (2015) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2723372.2746482 · Cited by 18
“For the subgraph-search problem, an inclusive logic is proposed to filter out false graphs [4, 18, 24, 25]: given index features F , a graph g cannot be query q’s supergraph (can be filtered out) if ∃f ∈ F, f ⊂ q, and f ̸⊂ g.”
BackgroundMethodInfluentialEfficient algorithms for generalized subgraph query processing
Lin, W., Xiao, X., Cheng, J. S.-C., & Bhowmick, S. S. (2012) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2396761.2396805 · Cited by 18
“The first one is subgraph query [4,9,13,15,18,21,23], which finds the subset of graphs A of G such that q is a subgraph of any graph in A .”
BackgroundMethodInfluentialSmiles2Monomers: a link between chemical and biological structures for polymers
Dufresne, Y., Noé, L., Leclère, V., & Pupin, M. (2015) · Journal of Cheminformatics · doi:10.1186/s13321-015-0111-5 · Cited by 18
“We optimized the VF2 algorithm with the strategies presented in Shang publication [28] and used by Zhu for the search of molecular graphs into molecular databases [29].”
MethodSuMGra: Querying Multigraphs via Efficient Indexing
Ingalalli, V., Ienco, D., & Poncelet, P. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44403-1_24 · Cited by 18
“To test the behavior of the different approaches, we generate random queries [7, 13] varying their size (in terms of vertices) from 3 to 11 in steps of 2.”
MethodAnswering Top-$k$ Graph Similarity Queries in Graph Databases
Zhu, Y., Qin, L., Yu, J. X., & Cheng, H. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2906608 · Cited by 18
“, gIndex [1], FG-Index [27], Tree+D [28], SwiftIndex [29], etc.”
Self-citationPrefIndex: An Efficient Supergraph Containment Search Technique
Zhu, G., Lin, X., Zhang, W., Wang, W., & Shang, H. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13818-8_26 · Cited by 18
“As our problem is the dual problem of that in [9], edges (labels) in a data graph g with lower occurrence rates in the database are ”signatures” of g and should be allocated earlier in Codeg for early pruning.”
BackgroundMethodSelf-citationSGSI – A Scalable GPU-Friendly Subgraph Isomorphism Algorithm
Zeng, L. M., Zou, L., & ÖZSU, M. T. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3230744 · Cited by 17
“ods [20], [21], [22], [23] pre-compute some structural indices to reduce the search space and optimize the matching vertex order using various heuristic methods.”
MethodCloud service placement via subgraph matching
Zong, B., Raghavendra, R., Srivatsa, M., Yan, X., Singh, A. K., & Lee, K. (2014) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2014.6816704 · Cited by 17
“Although the indexed substructures could be diverse, such as paths [13], [46], trees [26], [42], or general subgraphs [6], [18], [31], [38], [40], they follow a common spirit: a small data graph, or a small region in a large data graph, is worth searching, if it contains a query graph’s…”
BackgroundHybrid Subgraph Matching Framework Powered by Sketch Tree for Distributed Systems
Zhang, Y., Zheng, W., Zhang, Z., Peng, P., & Zhang, X. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00082 · Cited by 17
Self-citationComputing subgraph isomorphic queries using structural unification and minimum graph structures
Jamil, H. M. (2011) · ACM Symposium on Applied Computing · doi:10.1145/1982185.1982415 · Cited by 17
“However, we did compare our algorithm with one of the recent systems QuickSI [19] and show that our al-gorithm outperforms QuickSI.”
ResultIdentifying the Most Connected Vertices in Hidden Bipartite Graphs Using Group Testing
Wang, J., Lo, E., & Yiu, M. L. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.178 · Cited by 17
“Unfortunately, such testing is known to be expensive, for example, a subgraph isomorphism test is NP-complete [9], [27].”
BackgroundSQBC: An efficient subgraph matching method over large and dense graphs
Zheng, W., Zou, L., Lian, X., Zhang, H., Wang, W., & Zhao, D. (2013) · Information Sciences · doi:10.1016/j.ins.2013.10.003 · Cited by 17
“The main differences lies in the method of computing candidates and the vertex sequence pushed into SMQ .”
BackgroundMethodExtending Graph Patterns with Conditions
Fan, G., Fan, W., Li, Y., Lü, P., Tian, C., & Zhou, J. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3380585 · Cited by 17
“QuickSI [32] encodes, e.g., neighbors and degrees, as indices.”
BackgroundRIQ : Fast processing of SPARQL queries on RDF quadruples
Katib, A., Slavov, V., & Rao, P. R. (2016) · Journal of Web Semantics · doi:10.1016/j.websem.2016.03.005 · Cited by 17
Top-k Similarity Matching in Large Graphs with Attributes
Ding, X., Jia, J., Li, J., Liu, J., & Jin, H. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-05813-9_11 · Cited by 16
Correct filtering for subgraph isomorphism search in compressed vertex-labeled graphs
Wang, J., Ren, X., Anirban, S., & Wu, X.-W. (2019) · Information Sciences · doi:10.1016/j.ins.2019.01.036 · Cited by 16
A Reachability Index for Recursive Label-Concatenated Graph Queries
Zhang, C., Bonifati, A., Kapp, H., Haprian, V., & Lozi, J.-P. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00013 · Cited by 16
An Efficient Subgraph Isomorphism Solver for Large Graphs
Ansari, Z. A., Jahiruddin, & Abulaish, M. (2021) · IEEE Access · doi:10.1109/access.2021.3073494 · Cited by 16
“Some of the indexing-based existing solvers are GADDI [16], GraphQL [17], SPath [18], STW [19], CFL-Match [20],QuickSI [21], and TurboISO [22].”
MethodLi, Q., & Yu, J. X. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3659437.3659451 · Cited by 15
“Research efforts have been devoted to filtering candidates [10, 12, 19, 33, 38, 39, 53, 54, 87, 88, 103], optimizing matching order [12, 38, 39, 53, 54, 66, 83, 85, 87, 88], and using previous matching results for pruning [7, 38, 47, 53, 54].”
MethodSelf-citationGPU-Accelerated Batch-Dynamic Subgraph Matching
Qiu, L., Chen, L., Jie, H., Ke, X., Gao, Y., Liu, Y., & Zhang, Z. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00248 · Cited by 15
“Surprisingly, systematic exploration of subgraph matching in the context of batch-dynamic graphs, particularly on a GPU platform, remains untouched.”
BackgroundLarge Subgraph Matching: A Comprehensive and Efficient Approach for Heterogeneous Graphs
Cao, H., Wang, Q., Li, X., Najafi, M., Chang, K. C., & Cheng, R. C. K. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00231 · Cited by 15
Neural Similarity Search on Supergraph Containment
Wang, H., Yu, J., Wang, X., Chen, C., Zhang, W., & Lin, X. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3279920 · Cited by 15
“To solve this problem, a great number of subgraph search algorithms [1], [2], [3], [4], [5], [6], [7] and supergraph search algorithms [8], [9], [10], [11] have been proposed in the literature.”
BackgroundSelf-citationAny-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs
Yang, X., Ajwani, D., Gatterbauer, W., Nicholson, P. K., Riedewald, M., & Sala, A. (2018) · International World Wide Web Conference (WWW) · doi:10.1145/3178876.3186115 · Cited by 15
“[26] empirically compare the performance of several state-of-art subgraph isomorphism algorithms, including the Generic Subgraph Isomorphism Algorithm [11], Ullmann algorithm [36], VF2 [10], QuickSI [33], GADDI [41], and GraphQL [17].”
MethodQuerying Large Graph Databases
Ke, Y., Cheng, J. S.-C., & Yu, J. X. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12098-5_57 · Cited by 15
Self-citationPilos: Scalable Large-Subgraph Matching by Online Spectral Filtering
Skitsas, K., Mottin, D., & Karras, P. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00093 · Cited by 14
Subgraph matching on temporal graphs
Li, F., & Zou, Z. (2021) · Information Sciences · doi:10.1016/j.ins.2021.07.071 · Cited by 14
A Relational-Based Approach for Aggregated Search in Graph Databases
Le, T.-H., Elghazel, H., & Hacid, M.-S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29038-1_5 · Cited by 14
Connecting Requirements to Architecture and Analysis via Model-Based Systems Engineering
Cole, B. F., & Jenkins, J. S. (2015) · AIAA Infotech@Aerospace Conference · doi:10.2514/6.2015-1116 · Cited by 14
“Element-by-element matching is treated as a subroutine to a state-of-the-art graph query algorithm called Quick Subgraph Isomorphism [8].”
MethodAnomaly Detection of Network Streams via Dense Subgraph Discovery
Yan, H., Zhang, Q., Mao, D., Lu, Z., Guo, D., & Chen, S. (2021) · International Conference on Computer Communications and Networks (ICCCN) · doi:10.1109/icccn52240.2021.9522263 · Cited by 14
GPU acceleration of subgraph isomorphism search in large scale graph
Yang, B., Lü, K., Gao, Y., Wang, X.-P., & Xu, K. (2015) · Journal of Central South University · doi:10.1007/s11771-015-2748-7 · Cited by 14
Graph Aggregation Based Image Modeling and Indexing for Video Annotation
Aoun, N. B., Elghazel, H., Hacid, M.-S., & Amar, C. B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23678-5_38 · Cited by 14
“Applying an exhaustive search to find the query graph in a graphs database is a very time consuming process and an NP-complete problem since we have not only to survey the entire graphs database but also to investigate the subgraph isomorphism [ 8 ],[9].”
BackgroundMethodInfluentialEfficient breadth-first search on large graphs with skewed degree distributions
Shang, H., & Kitsuregawa, M. (2013) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/2452376.2452413 · Cited by 14
“A large number of graph data processing techniques have been proposed in recent years and applied to a wide range of applications including social networks [3, 8, 24, 27], telecommunication [23], chemistry informatics [7, 32], medical informatics [31, 33, 34] and”
BackgroundSelf-citationA Scalable Query Pricing Framework for Incomplete Graph Data
Hou, H., Qiao, L., Yuan, Y., Chen, C., & Wang, G. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30637-2_7 · Cited by 13
Efficient Multi-Query Oriented Continuous Subgraph Matching
Ma, Z., Yang, J., Zhou, X., Xiao, G., Wang, J., Yang, L., Li, K., & Lin, X. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00250 · Cited by 13
Self-citationiGraph in action: performance analysis of disk-based graph indexing techniques
Han, W.-S., Pham, M.-D., Lee, J., Kasperovičs, R., & Yu, J. X. (2011) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1989323.1989464 · Cited by 13
Self-citationQuick Mining of Isomorphic Exact Large Patterns from Large Graphs
Almasri, I., Gao, X., & Fedoroff, N. V. (2014) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2014.65 · Cited by 13
“The order is (b) Ullmann [10] (c) GraphQL [2] (d) VF2 [11] (e) QuickSI [12] and RI [13] and (f) L2G, our approach”
MethodInfluentialDeep Analysis on Subgraph IsomorphismPreprint
Zeng, L. M., Jiang, Y. L., Lu, W., & Zou, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.06802 · Cited by 13
“Except for tree search methods, current solutions [3]–[7], [9], [10], [14], [15] mainly adopt filtering-and-verification framework and leverage some auxiliary indices to accelerate the exploration.”
InfluentialMPMatch: A Multi-core Parallel Subgraph Matching Algorithm
Jin, X., & Lai, L. (2019) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2019.000-6 · Cited by 12
“Infrequence is used in candidates reduction in QuickSI [14] that proposes to first process infrequent query vertices and edges in data graph.”
MethodApproximating the maximum common subgraph isomorphism problem with a weighted graph
Chen, A. C.-L., Elhajj, A., Gao, S. H., Sarhan, A., Afra, S., Kassem, A., & Alhajj, R. (2015) · Knowledge-Based Systems · doi:10.1016/j.knosys.2015.05.012 · Cited by 12
“[21] also published another index based solution that uses the features of prefix trees to find the index.”
MethodSubISO: A Scalable and Novel Approach for Subgraph Isomorphism Search in Large Graph
Abulaish, M., Ansari, Z. A., & Jahiruddin (2019) · International Conference on Communication Systems & Networks (COMSNETS) · doi:10.1109/comsnets.2019.8711459 · Cited by 12
“Since subgraph isomorphism serach probelm has its root in various application domains, a number of solutions have been proposed by various researchers, e.g., Ullmann’s algorithm [6], VF2 [7], QuickSI [8], GraphQL [9], GADDI [10], SPath [11], NOVA [12], STW [5], TurboISO [4], CFL-Match [3], and SumISO [2].”
BackgroundMethodInfluentialInvestigation of incremental hybrid genetic algorithm with subgraph isomorphism problem
Choi, H., Kim, J., Yoon, Y., & Moon, B.-R. (2019) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2019.05.004 · Cited by 12
Hybrid algorithms for subgraph pattern queries in graph databases
Katsarou, F., Ntarmos, N., & Triantafillou, P. (2017) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2017.8257981 · Cited by 12
“Popular SI methods include [11], [16]–[19].”
BackgroundMethodSpace-Efficient Subgraph Search Over Streaming Graph With Timing Order Constraint
Li, Y., Zou, L., ÖZSU, M. T., & Zhao, D. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3035902 · Cited by 11
Efficient subhypergraph matching based on hyperedge features
Su, Y., Gu, Y., Wang, Z., Zhang, Y., Qin, J., & Yu, G. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3160393 · Cited by 11
“Specifically, QuickSI [18] uses the tree to determine the matching order and ensure the connectivity of the added vertices.”
BackgroundMethodSelf-citationTC-Match: Fast Time-Constrained Continuous Subgraph Matching
Yang, J., Fang, S., Gu, Z., Ma, Z., Lin, X., & Tian, Z. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3681954.3681963 · Cited by 11
Self-citationPathLAD+: Towards effective exact methods for subgraph isomorphism problem
Wang, Y., Jin, C., & Cai, S. (2024) · Artificial Intelligence · doi:10.1016/j.artint.2024.104219 · Cited by 11
A Modular Graph-Native Query Optimization Framework
Lyu, B., Zhou, X., Lai, L., Yang, Y., Lou, Y., Yu, W., Zhang, Y., & Zhou, J. (2025) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3722212.3724425 · Cited by 11
Self-citationOlifer, D., Goranin, N., Čenys, A., Kačeniauskas, A., & Janulevičius, J. (2019) · Applied Sciences · doi:10.3390/app9040681 · Cited by 11
“Other algorithms, like Ullmann [49], VF2 [50], QuickSI [51], and SPath [52] find all embedding for the given query and original graph.”
MethodAggregated Search in Graph Databases: Preliminary Results
Elghazel, H., & Hacid, M.-S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20844-7_10 · Cited by 11
“More recently, in order to significantly reduce the verification costs, Shang et al. [ 7 ] have proposed a new efficient subgraph isomorphism testing algorithm (QuickSI ) by improving the widely applied Ullman’s algorithm [9].”
BackgroundMethodInfluentialA tool for fast indexing and querying of graphs
Pal, D., & Rao, P. R. (2011) · International World Wide Web Conference (WWW) · doi:10.1145/1963192.1963299 · Cited by 11
“Many of the recent approaches for exact subgraph matching, load the index into memory before processing graph queries ( e.g. , gIndex [22], Tree+ Δ [28], GDIndex [21], QuickSI [13], GCod-ing [29]).”
BackgroundEgo-centric Graph Pattern Census
Moustafa, W. E., Deshpande, A., & Getoor, L. C. (2012) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2012.113 · Cited by 11
“, [34], [41], [19], [45], [42], [11], [33]).”
A Scalable Graph-Coarsening Based Index for Dynamic Graph Databases
Kansal, A., & Spezzano, F. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3133003 · Cited by 11
On Continuously Matching of Evolving Graph Patterns
Zhang, Q., Guo, D., Zhao, X. H., & Guo, A. (2019) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3357384.3358101 · Cited by 11
RIQ: Fast Processing of SPARQL Queries on RDF QuadruplesPreprint
Katib, A., Slavov, V., & Rao, P. R. (2016) · SSRN Electronic Journal · doi:10.2139/ssrn.3199230 · Cited by 11
GLumin: Fast Connectivity Check Based on LUTs For Efficient Graph Pattern Mining
Cao, W., Meng, K., Lin, Z., & Tan, G. (2025) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3710848.3710889 · Cited by 10
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.