Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering
Year: 2021

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 O(n) constraints and variables. Largescale 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 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.

text: 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 O(n2) constraints and variables. Largescale 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 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.

heading: 1 Introduction
text: Semidefinite programs (SDPs) arise naturally as a relaxation of a variety of problems such as k-means clustering [5], correlation clustering [6] and MAX-K-CUT [14]. In each case, the decision variable is an n × n matrix and there are d = Ω(n2) constraints. While reducing the memory bottleneck for large-scale SDPs has been studied quite extensively in literature [9, 11, 19, 36], all these methods use memory that scales linearly with the number of constraints and also depends on either the rank of the optimal solution or an approximation parameter. A recent Gaussian-sampling based technique to generate a near-optimal, near-feasible solution to SDPs with smooth objective function involves replacing the decision variable X with a zero-mean random vector whose covariance is X [27]. This method uses at most O(n+ d) memory, independent of the rank of the optimal solution. However, for SDPs with d = Ω(n2) constraints, these algorithms still use Ω(n2) memory and provide no advantage in storage reduction. In this paper, we show how to adapt the Gaussian sampling-based approach of [27] to generate an approximate solution with provable approximation guarantees to MAX-K-CUT, 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 (NeurIPS 2021).

heading: 1.1 MAX-K-CUT
text: MAX-K-CUT is the problem of partitioning the vertices of a weighted undirected graph G = (V,E) into k distinct parts, such that the total weight of the edges across the parts is maximized. If wij is the edge weight corresponding to edge (i, j) ∈ E, then the cut value of a partition is CUT = ∑ i and j are in different partitions wij . Consider the standard SDP relaxation of MAX-K-CUT
max X 0
〈C,X〉 subject to {
diag(X) = 1 Xij ≥ − 1k−1 i 6= j,
(k-Cut-SDP)
where C = k−12k LG is a scaled Laplacian. Frieze and Jerrum [14] developed a randomized rounding scheme that takes an optimal solution X? of (k-Cut-SDP) and produces a random partitioning satisfying
E[CUT] = ∑
ij∈E,i<j wijPr(i and j are in different partitions) ≥ αk〈C,X?〉 ≥ αkoptGk , (1)
where optGk is the optimal k-cut value and αk = min−1/(k−1)≤ρ≤1 kp(ρ)
(k−1)(1−ρ) , where p(ρ) is the probability that i and j are in different partitions given that Xij = ρ. The rounding scheme proposed in [14], referred to as the FJ rounding scheme in the rest of the paper, generates k i.i.d. samples, z1, . . . , zk ∼ N (0, X?) and assigns vertex i to part p, if [zp]i ≥ [zl]i for all l = 1, . . . , k.

heading: 1.2 Correlation clustering
text: In correlation clustering, we are given a set 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 to maximize
C = ∑ ij∈E− w−ij1[i,j in different clusters] + ∑ ij∈E+ w+ij1[i,j in the same cluster].
Define G+ = (V,E+) and G− = (V,E−). A natural SDP relaxation of MAX-AGREE [6] is
max X 0
〈C,X〉 subject to {
diag(X) = 1 Xij ≥ 0 i 6= j,
(MA-SDP)
where C = LG− +W+, LG− is 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 a rounding scheme that takes an optimal solution X?G of (MA-SDP) and produces a random clustering C satisfying
E[C] ≥ 0.766〈C,X?G〉 ≥ 0.766optGCC , (2)
where optGCC is the optimal clustering value. The rounding scheme proposed in [10], referred to as the CGW rounding scheme in the rest of the paper, generates either k = 2 or k = 3 i.i.d. zero-mean Gaussian samples with covariance X?G and uses them to define 2 k clusters.

heading: 1.3 Contributions
text: We now summarize key contributions of the paper.
Gaussian sampling for MAX-K-CUT. Applying Gaussian sampling-based Frank-Wolfe given in [27] directly to (k-Cut-SDP) uses n2 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 (1) (see Proposition 1) using O(n+ |E|) memory. A key highlight of our approach is that while the approximation ratio remains close to the state-of-the-art result in (1), reducing it by a factor of 1− 5 for ∈ (0, 1/5), the memory used is independent of . We summarize our result as follows.
Proposition 1. For ∈ (0, 1/5), our O ( n2.5|E|1.25 2.5 log(n/ ) log(|E|) ) -time method outlined in
Section 3 uses O(n+ |E|) memory and generates a k-cut for the graph G = (V,E) whose expected value satisfies E[CUT] ≥ αk(1− 5 )optGk , where optGk is the optimal k-cut value.
Gaussian sampling for MAX-AGREE. The structure of (MA-SDP) is similar to (k-Cut-SDP), however, the cost matrix in (MA-SDP) is no longer PSD or diagonally dominant, a 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− 7 )0.766-optimal clustering using O(n+ |E|) memory. Our approach makes a small sacrifice in the approximation ratio (as compared to (2)), however, the memory used remains independent of .
Proposition 2. For ∈ (0, 1/7), our O ( n2.5|E|1.25 2.5 log(n/ ) log(|E|) ) -time method outlined in
Section 4 uses O(n+ |E|) memory and generates a clustering of graph G = (V,E) whose expected value satisfies E[C] ≥ 0.766(1− 7 )optGCC , where optGCC is the optimal clustering value.
The constructive proof outline of Propositions 1 and 2 is given in Sections 3 and 4 respectively.
Memory reduction using graph sparsification. Propositions 1 and 2 state that the memory used by our approach is O(n + |E|). However, for dense graphs, the memory used by our method becomes Θ(n2). In this setting, to reduce the memory used, we first need to change the way we access the problem instance. We assume that the input (weighted) graph G arrives edge-by-edge, eliminating the need to store the entire dense graph. We then replace it with a τ -spectrally close graph G̃ (see Definition 1) with O(n log n/τ2) edges. Next, we compute an approximate solution to the new problem defined on the sparse graph using O(n log n/τ2) memory. For MAX-K-CUT and MAX-AGREE, we show that this method generates a solution with provable approximation guarantees.

heading: 1.4 Literature review
text: We first review key low memory algorithms for linearly constrained SDPs.
Burer and Monteiro [9] proposed a nonlinear programming approach which replaces the PSD decision variable with its low-rank factorization in SDPs with d linear constraints. If the selected value of rank r satisfies r(r + 1) ≥ 2d and the constraint set is a smooth manifold, then any second-order critical point of the nonconvex problem is a global optimum [8]. Another approach, that requires Θ(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 [11].
Alternatively, randomized sketching to a low dimensional subspace is often used as a low-memory alternative to storing a matrix decision variable [31, 34]. Recently, such sketched variables have been used to generate a 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 O(d + rn/ζ) for some sketching parameter ζ ∈ (0, 1). Gaussian sampling-based Frank-Wolfe [27] usesO(n+ d) memory to generate zero-mean Gaussian samples whose covariance represents a 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 n2 constraints, for which applying the existing low-memory techniques provide no benefit since the memory requirement of these techniques depends on the number of constraints in the problem. These problems have been studied extensively in literature as we see below.
MAX-K-CUT. MAX-K-CUT and its dual MIN-K-PARTITION have applications in frequency allocation [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 [21]. In each case, however, the SDP relaxation has Ω(n2) 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. [10], Swamy [30] provide 0.766-approximation schemes for MAX-AGREE 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 kmedian [3, 24]. Ahn et al. [1] propose a single-pass, Õ(|E|+n −10)-time 0.766(1− )-approximation algorithm for MAX-AGREE that uses Õ(n/ 2) memory. In contrast, to achieve the same approxima-
tion guarantee, our approach usesO ( n+ min { |E|, n logn 2 }) memory which is equal toO(n+ |E|)
for sparse graphs, and is independent of . Furthermore, the computational complexity of our approach has a better dependence on given by O ( n2.5 2.5 min{|E|, n logn 2 } 1.25 log(n/ ) log(|E|) )
which is at most O ( n3.75 5 (log n) 1.25 log(n/ ) log(|E|) ) . Moreover, our approach is algorithmically
simple to implement.

heading: 1.5 Outline
text: In Section 2, we review the Gaussian sampling-based Frank-Wolfe method [27] to compute a nearfeasible, near-optimal solution to SDPs with linear equality and inequality constraints. In Sections 3 and 4 respectively, we adapt the Gaussian sampling-based approach to give an approximation algorithm for MAX-K-CUT and MAX-AGREE respectively, that use only O(n + |E|) memory, proving Propositions 1 and 2 respectively. In Section 5, we show how to combine our methods with streaming spectral sparsification to reduce the memory required to O(n log n/ 2) for dense graphs presented edge-by-edge in a stream. We provide some preliminary computational results for MAX-AGREE in Section 6, and conclude our work and discuss possible future directions in Section 7. All proofs are deferred to the Supplementary material. Notations. The matrix inner product is denoted by 〈A,B〉 = Tr ( ATB ) . The vector of diagonal entries of a matrix X is diag(X), and diag∗(x) is a diagonal matrix with the vector x on the diagonal. The notations O,Ω,Θ have the usual complexity interpretation and Õ suppresses the dependence on log n. An undirected edge (i, j) in the set E is denoted using (i, j) ∈ E and ij ∈ E interchangably.

heading: 2 Gaussian Sampling-based Frank-Wolfe
text: Consider a smooth, concave function g and define the trace constrained SDP
max X∈S
g(B(X)), (BoundedSDP)
where S = {Tr(X) ≤ α,X 0} and B(·) : Sn → Rd is a linear mapping that projects the variable from ( n+1 2 ) -dimensional space to a d-dimensional space. One algorithmic approach to solving (BoundedSDP) is to use the Frank-Wolfe algorithm [18] which, in this case, computes an -optimal solution by taking steps of the form Xt+1 = (1− γt)Xt + γtαhthTt , where γt ∈ [0, 1] and unit vectors ht’s arise from approximately solving a symmetric eigenvalue problem that depends only on B(Xt) and g(·). Standard convergence results show that an -optimal solution is reached after O(Cug / ) iterations, where Cug is an upper bound on the curvature constant of g [18].
Frank-Wolfe with Gaussian sampling. The Gaussian sampling technique of [27] replaces the matrix-valued iterates, Xt, with Gaussian random vectors zt ∼ N (0, Xt). The update, at the level of samples, is then zt+1 = √ 1− γtzt + √ γtα ζtht, where ζt ∼ N (0, 1). Note that zt+1 is also a zero-mean Gaussian random vector with covariance equal to Xt+1 = (1 − γt)Xt + γtαhthTt . Furthermore, to track the change in the objective function value, it is sufficient to track the value vt = B(Xt), and compute vt+1 such that vt+1 = (1− γt)vt + γtB(αhthTt ). Thus, computing the updates to the decision variable and tracking the objective function value only requires the knowledge of zt ∼ N (0, Xt) and B(Xt), which can be updated without explicitly storing Xt, thereby reducing the memory used.
Algorithm 1 [27] describes, in detail, Frank-Wolfe algorithm with Gaussian sampling when applied to (BoundedSDP). It uses at most O(n + d) memory at each iteration, and after at most O(Cug / ) iterations, returns a sample ẑ ∼ N (0, X̂ ), where X̂ is an -optimal solution to (BoundedSDP).

heading: 2.1 SDP with linear equality and inequality constraints
text: Consider an SDP with linear objective function and a bounded feasible region,
max X 0 〈C,X〉 subject to { A(1)(X) = b(1) A(2)(X) ≥ b(2), (SDP)
Algorithm 1: (FWGaussian) Frank-Wolfe Algorithm with Gaussian Sampling [27] Input :Input data for (BoundedSDP), stopping criteria , accuracy parameter η, upper bound Cug on the curvature constant, probability p for the subproblem LMO Output :z ∼ N (0, X̂ ) and v = B(X̂ ), where X̂ is an -optimal solution of (BoundedSDP)
1 Function FWGaussian: 2 Select initial point X0 ∈ S; set v0 ← B(X0) and sample z0 ∼ N (0, X0) 3 t← 0, γ ← 2/(t+ 2) 4 (ht, qt)← LMO(B∗(∇g(vt)), 12ηγC u g ) 5 while 〈qt − vt,∇g(vt)〉 > do 6 (zt+1, vt+1)← UpdateVariable(zt, vt, ht, qt, γ) 7 t← t+ 1, γ ← 2/(t+ 2) 8 (ht, qt)← LMO(B∗(∇g(vt)), 12ηγC u g , p)
9 end 10 return (zt, vt) 11 Function LMO(J , δ): 12 Find a unit vector h such that with probability at least 1− p,
αλ = α〈hhT , J〉 ≥ maxd∈S α〈d, J〉 − δ 13 if λ ≥ 0 then q ← B(αhhT ) 14 else q ← 0, h← 0 15 return (h, q) 16 Function UpdateVariable(z, v, h, q, γ): 17 z ← ( √ 1− γ)z +√γαhζ where ζ ∼ N (0, 1) 18 v ← (1− γ)v + γq 19 return (z, v)
where A(1)(·) : Sn+ → Rd1 and A(2)(·) : Sn+ → Rd2 are linear maps. To use Algorithm 1, the linear constraints are penalized using a smooth penalty function. Let ul = 〈A(1)l , X〉−b (1) l for l = 1, . . . , d1 and vl = b (2) l − 〈A (2) l , X〉 for l = 1, . . . , d2. For M > 0, the smooth function φM (·) : Rd1+d2 → R,
φM (u, v) = 1
M log  d1∑ i=1 eM(ui) + d1∑ i=1 eM(−ui) + d2∑ j=1 eM(vj)  , satisfies (3) max { ‖u‖∞,max
i vi
} ≤ φM (u, v) ≤ log(2d1 + d2)
M + max
{ ‖u‖∞,max
i vi
} .
We add this penalty term to the objective of (SDP) and define
max X 0
{ 〈C,X〉 − βφM (A(1)(X)− b(1), b(2) −A(2)(X)) : Tr(X) ≤ α } , (SDP-LSE)
where α, β and M are appropriately chosen parameters. Algorithm 1 then generates a Gaussian sample with covariance X̂ which is an -optimal solution to (SDP-LSE). It is also a near-optimal, near-feasible solution to (SDP). This result is a slight modification of [27, Lemma 3.2] which only provides bounds for SDPs with linear equality constraints.
Lemma 1. For > 0, let (X?, ϑ?, µ?) be an optimal primal-dual solution to (SDP) and its dual, and let X̂ be an -optimal solution to (SDP-LSE). If β > ‖ϑ?‖1 + ‖µ?‖1 and M > 0, then
〈C,X?〉 − β log(2d1 + d2) M
− ≤ 〈C, X̂ 〉 ≤ 〈C,X?〉+ (‖ϑ?‖1 + ‖µ?‖1) β log(2d1+d2)M +
β − ‖ϑ?‖1 − ‖µ?‖1 ,
max { ‖A(1)(X)− b(1)‖∞,max
i
( b (2) i −A (2) i (X) )} ≤ β log(2d1+d2)M +
β − ‖ϑ?‖1 − ‖µ?‖1 .
3 Application of Gaussian Sampling to (k-Cut-SDP)
In this section, we look at the application of Gaussian sampling to MAX-K-CUT. Since Algorithm 1 uses O(n2) memory when solving (k-Cut-SDP), we define a new SDP relaxation of MAX-K-CUT with the same approximation guarantee, but with O(|E|) constraints. We then apply Algorithm 1 to this new relaxation, and show how to round the solution to achieve nearly the same approximation ratio as given in (1). Let
αk = min −1/(k−1)≤ρ≤1
kp(ρ)
(k − 1)(1− ρ) , (4)
where p(Xij) is the probability that vertices i and j are in different partitions. If X is feasible for (k-Cut-SDP) and CUT is the value of the k-cut generated by the FJ rounding scheme, then
E[CUT] = ∑
ij∈E,i<j wijp(Xij)
≥ ∑
ij∈E,i<j
k − 1 k
wij(1−Xij)αk = αk〈C,X〉. (5)
Frieze and Jerrum [14] derive a lower bound on αk, showing that the method gives a nontrivial approximation guarantee. Observe that (5) depends only on the values Xij if (i, j) ∈ E.
A new SDP relaxation of MAX-K-CUT. We relax the constraints in (k-Cut-SDP) to define
max X 0
〈C,X〉 subject to {
diag(X) = 1 Xij ≥ − 1k−1 (i, j) ∈ E, i < j.
(k-Cut-Rel)
Since (k-Cut-Rel) is a relaxation of (k-Cut-SDP), its optimal objective function value provides an upper bound on 〈C,X?〉, where X? is an optimal solution to (k-Cut-SDP), and hence, on the optimal k-cut value optGk . Note that the bound in (5) holds true even if we replace X
? by an optimal solution to (k-Cut-Rel) since it depends on the value of Xij only if (i, j) ∈ 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., E[CUT] ≥ αkoptGk .
Using Algorithm 1. We now have an SDP relaxation of MAX-K-CUT that has n+ |E| constraints. Penalizing the linear constraints in (k-Cut-Rel) using the function φM (·) (3), Algorithm 1 can now be used to generate k samples with covariance X̂ which is an -optimal solution to
max X 0
{ 〈C,X〉 − βφM ( diag(X)− 1,− 1k−1 − e T i Xej ) : (i, j) ∈ E,Tr(X) ≤ n } . (k-Cut-LSE)
Optimality and feasibility results for (k-Cut-Rel). Given an -optimal solution to (k-Cut-LSE), we show that it is also a near-optimal, near-feasible solution to (k-Cut-Rel).
Lemma 2. For ∈ (0, 1/2), let X?R be an optimal solution to (k-Cut-Rel) and let X̂ be an Tr(C)optimal solution to (k-Cut-LSE). For β = 6Tr(C) and M = 6 log(2n+|E|) , we have
(1− 2 )〈C,X?R〉 ≤ 〈C, X̂ 〉 ≤ (1 + 4 )〈C,X?R〉 and (6)
‖diag(X̂ )− 1‖∞ ≤ , [X̂ ]ij ≥ − 1
k − 1 − , (i, j) ∈ E, i < j. (7)
Generating a feasible solution to MAX-K-CUT. Since X̂ might not necessarily be feasible to (k-Cut-Rel), we cannot apply the FJ rounding scheme to the samples zi ∼ N (0, X̂ ). We, therefore, generate samples zfi ∼ N (0, Xf ) using the procedure given in Algorithm 2 such that Xf is a feasible solution to (k-Cut-Rel) and 〈C,Xf 〉 is close to 〈C, X̂ 〉.
We can now apply the FJ rounding scheme to zf1 , . . . , z f k as given in Lemma 3. Lemma 3. For G = (V,E), let optGk be the optimal k-cut value and let X?R be an optimal solution to (k-Cut-Rel). For ∈ ( 0, 14 ) , let X̂ 0 satisfy (6) and (7). Let zf1 , . . . , z f k be random vectors generated by Algorithm 2 with input zi, . . . , zk ∼ N (0, X̂ ) and let CUT denote the value of a k-cut generated by applying the FJ rounding scheme to zf1 , . . . , z f k . For αk as defined by (4), we have
αk(1− 4 )optGk ≤ αk(1− 4 )〈C,X?R〉 ≤ E[CUT] ≤ optGk . (8)
Algorithm 2: Generate Gaussian samples with covariance feasible to (k-Cut-Rel)
Input :Sample zi ∼ N (0, X̂ ) for i = 1, . . . , k and diag(X̂ ) Output :zfi ∼ N (0, Xf ) for i = 1, . . . , k with Xf feasible to (k-Cut-Rel)
1 Function GeneratekSamples: 2 for i = 1, . . . , k do 3 Set err = max{0,max(i,j)∈E,i<j −1/(k − 1)− [X̂ ]ij} 4 Set zi = zi + √ err y 1, where y ∼ N (0, 1)
5 Generate ζ ∼ N ( 0, I − diag∗ (
diag(X̂ )+err max(diag(X̂ ))+err )) 6 Set zfi =
zi√ max(diag(X̂ ))+err + ζ
7 end 8 return zf1 , . . . , z f k
Computational complexity of Algorithm 1 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 1. Lemma 4. When the method proposed in this section (Section 3), with p = T (n, ) and T (n, ) = 144 log(2n+|E|)n2
2 , is used to generate an approximate k-cut to MAX-K-CUT, the generated cut satisfies E[CUT] ≥ αk(1− 5 )optGk and runs in O ( n2.5|E|1.25 2.5 log(n/ ) log(|E|) ) time.
4 Application of Gaussian Sampling to (MA-SDP)
We now look at the application of our Gaussian sampling-based method to MAX-AGREE. Algorithm 1 uses O(n2) memory to generate samples whose covariance is an -optimal solution to (MA-SDP). However, with the similar observation as in the case of MAX-K-CUT, we note that for any X feasible to (MA-SDP), the proof of the inequality E[C] ≥ 0.766〈C,X〉, given in [10, Theorem 3], requires Xij ≥ 0 only if (i, j) ∈ E. We therefore, write a new relaxation of (MA-SDP),
max X 0
〈C,X〉 = 〈W+ + LG− , X〉 subject to {
Xii = 1 ∀ i ∈ {1, . . . , n} Xij ≥ 0 (i, j) ∈ E, i < j,
(MA-Rel)
with only n + |E| constraints. The bound E[C] ≥ 0.766〈C,X?〉 ≥ 0.766optGCC on the expected value of the clustering holds even if the clustering is generated by applying the CGW rounding scheme to an optimal solution X? of (MA-Rel). To use Algorithm 1, we penalize the constraints in (MA-Rel) and define
max X 0
{ 〈C,X〉 − βφM (diag(X)− 1,−eTi Xej) : (i, j) ∈ E,Tr(X) ≤ n } . (MA-LSE)
Optimality and feasibility results for (MA-Rel). Algorithm 1 is now used to generate z ∼ N (0, X̂ ), where X̂ is an -optimal solution to (MA-LSE). We show in Lemma 5 that X̂ is also a near-optimal, near-feasible solution to (MA-Rel). Lemma 5. For ∆ = Tr(LG−)+ ∑ ij∈E+ w + ij , ∈ ( 0, 14 ) , letX?G be an optimal solution to (MA-Rel) and X̂ be an ∆-optimal solution to (MA-LSE). Setting β = 4∆ and M = 4 log(2n+|E|) , we have
(1− 4 )〈C,X?G〉 ≤ 〈C, X̂ 〉 ≤ (1 + 4 )〈C,X?G〉 and (9) ‖diag(X̂ )− 1‖∞ ≤ , [X̂ ]ij ≥ − , (i, j) ∈ E, i < j. (10)
Generating an approximate clustering. The CGW rounding scheme can only be applied if we 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(i,j)∈E,i<j −[X̂ ]ij} and input z1, z2, z3 ∼ N (0, X̂ ), to generate zero-mean Gaussian samples whose covariance is a feasible solution to (MA-Rel). Finally, we apply the CGW rounding scheme to the output of the modified of Algorithm 2.
Lemma 6. Let X?G be an optimal solution to (MA-Rel). For ∈ (0, 1/6), let X̂ 0 satisfy (9) and (10), and let zf1 , z f 2 , z f 3 be random vectors generated by Algorithm 2 with input z1, z2, z3 ∼ N (0, X̂ ). Let optGCC 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 zf1 , z f 2 , z f 3 using the CGW rounding scheme. Then E[C] ≥ 0.766(1− 6 )〈C,X?G〉 ≥ 0.766(1− 6 )optGCC . (11)
Computational complexity of Algorithm 1 when applied to (MA-LSE). Lemma 7. When the method proposed in this section (Section 4), with p = T (n, ) and T (n, ) = 64 log(2n+|E|)n2
2 , is used to generate an approximate clustering, the value of the clustering satisfies E[C] ≥ 0.766(1− 7 )optGCC and runs in O ( n2.5|E|1.25 2.5 log(n/ ) log(|E|) ) time.
This completes the proof of Proposition 2.

heading: 5 Sparsifying the Laplacian Cost Matrix
text: As seen in Sections 3 and 4, the memory requirement for generating and representing an -optimal solution to (k-Cut-LSE) and (MA-LSE) is bounded by O(n+ |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 a sparse approximation with similar spectral properties. We refer to this additional step as sparsifying the cost.
Definition 1 (τ -spectral closeness). Two graphs G and G̃ defined on the same set of vertices are said to be τ -spectrally close if, for any x ∈ Rn and τ ∈ (0, 1),
(1− τ)xTLGx ≤ xTLG̃x ≤ (1 + τ)x TLGx. (12)
Spectral graph sparsification has been studied quite extensively (see, e.g., [2, 15, 28]). Kyng et al. [22] propose a O(|E| log2 n)-time framework to replace a dense graph G = (V,E) by a sparser graph G̃ = (V, Ẽ) such that |Ẽ| ∼ O(n log n/τ2) and G̃ satisfies (12) with probability 1− 1poly(n) . Their algorithm assumes that the edges of the graph arrive one at a time, so that the total memory requirement is O(n log n/τ2) rather than O(|E|). Furthermore, a sparse cost matrix decreases the computation time of the subproblem in Algorithm 1 since it involves matrix-vector multiplication with the gradient of the cost.
MAX-K-CUT with sparsification. Let G̃ be a sparse graph with O(n log n/τ2) 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 G̃ (using O(n log n/τ2) memory) whose expected value satisfies the bound (8). Note that, this generated cut is also a k-cut for the original graph G with provable approximation guarantee as shown in Lemma 8.
Lemma 8. For , τ ∈ (0, 1/5), let X̂ be a 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 2 followed by the FJ rounding scheme to X̂ . Then the generated cut satisfies
αk(1− 4 − τ)optGk ≤ E[CUT] ≤ optGk , where optGk is the value of the optimal k-cut for the original graph G.
MAX-AGREE with sparsification. The number of edges |E+| and |E−| in graphs G+ and G− respectively determine the working memory of Algorithm 1. For dense input graphs G+ and G−, we sparsify them to generate graphs G̃+ and G̃− with at most O(n log n/τ2) edges and define
max X∈S
f̃(X) = 〈LG̃− + W̃ +, X〉 − βφM (diag(X)− 1,−[eTi Xej ](i,j)∈Ẽ), (MA-Sparse)
where S = {X : Tr(X) ≤ n,X 0}, LG̃− is the Laplacian of the graph G̃−, W̃+ is matrix with nonnegative entries denoting the weight of each edge (i, j) ∈ Ẽ+, and Ẽ = Ẽ+ ∪ Ẽ−.
Algorithm 1 then generates an (Tr(LG̃−) + ∑ ij∈Ẽ+ w̃ + ij)-optimal solution, X̂ , to (MA-Sparse) usingO(n log n/τ2) memory. We can now use the method given in Section 4 to generate a clustering of graph G̃ whose expected value, E[C], satisfies (11). The following lemma shows that C also represents a clustering for the original graph G with provable guarantees.
Lemma 9. For , τ ∈ (0, 1/9), let X̂ be a near-feasible, near-optimal solution to (MA-Sparse) defined on the graph G̃ that satisfies (9) and (10). Let C denote the value of the clustering generated by applying Algorithm 2 followed by the CGW rounding scheme to X̂ . Then, E[C] satisfies
0.766(1− 6 − 3τ)(1− τ2)optGCC ≤ E[C] ≤ optGCC ,
where optGCC 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 a time in a stream. The procedure given in this section uses at most O(n log n/τ2) memory and in O ( n2.5|E|1.25 2.5 log(n/ ) log(|E|) ) -time, generates approximate solutions to MAX-K-CUT and MAX-
AGREE that satisfy the bounds E[CUT] ≥ αk(1− 5 − τ)optGk and E[C] ≥ 0.766(1− 7 − 3τ)(1− τ2)optGCC respectively.

heading: 6 Computational Results
text: 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 to 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, j) ∈ 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 Jij = |N(i)∩N(j)|/|N(i)∪N(j)|, where N(i) is the set of neighbours of i for each edge (i, j) ∈ E. Next we computed the quantity Sij = log((1−Jij +δ)/(1+Jij−δ)) with δ = 0.05 for each edge (i, j) ∈ E, which is a measure of the amount of ‘similarity’ or ‘dissimilarity’. Finally, the edge (i, j) was labelled as ‘dissimilar’ if Sij < 0 with w−ij = −Sij and labelled as ‘similar’ with w+ij = Sij otherwise. Experimental Setup. We set the input parameters to = 0.05, ∆ = Tr(LG−) + ∑ ij∈E+ w + ij , β = 4∆, M = 4 log(2n)+|E| . Using Algorithm 1, (MA-LSE) was solved to ∆-optimality and, we computed feasible samples using Algorithm 2. Finally, we generated two Gaussian samples and created at most four clusters by applying the 0.75-rounding scheme proposed by Swamy [30, Theorem 2.1], 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 1. 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 ∆-convergence satisfied the bound given in Proposition 1 and the infeasibility of the covariance X̂ of the generated samples was less than satisfying (10). We generated 10 pairs of i.i.d. zero-mean 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 Cbest. Note that, Cbest ≥ E[C] ≥ 0.75(1 − 6 )〈C,X?G〉 ≥ 0.75 1−6 1+4 〈C, X̂ 〉, where the last inequality follows from
combining (11) with (9). Since we were able to generate the values, Cbest and 〈C, X̂ 〉, we noted that the weaker bound Cbest/〈C, X̂ 〉 = AR ≥ 0.75(1− 6 )/(1 + 4 ) was satisfied by every input graph when = 0.05.
Table 1 also shows the memory used by our method. Consider the dataset G1, for which the memory used by our method was 1526.35kB ≈ 9.8× (|V |+ |E+|+ |E−|)× 8, where a factor of 8 denotes that MATLAB requires 8 bytes to store a real number. Similarly, we observed that our method used at most c× (|V |+ |E+|+ |E−|)× 8 memory to generate clusters for other instances from GSET, where c ≤ 33 for every instance of the input graph, showing that the memory used was linear in the size of the input graph.

heading: 7 Discussion
text: In this paper, we proposed a Gaussian sampling-based optimization algorithm to generate approximate solutions to MAX-K-CUT, and the MAX-AGREE variant of correlation clustering using O ( n+ min { |E|, n lognτ2 }) memory. The approximation guarantees given in [10, 14, 30] for these problems are based on solving SDP relaxations of these problems that have n2 constraints. The key observation that led to the low-memory method proposed in this paper was that the approximation guarantees from literature are preserved for both problems even if we solve their weaker SDP relaxations with only O(n+ |E|) constraints. We showed that for MAX-K-CUT, and the MAX-AGREE variant of correlation clustering, our approach nearly preserves the quality of the solution as given in [10, 14]. We also implemented the method outlined in Section 4 to generate approximate clustering for random graphs with provable guarantees. The numerical experiments showed that while the method was simple to implement, it was slow in practice. However, there is scope for improving the convergence rate of our method so that it can potentially be applied to the large-scale instances of various real-life applications of clustering.
Extending the low-memory method to solve problems with triangle inequalities. The known nontrivial approximation guarantees for sparsest cut problem involve solving an SDP relaxation that has n3 triangle inequalities [4]. It would be interesting to see whether it is possible to simplify these SDPs in such a 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 DE210101056) funded by the Australian Government.

Review summaries:
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.  A 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.

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.

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. 	This 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)$.

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.