EUVIMEDEUVIMED entdecken
Crossref

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

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

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (18) · 15360-15368

DOI: 10.1609/aaai.v40i18.38562 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Ya Liu und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given an undirected graph and a size parameter k, the Densest k-Subgraph (DkS) problem extracts the subgraph on k vertices with the largest number of induced edges. While DkS is NP--hard and difficult to approximate, penalty-based continuous relaxations of the problem have recently enjoyed practical success for real-world instances of DkS. In this work, we propose a scalable and exact continuous penalization approach for DkS 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 DkS problem and one of its variants, the Densest (k1, k2) Bipartite Subgraph (Dk1k2BS) problem, demonstrate that our method achieves a favorable balance between computation cost and solution quality.

Zitieren

APA

Liu, Y., Liu, J., Ma, W., & Konar, A. (2026). A Scalable and Exact Relaxation for Densest k-Subgraph via Error Bounds. Proceedings of the AAAI Conference on Artificial Intelligence, 40(18), 15360-15368. https://doi.org/10.1609/aaai.v40i18.38562

Vancouver

Liu Y, Liu J, Ma W, Konar A. A Scalable and Exact Relaxation for Densest k-Subgraph via Error Bounds. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(18):15360-15368. doi:10.1609/aaai.v40i18.38562

BibTeX
@article{Liu2026,
  author = {Liu, Ya and Liu, Junbin and Ma, Wing-Kin and Konar, Aritra},
  title = {A Scalable and Exact Relaxation for Densest k-Subgraph via Error Bounds},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {18},
  pages = {15360--15368},
  doi = {10.1609/aaai.v40i18.38562}
}
Kostenlos starten →