The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
GraMi: frequent subgraph and pattern mining in a single large graph
Open accessAbstract
Mining frequent subgraphs is an important operation on graphs; it is defined as finding all subgraphs that appear frequently in a database according to a given frequency threshold. Most existing work assumes a database of many small graphs, but modern applications, such as social networks, citation graphs, or protein-protein interactions in bioinformatics, are modeled as a single large graph. In this paper we present GraMi, a novel framework for frequent subgraph mining in a single large graph. GraMi undertakes a novel approach that only finds the minimal set of instances to satisfy the frequency threshold and avoids the costly enumeration of all instances required by previous approaches. We accompany our approach with a heuristic and optimizations that significantly improve performance. Additionally, we present an extension of GraMi that mines frequent patterns. Compared to subgraphs, patterns offer a more powerful version of matching that captures transitive interactions between graph nodes (like friend of a friend) which are very common in modern applications. Finally, we present CGraMi, a version supporting structural and semantic constraints, and AGraMi, an approximate version producing results with no false positives. Our experiments on real data demonstrate that our framework is up to 2 orders of magnitude faster and discovers more interesting patterns than existing approaches.
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
(1979) · Cited by 43,841
Data mining and knowledge discovery: making sense out of data
Feyyad, U. M. (1996) · IEEE Expert · doi:10.1109/64.539013 · Cited by 4,612
Consistency in networks of relations
Mackworth, A. K. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90007-8 · Cited by 2,498
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
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
Kuramochi, M., & Karypis, G. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989534 · Cited by 1,068
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
CloseGraph: mining closed frequent graph patterns
Yan, X., & Han, J. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956784 · Cited by 635
Substructure Discovery Using Minimum Description Length and Background Knowledge
Cook, D. J., & Holder, L. B. (1994) · Journal of Artificial Intelligence Research · doi:10.1613/jair.43 · Cited by 480
Storing semistructured data with STORED
Deutsch, A., Fernández, M., & Suciu, D. M. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304220 · Cited by 454
Cited by
DeepWear: Adaptive Local Offloading for On-Wearable Deep Learning
Xu, M., Qian, F., Zhu, M., Huang, F., Pushp, S., & Liu, X. (2020) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2019.2893250 · Cited by 138
Employee Attitudes and (Digital) Collaboration Data: A Preliminary Analysis in the HRM Field
Fabbri, T., Mandreoli, F., Martoglia, R., & Scapolan, A. C. (2019) · 2019 28th International Conference on Computer Communication and Networks (ICCCN) · doi:10.1109/icccn.2019.8846957 · Cited by 20
Metadata
- Authors
- Elseidy, M., Abdelhamid, E., Skiadopoulos, S., & Kalnis, P.
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2014-03
- Volume
- 7
- Issue
- 7
- Pages
- 517-528
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2122255072
- Cited by
- 315
- References
- 25
- FWCI
- 18.10
- Type
- journal article
- Language
- en
- Open access
- green
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: GraMi: frequent subgraph and pattern mining in a single large graph. https://app.cochat.ai/papers/10.14778/2732286.2732289
- The paper
- Elseidy, M., Abdelhamid, E., Skiadopoulos, S., & Kalnis, P. (2014). GraMi: frequent subgraph and pattern mining in a single large graph. Proceedings of the VLDB Endowment. https://doi.org/10.14778/2732286.2732289
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.