summaries: The authors of this paper consider the individual fair k-clustering problem, as introduced by Jung et al. [FORC 19]. In this model, for every point $j$ there is a given radius $r_j$, and the goal is to choose a set of centers such that each point has an open center within distance $r_j$ from it, and also one of the standard clustering objective functions is minimized.  Specifically, under the k-median and k-means objectives, the authors provide improved guarantees compared to the state of the art results (Mahabadi and Vakilian [ICML 2020]). For the k-median objective, they give an $(8,8)$-bicriteria algorithm, while the best known result was an $(84,7)$ one. For k-means their result is an $(4,8)$-bicriteria algorithm, while the result of Mahabadi and Vakilian was a $(\gamma,7)$ one, with $\gamma$ being a very large constant. (an $(a,b)$-bicriteria solution has objective cost at most $a$ times the optimal, and for every $j$ it has an open center within distance at most $b \cdot r_j$ from it).  The authors achieve their results via standard LP-rounding techniques.

summaries: This paper introduces a new algorithm for fair k-clustering problem(specifically when cost is measure with l_p norm for different p values) based on LP rounding. It provides a bi-criteria approximation guarantee for the clustering objective and experiments are provided to validate the theoretical properties. It is also shown how the runtime of the algorithm can be improved using sparsification with minimal effects on the objective.

summaries: The paper studies the problem of \ell_p norm and center-based clustering with a fairness consistent. The fairness constraint roughly says that no point should be further from its assigned center than it is from its (n/k)-th furthest neighbor. The authors consider a Linear Programming based (approximation) algorithm for this problem.

summaries: This submission proposes an approximation algorithm for individual fair k-clustering in a metric space. Here, individual fairness means that each point v has an individual radius $r(v)$ and we require an open facility within radius $r(v)$ of $v$. We may use the radius $r(v)$ to provide each point $v$ with a "fair share" of its assigned facility by, for instance, choosing $r(v)$ as the smallest radius such that $n/k$ points lie within radius $r(v)$ of $v$; as originally proposed by Jung, Kannan, and Lutz.   The approximation algorithm is the main contribution of the submission. It works for any p-norm objective and is bi-criterial, guaranteeing an $2^{1+2/p}$-approximation of the  objective while ensuring an open facility within radius $8r(v)$ of each point $v$. However, it requires a metric space which means, in particular, that all facilities/centers have to be chosen from the point set.  The algorithm roughly works in the following way: First, the authors compute an optimum solution to a linear programming relaxation of the problem. The solution is turned into an input for a filter function by Plesnik/Rita, Moro and Cortez; this function replaces the original point set by a smaller set of representatives. In the original version of the filter, the function may be run until only $k$ representatives remain (a point may represent another if it can serve as the point's facility; hence, in the original filter, the representatives are then chosen as the facilities to open). In this case, however, it may be that the filter stops early as the fairness restriction on the connection radius may make it impossible to cover all points with $k$ representatives. Hence, a final step is required to reduce the set of representatives down to $k$ points. This is done via an LP-rounding algorithm and turns out to be a substantial amount of work. Finally, in order to improve the running time of the algorithm, the authors propose a sparsification technique for the LP-relaxation (whose size is otherwise quadratic in the number of points and could be prohibitive for larger point sets).  An empirical part shows improvements over the previous approach.

abstractText: We study data clustering problems with lp-norm objectives (e.g. k-MEDIAN and k-MEANS) in the context of individual fairness. The dataset consists of n points, and we want to find k centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point v has a center within a distance at most r(v), where r(v) is v’s distance to its (n/k)th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the l∞ or k-CENTER objective. Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all lp-norms. Empirically, their algorithms outperform Jung et. al.’s by a large margin in terms of cost (for kMEDIAN and k-MEANS), but they incur a reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions. Although solving the LP exactly might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.

authors:
Mohsen Abbasi
Aditya Bhaskara
Suresh Venkatasubramanian

title: Fair clustering via equitable group representations

venue: In Proceedings of the 2021 ACM Conference on Fairness,

authors:
Sara Ahmadian
Ashkan Norouzi-Fard
Ola Svensson
Justin Ward

title: Better guarantees for k-means and euclidean k-median by primal-dual algorithms

venue: In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS),

authors:
Soroush Alamdari
David B. Shmoys

title: A bicriteria approximation algorithm for the k-center and k-median problems

venue: In WAOA,

authors:
David Arthur
Sergei Vassilvitskii

title: K-means++: The advantages of careful seeding

venue: In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA),

authors:
Tanvi Bajpai
Deeparnab Chakrabarty
Chandra Chekuri
Maryam Negahbani

title: Revisiting priority k-center: Fairness and outliers

authors:
Suman Bera
Deeparnab Chakrabarty
Nicolas Flores
Maryam

title: Negahbani. Fair algorithms for clustering

venue: In Adv. in Neural Information Processing Systems (NeurIPS),

authors:
Jarosław Byrka
Thomas Pensyl
Bartosz Rybicki
Aravind Srinivasan
Khoa Trinh

title: An improved approximation for k-median, and positive correlation in budgeted optimization

authors:
Jaroslaw Byrka
Krzysztof Sornat
Joachim Spoerhase

title: Constant-factor approximation for ordered k-median

venue: In Proceedings, ACM Symposium on Theory of Computing (STOC),

authors:
L. Elisa Celis
Damian Straszak
Nisheeth K. Vishnoi

title: Ranking with Fairness Constraints

authors:
Deeparnab Chakrabarty
Chaitanya Swamy

title: Interpolating between k-median and k-center: Approximation algorithms for ordered k-median

title: Approximation algorithms for minimum norm and ordered optimization problems

authors:
Moses Charikar
Sudipto Guha
Éva Tardos
David B Shmoys

title: A constant-factor approximation algorithm for the k-median problem

venue: Journal of Computer and System Sciences,

authors:
Xingyu Chen
Brandon Fain
Liang Lyu
Kamesh Munagala

title: Proportionally fair clustering

venue: In Proceedings, International Conference on Machine Leanring (ICML),

authors:
Flavio Chierichetti
Ravi Kumar
Silvio Lattanzi
Sergei Vassilvitskii

title: Fair clustering through fairlets

authors:
Vincent Cohen-Addad
C.S. Karthik
Euiwoong Lee

title: On approximability of clustering problems without candidate centers

title: Clustering to Minimize the Maximum Intercluster Distance

venue: Theoretical Computer Science,

authors:
Inge Li Gørtz
Anthony Wirth

title: Asymmetry in k-center variants

authors:
Sudipto Guha
Samir Khuller

title: Greedy strikes back: Improved facility location algorithms

authors:
David G. Harris
Shi Li
Thomas Pensyl
Aravind Srinivasan
Khoa Trinh

title: Approximation algorithms for stochastic clustering

venue: Journal of Machine Learning Research,

authors:
Dorit S. Hochbaum
David B. Shmoys

title: A best possible heuristic for the k-center problem

venue: Math. Oper. Res.,

authors:
K. Jain
V.V. Vazirani

title: Approximation algorithms for metric facility location and kmedian problems using the primal-dual schema and lagrangian relaxation

venue: Journal of the ACM,

authors:
Matthew Joseph
Michael Kearns
Jamie H Morgenstern
Aaron Roth

title: Fairness in learning: Classic and contextual bandits

authors:
Christopher Jung
Sampath Kannan
Neil Lutz

title: Service in your neighborhood: Fairness in center location

venue: In Proceedings, Foundations of Responsible Computing, FORC 2020,

authors:
Toshihiro Kamishima
Shotaro Akaho
Hideki Asoh
Jun Sakuma

title: Fairness-aware classifier with prejudice remover regularizer

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Tapas Kanungo
David M Mount
Nathan S Netanyahu
Christine D Piatko
Ruth Silverman
Angela Y Wu

title: An efficient k-means clustering algorithm: Analysis and implementation

venue: IEEE transactions on pattern analysis and machine intelligence,

title: Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid

venue: In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Sepideh Mahabadi
Ali Vakilian

title: individual) fairness for k-clustering

authors:
Evi Micha
Nisarg Shah

title: Proportionally fair clustering revisited

venue: In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020),

authors:
F. Pedregosa
G. Varoquaux
A. Gramfort
V. Michel
B. Thirion
O. Grisel
M. Blondel
P. Prettenhofer
R. Weiss
V. Dubourg
J. Vanderplas
A. Passos
D. Cournapeau
M. Brucher
M. Perrot
E. Duchesnay

title: Scikit-learn: Machine learning in Python

title: A heuristic for the p-center problems in graphs

venue: Discrete Applied Mathematics,

authors:
Clemens Rösner
Melanie Schmidt

title: Privacy Preserving Clustering with Constraints

authors:
Beata Strack
Jonathan P DeShazo
Chris Gennings
Juan L Olmo
Sebastian Ventura
Krzysztof J Cios
John N Clore

title: Impact of hba1c measurement on hospital readmission rates: analysis of 70,000 clinical database patient

venue: records. BioMed research international,

authors:
Paulo Rita Sérgio Moro
Paulo Cortez

title: A data-driven approach to predict the success of bank telemarketing

venue: Decision Support Systems,

authors:
Ke Yang
Julia Stoyanovich

title: Measuring fairness in ranked outputs

venue: In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), page 22

title: Sequential and parallel algorithms for mixed packing and covering

venue: In 42nd Annual Symposium on Foundations of Computer Science,

authors:
Muhammad Bilal Zafar
Isabel Valera
Manuel Gomez-Rodriguez
Krishna P. Gummadi

title: Fairness constraints: Mechanisms for fair classification

venue: In Proceedings, International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Rich Zemel
Yu Wu
Kevin Swersky
Toni Pitassi
Cynthia Dwork

title: Learning fair representations

heading: 1 Introduction

text:
As machine learning algorithms are widely used in practice for making high-stakes decisions affecting human lives, there has been a huge body of work on FAIR-ML trying to ensure ‘fairness’ in the solutions returned by these algorithms. There are two large intersecting bodies of work : one body’s main focus in to understand what ‘fairness’ means (e.g. [26, 39, 38, 36, 14, 25]) in various different contexts, and the second body’s focus has been on addressing the algorithmic challenges brought forth by these considerations (e.g., [24, 9, 33, 6, 29, 5]).
This paper falls in the second class. In particular, we consider an individual fairness model proposed by Jung, Kannan, and Lutz [25] for a k-clustering problem. Given points (clients) X in a space with metric distance d, find k points (facilities) S ⊆ X , minimizing (∑ v∈X d(v, S) p )1/p
where d(v, S) is v’s distance to the closest point in S. This includes k-CENTER, k-MEDIAN and the popular k-MEANS objective for p =∞, p = 1 and p = 2 respectively, problems which have been extensively studied [12, 23, 27, 4, 2] in the algorithms literature. Jung et. al. [25] proposed that in this context a solution would be deemed individually fair, if for every client v ∈ X there is an open facility not too far from it. More precisely, if there is a facility within distance r(v) which is the smallest radius
∗Supported by NSF grant #2041920
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
around v that contains n/k points. The rationale behind n/k is that if all the points had equal chance of getting picked as a facility, each client v would expect a facility to be open within distance r(v). Furthermore, this formulation encourages a solution to open more facilities in dense areas of the metric which is motivated by the facility location application of clustering.
Jung et al. [25] gave a solution where every client v was served within a radius of 2r(v), which as a jargon is called 2-approximate fair solution. However, their solution did not explicitly consider the “objective” function (k-MEANS/k-MEDIAN, for instance) in the clustering problem, which is often used as a proxy to measure the quality of the clustering. This was addressed in a follow up paper by Mahabadi and Vakilian [29] who gave a (7, O(p))-approximation with respect to the ℓp-norm objective. That is, they give a local-search based solution which is 7-approximately fair, but the objective is violated by some Cp-factor where the constant C is rather large (for p = 1, the factor is 84). The theoretical running time of their algorithm is Õ(pk5n4).

heading: 1.1 Our Contributions

text:
The main contribution of our paper is to give improved algorithms for this problem using linear programming rounding. Our study stems from two observations: one, that the problem at the core of Jung et al. [25] was in fact studied as “weighted/priority k-CENTER problem” by Plesník[32], and that if all the r(v)’s were the same (which may not at all be the case), then the clustering problem has also been studied under the guise of centridian/ordered median problem [3, 8, 10]. Combining ideas from these two bodies of work, we design an (8, 8) algorithm for the FAIR-k-MEDIAN problem, which obtains an 8-approximation for both cost and fairness (our cost guarantees improve as p grows).
Result 1. There is an (8, 21+2/p)-approximation algorithm for FAIR-(p, k)-CLUSTERING that runs in LP solving time plus Õ(n2), overall Õ(kn4). In particular, we have (8, 8)-approximation and (8, 4)-approximation algorithms for FAIR-k-MEDIAN and FAIR-k-MEANS, respectively.
Remark. The approximation factor compares itself with the optimal solution which opens centers at the points in X . This is also the notion considered by [29] and [25]. If the optimal solution is allowed to open centers anywhere in the real space, then one has an additional factor 2 loss in the approximation [15]. Whether this extra hit of factor 2 is necessary, we leave as an interesting algorithmic question.
Although solving an LP may seem prohibitive in practice, we can obtain a much faster running time by implementing a sparsification routine (inspired by [32, 21]) with a marginal hit in the fairness and clustering cost (see Lemma 5 for details). Empirically, this greatly decreases the running time, and is often faster than the [29] implementation.
In our experiments, we also find that our theoretical bounds are too pessimistic. Indeed, we show that our algorithm’s cost is at most %1 more than the optimal clustering cost (which does not have any fairness violation), almost always, and never more than %15 in the rest. Furthermore, our maximum fairness violation is at most a factor of 1.27 which is much better than our theoretical guarantee of 8. We also do a more fine-grained analysis of the fairness violation : consider a vector where each coordinate stands for a clients “unfairness” indicating the ratio of its distance to r(v). When we plot this as a histogram, we find that most of the mass is shifted to the “left”, that is, the percentage of clients who satisfy their fairness constraints is significantly larger than in the [29] solution. This seems to suggest the linear program, which is trying to minimize the cost, itself tries to increase the number of fairly treated clients. We leave a theoretical investigation of this phenomenon for future work.
Our experiments also demonstrate the price of fairness. We find that our linear programs, which maintains absolute fairness, have objective value considerably larger than that of [29]. On the other hand, if we tune the “fairness violation” of the linear program to match that of [29], then the objective value of our algorithm drops. We run experiments to further elaborate on the inherent cost of fairness in our datasets by demonstrating how the optimal cost changes with respect to varying degrees of fairness relaxation.
It is worth noting that our algorithm works for arbitrary values of r(v) ≥ 0 for points v (and this may be true for [29] as well), and we present our results thus. This setting might be of interest in applications where the “fair radius” may not be n/k but something more nuanced.

heading: 1.2 Other related work

text:
k-CENTER has a 2-approximation due to Gonzales, and Hochbaum and Shmoys [17, 21] and they prove it is NP-hard to get better approximations. k-MEDIAN, and k-MEANS are hard to approximate within factors better than 1.73 and 3.94 [19] respectively with current best approximations being 2.67 by [7] and 9 by [2]. Also recently, there has been an improvement on lower-bounds for approximating Continuous k-MEDIAN and k-MEANS where centers can be picked anywhere in the real space. By Cohen-Addad, Karthik, and Lee [15], it is NP-hard to approximate Continuous k-MEDIAN and k-MEANS within factors 2− o(1) and 4− o(1) respectively. FAIR-k-CENTER is a special case of Priority k-CENTER where the radii r(v) in which a point v demands a center at that distance, are general values. [32] introduced this problem and gave a best possible 2-approximation. Gørtz and Wirth [18] study the problem for asymmetric metrics and prove that it is NP-hard to obtain any non-trivial approximation. [5] give a 9-approximation for the problem in presence of outliers and further generalize to constant approximations for general constraints on the solution centers. Another very closely related problem is Chance-k-Coverage introduced in [20] in which for any point v, in addition to r(v), a probability p(v) is given and the goal is to find a distribution on possible solutions such that a solution drawn from this distribution covers v with probability at least p(v). This also has a 9-approximation by [20].
A clustering problem related to FAIR-k-MEDIAN and FAIR-k-MEANS is the Simultaneous kClustering in which the goal is to find a solution with approximation guarantees with respect to any monotone, symmetric norm. This problem has an O(1)-approximation due to Chakrabarty and Swamy [11] with a line of previous work including [3, 10, 8].
Another similar notion of individual fairness is introduced by Chen et al. [13] in which a solution is fair if there is no group of size at least n/k for which there exists a facility that would reduce the connection cost of all members of the group if opened. [13] give a (1 + √ 2)-approximation for ℓ1, ℓ2, and ℓ∞ norm distances for the setting where facilities can be places anywhere in the real space. Micha and Shah [30] modified the approach to give close to 2-approximation for ℓ2 and proved the previous results for ℓ1 and ℓ∞ are indeed tight.
Recently, Abbasi et al. [1] introduced a new notion of fairness centered around providing equitable group representations. In this problem, the points are partitioned into groups and the goal is to minimize the maximum clustering cost a group can have in the solution. The idea is that the cluster centers should represent each group fairly, and this is captured by ensuring that each group’s clustering cost is comparable with the others. This notion is orthogonal to the fairness criteria we study in this paper; Although we could tune the maximum distance the points in a group can have to our solution, that does not give any guarantees with respect to the objective cost and vice versa.

heading: 2 Preliminaries

text:
In this section, we formally define our problems, establish some notations, and describe a classic clustering routine due to Hochbaum and Shmoys [21] with modifications by Plesník[32]. Given a subset S ⊆ X , we use d(v, S) to denote v’s distance to the closest point in S. Definition 1 (FAIR-(p, k)-CLUSTERING Problem). The input is a metric space (X, d), radius function r : X → R+, and integers p, k ≥ 1. The goal is to find S ⊆ X of size at most k such that d(v, S) ≤ r(v) for all v ∈ X and the clustering cost (∑ v∈X d(v, S) p )1/p is minimized.
Let opt be the clustering cost of an optimal solution. For α, β ≥ 1, an (α, β)-approximate solution is S ⊆ X of size at most k with d(v, S) ≤ αr(v) for all v ∈ X and (∑ v∈X d(v, S) p )1/p≤ βopt. In plain English, the fairness approximation is α while the objective/cost approximation is β. Our main result is the following.
Theorem 1. There is an (8, 21+2/p)-approximation algorithm for FAIR-(p, k)-CLUSTERING that runs in LP solving time plus Õ(n2), overall Õ(kn4).
The algorithm relies on rounding a solution to the following LP for FAIR-(p, k)-CLUSTERING2 where the optimal LP objective is at most optp. The variable yu denotes the amount by which u ∈ X
2The LP and its rounding is slightly different for p = ∞; we omit this from this version.
is open as a center. xvu for v, u ∈ X is the amount by which v is assigned to u. The constraints respectively capture the conditions: every client must connect to someone, k centers are opened, no client can connect to an unopened center, and crucially that a client cannot travel to a center further than r(v).
optp ≥ min ∑
v,u∈X d(v, u)pxvu (LP)∑
u∈X xvu = 1, ∀v ∈ X (LP1)∑
u∈X yu = k (LP2)
xvu ≤ yu, ∀v, u ∈ X (LP3)
xvu = 0, ∀v, u : d(v, u) > r(v) (LP4)
0 ≤ xvu, yu ≤ 1, ∀v, u ∈ X.
From here on, we use the notation B(u, r) for u ∈ X and r ∈ R+ to denote the points in a ball of radius r around u. That is B(u, r) := {v ∈ X : d(u, v) ≤ r}. Also, for any set of points U ⊆ X , let y(U) := ∑ u∈U yu. Considering (LP4) and (LP1) the following holds.
Fact 1. If y is from a feasible LP solution, then y(B(v, r(v))) ≥ 1 for all v ∈ X .
We now describe a routine Filter due to [32, 21] which is used as a subroutine in our main algorithm. Assume all the points are initially “uncovered”. The routine takes a function R : X → R+, sorts the points in order of increasing R(v)’s. Then it considers the first point in this order, calls it a “representative” and “covers” all the points v at distance at most 2r(v) from it. Call these points D(v). Repeating this procedure until all the points are covered, forms a partition on X such that the representatives are “far apart”, while each non-representative is assigned to a “nearby” representative, among other useful properties listed in Fact 2 and Fact 3.
Algorithm 1 Filter Input: Metric (X, d), radius function R : X → R+
1: U ← X ▷ The set of “uncovered points” 2: S ← ∅ ▷ The set of “representatives” 3: while U ̸= ∅ do 4: u← argminv∈U R(v) ▷ The first point in U in non-decreasing R order 5: S ← S ∪ u 6: D(u)← {v ∈ U : d(u, v) ≤ 2R(v)} ▷ D(u) = B(u, 2R(v)) ∩ U and includes u itself 7: U ← U\D(u) 8: end while
Output: S, {D(u) : u ∈ S}
Fact 2. [32, 21] The following is true for the output of Filter: (a) ∀u, v ∈ S, d(u, v) > 2max{R(u), R(v)}, (b) The balls {B(u,R(u)) : u ∈ S} are mutually disjoint, (c) The set {D(u) : u ∈ S} partitions X , (d) ∀u ∈ S,∀v ∈ D(u), R(u) ≤ R(v), and (e) ∀u ∈ S,∀v ∈ D(u), d(u, v) ≤ 2R(v).
Fact 3. For any u ∈ S and w ∈ B(u,R(u)), the unique closest point in S to w is u.
Proof. Suppose otherwise. That is, there exists v ∈ S not equal to u s.t. d(w, v) ≤ d(w, u). Then d(u, v) ≤ d(u,w) + d(w, v) ≤ 2d(w, u) ≤ 2R(u) which contradicts Fact 2 as we must have d(u, v) > 2max{R(u), R(v)}.
To elaborate on the importance of Algorithm 1 and build some intuition, we point out the following theorem of [32, 25].
Theorem 2. Take S the output of Algorithm 1 on a FAIR-(p, k)-CLUSTERING instance with R := r. Then if the instance is feasible, |S| ≤ k and d(v, S) ≤ 2r(v) for all v ∈ X .
Proof. By Fact 2 we know that {D(u) : u ∈ S} partitions X so for any v ∈ X , there exists a u ∈ S for which v ∈ D(u). Plus, d(v, u) ≤ 2R(v) = 2r(v). Now it only remains to prove |S| ≤ k. To see this, let S∗ be some feasible solution and observe that two different u,w ∈ S, cannot be
covered by the same center in S∗. Since otherwise, if there exists f ∈ S∗ for which d(u, f) ≤ r(u) and d(w, f) ≤ r(w) by triangle inequality d(u, v) ≤ d(u, f) + d(f, w) ≤ r(u) + r(v) and this contradicts d(u,w) > 2max{r(u), r(v)} from Fact 2.
But of course, the above theorem does not give any guarantees for the clustering cost (unless p =∞). It might be the case that many points are paying close to 0 towards the clustering cost in the optimal solution, but are made to connect to a point much farther in the above procedure.
3 Algorithm for FAIR-(p, k)-CLUSTERING problem
Now we are ready to describe our algorithm Fair-Round which establishes Theorem 1. At a highlevel, we run our Filter routine by defining the input function R in a manner that is conscious of the FAIR-(p, k)-CLUSTERING cost: given (x∗, y∗) which is an optimal solution to (LP), for any v ∈ X let Cv be v’s contribution to the LP cost i.e. Cv := ∑ u∈X d(v, u)
px∗vu and define R(v) := min{r(v), (2Cv)1/p}. Let us ponder for a bit to see what changes from Theorem 2. For the output S, we still have the fairness guarantee d(v, S) ≤ 2r(v) for all v but since (2Cv)1/p might be less than r(v) for any v, we cannot guarantee that |S| ≤ k. Thankfully, in this case, we can still prove |S| ≤ 2k (Corollary 1). The rest of the algorithm is deciding on a subset of at most k points out of this S to return as the final solution, while ensuring the fairness and cost guarantees are still within constant factor of the optimal. This idea is very similar to existing ideas in [3, 12] which look at the problem without fairness considerations.
Recall that {D(u) : u ∈ S} partitions X and each u ∈ S is responsible for covering all the points in D(u). Here, we could simply move each point in D(u) to u and divert the y value of each point to its closest point in S. Note that, y(S) = k (Fact 4) and similar to the proof of Theorem 2 we could show yu ≥ 1/2 (Lemma 1) for all u ∈ S hence |S| ≤ 2k (Corollary 1). If this leads to some y-value reaching 1, we open those centers.
For u ∈ S with yu < 1, if we do not decide to include it in the final solution, we promise to open Su, its closest point in S other than itself. In this case, all the |D(u)| points on u are delegated to Su. Using the fact that yu < 1, we can prove that fairness guarantee (Lemma 3) approximately holds for the points in D(u) even after this delegation.
To get the clustering cost guarantee, we need to do more work. Observe that, currently, u is already fractionally assigned to v by 1− yu. So if instead of yu ≥ 1/2 we had yu = 1/2 we could ensure that already u is assigned to v by 1/2 thus integrally assigning u to v only doubles the cost. This is why we need to do more work to get yu ∈ {1/2, 1} for u ∈ S (see Lemma 2) and then bound the clustering cost in Lemma 4. Fact 4. y(S) = k and remains so after Line 11.
Proof. We initialize y to y∗ for which y∗(X) = k by LP2. The algorithm then transfers y(X) to S by Line 11 without changing the total. Afterwards, the modifications in Lines 13 and 19 move the y mass around in S but the total value y(S) remains unchanged.
Lemma 1. After Line 14 of Algorithm 2, 1/2 ≤ yu ≤ 1 for all u ∈ S.
Proof. First we argue that yu ≥ 1/2 for all u ∈ S by the end of Line 11. Fix u ∈ S. Per Fact 3 y(B(u,R(u))) is entirely moved to yu. By definition of R(u) there are two cases: Case I, R(u) = r(u) thus yu ≥ 1 as y∗(B(v, r(v))) ≥ 1 for all v ∈ X according to Fact 1. Case II, R(u) = (2Cu)
1/p then by Markov’s inequality y∗(B(u,R(u))) ≥ 1/2 and after this point, yu is never decreased to below 1/2. More precisely, Cu = ∑ v∈X d(u, v) px∗uv ≥ ∑
v∈X: d(u,v)>R(u)
d(u, v)px∗uv ≥ 2Cu ∑
v∈X: d(u,v)>R(u)
x∗uv . Considering ∑ v∈X x ∗ uv = 1 by LP1, this implies ∑ v∈X:
d(u,v)≤R(u) x∗uv ≥ 1/2
thus y∗(B(u,R(u))) ≥ 1/2. As for proving yu ≤ 1, it might indeed be the case that yu > 1 by the end of Line 11 but the loop ending at Line 14 can guarantee yu ≤ 1 for all u ∈ S. This is because y(S) = k (Fact 4) and we already checked in the beginning of Algorithm 2 that |S| > k.
Corollary 1. S in Algorithm 2 has size at most 2k.
Algorithm 2 Fair-Round: FAIR-(p, k)-CLUSTERING bi-criteria approximation Input: Metric (X, d), radius function r : X → R+, and (x∗, y∗) an optimal solution of LP
1: Cv ← ∑ u∈X d(v, u) px∗vu ∀v ∈ X ▷ v’s cost share in the LP objective 2: R(v)← min{r(v), (2Cv)1/p} ∀v ∈ X 3: S, {D(u) : u ∈ S} ← Filter((X, d), R) 4: if |S| ≤ k then 5: return S 6: end if 7: (x, y)← (x∗, y∗) 8: for all v ∈ X\S do ▷ Direct y mass from outside of S to the closest point in S 9: u← closest point in S to v 10: yu ← yu + yv , yv ← 0 ▷ Note: May cause yu to increase above 1 11: end for 12: while There are u, v ∈ S with yu > 1 and yv < 1 do ▷ Ensure yu ≤ 1 for all u ∈ S 13: yu ← yu − δ, yv ← yv + δ, where δ := min{1− yv, yu − 1} 14: end while ▷ Remark: By now, 1/2 ≤ yu ≤ 1 for all u ∈ S (see Lemma 1). 15: Su ← closest point in S\u to u ∀u ∈ S 16: while There are u, v ∈ S with 17: 1/2 < yu < 1, and yv < 1, 18: d(u, Su)p|D(u)| > d(v, Sv)p|D(v)| do ▷ Move y mass from u to v if u is costlier 19: yu ← yu − δ, yv ← yv + δ, where δ := min{1− yv, yu − 1/2} 20: end while ▷ Remark: At this point, yu ∈ {1/2, 1} for all u ∈ S (see Lemma 2). 21: T ← u ∈ S with yu = 1 22: Consider the forest of arbitrary rooted trees on vertices u ∈ S with edges (u, Su). Let O be
odd-level vertices in S\T , and E be even-level vertices in S\T . 23: if |E| ≤ |O| then 24: T ← T ∪ E 25: else 26: T ← T ∪O 27: end if Output: T
Lemma 2. After Line 20 of Algorithm 2, yu ∈ {1/2, 1} for all u ∈ S.
Proof. Suppose not. Since y(S) = k (Fact 4) and k is an integer, by Lemma 1, there has to be at least two u, v ∈ S with yu, yv ∈ (1/2, 1) which is a contradiction, since either one of them has to be changed to 1/2 or 1 in the while loop ending at Line 20.
Lemma 3. For all v ∈ X , d(v, T ) ≤ 8r(v).
Proof. Fix v ∈ X . Since {D(u) : u ∈ S} partitions X there exists u ∈ S such that v ∈ D(u). According to Fact 2 d(v, u) ≤ 2R(v) ≤ 2r(v) by definition of R. If u ends up in T we are done. Else, it has to be that yu < 1 and Su ∈ T . In what follows, we prove that if yu < 1 at Line 20 then d(u, Su) ≤ 6r(v). This implies d(v, Su) ≤ 8r(v) hence the lemma. We know that initially y∗(B(v, r(v))) ≥ 1 per Fact 1 but since v /∈ S, the y mass on B(v, r(v)) has been moved to S by Line 11. If for all w ∈ B(v, r(v)) their closest point in S was u, all of y(B(v, r(v))) would be moved to u then yu = 1 by the end of Line 20. So there must exist w ∈ B(v, r(v)) with x∗vw > 0 along with u′ ∈ S, u′ ̸= u, such that d(w, u′) ≤ d(w, u) which made yw to be moved to u′. By definition of Su, d(u, Su) ≤ d(u, u′). Applying the triangle inequality twice gives:
d(u, Su) ≤ d(u, u′) ≤ d(u,w) + d(w, u′) ≤ 2d(u,w) ≤ 2(d(u, v) + d(v, w)) ≤ 2(2r(v) + r(v)) = 6r(v)
where the last inequality comes from Fact 2 stating d(u, v) ≤ 2r(v), and from the fact that x∗vw > 0 implies d(v, w) ≤ r(v) by LP4.
Lemma 4. (∑ v∈X d(v, T ) p )1/p ≤ ((2p+2)∑v,u∈X Cv)1/p ≤ 21+2/popt.
Proof. For the proof, we compare ∑
v∈X d(v, T ) p with the optimal LP cost ∑ v∈X Cv which is
at most optp. Fix v ∈ X and u ∈ S for which v ∈ D(u). By Fact 2 d(v, u) ≤ 2R(v) ≤ 2(2Cv)
1/p per definition of R. So moving D(u) to u for all u ∈ S has an additive cost of∑ u∈S ∑ v∈D(u) d(v, u) p ≤ 2p+1 ∑
v∈X Cv. From now on, assume there are D(u) collocated points on a u ∈ S. Moving around the y mass up to Line 11 adds a multiplicative factor of 2p loss in the approximation ratio. The logic is: if u ∈ S was relying on w ∈ X in the LP solution, meaning, x∗uw > 0 and yw was moved to a u′ ∈ S (due to d(w, u′) ≤ d(w, u)) then the cost u has to pay to connect to u′ is d(u, u′)p ≤ (d(u,w) + d(w, u′))p ≤ 2pd(u,w)p which is a 2p factor worse than the LP cost d(u,w)p it was paying to connect to w earlier.
At this point (Line 14), note that the cost incurred by u is |D(u)|d(u, Su)p(1 − yu). To elaborate on this, corresponding to y, we define an x such that (x, y) is feasible for LP. Let xuu = yu and xuSu = 1− yu so that LP4 is satisfied for u. Then the cost incurred by u is |D(u)|(d(u, u)pxuu + d(u, Su)
pxuSu) = |D(u)|d(u, Su)p(1 − yu). The while loop ending at Line 20 does not increase the value of the objective function: As we decrease yu and increase yv, only if the cost incurred by u is bigger than that of v. The last multiplicative factor 2 loss comes from when u ∈ S\T . In which case, yu = 1/2 and Su ∈ T . So by assigning u to Su we pay |D(u)|d(u, Su)p which is twice more than before (as 1 − yu = 1/2). Observe that this last step is why we needed to do all the work to get yu ∈ {1/2, 1} in Lemma 2. Putting the three steps together, the overall cost is at most 2× 2p + 2p+1 = 2p+2 times the LP cost or at most 21+2/popt.
Proof of Theorem 1. Using Corollary 1 and the fact that |T | ≤ |S|/2 by construction, we have |T | ≤ k. Lemmas 3 and 4 give the fairness and approximation guarantees. As for runtime, notice that Algorithm 2 runs in time Õ(n2). But the runtime is dominated by the LP solving time. According to [37], finding a (1 + ε)-approximation to LP takes time O(kn2/ϵ2). Setting ε = 1/n gives the O(kn4) runtime.
As evident, the runtime is dominated by the LP solving time. We end this section by descibing the sparsification pre-processing that when applied to the original instance, can tremendously decrease the LP solving time in practice while incurring only a small loss in fairness and clustering cost. One reason why the LP takes a lot of time is because there are many variables; xvu for every v ∈ X and every u within distance r(v) of v. To fix this, we first run the Filter algorithm on the data set with R(v) = δr(v), where δ is a tune-able parameter. It is not too hard to quantify the loss in fairness and cost as a function of δ, and we do so in the lemma below. More importantly, note that when δ = 1, then the number of variables goes down from n to O(k); this is because of the definition of r(v) which guarantees ≈ n/k points in the radius r(v) around v. Therefore, running the pre-processing step would make the number of remaining points ≈ k. In our experiments we set δ to be much smaller, and yet observe a great drop in our running times.
Algorithm 3 Sparsification + Fair-Round Input: Metric (X, d), radius function r : X → R+, parameter δ > 0
1: S, {D(u) : u ∈ S} ← Filter((X, d), δr) 2: (x′, y′)← solve LP only on points S with objective function ∑ v,u∈S d(v, u)
pxvu|D(v)| 3: x∗vw ← x′uw∀v, w ∈ X,u ∈ S : v ∈ D(u) ▷ v’s assignment is identical to its representative u 4: y∗u ← y′u if u ∈ S and 0 otherwise
Output: Fair-Round((X, d), (1 + δ)r, (x∗, y∗))
Lemma 5. Algorithm 3 outputs an (8(1 + δ), 21+2/p(1 + (δϕ)p)1/p)-approximation where ϕ = ( ∑
v∈X r(v) p)1/p/opt.
Proof. Observe that (x∗, y∗) is not a feasible LP solution anymore. Nevertheless, it will be feasible for when r is dilated by a factor of (1 + δ) in the LP4. Here is how we argue LP4 holds in this case: For any v, w ∈ X for which x∗vw > 0, recall u ∈ S is chosen so v ∈ D(u) and x∗vw := x′uw > 0 meaning d(u,w) ≤ r(u). We have d(v, w) ≤ d(v, u)+d(u,w) ≤ δr(v)+ r(u) ≤ (1+ δ)r(v). The last two inequalities are by Fact 2 as d(v, u) ≤ δr(v) and r(u) ≤ r(v). As for the LP cost of (x∗, y∗),
it is not longer upper-bounded by optp but rather by optp + ∑ u∈S ∑ v∈D(u) d(v, u) p. This additive
term is at most ∑
v∈X(δr(v)) p ≤ (δϕopt)p. Plugging this into Lemma 4 finishes the proof.

heading: 4 Experiments

text:
Summary. We run experiments to show that the empirical performance of our algorithms can be much superior to the worst-case guarantees claimed by our theorems (the codes are publicly availably on Github3). While implementing our algorithm, we make the following optimization : instead of choosing the constant “2” in Line 2 (definition of R) in our algorithm, we perform a binary-search to determine a better constant. Specifically, we find the smallest β for which Algorithm 1 gives at most k centers with R(v) := min{r(v), (βCv)1/p} for all v. This step is motivated by the experiments in [25].
We assess the performance with respect to (a) fairness, (b) objective value, and (c) running times. Due to space restrictions, we focus on the k-MEANS objective and leave k-MEDIAN results to Appendix B. Our fairness violation seldom exceeds 1.3 (compare this to the theoretical bound of 8), and often is much better than that of [29] and [25]. The objective value of our solution is in fact extremely close to the LP solution, which is a lower bound on the optimum cost (compare this to the theoretical bound of 4). This occurs because typically the LP solution itself has many integer entries. Finally, although the “vanilla” running time of the LP is pretty large, our sparsification routine Lemma 5 tremendously reduces the running time.
Datasets. Similar to [29], we use 3 datasets from the UCI repository4 [16] (also used in previous fair clustsering works of [14, 6]). We use a set of numeric features (matching previous work) to represent data in Euclidean metric. 1- bank [35] with 4,521 points, on data collected by the marketing campaign of a Portuguese banking institution. We use 3 features “age”, “balance”, and “duration”. 2- census [28] with 32,561 points, based on the 1994 US census. Here we use the following 5 features: “age” , “final-weight”, “education-num”, “capital-gain”, and “hours-per-week”. 3- diabetes [34] with 101,766 points, from diabetes patient records from 130 hospitals across US.
Benchmarks. We compare with the algorithms of [29] and [25]. For [29], we set parameters according to the experimental section of their paper. We remark that in their experimental section they perform 1 swap in their local search instead of the 4-swaps for which they prove their theorem. For our running time comparison, we also compare ours and the above two algorithm’s running times with the popular k-Means++ algorithm of [4] from scikit learn toolkit [31] which has no fairness guarantees.

heading: 4.1 Fairness analysis

text:
For any solution T ⊆ X , define the “violation array” θT over v ∈ X as θT (v) = d(v, T )/r(v). This provides a more fine-grained view of the per-client fairness guarantee violation. Similar to [29] we use maximum violation (i.e. maxv∈X θT (v)) as a benchmark for fairness. In Figure 1 we have plotted the maximum violation of our algorithm Fair-Round, [29] (noted as MV), and [25] (noted as JKL). We find that our results are noticeably fairer than [29] while improving over [25] in many cases.
Next, we compare the histograms of the violation vectors θ as described above. This picture provides a better view of the fairness profile, as just looking at the maximum violation may not be a robust measure; an algorithm that is largely unfair may be preferred to an algorithm that is extremely unfair on a single point but extremely fair on all the rest. We show the histograms of the violation vectors of these algorithms in Figure 2 (for a full set of histograms see Appendix A.1). As an example, even though in bank with k = 20 our maximum violation is slightly worse than [25] our histogram shows that we are slightly fairer overall. We observe that our algorithm ensures complete fairness for at least %80 of the points in almost all the experiments. A theoretical study of the violation vector is interesting and left as future work.
3https://github.com/moonin12/individually-fair-k-clustering 4https://archive.ics.uci.edu/ml/datasets/

heading: 4.2 Cost analysis

text:
In Figure 3 we demonstrate that in our experiments, the objective value almost matches the optimal cost, begin at most %1 more almost always, and never above %15 more than the LP cost. Note that our cost is also higher than that of [29], and the reader may be wondering how the latter can be better than the optimum cost. The reason is that the [29] cost is violating the fairness constraint while the optimal cost is not. To do a more apples-to-apples comparison, one can also allow the same violations as [29] and re-solve the linear program and also our rounding algorithms. On doing so, we do find that our algorithm’s cost becomes lower than that of [29]. Details of this can be found in Appendix A.2. The set-up also allows us to measure the cost of fairness: how much does the linear programming cost and our algorithm’s cost decrease as we relax the fairness constraints. We do this empirical study; see Appendix A.3 for our results.
Runtime analysis. We run our experiments in Python 3.8.2 on a MacBook Pro with 2.3 GHz 8-Core Intel Corei9 processor and 32 GB of DDR4 memory. We solve our linear programs using the Python API for CPLEX [22]. We demonstrate that even though solving an LP on the entire instance is time consuming, our sparsification step tremendously improves on the runtime (Figure 4) while increasing the clustering cost or fairness performance by a only a negligible margin (see Appendix A.4 for the cost and fairness results). Below, the blue line with circles shows Fair-Round with “vanilla” LP
solver, and the green line with upside-down triangles Sparse-Fair-Round is the runtimes with the sparse LP solution.

title: Better Algorithms for Individually Fair k-Clustering


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.

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

summaries: 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)$.

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

abstractText: 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.

authors:
K. Ahn
G. Cormode
S. Guha
A. McGregor
A. Wirth

title: Correlation clustering in data streams

venue: International Conference on Machine Learning, pages 2237–2246. PMLR,

authors:
K.J. Ahn
S. Guha

title: Graph sparsification in the semi-streaming model

venue: International Colloquium on Automata, Languages, and Programming, pages 328–338. Springer,

authors:
N. Ailon
R. Jaiswal
C. Monteleoni

title: Streaming k-means approximation

venue: Proceddings of the Twenty-Third Annual Conference on Neural Information Processing Systems, volume 4, page 2,

authors:
S. Arora
S. Rao
U. Vazirani

title: Expander flows, geometric embeddings and graph partitioning

venue: Journal of the ACM (JACM), 56(2):1–37,

authors:
P. Awasthi
A.S. Bandeira
M. Charikar
R. Krishnaswamy
S. Villar
R. Ward

title: Relax, no need to round: Integrality of clustering formulations

venue: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 191–200,

authors:
N. Bansal
A. Blum
S. Chawla

title: Correlation clustering

venue: Machine Learning, 56(1-3):89–113,

authors:
R. Borndörfer
A. Eisenblätter
M. Grötschel
A. Martin

title: Frequency assignment in cellular phone networks

venue: Annals of Operations Research, 76:73–93,

authors:
N. Boumal
V. Voroninski
A. Bandeira

title: The non-convex Burer-Monteiro approach works on smooth semidefinite programs

venue: Advances in Neural Information Processing Systems, pages 2757–2765,

authors:
S. Burer
R.D. Monteiro

title: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

authors:
M. Charikar
V. Guruswami
A. Wirth

title: Clustering with qualitative information

venue: Journal of Computer and System Sciences, 71(3):360–383,

authors:
L. Ding
A. Yurtsever
V. Cevher
J.A. Tropp
M. Udell

title: An optimal-storage approach to semidefinite programming using approximate complementarity

venue: arXiv preprint arXiv:1902.03373,

authors:
A. Eisenblätter
M. Grötschel
A. Koster

title: Frequency planning and ramifications of coloring

venue: Discussiones Mathematicae Graph Theory, 22(1):51–88,

authors:
T.A. Feo
M.G. Resende

title: Greedy randomized adaptive search procedures

venue: Journal of Global Optimization, 6(2):109–133,

authors:
A. Frieze
M. Jerrum

title: Improved approximation algorithms for MAX-K-CUT and max bisection

venue: Algorithmica, 18(1):67–81,

authors:
W.-S. Fung
R. Hariharan
N.J. Harvey
D. Panigrahi

title: A general framework for graph sparsification

venue: SIAM Journal on Scientific Computing, 48(4):1196–1223,

authors:
D.R. Gaur
R. Krishnamurti
R. Kohli

title: The capacitated MAX-K-CUT problem

venue: Mathematical Programming, 115(1):65–72,

authors:
B. Ghaddar
M.F. Anjos
F. Liers

title: A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem

venue: Annals of Operations Research, 188(1):155–174,

title: Revisiting Frank-Wolfe: Projection-free sparse convex optimization

venue: Proceedings of the 30th International Conference on Machine Learning, pages 427–435,

authors:
M. Journée
F. Bach
P.-A. Absil
R. Sepulchre

title: Low-rank optimization on the cone of positive semidefinite matrices

venue: SIAM Journal on Optimization, 20(5):2327–2351,

authors:
V. Kann
S. Khanna
J. Lagergren
A. Panconesi

title: On the Hardness of Approximating MAX-K-CUT and Its Dual

venue: Citeseer,

authors:
D. Karger
R. Motwani
M. Sudan

title: Approximate graph coloring by semidefinite programming

venue: Journal of the ACM (JACM), 45(2):246–265,

authors:
R. Kyng
J. Pachocki
R. Peng
S. Sachdeva

title: A framework for analyzing resparsification algorithms

venue: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2032–2043. SIAM,

authors:
F. Ma
J.-K. Hao

title: A multiple search operator heuristic for the MAX-K-CUT problem

venue: Annals of Operations Research, 248(1-2):365–403,

authors:
R.M. McCutchen
S. Khuller

title: Streaming algorithms for k-center clustering with outliers and with anonymity

venue: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 165–178. Springer,

authors:
N. Mladenović
P. Hansen

title: Variable neighborhood search

venue: Computers & Operations Research, 24(11): 1097–1100,

title: Complex semidefinite programming and MAX-K-CUT

venue: arXiv preprint arXiv:1812.10770,

authors:
N. Shinde
V. Narayanan
J. Saunderson

title: Memory-efficient structured convex optimization via extreme point sampling

venue: SIAM Journal on Mathematics of Data Science, 3(3):787–814,

authors:
D.A. Spielman
S. Teng

title: Spectral sparsification of graphs

venue: SIAM Journal on Scientific Computing, 40 (4):981–1025,

authors:
A.P. Subramanian
H. Gupta
S.R. Das
J. Cao

title: Minimum interference channel assignment in multiradio wireless mesh networks

venue: IEEE Transactions on Mobile Computing, 7(12):1459–1473,

title: Correlation clustering: maximizing agreements via semidefinite programming

venue: SIAM Symposium on Discrete Algorithms, volume 4, pages 526–527. Citeseer,

authors:
J.A. Tropp
A. Yurtsever
M. Udell
V. Cevher

title: Streaming low-rank matrix approximation with an application to scientific simulation

venue: SIAM Journal on Scientific Computing, 41(4):A2430–A2463,

authors:
N. Veldt
D.F. Gleich
A. Wirth
J. Saunderson

title: Metric-constrained optimization for graph clustering algorithms

venue: SIAM Journal on Mathematics of Data Science, 1(2):333–355,

authors:
Y. Wang
L. Xu
Y. Chen
H. Wang

title: A scalable approach for general correlation clustering

venue: International Conference on Advanced Data Mining and Applications, pages 13–24. Springer,

title: Sketching as a tool for numerical linear algebra

venue: Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157,

title: GSET random graphs

authors:
A. Yurtsever
M. Udell
J.A. Tropp
V. Cevher

title: Sketchy decisions: Convex low-rank matrix optimization with optimal storage

venue: Artificial Intelligence and Statistics, pages 1188–1196,

authors:
A. Yurtsever
J.A. Tropp
O. Fercoq
M. Udell
V. Cevher

title: Scalable semidefinite programming

venue: SIAM Journal on Mathematics of Data Science, 3(1):171–200,

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.

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