Maximal Defective Clique Enumeration

Summary: Introduces maximal s-defective clique enumeration (s>0) to relax cliques; uses polynomial-delay reverse-search. Pivot-based branch-and-bound with degeneracy-order optimization beats 2^n time; extends to hereditary properties. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf2d5ad622c04b932
Venue: SIGMOD
Year: 2023
Pagerank: 6.7613076e-05
Overall Rank: 4,155 | 72.15%
DOI: 10.1145/3588931

Incoming Non-self Citations Over Time

Authors

1. Qiangqiang Dai (Beijing Institute of Technology)
2. Rong-Hua Li (Beijing Institute of Technology)
3. Meihao Liao (Beijing Institute of Technology)
4. Guoren Wang (Beijing Institute of Technology)

BibTeX Citation

@inproceedings{dai_sigmod23,
        title = {{Maximal Defective Clique Enumeration}},
        author = {Dai, Qiangqiang and Li, Rong-Hua and Liao, Meihao and Wang, Guoren},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588931},
        url = {https://dl.acm.org/doi/10.1145/3588931},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	6.0630474e-05
6,933	Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance	2025	VLDB	5.6252271e-05
8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2361195e-05
9,713	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.124163e-05
9,714	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.124163e-05
9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.0910746e-05
10,395	Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs	2027	SIGMOD	4.9605343e-05
10,572	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	4.9605343e-05
10,613	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9605343e-05
10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB	4.9605343e-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,591	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD	0.00010107236
2,314	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6412801e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,500	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD
2	10,930	Maximum Defective Biclique Search in Large Bipartite Graphs	2026	VLDB
3	11,573	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
4	1,591	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
5	10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB
6	4,753	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD
7	3,591	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
8	6,933	Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance	2025	VLDB
9	5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
10	8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD