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.1914756e-05
Overall Rank: 2,010 | 86.49%
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.00012422544
3,168	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5723309e-05
4,350	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB	6.645396e-05
4,647	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.4867875e-05
5,478	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.1142386e-05
5,729	Output Space Sampling for Graph Patterns	2009	VLDB	6.0157118e-05
6,760	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6887265e-05
6,773	GAIA: Graph Classification Using Evolutionary Computation	2010	SIGMOD	5.6860134e-05
7,357	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5432592e-05
8,342	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3516819e-05
8,891	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2559789e-05
9,296	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1991444e-05
9,386	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	5.1868213e-05
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-05
10,105	View-based Explanations for Graph Neural Networks	2024	SIGMOD	5.0789354e-05
12,532	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.9793485e-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.00064420972
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
4,180	Traversing Itemset Lattices with Statistical Metric Pruning	2000	PODS	6.7554731e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,037	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,350	Mining Top-K Large Structural Patterns in a Massive Network	2011	VLDB
4	4,320	On Dense Pattern Mining in Graph Streams	2010	VLDB
5	12,532	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD
6	11,581	Efficient Discovery of Significant Patterns with Few-Shot Resampling	2024	VLDB
7	5,729	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,647	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB
10	7,606	Mining Attribute-structure Correlated Patterns in Large Attributed Graphs	2012	VLDB