Research map / Learning theory and algorithms / Sample complexity
Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
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.
Gives MWU and area-convexity algorithms for densest subgraph (O(log m/eps^2) and O(log m/eps) iterations, nearly-linear per iteration) plus an accelerated random coordinate descent method for dense subgraph decomposition with linear convergence O(mn log(1/eps)).
Problem
Computing (approximate) densest subgraphs and dense subgraph decompositions efficiently, with practical iterative algorithms that have strong theoretical guarantees and good dependence on the approximation error and maximum degree.
Approach
Solve Charikar's LP via MWU over edge weights with a simple oracle that greedily packs edges per vertex, recover the primal subgraph via complementary slackness and Charikar rounding without binary search; use area-convex regularizers to remove the maximum-degree factor; and adapt accelerated random coordinate descent for submodular-type decomposable minimization over base polytopes to get linear
Key results
- MWU algorithm gives (1-eps)-approximate densest subgraph in O(log m/eps^2) iterations, each O(m log Δ), total O(m log Δ log m/eps^2).
- Area-convexity algorithm achieves O(log m/eps) iterations, improving the Δ factor over prior work, with total time O(m/eps log m log Δ log(1/eps)).
- Accelerated random coordinate descent gives linear convergence for dense decomposition with expected time O(mn log(n/eps)); experiments show it outperforms FISTA and is competitive with Greedy++ on large graphs such as orkut (3M nodes, 100M edges).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the prior area-convexity approach with the proposed width reduction and oracle | Area convexity algorithm for densest subgraph · Densest subgraph (approx.) | iterations: $O\big(\frac{\Delta\log m}{\epsilon}\big)$ -> $O\big(\frac{\log m}{\epsilon}\big)$ | Helped |
| Use accelerated random coordinate descent instead of the FISTA-based algorithm | Dense subgraph decomposition · Dense subgraph decomposition | total runtime: $O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$ -> $O\left(mn\log\frac{1}{\epsilon}\right)$ | Helped |
| Use the proposed accelerated random coordinate descent and fractional peeling | Dense subgraph decomposition · Dense subgraph decomposition | total runtime: $O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$ -> $O\left(mn\log\frac{n}{\epsilon}\right)$ | Helped |
| Use MWU with the proposed direct optimization and solution construction instead of the prior MWU procedure | MWU algorithm for densest subgraph · Densest subgraph (approx.) | per-iteration time: $O(m)$ -> $O(m\log\Delta)$ | Mixed |
Limitations
- Area-convexity algorithm is more complex and less practical per iteration than the MWU approach.
- Coordinate descent analysis is omitted from the paper and relies on prior work; theoretical runtime for decomposition depends on expected rather than worst-case time.
- Practical variants modify the algorithms (random permutations instead of sampling, restarts), departing from the analyzed versions.
Experimental setup
Datasets: com-Amazon orkut eight graph datasets from prior work
Benchmarks: com-Amazon orkut
Metrics: best density over iterations wall clock time L2 norm of load vector
Baselines: Greedy++ Frank-Wolfe FISTA-based dense decomposition (Harb et al.)
Builds on: Bahmani et al. 2014 MWU densest subgraph Charikar LP rounding area convexity (Sherman) accelerated coordinate descent for submodular minimization Greedy++
Closest papers by meaning
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.87)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.86)
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.86)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.84)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.83)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.83)
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.