Certified Optimality Gaps for Densest k-Subgraph Solvers

Finding the $k$ most tightly connected nodes in a network is the densest $k$-subgraph problem (D$k$S): pick exactly $k$ vertices so that as many edges as possible fall among them. Uses include fraud rings, protein complexes, and tight communities. The problem is NP-hard and, under standard complexity assumptions, cannot even be approximated well in the worst case. Recent solvers nonetheless report strong results on graphs with a hundred million edges. These solvers relax the yes/no choice of each vertex to a number between 0 and 1, then climb that smooth landscape. The catch is that their results are graded only against one another. On real graphs nobody knows the true optimum, so "method A finds 3% more edges than method B" is compatible both with "both are near-optimal" and with "both are far off." The one experiment with known answers, a planted hidden clique, found that the best such solver recovered the answer in only 9 of 20 trials.

This note proposes to replace relative scoring with per-instance certificates. For every graph and every $k$, we compute a provable upper bound on the best achievable edge count. Then every solver's output gets an absolute score: the gap to that bound. The bounds come from the same algebraic knob the solvers already use, a constant added to the diagonal of the adjacency matrix. The solvers turn that knob positive to make the relaxation exact but non-convex. Turning it sufficiently negative makes the relaxation convex, so its maximum is an efficiently computable ceiling. Where exact integer programming is feasible, we check the ceilings against true optima. The payoff is a benchmark that turns "which heuristic wins" into "how far from optimal is anyone," together with the first measurement of how much the worst-case hardness theory actually bites on real networks.

Core Claim

Write $A$ for the 0/1 adjacency matrix and $x \in \{0,1\}^n$ for the indicator of the chosen set, with $\mathbf{1}^T x = k$. Every such binary $x$ has $x^T x = k$. So for any scalar $\mu$,

$$2|E(S)| = x^T (A + \mu I) x - \mu k .$$

Densest k-Subgraph Mining via a Provably Tight Relaxation takes $\mu = \lambda \ge 1$ and maximizes over the box $[0,1]^n$ intersected with $\mathbf{1}^T x = k$. There the relaxation's maximum equals the discrete optimum, but the landscape is non-convex, so solvers find only local optima. If instead $\mu \le -\lambda_{\max}(A)$, where $\lambda_{\max}$ is the largest eigenvalue, the objective becomes concave. Its maximum over the same set is then a convex program and gives a valid upper bound $U_\mu(k)$. Around this spectral bound we would build a small family of cheap certificates. One is a degree bound: half the sum of the $k$ largest values of $\min(d_v, k-1)$, where $d_v$ is the degree of vertex $v$. Another is the trivial $\binom{k}{2}$. A third applies the concave bound restricted to vertices that survive core-based pruning. On moderate graphs we would also add an SDP bound, a tighter convex relaxation based on semidefinite programming.

The empirical claim to test has two parts. First, on real networks, although not in the worst case, these certificates close to within a few percent of the solvers' best solutions for a meaningful range of $k$. Second, grading by certified gap reorders the method rankings that the published relative-density comparisons suggest. If the first part fails, that is itself informative. It would say the integrality gaps proved by Sum-of-Squares Lower Bounds for Densest k-Subgraph and Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph are not merely worst-case pathologies but visible on social and web graphs.

Why this is the right gap

The motivating evidence is the tension inside On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis. That paper proves the loaded relaxation is exact for every $\lambda \ge 1$ and has no fractional local maxima. It also shows its saddle-escaping Frank-Wolfe method (SE-FW) reaches an integral local maximum in finitely many steps. Yet the same paper reports 9/20 planted-clique recoveries and notes that larger $\lambda$ crowds the landscape with poor local maxima.

A Scalable and Exact Relaxation for Densest $k$-Subgraph via Error Bounds proposes EP-Prox, a proximal method with an exact penalty on the box. It reports roughly 2x speedups over Lovász-extension and EXPP solvers on graphs up to LiveJournal1, but again only as relative density. Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining shows that a single greedy peeling pass traces the size-density frontier and matches ADMM relaxations. In all three papers, what counts as success is defined against other heuristics.

This is the pattern the empirical-validation literature describes. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning is a prominent example: it gives guarantees but no data. D$k$S has the reverse problem. It has data and guarantees, but the guarantees ("exact relaxation," "local optimum") are not the ones practitioners need ("close to global"), and the data cannot tell them apart.

What is new relative to the closest work is the measurement, not another solver. None of the cited D$k$S papers computes an upper bound on real graphs. None compares diagonal-loading Frank-Wolfe against EP-Prox. None reports ground-truth optima beyond planted cliques.

Research Program

The first component is the certificate library. We compute $\lambda_{\max}(A)$ by power iteration, which costs $O(m)$ per step, where $m$ is the number of edges. We then solve the concave program for $U_{-\lambda_{\max}}(k)$ with Frank-Wolfe. On a concave maximization, Frank-Wolfe's duality gap gives a rigorous bound at any stopping point, so the certificate is valid even when the solve is truncated. We would then tighten the bound in two ways. One is recomputing it on the subgraph left after pruning. The pruning uses a lower bound $L$ from any feasible solution: we remove vertices that provably cannot belong to any size-$k$ set with more than $L$ edges, testing each vertex's degree cap against the remaining budget. The other is sweeping $\mu$ between $-\lambda_{\max}$ and the most negative diagonal shift that keeps the objective concave on the constraint subspace, since that shift is smaller in magnitude and gives a tighter bound. On graphs up to tens of thousands of nodes we would add an SDP bound. We would also run a mixed-integer solver with a time limit, recording the proven optimum when the solver closes the instance.

The second component is the instance suite. It combines the real graphs already used in this literature with synthetic graphs where the answer is known. The real graphs are Facebook, ca-HepTh, ca-CondMat, web-Stanford, DBLP, roadNet, wiki-Talk, LiveJournal1 and com-Orkut. The synthetic side has three parts. Planted cliques with $k$ equal to the clique size are certified exactly by $\binom{k}{2}$. The 10-regular graphs of the SE-FW paper probe symmetric saddles. R-MAT graphs, as used in Efficient Algorithms for Densest Subgraph Discovery, let us vary how skewed the degrees are. For each graph we would use a grid of $k$ spanning small (near the clique number), medium and large. This matters because tightness behavior was historically unclear above the clique number.

The third component is a uniform harness. Every solver runs on the same machine, under the same wall-clock budget per $(G,k)$ pair and with the same restart budget. The harness logs the gap to the best certificate and, where available, to the proven optimum.

Baselines

The naive reference is greedy peeling: repeatedly delete the minimum-degree vertex and read off the set when $k$ vertices remain. It is $O(m+n)$ and has no tuning knobs. On the planted-clique test it recovered the clique 2/20 times (On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis). We would pair it with two other cheap heuristics. One is the Optimal Quasi-clique peeling sequence (Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining), which is the strongest cheap competitor because it matched ADMM relaxations. The other is the top-$k$ vertices by degree inside the deepest core.

The strongest existing methods are SE-FW and EP-Prox. SE-FW's reported figure is planted-clique recovery of 9 out of 20 instances. EP-Prox's reported figure is approximately 2x faster than Lovász relaxation and EXPP at equal or better density (A Scalable and Exact Relaxation for Densest $k$-Subgraph via Error Bounds). No reported absolute optimality gap was found on Lacuna for either method on any real graph. We also include plain Frank-Wolfe with $\lambda=1$ from Densest k-Subgraph Mining via a Provably Tight Relaxation, which isolates the value of saddle escaping. Each continuous solver gets identical initializations and identical restart counts, and we sweep $\lambda$ over the same grid for both loading-based methods. EP-Prox's step size is tuned with the same number of trial runs.

The ablations target the proposal's key ingredient, the certificate. One ablation compares rankings by certified gap against rankings by relative density. Another drops each bound component in turn (spectral, degree, pruning, SDP) to see which ones do the work. "Beating" in this study means something different from winning a leaderboard. The certificates succeed if, on exactly solved instances, the certified gap tracks the true gap within a small tolerance. They also succeed if they reveal at least one ranking reversal, or a regime in $k$ or degree skew where every solver is provably more than 10% from optimal.

Why not just…?

Why not just run an integer programming solver and get exact answers everywhere? Because D$k$S has $\binom{n}{k}$ candidate sets and inapproximability results such as Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph, exact solves will not reach LiveJournal1 or com-Orkut. We do use exact solvers where they finish, as the validation set for the cheap bounds. The certificates matter precisely for the instances the solver cannot close.

Why not just keep comparing relative density, as prior papers do? Relative density cannot separate "all methods are near-optimal" from "all methods share the same blind spot." The 9/20 planted-clique result shows that shared failure is real even for the best method. The ranking-reversal check measures directly whether this changes conclusions. If rankings never change and gaps are uniformly tiny, the honest conclusion is that current practice was adequate, and we would report that.

Why not just use greedy or quasi-clique peeling and skip continuous solvers? The quasi-clique evidence (Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining) says peeling may be enough on real graphs. The planted-clique evidence says it is not on hidden structure. This is a real threat to the continuous-relaxation line of work. The certified-gap tables would settle it per regime, and the proposal gains either way.

Why not just add random restarts to SE-FW? If many restarts drive the gap to near zero, SE-FW's local-only guarantee would stop mattering in practice. We treat this as a hypothesis to measure, not dismiss. We report the gap as a function of restart count under a fixed time budget. Without a certificate, one cannot tell when to stop restarting.

Proposed Experiments

The first decisive check is calibration. On planted cliques and on the real graphs where the integer solver finishes, we compare the cheapest certificate's gap to the true gap across the $k$ grid. We expect the spectral bound to be loosest on hub-dominated graphs, because a few very high-degree vertices inflate $\lambda_{\max}$. We expect pruning to recover much of that looseness.

The second check is head-to-head. SE-FW and EP-Prox have never been compared directly. We would run both, plus plain Frank-Wolfe, on the full suite, reporting certified gap and wall-clock time. The goal is to learn whether either family dominates, or whether the winner depends on degree skew.

The third check addresses the open question of how to choose $\lambda$. We would plot certified gap against $\lambda$ from 1 upward to show empirically where landscape crowding starts to hurt. We would also test whether warm-starting from the quasi-clique peeling set shrinks the gap.

The final check is scale. We report certified gaps on LiveJournal1 and com-Orkut, which would be the first absolute quality statements for D$k$S on graphs of that size. We would also state plainly the $k$ regimes where no bound comes close, since those are the empirical footprint of the worst-case hardness theory.