Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds

Summary: Minting accelerates single-graph top-k subgraph mining under MNI by pruning candidates with tight upper bounds and reducing MNI computation via lower/upper bounds. It achieves up to 10^3× speedups and remains practical for large k. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h18d2577709bf09c3
Venue: VLDB
Year: 2025
Pagerank: 5.2559789e-05
Overall Rank: 8,891 | 40.23%
DOI: 10.14778/3712221.3712225

Incoming Non-self Citations Over Time

Authors

1. Seonho Lee (Seoul National University)
2. Yeunjun Lee (Seoul National University)
3. Kunsoo Park (Seoul National University)

BibTeX Citation

@article{lee_vldb25,
        title = {{Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds}},
        author = {Lee, Seonho and Lee, Yeunjun and Park, Kunsoo},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {3},
        pages = {557--570},
        doi = {10.14778/3712221.3712225},
        url = {https://doi.org/10.14778/3712221.3712225},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,786	MDS-FSM: Coverage-Based Frequent Subgraph Mining in Single Graphs	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.0001505607
712	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014578373
960	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012836554
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012422544
1,180	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011627669
1,900	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.4059063e-05
2,010	Mining Significant Graph Patterns by Leap Search	2008	SIGMOD	9.1914756e-05
2,014	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.1832045e-05
2,824	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9698957e-05
3,164	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.5771124e-05
5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1155396e-05
6,440	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	5.7842039e-05
6,504	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.7617085e-05
6,811	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.6744946e-05
6,978	Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Selection of Canned Patterns for Large Networks	2021	VLDB	5.6293636e-05
8,037	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD	5.4019783e-05
8,342	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3516819e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,807	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD
2	1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB
3	2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
4	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
5	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
6	11,321	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB
7	8,342	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB
8	7,668	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
9	8,037	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD
10	6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB