Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3
The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
Graph matching is essential in several fields that use structured information, such as biology, chemistry, social networks, knowledge management, document analysis and others. Except for special classes of graphs, graph matching has in the worst-case an exponential complexity; however, there are algorithms that show an acceptable execution time, as long as the graphs are not too large and not too dense. In this paper we introduce a novel subgraph isomorphism algorithm, VF3, particularly efficient in the challenging case of graphs with thousands of nodes and a high edge density. Its performance, both in terms of time and memory, has been assessed on a large dataset of 12,700 random graphs with a size up to 10,000 nodes, made publicly available. VF3 has been compared with four other state-of-the-art algorithms, and the huge experimentation required more than two years of processing time. The results confirm that VF3 definitely outperforms the other algorithms when the graphs become huge and dense, but also has a very good performance on smaller or sparser graphs.
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
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Principles of Artificial Intelligence
Nilsson, N. J. (1982) · doi:10.1007/978-3-662-09438-9 · Cited by 3,457
Taming 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 · cited 2×
“…[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…”
Metadata
- Authors
- Carletti, V., Foggia, P., Saggese, A., & Vento, M.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2018-04-01
- Volume
- 40
- Issue
- 4
- Pages
- 804-818
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2608355501
- Cited by
- 177
- References
- 3
- FWCI
- 5.05
- Type
- journal article
- 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: Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3. https://app.cochat.ai/papers/10.1109/tpami.2017.2696940
- The paper
- Carletti, V., Foggia, P., Saggese, A., & Vento, M. (2018). Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence. https://doi.org/10.1109/tpami.2017.2696940
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.