acceptodds
Under review as a conference paper at ICLR 2027

Fast Tuning-Free Densest -Subgraph Extraction

Abstract

In this paper, we investigate the densest -subgraph (DS) problem, which asks for the vertices of a graph that induce the largest number of edges. DS 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-DS (Fast, Free of eigendecomposition, Free of hyperparameters for Densest -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-DS 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.

Primary area:
optimization
Keywords:
capped simplex, densest $k$-subgraph, hyperparameter-free optimization, non-convex optimization

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_fb5bOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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:

  1. The acronyms SQM and SLM are not explicitly defined. It would improve readability to provide their full names.

  2. 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:

  1. 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.

  2. Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. Greedily finding a dense subgraph. SWAT 1996.

Questions for authors
  1. Table 5 shows that the choice of beta can substantially affect performance on Web-Stanford. How instance-dependent is the choice beta=0.5?

  2. 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?

  3. 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.

Reviewer_JmZUOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes F3-DkS, a minorization–maximization algorithm for the diagonally loaded densest kk-subgraph relaxation---a practical way to optimize the continuous formulation of the problem. The main idea is to use diagonal weights that allow for a separable quadratic minorizer. The proposed admissible weights include spectral based weights, d_i = \max\\{-\lambda_\min - \lambda, 0\\}, signless Laplacian di=deg⁡i−λd_i = \deg_i - \lambda and a degree-adaptive weight family that generalizes the signless laplacian choice. The final algorithm uses degree-adaptive weights, avoiding eigenvalue computation. It takes larger steps by shrinking those weights and falls back to a theoretically safe update whenever the objective decreases.

Experimentally, on 7 real-world networks F³-DkS reports 57.3% mean density, compared with 52.8% for AdamW and 50.5% for Frank–Wolfe, with large gains on some instances and competitive running times.

Critical strengths
  • The proposed algorithm is eifficient and practical. The updates use sparse matrix–vector products and simple vector operation, so it can be scaled to large graphs.
  • The empirical results improve the baselines quite significantly, on several instances, together with competitive runtime.
  • The safeguard provides a simple way to use aggressive updates while preserving monotonicity under the stated assumptions.
Critical weaknesses
  • Although Theorem 10(ii) provides an O(T−1/2)O(T^{-1/2}) bound on the minimum step norm for unshrunk SQM, the paper does not establish a corresponding convergence rate for the main algorithm.
  • I don't understand the claim "The graph term therefore governs the search direction exactly". How do you define "governs the search direction". Here we have a constrained domain so it's unclear after the projection onto the domain, what actually governs the search. Especially at the uniform point, the loading term contributes equally in all coordinates.
  • It's unclear how the algorithm deals with the case when did_i is 0 or negative.

After rebuttal: the paper handles the case when did_i is 0 or negative, adds better explanation for the dynamics of the algorithm and adds a convergence result.

Questions for authors

See the weaknesses above.

  • Also the authors seem to miss out Lu, Sidiropoulos, Konar (ICML 2026), which proves the tightness of the continuous relaxation for all kk.
1 comment

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.

Reviewer_pNw2OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Authors studied fast tuning-free densest kk-subgraph extractions. In this problem the goal is to find a subset of kk nodes in the graph that have a maximum number of induced edges between them. The problem is a fundamental problem in the computer science and known to be NP-hard. They introduced F3F^3-DkSDkS algorithm (Fast, Free of eigendecomposition, Free of hyperparameters for Densest k-Subgraph extraction) by relaxing the problem to its continuous version.

Instead of assigning each vertex a boolean of being in the subgraph or not, they assign a continuous value xix_i between 0 and 1 and the total value for all vertices will be equal to k which is going to be a capped simplex. By adding a light diagonal loading, they try to force the optimization toward discrete values while ensuring the graph structure does not change. Authors assign a quadratic weight did_i for each vertex based on their degree to balance how fast high and low degree nodes can grow early on. In each step they update the values and shrink the weights to move faster, using a simple check to make sure they don't go too far. In the end they choose kk vertices with the largest values of xix_i to be in the solution. Since they avoid eigenvalue calculations, they can run each iteration in linear time.

They tested their algorithm on different real world examples from SNAP dataset and compared with baselines such as Frank-Wolfe, AdamW, and Greedy. F3F^3-DkSDkS performed better and found denser subgraphs compared to baseline while its running time is faster.

Critical strengths

The paper is well written. The algorithm runs in linear time for each iteration and beats baselines on real word dataset. It doesn’t need eigenvalue calculations or hyprparameter tuning.

Critical weaknesses

I could not get a right intuition about some parts of the paper by reading them. For example, the weight shrinkage factor is set by hand instead of something that is coming from some mathematical formalization that proved to be optimal for all graphs.

Questions for authors

1-you mentioned the algorithm is tunning-free but something that makes me confused is the fact that the fixed weight beta=1/2 is worse than beta=0 in some of the examples.

2-what is the reason the performance decreases for larger subgraphs? is it because the continuous relaxation is tight when it's below the clique number?

Comments on the paper

2 comments

Thank you for the detailed response. The rebuttal has resolved most of my questions, and I am generally satisfied with the clarifications and revisions. I would consider increasing my score if the authors could further address the following points.

1. Convergence guarantee of F³-DkS.

The sufficient-increase condition in Eq. (16) provides the convergence guarantees. However, Line 6 of Algorithm 1 still uses the original monotonicity safeguard rather than the sufficient-increase condition. I suggest updating Algorithm 1 accordingly and rerunning the F³-DkS experiments with the modified safeguard, so that the theoretical guarantees directly apply to the algorithm evaluated in the experiments.

2. Finite-step exact identification.

Lemma 12 assumes the existence of a strictly positive gradient gap. However, Lu et al. (ICML 2026, Theorem 3.7 and Corollary 4.3) show that for any non-integer λ>1\lambda>1, every integral KKT point automatically satisfies a strictly positive gradient gap. Therefore, I suggest considering a non-integer λ∈(1,2)\lambda \in (1, 2), such as λ=1.5\lambda = 1.5, as used in Lu et al. (ICML 2026). This would allow the positive gradient gap assumption to be removed and make the theoretical result more natural.

I also suggest presenting Corollary 13 more explicitly as a local finite-step identification result, since its conclusion is conditional on the existence of an integral limit point. This would help distinguish it from an unconditional finite-step convergence guarantee.

3. Additional experiments on com-Orkut.

I appreciate the additional experiments on com-Orkut. To better understand the discrepancy between the reported FW results and those in Lu et al. (AAAI 2025), I downloaded the publicly available implementation and reran FW with a maximum budget of 200 iterations. The reproduced results are summarized below:

k102030405070100Mean
FW Density (%)100.0100.096.193.189.685.278.691.8

FW reached the 200-iteration limit for some instances (e.g., k=10, 20), which may explain its lower performance under the rebuttal's 60-80 second time budget. I suggest clarifying that FW may not have fully converged and that F³-DkS's main advantage on com-Orkut is achieving comparable solution quality at lower computational cost.

4. Minor comment on the ETH-based hardness statement.

Given the recent work by OpenAI and Anthropic claiming to refute ETH, I suggest revisiting the ETH-based hardness statement in the introduction.

Thanks for the response. I have raised my rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.