On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis

The Densest $k$-Subgraph (D$k$S) is a fundamental combinatorial problem known for its theoretical hardness and breadth of applications. Recently, Lu et al. (AAAI 2025) introduced a penalty-based non-convex relaxation that achieves promising empirical performance; however, a rigorous theoretical understanding of its success remains unclear. In this work, we bridge this gap by providing a comprehensive theoretical analysis. We first establish the tightness of the relaxation, ensuring that the global maximum values of the original combinatorial problem and the relaxed problem coincide. Then we reveal the benign geometry of the optimization landscape by proving a strict dichotomy of stationary points: all integral stationary points are local maximizers, whereas all non-integral stationary points are strict saddles with explicit positive curvature. We propose a saddle-escaping Frank--Wolfe algorithm and prove that it achieves exact convergence to an integral local maximizer in a finite number of steps.

Finding the most tightly-connected group of a fixed size in a large network is a fundamental problem with applications in social media analysis, computational biology, and fraud detection — yet it is notoriously hard to solve. We analyze a recent relaxation approach that makes this problem tractable by adding a small diagonal term to the network's adjacency matrix. We prove that this relaxation is exact, and show that its optimization landscape has a clean structure: every candidate solution is either a genuine local optimum or an unstable point with a guaranteed uphill direction. Exploiting this structure, we propose an algorithm that deterministically escapes these unstable points and converges to an exact solution in a finite number of steps.