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.1569678e-05
Overall Rank: 2,022 | 86.45%
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,031	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012379698
3,150	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5754686e-05
4,363	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB	6.6264137e-05
4,666	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.4630612e-05
5,499	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.0913421e-05
5,744	Output Space Sampling for Graph Patterns	2009	VLDB	5.9929825e-05
6,784	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6673728e-05
6,792	GAIA: Graph Classification Using Evolutionary Computation	2010	SIGMOD	5.664537e-05
7,382	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5223652e-05
8,358	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3314609e-05
8,920	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2361195e-05
9,334	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1794997e-05
9,421	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	5.1672232e-05
9,491	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1549931e-05
10,145	View-based Explanations for Graph Neural Networks	2024	SIGMOD	5.0597449e-05
12,581	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.9605343e-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.0006440069
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026634326
333	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020712452
4,199	Traversing Itemset Lattices with Statistical Metric Pruning	2000	PODS	6.7299701e-05

Semantically Similar Papers

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