Fast Tuning-Free Densest $k$-Subgraph Extraction

In this paper, we investigate the densest $k$-subgraph (D$k$S) problem, which asks for the $k$ vertices of a graph that induce the largest number of edges. D$k$S is NP-hard and beyond the reach of exact methods at the scale of real networks, so practical solvers work with a continuous relaxation (in the sense of losing tightness) instead. We build our solver on the diagonally loaded relaxation over the capped simplex, which is tight below the clique number, and we prove that a light loading keeps the graph itself in control of the search direction, where the classical heavy loading does not. The difficulty is thereby displaced from modelling to optimization, since the relaxed landscape is non-convex and densely populated with stationary points of very unequal quality. Our main contribution is F${}^3$-D$k$S (Fast, Free of eigendecomposition, Free of hyperparameters for Densest $k$-Subgraph extraction), built on the minorization–maximization principle, with a family of separable minorizers indexed by a vector of weights and maximized over the capped simplex in closed form. Every member ascends monotonically to a Karush–Kuhn–Tucker point, and yet individual members reach markedly different stationary points, so that the weights select the solution rather than merely the step length. Exploiting this freedom, we single out a degree-adaptive member requiring neither tuning nor any eigenvalue computation, and we show that shrinking the weights lengthens every step while an inexpensive run-time test preserves monotone ascent. F${}^3$-D$k$S completes each iteration in time linear in the size of the graph, and extensive experiments on real-world networks show that it outperforms the state-of-the-art solvers it is compared against.