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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together. https://app.cochat.ai/papers/10.1145/3299869.3319880
- The paper
- Han, M., Kim, H., Gu, G., Park, K., & Han, W.-S. (2019). Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together. Proceedings of the 2019 International Conference on Management of Data. https://doi.org/10.1145/3299869.3319880
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.