The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
An efficient algorithm for discovering frequent subgraphs
Abstract
Over the years, frequent itemset discovery algorithms have been used to find interesting patterns in various application areas. However, as data mining techniques are being increasingly applied to nontraditional domains, existing frequent pattern discovery approaches cannot be used. This is because the transaction framework that is assumed by these algorithms cannot be used to effectively model the data sets in these domains. An alternate way of modeling the objects in these data sets is to represent them using graphs. Within that model, one way of formulating the frequent pattern discovery problem is that of discovering subgraphs that occur frequently over the entire set of graphs. We present a computationally efficient algorithm, called FSG, for finding all frequent subgraphs in large graph data sets. We experimentally evaluate the performance of FSG using a variety of real and synthetic data sets. Our results show that despite the underlying complexity associated with frequent subgraph discovery, FSG is effective in finding all frequently occurring subgraphs in data sets containing more than 200,000 graph transactions and scales linearly with respect to the size of the data set.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Mining frequent patterns without candidate generation
Han, J., Pei, J., & Yin, Y. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335372 · Cited by 6,402
Learning Logical Definitions from Relations
Quinlan, J. R. (1990) · Machine Learning · doi:10.1023/a:1022699322624 · Cited by 1,644
HANSCH, C., MALONEY, P. P., FUJITA, T., & MUIR, R. M. (1962) · Nature · doi:10.1038/194178b0 · Cited by 1,056
Cited by
Frequent substructure-based approaches for classifying chemical compounds
Deshpande, M., Kuramochi, M., Wale, N., & Karypis, G. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.127 · Cited by 371
Self-citationPatterns of Influence in a Recommendation Network
Leskovec, J., Singh, A., & Kleinberg, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11731139_44 · Cited by 307
Efficiently mining frequent trees in a forest: algorithms and applications
Zaki, M. J. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.125 · Cited by 306
Frequent Subtree Mining - An Overview
Chi, Y., Muntz, R. R., Nijssen, S., & Kok, J. N. (2004) · doi:10.5555/1227174.1227182 · Cited by 262
Data Organisation for Efficient Pattern Retrieval: Indexing, Storage, and Access Structures
Koukaras, P., & Tjortjis, C. (2025) · Big Data and Cognitive Computing · doi:10.3390/bdcc9100258 · Cited by 3
Metadata
- Authors
- Kuramochi, M., & Karypis, G.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2004-09
- Volume
- 16
- Issue
- 9
- Pages
- 1038-1051
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2168209541
- Cited by
- 352
- References
- 3
- FWCI
- 78.02
- 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
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.