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: 4068
Venue: SIGMOD
Year: 2008
Pagerank: 9.3708222e-05
Overall Rank: 1,972 | 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,085	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.0001225302
3,119	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.7370163e-05
4,282	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB	6.7842201e-05
4,581	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.6198548e-05
5,401	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.2318138e-05
5,603	Output Space Sampling for Graph Patterns	2009	VLDB	6.153476e-05
6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.8190404e-05
6,641	GAIA: Graph Classification Using Evolutionary Computation	2010	SIGMOD	5.8162256e-05
7,231	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.6664362e-05
8,206	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.4666548e-05
9,131	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.3184767e-05
9,207	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	5.3058708e-05
9,281	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.2933125e-05
9,922	View-based Explanations for Graph Neural Networks	2024	SIGMOD	5.1955087e-05
11,072	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.093636e-05
12,241	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	5.093636e-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.0006567919
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
4,092	Traversing Itemset Lattices with Statistical Metric Pruning	2000	PODS	6.907339e-05

Semantically Similar Papers

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