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.2534908e-05
Overall Rank: 8,900 | 40.19%
DOI: 10.14778/3712221.3712225
PDF: Download (CC BY-NC-ND 4.0)

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,796	MDS-FSM: Coverage-Based Frequent Subgraph Mining in Single Graphs	2026	VLDB	4.9769913e-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.00026688651
489	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017440023
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015048943
713	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014571507
961	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012830477
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012416665
1,180	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011622165
1,901	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.4014537e-05
2,013	Mining Significant Graph Patterns by Leap Search	2008	SIGMOD	9.1871245e-05
2,017	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.1788573e-05
2,824	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9662478e-05
3,165	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.5735255e-05
5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1126446e-05
6,443	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	5.7814657e-05
6,506	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.758981e-05
6,816	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.6718083e-05
6,981	Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Selection of Canned Patterns for Large Networks	2021	VLDB	5.6266987e-05
8,044	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD	5.3994211e-05
8,345	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3491485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,814	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,044	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
4	5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
5	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
6	11,329	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB
7	8,345	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB
8	7,674	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
9	8,044	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD
10	6,647	Mining and Indexing Graphs for Supergraph Search	2013	VLDB