Research map / Graph learning / Graph algorithms and clustering
Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves optimal quasi-clique (OQC) is NP-hard on unweighted undirected graphs, shows that varying its parameter α traces the same size-density frontier as Densest-k-Subgraph, and uses greedy peeling to mine large low-density quasi-cliques with local community structure.
Problem
Dense subgraph discovery needs a size-density trade-off; the complexity of the optimal quasi-clique (OQC) formulation was open, and its relationship to densest-k-subgraph (DkS) and the role of its parameter α were not understood.
Approach
Shows via a reduction from MAXCLIQUE (using Turán's theorem) that OQC is NP-hard, and that for suitable sub-intervals of α the OQC maximizers are the densest subgraphs of each size, so varying α yields the DkS optimal size-density frontier; uses the single-pass greedy peeling for OQC with post-hoc α tuning as a fast frontier approximation.
Key results
- OQC is proven NP-hard for undirected unweighted graphs via reduction from MAXCLIQUE, settling a longstanding conjecture.
- Continuous variation of α in OQC yields maximizer densities equal to those of DkS across sizes, with OQC maximizers coinciding with DkS maximizers for all α except when densities repeat across sizes.
- On Facebook, greedy OQC with α=0.99 yields a clique of size 69, and α=1/3 yields a size-200 subgraph with density 0.78; low-density (5-10%) large subgraphs exhibit local community structure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase α from 1/3 to 0.99 (ablation) | greedyOQC on Facebook · Facebook | density | Helped |
| Increase α from 1/3 to 0.99 (ablation) | greedyOQC on Facebook · Facebook | subgraph size: 200 -> 69 | Hurt |
| Use smaller α to extract larger, loosely connected subgraphs | OQC · Real-world graphs | local community structure | Helped |
Surprising findings
- Large, sparse quasi-cliques with density as low as 5-10% exhibit well-defined local community structure despite OQC not explicitly promoting communities.
- The recommended alpha=1/3 can be suboptimal; larger alpha values retrieve denser subgraphs.
Limitations
- Greedy peeling gives a coarse frontier with gaps (limited resolution) compared to DkS methods.
- Theoretical α sub-intervals depend on unknown graph parameters, so α must be chosen empirically.
- Equivalence of maximizers holds only up to repeated-density cases; Assumption 1 of unique densities is not without loss of generality.
Experimental setup
Datasets: Facebook SOC-GOOGLE WEB-STANFORD MATHSCINET CA-DBLP WEB-GOOGLE PATENTS
Benchmarks: Facebook SOC-GOOGLE WEB-STANFORD MATHSCINET CA-DBLP WEB-GOOGLE PATENTS
Metrics: subgraph density subgraph size edge surplus
Baselines: DkS via ADMM convex relaxation (Konar and Sidiropoulos 2021) Densest Subgraph peeling (Charikar 2000) GMDSG
Builds on: optimal quasi-clique (Tsourakakis et al. 2013) greedy peeling (Charikar 2000) Densest-k-Subgraph Turán's theorem
Closest papers by meaning
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.89)
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.88)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.88)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.88)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.87)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.