The DOI matches its Crossref record; 93 of the 93 references it cites were found in a registry or an index.
A survey of frequent subgraph mining algorithms
Abstract
Graph mining is an important research area within the domain of data mining. The field of study concentrates on the identification of frequent subgraphs within graph data sets. The research goals are directed at: (i) effective mechanisms for generating candidate subgraphs (without generating duplicates) and (ii) how best to process the generated candidate subgraphs so as to identify the desired frequent subgraphs in a way that is computationally efficient and procedurally effective. This paper presents a survey of current research in the field of frequent subgraph mining and proposes solutions to address the main research issues.
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: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Artificial intelligence: a modern approach
(1995) · Choice Reviews Online · doi:10.5860/choice.33-1577 · Cited by 21,974
Centrality in social networks conceptual clarification
Freeman, L. C. (1978) · Social Networks · doi:10.1016/0378-8733(78)90021-7 · Cited by 17,062
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368 · cited 1×
“Although Nauty was regarded as the fastest graph isomorphism algorithm by Conte et al. (2004), Miyazaki (1997) demonstrated that there exists some categories of graphs which required exponential time to generate the canonical labelling.”
MethodMining frequent patterns without candidate generation
Han, J., Pei, J., & Yin, Y. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335372 · Cited by 6,402
(2010) · Introduction to Combinatorics · doi:10.1201/b12336-12 · Cited by 5,632
Diestel, R. (1997) · Cited by 5,082
Fields, J. (2001) · Cited by 4,160
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
Data mining: an overview from a database perspective
Chen, M.-S., Han, J., & Yu, P. S. (1996) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.553155 · Cited by 2,232
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
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
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1998) · Symposium on Discrete Algorithms · doi:10.5555/314613.315045 · Cited by 1,814
PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., & Hsu, M.-C. (2005) · Proceedings 17th International Conference on Data Engineering · doi:10.1109/icde.2001.914830 · Cited by 1,791
Practical graph isomorphism, II
McKay, B. D., & Piperno, A. (2014) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2013.09.003 · Cited by 1,597
Kosala, R., & Blockeel, H. (2000) · ACM SIGKDD Explorations Newsletter · doi:10.1145/360402.360406 · Cited by 1,438
Frequent pattern mining: current status and future directions
Han, J., Cheng, H., Xin, D., & Yan, X. (2007) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-006-0059-1 · Cited by 1,380
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
Efficiently mining long patterns from databases
Bayardo, R. J. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276313 · Cited by 1,302
Web data mining: exploring hyperlinks, contents, and usage data
(2012) · Choice Reviews Online · doi:10.5860/choice.49-2718 · Cited by 1,179
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Kuramochi, M., & Karypis, G. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989534 · Cited by 1,068
An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
Inokuchi, A., Washio, T., & Motoda, H. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45372-5_2 · Cited by 1,039
Getoor, L., & Diehl, C. P. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117456 · Cited by 973
CHARM: An Efficient Algorithm for Closed Itemset Mining
Zaki, M. J., & Hsiao, C.-J. (2002) · Proceedings of the 2002 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972726.27 · Cited by 929
Fast algorithm for mining association rules
Agrawal, R. K. (1994) · Very Large Data Bases · Cited by 904
On Graph Kernels: Hardness Results and Efficient Alternatives
Gärtner, T., Flach, P., & Wrobel, S. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45167-9_11 · Cited by 879
Shortest-Path Kernels on Graphs
Borgwardt, K. M., & Kriegel, H. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.132 · Cited by 837
Gibbons, A. (1985) · Cited by 828
Conserved patterns of protein interaction in multiple species
Sharan, R., Suthram, S., Kelley, R. M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R. M., & Ideker, T. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0409522102 · Cited by 796
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 754
Marginalized kernels between labeled graphs
Kashima, H., Tsuda, K., & Inokuchi, A. (2003) · Cited by 710
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
Efficient mining of frequent subgraphs in the presence of isomorphism
Huan, J., Wang, W., & Prins, J. (2004) · Third IEEE International Conference on Data Mining · doi:10.1109/icdm.2003.1250974 · Cited by 614
Structural Descriptions and Inexact Matching
Shapiro, L. G., & Haralick, R. M. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767144 · Cited by 544
Conserved pathways within bacteria and yeast as revealed by global protein network alignment
Kelley, B. P., Sharan, R., Karp, R. M., Sittler, T., Root, D. E., Stockwell, B. R., & Ideker, T. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1534710100 · Cited by 529
A Tree Projection Algorithm for Generation of Frequent Item Sets
Agarwal, R. C., Aggarwal, C. C., & Prasad, V. V. V. (2001) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.2000.1693 · Cited by 510
Mining the Web's link structure
Chakrabarti, S., Dom, B. E., Kumar, S. R., Raghavan, P., Rajagopalan, S., Tomkins, A., Gibson, D., & Kleinberg, J. (1999) · Computer · doi:10.1109/2.781636 · Cited by 501
Structural matching in computer vision using probabilistic relaxation
Christmas, W. J., Kittler, J., & Petrou, M. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.400565 · Cited by 495
Inexact graph matching for structural pattern recognition
Bunke, H., & Allermann, G. (1983) · Pattern Recognition Letters · doi:10.1016/0167-8655(83)90033-8 · Cited by 487
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
Efficiently mining frequent trees in a forest
Zaki, M. J. (2002) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/775047.775058 · Cited by 472
Read, R. C., & Corneil, D. G. (1977) · Journal of Graph Theory · doi:10.1002/jgt.3190010410 · Cited by 453
State of the art of graph-based data mining
Washio, T., & Motoda, H. (2003) · ACM SIGKDD Explorations Newsletter · doi:10.1145/959242.959249 · Cited by 448
Mining molecular fragments: finding relevant substructures of molecules
Borgelt, C., & Berthold, M. R. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1183885 · Cited by 442
Cook, D. J., & Holder, L. B. (2000) · IEEE Intelligent Systems and their Applications · doi:10.1109/5254.850825 · Cited by 406
Efficiently mining long patterns from databases
Bayardo, R. J. (1998) · ACM SIGMOD Record · doi:10.1145/276305.276313 · Cited by 398
Algorithmics and applications of tree and graph searching
Shasha, D., Wang, J. T. L., & Giugno, R. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543620 · Cited by 387
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
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
Efficient Substructure Discovery from Large Semi-structured Data
Asai, T., Abe, K., Kawasoe, S., Arimura, H., Sakamoto, H., & Arikawa, S. (2002) · Proceedings of the 2002 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972726.10 · Cited by 364
An Improved Algorithm for Matching Large Graphs
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2001) · Cited by 358
An efficient algorithm for discovering frequent subgraphs
Kuramochi, M., & Karypis, G. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.33 · Cited by 352
A new algorithm for error-tolerant subgraph isomorphism detection
Messmer, B., & Bunke, H. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.682179 · Cited by 348
Graph Clustering and Minimum Cut Trees
Flake, G. W., Tarjan, R. E., & Tsioutsiouliklis, K. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129093 · Cited by 333
Mining coherent dense subgraphs across massive biological networks for functional discovery
Hu, H., Yan, X., Huang, Y., Han, J., & Zhou, X. J. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1049 · Cited by 333
Massive Quasi-Clique Detection
Abello, J., Resende, M. G. C., & Sudarsky, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45995-2_51 · Cited by 331
Substructure similarity search in graph databases
Yan, X., Yu, P. S., & Han, J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066244 · Cited by 314
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
Alm, E. (2003) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(03)00031-9 · Cited by 298
Algorithms on Trees and Graphs
Valiente, G. (2002) · Springer eBooks · doi:10.1007/978-3-662-04921-1 · Cited by 291
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
Complete Mining of Frequent Patterns from Graphs: Mining Graph Data
Inokuchi, A., Washio, T., & Motoda, H. (2003) · Machine Learning · doi:10.1023/a:1021726221443 · Cited by 279
Frequent Subtree Mining - An Overview
Chi, Y., Muntz, R. R., Nijssen, S., & Kok, J. N. (2004) · doi:10.5555/1227174.1227182 · Cited by 262
Proceedings of the 2010 International Conference on Data Mining
Stahlbock, R., Crone, S. F., Abou-Nasr, M., Arabnia, H. R., Kourentzes, N., Lenca, P., Lippe, W.-M., & Weiss, G. M. (2010) · HAL · Cited by 250
On mining cross-graph quasi-cliques
Pei, J., Jiang, D., & Zhang, A. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081898 · Cited by 246
On the complexity of comparing evolutionary trees
Hein, J., Jiang, T., Wang, L., & Zhang, K. (1996) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(96)00062-5 · Cited by 231
Data Structures and Algorithms with Object-Oriented Design Patterns in Java
Preiss, B. R. (1999) · Cited by 208
Zaki, M. J., & Aggarwal, C. C. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956787 · Cited by 186
TreeFinder: a first step towards XML data mining
Termier, A., Rousset, M.-C., & Sebag, M. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1183987 · Cited by 183
An efficient algorithm for detecting frequent subgraphs in biological networks
Koyutürk, M., Grama, A. Y., & Szpankowski, W. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth919 · Cited by 182
Finding frequent substructures in chemical compounds
Raedt, L. D., Toivonen, H. T. T., & King, R. D. (1998) · Lirias · Cited by 171
Mining closed relational graphs with connectivity constraints
Yan, X., Zhou, X. J., & Han, J. (2005) · doi:10.1145/1081870.1081908 · Cited by 148
A Quantitative Comparison of the Subgraph Miners MoFa, gSpan, FFSM, and Gaston
Wörlein, M. S., Meinl, T., Fischer, I., & Philippsen, M. (2005) · Lecture notes in computer science · doi:10.1007/11564126_39 · Cited by 145
Coherent closed quasi-clique discovery from large dense graph databases
Zeng, Z., Wang, J., Zhou, L., et al. (2006) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150506 · Cited by 144
The levelwise version space algorithm and its application to molecular fragment finding
Raedt, L. D., & Krämer, S. (2001) · Lirias · Cited by 134
Extracting redundancy-aware top-k patterns
Xin, D., Cheng, H., Yan, X., & Han, J. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150452 · Cited by 129
Direct mining of discriminative and essential frequent patterns via model-based search tree
Fan, W., Zhang, K., Cheng, H., Gao, J., Yan, X., Han, J., Yu, P. S., & Verscheure, O. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401922 · Cited by 126
CMTreeMiner: Mining Both Closed and Maximal Frequent Subtrees
Chi, Y., Yang, Y., Xia, Y., & Muntz, R. R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24775-3_9 · Cited by 118
Ron Shamir, A., & Tsur, D. (1999) · Journal of Algorithms · doi:10.1006/jagm.1999.1044 · Cited by 113
Canonical forms for labelled trees and their applications in frequent subtree mining
Chi, Y., Yang, Y., & Muntz, R. R. (2004) · Knowledge and Information Systems · doi:10.1007/s10115-004-0180-7 · Cited by 102
Efficient Pattern-Growth Methods for Frequent Tree Pattern Mining
Wang, C., Hong, M., Pei, J., Zhou, H., Wang, W., & Shi, B. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24775-3_54 · Cited by 98
Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks
Schreiber, F., & Schwöbbermeyer, H. (2005) · Lecture notes in computer science · doi:10.1007/11599128_7 · Cited by 95
Towards graph containment search and indexing
Chen, C., Yan, X., Yu, P. S., Han, J., Zhang, D., & Gu, X. (2007) · Cited by 86
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
Discovering frequent geometric subgraphs
Kuramochi, M., & Karypis, G. (2003) · Proceedings · doi:10.1109/icdm.2002.1183911 · Cited by 47
Tatikonda, S., Parthasarathy, S., & Kurç, T. (2006) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1183614.1183680 · Cited by 42
Graph based molecular data mining - an overview
Fischer, I., & Meinl, T. (2005) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2004.1401253 · Cited by 42
AMIOT: Induced Ordered Tree Mining in Tree-Structured Databases
Hido, S., & Kawano, H. (2006) · Proceedings · doi:10.1109/icdm.2005.20 · Cited by 38
Fast Frequent Free Tree Mining in Graph Databases
Zhao, P., & Yu, J. X. (2007) · World Wide Web · doi:10.1007/s11280-007-0031-z · Cited by 17
Cited by
Knowledge graph refinement: A survey of approaches and evaluation methods
Paulheim, H. (2016) · Semantic Web · doi:10.3233/sw-160218 · Cited by 849
Frequent itemset mining: A 25 years review
Luna, J. M., Fournier‐Viger, P., & Ventura, S. (2019) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1329 · Cited by 258
A Survey of Utility-Oriented Pattern Mining
Gan, W., Lin, J. C.-W., Fournier-Viger, P., Chao, H.-C., Tseng, V. S., & Yu, P. S. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2942594 · Cited by 257
Sifter: Scalable Sampling for Distributed Traces, without Feature Engineering
Las-Casas, P., Papakerashvili, G., Anand, V., & Mace, J. (2019) · Proceedings of the ACM Symposium on Cloud Computing · doi:10.1145/3357223.3362736 · Cited by 42
Lin, W., Ma, M., Pan, D., & Wang, P. (2018) · 2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC) · doi:10.1109/pccc.2018.8711092 · Cited by 29
“The objective of FSM is to extract all the frequent patterns in a given data set [14].”
Background
Metadata
- Authors
- Jiang, C., Coenen, F., & Zito, M.
- Venue
- The Knowledge Engineering Review
- Publisher
- Maximum Academic Press
- Published
- 2012-11-20
- Volume
- 28
- Issue
- 1
- Pages
- 75-105
- ISSN
- 0269-8889 (ISSN-L)
- 1469-8005
- OpenAlex
- W1985644065
- Cited by
- 346
- References
- 93
- FWCI
- 26.23
- 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.