Research map / Learning theory and algorithms / Combinatorial and search optimization
Densest k-Subgraph Mining via a Provably Tight Relaxation
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.
Reformulates the Densest k-Subgraph problem with diagonal loading, proves the continuous relaxation is tight for lambda=1 when k is at most the max clique size (via an extended Motzkin-Straus theorem), and solves it with projection-free Frank-Wolfe and sigmoid-based parameterization with AdamW.
Problem
Finding the size-k subgraph with maximum average induced degree (Densest k-Subgraph) is NP-hard, and continuous relaxations used by prior work lacked tightness guarantees and were often hard to optimize.
Approach
Adds diagonal loading lambda*I to the adjacency matrix and relaxes the sum-to-k constraint to its convex hull; an extended Motzkin-Straus theorem shows lambda=1 makes the relaxation tight for k up to the maximum clique size, and a projection-free Frank-Wolfe method solves the relaxed problem efficiently.
Key results
- The Frank-Wolfe algorithm with diagonal loading lambda=1 generally yields better normalized edge density than baselines across most datasets and subgraph sizes while having lower computational cost.
- Theorem 2 proves that lambda=1 makes the relaxation tight for all subgraph sizes k at most the maximum clique size omega, for any graph.
- The Frank-Wolfe method scales to graphs with millions of nodes (e.g., com-Orkut with 3M vertices and 117M edges).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Frank-Wolfe algorithm for the diagonal-loading relaxation | DkS · Real-world graph benchmarks | normalized edge density | Helped |
| Use the Frank-Wolfe algorithm instead of comparable-cost baselines | DkS · Real-world graph benchmarks | execution time | Helped |
| Use AdamW with the parameterized optimization problem instead of Frank-Wolfe | DkS · Real-world graph benchmarks | normalized edge density | Mixed |
| Set diagonal loading parameter λ=1 instead of λ=10 or λ=100 (ablation) | Frank-Wolfe for DkS · Facebook | subgraph density | Helped |
| Set diagonal loading parameter λ=1 instead of λ=0 or λ=0.1 (ablation) | Frank-Wolfe for DkS · Facebook | convergence rate | Helped |
| Set diagonal loading parameter λ=1 instead of λ=0 or λ=0.1 (ablation) | Frank-Wolfe for DkS · Facebook | convergence to integer solutions | Helped |
| Use Frank-Wolfe step-size Option I instead of Option II (ablation) | Frank-Wolfe for DkS · Facebook | convergence rate | Helped |
Surprising findings
- Tightness holds for the small, data-independent value lambda=1 rather than the classical lambda >= -lambda_min(A) required for convexity.
- AdamW-based parameterization does not generally outperform the Frank-Wolfe method despite its unconstrained formulation.
Limitations
- Tightness is only guaranteed for k at most the maximum clique size omega; for k > omega no guarantee is given.
- Frank-Wolfe converges only to stationary points of a non-convex problem; results rely on post-processing projection onto the sum-to-k constraint.
- Experiments are limited to graphs from SNAP with pre-processing; the AdamW parameterization is computationally costly with PyTorch.
Experimental setup
Datasets: Facebook web-Stanford com-Youtube soc-Pokec as-Skitter com-Orkut
Benchmarks: Facebook web-Stanford com-Youtube soc-Pokec as-Skitter com-Orkut
Metrics: normalized edge density execution time
Baselines: Greedy (Feige et al. 2001) LRBO (Spannogram) L-ADMM EXPP Upper Bound
Builds on: Motzkin-Straus theorem Frank-Wolfe algorithm L-ADMM (Lovász relaxation) EXPP
Closest papers by meaning
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.89)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.88)
- Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems (ICML 2024 · similarity 0.86)
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.86)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.85)
- The Parameterized Complexity of Computing the VC-Dimension (NeurIPS 2025 · similarity 0.84)
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.