A Scalable and Exact Relaxation for Densest $k$-Subgraph via Error Bounds

Ya Liu, Junbin Liu, Wing‐Kin Ma, Aritra Konar

Introduction

Identifying the densest component of a network is a cornerstone task in graph mining, with applications ranging from community detection in social networks to fraud identification in financial systems. While the standard Densest Subgraph (DSG) problem is computationally tractable, it lacks the ability to constrain the size of the resulting subgraph. This often leads to the identification of large, loosely connected components rather than the tight-knit clusters required for many practical applications.

The Densest $k$-Subgraph (D$k$S) problem addresses this by imposing a size constraint: find exactly $k$ vertices that maximize the number of internal edges. However, this constraint transforms the problem into an NP-hard challenge that is notoriously difficult to approximate. Current solutions typically face a trade-off: greedy heuristics offer speed at the cost of quality, while complex convex relaxations provide high quality but fail to scale to massive real-world datasets.

The EP-Prox Framework

This paper introduces EP-Prox, a new optimization framework that bridges the gap between theoretical exactness and practical scalability. EP-Prox leverages a penalty-based continuous relaxation to solve the D$k$S problem efficiently on graphs with millions of nodes.

The framework is built on three core technical pillars:

  1. The Error Bound Principle: Traditional methods often relax discrete constraints to a complex "convex hull," which is computationally burdensome. EP-Prox instead relaxes the search space to a simple hypercube $[0, 1]^n$ and utilizes a specific penalty function derived from error bounds. This penalty effectively "pushes" the continuous solution toward valid discrete points.
  2. Local Optima Equivalence: A significant theoretical contribution of this work is the proof that both global and local optima of the penalized continuous problem match those of the original discrete problem. This ensures that first-order optimization methods, which may converge to local minima, still yield valid and high-quality solutions to the D$k$S problem.
  3. Efficient Proximal Operator: The authors developed a non-convex proximal gradient algorithm featuring a closed-form proximal operator. This operator can be computed in $O(n \log k)$ time using a min-heap, ensuring that each iteration of the algorithm is extremely fast.

Experimental Evaluation

The authors evaluated EP-Prox on several large-scale benchmarks, including HepTh, CondMat, DBLP, roadNet, Talk, and LiveJournal1. The largest of these, LiveJournal1, contains 4.8 million nodes and 69 million edges.

Edge density comparison on the DBLP dataset across varying subgraph sizes k.

Solution Quality and Scalability

EP-Prox consistently matches or exceeds the edge density achieved by state-of-the-art methods like the Lovász relaxation and EXPP across various values of $k$. In terms of computational efficiency, EP-Prox is approximately 2x faster than previous top-tier D$k$S solvers.

Edge density comparison on the large-scale LiveJournal1 dataset.

The framework also extends to the Densest ($k_1, k_2$) Bipartite Subgraph (D$k_1k_2$BS) problem. On bipartite benchmarks like Wikipedia edits—which features over 50 million nodes and 572 million edges—EP-Prox demonstrated an order of magnitude (10x) speedup over the EXPP method while maintaining superior density.

Conclusion

EP-Prox represents a significant advancement in solving cardinality-constrained graph problems. By prioritizing algorithmic efficiency through hypercube relaxation and providing strong theoretical guarantees for local optima, the framework enables high-quality subgraph extraction at an unprecedented scale. Future work may explore applying this error-bound framework to a broader class of discrete optimization problems.

Summary updated

Abstract

Given an undirected graph and a size parameter $k$, the Densest $k$-Subgraph (D$k$S) problem extracts the subgraph on $k$ vertices with the largest number of induced edges. While D$k$S is NP--hard and difficult to approximate, penalty-based continuous relaxations of the problem have recently enjoyed practical success for real-world instances of D$k$S. In this work, we propose a scalable and exact continuous penalization approach for D$k$S using the error bound principle, which enables the design of suitable penalty functions. Notably, we develop new theoretical guarantees ensuring that both the global and local optima of the penalized problem match those of the original problem. The proposed penalized reformulation enables the use of first-order continuous optimization methods. In particular, we develop a non-convex proximal gradient algorithm, where the non-convex proximal operator can be computed in closed form, resulting in low per-iteration complexity. We also provide convergence analysis of the algorithm. Experiments on large-scale instances of the D$k$S problem and one of its variants, the Densest ($k_1, k_2$) Bipartite Subgraph (D$k_1k_2$BS) problem, demonstrate that our method achieves a favorable balance between computation cost and solution quality.
BibTeX
@inproceedings{liu2026scalable,
  author = {Ya Liu and Junbin Liu and Wing‐Kin Ma and Aritra Konar},
  title = {{A Scalable and Exact Relaxation for Densest $k$-Subgraph via Error Bounds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2026},
  doi = {10.1609/aaai.v40i18.38562},
}
Figure