The Complexity of Mining Maximal Frequent Subgraphs

Summary: Maps complexity of enumerating maximal frequent subgraphs for connected graph classes and labeled vs unlabeled variants under bounded support or bounded output-size. For labeled instances bounded support yields tractability (bounded output often doesn't, except labeled trees where either bound suffices); unlabeled instances are harder—NP-complete even for two unlabeled trees with support=output=2. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1604
Venue: PODS
Year: 2013
Pagerank: 5.6029996e-05
Overall Rank: 7,522 | 48.40%
DOI: 10.1145/2463664.2465222

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (IBM)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)

BibTeX Citation

@inproceedings{kimelfeld_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{The Complexity of Mining Maximal Frequent Subgraphs}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2465222},
        doi = {10.1145/2463664.2465222},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Kolaitis, Phokion G.},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,804	A Relational Framework for Classifier Engineering	2017	PODS	6.0829486e-05
10,654	The Complexity of Maximal Common Subsequence Enumeration	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
4,187	Maximally Joining Probabilistic Data	2007	PODS	6.8456588e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
2	11,267	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB
3	1,633	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
4	2,083	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
5	5,758	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD
6	11,072	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB
7	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
8	6,520	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
9	9,703	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD
10	10,654	The Complexity of Maximal Common Subsequence Enumeration	2025	PODS