Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Abstract
Subgraph matching (or subgraph isomorphism) is one of the fundamental problems in graph analysis. Extensive research has been done to develop practical solutions for subgraph matching. The state-of-the-art algorithms such as \textsfCFL-Match and \textsfTurbo\textsubscriptiso convert a query graph into a spanning tree for obtaining candidates for each query vertex and obtaining a good matching order with the spanning tree. However, by using the spanning tree instead of the original query graph, it could lead to lower pruning power and a sub-optimal matching order. Another limitation is that they perform redundant computation in search without utilizing the knowledge learned from past computation. In this paper, we introduce three novel concepts to address these inherent limitations: 1) dynamic programming between a directed acyclic graph (DAG) and a graph, 2) adaptive matching order with DAG ordering, and 3) pruning by failing sets, which together lead to a much faster algorithm \textsfDAF for subgraph matching. Extensive experiments with real datasets show that \textsfDAF outperforms the fastest existing solution by up to orders of magnitude in terms of recursive calls as well as in terms of the elapsed time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
(1979) · Cited by 43,841
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
What is Twitter, a social network or a news media?
Kwak, H., Lee, C., Park, H., & Moon, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772751 · Cited by 6,652
Introduction to Algorithms, third edition
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009) · Cited by 2,309
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277 · cited 2×
“Most practical solutions (including VF2 [9],QuickSI [35], GraphQL [17], GADDI [46], SPath [47], Turboiso [16], and CFL-Match [5]) are based on the backtracking approach [26, 44], which recursively extends a partial embedding by mapping the next query vertex Research 15: Graphs 3 SIGMOD ’19, June 30–July 5, 2019, Amste…”
MethodA (sub)graph isomorphism algorithm for matching large graphs
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.75 · Cited by 1,477 · cited 3×
“For performance evaluation, we compare VF2 [9], QuickSI [35], GraphQL [17], GADDI [46], SPath [47], Turboiso [16], CFL-Match [5], and four versions of our algorithm: • DA-cand andDA-path: using DAG-graph DP and adaptive matching order (candidate-size order and path-size order, respectively) without pruning by failing…”
BackgroundMethodNew Specifications for Exponential Random Graph Models
Snijders, T. A. B., Pattison, P. E., Robins, G. L., & Handcock, M. S. (2006) · Sociological Methodology · doi:10.1111/j.1467-9531.2006.00176.x · Cited by 1,445 · cited 1×
“In practice, subgraph matching has a wide range of applications including RDF query processing [21], protein interaction analysis [31], chemical compound search [45], and social network analysis [12, 37].”
BackgroundAlon, N., Yuster, R., & Zwick, U. (1995) · Journal of the ACM · doi:10.1145/210332.210337 · Cited by 1,002
Proceedings of the VLDB Endowment
Alonso, G., Freire, J., Saçan, A., & Tatbul, N. (2011) · Cited by 653
Graph indexing: a frequent structure-based approach
Yan, X., Yu, P. S., & Han, J. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007607 · Cited by 637 · cited 1×
“In practice, subgraph matching has a wide range of applications including RDF query processing [21], protein interaction analysis [31], chemical compound search [45], and social network analysis [12, 37].”
BackgroundAlgorithms for approximate string matching
Ukkonen, E. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80046-2 · Cited by 610
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
Self-citationGraphs-at-a-time: query language and access methods for graph databases
He, H., & Singh, A. K. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376660 · Cited by 450
On graph query optimization in large networks
Zhao, P., & Han, J. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920887 · Cited by 427 · cited 8×
“This infrequent-path-first strategy has been shown to be effective in previous works [5, 16, 47].”
BackgroundMethodResultInfluentialTaming verification hardness: an efficient algorithm for testing subgraph isomorphism
Shang, H., Zhang, Y., Lin, X., & Yu, J. X. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453899 · Cited by 401
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 · cited 10×
“In this paper we focus on two fastest algorithms Turboiso [16] and CFL-Match [5], both of which use the general framework of backtracking in Section 1.”
BackgroundMethodInfluentialAn 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 · cited 4×
“Only the path-at-a-time strategy of SPath [47] dynamically selects the next matching vertex considering the current partial embedding, but its matching order selection is found to be far from optimal [26].”
BackgroundMethodInfluentialSelf-citationFast parallel and serial approximate string matching
Landau, G. M., & Vishkin, U. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90010-2 · Cited by 328 · cited 1×
“Dynamic programming has been one of the most popular methods to solve string problems [2, 25, 43] such as approximate string matching, and it is also used to solve tree pattern matching and mining [32, 40, 41].”
MethodGADDI: distance index based subgraph matching in biological networks
Zhang, S., Li, S., & Yang, J. (2009) · Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology · doi:10.1145/1516360.1516384 · Cited by 245
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 · cited 3×
“BoostIso [33] proposes a boosting technique that speeds up the existing subgraph matching algorithms by compressing similar vertices in the data graph.”
MethodGraph pattern matching revised for social network analysis
Fan, W. (2012) · Proceedings of the 15th International Conference on Database Theory · doi:10.1145/2274576.2274578 · Cited by 176 · cited 1×
“In practice, subgraph matching has a wide range of applications including RDF query processing [21], protein interaction analysis [31], chemical compound search [45], and social network analysis [12, 37].”
BackgroundIncremental graph pattern matching
Fan, W., Wang, X., & Wu, Y. (2013) · ACM Transactions on Database Systems · doi:10.1145/2489791 · Cited by 164 · cited 1×
“Efficient subgraph matching on streaming graphs has also been studied [8, 14, 22].”
BackgroundEfficient estimation of graphlet frequency distributions in protein–protein interaction networks
Pržulj, N., Corneil, D. G., & Jurišica, I. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl030 · Cited by 156 · cited 1×
“In practice, subgraph matching has a wide range of applications including RDF query processing [21], protein interaction analysis [31], chemical compound search [45], and social network analysis [12, 37].”
BackgroundParallel subgraph listing in a large-scale graph
Shao, Y., Cui, B., Chen, L., Ma, L., Yao, J., & Xu, N. (2014) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2588555.2588557 · Cited by 143 · cited 1×
“There are an increasing number of studies on the problem of subgraph matching in a distributed environment [3, 24, 36], where the join paradigm has been shown as the most popular strategy.”
BackgroundIosup, A., Hegeman, T., Ngai, W. L., Heldens, S., Prat-Pèrez, A., Manhardto, T., Chafio, H., Capotă, M., Sundaram, N., Anderson, M. C., et al. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3007263.3007270 · Cited by 136
TurboFlux: 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
Self-citationMa, S., Cao, Y., Fan, W., Huai, J., & Wo, T. (2014) · ACM Transactions on Database Systems · doi:10.1145/2528937 · Cited by 121
Taming 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
Self-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 · cited 1×
“In such applications, subgraph matching is a bottleneck in the overall performance because it is one of the well-known NP-hard problems [15, 42].”
BackgroundMulti-query optimization for subgraph isomorphism search
Ren, X., & Wang, J. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021929 · Cited by 71 · cited 1×
“MQOsubiso [34] proposes a multi-query optimization technique which revises existing algorithms to handle multiple query graphs efficiently.”
MethodEfficient processing of graph similarity queries with edit distance constraints
Zhao, X. H., Xiao, C., Lin, X., Wang, W., & Ishikawa, Y. (2013) · The VLDB Journal · doi:10.1007/s00778-013-0306-1 · Cited by 60 · cited 1×
“Also, there are many interesting results on other related problems such as graph similarity [48], graph simulation [27], diversified top-k matching [13], etc [7, 30, 50].”
BackgroundDistributed evaluation of subgraph queries using worst-case optimal low-memory dataflows
Ammar, K., McSherry, F., Salihoğlu, S., & Joglekar, M. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3199517.3199520 · Cited by 51
Mining tree-structured data on multicore systems
Tatikonda, S., & Parthasarathy, S. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687706 · Cited by 42
Park, H., & Kim, M.-S. (2018) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3219819.3220123 · Cited by 29
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 · cited 1×
“Also, there are many interesting results on other related problems such as graph similarity [48], graph simulation [27], diversified top-k matching [13], etc [7, 30, 50].”
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 · cited 1×
“Since YAGO is an RDF dataset, we transformed it into a graph dataset by applying the type-aware transformation proposed in [21] (a similar transformation has also been employed in [49]).”
MethodHybrid 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 · cited 1×
“Most algorithms are nicely surveyed and compared in depth [20, 26, 28].”
BackgroundAnswering subgraph queries over massive disk resident graphs
Peng, P., Zou, L., Chen, L., Lin, X., & Zhao, D. (2015) · World Wide Web · doi:10.1007/s11280-014-0322-0 · Cited by 10 · cited 1×
“Also, there are many interesting results on other related problems such as graph similarity [48], graph simulation [27], diversified top-k matching [13], etc [7, 30, 50].”
Background
Metadata
- Authors
- Han, M., Kim, H., Gu, G., Park, K., & Han, W.-S.
- Venue
- Proceedings of the 2019 International Conference on Management of Data
- Publisher
- ACM
- Published
- 2019-06-25
- Pages
- 1429-1446
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2948359422
- Cited by
- 203
- References
- 39
- FWCI
- 5.90
- Type
- conference paper
- Language
- en
- Open access
- closed
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.