- Rating
- 4(+1)
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the densest k-subgraph (DkS) problem through a diagonally loaded relaxation over the capped simplex. The authors develop a minorization–maximization (MM) framework and propose degree-adaptive algorithms to tackle DkS. Empirically, the proposed algorithms achieve strong solution quality and favorable runtime compared with baselines on several real-world networks.
Critical strengths
-
The paper is well motivated and targets an important graph mining problem. The degree-adaptive construction is intuitive and well aligned with the heterogeneous degree structure of real-world networks.
-
The empirical results are strong and comprehensive. The comparison against strong recent baselines such as Frank–Wolfe and AdamW are convincing, and the ablation studies are comprehensive.
Critical weaknesses
-
The paper misses a closely related recent work (Lu et al., ICML 2026). That work already resolves the limitation stated in this paper that tightness is only known for k below the clique number, by proving tightness for arbitrary k when lambda>=1. It also provides a detailed landscape characterization and convergence analysis that could strengthen the motivation and theoretical discussion of the present MM framework.
-
The paper states an O(m+n) cost per MM iteration, but the solving the inner problem exactly takes O(nlogn) as shown in Proposition 4. The Newton bisection method requires O(n) per pass, while the number of passes is only shown empirically to be small in Remark 12 rather than theoretically bounded by a constant. Therefore, worst-case bound should be O(m+nlogn).
Minor comments:
-
The acronyms SQM and SLM are not explicitly defined. It would improve readability to provide their full names.
-
The terminology/citation for the "greedy peeling" baseline in Table 6 should be clarified. If the method is indeed the standard greedy peeling algorithm, the more appropriate reference would be Asahiro et al. (SWAT 1996). The current reference [11] corresponds to a different greedy algorithm.
Reference:
-
Qiheng Lu, Nicholas D. Sidiropoulos, and Aritra Konar. On Densest k-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis. ICML 2026.
-
Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. Greedily finding a dense subgraph. SWAT 1996.
Questions for authors
-
Table 5 shows that the choice of beta can substantially affect performance on Web-Stanford. How instance-dependent is the choice beta=0.5?
-
Given the recent tightness, landscape, and convergence analysis of the diagonally loaded relaxation in Lu et al. (ICML 2026), can any of those results be leveraged to strengthen the theoretical guarantees of the proposed MM framework?
-
Since scalability is an important motivation of this paper, would it be possible to include larger networks such as com-Orkut? I understand that this may be difficult given the hardware described in this paper, but such an experiment would be useful.
Thank you for the response. I would appreciate it if the authors had written a more concise response.
W2 and W3 are largely addressed. However, W1 remains unclear to me. The question was whether the iterate sequence converges (to a single point). I would consider raising the score if this is addressed.