Fast and Simple Densest Subgraph with Predictions
Thai Bui, Luan Nguyen · 2025
Read Fast and Simple Densest Subgraph with Predictions by Thai Bui, Luan Nguyen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12600.txt.
Introduction
Thai Bui, Luan Nguyen, and Hoa Vu wrote a computer science paper in two thousand twenty-five on finding the densest part of a network. The densest subgraph problem asks for the set of points with the most links among them. A harder version caps the size of that set, and it has no fast exact solution.
The authors take a learning-augmented route. A predictor, such as a trained classifier, first guesses which points belong in the answer. With a fairly good predictor, their simple methods run in linear time and land close to the best possible answer. Tests on real-world graphs back up the claims for the capped version.
Catalog record
| CREATOR | Thai Bui, Luan Nguyen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast and Simple Densest Subgraph with Predictions Thanks: [email protected], San Diego State University. Supported by NSF Grant No. 2342527. Thai Bui, Luan Nguyen Abstract We study the densest subgraph problem and its NP-hard densest at-most- k k subgraph variant through the lens of learning-augmented algorithms. We show that, given a reasonably accurate predictor that estimates whether a node belongs to the solution (e.g., a machine learning classifier), one can design simple linear-time algorithms that achieve a ( 1 − ϵ ) (1-\epsilon) approximation. Finally, we present experimental results demonstrating the effectiveness of our methods for the densest at-most- k k subgraph problem on real-world graphs. 1 Introduction Computing the densest subgraph and its variants is a well-studied problem in graph algorithms and data mining. Given a graph G=(V,E) , the density of a subgraph induced by a subset of nodes H is defined as \textup{d}(H)=\frac{|E(H)|}{|H|}. The densest subgraph problem asks to find the subgraph with the maximum possible density. Other interesting variants of this problem include the densest k subgraph, densest at-most- k subgraph, and densest at-least- k subgraph problems where H is required to have size k , \leq k , \geq k respectively [ 35 , 11 , 31 , 4 ] . The densest subgraph problem, initially explored by Picard and Queyranne [ 39 ] and Goldberg [ 30 ] , has since become central to a wide range of applications, including community detection in social networks [ 22 , 19 ] , link spam detection [ 29 , 10 ] , and computational biology [ 25 , 41 ] . Over time, faster algorithms have been proposed for the problem and its variants [ 26 , 17 , 32 ] . Additionally, the problem has been extensively studied across various computational models, including streaming [ 12 , 23 , 36 ] , dynamic [ 43 , 12 ] , massively parallel [ 8 , 7 , 27 ] , and distributed settings [ 42 , 44 ] . For a survey, see [ 33 ] . In this work, we study the densest subgraph problem and its NP-hard variant, the densest at-most- k subgraph, within the framework of learning-augmented algorithms. This approach is motivated by the observation that real-world data often exhibit underlying patterns that can be captured using machine learning. We mainly assume access to a predictor (e.g., a machine-learning model) that estimates whether a node belongs to the densest subgraph. Such a predictor is typically obtained by training a model on a dataset for which ground-truth labels are available. Designing algorithms that incorporate machine learning predictions has seen a lot of recent success and became a popular paradigm. Examples of graph problems that have been studied in this paradigm are shortest paths, maximum matching, maximum independent set, min cut, and triangle counting [ 24 , 16 , 20 , 38 , 21 , 14 ] . Many other problems in algorithms and data structures in different computational models have also been studied in this setting. For a survey, see [ 37 ] . A more comprehensive list of works can be found at [ 1 ] . In the context of the densest subgraph problem, a predictor can be viewed as a classifier that predicts whether a node belongs to the densest subgraph, based on features such as its degree, average neighbor degree, and domain-specific attributes, if available. The pitfall of outputting the predictor’s solution. However, blindly relying on the predictor’s output might result in a poor solution. The predictor may simply have low accuracy in predicting which nodes belong to the densest subgraph. This issue can often be overcome in practice by rigorous model testing and training. More dangerously, even an accurate predictor can still lead to poor approximations if it is not combined with additional algorithmic processing. One can devise a simple example in the context of the densest subgraph problem. Suppose that we have a predictor that correctly identifies 90% of the nodes in the densest subgraph. If the densest subgraph is a dense bipartite graph with partitions X,Y and |Y|=0.9(|X|+|Y|) (i.e., Y contains 90% of the nodes of the densest subgraph), and the predictor provides us with Y , simply returning Y results in a subgraph with density 0, which is arbitrarily worse than the optimal solution, even though the predictor has a 90% “recall”. See Figure 1 for an example. x_{1} x_{2} y_{1} y_{2} y_{3} y_{4} y_{5} Figure 1: Suppose that this is the densest subgraph and the predictor identifies the nodes y_{1},\ldots,y_{5} . Returning y_{1},\ldots,y_{5} will yield an infinitely bad solution with density 0. Related work. Exact algorithms for the densest subgraph problem exist using linear programming or maximum flow [ 17 , 30 ] . For unweighted graphs, Goldberg’s max-flow based algorithm runs in O(mn\log n) time [ 33 ] . One can also approximate the densest subgraph up to a 1-\epsilon factor using the multiplicative weights method to solve the dual linear program followed by a clever rounding algorithm [ 44 , 7 , 28 ] which runs in O(m\cdot 1/\epsilon^{2}\cdot\log^{2}n) time. There is, however, a simple and practical greedy 1/2 -approximation that can be implemented in O(m+n) time by Charikar [ 17 ] ; this algorithm keeps removing the node with the lowest degree from the graph and recording the densest subgraph in the process. There is also a heuristic proposed by Boob et al. [ 15 ] called Greedy++; this heuristic was later shown by Chekuri, Quanrud, and Torres [ 18 ] to run in O\left(\frac{m\Delta\log n}{\epsilon^{2}d(H^{\star})}\right) time (which is O(\epsilon^{-2}mn\log n) in the worst case). Chekuri, Quanrud, and Torres [ 18 ] also provided a flow-based \tilde{O}(m/\epsilon) time algorithm that obtains a 1-\epsilon approximation. One practical issue with the densest subgraph problem is that the densest subgraph is often too large to be useful in many real-world graphs. Instead, one may consider the problem of finding the densest subgraph with at most k nodes. This variant is NP-hard. Andersen [ 3 ] showed that an \alpha -approximation for this problem implies an O(\alpha^{2}) -approximation for the densest k subgraph problem. Furthermore, under the Exponential Time Hypothesis (ETH), no polynomial-time constant-factor approximation exists for the densest k subgraph problem [ 35 ] . Hence, the densest at-most- k -subgraph problem is also likely difficult to approximate. For the densest k subgraph problem, the current best polynomial time approximation is O(n^{1/4}) [ 11 ] . Our results. We show that, given a large partial solution to the densest subgraph or the densest at-most- k subgraph problem, there exists a simple linear-time algorithm that produces a good approximation. For ease of notation, we use (i) e(X) to denote the number of edges in the subgraph G[X] induced by X , (ii) e(X,Y) to denote the number of edges with one endpoint in X and the other in Y , and (iii) e(v,X) to denote the number of edges vu such that u\in X . Unless stated otherwise, n and m refer to the number of nodes and edges in the input graph respectively. We first address the issue of uniqueness. Throughout, we let H^{\star} denote a fixed optimal solution, and the predictor predicts membership for H^{\star}