Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clustering
Authors: Nimita Rajendra Shinde
Vishnu Narayanan
James Saunderson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Semidefinite programming
Max-k-Cut
correlation clustering
Convex optimization
Gaussian sampling

Abstract: Max-k-Cut and correlation clustering are fundamental graph partitioning problems. For a graph $G=(V,E)$ with $n$ vertices, the methods with the best approximation guarantees for Max-k-Cut and the Max-Agree variant of correlation clustering involve solving SDPs with $\mathcal{O}(n^2)$ constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use $\mathcal{O}(n+|E|)$ memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on $|E|$ in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.

Memory-Efficien Approximation Algorithms for MAX-K-CUT and Correlation Clustering
Nimita Shinde
ITTB-Monash Research Academy, Mumbai, India nimitas@iith ac.
Vishnu Narayanan
Industrial Engineering and Operations Research ITT Bombay, Mumbai, India vishnu@iitb. in
James Saunderson
Electrical and Computer Systems Engineering Monash University, Clayton, Australia james. saunderson@monashh edu
Abstract
MAX-K-CUS CUT and correlation clustering are fundamental graph partitioning prob- lems. For graph G (V, E) with n vertices, the methods with the best approxi- mation guarantees for MAX-K-CU KUCUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O constraints and variables. Large- scale instances of SDPs, thus, present memory bottleneck. In this paper, we develop simple polynomial-time Gaussian campiing-based algorithms for these two problems that use On + EE) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving stream, we eliminate the dependence on EE| in the storage complexity at the cost of slightly worse approximation ratio by combining our approach with sparsification.
Introduction
Semidefinite programs (SDPs) arise naturally relaxation of a variety of problems such k-means clustering [5], correlation clustering (6 and MAX-K-CUT [4]. each case, the decision variable is matrix and there
? constraints. While reducing the memory bottleneck for large-scale SDPs has been studied quite extensively in literature
19 36], all these methods use memory that scales linearly with the number of constraints and also depends either the rank of the optimal solution or an approximation parameter. A recent Gaussian-sampling based technique generate near-optimal, near-feasible solution SDPs with smooth objective function involves replacing the decision variable with a zero-mean random vector whose covariance is 27 This method uses most On dl) memory, independent of the rank the optimal solution. However. for SDPs with = 2(n²) constraints, these algorithms still use ((n²)) memory and provide no advantage in storage reduction. In this paper, we show how adapt the Gaussian sampling-bait -aaed approach of (27) to generate an approximate solution with provable approximation guarantees to MAX-I K- K-CU,, and to the MAX-AGREE variant of correlation clustering on a graph G (V, E) with arbitrary edge weights using only O([V] + [E) memory.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 MAX-K-CUT
MAX-K MOx-K-CUUL K-CUT is the problem of partitioning the vertices of a weighted undirected graph G= (V, E) into & distinct parts, such that the total weight of the edges across the parts is maximized. If wi is the edge weight corresponding to edge (i.j) E. then the cut value a partition is CUT = Ei and in different partitions Wij- Consider the standard SDP relaxation of MAX-K-CUT
{
diag(X) = 1 Xi3
max
XC,X) subject to 0
E i i
(k-Cut-SDP)
where C= 8-1 La is a scaled Laplacian. Frieze and Jerrum [14] developed randomized rounding X of (k-Cut-SDP) and produces random partitioning
2
scheme that takes optimal solution satisfying
E|CTT]
Σ ijER
WiyPr(i and j are in different partitions) 2 ax(C, 2 agopt
(1)
where o the optimal k-cut value and ag = min-inn-- min-1/(k- 1)55
1=-1) where p(p) is the
kp(p))
probability that and are in different partitions given that Xij = p. The rounding scheme proposed in [14, referred to as the FJ rounding scheme the rest of the paper, generates i.i.d. samples,
21...... 2% ~ (O, X*) and assigns vertex to part if [2pls 2 [æ]] for all = =1,.... I.....k.
1.2 Correlation clustering
In correlation clustering, given of V vertices together with the information indicating whether pairs of vertices are similar or dissimilar, modeled by the edges in the sets E and E respectively. The MAX-AGREE variant of correlation clustering seeks maximize
C=
Σ Wij 1 [igj in differrntt clusters] +
Σ +
Wiy [á.j in the same cluster]
iJEE
Define G = (V, and G = EV, A natural SDP relaxation of MAX-AGREE 6
diag (X) = 1
max (C,X) subject to X
(MA-SDP)
Xij 2 0 1 + j.
where C LG- + W+ Lo- the Laplacian of the graph G and W+ is the weighted adjacency matrix of the graph G+. Charikar et al. [10] (see also Swamy (30) propose rounding scheme that
takes an optimal solution X3 (MA-SDP) and produces a random clustering C satisfying
[CC] 2 0. (6766(C, X 2 0.766opt
(2)
where opt is the optimal clustering value. The rounding scheme proposed in [10] referred to as the CGW rounding scheme the rest of the paper, generates either Gaussian samples with covariance X and uses them to define 2 clusters.
3 i.i.. zero-mean
1.3 Contributions
We now summarize key contributions of the paper.
Gaussian sampling for MAX-K-CUT. Applying Gaussian sampling-based Frank-Wolf given in (7 directly to (KCCut-SDP) uses n² memory. We, however, show how to extend the approach from 27 to MAX-K-CUT by proposing an alternate SDP relaxation for the problem, and combining it with the FJ rounding scheme to generate a k-cut with nearly the same approximation guarantees as stated in (I) (see Proposition D using On + |ET) memory. key highlight of our approach that while the approximation ratio remains close to the state-of-the-art result in ( reducing it by factor of 5e for E (0, 1/5), the memory used independent of We summarize our result as follows.
log(n/ log(1 E!) -time method outlined in Section 3 uses O(n + |Fl)) memory and generates a k-cut for the graph = (V, F) whose expected value satisfies E 2 ar (1- - 5e)opt where gpto is the optimal k-cut value.
Proposition 1. For 6 E 1/51. our O
12 22.

---

The structure of (MA) is similar to (PP) however, the cost matrix in (M-SDPP) is no longer PSD or diagonally dominant, property that plays an important role in our analysis in the case of MAX-K-CUT. Despite this, we show how to generate a (1 Te
Gaussian sampling for MAX-AGREE
clustering using On + [Fl) memory. Our approach makes a small sacrifice in the approximation ratio (as compared to (2. however, the memory used remains independent of c.
log(n/s) log(1 E1) -time method outlined in Section 4 uses On n + (EI) memory and generates a clustering of graph G = (V, E) whose expected
Proposition 2. For E (0,1/7), our O
2
value satisfies E [[C] 2 0. 0.766(1 - Te)opt&c. where opt is the optimal clustering value.
The constructive proof outline Propositions and is given in Sections and respectively.
Memory reduction using graph sparsification. Propositions 1 and 2 state that the memory used by our approach is On + E.). However, for dense graphs. the memory used by our method becomes (n²²). ). In this setting, to reduce the memory used, we first need to change the way we access the problem instance. We assume that the imput (weighted) graph G arrives edge-by-edge. eliminating the need to store the entire dense graph. We then replace it with 7-spectrally close graph G (see Definition I) with On log n//²), edges. Next, we compute an approximate solution to the new problem defined on the sparse graph using O(n log nog//"" memory. For MAX-K-CUL and MAX-AGREE, we show that this method generates solution with provable approximation guarantees.
1.4 Literature review
We first review key low memory algorithms for linearly constrained SDPs.
Burer and Monteiro [9] proposed nonlinear programming approach which replaces the PSD decision variable with its low-rank factorization in SDPs with d linear constraints. the selected value of rank satisfies r(r + 1) 2 2d and the constraint set is smooth manifold, then any second-orde order critical point of the nonconvex problem a global optimum (8] Another approach, that requires O(d + nr) working memory, is to first determine (approximately) the subspace in which the (low) rank-r solution to an SDP lies and then solve the problem over the (low) r-dimensional subspace (TT.
Alternatively, randomized sketching to low dimensional subspace is often used as low-memory alternative to storing a matrix decision variable 31 Recently, such sketched variables have been used to generate low-rank approximation of a near-optimal solution to SDPs (37. The working memory required to compute a near-optimal solution and generate its rank-r approximation using the algorithmic framework proposed by Yurtsever et al. (37 is Odd + rn/C) for some sketching parameter ( E (o, 1). Gaussian campling-based Frank-Wolfe 27 uses On + memory to generate zero-mean Gaussian samples whose covariance represents near-optimal solution to the SDPs with d linear constraints. This eliminates the dependency on the rank of the near-optimal solution or the accuracy to which its low rank approximation is computed.
However, the two problems considered in this paper have SDP relaxations with n² constraints, for which applying the existing low-memory techniques provide no benefit since the memory requirement of these techniques depends on the number constraints in the problem. These problems have been studied extensively in literature as we see below.
MAX-K-CUT. MAX-K-CUr CUT and its dual MIN-K-PARTITIIN PARTITION have applications in frequency allo- cation 12] and generating lower bound on co-channel interference in cellular networks 7 These
problems have been studied extensively in the literature 20 26 29 The SDP-based rounding scheme given in [14] has also been adapted for similar problems of capacitated MAX-K-CUT [16] and approximate graph coloring (1 In each case, however, the SDP relaxation has 2(n constraints.
Alternative heuristic methods have been proposed in 13 17 23 25), however, these methods generate a feasible cut which only provides a lower bound on the optimal cut value.
Correlation clustering. Charikar et al. [00, Swamy 30 provide 0.766 a..oxaapproiinaation schemes for MAX-AGRER each of which involve solving (MA-SDP). For large-scale applications, data streaming techniques have been studied quite extensively for various clustering problems, such as k-means and k- median B 24.. Ahn et al. [ propose a single-pase pass, O(EE+nc - 0. 0.766(1 (11 - approoximatio algorithm for MAX-AGREE that uses Ó(n/e²) 2) memory. In contrast, to achieve the same approxima-
3

---

tion guarantee, our approach uses O n + min [B) log " memory which equal to O(n + I
for sparse graphs, and is independent of Furthermore, the computational complexity of our
approach has a better dependence on e given by O which is at most O simple to implement.
min E). "logyy 1.25 log(n/c) log((
3.76 e (log n) 1.25 log(n/)) Moreover, our approach is algorithmically 2
1.5 Outline
In Section 2 we review the Gaussian sampling-base based Frank- Wolle method [27] to compute a near- feasible, near-optimal solution to SDPs with linear equality and inequality constraints. In Sections E and 4 respectively, we adapt the Gaussian sampling-basee
approach to give an approximation algorithm for MAX-K-CUT and MAX-AGREE respectively, that use only O(n + |E() memory, proving Propositions | and 2 respectively. In Section [ we show how to combine our methods with streaming spectral sparsification to reduce the memory required to On logn/e n/c²) for dense graphs presented edge-by-edge in a stream. We provide some preliminary computational results for MAX-AGREE in Section 0 and conclude our work and discuss possible future directions in Section All proofs are deferred to the Supplementary material.
Notations. The matrix inner product is denoted by B) Tr (A The vector of diagonal entries of matrix X is diag(X), and diag" (x) is diagonal matrix with the vector z the diagonal. The notations O, O have the usual complexity interpretation and Ô suppresses the dependence on log n. An undirected edge (i,j) in the set E is denoted using (i,j) E E and ij E E interchangably.
2 Gaussian Sampling-based Frank-
Consider smooth, concave function g and define the trace constrained SDP
max XES
g(B())),
(BoundedSDP)
10:0 where S = (Tr(X)= < a. 2 0} and B(-) S" + Rd is linear mapping that projects the variable from mn+1) dimensional space to d-dimensional space. One algorithmic approach to solving (BoundedSDP) to use the Frank- Wolfe algorithm [8] which, in this case, computes an e-optimal solution by taking steps of the form X = (1-7) X tahhhh where % E [0. 1] and unit vectors h,'s arise from upproximately solving a symmetric eigenvalue problem that depends only on B Xx) and g(-). Standard convergence results show that an e-optimal solution is reached after (C /e) iterations, where C2 is an upper bound on the curvature constant of g [8]
Frank-Wold with Gaussian sampling. The Gaussian sampling technique of [27 replaces the valued iterates, X₁, with Gaussian random vectors 2 ((0, X,). The update, at the level of samples, is then žt+1 = VI 2 + /hra Sah where Çe ~ _N(0,1) 1). Note that 21+1 is also zero-mean Gaussian random vector with covariance equal to X,+1 (1 Xx) + nah, Furthermore, to track the change in the objective function value, is sufficient to track the value Vt B(X,), and compute 7t-1 such that 1++11 = (1 11--% 7))u + BxB((cchh hch ). Thus, computing the updates to the decision variable and tracking the objective function value only requires the know mewgedge of 2, (N, X1) and B(X,), which can be updated without explicitly storing Xt, thereby reducing the memory used.
Algorithm 1 27 describes, in detail, Frank algorithm with Gaussian sampling when applied to (BoundedSDP), uses at most O(n + d) memory at each iteration, and after at most (C /4)
iterations, returns sample 2. (O, X.), where X, is an c-optimal solution to [BoundedSDPP
2.1 SDP with linear equality and inequality constraints
Consider an SDP with linear objective function and bounded feasible region,
{
A0(X) (() ( 2 6(2).
max X=
(C, X) subject
(SDP)

---

Algorithm 1: (FWGaussian) Frank- Frank-Wolfe Algorithm with Gaussian Sampling [27]
Input =Input data for (BoundedSiPP). stopping criteria e, accuracy parameter 7/, upper bound
Oy on the curvature constant, probability p for the subproblem LMO
Output:2 :2 ~ NO, X.) and v = ((.,,, where X, is an e-optimal solution of (BoundedSDPP)
Function FWGaussian:
Select initial point Xo E set B(Xo) and sample ~ N(00 Xo)
t 0, 2/(1 2)
(he. + LM (Vg(v:)): (v
5
while (q: - ur Vg(vz)) > do
(2++1, U++1) Updateeaaribble(zz Uz, 9: + + 2t
(he, qr) + LMO (Vg(e+)), EnC.
end
10 return (ze, 0t)
Function LMD (J. 8):
12
Find a unit vector h such that with probability at least 1 - p.
a: = a(hh²" J) 2 maxdes o(d, J)
13
i 2 0 then - B(ahh")
else ạ k 0, +
return (h,
16
Function UpdateVariable(C h,,
17
2 (vI-7)= + V/a hy where ( ~ 1),
(1-
return (2,0)
where (.) : 84 + dR and ()) : S + Rda are linear maps. To use Algorithm the linear constraints penalized using smooth penalty funetion. Let u, (A x) -(tb b(t) for 1 1....; dj and Ui b/20 -A{(2) X) for / = =1== dy. For M > O, the smooth function @ar (-) IRd +dz + R.
dg
oe (u, v) = M
log
M(ss)
e
M M(-us) +
Σ e
M(ss)
satisfies
(3)
1=1
max { [lullse, max uz} I (um(u.)) u) log(2ds (2g + d2)
[lulloc max
+ max
M
We add this penalty term the objective of (SD and define
max X
(C, x) - Bchw (ib b0) ( (x)) Tr(X) saj.
b())
(SDP-LSE)
where a, 8 and M are appropriately chosen parameters. Algorithm [ then generates Gaussian sample with covariance X, which is an e-optimal solution to (SEP-LSE) It is also a near-optimal,
near-feasible solution to (SD)). This result is slight modification of (27 Lemma 3.2] which only provides bounds for SDPs with linear equality constraints.
Lemma 1. For > 0, let (X*, ,1²) be an optimal primal-dual solution to SDP and its dual,
and let X, be e-optimal solution to (SDP-LSE) If B > || + || and M > 0, then
(C) 3log(2d, + d2) - - XC) < (C,X*) + (1100 111 + || (11)
3 log(2d, +
M
M
B
1
8 glog(2d)+ +
max (1LA0(() 6(1) 110, max - (x) 5
M
8 0
1100
5

---

3 Application of Gaussian Sampling to (kCCut-SDP)
In this section, we look at the application of Gaussian sampling to MAX-K-CUL Since Algorithm uses (n²)) memory when solving (k-Cut-SDPP) we define a new SDP relaxation of MAX-K-CUT with the same approximation guarantee, but with ([E)) constraints. We then apply Algorithm to this new relaxation, and show how to round the solution to achieve nearly the same approximation ratio given in Let
kp(p)
min Spp (k () P)
(4)
where p(X;z) is the probability that vertices and in different partitions. If X is feasible for CuCCut-DDP) and CUT is the value of the k-cut generated by the FJ rounding scheme, then
B|CUT]
Wiyp(Xig) ijEE
Σ
(5)
Σ
k
1 win X1y)aR X).
k
(EE,
Frieze and Jerrum [1] derive lower bound on ork, showing that the method gives a nontrivial approximation guarantee. Observe that (5) depends only on the values X;j if (i,j) E E.
A new SDP relaxation of MAX-K-CUT.
We relax the constraints in (kCCut-DDP) to define
diag () = 2 8-
max X
XC
subject to
E,
(k-Cut-Rel)
Since (eeCut-Rel) is a relaxation of Su- its optimal objective function value provides an upper bound on X²), where X* is an optimal solution to (k-Cut-SDP). and hence, on the optimal k-cut value opt Note that the bound in (5) holds true even we replace X by an optimal solution the value of Xú; only if (i,j) E E. Furthermore, when the FJ rounding scheme is applied to the solution of (k-Cut-Rel), it satisfies the approximation guarantee on the expected value of the generated k-cut given in (1. i.e., R[CUT] ox.opt
to (-Cut-Ree) since depends
Using Algorithm 1.
We now have an SDP relaxation of MAX-K-CUO K-CTT that has + [E] constraints. Penalizing the linear constraints in (k-Cut-Re)) using the function (m (3, Algorithm I can now be used generate & samples with covariance X, which is e-optimal solution
X (C,X) B.M (diag(X) 1, - - eτ Xe,) (i.j) E E, Tx() S m] (k-Cut-LSE))
max
Optimality and feasibility results for Rut- Given an e-optimal solution to (-CCttLSSE) we show that it is also near-optimal, near-feasible solution (k ReCut-Rell.
Lemma 2. For 10,1. let Xj be optimal solution k-CCtt Rel and let X, be an eTr(C)-
optimal solution to K-Cut-LSE). For 3 = 6Tr(C) and M = log( log(2n (2
we have
(1-26) (1,2e)(C,XF, < (C) < (1 (C, XHi and
(6)
|diag X.) - 11100 S,, [Rcys 2 k e, (1,))
(7)
Generating a feasible solution to MAX-K-CUT. Since X. might not necessarily be feasible
to (klCut-Rel), we cannot apply the FJ rounding scheme to the samples 2; ~ (0, X.). We, therefore, generate samples 2! ~ (O, X/) using the procedure given in Algorithm 2 such that X is a feasible solution to Re-Cut-Rel) and (C, X') is close to (C, (.)
We now apply the FJ rounding scheme to .f....,.2. of given in Lemmal 3
Lemma 3. For G = (V, E), let &pt be the optimal k-cut value and let X be an optimal solution to Rel). For (0, t). let X, - 0 satisfy (6) and ( Let of....,,? be random vectors generated by Algorithm with input Zi,..., 2h ~ NN0 X.) and let CUT denote the value of a k-cut generated by applying the FJ rounding scheme to of ... 2 For defined by (4) we have
ap(1 - 4e)opt Lau(1 4c) XR) E|CUT] S opt
(8)

---

Algorithm 2: Generate Gaussian samples with covariance feasible to (k-Cut-Rel)
Input :Sample 2; (O, Xx) for i 1,..., , and diag(X.)
O (0, X for i .,..., with x feasible (uCCttRell
Function GeneratexSamples::
2
for i ,,..., k do
Set err max (0, (aX() - -1/(k (Rebs) Set 2, + vert L, where y (0,
Generate Ç N (0, diag" 21
ding( (
max (XX, +em
Set 2
+
mmxx(diag(X.)) teir
end
return
Computational complexity of Algorithm I when applied to (k-Cut-LSE).. Finally, in Lemma 4 we provide the computational complexity of the method proposed in this section, which concludes the proof of Proposition 0
Lemma 4. When the method proposed in this section (Section with T(nee] and T(n, c)
144 11ilog(2n++ E )n" is used to generate an approximate k-cut MAX-K-CUT, the generated cut satisfies E CUT 2 au
5e)opt (1)) and runs in O | log(n/e) log((E)) time.
4 Application of Gaussian Sampling to (MA-SDP)
now look at the application of our Gaussian sampling based method to MAX-AGREE Algorithm| T uses Onn²) memory generate samples whose covariance is c-optimal solution to (MA-SDP). However, with the similar observation as in the case of MAX-K-CUTY we note that for any X feasible to (DP), the proof of the inequality E[C] 2 0.766 (C, X), given in [10) Theorem 3], requires X;J 2 0 only (1.3) E E. We therefore, write a new relaxation of (DP..
X = ViE (1.....
max (C,X) = (W+ + LG-,X) subject to X
(MA-Rel)
X,j 20 0 (1.5) E E,icj,
with only + [E] constraints. The bound E[C] > O,766 X*) 0.766optec on the expected value of the clustering holds even if the clustering is generated by applying the CGW rounding scheme optimal solution X of (MA-Rel). To use Algorithm I penalize the constraints in (MlR and define
max {C, X) - (diag(iaa(X)) (X) - 11, - Xe,) (1,5) E (,T((X) sn) X=0
(MA-LSE)
Optimality and feasibility results for Rel
Algorithm is now used to generate
(0, X.). where X, is e-optimal solution to (SA-LSE.
We show in Lemma 5 that X, is
also a near-optimal, near-feasible solution to Re-Rel).
Lemma 5. For A + w. (0. 1). let X be an optimal solution to MA- Rel
and X, be an eA-optimal solution (SA...E). Setting 4A and M log(2n+ El)
we have
- 4c, < (C, < (1 4c) and
(9)
|iaag X.) 1| Se, [Xcc 2 -c, c, (i,j) R,icj.
(10)
Generating an approximate clustering. The CGW rounding scheme can only be applied if have a feasible solution to (MA-Rel). We, therefore, use a modified version of Algorithm 2 with Step
3 replaced by err max (0, max - [ ] and input 21, #2, 23 (0, X.). to generate zero-mean Gaussian samples whose covariance feasible solution to (A-Rell. Finally, we apply the CGW rounding scheme to the output of the modified of Algorithm
7

---

Lemma 6. Let X be an optimal solution to MA-Rell. For E (0.1/6), let X. 2 0 satisfy (9)
and (10). and let zf z/2 z/g be random vectors generated by Algorithm with input 21, 22, 23
NO X.) ). Let optcc denote the optimal clustering value for the graph G (V, E) and let C denote
the value of the clustering generated from the random vectors of 22, 23 using the CGW rounding
24
scheme. Then
E|C] 2 0.766(1 - -6e) 2 0.766(1 - -6 oc)
(11)
Computational complexity of Algorithm [ when applied to (MA-LSE).
Lemma 7. When the method proposed in this section (Section with T(m and T(n, e) = 61 1og(2n= [1))) used generate an approximate clustering, the value of the clustering satisfies B[C] 2 0.766(1 - 7c) and runs O
2 E log(n/c) log((E]) time.
This completes the proof of Proposition 2
Sparsifying the Laplacian Cost Matrix
As seen in Sections and 4 the memory requirement for generating and representing an c-optimal solution to (k-Cut-LSE) and (MA-LSE) is bounded by Onn + |E)). However, if the input graph G is dense, the cost matrix will be dense and the number of inequality constraints will still be high. In this section, we consider the situation in which the dense weighted graph arrives in a stream, and we first build sparse approximation with similar spectral properties. We refer this additional step as sparsifying the cost.
Definition (r-spectral closeness). Two graphs G and G defined on the same set of verfices are said to be r-spectrally close if. for any IK' and T (0, 1).
(1-7)x" Lox S xxx Lax S (1+T)z² LGx.
(12)
Spectral graph sparsification has been studied quite extensively (see, e.g., 2 15 28 Kyng et al.
22 propose a O(E)) log" -tmm framework to replace a dense graph = (V, E) by sparser graph G = (V, E) such that [E] ~ O(n log n and G satisfies 12 with probability 1 poly(n) Their algorithm assumes that the edges of the graph arrive one at a time, so that the total memory requirement is On log n/7²) rather than El.. Furthermore, a sparse cost matrix decreases the computation time of the subproblem in Algorithm I since it involves matrix-ved vector multplicatioon with the gradient of the cost.
MAX-K-CUT with sparsification. Let Ō be sparse graph with Onn n/7?) edges that is
spectrally close to the input graph G. By applying the method outlined in Section 3 we can generate a k-cut for the graph & (using O(n (ogn//2)) n//²) memory) whose expected value satisfies the bound (8) Note that, this generated cut is also k-cut for the original graph G with provable approximation guarantee as shown in Lemma 8
Lemma 8. For C,T E (0,1/5) let X. be near-feasible, near-optimal solution to (k-Cut-Rel
defined on the graph G that satisfies (6) and 7 Let CUT denote the value of the k-cut generated by applying Algorithm followed by the FJ rounding scheme Xe. Then the generated cut satisfies
(r 4E - T S E|CuT] S opt where g is the value of the optimal k-cut for the original graph G.
MAX-AGREE with sparsification. The number of edges |E+ and |F-| in graphs G+ and G- respectively determine the working memory of Algorithm] For dense input graphs G and G=, we sparsify them to generate graphs Ö+ and G- with at most On n//²) edges and define
max f(x) (L8- W X)= Baas (diag(X) 1, -le X (El...E))) XES
(MA-Sparse)
where = (X Tx(X S n, X 2 0}. La- is the Laplacian of the graph Ō-, W+ is matrix with nonnegative entries denoting the weight of each edge (i.j) Et, and E É-UÊ-
8

---

Algorithm then generates an e(Tr(LG-) + EnjeE=+ w )opttmal solution. Xx to MA-Sparse) using (n log n//²) memory. We can now use the method given in Section 4 to generate clustering of graph G whose expected value, E[C], satisfies (II). The following lemma shows that C also represents a clustering for the original graph G with provable guarantees.
Lemma 9. For E,T E 10,1/9), let X be near-feasible, near-optimal solution (A-Sparse)
defined on the graph G that satisfies (9) and (10). Let C denote the value of the clustering generated by applying Algorithm followed by the CGW rounding scheme to X.. Then, [E[]] satisfies
0.766(1 6c -r) )opt S E[C optc.
where opt is the value of the optimal clustering of the original graph G.
We summarize our results in the following lemma whose proof is given in the Supplementary material. Lemma 10. Assume that the edges of the input graph G = (V, E) arrive one at time in a stream. The procedure given in this section uses at most Oonlog//7) memory and in
n 1gjt log(n/c) log(lEl)) -time, generates approximate solutions to MAX-K-CUT and MAX-
O
AGREE that satisfy the bounds [E[CT]] 2 og.(1 55 -)opt and ECC] 0.766(1 7e -37) 7² PoptEc respectively.
6 Computational Results
We now discuss the results of preliminary computations to cluster the vertices of a graph G using the approach outlined in Section[4 The aim of numerical experiments was verify that the bounds given in Lemma 6 were satisfied when we used the procedure outlined in Section 4 to generate a clustering for each input graph. We used the graphs from GSET dataset [35] which is a collection of randomly generated graphs. Note that the aim of correlation clustering is to generate a clustering of vertices for graphs where each edge has a label indicating 'similarity" or 'dissimilarity' of the vertices connected to that edge. We, therefore, first converted the undirected, unweighted graphs from the GSET dataset (35 into the instances of graphs with labelled edges using an adaptation of the approach used in [32 33). This modified approach generated a label and weight for each edge (i, E E indicating the amount of 'similarity" or 'dissimilarity" between vertices i and j.
Generating input graphs for MAX-AGREE. In the process of label generation, we first computed the Jaccard coefficient Jiy (i) n N UN))), where N (i) is the set of neighbours of for each edge j) E. Next we computed the quantity Sij = log((? (1((111 - Jij + 8)/ Ji (0:k--6) 5)) with 8 0.05 for each edge (i E E, which is measure of the amount of "similarity or 'dissimilarity.
Finally, the edge (i.j) was labelled as 'dissimilar' if Sij < 0 with wi = SSg and labelled as 'similar' with wij = Sij otherwise.
Experimental Setup. We set the input parameters to 0.05, A = Tr(Lo ) + Eijer= w.t
= 4A, M 4 [[][ Using Algorithm I MA-LSE was solved to eA-optimality and, we computed feasible samples using Algorithm Finally, we generated two Gaussian samples and created at most four clusters by applying the 0.75-rounding scheme proposed by Swamy 130 Theorem 2. I.. for simplicity. The computations were performed using MATLAB R2021a on a machine with 8GB RAM. We noted the peak memory used by the algorithm using the profiler command in MATLAB. The code and the GSET dataset are included in the Supplementary material.
The computational result for some randomly selected instances from the dataset is given in Table We have provided the result for the rest of the graphs from GSET in the Supplementary material. First, we observed that for each input graph, the number of iterations of LMO for <A rA-convergence satisfied the bound given in Proposition and the infeasibility of the covariance X, of the generated samples was less than satisfying (1O). We generated 10 pairs of i.i.d. zero-mean rrro Gaussian samples with covariance X., and each in turn was used to generate a clustering for the input graph using the 0.75-rounding scheme proposed by Swamy [30]. Amongst the 10 clusterings generated for each graph, we picked the clustering with largest value denoted by Crest- Note that, Crsa 2 E[C] > 0.75(1 (C) X&) 0.75
I+4c 1-6e (C, Xe), where the last inequality follows from

---

combining with 97. Since we were able to generate the values, Ceest and (C, (C,X.), we noted that the weaker bound Crea/ (C, Xx) AR 0.75(1 6c) 4c) was satisfied by every input graph when c = 0.05.
Table 1 also shows the memory used by our method. Consider the dataset GI, for which the memory used by our method was 1526.35kB 9.8 x + |E+ + E 8, where a factor of 8 denotes that MATLAB requires 8 bytes store real number. Similarly, we observed that our method used at most x ([V] + | + I) x memory to generate clusters for other instances from GSET, where 33 for every instance of the imput graph, showing that the memory used was linear in the size of the input graph.
Table 1: Result of generating clustering of graphs from GSET using the method outlined in
Section 4 We have, infeas max [|]diag( (X) o max (0, (x AR Caes/ X.) and
0.75(1
6e) (1
4e) = 0.4375 for e = 0.05.
#
Memory
Dataset
[V]
|
|
Iterations (x10%)
infeas
(C, Xx)
Ceest
required
(in kB)
GI
800
2453
16627
669.46
10
849.48
643
0.757
1526.35
G11
800
817
783
397.2
6 x 10
3000.3
2080
0.693
448.26
G14
800
3861
797
330.02
8 10-4
542.55
469.7 .77
0.866
423.45
G22
2000
11.5
1 19849
725.66
10-3
1792.9
1371.1
0.764
1655.09
G32
2000
2011
1989
571.42
9 10 10-4
7370
4488
0.609
1124
G43
1000
248
9704
501.31
10-3 3
803.8
616.05
0.766
654.46
G48
3000
0
6000
9806.22
0,004
599.64
461.38
0.769
736.09
G51
1000
4734
1 144
1038.99
0,001
676.21
446.29
0.66
517.09
G55
5000
66
12432
2707.07
0.002
1244.2
901.7 74
0.724
/281.03
G57
5000
4981
5019
574.5
0.005
18195
10292
0.565
812.78
7
Discussion
In this paper, we proposed Gaussian sampling-based optimization algorithm to generate approx- imate solutions MAX-K-CUT, and the MAX-AGREE variant of correlation clustering using
O On + min [E] log memory. The approximation guarantees given in [10
14
30
for these
problems are based solving SDP relaxations of these problems that have n² constraints. The key observation that led to the low-memory method proposed this paper was that the approximation guarantees from literature are preserved for both problems even if we solve their weaker SDP relax- ations with only (n + |EI) constraints. We showed that for MAX-K KEcK--CUur CUT, and the MAX-AGREE variant of correlation clustering,
approach nearly preserves the quality of the solution as given in [0 We also implemented the method outlined in Section to generate approximate clustcring for random graphs with provable guarantees. The numerical experiments showed that while the method was simple to implement, was slow in practice. However, there is scope for improving the convergence rate of method that it can potentially be applied to the large-scale instances of various real-life applications of clustering.
Extending the low-memory method solve problems with triangle inequalities. The known nontrivial approximation guarantees for sparsest cut problem involve solving an SDP relaxation that has n triangle inequalities 4 would be interesting to see whether it is possible simplify these SDPs in such way that they can be combined nicely with memory efficient algorithms, and still maintain good approximation guarantees.
Disclosure of Funding
Funding in direct support of this work: scholarship for Nimita Shinde was provided by IITB-Monash Research Academy. Additionally, Dr. James Saunderson was supported in part by an Australian Research Council Discovery Early Career Researcher Award (project number DF210101056) funded by the Australian Government.
10

---

References
[1] K. Ahn, G. Cormode, S. Guha, A. McGregor, and A. Wirth. Correlation clustering in data streams. In International Conference on Machine Learning, pages 2237-2246. PMLR, 2015.
[2] K. J. Ahn and S. Guha. Graph sparsification in the semi-streaming model. In International Colloquium on Automata, Languages, and Programmiing pages 328 338. Springer, 2009.
[3] N. Ailon, R. Jaiswal, and C. Monteleoni. Streaming k-means approximation, Proceddings of the Twenty-Third Annual Conference on Neural Information Processing Systems, volume 4, page 2, 2009.
[4] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1-33 37, 2009.
[5] P. Awasthi, S. Bandcira, M. Charikar, Krishnaswamy, S. Villar, and R. Ward. Relax, no need to round: Integrality of clustering formulations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 191-200, 2015.
[6] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3) ():133)89-111 113, 2004.
[7] R. Bordörfer, A. Eisenblätter, M. Grötschel, and A. Martin. Frequency assignment in cellular phone networks. Amnals of Operations Research, 76:73-93, 1998.
[8] N. Boumal, Voroninski, and Bandeira. The non-coavex semidefinite programs. Advances Neural Information Processing Systems, pages 2757 2765, 2016.
approach works on smooth
191 S. Burer and R. D. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 35(2):3293357, 2003.
[10] M. Charikar, V. Guruswani, and A. Wirth, Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):360-33 383, 2005.
[11] L. Ding, A. Yurtsever, V. Cevher, A. Tropp, and M. Udell. An optimal-storage approach to semidefinite programming using approximate complementarity. arXiv preprint arXiv:1902.03377, 2019.
a
[12] A. Eisenblätter. M. Grötschel, and A. Koster. Frequency planning and ramifications of coloring. Discus- siones Mathematicae Graph Theory, 22(1):51-88) 2002.
[13] T. A. Feo and M. G. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109-133, 1995.
[14] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX-K-CUT and max bisection. Algorithmica, 18(1)667-88 81, 1997.
[15] W.-S. Fung, R. Hariharan, J. Harvey, and D. Panigrahi. A general framework for graph sparsification. SIAM Journal on Scientific Computing, (((4):11961122)) 2019.
[16] D. R. Gaur, Krishnamurti, and R. Kohli. The capacitated MAX-K-CUT problem. Mathmatical Programming, 115(1))65 72, 2008
[17] B. Ghaddar, M. F. Anjos, and F. Liers. A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Annals of Operations Research, 188(1): (88(1):155-174 2011.
[18] M. Jaggi. Revisiting Frank-Wolfes Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pages 427 027-435,22 2013.
[19] Journée, F. Bach, P.-A, Absil, and R. Sepulchre. Low-rank optimization on the cone of positive semidefinite matrices. SIAM Journal on Optimization, 20(5):2377-2551, 2010.
[20] V. Kann. S. Khanna. J. Lagergren, and A. Panconesi. On the Hardness of Apprexxmaaiing MAX-K-CUT and Its Dual, Citeseer, 1995.
[21] D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring hy semidefinite programming. Journal of the ACM (JACM), 45(2):246-265, 1998.
[22] R. Kyng, J. Pachocki, R. Peng. and S. Sachdeva. A framework for analyzing resparsification algorithms. In Proceedings of the TightyEighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2032-2043. SIAM, 2017.
[23] F. Ma and J.K. Hao. A multiple search operator heuristic for the MAX-K-CUT problem. Annals of Operations Research, 248(1 2):366 403, 2017.
[24] R. M. McCutchen and Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity. In Approximation, Randomization and Combinatorial Optimization. Algorithmm and Techniques, pages 165-178. Springer, 2008.

---

[25] N. Mladenovié and P. Hansen. Variable neighborhood search. Computers & Operations Research, 24(11); 1): 1097-1100, 1997.
[26] A. Newman. Complex semidefinite programming and MAX-K-CUri arXiv preprint urXiv:1812.1077 2018.
[27] N. Shinde, V. Narayanan, and J. Saunderson. Memory-efficiere structured convex optimization via extreme point sampling. SIAM Journal on Mathematics of Data Science, (3):787-814, 2021.
[28] D. A. Spielman and Teng. Spectral sparsification of graphs. SIAM Journal on Scientific Computing. 40 1-981-10255 201
[29] A. P. Subramanian, H. Gupta, S. R. Das, and J. Cao. Minimum interference channel assignment in multiradio wireless mesh networks. IEEE Trunsactions on Mobile Computing, (112):449-14777 2008
[30] Swamy. Correlation clustering: maximizing agreements semidefinite programming. SIAM Symposium on Discrete Algorithms,, volume pages 526-527. Citeseer, 2004.
[31] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher. Streaming low-rank matrix approximation with an application to scientific simulation. SIAM Journal on Scientific Computing, 41(44::2430-A22 2019.
[32] Veldt, Gleich, A. Wirth, and Saunderson. Metric-constrained optimization for graph clustering algorithms. SIAM Journal Mathematics of Data Science, 1(2):333 355, 2019.
[33] Y. Wang, L. Xu, Y. Chen, and H. Wang. A scalable approach for general correlation clustering. In International Conference on Advanced Data Mining and Applications, pages 13-24. Springer, 2013.
[34] D. Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends@ Theoretical Computer Science, 10(1 2):1-157, 2014.
[35] Y. Ye. GSET random graphs. https://www http:://wwwwwse.e.eem wfw. wtt.cch//eeeerrd///peeesessssssa 2003. [accessed April-2021
[36] A. Yurtsever, M. Udell, J. A. Tropp, and Cevher. Sketchy decisions: Convex low-rank matrix optimization with optimal storage. Artificial Intelligence and Statistics, pages 1188 1196, 2017.
[37] A. Yurtsever, J. A. Tropp, O. Fercoq, M. Udell, and V. Cevher. Scalable semidefinite programming. SIAM Journal on Mathematics of Data Science, 3(1):171-200 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The abstract provides an overview of the results. See Section 1.3 (Contributions) for the summary of the results.
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No] Our method, while memory-efficien and simple to implement, is not yet a practical algorithm, owing to slow convergence. While clustering algorithms can potentially be misused, our contributions do not seem to have direct impact on large-scale applications.
(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] The assump- tions are provided in the statements of the results.
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs of all the results provided in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and data are included in the Supplementary material. We will include the de-anonymized URL to the github repository containing the code and the data the camera-ready version of the accepted paper.
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All parameters choices for our experiments are explicitly given and they are chosen according to theory in the paper.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] We have reported the best solution value and explicitly stated the results with reference to the best value as this appropriate from the context.
(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] We have used MATLAB 202 lb and performed the experiments on a local machine with 8GB RAM and cores. We have also included this information in Section 6.
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] We have used graphs from GSET dataset (35) for numerical experiments. We have added the citation accordingly Section 6 (Computational results).
(b) Did you mention the license of the assets? [No] The license situation of the assets is not clear. However, the dataset has been widely used for over 18 years, and is posted publicly in multiple places.
(c) Did you include any new assets either in the supplemental material or URL? [Yes] We have added link (URL) to the code which we created and used to run the experiment.
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A] GSET comprises of collection of randomly generated graphs, and does not contain personal information/data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] GSET comprises of randomly generated graphs and as such, is not deemed to have personal data in any way.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wUrHdRLfpEH", "reviewer": "Reviewer_6muF", "summary": "The methods with best approximation guarantees for max-K-cut and the max-agree variant  of correlation clustering involve solving semidefinte programs (SDPs) with $n^2$ variables and $n^2$ constraints, which use  a lot of memory. \tThis paper proposes a modified polynomial-time Gaussian sampling-based algorithms from [27] that reduce the memory from $\\mathcal{O}(n^2)$ to $\\mathcal{O}(n + |E|)$ and nearly achieve the best approximation guarantees. The paper further extend their approach to the dense graphs cases by combining it with graph sparsification and the memory is reduced to $\\mathcal{O}(nlog n / \\tau^2)$.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nOriginality & presentation:  \n\n\n- The idea of the paper is based on the observation that the approximation guarantee depends only on $X_{i,j}, (i, j) \\in E$. Therefore, they define new SDP relaxations of Max-K-Cut and Max-Agree with $n+|E|$ constraints. The Frank-Wolfe algorithm with Gaussian sampling is then used to obtain the $\\epsilon$-optimal solutions of these two relaxations. The algorithms only use $\\mathcal{O}(n + |E|)$ memory since the relaxations have only $n+|E|$ constraints. For dense graphs, the memory will still be high and the paper tackles this issue by combining their approach with spectral graph sparsification and the memory is reudced to $\\mathcal{O}(nlog n / \\tau^2)$. The proposed approach nearly obtains the same quality solutions as previous work but uses less memory. \n\n- The idea of the paper is intriguing and the reduction of the memory used by the algorithms is impressive. However, the computational complexity of the presented approach is in $\\mathcal{O}(n^2|E|log(2n + |E|)/\\epsilon^2)$, which makes it hard to be used in large-scale instances. \n\n\n- One of techniques of the paper,  Gaussian sampling-based Frank-Wolfe, was introdudced in [27]. Can you explain the major differences or overlaps compared to [27]?  \n\n- What is the convergence  rate of the algorithm for MA-SDPs in Section 4?\n\n\nOverall, I like the theoretical contribution of the paper. \n\nThe paper is well structured and main techniques are clearly presented. \n\n\n\nExperiments:  \n\n\nIn the experiments, the paper presents only the computational results of their own algorithm. There is not clear that it is able to outperform the previous baselines in practical. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "uYIsBQvtTpN", "reviewer": "Reviewer_kFS9", "summary": "This paper studies several methods for speeding up / reducing memory of computing max k-way cuts, via methods such as sampling and sparsification. They rigorously prove that the semi-definite program can be approximated to an error of \\epsilon in about m \\epsilon^{-2} space, and furthermore, the quality of approximations are preserved with the use of spectral graph sparsifiers.\n\nA Matlab implemention of this method is then tested on a multitude of clustering instances, showing that the memory usage is quite low, but at a cost of a fairly large (between 15~40%) relative error.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I believe the bounds shown in this paper are quite useful for (approximately) solving semi-definite programs, especially in settings with limited memory. On the other hand, I feel the style of algorithm, and tools used, place this result one step away from being truly practical. My understanding is that clustering / inference on graphs tend to use more features of the datasets, instead of just the underlying graph structure. While I believe many of the ideas used here can be incorporated into more sophisticated semidefinite programming based algorithms, I feel the direct application to k-cut will likely be of interest primarily to those working on continuous optimization and streaming algorithms.\n\nI also thank the authors for their responses that agree about this result being an intermediate result. My overall score is unchanged because I believe there are enough ideas in this result for it to be of interest to many.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I'm most concerned about the experiments: the scale of the data (5000 vertices, 20000 edges) is still at a scale where the entire semidefinite program fits into 100MB or so of memory, and can be solved as such. On the other hand, iterative / first order methods for solving semidefinite programs tend to converge significantly slower. So my interpretation of the data is that it's getting a 100 fold memory reduction at the cost of a 10^3~10^4 fold increase in runtime (10^6 iterations, vs the rougly factor 100 overhead of matrix inversion vs. multiplication), as well as a fairly large loss in accuracy. So I view the experiments mostly demonstrate that these methods can feasibly be implemented, instead of showing that they have clear gains over existing optimization tools.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "YQ1wmjbwLqV", "reviewer": "Reviewer_qqhg", "summary": "The authors study two graph partitioning problems MAX-K-CUT and correlation clustering (MAX-AGREE) under a limited memory setting. The authors propose polytime sampling-based algorithms for these two problems that require $O(n + |E|)$ memory while preserving the best approximation guarantees ($n$ is the number of vertices and $E$ is the edge set). In addition, for the case of dense graphs the authors eliminate the quadratic memory requirements by utilizing spectral sparsification results in the streaming model of computation.\n\n", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "* In my opinion, the manuscript could be a better fit to an algorithmic / graph theory related conference rather than NeurIPS. Graph sparsification and approximation algorithms for graph related problems have mostly appeared in such conferences (SODA,ICALP, etc).  \n* What is the contribution of the current paper following [27]? Please elaborate on the contributions section how you \"...modify their approach...\" in L49-L50 at this point. This is your key contribution and should be clearly explained in this level of abstraction.\n* Memory reduction using graph sparsification is a direct outcome of the spectral sparsification result.\n* Correlation clustering / Literature Review: Is the result of Ahn et al [1] superior compared to your proposed algorithm? Memory requirements in [1] is $\\tilde{O}(n/\\epsilon^2)$, right? Moreover, [1] is a single pass algorithm. Please clarify.\n* Experimental results are based on relatively small graphs 1-2MBs memory footprint. Here, the reader would expect instances of large graphs, at least sparse once to see the benefits of the proposed methods.\n* Notation: Please do not hide logarithmic terms on n using $\\tilde{O}$. Such notations can be used to hide $loglogn$ terms, etc.\n\n\n*******************\nMinor comments\n*******************\n\n\nAbstract:\n* L8: E is undefined (edge set).\n\n\nIntroduction\n* L33: \"Equation (3)\" is a forward reference (next 2 pages). Hard for the reader to follow the flow.\n* L35: \"for $l\\in {1, \\dots , k}$\" . Is this \"for all\" or \"for every\"?\n* L39: Equation on second \\sum should read \"ij\\inE^{+}\", not E^{-}.\n* L40: Give reference to the SDP relaxation of MAX-AGREE or state if it is folklore.\n* L45-46: \"...uses them to define up to $8$ clusters\". The 3 Gaussian samples here and 8 clusters seem arbitrary here. Please elaborate or add a sentence commenting about these numbers.\n* L48: It would be great to add a sentence in the \"1.3 Contribution Section\". Enumerating the contributions directly is quite dense.\n* L50: \"nearly the same\". Please be precise if possible here.\n* L53: \"$1-4\\epsilon$\". $\\epsilon$ is not defined here, only on the proposition below.\n* L69: \"arrives edge-by-edge\": Is the streaming model adversary or not? I am not an expert but it is good to make it clear to the reader.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they did.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "H6BmHxAnOZm", "reviewer": "Reviewer_xu1n", "summary": "The paper presents an algorithm for approximating MAX-$k$-CUT to within the SDP bound that avoids the $\\Omega(n^2)$ memory requirement of the SDP formulation. The improvement is to $O(n+m)$ space. Here, $n$ is the number of nodes of the input graph and $m$ is the number of edges. Coupled with known sparsification techniques, the algorithm runs using $O(n\\log n)$ space (hiding a factor that depends on how close one gets to the SDP guarantee. The algorithm uses Frank-Wolfe with Gaussian sampling on a relaxation that replaces the constraints by some regularization. Similar results apply to correlation clustering, though such bounds were known previously.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "It's a nice result which uses mostly previously known techniques, but the application requires some effort. The problems are justified in the machine learning context as clustering problems, and the practical motivation for reducing substantially the memory requirements is indeed meaningful. There are some empirical results on randomly generated graphs. The paper has some annoying typos, for instance in line 40 and the preceding displayed equation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission was universally appreciated for its application to SDP-based methods for clustering but with lower memory requirements. Though, there were some suggestions that the paper might be more of a natural fit at a TCS conference instead of NeurIPS.
Decision: Accept (Poster)