Mining Significant Graph Patterns by Leap Search

Summary: Introduces LEAP, a framework for mining the most significant graph patterns under general, non-antimonotonic objectives. Structural leap search and frequency-descending mining rapidly identify highly significant patterns, outperforming branch-and-bound and enabling effective graph classification. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8e2a9ceb2b768045
Venue: SIGMOD
Year: 2008
Pagerank: 9.1871245e-05
Overall Rank: 2,013 | 86.48%
DOI: 10.1145/1376616.1376662

Incoming Non-self Citations Over Time

Authors

1. Xifeng Yan (IBM)
2. Hong Cheng (University of Illinois Urbana-Champaign)
3. Jiawei Han (University of Illinois Urbana-Champaign)
4. Philip S. Yu (University of Illinois Chicago)

BibTeX Citation

@inproceedings{yan_sigmod08,
        title = {{Mining Significant Graph Patterns by Leap Search}},
        author = {Yan, Xifeng and Cheng, Hong and Han, Jiawei and Yu, Philip S.},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376662},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376662},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012416665
3,169	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5687463e-05
4,351	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB	6.6423305e-05
4,650	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.4837167e-05
5,483	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.1113443e-05
5,730	Output Space Sampling for Graph Patterns	2009	VLDB	6.012864e-05
6,767	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6860336e-05
6,778	GAIA: Graph Classification Using Evolutionary Computation	2010	SIGMOD	5.6833217e-05
7,361	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5406351e-05
8,345	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3491485e-05
8,900	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2534908e-05
9,306	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1966832e-05
9,395	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	5.1843659e-05
9,461	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1720952e-05
10,109	View-based Explanations for Graph Neural Networks	2024	SIGMOD	5.0765311e-05
12,538	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.00064391979
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026688651
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020756016
4,181	Traversing Itemset Lattices with Statistical Metric Pruning	2000	PODS	6.7522751e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,044	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD
2	1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB
3	4,351	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB
4	4,321	On Dense Pattern Mining in Graph Streams	2010	VLDB
5	12,538	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD
6	11,587	Efficient Discovery of Significant Patterns with Few-Shot Resampling	2024	VLDB
7	5,730	Output Space Sampling for Graph Patterns	2009	VLDB
8	2,767	GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications	2005	SIGMOD
9	4,650	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB
10	7,613	Mining Attribute-structure Correlated Patterns in Large Attributed Graphs	2012	VLDB