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

Qiheng Lu, Nicholas D. Sidiropoulos, Aritra Konar
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:81531-81549, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-lu26ad, title = {On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis}, author = {Lu, Qiheng and Sidiropoulos, Nicholas D. and Konar, Aritra}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {81531--81549}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/lu26ad/lu26ad.pdf}, url = {https://proceedings.mlr.press/v306/lu26ad.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis %A Qiheng Lu %A Nicholas D. Sidiropoulos %A Aritra Konar %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-lu26ad %I PMLR %P 81531--81549 %U https://proceedings.mlr.press/v306/lu26ad.html %V 306 %X 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.
APA
Lu, Q., Sidiropoulos, N.D. & Konar, A.. (2026). On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:81531-81549 Available from https://proceedings.mlr.press/v306/lu26ad.html.

Related Material