Densest k-Subgraph Mining via a Provably Tight Relaxation

Qiheng Lu, Nicholas D. Sidiropoulos, Aritra KonarAAAI 2025 · OpenReview

Introduction

Finding the Densest $k$-Subgraph (DkS) is a fundamental problem in network analysis, with applications ranging from community detection in social networks to identifying functional modules in biological systems. Given a graph $G$ and an integer $k$, the goal is to find a subset of $k$ vertices that induces a subgraph with the maximum number of edges. While finding the densest subgraph of any size is solvable in polynomial time, the cardinality constraint $k$ makes the DkS problem NP-hard and notoriously difficult to approximate.

A Provably Tight Continuous Relaxation

The core challenge in DkS lies in its discrete nature. Researchers have traditionally turned to continuous relaxations—transforming the binary "in or out" decision for each node into a continuous value between 0 and 1. However, standard relaxations often fail to be "tight," meaning the optimal continuous solution does not necessarily correspond to a valid discrete subgraph.

This work introduces a novel relaxation using diagonal loading. By modifying the graph's adjacency matrix $A$ with a multiple of the identity matrix ($\lambda I$), the authors reshape the optimization landscape.

Solution sparsity over iterations for different diagonal loading values (λ).

A key theoretical contribution is the extension of the Motzkin-Straus theorem. The authors prove that for $\lambda = 1$, the relaxation is guaranteed to be tight as long as $k$ is less than or equal to the size of the graph's maximum clique ($\omega$). While theoretical guarantees are currently limited to $k \le \omega$, empirical results demonstrate that this "light" loading of $\lambda = 1$ remains highly effective for much larger values of $k$, providing a smooth landscape that avoids the local optima common in more aggressive relaxations.

Efficient Optimization with Frank-Wolfe

To scale this approach to massive real-world networks, the authors employ the Frank-Wolfe (FW) algorithm. Unlike many optimization methods that require expensive projection steps to keep variables within a valid range, Frank-Wolfe is "projection-free." In the context of DkS, each FW iteration reduces to a simple "top-$k$" selection—essentially a partial sort of the gradient vector. This allows the algorithm to scale linearly with the number of edges in the graph.

Experimental Results

The proposed method was evaluated against state-of-the-art baselines, including Greedy algorithms, L-ADMM, and EXPP, across diverse datasets from the SNAP repository, such as Facebook, web-Stanford, and com-Orkut.

Runtime comparison on the massive com-Orkut dataset across varying subgraph sizes k.

The results consistently showed that the Frank-Wolfe approach (FW) outperforms existing methods in both solution quality (edge density) and computational efficiency. On the com-Orkut dataset, which contains over 3 million nodes and 117 million edges, FW reached high-quality solutions orders of magnitude faster than sophisticated alternatives like L-ADMM.

Conclusion

By combining a theoretically grounded diagonal loading technique with the efficiency of the Frank-Wolfe algorithm, this research provides a powerful new tool for large-scale graph mining. The ability to find dense communities in networks with millions of nodes in a matter of seconds opens new possibilities for real-time network analysis. Future work aims to extend these tightness proofs to larger $k$ and explore applications in weighted and directed graphs.

Summary updated

Abstract

Given an unweighted, undirected, and simple graph, the Densest k-Subgraph (DkS) problem aims to find a subgraph of k vertices that has the maximum average induced degree. In this paper, we consider an equivalent reformulation of the DkS problem via diagonal loading. On relaxing the combinatorial constraint of the reformulated problem, we show that the resulting non-convex, continuous relaxation is tight under certain conditions by leveraging an extension of the Motzkin-Straus theorem. We utilize two projection-free approaches to solve the relaxed problem: one based on the Frank-Wolfe algorithm and the other on explicit constraint parameterization. We compare their performance to state-of-the-art baselines across various benchmarks. Our empirical results show that the Frank-Wolfe-based algorithm proposed in this paper outperforms existing baselines in terms of subgraph density and computational complexity.
BibTeX
@inproceedings{lu2025densest,
  author = {Qiheng Lu and Nicholas D. Sidiropoulos and Aritra Konar},
  title = {{Densest k-Subgraph Mining via a Provably Tight Relaxation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=JGk9zjocxC},
}
Figure