Faster and Scalable Algorithms for Densest Subgraph and Decomposition
Authors: Elfarouk Harb
Kent Quanrud
Chandra Chekuri
Venue: NeurIPS 2022 Accept (2022)
Keywords: densest subgraph
densest subgraph decomposition
scalable algorithms
supermodular
densest supermodular set
proximal gradient method

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-\epsilon)$ relative approximation to the optimum density in $O(\frac{1}{\epsilon^2} \frac{\Delta(G)}{\lambda^*})$ iterations where $\Delta(G)$ is the maximum degree and $\lambda^*$ is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank-Wolfe algorithm for DSG-LD that takes $O(\frac{m\Delta(G) }{\epsilon^2})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector $\hat{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 $O(\frac{\sqrt{m\Delta(G)}}{\epsilon})$ iterations to converge to an $\epsilon$-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.

Faster and Scalable Algorithms for Densest Subgraph and Decomposition
Harb, Elfarouk' syharb2@illinofe edu
Quanrud, Kent krq@purdue edu edu Purdue University
University of Illinois Urbana-Chame ChammaCha
Chekuri, Chandra thekuri@illime edu University of Illinois at Urbana- Chaana-Chammaign
Abstract
We study the densest subgraph problem (DSG) and the densest subgraph local decomposition problem (DSG-LD) in undirected graphs. We also consider su- permodular generalizations of these problems. For large scale graphs simple iter- ative algorithms perform much better in practice than theoretically fast algorithms based on network-flow or LP solvers. Boob et al. [1] recently gave fast iterative algorithm called GREEDY++ for DSG. It was shown in [2] that it converges
(1 e) relative approximation to the optimum density in O 2 X- iterations where A(G) is the maximum degree and X is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank- Wolfe algorithm for DSG-LD that takes 0 mA()) iterations to converge to an e-additive approximate local de-
22
composition vector b, where is number of edges in the graph.
In this paper give new iterative algorithm for both problems that takes at most
0 (//mA()) iterations to converge to an e-adiitive approximate local decompo- sition vector; each iteration be implemented in O(m) time. We deseribe 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 significant benefit over previous algorithms. The algorithm and analysis extends to hypergraphs.
1. Introduction
The densest subgraph problem (DSG) is classical problem in combinatorial optimization and has many real world applications in data mining, network analysis, and machine learning. The input for DSG is undirected graph G E) with = |E| and = [V]. The goal is to return subset S V that maximizes [E(S) where E(S) = (( E u, E 5} is the set of edges with both end points in S. DSG has a variety of applications which dense subgraphs reveal important information about the underlying network such communities. One can view it as subroutine in
[S]
'Supported in part by NSF grant 1C2-2028861. Supported part by NSF grant CCF-2129816.
"Supported in part by NSF grants CCF-2028861 and 191-19, We thank Professors Sariel Har-Peled and Ruoyu Sun from the University of Illinois Urbana Chham---aam for fruitful discussions private correspondences.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

an unsupervised clustering procedure. It is canonical problem in the broad area of dense subgraph discovery which has seen many developments and applications in the past two decades. We point the reader's attention to a (non-exhaustive) list of recent, and some not so recent, important work and the pointers therein [4, 5, 6. 7, 1, 3, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17.18, 19, 20, 21, 22, 23]. Constrained versions of DSG such as the densest k-subgraph problem DKSG, densest at most k-subgraph, and densest at least k-subgraph DALKSG are also well-studied and many of these are NP-Hard. See [24, 25, 26, 10, 6, 27] for some positive and negative results on approximation algorithms.
One of the key advantages of DSG is its polynomial -ime solvability. The first polynomial- -tmme algorithms were due to Goldberg [4] and Picard and Queuranne [28]. The decision version of DSG the following: given G and a rational number X, the density in G at least X? The algorithms in [4, 28] construct an auxiliary directed flow-network H such that the maximum flow in H allows one to answer the decision version. Binary search over À leads to the final algorithm. Maximum flow is a powerful algorithmic subroutine, however, it is not practical or scalable algorithm for modern graph data sets with millions and even billions of vertices and edges. For example, authors from [1] noted that the Goldberg's 's maximum flow algorithm failed on many large scale graphs even though they used a highly optimized maximum flow library. Charikar [5] described a linear programming formulation for DSG that gives an exact solution and has O(EE) variables and constraints. LP solvers are also unsuitable for large data sets due to memory limitations among others. Charikar [5] described very simple -approximation algorithm for DSG known the GREEDY or PEELING algorithm. The algorithm creates an ordering of the vertices as follows. The first vertex V1 is the one with the smallest degree in G' (ties broken arbitrarily). It selects 2/2 to be the smallest degree vertex in G U1. Letting G be the graph after removing f1, 02...... U--1 (with Go = G), the algorithm returns the graph among G ; G" with the highest density. The algorithm can be implemented in (m) time. The ordering created by the algorithm is the same as the one to compute a k-core decomposition of graph this is well-studied graph decomposition procedure with several applications [29]. The simplicity and the efficiency of the Greedy algorithm, and its approximation guarantees, has led to its adoption for a number of other density measures.
Despite Greedy's 's advantages, its worst-case approximation guarantee is only 1. and is worse for other density measures. The goal is to develop algorithms that obtain a (1-s) relative approximation for a given parameter& E E (0, 1) while also being scalable to large graphs. One approach to obtain such algorithms is via the dual of Charikar's LP relaxation. It is mixed packing and covering LP for a given guess of the optimal value. Such LPs can be approximately solved via iterative methods such the multiplicative weight updates (MWU) other methods based on convex optimization. Bahmani, Goel and Munagala [30] applied this methodology to obtain an algorithm that yields a (1 e)- -approximation in (mm/=²)) )ttme. Boob, Sawlani and Wang [31] described an algorithm that yields a (1 - e) >-aproxximation in (m)A(G)/E)
where (G)) is the maximum degree in G. More recently Chekuri, Quanrud and Torres [2] obtained (1 - -)aprooxiimation in (mm/s) )-time via approximate flow techniques. Some of these nice theoretical developments have not yet led to practically useful algorithms for large scale graphs. In a different direction, Boob et al. [1] described a fast iterative algorithm called GREEDY++ which builds on the Greedy algorithm and insights from the I.P relaxation. It does extremely well in experiments, and the authors conjectured that it yields (1 1-6 <) relative approximation in O ) iterations and each iteration can be implemented in O(m) time. Chekuri al. [2] proved that +REEDY++ converges (1 apppproxintttoon in O A(G) X-22 iterations where X is the optimum density. This gives evidence of the theoretical soundness of the algorithm.
Our goal in this paper is to develop new and scalable algorithms that outperform GREEDY++ ++ while having strong theoretical guarantees. In addition, we are interested in an algorithm that finds an approximate dense subgraph decomposition which gives information on the density structure of the graph and is different from another such decomposition, namely the k-core decomposition. Further, as shown in previous work [32, 2], a dense subgraph decomposition allows one to compactly rep- resent approximate solutions densest subgraphs of different sizes; in particular the representation yields a 2-approximation for densest at least k-subgraph for any given l: [32, 2].
Dense subgraph decomposition. One can show that every graph G = (V, E) admits a certain structured nested decomposition based on decreasing density. In particular, the vertex set V can partitioned into Si, S2. S₁ such that S is the unique maximal densest subgraph in G. and S; is the unique maximal densest set with respect to S U... U U.S (a formal definition is deferred to
2

---

Section 3). For each vertex e we let A denote the density of the set containing v. The existence of such a decomposition follows from the supermodularity properties of the function f() |E(S) and is implicitly known from past work on submodular functions (in particular, the classical result of Fujishige [34]) For graphs this decomposition was rediscovered by Tatti and Gionis [35, 12] under the name of locally-dense decomposition. Tatti showed that one can compute the exact decomposi- tion via n maximum flow computations. Danisch et al. [3] showed that computing the A, values can be cast as solving quadratic program that extends the LP of Charikar, and applied the Frank-Wolfe
algorithm. They showed that their algorithm needs O ( iterations (each taking O(EE)) time) to converge to an E-approximate vector. Their work shows that the Frank-Wolfe algorithm leads to a good approximation
the densest subgraph in relatively small number of iterations based on experiments. However, they do not describe a systematic way to extract a dense subgraph decom- position from the approximate vector with provable guarantees. See Figure 6.4 in Appendix 6.1 for a table summarizing known results. For DSG-LD, GREEDY++ is not proven to converge to the optimal dense decomposition load vector 4. The FRANK- TLANK-WOLFFF OOLFFF based algorithm takes O ( iterations, each taking ((m) time to converge to a (1 <) dense decomposition. Our algorithm re-
quires O VmA(G) iterations, each taking (m)) time, converge to (1 - c) dense decomposition
vector. Finally, the multiplicative weight update algorithm takes O ((AA()) iterations, each taking ((m) time. We note that the multiplicative weight update algorithm has several variants, and the one we implement is discussed in Section 5.5. Except for GREEDY++ due to the peeling nature of the algorithm, each iteration of the other algorithms are easy to parallelize.
Densest Supermodular Set. Efficient solvability of DSG can also be seen via a connection to a more general problem called the densest supermodular set problem, which we refer to DSS. A real-valued set function f 2 + R+ is said to be supermodular iff f(A) + f(B)= < f(A ((AB)) B) + B) for all A, B C V. The goal in DSS is to return S V that maximizes f(S) [S]. For any graph G = (V, E). the function f 2 + E., defined as f(S)= = ESS) for each S S V, is known to be supermodular. Hence DSS generalizes DSG. Several algorithms and structural features for DSG are easier to understand via supermodularity, as shown in recent work [2].
Notation: For undirected graph G = (V, E) and S1, S2 C V, we use E(S1, S2) for the edge set {fu E E u E St, U E S2). For a vector b E IR and a subset S C V. we let b(S) denote Eies by. We let ord (E) be the set of 2 E edges that are ordered edges we and vu for each unordered edge {u, v) E E. Finally, and n denote [E and [V] respectively.
2. Technical Contributions
We summarize the main contributions of this paper. A fast and scalable algorithm based on projections: We describe an iterative algorithm for DSG and dense subgraph decomposition based on solving a quadratic objective with linear constraints that is derived from the dual of Charikar's 's I.P. Unlike previous work [36] that relied on the Frank-Wolft method, we use a projection-based approach. The algorithm is extremely simple and highly parallelizable. We show that it converges to an e-additive approximation in O( (mmm(GG)/ iterations which is significantly better than the bound for the Frank- Wolfe method. The algorithm scales to extremely large graphs and outperforms existing algorithms in both running time and the approximation quality on almost all data sets. The algorithm and analysis generalizes to hypergraphs.
Fractional Peeling:
We introduce the idea of fractional peeling to round fractional solution the underlying LP/QP relaxation and show its effectiveness in theory and practice. In experiments it significantly outperforms ordering based rounding algorithms considered previously. We use it to obtain a provably approximate dense subgraph decomposition from a fractional solution.
We explicitly connect the result of Fujishige [34] the existence of a lexico- graphically optimal base in a polymatroid with the problem of computing a densest decomposition of a supermodular function. We show that the a vertex load vector is feasible for the dual of Charikar's LP for DSG iff it is feasible for the base contrapolymatroid associated with the supermodular func-
Connections to DSS:
'Very recently the authors of this paper were able to prove the convergence of GREEDY++ to the dense decomposition. A proof will appear in followup manuscript.
3

---

tion f(S) = E(S) induced by the graph. These connections clarify past results such as the one in [36, 2] and allow us to compare Frank-Won versus projection based methods.
Experimental evaluation: We compare five algorithms for DSG, namely GREEDY++, FRANK- WOLFF, MWU, FISTA, and FISTA-PARALLEL parallel version of FISTA. We test the algo- rithms on real world and synthetic data sets and show the effectiveness of FISTA when combined with fractional peeling.
To make the paper self contained we provide all proofs in the appendix, even for results implic- itly contained in past literature. We focus DSG (unweighted), however, the ideas generalize to hypergraphs and weighted graphs, and we leave a more in-depth exploration for future work.
3. Densest Subgraph Decomposition and Supermodularity
Let G (V, be an undirected graph. Each graph admits unique nested decomposition of de- creasing densities. This property is more transparently seen via supermodularity Let f : 2 + R+ be a non-negative supermodular set function'. For example, fix f(S) = [[S] which is supermod- ular. Supermodularity implies that there is unique inclusion-wic wise maximal densest set S₁. It is convenient to describe the decomposition in an algorithmic fashion. The algorithm calculates the in G with density \ = X = SS
maximal set S C Vo = V that maximizes [8|
[E(S)]
[((S)) For
DSS this corresponds to finding the unique maximal set S that achieves the maximum density maxs S(
In iteration i, letting U = Uisjeijj, it calculates the maximal set S; V = - U that
maximizes (|E(SUU,)) [(U())))\/SS) The algorithm described formally in Algorithm
Algorithm Dense graph decomposition (left) and dense supermodular set decomposition (right)
Uo f V/ + V
Uo + 0. Vi <- V. 0
while V/2 + do
while V2 + 0 do
x- k:
h + 4: +
S arg max 18(S)_))
S + arg max SCV-11
[8]
[8]
maximal
S maximal
U3 - US Sg, V/8 + V/- - S₁
Uk +
Sg. Vv + 1/- - Sk
return Si...., Sk
return Si,..., Sk
The algorithm outputs a partition V into St,..., Sk. where & is the dense decomposition depth of G (or any supermodular function f). With each set S;, we associate density defined as X; (IE(S)) + ES, U, 1-1)))/(SS (or in the case of f, = (J(S, U U,-1) - ((U,-1))((SA) In addition, for any for some basic properties of the dense decomposition. Specifically, the densities monotonically decrease, that is, A > A2
St, say the density of u. Au A₁. Refer to Lemma 6.2 (Appendix 6.1)
A/-
4. LP and QP for DSG and Decomposition
Charikar's [5] exact LP relaxation for DSG 4.1, and its dual 4.2 (in a slightly modified form), are given below. The primal has variable Vu for each vertex E V which indicates whether is chosen in the densest set. For each edge = {u, u} E E there is a variable z, to indicate whether it is chosen. An edge {u, o} can be chosen only if both u and are chosen which explains the constraints linking žn to Yus ye- The LP normalizes Σn, yn. to 1 for linearity, and maximizes chosen edges.
'ee restrict attention to non negnaeative supermodular set functions that satisfy f(0) = 0 and this automati- cally also implies that they are monotone, that is. (AA S. f(B) for A c B

---

max
Σ Ze
(4.1)
min max bu
(4.2)
NEV
BEB
s.t. 2e S Vau
Ve = [u, v) E F
s.t.
Luv = by
Vu E G
Ze. S y/
Ve {u, v) E
vEő(u)
Euo + Ton (u,o)E
Σ Ua 1
Luvs Tous bu 0
NEV
Ze Mu 2
The dual can be viewed as orienting each edge {u, 8) fractionally towards u and v. The orientation induces loads on the vertices and the goal is to find orientation that minimizes the maximum load over vertices. It is not hard to see that LP 4.2 is actually the same as the dual of 4.1; the variables by be replaced by single variable The optimum value of LP 4.1 and LP 4.2 is the density X = λn. However, we show that the by values have additional information.
Theorem 4.1. Let SI.... Sy and )1...., 2 be the densest subgraph decomposition of a graph G, for any u E Sy, let Ar X₁ There is an optimal solution (x* b²)) 4.2 such that b Xu.
We give two proofs, by relating 4.2 to another relaxation and using a known result of Fujishige that is captured in The- orem 4.3. We say a vector E IR is lexicographically smaller than vector b E R" if the sorted vector a (in descending order) is lexicographically smaller than the sorted vector b. Theorem 4. suggests that there exists lexicographically least optimal solution to LP 4.2 where each vertex load bu is precisely An- To obtain the lexicographic solution, it suffices to introduce some strict convexity into the objective. Let P(a,, b) denote the polyhedron defined by the constraints in 4.2. Consider the quadratic program 4.3:
direct proof using Rado's theorem [37] in Appendix 6.1, and second
min Σ by such that (xr, b) P(z,b)
(4.3)
The theorem below was shown by Danisch et al. [3] but as we will show later, this is special case of Fujishige's 's result [34] from 1980 via Theorem 4.3.
Theorem 4.2. There a unique optimum solution b" to 4.3 and for each u E V(G), b = Au-
4.1. LP and QP for DSS and densest decomposition
We will now generalize Theorem 1 and Theorem 4.2 for the DSS problem. We start by recapping the notion of contrapolymatroid (see [38]) which is the relevant notion for supermodular func- tions (as polymatroids are for submodular functions). For normalized non-negative supermodular function f: + R4, the contrapolymatroid with it is the following polyhedron
P;= f RV | x 2 0, 2(S) 2 f(S) for all S C V}
(4.4)
vector x E Py is a base xvV) = f(V). The base contrapolymatroid is defined as:
= ( x 0, x(S) > f(S) for all S S V, x(V) f(V))
(4.5)
Now consider problem 4.6 where we are given a monotone non-negative supermodular function f: 2 > , and want find the lexicographically minimal solution 3" for Problem 4.6. We will show that we can do this by instead solving Problem 4.7:
minimize
max b. wEV subject to beD B₁
minimize
Σ 62
(4.6)
NEV b
(4.7)
subject to
Bj
Theorem 4.3. Let S1, .., Sa and >iy.... DE be the densest supermodular set decomposition of f. and for any u E S,, let Xu >4. Then the following must hold
1. The solution b where b.. Aa is feasible in the base polytope (i.e E B1)
5

---

2. The lexicographically minimal solution b" for Problem 4.6 satisfies by = Au
3. The optimal solution of 4.7, b" is unique, for each E V. bu Au
We give a self-contained proof in Appendix 6.1 and note that the theorem is implied by (essen- tially equivalent to) Fujishige's 's result [34] on the existence of a lexicographically optimal base of a polymatroid with respect to a weight vector. LP 4.2 and LP 4.6 can be related via the following theorem.
Theorem 4.4. Consider graph G = (V,E) and the associated supermodular function f 2 R++ where [(S) |E(S)]. A vector b E By if and only if there is an x E (Rord(E) x 2 0 such that the pair (z, b) satisfy the constraints of the LP 4.2.
See Appendix 6.1 for proof. This implies that Theorem 4.2 is a corollary of Theorem 4.3.
5. Solving the Quadratic Program using proximal projections, and rounding
In this section we show how to approximately solve 4.3. We let (xx = Euev (Evestu) Fuo) Note that this is simply the objective function rewritten in terms of x. Similarly, let h(z) be an indicator function where h(x) if Zuv 2 and Zue + Tru = Yu,, v) E E and t00 otherwise. Then Problem 4.3 can be rewritten as minimizing the unconstrained objective f(x) + h(x) for r E Rm2m We will use a proximal gradient method to solve the problem. For that, we need two lemmas whose proofs are in Appendix 6.2.
Lemma 5.1. The Lipschitz constant o is at most (A(G) where A(G) is the max degree of G. Lemma 5.2. Let E R.2mm Define the proximal mapping prox,, (x) as the point p R22m that minimizes l|p x1|2 such that h(p) O. Then we have that for u < U, prox,, un Zun-Zunt Bont1 [Tuee Tvull < 1, prexx (z) if Jnn Twu > 1, and prox (x))ur = 0 if Tun Tmu -1. Additionally, prox,, (T))
prox,, (z)
We present the algorithm now. We are interested in the unconstrained optimization problem of minimizing f(x:) h(x:)) where f is convex, and h has an easy to compute proximal mapping. This type of problem can be solved using proximal gradient methods. From a high level, the (basic) algorithm is described Algorithm
At any iteration it has a guess for the minimizer (()), It then calculates the gradient of f and moves slightly against it. However, since this might make the new guess infeasible, uses the proximal mapping to project the new guess to a feasible solution.
Algorithm Basic Proximal Gradient Method (left) and accelerated FISTA (right)
Input: f and with prox,, (z),, learning rate a and iterations T. Initialize z(0) with h(xx(0)) = 0 for t [1, T] do
y0) (0(
(+)) prox, (2- 1) - a (V(((((-1)))
for t E [1, T) do
return x
(t) = prox,, (v) (t - aV aVy(t((-1))
(0) = (t)) + i-2 =2((()) (l1-1))
return x! (T)
While the basic proximal gradient method works, we will use an even faster (both theoretically and practically) version known as the accelerated proximal gradient method which incorporates Nesterov-like momentum terms [39] in the projection step. It has other names in the literature such as proximal gradient method with extrapolation and FISTA [40]. The algorithm outlined in Algorithm 2. We have the following known result on the FISTA algorithm.
Lemma 5.3. [40]. Let x² be the minimizer of f. Suppose that the learning rate satisfies a S L.F) 2012 11
where L(f) is the Lipschitz constant f. Then after k iterations, f(x! f(x*((
ak!
In our case, we bounded the Lipschitz constant to 2A(G) and an easy upper bound on lz) - x=
is 2m = 2) [-)). Combining this with a learning rate of Za[oy. we get the following result

---

Lemma 5.4. If FISTA is applied to the objective f(z) + h(x) as previously defined, then in the kth iteration, we have f(x(k)) f(x*)= < (l
The final FISTA algorithm for our problem is shown in Algorithm 3 in Appendix 6.2 with the correct gradient computation, projective mappings, and iteration updates. Lastly, to get good additive approximation on each Xu, we have the following result whose proof is in Appendix 6.3
After O A(G)
Theorem 5.5. Let by
Au-
1 Xu for all iterations of FISTA, we must have
[600 b" S This implies
5.1. Fractional Peeling.
Given approximate solution (6, x)) to Problem 4.3, how do we round it to obtain good densest decomposition? The natural approach is to sort the vertices in non-increasing values of b and take suffixes. This is used in [36]. This is exact rounding algorithm when b is optimum solution, however one can construct approximate solutions for which this rounding is not ideal. We describe peeling algorithm inspired by +REEDY++ [1] that takes advantage of the auxiliary information provided by the vector First, set V/ = and (()) = G. In iteration, / 2 1, peel the vertex u with minimum current load by Then, for each v E 6g-- (u). set b2 < b/ yuu (i.e subtract the fractional value of vou from v's load). Update G Gt u. Repeat this process to obtain ( G Finally, return graph G with maximum density. The algorithm can be implemented in O(m + log n)) using Fibonacci heap. We will refer to this process as fractional peeling. We show both theoretically and experimentally that fractional peeling leads better algorithms.
5.2. c-dense local decomposition
We show that fractional peeling can be used on an approximate solution to 4.3 to obtain an approxi- mate dense decomposition with theoretical guarantee. This is in contrast to previous work in [36]. We define a strong notion of approximate decomposition. Given a solution (b, x)) 4.3, we say ò is an e-load-vector if an e-approximate dense decomposition to St,..., Sk (the true dense decomposition) if
6-| S Given a partition of the vertices ....... Tr, we say the partition is
[E(T)) + [Th,, UjenTH)
[E(S)) + [E(S, Uj<iS,)
u St, T
[Th]
[
Intuitively, what this says is that every E V belongs to set Ty, that has a density that is not much less than Ag-
Theorem 5.6. Given an load vector b and an edge vector that induces b, we can calculate an <(vū + a-ppprooiemtte dense decomposition in Ó(mn) time.
The proof in Appendix 6.4. Note that the notion of error is additive and holds for every vertex u. Although the fn-factor is large, the analysis shows that one can usually obtain a much stronger bound. Qualitatively shows that fractional peeling leads to good dense decomposition 0.
5.3. Projections vs Frank- vs MWU for DSG and DSS
The Frank Wolfe method is natural to apply to solve 4.7 since each iteration requires optimizing a linear objective over the base contrapolymatroid By: this is easy and fast via the greedy algorithm, as shown originally by Edmonds in the context of polymatroids (see [38]). Danisch et al. work with 4.3. However, as we observed earlier, 4.3 is a compact way to represent the associated base polyhedron, and hence the algorithm in [36] is the same as the Frank- Wolfe algorithm applied to Hoille
4.7. The Fujishige- Wolfe minimum norm point algorithm for submodular function minimization is related but is based on Wolfe's 's method (see [41, 42]). The fact that the optimum point in the base polytope has additional information was already pointed out in [34], and also explored the con- text of size-constrained submodular function minimization by Nagano et al. [33]. The advantage of proximal gradient methods such as FISTA is their faster convergence rates when compared to the Frank- Wolfe method, although each iteration requires projection oracle for By. Our algorithm is
7

---

based on the observation that there is an ((m))-(im))) projection oracle for DSG due to the alternate characterization of By via the edge variable LP 4.2. This same observation holds for hypergraphs and we obtain a fast algorithm for them. We outline the formal details in Appendix 6.5. The multi- plicative weight update (MWU) method another broad methodology for solving linear and convex programs and there are several variants. One variant of MWU for solving 4.2 can be interpreted as a Wolle method with a certain convex objective and with a certain step size; each iteration of this algorithm is again greedy optimization over B, We provide more details in the Appendix 6.7.
5.4. A theoretically fast algorithm for approximate load vector via min-cost flow
While Algorithm 3 (detailed in Appendix 6.2) works extremely well in practice, there is room to im- prove the theoretical run time. Each iteration takes (()) time and can easily be parallelized. How- ever, in the worst-case it would need ( (G)mm//) time to get an additive e-approximation. Can obtain theoretically faster algorithm? In Appendix 6.6 we describe reduction com- puting exact minimum quadratic-cost flow in a directed network. Very recently, in a breakthrough, [43] developed near-linear time algorithm for min-cost flow and also convex-cost flows. Via their algorithm we obtain an Om ( time algorithm to get optimal dense decomposition vector. We hope that this theoretical result will inspire the development of new algorithms that are provably faster in theory while also having good empirical performance.
5.5. Frank- Wolfe and MWU
The Frank-Wolft algorithms is part of the broader family of algorithms referred to conditional linear gradient methods. These algorithms approximately minimize a convex function f(xx) over a polytope P which one do efficient linear optimization. Generally speaking, each iteration t, these algorithms start with the current point I;-1 E P and solve the linear optimization problem minge (V (xx-))² y. Let Pt be optimum solution to this; the algorithm sets 24 to be convex combination of the current point and this vertex, It = QtPr + (1 az -1 The parameter or, called the step size, controls the convergence rate. The Frank-Wolfe method often refers to the specific step size of a = 2/(t + 2) [44]. Other possibilities including a 1/t, which implies that each 24 will be a uniform combination of all previous vertices P1.P2.... Pt- This gives a slower rate of convergence proportional to In l/t, rather than 1/L (see for instance [45]).
An alternative continuous approach, popular for solving obtaining multiplicative approximations to LP's, is the multiplicative weight update framework [46]. There are several ways to lever- age the MWU framework for the densest subgraph problem (c.g.. [30, 1, 2]). We test one vari- ation that applies the MWU framework to solve LP 4.2 that minimizes the maximum load. In this case, the MWU framework implicitly tries minimize potential function that exponentiates these loads and sums them together. More formally, for a parameter 7) > O, consider the problem min In In(E Veev exp(r)b)) over b E By. As 17 + oo one can see that the optimum solution to this problem converges to the minimum load vector b". Each iteration of the MWU framework involves solving simpler linear optimization problem induced by the gradient of this potential. In the spe- cific context of DSS the línear optimization problem corresponds to the greedy algorithm over By. The greedy algorithm only depends on the ordering of V based on the current loads (and not their specific values). For this reason, when the MWU method is applied with a fixed step size (in the so- called "width- -redth--ependent MWU framework"), the MWU algorithm ends up solving the exact same sequence of optimization problems, in the exact same way, as the conditional linear gradient method with step size a = 1/t would for the objective Σn, 62! Thus the parameter 77 does not play role in this specific case, and it also follows that the MWU algorithm converges to an e-approximate load vector, although at a slightly lower rate than the Frank-Wolfe method.
nu
6. Experimental Evaluation
Datasets & Implementation Details. We ran experiments on 7 real world datasets (6 from the SNAP database [47], and 1 from [48]), and one tailored synthetic dataset (used for clarifying an important difference between all algorithms) for a total of 8 datasets. The dataset information is summarized in the table below. The CLLOSF-CI.IQUSS dataset consists of the complete bipartite graph Ka,D for d = 30 and D 2000, and 20 copics of the complete graph K₁, where h = 60.
8

---

Dataset
Vertices
Edges
Source
Dataset
Vertices
Edges
Source
Cil- Pi-Pateents
3.774,768
16.518,947
[47]
roudNet-CA
2965,206
2,766,607
[47]
com Amaa-mmaonn
334,863
925,872
[47]
Cluse- Close-Cligue Cliques
3,230
95,400
Synthetic
orkut
3,072,441
117,185.083
[48]
dblp-author
317,080
1,049,866
[47]
roadNet-PA
1,088,092
1,541,898
[47]
wiki-topcats
1,791,489
28,508,141
[47]
Readurt Loak
Roadiat Ph. Sontacds
Acaaoa Sac
Walpeda Tap Caupsio Sart Load
1.3
4:30
3:30
sobbock
1.4
2:75
10
Realist Frackaed Pullicg
Roaditt Ph. Peddiaal
Viilpeda Cargodis Flatioal Palla)
19
14-
4.50
3.7
144
riclac
kit eoplls
330
Figure 6.1: Density based on sorting loads vs fractional peeling.
We tested 5 algorithms to approximate DSG: The FISTA based algorithm (sequential, no paral- lelism),
GREEDY++ from [1], the FRANK-WOLFH based algorithm from [3], and the MWU algorithm respectively. See supplementary section for implementation details of the algorithms. Also see Appendix 6.7 for details on the specific variant of MWU we tested. All algo- rithms were implemented in C++17 and were compiled with O3 and UNROLL-LOOPS optimizations. The implementations of Algorithms FISTA,
FRANK- WOLFF, and MWU are the authors' implementations, but we used the original implementation for GREEDY++ [1] as it was extremely well optimized. We modified their implementation minimally to log basic information needed for the evaluation. experiments on Slurm- based university campus cluster. For all machines, we requested 1 node and 16 cores per experiment. The nodes had 64 GB of RAM and Xeon PHI 5100 CPUs.
ASSTA-PRRALEL used Open MPI [49] for parallelism. We ran our
Densities. In the first experiment, we ran all the algorithms for a number of iterations, and monitored the maximum density reached by the algorithm until iteration t. The density in each iteration was calculated by statically sorting the vertices by the value of their load vector, and peeling in that order and returning the maximum density subgraph in that iteration. The result is shown in Figure 6. I (Top plots, we only show 4 datasets, remaining plots in Appendix 6.7). Specifically, this does not use the fractional peeling technique we discussed. We also plot the maximum density reached by using fractional peeling instcad (Bottom plots in 6. we show datasets, remaining plots in Appendix 6.7).
When the peeling order changed from static peel (based on the load vector value) to fractional peel, the results improve dramatically. See Figure 6.1 and Appendix 6.7. In all algorithms (except MWU). fractional peeling leads a dramatic speedup in terms of the number of iterations needed to get the densest subgraph on almost all datasets. Fractional peeling provides little benefit to MWU. We can observe that for all the real world datasets, GREEDY++ and FISTA are extremely competi- tive and reach near-optimal densities in just few iterations. Meanwhile, the FRANK- WOLFF based algorithm lagged behind in the beginning, but steadily made progress towards the maximum density in later iterations. MWU strongly lagged behind all algorithms in several datasets. The only excep-

---

tion is for the has density ~ 29.5566. Mcanwhile, the remaining components have density (2) (2) = 29.5. This similar but nonidentical to the example from [1]. Note that for Ka.D and copies of K2d (for sufficiently large r, D). 3e where +REEDY++ requires O iterations to converge
dataset (see Appendix 6.7). The component in the densest subgraph
(1 e) ap- did better for this synthetic example where the densities are very close and is worth understanding in more detail.
proximation for DSG in the worst case. MWU and FRANK-WOR
Wall clock time and run-time per iteration. In the second experiment we examine the wall-clock time and time per iteration. We study the maximum density reached by an algorithm after T seconds of wall-clock time (cumulative time of all iterations). Figure 6.13 (Appendix 6.7) and last 4 plots of Figure 6.2 shows the result. As can be seen, FISTA-PARALLES and FISTA (sequential) finds the maximum density on almost all datasets in the least wall-clock time (albeit sequential FISTA are close runners if we only restrict non-parallel implementations). On the other hand, MWU performed poorly in wall-clock time, often taking orders of magnitude longer than FISTA or +REEDY++ to find suboptimal dense subgraphs. Overall, the number of iterations of FISTA is the lowest, and each iteration is fast and can be parallelized, so it is the best performer.
and FRANK-WOR
Deasiy be Reacact CA
Dosaly Ea Ro PA
Dessiyy for Artsoa
Davily for Wikgeda Dop Calgutics
477-
70.0
4.75
07.5-
paiid pochep
12-
megn
petor
04
35
20
15
Figure 6.2: Wall clock time of algorithms.
We also considered the run time per iteration for the algorithms. Figure 6.9 (appendix) shows the result. The per iteration time depends on several factors. Although all algorithms have linear or near- linear in m running time, the specific data structure used and cache performance can have substantial impact. Overall, FRANK- WOLFE (due to its simple implementation) and IISTA-PARALEE the best per-iteration performance. The average speedup per iteration from FISTA-PARALIE PARALLEL over GREEDY++ was roughly 5 fold. Note that due to the peeling nature of GREEDY ++, it cannot be parallelized like FISTA.
had
Convergence to optimal load vector. Recall that we are minimizing E. and hence the norm [b<0] gives a proxy for the convergence of the errors in b(0) In this experiment, we plotted the norm of the vector 1,(() for each algorithm in each dataset. The result is shown in Figure 6.10 (Ap- pendix 6.7). GREEDY++ does very well in the first few iterations, but slows down in its improve- ment on [B[9]] || as the number of iterations increases. In comparison, FISTA eventually surpasses GREEDY++ and reduces the error at faster rate than GREEDY++. In comparison, FRANK-WOR WOLFE and MWU start with substantial error in the b vector but quickly reduce it, however, their error was always worse that both GREEDY++ and FISTA in all iterations even when left to run 200 iterations.
Conclusion. We introduced new iterative algorithm for the densest subgraph and densest decom- position problems. We also described a new fractional peeling technique which has strong empirical performance as well as theoretical guarantees and showed experimentally how it improved almost all existing algorithms compared to static load sorting. The new algorithm is scalable and simple, and can be applied to graphs with hundreds of millions of edges. Our experiments support the theory established on the utility of the new algorithm and fractional peeling. Our work also adds value via detailed comparison of the practical performance of existing algorithms and the new algorithm. A few limitations remain for the paper. First, reducing the vn dependency in Theo- rem 5.6 is important, even if fractional peeling shows strong experimental bounds. Finally, we need to evaluate empirically the quality of the decomposition achieved by algorithms (with and without fractional peeling), and also algorithms for approximating at least l DSG and related problems via the decomposition.
10

---

References
[1] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting Densest Subgraphs Without Flow Computations, page 573-583. Association for Computing Machinery, New York, NY, USA, 2020.
[2] Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. Densest subgraph: Supermodularity. iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1531-1555.
[3] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio, Large scale (ensity-friennde graph decomposition via convex programming. In Proceedings of the 26th International Conference on World Wide Web, WWW '17, page 233-242, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee.
[4] A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171. EECS Department, University California, Berkeley, 1984.
[5] Moses Charikar. Greedy approximation algorithms for finding dense components in graph. In Klaus Jansen and Samir Khuller, editors, Approximation Algorithms for Combinatorial Op- timization, pages 94, Berlin, Heidelbbegg 2000. Springer Berlin Heidelberg.
[6] Samir Khuller and Barna Saha. On finding dense subgraphs. In Susanne Albers, Alberto Marchetti-Spaccamet Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Au- tomata, Languages and Programming, pages 597-608, Berlin, Heidelberg, 2009, Springer Berlin Heidelberg.
[7] Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V.S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. Efficient algorithms for densest subgraph discovery on large directed graphs. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 220 page 1051-1066, New York, NY, USA, 2020. Association for Computing Ma- chinery.
[8] Charalampos Tsourakakis. The k-clique densest subgraph problem. In Proceedings of the 24th International Conference World Wide Web, WWW '15, page 1122-1132, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Commit- tee.
[9] Bintao Sun, Maximilien Danisch, T-H. Hubert Chan, and Mauro Sozio. Kelist++: A sim- ple algorithm for finding k-clique densest subgraphs in large graphs. Proc. VLDB Endow. 13(10):1628-11 jun 2020.
[10] Reid Andersen and Kumar Chellapilla. Finding dense subgraphs with size bounds. In Kon- stantin Avrachenkov, Debora Donato, and Nelly Litvak, editors, Algorithms and Models for the Web-Graph, pages 25-37, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg.
[11] Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guar- antees. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, page 104-112. New York, NY, USA, 2013. Associa- tion for Computing Machinery.
[12] Nikolaj Tatti. Density-friendly graph decomposition. ACM Trans. Knowl. Discov. Data, 13(5), sep 2019.
[13] Bahman Bahmani. Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proc. VLDB Endow,, 5(5):454 jan 2012.
[14] Francesco Bonchi, David Gareía-Soriane Atsushi Miyauchi, and Charalampos E. Tsourakakis. Finding densest k-connected subgraphs. Discrete Appl. Math., 305(C):34-47, dee 2022.
11

---

[15] Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. Efficient densest subgraph computation in evolving graphs. In Proceedings of the 24th International Conference on World Wide Web, WWW *15, page 300-310, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee.
[16] Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. Densest subgraph in dynamic graph streams. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald T. San- nella, editors, Mathematical Foundations of Computer Science 2015, pages 472-482, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[17] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proceedings of the Sorty-Seventh Annual ACM Symposium on Theory of Com- puting, STOC 15, page 173-182, New York, NY, USA, 2015. Association for Computing Machinery.
[18] Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. Discovering dynamic communities in interaction networks. In Toon Calders, Floriana Esposito. Eyke Hüllermeier, and Rosa Mco, editors, Machine Learning and Knowledge Discovery in Databases, pages 678-693, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
[19] Oana Denisa Balalau, Francesco Bonchi, T-H. Hubert Chan, Francesco Gullo, and Mauro Sozio. Finding subgraphs with maximum total density and limited overlap. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, WSDM '15, page 379-388, New York, NY, USA, 2015. Association for Computing Machinery.
[20] Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Online dense subgraph discovery via blurred-graph feedback. In ICML,, 2020.
[21] Albert Angel, Nikos Sarkas, Nick Koudas, and Divesh Srivastava. Dense subgraph mainte- nance under streaming edge weight updates for real-time story identification. Proc. VILDB Endow., 56))5574-585 feb 2012.
[22] Kijung Shin, Tina Eliassi-Rade and Christos Faloutsos. Corescope: Graph mining using k-core analysis patterns, anomalies and algorithms. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 469-478, 2016.
[23] Xiangfeng Li, Shenghua Liu, Zifeng Li, Xiaotian Han, Chuan Shi, Bryan Hooi, He Huang, and Xueqi Cheng. Flowscope: Spotting money laundering based on graphs. In AAAI, 2020.
[24] Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaragha- van. Detecting high log-densities - an O(n 1/4) approximation for densest k-subgraph.
[25] U. Feige, D. Peleg, and G. Kortsarz. The dense k -subgraph problem. Algorithmica, 29(3):410-421, mar 2001.
[26] Subhash Khot. Ruling out ptas for graph min-bisection, dense k- subgraphhh and bipartite clique. SIAM Journal on Computing. 36(4):1025-100) 1071, 2006.
[27] Pasin Manurangsi. Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. ArXiv, abs/1705.03581, 2018.
[28] Jean-Claude Picard and Maurice Queyranne. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):411-59, 1982.
[29] Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazir- giannis. The core decomposition of networks: Theory, algorithms and applications. The VL.DB Journal,
92, 2020.
[30] Bahman Bahmani, Ashish Goel, and Kamesh Munagala. Efficient primal-dual graph algo- rithms for mapreduce. International Workshop on Algorithms and Models for the Web- Graph, pages 59-78. Springer, 2014.
12

---

[31] Digvijay Boob, Saurabh Sawlani, and Di Wang. Faster width-dependent algorithm for mixed packing and covering Ips. Advances in Neural Information Processing Systems (NIPS 2019), 2019.
[32] Samir Khuller and Barna Saha. On finding dense subgraphs. In International Colloquium on Automata, Languages, and Programming, pages 597-608. Springer. 2009.
[33] Kiyohito Nagano, Yoshinobu Kawahara, and Kazuyuki Aihara. Size-constrained submodular minimization through minimum norm base. In ICML, 2011.
[34] Satoru Fujishige. Lexicographically optimal base of polymatroid with respect to weight vector. Mathematics of Operations Research, 5(2): 86-196, 1980.
[35] Nikolaj Tatti and Aristides Gionis. Density-friende graph decomposition. In Proceedings of the 24th International Conference on World Wide Web, pages 1089-1099, 2015.
[36] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. Large scale decomposition via convex programming. Proceedings of the 26th International Conference on World Wide Web, pages 233-2422 2017.
graph
[37] R. Rado. Theorems on linear combinatorial topology and general measure. Annals of Mathe- maticy, 44(2):228-270, 1943.
[38] Alexander Schrijver.
Combinatorial optimization: polyhedra and efficiency, volume 24.
Springer Science & Business Media, 2003.
[39] Yurii Nesterov. A method for solving the convex programming problem with convergence rate ((1/k²). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
[40] Amir Beck and Mare Teboulle. A fast iterative shrinkage-threesholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
[41] Philip Wolfe. Finding the nearest point in polytope. Mathematical Programming, 11(1):128- 149, 1976.
[42] Satoru Fujishige and Shigueo Isotani. A submodular function minimization algorithm based on the minimum-nome base. Pacific Journal of Optimization, 7(1):3-17, 2011.
[43] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time, 2022.
[44] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna-
tional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[45] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
[46] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of computing, 8(1):121-164, 2012.
[47] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.
htsap//snap....
http:///maa...taffr.tooeo stanfordddrroooo adu/data, June 2014.
[48] Jérôme Kunegis. Konect:
The koblenz network collection. In Proceedings of the 22nd Interna- tional Conference on World Wide Web. WWW '13 Companion, page 1343-1350, New York, NY, USA, 2013. Association for Computing Machinery.
[49] Richard L. Graham, Timothy S. Woodall, and Jeffrey M. Squyres. Open mpi: flexible high performance mpi. In Roman Wyrzykowski, Jack Dongarra, Norbert Meyer, and Jerzy Wasniewski, editors, Parallel Processing and Applied Mathematics, pages 228-239, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[50] Satoru Fujishige, Theory principal partitions revisited. Research Trends Combinatorial Optimization, pages 127-162. Springer, 2009.
13

---

[51] Weiran Wang and Miguel A. Carreira-Perpinn Projection onto the probability simplex: An efficient algorithm with simple proof, and an application, 2013.
[52] Franck lutzeler and Laurent Condat. Distributed projection on the simplex and & ball via admm and gossip. IEEE Signal Processing Letters, 25(1 (5(11):16001165, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the experimental discussion,
we describe the limitations of different algorithms (including ours) on the datasets
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Work is mainly theoretical with an applied flavor and doesn't involve inherent potential soci- etal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are in- cluded in Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URLY? [Yes] Code is in supplemental section, Data available online (not our data include)
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] The algorithm isn't randomized, no random seed or emror plots applicable.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Code for Greedy++ was cited appropriately together with used libraries. All the sources data were also cited.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 'e using/curating? [N/A] No personal data of people was used
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A] Personal data is not used
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Crowdsourcing is not used
(b) Did you describe any potential participant risks, with links Institutional Review
Board (IRB) approvals, applicable? [N/A] Crowdsourcing is not used
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Crowdsourcing is not used
14


Reviews:
[{"review_id": "xo3b5kww74s", "reviewer": "Reviewer_BbXa", "summary": "This paper considered the densest subgraph, densest subgraph decomposition, and supermodular generalizations of these problems. They provided a fast and scalable algorithm that can compute a $\\epsilon$ approximate local decomposition vector in $O(\\sqrt{m\\Delta(G)}/\\epsilon)$ iterations, where $\\Delta(G)$ is the maximum degree of graph G. \nThey also showed that a fractional peeling algorithm can round the fractional solution to get an $\\epsilon\\sqrt{n}$ approximation dense decomposition. ", "questions": "1. Is the improvement in the number of iterations to convergence mainly coming from the connection between the LP dual and the QP shown in Thm 4.3? ", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe densest subgraph and densest subgraph decomposition are classic and important problems. This paper provided a fast and scalable algorithm that reduces the number of iterations to converge to an $\\epsilon$ approximate local decomposition vector. They showed an interesting connection between LP and its dual and QP.  \nThe paper is well-written and easy to follow. \n \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MbWJTEfv3rx", "reviewer": "Reviewer_ZguU", "summary": "The authors of this paper propose an iterative algorithm for densest subgraph detection and decomposition, where the proposed algorithm is guaranteed to converge to an \\epsilon-additive approximate solution and the number of iterations needed is significantly smaller than [3]. Besides the theoretical contributions, the authors conduct extensive experiments on several large-scale real-world graphs to show the practical effectiveness and efficiency of their proposed algorithm.", "questions": "I do not have questions so far.", "limitations": "1. It would be better if the authors could list the approximation guarantee and the time complexity of each existing algorithm in a Table. Then readers can easily compare the theoretical guarantees of this paper and existing studies.  \n2. Although optimization definitely is an important topic in NeurIPS, my understanding is that optimization papers published in NeurIPS majorly focus on optimization problems closely related to machine learning. It seems to me that dense subgraph detection is not directly related to major machine learning problems and it is more extensively studied in the data mining community or the algorithm design community. The weak relevance of this paper to NeurIPS is the major reason that I give a score of 6 for this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The proposed algorithm significantly improves the algorithm in [3].\n2. The results of this paper also apply to the densest decomposition of a supermodular function, which is a more general problem.\n3. The authors also conduct extensive experiments on a number of large-scale graphs. The experimental results demonstrate that the proposed algorithm is not only theoretically sound but also highly effective and efficient in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H-8XzE2dV5u", "reviewer": "Reviewer_wCmG", "summary": "The authors present a new iterative algorithm for Densest subgraph (DSG) and Densest Subgraph Decomposition (DSG-LD) problems. The algorithm takes $O(\\frac{\\sqrt(m \\Delta(G))}{\\epsilon})$ iteration to converge to an $\\epsilon$-additive approximate local decomposition vector, where each iteration takes $O(m)$ time. The paper describe a fractional peeling technique to round the fractional solution for densest subgraph decompositon. The theoretical contribution is supported with experiments by comparing the proposed algorithm with some state of the art algorithms on real world and synthetic datasets.   \n\n", "questions": "No comments for now.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- An efficient, simple, and scalable (epsilon-additive) algorithm for DSG and DSG-LD\n- Fractional peeling technique with strong theoretical and empirical results\n- Connection DSG-LD to decomposition of Supermodular function (DSS)\n- Empirical evaluation of the described algorithms and fractional peeling technique and its comparison to the state of the art algorithms\n- The algorithm being parallelizable \n- The extension of the algorithm for hypergraphs\n- The connection of the LP and QP for DSS\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "A7ABGA3fzW2", "reviewer": "Reviewer_WcJR", "summary": "The authors present a new algorithm for densest subgraph (DSG) and graph decomposition  (DSG-LD) in undirected graphs by leveraging (1) proximal method and (2) fractional peeling inspired by recent work of GREEDY++ which uses information from load vector of the dual LP for a modified iterative peeling. The method is shown theoretically and empirically to be faster than competing methods and the fractional peeling improves quality of the solution compared to direct ordering. ", "questions": "- Lines 309-311 is not new information and may/should be removed? Poor performance of Greedy++ for CloseCliques is a known example which was highlighted in the original [Boob+] paper and later expanded upon in the [Chekuri+, SODA '22] paper.  \n  ", "limitations": "Yes, discussed in Conclusion L347-351 ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Well-explained paper starting from Charikar's dual LP with clear description of connection to supermodular functions and results therein. Parts of this are known (e.g. Danisch et al and Chekuri et al, SODA 2022) but the relevant parts for this paper are clearly presented.\n+ Paper adapts iterative peeling based on dual load vector idea introduced in Boob et al. to the DSG-LD problem.   \n+ Adapts proximal method for DSG and DSG-LD with theoretical results\n+ Detailed empirical evaluation with good comparison highlighting different scenarios.\n+ (Minor) Theoretical connection to the breakthrough result of [Peng et al, 2022] which promises new avenues for development of practical algorithms. \n+ (Minor) Extension of hypergraphs discussed in appendix 6.7 \n\nThe discussion in the main text is good but the proofs could be better illustrated in places (See some suggestions below).\n\n- Section 6.1 (Rado, b-transportation) Suggest adding a figure showing B(V', E') for easier comprehension.\n- Section 6.5 - please refer explicitly from main text in Section 5.4 (lines 266 or 269). Also the order of the appendix section and main text is inverted so suggest changing order of 6.5 and 6.7 \n- Line 260. \"outline the formal details in appendix `6.7`\" \n- Section 6.4 - Proof of 5.6 requires very careful reading. Suggest adding a figure/Venn diagram showing T_t and summation in 619.\n  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept