The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Mining significant graph patterns by leap search
Abstract
With ever-increasing amounts of graph data from disparate sources, there has been a strong need for exploiting significant graph patterns with user-specified objective functions. Most objective functions are not antimonotonic, which could fail all of frequency-centric graph mining algorithms. In this paper, we give the first comprehensive study on general mining method aiming to find most significant patterns directly. Our new mining framework, called LEAP (Descending Leap Mine), is developed to exploit the correlation between structural similarity and significance similarity in a way that the most significant pattern could be identified quickly by searching dissimilar graph patterns. Two novel concepts, structural leap search and frequency descending mining, are proposed to support leap search in graph pattern space. Our new mining method revealed that the widely adopted branch-and-bound search in data mining literature is indeed not the best, thus sketching a new picture on scalable graph pattern discovery. Empirical results show that LEAP achieves orders of magnitude speedup in comparison with the state-of-the-art method. Furthermore, graph classifiers built on mined patterns outperform the up-to-date graph kernel method in terms of efficiency and accuracy, demonstrating the high promise of such patterns.
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
LIBSVM: A library for support vector machines
Chang, C.-C., & Lin, C.-J. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961199 · Cited by 40,918
Biometry: The Principles and Practice of Statistics in Biological Research
Sokal, R. R., & Rohlf, F. J. (1969) · Cited by 20,963
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
Biometry. The Principles and Practice of Statistics in Biological Research
Fienberg, S. E., Sokal, R. R., Rohlf, F. J., Rohlf, F. J., & Sokal, R. R. (1970) · Biometrics · doi:10.2307/2529087 · Cited by 9,364
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
Self-citationKuramochi, 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
Efficient mining of emerging patterns: discovering trends and differences
Dong, G., & Li, J. (1999) · Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/312129.312191 · Cited by 1,018
Discovery, Analysis, and Presentation of Strong Rules
Piatetsky-Shapiro, G. (1991) · Medical Entomology and Zoology · Cited by 993
Selecting the right interestingness measure for association patterns
Tan, P.-N., Kumar, V., & Srivastava, J. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775053 · Cited by 862
Cited by
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
A survey of frequent subgraph mining algorithms
Jiang, C., Coenen, F., & Zito, M. (2013) · The Knowledge Engineering Review · doi:10.1017/s0269888912000331 · Cited by 346
GraMi: frequent subgraph and pattern mining in a single large graph
Elseidy, M., Abdelhamid, E., Skiadopoulos, S., & Kalnis, P. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2732286.2732289 · Cited by 315
TUDataset: A collection of benchmark datasets for learning with graphs
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., & Neumann, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.08663 · Cited by 281
Metadata
- Authors
- Yan, X., Cheng, H., Han, J., & Yu, P. S.
- Venue
- Proceedings of the 2008 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2008-06-09
- Pages
- 433-444
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2164281374
- Cited by
- 291
- References
- 27
- FWCI
- 22.44
- Type
- conference paper
- 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: Mining significant graph patterns by leap search. https://app.cochat.ai/papers/10.1145/1376616.1376662
- The paper
- Yan, X., Cheng, H., Han, J., & Yu, P. S. (2008). Mining significant graph patterns by leap search. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. https://doi.org/10.1145/1376616.1376662
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.