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.
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
(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
Graphs-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
Finding Frequent Patterns in a Large Sparse Graph*
Kuramochi, M., & Karypis, G. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0003-9 · Cited by 371
Mining significant graph patterns by leap search
Yan, X., Cheng, H., Han, J., & Yu, P. S. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376662 · Cited by 291
Storing semistructured data with STORED
Deutsch, A., Fernandez, M., & Suciu, D. (1999) · Proceedings of the 1999 ACM SIGMOD international conference on Management of data · doi:10.1145/304182.304220 · Cited by 245
Distance-join: pattern match query in a large graph database
Zou, L., Chen, L., & Özsu, M. T. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687727 · Cited by 200
Cheng, J., Yu, J. X., Ding, B., Yu, P. S., & Wang, H. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497500 · Cited by 164
GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases
Ranu, S., & Singh, A. K. (2009) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2009.133 · Cited by 156
Frequent sub-structure-based approaches for classifying chemical compounds
Deshpande, M., Kuramochi, M., & Karypis, G. (2004) · Proceedings · doi:10.1109/icdm.2003.1250900 · Cited by 153
Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
McGregor, J. J. (1979) · Information Sciences · doi:10.1016/0020-0255(79)90023-9 · Cited by 143
gPrune: A Constraint Pushing Framework for Graph Pattern Mining
Zhu, F., Yan, X., Han, J., & Yu, P. S. (2007) · Springer eBooks · doi:10.1007/978-3-540-71701-0_38 · Cited by 79
MARGIN: Maximal frequent subgraph mining
Thomas, L. T., Valluri, S. R., & Karlapalem, K. (2010) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1839490.1839491 · Cited by 73
Visual pattern discovery for architecture image classification and product image search
Chu, W.-T., & Tsai, M.-H. (2012) · International Conference on Multimedia Retrieval · doi:10.1145/2324796.2324831 · Cited by 62
SEuS: Structure Extraction Using Summaries
Ghazizadeh, S., & Chawathe, S. S. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36182-0_9 · Cited by 58
Towards proximity pattern mining in large graphs
Khan, A., Yan, X., & Wu, K. (2010) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1807167.1807261 · Cited by 58
Hira, S., & Tsumoto, S. (2007) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2007.105 · Cited by 43
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
“We utilize GRAMI [60], a fast and versatile algorithm that automatically mines frequent subgraphs.”
MethodEmployee 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
“For this alternative approach, that we named data-driven, we foresee to exploit graph pattern mining techniques [16].”
Method
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
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.