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
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
In-Memory Subgraph Matching: An In-depth Study
Sun, S., & Luo, Q. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3380581 · Cited by 221
Optimizing subgraph queries by combining binary and worst-case optimal joins
Mhedhbi, A., & Salihoğlu, S. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3342263.3342643 · Cited by 214
“This initial version has been improved with different techniques to pick better QVOs and filter partial matches, often focusing on queries with labels [11, 12, 35].”
MethodHan, M., Kim, H., Gu, G., Park, K., & Han, W.-S. (2019) · Proceedings of the 2019 International Conference on Management of Data · doi:10.1145/3299869.3319880 · Cited by 203
Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs
Ren, X., & Wang, J. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2735479.2735493 · Cited by 183
“By utilizing global statistics of vertex label frequencies, QuickSI [12] proposes a matching order which accesses query vertices having infrequent vertex labels as early as possible.”
MethodChallenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3
Carletti, V., Foggia, P., Saggese, A., & Vento, M. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2696940 · Cited by 177
“…[22][23] McGregor [24], Larrosa and Valiente[25], Zampelli [26], Solnon [27], Ullmann [28], Kotthoff [29] Graph Indexing GraphQL [30], QuickSI [31], GADDI [32], SPath [33], TurboIso [34] TABLE I: The three main approaches to subgraph isomorphism and the relative most known algorithms. remains…”
Privacy-Preserving Query over Encrypted Graph-Structured Data in Cloud Computing
Cao, N., Yang, Z., Wang, C., Ren, K., & Lou, W. (2011) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdcs.2011.84 · Cited by 176
SAPPER: subgraph indexing and approximate matching in large graphs
Zhang, S., Yang, J., & Jin, W. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920988 · Cited by 172
“Many index-based graph matching and searching schemes have been proposed to find where the query graph occurs in the graph databases [4, 12, 18, 22, 23, 9], which can be further divided into the graph indexing and subgraph indexing.”
BackgroundNeMa: fast graph search with label similarity
Khan, A., Wu, Y., Aggarwal, C. C., & Yan, X. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2535569.2448952 · Cited by 165
“Ullmann’s backtracking method [38], VF2 [9], SwiftIndex [32] are used for subgraph isomorphism checking.”
MethodNeighborhood based fast graph search in large networks
Khan, A., Li, N., Yan, X., Guan, Z., Chakraborty, S., & Tao, S. (2011) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1989323.1989418 · Cited by 156
“introduce an efficient algorithm for testing subgraph isomorphism [29].”
MethodProcessing SPARQL queries over distributed RDF graphs
Peng, P., Zou, L., ÖZSU, M. T., Chen, L., & Zhao, D. (2016) · The VLDB Journal · doi:10.1007/s00778-015-0415-0 · Cited by 141
“However, QuickSI [43] proposes several heuristic rules to select an optimized order that can speed up the matching process.”
MethodScalable distributed subgraph enumeration
Lai, L., Qin, L., Lin, X., Zhang, Y., Chang, L., & Yang, S. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021937 · Cited by 136
Self-citationRapidMatch: a holistic approach to subgraph query processing
Sun, S., Sun, X., Che, Y., Luo, Q., & He, B. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3425879.3425888 · Cited by 134
“The first category of algorithms such as QuickSI [33] follow the direct-enumeration paradigm, which directly explores G to enumerate matches.”
BackgroundMethodTurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data
Kim, K., Seo, I., Han, W.-S., Lee, J.-H., Hong, S., Chafi, H., Shin, H., & Jeong, G. (2018) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3183713.3196917 · Cited by 131
“The representative algorithms in subgraph isomorphism are VF2 [8], QuickSI [26], GraphQL [15], SPATH [32], TurboISO [14], TurboISOBoosted [24], and CFL [5].”
MethodiGraph: a framework for comparisons of disk-based graph indexing techniques
Han, W.-S., Lee, J., Pham, M.-D., & Yu, J. X. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920901 · Cited by 126
“Database Construction Cost: Table 2 shows database construction costs for the default synthetic dataset.”
InfluentialSelf-citationBit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
Ullmann, J. R. (2010) · ACM Journal of Experimental Algorithmics · doi:10.1145/1671970.1921702 · Cited by 121
“This is why in Figure 27(c)(d) the total time per molecular comparison decreases as nα increases, contradicting an assertion [Shang et al. 2008] that the larger the query graphs “the higher the cost for subgraph isomorphism testing.”
ResultSemantic proximity search on graphs with metagraph-based learning
Fang, Y., Lin, W., Zheng, V. W., Wu, M., Chang, K. C., & Li, X. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498247 · Cited by 115
“[19] have proposed a special ordering of nodes for matching instead of just a random ordering.”
BackgroundMethodInfluentialVersatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching
Kim, H., Choi, Y.-Y., Park, K., Lin, X., Hong, S.-H., & Han, W.-S. (2021) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3448016.3457265 · Cited by 112
“Early subgraph matching algorithms such as Ullmann [37], VF2 [7], QuickSI [33], and SPath [43] obtain a candidate set by using local filters that consider the neighborhood of vertices; however,”
MethodSelf-citationTaming subgraph isomorphism for RDF query processing
Kim, J., Shin, H., Han, W.-S., Hong, S., & Chafi, H. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2809974.2809985 · Cited by 109
Distributed subgraph matching on timely dataflow
Lai, L., Qing, Z., Yang, Z., Jin, X., Lai, Z., Wang, R., Hao, K., Lin, X., Qin, L., Zhang, W., et al. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3339490.3339494 · Cited by 103
“[45] used the spanning tree of the query graph to filter infeasible results.”
MethodSelf-citationFast Subgraph Matching on Large Graphs using Graphics Processors
Tran, H.-N., Kim, J., & He, B. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18120-2_18 · Cited by 99
“Figure 8 shows that GpSM clearly outperforms VF2, QuickSI and GraphQL.”
MethodInfluentialGPU-Accelerated Subgraph Enumeration on Partitioned Graphs
Guo, W., Li, Y., Sha, M., He, B., Xiao, X., & Tan, K. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3389699 · Cited by 98
“Thus, there have been a lot of studies on improving the performance of subgraph enumerations (such as [8, 23, 26, 34]).”
BackgroundMethodInfluentialEfficient Graph Similarity Search Over Large Graph Databases
Zheng, W., Zou, L., Lian, X., Wang, D., & Zhao, D. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2014.2349924 · Cited by 96
Efficient subgraph search over large uncertain graphs
Yuan, Y., Wang, G., Wang, H., & Chen, L. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402707.3402726 · Cited by 96
“2, we implement the method in [29] to do structural pruning.”
BackgroundMethodInfluentialEfficient subgraph similarity search on large probabilistic graph databases
Yuan, Y., Wang, G., Chen, L., & Wang, H. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2311906.2311908 · Cited by 95
“To control feature number [37, 29], we also define the discriminative measure as: | f ⊆ iso g c . discriminative , where D f is the list probabilistic graphs g s.t.”
GSI: GPU-friendly Subgraph Isomorphism
Zeng, L., Zou, L., ÖZSU, M. T., Hu, L., & Zhang, F. (2020) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde48307.2020.00112 · Cited by 94
Efficiently Indexing Large Sparse Graphs for Similarity Search
Wang, G., Wang, B., Yang, X., & Yu, G. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.28 · Cited by 90
“Bioinformatical data such as proteinprotein interaction networks and chemical compounds, Web and XML documents, and road networks also have similar structures to graphs.”
BackgroundPark, Y., Ko, S., Bhowmick, S. S., Kim, K., Hong, K., & Han, W.-S. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3389702 · Cited by 86
“We use five synthetic and real-world datasets for evaluation: LUBM [15], YAGO [40], DBpedia [6], AIDS (used in [37]), and Human (used in [43]).”
MethodHUGE: An Efficient and Scalable Subgraph Enumeration System
Yang, Z., Lai, L., Lin, X., Hao, K., & Zhang, W. (2021) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3448016.3457237 · Cited by 83
“Most of them follows Ullmann’s [80] backtracking approach [47, 77] with different matching order, pruning rules, and index structure [8, 12, 19, 29, 30, 33, 42, 68, 85, 86].”
BackgroundSelf-citationContinuous Subgraph Pattern Search over Certain and Uncertain Graph Streams
Chen, L., & Wang, C. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.67 · Cited by 76
“Shang et al. [29] proposed an improved subgraph isomorphism checking method using tree features.”
MethodG-Finder: Approximate Attributed Subgraph Matching
Liu, L., Du, B., Xu, J., & Tong, H. (2019) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata47090.2019.9006525 · Cited by 73
“to order paths [6], and the least frequent node first [22].”
BackgroundWhen Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases
McCreesh, C., Prosser, P., Solnon, C., & Trimble, J. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5768 · Cited by 73
Network Motif Discovery: A GPU Approach
Lin, W., Xiao, X., Xie, X., & Li, X. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2566618 · Cited by 72
“technique in [21] for choosing a matching order for g.”
BackgroundMethodInfluentialSmurf-Based Anti-money Laundering in Time-Evolving Transaction Networks
Starnini, M., Tsourakakis, C. E., Zamanipour, M., Panisson, A., Allasia, W., Fornasiero, M., Puma, L. L., Ricci, V., Ronchiadin, S., Ugrinoska, A., et al. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-86514-6_11 · Cited by 71
Top-k graph pattern matching over large graphs
Cheng, J., Zeng, X., & Yu, J. X. (2013) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544895 · Cited by 71
“Its main application is the so called frequent subgraph mining, which has been extensively studied for the last decade, such as [24], [25], [26], [27] to name a few.”
BackgroundSelf-citationMulti-query optimization for subgraph isomorphism search
Ren, X., & Wang, J. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021929 · Cited by 71
“Algorithms falling into the second category include Ull-mann [22], VF2 [3], GraphQL [10], TurboIso [9], QuickSI [20] and many others [21, 23].”
BackgroundA partition-based approach to structure similarity search
Zhao, X. H., Xiao, C., Lin, X., Liu, Q., & Zhang, W. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2732232.2732236 · Cited by 70
“1 Half-edge Subgraph Isomorphism Test QISequence [13] is a graph encoding technique originally proposed for efficient (non-half-edge) subgraph isomorphism test.”
BackgroundMethodInfluentialSelf-citationNScale: neighborhood-centric large-scale graph analytics in the cloud
Quamar, A., Deshpande, A., & Lin, J. (2015) · The VLDB Journal · doi:10.1007/s00778-015-0405-2 · Cited by 68
“applications in a variety of application domains including biological networks, chemical interaction networks, social networks, and many others; and a wide variety of techniques have been developed for exact or approximate subgraph pattern matching [46,52,12,53,54,50,36,45,19,49,33] (see Lee et al.”
BackgroundTreeSpan: efficiently computing similarity all-matching
Zhu, G., Lin, X., Zhu, K., Zhang, W., & Yu, J. X. (2012) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2213836.2213896 · Cited by 67
“Observing that, in graph structure search, search (i.e., retrieving the actual mappings from a query graph to data graphs) costs play a dominant role, [4, 12, 13, 23] also focus on developing effi-cient search techniques.”
BackgroundMethodInfluentialSelf-citationConnected substructure similarity search
Shang, H., Lin, X., Zhang, Y., Yu, J. X., & Wang, W. (2010) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1807167.1807264 · Cited by 66
“Following the recent performance study settings [6, 19, 23], edge labels are ignored for a tough evaluation.”
BackgroundMethodInfluentialSelf-citationContinuous pattern detection over billion-edge graph using distributed framework
Gao, J., Zhou, C., Zhou, J., & Yu, J. X. (2014) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2014.6816681 · Cited by 66
“The selection of join orders will be an important optimization strategy [8], [7], [21].”
BackgroundSelf-citationA Learned Sketch for Subgraph Counting
Zhao, K., Yu, J. X., Zhang, H., Li, Q., & Rong, Y. (2021) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3448016.3457289 · Cited by 65
“As surveyed in [69], there are enumeration methods [11, 14, 15, 17, 41, 57, 71] and analytical methods [8, 56, 62, 66].”
BackgroundMethodSelf-citationGraph-Based Text Representation and Matching: A Review of the State of the Art and Future Challenges
Osman, A. H., & Barukab, O. (2020) · IEEE Access · doi:10.1109/access.2020.2993191 · Cited by 64
A Survey on Distributed Graph Pattern Matching in Massive Graphs
Bouhenni, S., Yahiaoui, S., Nouali‐Taboudjemat, N., & Kheddouci, H. (2021) · ACM Computing Surveys · doi:10.1145/3439724 · Cited by 63
“Furthermore, we find algorithms that use exploration of the data graph to evaluate subgraph isomorphism such as QuickSI [72], RI [5] or VF2++ [41].”
MethodInfluentialA novel approach for efficient supergraph query processing on graph databases
Zhang, S., Li, J., Gao, H., & Zou, Z. (2009) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/1516360.1516385 · Cited by 63
“Subgraph query processing has attracted much research attention in last several years, and many algorithms have been proposed [5, 11, 12, 17, 18, 21, 25-28].”
MethodGuP: Fast Subgraph Matching by Guard-based Pruning
Arai, J., Fujiwara, Y., & Onizuka, M. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3589312 · Cited by 62
Performance and scalability of indexed subgraph query processing methods
Katsarou, F., Ntarmos, N., & Triantafillou, P. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2824032.2824054 · Cited by 61
“, [5, 15, 21, 27]), and is thus able to function with several feature types.”
BackgroundNeural Subgraph Counting with Wasserstein Estimator
Wang, H., Hu, R., Zhang, Y., Qin, L., Wang, W., & Zhang, W. (2022) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3514221.3526163 · Cited by 60
Self-citationEfficient and scalable labeled subgraph matching using SGMatch
Rivero, C. R., & Jamil, H. M. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-016-0968-2 · Cited by 59
“As it can be seen, SGMatch is the single technique that is scalable in the size of data nodes and significantly outperforms VF2 and QuickSI except in 450K, in which QuickSI is able to compute the solutions faster than SGMatch but still comparable.”
BackgroundMethodInfluentialVF2 Plus: An Improved version of VF2 for Biological Graphs
Carletti, V., Foggia, P., & Vento, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18224-7_17 · Cited by 58
Querying business process model repositories: A survey of current approaches and issues
Wang, J., Jin, T., Wong, R. K., & Wen, L. (2013) · World Wide Web · doi:10.1007/s11280-013-0210-z · Cited by 57
“gIndex [67, 68] C1 TreePi [73] C1 Tree+ [74] C1 FG-index [12] C1 Swift-Index [55] C1 Summ Graph [77] C1 GraphGrep [57] C1 GCoding [76] C1 C-tree [30] C1, C2 GDI [64] C1, C2 GString [32] C1, C2 RASCAL [50] C2 Grafil [69] C2”
MethodInfluentialDiversified Top-k Subgraph Querying in a Large Graph
Yang, Z., Fu, A. W.-C., & Liu, R. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2915216 · Cited by 57
“For the study of querying a large set of relatively small graphs, indexes have been used as the filters of candidate graphs, some previous works are gIndex[30], FG-index[4], Tree+δ[36], and SwiftIndex[26].”
BackgroundMethodDurable graph pattern queries on historical graphs
Semertzidis, K., & Pitoura, E. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498269 · Cited by 56
“Many approaches use indexes to accelerate subgraph pattern matching [5], [6], [27], [28].”
BackgroundMethodTime Constrained Continuous Subgraph Search Over Streaming Graphs
Li, Y., Zou, L., ÖZSU, M. T., & Zhao, D. (2019) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00100 · Cited by 56
Finding top-k similar graphs in graph databases
Zhu, Y., Qin, L., Yu, J. X., & Cheng, H. (2012) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/2247596.2247650 · Cited by 55
“A lot of feature extraction methods have been developed in [24] [7] [27] [16] [25] [23] and techniques of feature based similarity search are summarized in [21].”
MethodInfluentialSelf-citationA Comparative Study on Exact Triangle Counting Algorithms on the GPU
Wang, L., Wang, Y., Yang, C., & Owens, J. D. (2016) · doi:10.1145/2915516.2915521 · Cited by 54
“Later, VF2 [6], QuickSI [21], GraphQL [12], GADDI [31], and SPath [32] have been proposed as improvements to Ullmann’s method.”
MethodScaling Up Subgraph Query Processing with Efficient Subgraph Matching
Sun, S., & Luo, Q. (2019) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00028 · Cited by 54
“The direct-enumeration approaches such as Ullmann [32], VF2 [6], QuickSI [28] and SPath [41] do not construct any auxiliary data structure given a query graph before enumeration, but obtain the candidate data vertices of each query vertex individually based on filters such as the neighborhood signature.”
MethodSubgraph Matching With Effective Matching Order and Indexing
Sun, S., & Luo, Q. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.2980257 · Cited by 54
“The subgraph matching problem is NP-complete [6], and a variety of algorithms [3], [5], [9], [11], [20], [23], [28] have been proposed.”
BackgroundMethodInfluentialSymmetric continuous subgraph matching with bidirectional dynamic programming
Min, S., Park, S. G., Park, K., Giammarresi, D., Italiano, G. F., & Han, W.-S. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3457390.3457395 · Cited by 53
Querying big graphs within bounded resources
Fan, W., Wang, X., & Wu, Y. (2014) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2588555.2610513 · Cited by 51
“, subgraph isomorphism [5, 28].”
Continuous Subgraph Pattern Search over Graph Streams
Wang, C., & Chen, L. (2009) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2009.132 · Cited by 50
Efficient structure similarity searches: a partition-based approach
Zhao, X. H., Xiao, C., Lin, X., Zhang, W., & Wang, Y. (2017) · The VLDB Journal · doi:10.1007/s00778-017-0487-0 · Cited by 50
“Practical algorithms to this problem includes the classic backtrack algorithm and a successive of advances leveraging bit vectors [21], degree reduction [22], and various indexes [20,25].”
BackgroundMethodSelf-citationOptimizing One-time and Continuous Subgraph Queries using Worst-case Optimal Joins
Mhedhbi, A., Kankanamge, C., & Salihoğlu, S. (2021) · ACM Transactions on Database Systems · doi:10.1145/3446980 · Cited by 50
“This algorithm has been improved with different techniques to pick better QVOs and filter partial matches, often focusing on queries with labels [17, 18, 63].”
MethodRapidFlow: an efficient approach to continuous subgraph matching
Sun, S., Sun, X., He, B., & Luo, Q. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3551793.3551803 · Cited by 49
GBLENDER: towards blending visual query formulation and query processing in graph databases
Jin, C., Bhowmick, S. S., Xiao, X., Cheng, J. S.-C., & Choi, B. K. K. (2010) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1807167.1807182 · Cited by 49
“We follow the default settings of FGI, SSI ,a ndCT as suggested in [2], [ 12 ], and [5], respectively.”
MethodResultInfluentialFast graph query processing with a low-cost index
Cheng, J. S.-C., Ke, Y., Fu, A. W.-C., & Yu, J. X. (2010) · The VLDB Journal · doi:10.1007/s00778-010-0212-8 · Cited by 49
“Almost all existing work [2,3,5,10,12,13,16,20,21,23] on either subgraph or supergraph query processing, as well as our work, assume that commonality exists among the data graphs.”
BackgroundSelf-citationCircinus: Fast Redundancy-Reduced Subgraph Matching
Jin, T., Li, B., Li, Y., Zhou, Q., Ma, Q., Zhao, Y., Chen, H., & Cheng, J. S.-C. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3588692 · Cited by 48
“…matches caused by graph automorphism [1, 8, 11, 12, 17, 34, 38, 39, 46], computation sharing among query vertices with equivalence relationship [15, 20, 30, 34], candidate pruning [2, 3, 14, 16, 18, 20, 47], and matching order selection to reduce backtracking search space [3, 14, 18, 33, 34].”
BackgroundTop- Durable Graph Pattern Queries on Temporal Graphs
Semertzidis, K., & Pitoura, E. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2823754 · Cited by 48
“The first category includes indexing algorithms [1], [4], [6], [23], [27], [28], [29] that find all embeddings for a given query and data graph.”
BackgroundEfficient bi-triangle counting for large bipartite networks
Yang, Y., Fang, Y., Orłowska, M. E., Zhang, W., & Lin, X. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3447689.3447702 · Cited by 47
“Later, VF2 [8] and QuickSI [46] were proposed by considering the order of vertices, while TurboISO [19] was developed using the concept of neighborhood equivalence class to accelerate the computation.”
MethodSelf-citationAn in-depth study of continuous subgraph matching
Sun, X., Sun, S., Luo, Q., & He, B. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3523210.3523218 · Cited by 47
Exploiting Reuse for GPU Subgraph Enumeration
Guo, W., Li, Y., & Tan, K. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3035564 · Cited by 46
“Based on the approach proposed by Ullman et al. [33], existing algorithms make improvements by various pruning heuristics [2], [7], [8], [9], [10] and selective match orders [7], [8], [26], [34].”
MethodEfficient streaming subgraph isomorphism with graph neural networks
Duong, C. T., Hoang, T. D., Yin, H., Weidlich, M., Nguyen, Q. V. H., & Aberer, K. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3446095.3446097 · Cited by 46
“, nodes [8], trees [38], or paths [45].”
BackgroundMethodInfluentialFAST: FPGA-based Subgraph Matching on Massive Graphs
Jin, X., Yang, Z., Lin, X., Yang, S., Qin, L., & Peng, Y. X. (2021) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde51399.2021.00129 · Cited by 46
“Later re-searches [14], [20], [30], [39] focus on different matching order, pruning rules, and index structure.”
BackgroundSelf-citationcuTS: scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure
Xiang, L., Khan, A. M., Serra, E., Halappanavar, M. M., & Sukumaran-Rajam, A. (2021) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3458817.3476214 · Cited by 46
Fast subgraph query processing and subgraph matching via static and dynamic equivalences
Kim, H., Choi, Y.-Y., Park, K., Lin, X., Hong, S.-H., & Han, W.-S. (2022) · The VLDB Journal · doi:10.1007/s00778-022-00749-x · Cited by 46
“Early subgraph matching algorithms such as Ullmann [43],VF2 [8],QuickSI [37], and SPath [49] obtain a candidate set by using local filters that consider the neighborhood of vertices; however, recent algorithms such as GraphQL [16], Turboiso [14], CFL-Match [3], CECI [2] and DAF [13] build auxiliary data structures on…”
MethodSelf-citationMetagraph-Based Learning on Heterogeneous Graphs
Fang, Y., Lin, W., Zheng, V. W., Wu, M., Shi, J., Chang, K. C., & Li, X. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2922956 · Cited by 44
“To compute the instances of M on G, there are a number of existing approaches [16], [17], [18], [19] based on the backtracking method, summarized as follows.”
BackgroundMethodInfluentialReinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching
Wang, H., Zhang, Y., Qin, L., Wang, W., Zhang, W., & Lin, X. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00023 · Cited by 43
Self-citationEfficient GPU-Accelerated Subgraph Matching
Sun, X., & Luo, Q. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3589326 · Cited by 42
“These GPU-based algorithms achieve signi � cant speedups over CPU-based competitors; however, they often run out of GPU memory due to ine � ective � ltering and ordering, and their breadth-� rst-search enumeration.”
MethodInfluentialEfficiently detecting structural design pattern instances based on ordered sequences
Yu, D., Zhang, P., Yang, J., Chen, Z., Chengfei Liu, A., & Chen, J. (2018) · Journal of Systems and Software · doi:10.1016/j.jss.2018.04.015 · Cited by 41
Efficient Exact Subgraph Matching via GNN-Based Path Dominance Embedding
Ye, Y., Lian, X., & Chen, M. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3654621.3654630 · Cited by 40
Lindex: a lattice-based index for graph databases
Yuan, D., & Mitra, P. (2012) · The VLDB Journal · doi:10.1007/s00778-012-0284-8 · Cited by 40
“In related works [5,13,19,23], different graph index structures have been used for different kinds of features; no index structure is general enough to support all kinds of substructure features.”
InfluentialA subgraph matching algorithm based on subgraph index for knowledge graph
Sun, Y., Li, G., Du, J., Ning, B., & Chen, H. (2021) · Frontiers of Computer Science · doi:10.1007/s11704-020-0360-y · Cited by 40
Subgraph Matching with Set Similarity in a Large Graph Database
Hong, L., Zou, L., Lian, X., & Yu, P. S. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2391125 · Cited by 40
“[19] proposed QuickSI algorithm for subgraph isomorphism optimized by choosing an search order based on some features of graphs.”
MethodA survey of typical attributed graph queries
Wang, Y., Li, Y., Fan, J., Ye, C., & Chai, M. (2020) · World Wide Web · doi:10.1007/s11280-020-00849-0 · Cited by 39
STMatch: Accelerating Graph Pattern Matching on GPU with Stack-Based Loop Optimizations
Wei, Y., & Jiang, P. (2022) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc41404.2022.00058 · Cited by 39
“Prior work has shown that a carefully selected matching order can effectively prune the exploration space and reduce the computation [5], [18], [22], [33].”
BackgroundMethodHiddenCPG: Large-Scale Vulnerable Clone Detection Using Subgraph Isomorphism of Code Property Graphs
Wi, S., Woo, S., Whang, J. J., & Son, S. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3512235 · Cited by 38
“Therefore, the direct application of a known algorithm [17, 53] does not scale well.”
BackgroundNOVA: A Novel and Efficient Framework for Finding Subgraph Isomorphism Mappings in Large Graphs
Zhu, K., Zhang, Y., Lin, X., Zhu, G., & Wang, W. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12026-8_13 · Cited by 37
“There are already a large amount of existing work([1], [2], [3], [4], [5], [6], [7]), [16] related to subgraph containment in a database containing many small( less than 100 vertices) graphs.”
BackgroundMethodSelf-citationSimilarity search on supergraph containment
Shang, H., Zhu, K., Lin, X., Zhang, Y., & Ichise, R. (2010) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2010.5447846 · Cited by 37
“Many indexing and query processing techniques have been proposed to solve these two problems [2], [3], [4], [5], [6], [7], [8], [9].”
MethodSelf-citationPGX.ISO: Parallel and Efficient In-Memory Engine for Subgraph Isomorphism
Raman, R., van Rest, O., Hong, S., Wu, Z., Chafi, H., & Banerjee, J. (2014) · doi:10.1145/2621934.2621939 · Cited by 36
“Second, there are also in-memory solutions for this problem [5, 8, 12, 11].”
BackgroundNeighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics
Dutta, S., Nayek, P., & Bhattacharya, A. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3038912.3052561 · Cited by 35
“Some earlier works targeting this problem involve tree-pruning [46], Swift-Index [36] and VF2 [11].”
BackgroundKaleido: An Efficient Out-of-core Graph Mining System on A Single Machine
Zhao, C., Zhang, Z., Xu, P., Zheng, T., & Guo, J. (2020) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde48307.2020.00064 · Cited by 35
“As it is well studied, GI is known as an NP-hard problem [31].”
BackgroundA Comparative Study on Exact Triangle Counting Algorithms on the GPU
Wang, L., Wang, Y., Yang, C., & Owens, J. D. (2016) · eScholarship (California Digital Library) · Cited by 35
HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs
Yang, Z., Zhang, W., Lin, X., Zhang, Y., & Li, S. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00160 · Cited by 34
Self-citationZeng, L. M., & Zou, L. (2018) · Frontiers of Computer Science · doi:10.1007/s11704-018-7212-z · Cited by 34
“QuickSI [26] generates a matching order based on the infrequent-labels first strategy.”
Structure and attribute index for approximate graph matching in large graphs
Zhu, L., Ng, W. K., & Cheng, J. S.-C. (2011) · Information Systems · doi:10.1016/j.is.2011.03.009 · Cited by 32
“The popularity of graph model has attracted much interest in graph research such as querying graph databases [1,5–17], approximate subgraph matching [2–4], frequent subgraph mining [18–22], and correlation subgraph discovery [23–26].”
BackgroundTowards Efficient Authenticated Subgraph Query Service in Outsourced Graph Databases
Fan, Z., Peng, Y. F., Choi, B. K. K., Xu, J., & Bhowmick, S. S. (2013) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2013.42 · Cited by 32
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.