@inproceedings{888b53847fd446318a6db0bf97613b44,

title = "Faster and Scalable Algorithms for Densest Subgraph and Decomposition",

abstract = "We study the densest subgraph problem (DSG) and the densest subgraph local decomposition problem (DSG-LD) in undirected graphs. We also consider supermodular generalizations of these problems. For large scale graphs simple iterative algorithms perform much better in practice than theoretically fast algorithms based on network-flow or LP solvers. Boob et al. [1] recently gave a fast iterative algorithm called GREEDY++ for DSG. It was shown in [2] that it converges to a (1 - ε) relative approximation to the optimum density in O(ε 1/2 Δ λ(G)) iterations where Δ(G) is the maximum degree and λ* is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank-Wolfe algorithm for DSG-LD that takes O(mΔ ε2(G)) iterations to converge to an ε-additive approximate local decomposition vector {\^b}, where m is number of edges in the graph. In this paper we give a new iterative algorithm for both problems that takes at most (Equation presented) iterations to converge to an ε-additive approximate local decomposition vector; each iteration can be implemented in O(m) time. We describe a fractional peeling technique which has strong empirical performance as well as theoretical guarantees. The algorithm is scalable and simple, and can be applied to graphs with hundreds of millions of edges. We test our algorithm on real and synthetic data sets and show that it provides a significant benefit over previous algorithms. The algorithm and analysis extends to hypergraphs.",

author = "Elfarouk Harb and Kent Quanrud and Chandra Chekuri",

note = "Publisher Copyright: {\textcopyright} 2022 Neural information processing systems foundation. All rights reserved.; 36th Conference on Neural Information Processing Systems, NeurIPS 2022 ; Conference date: 28-11-2022 Through 09-12-2022",

year = "2022",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

editor = "S. Koyejo and S. Mohamed and A. Agarwal and D. Belgrave and K. Cho and A. Oh",

booktitle = "Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022",

}