Constant Approximation for Individual Preference Stable Clustering
Authors: Anders Aamand
Justin Y. Chen
Allen Liu
Sandeep Silwal
Pattara Sukprasert
Ali Vakilian
Fred Zhang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: clustering
fairness
approximation algorithms
TL;DR: We give a constant-factor approximation algorithm for individual preference (IP) stability clustering.

Abstract: Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance of every data point to its own cluster is at most $\alpha$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always exists, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering.  We also introduce generalizations of IP stability beyond average distance and give efficient near optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

Constant Approximation for Individual Preference Stable Clustering
Anders Aamand MIT
Justin Chen MIT justc@mit edu
Allen Li MIT
Sandeep Silwal MIT silwal@mit edu
aamand@mit..o edu
cliu5680mit.c edu
Pattara Sukprasert
Ali Vakilian
Fred Zhang UC Berkeley z0@berkeley edu
Databricks
TTIC vakilianSttic.ed
pat. wtt..uukkraserrttttaaiiic.c com
Abstract
Individual preference (IP) stability, introduced by Ahmadi et al. (ICMI 2022), is natural clustering objective inspired by stability and fairness constraints. A clustering is a-IP stable if the average distance of every data point to its own cluster most times the average distance any other cluster. Unfortunately, determining if a dataset admits a 1-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if o stable clustering always exists, as the prior state of the art only guaranteed an (I1)-IP stable clustering. We close this gap understanding and show that an (1) stable clustering always exists for general metries, and we give efficient algorithm which outputs such clustering. We also introduce generalizations of IP stability beyond average distance and give efficient near optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.
Introduction
In applications involving and affecting people, socioeconomic concepts such as game theory, stability, and fairesss are important considerations in algorithm design. Within this context, Ahmadi al. [I] (ICML 2022) introduced the notion of individual preference stability (IP stability) for clustering. At a high-level, a clustering of an input dataset is called 1-IP stable if, for each individual point, its average distance to any other cluster is larger than the average distance to its own cluster. Intuitively, each individual prefers its own cluster to any other, and so the clustering is stable.
There are plenty of applications of clustering which the utility of each individual in any cluster is determined according to the other individuals who belong to the same cluster. For example, in designing personalized medicine, the more similar the individuals in each cluster are, the more effective medical decisions, interventions, and treatments can be made for each group of patients. Similarly, stability guarantees are desired in designing personalized learning environments or market- ing campaigns to ensure that no individual wants to deviate from their assigned cluster. Furthermore the focus on individual utility in IP stability (a clustering is only stable if every individual is "happy") enforces notion of individual fairness in clustering.
In addition to natural connections cluster stability, algorithmic fairness, and Nash equilibria, IP stability is also algorithmically interesting in its own right. While clustering is well-studied with respect to global objective functions (e.g. the objectives of centroid-based clustering such as k-means
Significant part of the work was done while P.S. was Ph.D. candidate at Northwestern University.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

or correlation/hierarciiaal clustering), less is known when the goal is to partition the dataset such that every point in the dataset is individually satisfied with the solution. Thus, IP stability also serves as natural and motivated model of individual preferences in clustering.
1.1 Problem Statement and Preliminaries
The main objective of our clustering algorithms is to achieve IP stability given a set P n points lying in metric space (M, d) and k, the number of clusters.
Definition 1.1 (Individual Preference (IP) Stability (T). The goal is to find disjoint k-clustering C= (CI,... ................................ C&) of P such that every point, on average, is closer to the points of its own cluster than to the points in any other cluster. Formally, for all E P, let C(v) denote the cluster that contains u. We say that E P is IP stable with respect to if either C(v) = {u) or for every C' E C with C' + C.
Σ d(u, S
Σ d(c,u).
(I)
C(+)
|C'
wEC(v)
NEC"
The clustering is 1-IP stable (or simply IP stable) if and only if every v E stable with respect to C.
Ahmadi et al. [ showed that an arbitrary dataset may not admit an IP stable clustering. This can be the case even when n Furthermore, they proved that is NP-hard to decide whether given a set of points have an IP stable k-clustering, even for l = 2. This naturally motivates the study of the relaxations of stability.
Definition 1.2 (Approximate IP Stability). A k-clustering C = (C,,.... C₂)) of P a-approximate
IP stable, or simply a-IP stable, if for every point E P, the following holds: either C(v) = {v} or for every C' C and C' CC
Σ MEC(v)
d(v,u)
E(r,u). |C'
2)
((0)
DEC"
The work of 1 proposed algorithms to outputting IP stable clusterings on the one-dimensional line for any value of k and on tree metrics for k = The first result implies an (nn) stable clustering for general metrics, by applying standard (m)-ciisorriion embedding to one-dimensional Euclidean space. In addition, they give a bicriteria approximation that discards an e-fraction of the input points and outputs O
log"
IIP stable clustering for the remaining points.
Given the prior results, it natural to ask the (n) factor for IP stable clustering given in 1 can be improved.
1.2 Our Results
New Approximations. Improving on the ( -IP stable algorithm in [I], we present deterministic algorithm which for general metrics obtains an (L)-IIP stable k-clustering, for any value of k. Note that given the existence of instances without 1-IP stable clusterings, our approximation factor is optimal up a constant factor.
Theorem 1.3. (Informal; see Theorem 3.1 Given a set P of n points in a metric space (M, d) and number of desired clusters k < n, there exists an algorithm that computes an O(1)-IP stable k-clustering of in polynomial time.
Our algorithm outputs clustering with an even stronger guarantee that we call uniform (approximate) IP stability. Specifically, for some global parameter r and for every point v E P, the average distance from to points in its cluster is upper bounded by O(r) and the average distance from v to points in any other cluster is lower bounded by 2(r). Note that the general condition of O(1) stability would allow for different value of for each v.
We again emphasize that Theorem 1.3 implies that an O(1)-IP stable clustering always exists, where prior to this work, only the O(n) bound from [ was known for general metrics.

---

Additional k-center clustering guarantee. The clustering outputted by our algorithm satisfies additional desirable properties beyond ( stability. In the k-center problem. we are given n points in metric space, and our goal is to pick & centers as to minimize the maximal distance of any point to the nearest center. The clustering outputted by our algorithm from Theorem [.3 has the added benefit of being a constant factor approximation to the k-center problem in the sense that if the optimal k-center solution has value ro. then the diameter of each cluster outputted by the algorithm is (ro). In fact, we argue that IP stability is more meaningful when we also seek solution that optimizes some clustering objective. we only ask for IP stability, there are instances where is easy to obtain OII) stable clusterings, but where such clusterings do not provide insightful information in typical clustering application. Indeed, as we will show in Appendix B randomly k-collring the nodes of an unweighted, undirected graph (where the distance between two nodes is the number of VI
edges on the shortest path between them), gives an - stable clustering when k S 505
log
Our result on trees demonstrates the idiosyncrasies of individual objectives thus our work raises further interesting questions about studying standard global clustering objectives under the restriction that the solutions are also (approximately) IP stable.
Max and Min-IP Stability. Lastly, we introduce notion of f-IP stability, generalizing IP stability,
Definition 1.4 (f-IP Stability). Let (M, d) be a metric space, P a set of n points of M, and & the desired number of partitions. Let f P x 2 -> R220 be a function which takes in point v E P. subset C' of P, and outputs a non-negative real number. we say that a k-clustering C = (G1 ... Cc.) of P f-IP stable if for every point P. the following holds: either C(v) = {u} or for every C" E C and C" # C,
f (e, C(u) \ (v)) $(,,C)).
Note that the standard setting of IP stability given in Definition I.] corresponds to the case where f(, C*) = (1/|Cl) x> Evrc d(u, v'). The formulation of f-IP stability, therefore, extends IP stability beyond average distances and allows for alternative objectives that may be more desirable in certain settings. For instance, in hierarchical clustering, average, minimum, and maximum distance measures are well-studied.
In particular, we focus on max-distance and min-distance in the definition of f-IP stable clustering in addition to average distance (which is just Definition 1.1). where f(vv, C) = maxwec d(v, v') and (v, C)- ec d(u,, v²). We show that in both the max and min distance formulations, can solve the corresponding f-IP stable clustering (nearly) optimally in polynomial time. We provide the following result:
Theorem 1.5 (Informal;
Theorem 4.1 and Theorem 4.2p. In any metric space, Min-IP stable clustering can be solved optimally and Max-IP stable clustering can be solved approximately within factor 3, 3, in polynomial time.
We show that the standard greedy algorithm of k-center, a...,, the Gonzalez's 's algorithm [5], yields a 3- 3-approximate Max-IP stable clustering. Moreover, we present conceptually clean algorithm which is motivated by considering the minimum spanning tree (MST) to output Min-IP stable clustering. This implies that unlike the average distance formulation of IP stable clustering, Min-IP stable clustering always exists. Both algorithms work in general metrics.
Metric
Approximation Factor
Reference
Remark
ID Line metric Weighted tree
1
1
Only for k: = 2
General metric
O(n)
General metric
O(I)
This work
Table 1: Our results on IP stable k-clustering of n points. All algorithms run in polynomial time.
Empirical Evaluations. We experimentally evaluate our 0(1)-IP stable clustering algorithm
against k-means++, which is the empirically best-known algorithm in (. We also compare means++ with our optimal algorithm for Min-IP stability. We run experiments on the Adult data se
see [8]
3

---

used by [.. For IP stability. we also use four more datasets from UCI ML repositoriy [ and synthetic data set designed be a hard instance for k-meanst+. On the Adult data set, our algorithm performs slightly worse than k-means++ for IP stability. This is consistent with the empirical results of [. On the hard instance" our algorithm performs better than k-means+++, demonstrating that the algorithm proposed in this paper is more robust than k-means++. Furthermore for Min-lP stability, we empirically demonstrate that k-means++ can have an approximation factors which are up to factor of 5x worse than our algorithm. We refer to Section 5 and Appendix C for more details.
1.3 Technical Overview
The main contribution is our Dappaapproinntooon algorithm for IP stable clustering for general metrics. We discuss the proof technique used to obtain this result. Our algorithm comprises two steps. We first show that for any radius r, we can find a clustering C = (C1,-.., ,,,) such that (a) each cluster has diameter Or)), and (b) the average distance from point in cluster the points of any other cluster is S2(r).
Conditions (a) and (b) are achieved through ball carving technique, where we iteratively pick centers 9. of distance > 6r to previous centers such that the radius r ball (g: r) centered at q contains a maximal number of points, say st. For each of these balls, we initialize cluster D, containing the s; points of B(q,r) r). We next consider the annulus B Bgg, 3r) B(q,, 2r). If this annulus contains less than 8; points, we include all points from B(q; 3r) in D.. Otherwise, from the annulus. We assign each unassigned point to the first center picked by our algorithm and is within distance (r) to the point. This is a subtle but erucial component of the algorithm as the more natural "assign to the closest center" approach fails to obtain (I)- stability.
include any 8; points in D,
One issue remains. With this approach, we have guarantee on the number of clusters. We solve this by merging some of these clusters while still maintaining that the final clusters have radius O This may not be possible for any choice of r. Thus the second step is to find the right choice of r. We first run the greedy algorithm of k-center and let ro be the minimal distance between centers we can run the ball carving algorithm cluster of C to its nearest k-center, we do indeed maintain the property that all clusters have diameter O(r), and since is small enough constant, all the clusters will be non-empty. The final number of clusters will therefore k. As an added benefit of using the greedy algorithm for k-center as a subroutine, obtain that the diameter of each cluster is also Orro), namely the output clustering is a constant factor approximation to k-center.
cro for sufficiently small constant Then if assign each
be
1.4 Related Work
Fair Clustering. One of the main motivations of IP stable clustering is its interpretation as a notion of individual fairness for clustering []. Individual fairness was first introduced by [12] for the classification task, where, at high-level, the authors aim for a classifier that gives "similar predictions" for "similar" data points. Recently, other formulations of individual fairness have been studied for
2 7 8] too. [17] proposed a notion of fairness for centroid- based clustering: given set of points P and the number of clusters k for each point, center must be picked among its (n/k)-th closest neighbors. The optimization variant of it was later studied by 19 20 24] [7] studied pairwise notion of fairness in which data points represent people who gain some benefit from being clustered together. In a subsequent work, [6] introduced a stochastic variant of this notion. [2] studied
clustering 17
the setting in which the output is distribution over centers and "similar" points are required to have "similar" centers distributions.
Stability in Clustering. Designing efficient clustering algorithms under notions of stability is well-studied problem[" Among the various notion of stability, average stability is the most relevant to our model [4]. In particular, they showed that if there is ground-truth clustering satisfying the requirement of Equation (T) with an additive gap of > > 0, then it is possible to recover the solution in the list model where the list size is exponential in 1 1/7- Similar types of guarantees are shown in the work by [9] While this line of research mainly focuses on presenting faster algorithms utilizing the
'The construction of this hard instance is available in the appendix I For a comprehensive survey this topic, refer to B.
4

---

strong stability conditions, the focus of IP stable clustering is whether we can recover such stability properties in general instances, either exactly or approximately.
Hedonic Games. Another game-theoretic study of clustering is hedonic games [10
13 In
hedonic game, players choose to form coalitions (i.e., clusters) based on their utility. Our work differs from theirs, since we do not model the data points as selfish players. In a related work, 23 proposes another utility measure for hedonic clustering games on graphs. In particular, they define a closeness utility, where the utility of node i in cluster C' is the ratio between the number of nodes C' adjacent to and the sum of distances from i to other nodes in C. This measure is incomparable to IP stability, In addition, their work focuses only on clustering in graphs while we consider general metrics.
2 Preliminaries and Notations
We let (M, d) denote a metric space, where d is the underlying distance function. We let P denote a fixed set of points of M. Here P may contain multiple copies of the same point. For a given point x E P and radius r 2 O, we denote by B(x, r) = {y E P d(x, y) S r). the ball of radius r centered at z. For two subsets X, Y C P, we denote by d(X,Y) the paper, X and Y will always be finite and then the infimuum can be replaced by a minimum. For E P and S P. we simply write d(x, Y) for d((x), Y). Finally, for X C P. we denote by (Xam = x. d(z, y), the diameter of the set X. Again, X will always be finite, so the supremum can be replaced by maximum.
inl sex d(x.,)) Throughout
3 Constant-Factor IP Stable Clustering
In this section, we prove our main result: For a set P f#1.... InA of n points with a metric d and every A S n, there exists k-clustering C = (C1, ......... Ck) of P which is O1))aaprrxximae IP stable. Moreover, such a clustering can be found in time Ö where T is an upper bound on the time it takes to compute the distance between two points of P.
Algorithm Our algorithm uses a subroutine, Algorithm I which takes as input P and a radius E R and returns t-clustering D (D1... ...,...> D.) of P with the properties that (1) for any S i S t. the maximum distance between any two points of D; is (r), and (2) for any x E P and any such that D;, the average distance from x to points of D, 1(r). These two properties ensure that D is o(1)-approximate IP stable. However, we have no control on the number of clusters t that the algorithm produces. To remedy this, we first run a greedy k-center algorithm on P to obtain a set of centers {cI...., ) and let vn denote the maximum distance from a point of P to the nearest center. We then run Algorithm| with input radius r erp for some small constant e. This gives a clustering D (Di, Di) where & > k. Moreover, we show that if we assign each cluster of D to the nearest center in (ci..... } (in terms of the minimum distance from a point of the cluster to the center), we obtain k-clustering C' = (Ct...., C₂) which is 0 o())-approxe IP stable. The combined algorithm is Algorithm? 2
We now describe the details of Algorithm [ The algorithm takes as input n points æ1, ........2 In of a metric space (M, d) and a radius r. It first mitializes set Q and then iteratively adds points from P to Q that are of distance greater than 6r from points already in Q such that [B(r, r)), the number of points of P within radius r of x, is maximized. This is line 516 of the algorithm. Whenever point is added to Q, we define the annulus A, == B(g, 3r) B (i. 2r). We further let 8t = [[g;, r).. At this point the algorithm splits into two cases. If [.A.] 2 $4, we initialize a cluster D. which consists of the s; points in [xx, r) and any arbitrarily chosen s; points in A, This is line of the algorithm. If on the other hand [A: < 5, we define D; := B(g. 3r), namely D, contains all points of P within distance 3r from 9;- This is line of the algorithm. After iteratively picking the points qi and initializing the clusters D,. we assign the remaining points as follows. For any point U, Dr, we find the minimum i such that d(z, qb) 7r and assign to D,. This is line 13 16 of the algorithm. We finally return the clustering D = (D,....,
We next describe the details of Algorithm 2 The algorithm iteratively pick & centers .I,..., Ck from P. for each center maximizing the minimum distance to previously chosen centers. For each center Ca initializes cluster, starting with C.- {c... This is line 7 of the algorithm. Letting ro be
5

---

Algorithm BALL-CARVING
1: Input: A set P f=...... Fn of n points with a metric and radius r > 0.
2: Output: Clustering D 1 ( Dτ) of
3: Q 0
4: while there exists x E with d(xr, Q) > 6r do
5: qi + arg. [B(rr))
6:
Q - (4)), - B(q. r),, A, B(q;, B(q.. 2r)
7:
if 2 81
8:
S; + any set of 8, points from A, D; + r)
9:
else D; 3r:)
11:
i i-++1 i+1
end while
13:
for x E P assigned to no D; do
j + d(x, q:) 7r)
15:
D,+D,U
end for
17: t [Q]
return (D....., D.)
Algorithm IP- PP-CLUSTERING
1: Input: Set P fai...... nn of n points with a metric d and integer with S S n.
2: Output: k-clustering C (CI.... Ck) of P.
3: S+0
4: for f do
5:
c f ara max p (d(r, 5)}
6: Su)U C₁ + (G)
7: end for
8: ro min(d(e,, 94) 1 b
9: D + BALL-CCRVVNNG(P, /
for DE Do
11: aig (d(c, D)}
C₁ C,+
13: end for
return C= (CI,...,Ck)
the minimum distance between pairs of distinct centers, the algorithm runs Algorithm on P with input radius 7 = To/ 15 (line g This produces a clustering D. In the final step. we iterate over the clusters D of D. assigning to the C for which d(e,, D) is minimized (line 11 13 We finally return the clustering (CI..... C.).
Analysis We now analyze our algorithm and provide its main guarantees.
Theorem 3.1. Algorithm 2 returns an (a)aaapprx IP stable clustering in time O(n² + n² log n). Furthermore, the solution also constant factor approximation the k-center problem.
In order to prove this theorem, we require the following lemma on Algorithm 1
Lemma 3.2. Let (DI...., Dr) be the clustering output by Algorithm 7. For each E [t], the diameter of D, is at most 14r. Further, for x E D; and + the average distance from to points of D is at least 4.
Given Lemma we can prove the the main result.
Proof of Theurem 3.7 We first argue correctness. each e; was chosen to maximize the minimal distance to points Cy already in S, for any E P. it holds that min(d(xr,c) By Lemma 3.2 in the clustering 'D output by BALL-CARVING(PP ro/15) each cluster has diameter at 14
E [b]] S ro-
most 15 ro < To. and thus, for each i [k], the cluster D D which contains c, will be included in

---

C in the final clustering, Indeed. in line 11 of Algorithm 2 d(c;, D) = 0 whereas d(cy, D) 2 1 for all j o Thus, each cluster in (Ci..... Cx.) non-empty. Secondly, the diameter of each cluster is at most 4ro. namely, for each two points 2 x E C,, they are both within distance To + IG ro < 2ro of cs. Finally, by Lemma 3.2 for x E D and j * i, the average distance from x to points of D3 is at least za. Since, C is a coarsening of DD i.e., each cluster of C is the disjoint union of some of the clusters in D, it is straightforward to check that the same property holds for the clustering C. Thus is (apaapproxee IP stable.
15 no
14
3.2
We now analyze the running time. We claim that Algorithm can be implemented to run in O + n² log n) time, where T is the time to compute the distance between any two points in the metric space. First, we can query all pairs to form the x n distance matrix A. Then we sort along every row to form the matrix A'. Given A and A', we easily implement our algorithms as follows.
First, we argue about the greedy k-center steps of Algorithm 2, namely, the for loop on line 4 The most straightforward implementation computes the distance from every point to new chosen centers. At the end, we have computed at most nk distances from points to centers which can be looked up in A in time (nk) = (nn²) as k S n. In line 8 the total time is also (n ). The same reasoning also holds for the for loop on line 10 It remains to analyze the runtime.
we only look at every entry of A at most once so
Given r, Alg. cann be implemented as follows. First. calculate the size of B(x, r'] for every point x in our dataset. This can easily be done by binary searching on the value of r along each of the (sorted) rows of A', which takes O(n log n) time in total. We can similarly calculate the sizes of [B(r, 2r]] and (xx,33)) 3. and thus the number of points in the annulus [Br, (r)) [r., 2r) in the same time initialize the clusters D;- Similar to the k-center reasoning above, we can also pick the centers in Algorithm D which are > 6r apart iteratively by just calculating the distances from points to the chosen centers so far. This costs at most Onn") time, since there are at most n centers. After initializing the clusters D;, we finally need to assign the remaining unassigned points (line [3][]] This can easily be done in time (n)) per point, namely for each unassigned point x. we calculate its distance to each ds assigning it to D, where i is minimal such that d(zz, 9:) S 7r. The total time for this is then O(n²). ). The k-center guarantees follow from our choice of ro and Lemma 3.2
Remark 3.3. We note that the runtime can possibly be improved if we assume special structure about the metric space (e.g., Euclidean metric). See Appendix A for discussion.
We now prove Lemma 3.2
Proof of Lemma 3.2 The upper bound on the diameter of each cluster follows from the fact that for any cluster D; in the final clustering D = (Di....,Dy and any x E D,, it holds that d(x, q)) S 7 The main challenge is to prove the lower bound on the average distance from x E D, to Dj where j # i.
jnd Suppose for contradiction that, there exists i with i * and x E D, such that the average distance
from x to D2 is smaller than r/4, i.c. D.JT Eyen, d(z,y) v) < r/4. Then, it in particular holds that [B(r, r/2) n DyI >> >DDyl/2, namely the ball of radius r/2 centered at x contains more than half the points of Dy. We split the analysis into two cases corresponding to the if-else statements in line I0 of the algorithm.
Case 1: | 8yt In this case, cluster Dj consists of at least 2s, points, namely the 8j points in B(g;.r) and the set Sj of 8j points in A; assigned D, in line 8 of the algorithm. It follows from the preeeding paragraph that, [xx 22) n DyI > 8y. Now, when Z was added to Q, it was chosen as to maximize the number of points B(q,, r) under the constraint that qj had distance greater than 6r to previously chosen points of Q. Since [B(2,) r) > [B(z, r r/2) > [[gg, r)]. at the point where q was chosen, Q already contained some point 9jo (with jo < 9) of distance at most 6r to x and thus of distance at most 7 to any point of r/2). It follows that B(x, r/2) n Dj contains no point assigned during line 13 1f the algorithm. Indeed, by the assignment rule, such a point y would have been assigned to either D,, or potentially an even earlier initialized cluster of distance at most 7r to y. Thus, Bax,r/2) n D, is contained in the set B(g,,r) US However, [B(g, r) = |S = 83 and moreover, for (y1, 12) E r( x Sj. it holds that d(yn, v2) > In particular, no ball of radius r/2 can contain more than 8, points of B(g,,) r) U Sj. As B(x, r r/2) 0 D, > 83, this is a contradiction.
7

---

Case 2: |Ayl < sy: In this case. D, includes all points in B(g,. 3r). As x' & Dj, we must have that $ Bigj. 3r) and in particular. the ball (x, r/2) does not intersect B(g;. r). Thus,
1,1 2 r2x D,1 + Big r) n D2I> 12 8j.
so 12y1 > 28j. and finally, [B(r, r /2) n D IDj1/2 8j. Similarly to case 1, B(r, r
contains no points assigned during line E 16 of the algorithm. Moreover, r(x,r/2 B(gj, 3r) S Ay. In particular, rfr,,/22nn)) _ S contradiction as [Sy] = but /2) 83- E
4 Min and Max-IP Stable Clustering
The Min-IP stable clustering aims to ensure that for any point z, the minimum distance to a point in the cluster of is at most the minimum distance point in any other cluster. We show that Min-IP stable k-clustering always exists for any value of E [n] and moreover, can be found by a simple algorithm (Algorithm 3)
Algorithm 3 MIN-IP-CLLSTERIING
Input: Pointset P {z1..... In from metric space (M, d) and integer with n.
2: Output: k-clustering C = (C1. Ck) of P.
3: L + (1i, sorted according to d(r,, 23y
4: E E+8
5: while
E) has i connected components do 6: e an edge (z, y) in L with d(æ; y) minimal.
7: L L
8: i connects different connected components of G' then E EU
9: end while
10: return the connected components (CI,...,Cy)) G.
The algorithm is identical to Kruskal's 's algorithm for finding a minimum spanning tree except that it stops as soon as it has constructed forest with k connected components. First, it initializes graph G = (V, F)) with pairs of points (x,, 22y) of P and sorts the pairs (I4, xyy) according to these distances. Finally, it goes through this sorted list adding each edge (z,, xz)) to if connects different connected components of G. After computing the distances, it is well known that this algorithm can be made to run in time On² log n),, so the total running time is O(n? (T + log n)) where is the time to compute the distance between a single pair of points.
and F. 0. Next, computes all distances d(x,,, T.y) between
Theorem 4.1. The k-clustering output by Algorithm
3 is a Min-IP stable clustering.
Proof. Let C be the clustering output by the algorithm. Conditions (1) and (2) in the definition of a min-stable clustering
trivially satisfied. To prove that (3) holds, let C e C with |C| 2 2 and C. Let yo * x be a point in such that (z, yo) E E' (such an edge exists because C is the connected component of G containing x) and let yı be the closest point to in P C. When the algorithm added (x, Mo) to E, (I, was also candidate choice of an edge between connected components of G. Since the algorithm chose the edge of minimal length with this property, d(x, vo) d(x; y1). Thus, we get the desired bound:
min d(x,y) v) S d(x, Mo) S d(x, vn) min d(x, v)- (EC)(a)
vEriC
Theorem 4.2. The solution output by the greedy algorithm of k-center a 3-approximate Max-IP stable clustering.
Proof. To recall, the greedy algorithm of k-center (aka Gonzalez algorithm 15] starts with an arbitrary point as the first center and then goes through k - iterations. In each iteration, it picks new point as a center which is furthest from all previously picked centers. Let c..... Ck denote the selected centers and let == max.ep d(v, {ci,... C& )). Then, each point is assigned to the cluster of closest center. We denote the constructed clusters as Ci.... Ck. Now, for every + j E and each point C,, consider two cases:

---

d(v,G) r//
max d(v,u,) S d(e, (( d(u,, 53r2 wicC
max d(v,u,) 2 d(v,c)) 2 d(c 9j) (). (2.442211 21/2 uyeC;
d(v,4) r//
max d(e, u)) S d(v, () d(u, c,) s 3d(v,c), ,cCC
max d(v,u,) d(v, cj) d(u, a). WyECy
In both cases, ma, d(v,u)) S 3 max d(v, uy),
5 Experiments
While the goal and the main contributions of paper mainly theoretical, also implement optimal Min-IP clustering algorithm as well as extend the experimental results for IP stable clustering given in [T] Our experiments demonstrate that our optimal Min-IP stable clustering algorithm is superior to k-means++, the strongest baseline in []], and show that our IP clustering algorithm for average distances is practical on real world datasets and competitive to k-means++ (which fails to find good stable clusterings in the worst case [[]. We give our experimental results for Min-IP stability and defer the rest of the empirical evaluations to Section C All experiments were performed in Python 3. The results shown below are an average of 10 runs for k-means++.
Metrics We measure the quality of clustering using the same metrics used in ①I for standard- ization. Considering the question of f-IP stability (Definition) 1.4), let the violation of point æ be defined as Vi(x) (C(x, [(2.C(x))
f(2.6))
For example, setting [xx; =) d(x.v)/ and fzz C) mingec d(x,, y) the Min-IP formulation. Note point x stable iff Vi(x) S
corresponds to the standard IP stability objective
We measure the extent to which a k-clustering C = (CI,..., Cx) of is (un-)stable by comput- ing MaxVi maxzep Vi(x) (i.e. maximum violation) and Mean = Exer Vi(x)/\PI (mean violation).
Results For Min-IP stability, have optimal algorithm; it always return stable clustering for all k. We see Figures I that for the max and mean violation metrics, our algorithm outperforms k k-means++ by up to a factor of 5x, consistently across various values of k. k-means much worse clustering under Min-IP stability on real data, motivating the use of our theoretically- optimal algorithm in practice.
return
Adult data set
Adult data set
0.5
*
MaxVi
4
*
Our Alg
MeanVi
0.4
Our Alg
k-means++
0.3
k-means
0.2
0.1
20
60
80
100
20
40
60
80
100
k
k
Figure Maximum and mean violation for Min-IP stability for the Adult dataset, as used in [I] lower values are better.

---

Conclusion
We presented deterministic polynomial time algorithm which provides an -aprooopoo IP stable clustering of points in a general metric space, improving prior works which only guaranteed an aaprroxiie
stable clustering. We also generalized stability to f-stability and provided an algorithm which finds exact Min-IP stable clustering and a 3-approximation for Max-IP stability, both of which hold for all and in general metric spaces.
Acknowledgements
Anders Aamand supported by DFF-International Postdoc Grant 0164-00022B from the Independent Research Fund Denmark and a Simons Investigator Award. Justin Chen and Allen Liu are supported in part by an NSF Graduate Research Fellowship under Grant No. 174530. Allen Liu is supported in part by a Hertz Fellowship. Fred Zhang is supported by ONR grant N00014-18-1-2562
References
[1] Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pat- tara Sukprasert, and Ali Vakilian. Individual preference stability for clustering. In International Conference on Machine Learning (ICML), 2022.
[2] Nihesh Anderson, Suman K Bera, Syamantak Das, and Yang Liu. Distributional individual fairness in clustering, arXiv preprint arXiv:2006. 12589, 2020.
[3] Awasthi and M.-F. Balcan. Center based clustering: A foundational perspective. In Handbook of Cluster Analysis. CRC Press, 2014.
[4] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. A discriminative framework for clustering via similarity functions. In Symposium on Theory of computing (STOC), pages 671 671-680, 2008.
[5] Anna Bogomolnaia and Matthew O Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201-230, 2002.
[6] B Brubach, D Chakrabarti, J Dickerson, A Srinivasan, and L Tsepenekas. Fairness, semi- supervised learning, and more: general framework for clustering with stochastic pairwise constraints. In AAAI Conference Artificial Intelligence (AAAI), 2021.
[7] Brian Brubach, Darshan Chakrabarti, John Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas. A pairwise fair and community-preservin approach to k-center clustering. In International Conference on Machine Learning (ICML), pages 1178-1189, 2020.
[8] Darshan Chakrabarti, John P Dickerson, Seyed A Esmaeili, Aravind Srinivasan, and Leonidas Tsepenekas. A new notion of individually fair clustering: a-equitable k-center. International Conference Artificial Intelligence and Statistics, pages 6387-6408. PMLR, 2022.
[9] Amit Daniely, Nati Linial, and Michael Saks. Clustering is difficult only when does not matter. arXiv preprint arXiv: 220.. 2012.
[10] Jacques Dreze and Joseph Greenberg. Hedonic coalitions: Optimality and stability. Econo- metrica: Journal of the Econometric Society, pages 987-1003, 1980.
[11] D. Dua and C. Graff. UCI machine learning repository, 2019. Adult data set avail- able on https://archiwe ics wci. http:u.lldd/mm//atttttts/aaaaaaa sin data set available on httpaatss//t/tiea.eeeeeee ics. httpii/cc//ll/aaaattt/eeeeeesee wisconsin+ (diagnostic))) Car Evaluation data set available on https://archive on fit..ee..cca/a///aaatttaaaaaaaar Drug Consumption data set available Indian Liver Patient data set ow http:
Breast Cancer Wiscon-
ics. icssuuiieed
uci htt.://www....a........a.aaaaaaa (quaaatiiiiiitnaagiiaaiiiielllll ics. www. edw.ml/datasstts//
ILPD+ (atoommmiiiiiiieeeaaaaaaetttttee
10

---

[12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science (ITCS), pages 214-226, 2012.
[13] Edith Elkind, Angelo Fanelli, and Michele Flammini. Price of pareto optimality in hedonic games. Artificial Intelligence, 288: 103357, 2020.
[14] E. Fehrman, A. K. Muhammad, E. M. Mirkes, V. Egan, and A. N. Gorban. The five factor model of personality and evaluation of drug consumption risk, 2017.
[15] Teofilo Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
[16] Piotr Indyk and Sandeep Silwal. Faster linear algebra for distance matrices, In Neural Informa- tion Processing Systems (NeurIPS), 2022.
[17] C. Jung, S. Kannan, and N. Lutz. center in your neighborhood: Fairness facility location.
In Symposium on Foundations Responsible Computing (FORC), 2020.
[18] Ron Kohavi al. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 202-207, 1996.
[19] S. Mahabadi and A. Vakilian. Individual fairness for k-clustering, In International Conference on Machine Learning (ICML), 2020.
[20] Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k- clustering. Advances in Neural Information Processing Systems (NeurIPS), 34:13340-13351, 2021.
[21] Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 201
[22] Jack Snoeyink. Point location. In Jacob E. Goodman and Joseph O' O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition, pages 767-785. Chapman and Hall/CRC, 2004.
[23] Ana-Andreea Stoica and Christos Papadimitriou. Strategic clustering. 2018.
[24] A. Vakilian and M. Yalciner. Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.

---

A Discussion on the Runtime of Algorithm 2
We remark that the runtime of our -appoxxxox IP-stable clustering algorithm can potentially be improved if assume special structure about the metric space, such tree Euclidean metric. In special cases, we can improve the running time by appealing to particular properties of the metric which allow tree metrics, all distances can be calculated in Onn") time, even though T = (n)) Likewise for the Fuclidean case, we can utilize specialized algorithms for computing the all pairs distance matrix, which obtain speedups over the naive methods [16]. or use geometric point location data structures to quickly compute quantities such (Brr,)) r)]
either calculate distances implement our subroutines faster. For example for
12 Our presentation is optimized for simplicity and
generality so detailed discussions of specific metric spaces are beyond the scope of the work.
B Random Clustering in Unweighted Graphs
In this appendix, we show that for unweigthed, undirected, graphs (where the distance d(u, v) between two vertices u and is the length of the shortest path between them), randomly k-coloring the nodes gives an (11) approximaeeee IP-stable clustering whenever k O(n' 1/2 logn).
We start with the following lemma.
Lemma B.1. Let 7 = 0(1 be constant. There exists a constant e. > 0 (depending on 7)) such that the following holds: Let T (V, E) be an unweighted tree on nodes rooted at vertex r. Suppose that we randomly k-color the nodes of T. Let V; S V be the nodes of color i, let yn X, =vevv d(r, v). and let X = = d(r,v). If k S Cloga then with probability 1 - Onn7), holds that X/2 S IX, S 2X for all E [k]].
Proof. We will fix i, and prove that the bound X/2 S X; S 2X holds with probability 1 1-O(n 1 Union bounding over all then gives the desired result. Let = max,ev d(r, v) be the maximum distance from the root to any vertex of the tree. We may assume that A > 5 as otherwise the result follows directly from simple Chernoff bound. Since the tree is unweighted and there exists node of distance A to r, there must also exist nodes of distances 1, 2..... A to namely the nodes the path from r to v. For the remaining nodes, we know that the distance is at least 1. Therefore,
(
A 3
d(r,o) (n- A- 1)+ jj=n
12
DEV
and 14; [[X,] > n+ Since the variables (d(r, u)(u E Vil),ey sum to X, and are indepen- dent and bounded by A, follows by a Chernoff bound that for any 0 < < 1,
82pu
Pr| mal 8pss] S 2exp
3A
By the AM-GM inequality,
#4
A
2 2/n
+
A
3k
Putting 6 = 1/22, the bound above thus becomes
Pr[[X: mil
Pi
2 exp
n
3
6v33/
/n
<
exp
S 2n nh.
11k
where the last bound uses the assumption on the magnitude of k the lemma. Choosing c I1(++1) the desired result follows.
Next, we state our result on the approoipt IP-stability for randomly colored graphs.
12

---

Theorem B.2. Let 0(1) and k S Toga for a sufficiently small constant c. Lei G (V, B) be an unweighted, undirected graph n nodes, and suppose that k-color the vertices of G randomly. Let V; denote the nodes of color i. With probability at least 1 - n= .V....., for. forms an O(1) approximate IP-clustering.
//
Proof. Consider a node u and let X; = E d(u, v). Node that the distances duu, v) are exactly the distances in breath first search tree rooted at v. Thus, by Lemma B.1 the X;'s are all
within a constant factor of each other with probability 1 10000nn--00 Moreover, a simple Chernoff
bound shows that with the same high probability, [V]
- + O
log
θ ( for all [k].
In particular, the values Y = | for i E [k] also all lie within a constant factor of each other which implies that is -ttaabbe in the clustering (V....,, Vi.,. we find that with probability
Union bounding over all nodes
(Vi...., V&) is an 0(1) -appapproee IP-clustering. C
Remark B.3. The assumed upper bound on l in Theorem B.2 is necessary (even in terms of log n). Indeed, consider tree I" which is star S on - k log k vertices along with a path / of length & log k having one endpoint at the center v of the star. With probability ((1), some color does not appear on P. We refer to this color as color 1. Now consider the color of the star center. With probability at least 9/10, say, this color is different from 1 and appears 22log k) times on P with average distance (2k log k) to the star center c. Let the star center have color 2. With high probability, each color appears (nz/k) times in S. Combining these bounds, we find that with constant probability, the average distance from vertices of color is O(1), whereas the average distance from vertices
of color 2 is Ω (log)))) In particular for the algorithm to give an ((1))apprxximae IP-stable
clustering, need assume that le O
V
log 12
C Additional Empirical Evaluations
We implement our (ppoxxpproinnation algorithm for IP-clustering. These experiments extend those of [ and confirm their experimental findings: k-means++ is a strong baseline for IP-stable clustering. Nevertheless, our algorithm is competitive with it while guaranteeing robustness against worst-case datasets, a property which m-means++ does not posses.
Our datasets are the following. There are three datasets from 11 used in M. namely. Adult, Drug [4], and Indi anLiver. We also add two additional datasets from UCI Machine Learning Repository [11), namely, BreastCancer and Car. For IP-clustering, also consider a synthetic dataset which is the hard instance for k-means++ given 1.
Our goal is to show that our IP-clustering algorithm is practical and in real world datasets, is competitive with respect to k-means++, which was the best algorithm in the experiments in [T. Furthermore, our algorithm is robust and outperform k-means++ for worst case datasets.
As before, all experiments were performed in Python We use the k-means++ implementation of Scikit-learn package [21]. We note that in the default implementation in Scikit-learn, k-means++ is initiated many times with different centroid seeds. The output is the best of 10 runs by default. As we want to have control of this behavior, we set the parameter n init=1 and then compute the average of many different runs.
Additionally to the metrics used in the main experimental section, we also compute the number of unstable points, defined as the size of the set U = {o E M clustering qualities, we additionally measure three quantities. First, we measure "cost", which is the average within-cluster distances. Formally, Cost = Σk (1 Exyec, d(x v). We
stable). In terms of
then measure k-center costs, defined the maximum distances from any point to its center. Here, centers are given naturally from k-means++ and our algorithm. Finally, k-means costs, defined as k-means-cost = Σ [. Ex.geC d(
13

---

C.1 Hard Instance for k-means++ for IP-Stability
We briefly describe the hard instance for k-means++ for the standard stabiiiiyity formulation given in [ see their paper for full details. The hard instance consists of gadget of size 4. In the seed- finding phase of k-means++, if incorrectly picks centers in the gadget, then the final clustering is not (9-approximate IP-stable, where /3 is a configurable parameter. The instance for k-clustering is produced by concatenating these gadgets together. In such an instance, with a constant probability, the clustering returned by k-means+ is not --approximmte IP-stable and in particular. We remark that the proof of Theorem in [ easily implies that k-means++ cannot have an approximation factor better than n for some absolute constant 0, ie.. we can insure 3 (2(n"). Here, we test both our algorithm and k-means++ in an instance with 8,000 points (for k = 2, 000 clusters).
IP-Stability results We first discuss five real dataset. We tested the algorithms for the range of l: up to 25. The result Figures and iis consistent with the experiments in the previous paper as we that k-means++ is a very competitive algorithm for these datasets. For small number of clusters, our algorithm sometimes outperforms k-means++. We hypothesize that on these datasets, especially for large k, clusters which have low k-means cost separate the points well and therefore are good clusters for It-stability.
and
Next we discuss the + hard instance. The instance used in Figure was constructed with = 50. We vary & but omit the results for higher values since the outputs from both algorithms are stable. We remark that the empirical results with different 3 gave qualitatively similar results. For maximum and mean violation, our algorithm outperforms k-means++ (Figure
D
Future Directions
There multiple natural open questions following our work.
Note that in some cases, a-IP stable clusterings for a < may exist. On the other hand, in the hard example on 4 from [. know that there some constant C >> 1 such that no C-IP stable clutering exists. For a given input, let a" be the minimum value such that -IP stable clustering exists. Is there an efficient algorithm which returns an O(a")-IP stable clustering? Note that our algorithm satisfies this for a 22(1). An even stronger result would be to find PTAS which returns + =)a--IP stable clustering.
For what specific metrics (other than the line or tree metries with k 2) can we get 1-IP stable clusterings efficiently?
In addition to stability, desirable that a clustering algorithm also achieves strong global welfare guarantee. Our algorithm gives constant approximation for k-center. What about other metries, such as k-means?
14

---

Our Alg
k-means++
Adult
Drug
IndianLiver
200
500
#Unf
200
100
5
10
15
20
25
10
15
20
5
16
20
25
3.0
2.5
2.5
2.0
2.0
1.5
XA
0.5
0.5
5
10
25
15
20
25
1.6
1.6
MeanVi
1.2
1.2
0.8
**
0.4
0.4
0.4
5
10
15
20
25
10
15
20
25
0
5
10
15
20
25
40
75
Cost
20
25
10000
40000
10000
k-means
30000
5000
5000
20000
5
10
15
20
25
10
15
20
25
0
5
10
15
20
25
k-conter Cost
10
10
10
15
k
Figure 2: Experiment results three datasets used in
0.
15

---

Our Alg
k-means++
BreastCancer
Car
Hard
400
750
#Unf
100
200
500
250
0
5
10
15
20
25
10
15
1000
2000
3000
1.6
1.4
1.1
1.2
10
25
10
15
1000
2000
3000
0.80
0.95
0.55
0.6
0.90
0.50
5
10
15
20
25
10
15
20
25
1000
2000
3000
100
100
Cost
4.0
50
3.5
30000
80000
10
komeans
20000
60000
5
10
15
20
25
10
15
20
25
1000
2000
3000
k-center Cost
15
0.05
10
6
10
15
1000
2000
3000
k
Figure 3: Additional experiment results real datasets and the synthetic dataset.
16


Reviews:
[{"review_id": "zgSavgOqDN", "reviewer": "Reviewer_d1bb", "summary": "In $\\alpha$-individual preference (IP) stable clustering, the average distance between every data point to other points in its cluster must be at most $\\alpha$ times the average distance between it to points in any other cluster. \n\nThis paper gives the first polynomial time $O(1)$-IP stable clustering algorithm in general metrics, which improves [Ahmadi et.al, ICML 2022] 's $O(n)$-IP stable result. The algorithm in this paper also has more interesting features that I appreciate. Firstly, it satisfies an even stronger uniform IP stability guarantee. Precisely, there exists a global parameter $r$, such that for every data point, its average distance to points in its cluster is bounded by $O(r)$ while its average distance to point in any other cluster is at least $O(r)$. Secondly, the k-clustering it finds is also a constant factor approximation to the classical k-center clustering problem, which makes the solution much more meaningful in applications. I think this result shows that k-center clustering can admit IP stability without paying too much. Exciting news!\n\nMoreover, the algorithm presented is clean and easy to follow with its analysis building on certain clever observations. Authors also do experiments against [Ahmadi et.al, ICML 2022]  to show the practical value of their algorithm. At last, the authors also study other definitions of IP-stable and obtain similar results.\n\nOverall, I recommend \"accept\".", "questions": "1. It is argued that the running time can be improved in Euclidean space. What is the exact running time that you can achieve? What about $\\tilde{O}(nkd)$? (a typical running time for Euclidean $k$-clustering.)\n\n2. Have you formally proved that your algorithm returns an $O(1)$-approximation for $k$-center in the main text? I know it can be seen from Algorithm 2 but it is better to provide formal proof and write the exact approximation ratio. ", "limitations": "I do not see the potential negative societal impact.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The first efficient algorithm to compute O(1)-IP stable approximate clustering in general metrics. Additionally, the algorithm has more important features beyond IP stability. The result significantly improves the previous works.\n\n2. The algorithm and analysis are interesting and have some non-trivial insights.\n\n3. The experiments also outperform the baseline.", "weaknesses": "Both the constants for IP approximation and k-center approximation may be too large. While IP stability is motivated by practical applications, I would expect that the guarantee is not a quite large number such as 2 or 3. The paper's experiment already shows that the worst case may be avoided in practice and I would like to see more discussion in this direction. Anyway, as a theoretical submission, I think this is totally fine and does not lower my rating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Below is our response.\n\n> \"[...] the constants for IP approximation and k-center approximation may be too large.\"\n\nThe focus of this paper is to give a constant factor approximation, improving upon the only O(n)-approximation of the IP-stability clustering problem. For the sake of clarity of the presentation, we did not try to optimize the constants here.\n\n> \"The paper's experiment already shows that the worst case may be avoided in practice and I would like to see more discussion in this direction.\"\n\nThis is indeed an interesting future direction to explore the approximability of IP-stability for instances in practice. A challenge in this direction is to identify the properties that result in better IP-stable clustering guarantees.   \n\n> It is argued that the running time can be improved in Euclidean space. What is the exact running time that you can achieve? What about O~(ndk) (a typical running time for Euclidean k-clustering.)? \n\nWe have opted for simplicity and generality to ensure our algorithm applies to any metric space. As stated in Section 3, our algorithm can be naively implemented in $\\tilde{O}(n^2T)$ time for any metric space where $T$ is the time to compute a distance between two points. However, we believe that for specialized metrics, such as Euclidean metrics, it is an interesting future question to obtain faster algorithms. For example, one can show that for *constant* dimensional Euclidean space, our algorithm can be made to run in O(nk) time. \n\n> Have you formally proved that your algorithm returns an O(1) approximation for k-center in the main text? I know it can be seen from Algorithm 2 but it is better to provide formal proof and write the exact approximation ratio\n\nThe k-center guarantee is shown in Theorem 3.1. Per the reviewer's suggestion, we will include the exact k-center approximation factor in the final version."}, {"review_id": "eQmNa3EnCz", "reviewer": "Reviewer_zmPi", "summary": "This paper concerns alpha-individual preference (IP) stable clusterings, meaning clusterings such that its average distance to points in its cluster is at most alpha times greater than to that in any other cluster. Previously, only O(n)-IP solutions were known, 1-IP solutions were known to not always exist, and we did not know if there existed O(1)-IP solutions. This paper answers affirmatively on metric spaces.\n\nThey provide an O(1)-IP algorithm on metric spaces which additionally is a constant-factor approximation to the k-center problem. The algorithm follows the popular greedy ball technique on metrics, which selects radius-bounded balls (bounded by O(1) times the optimal k-center solution) that cover many points and are distant from each other, and then fixes unassigned points (according to the greedy cluster order) and merges some clusters according to their closest k-center centers.\n\nAdditionally, they define variants Max-IP and Min-IP (where you instead look at the maximum/minimum distances, as opposed to the averages). They show Min-IP can be solved optimally by running Kruskal’s algorithm until there are k trees in the forest. Additionally, greedy k-center 3-approximates Max-IP.\n\nFinally, the experimentally validate their IP algorithm on real and synthetic (adersarily-designed) datasets. On both, their algorithm outperforms k-means++, showing its robustness to hard instances.", "questions": "1. Can you motivate this problem a bit more? Has anyone other than [1] tried attacking this problem?\n2. Do you have any citations for uses?\n3. I understand that IP was the main focus of the paper, but it would be nice to have an argument for the motivations of Min-IP and Max-IP. Do you know any applications they might work for?", "limitations": "I did not see a limitations section. It would be preferable but is not necessary for this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a nice result that bridges a significant gap posed by previous works (i.e., the gap between O(n)-IP and O(1)-IP). In addition, it is complemented by the lower bound of 1-IP, and it implies a few nice future directions for this work, including finding the minimum alpha such that an alpha-IP solution exists and characterizing when 1-IP solutions exist. The extensions to Max-IP and Min-IP are also strong. For the most part, the writing was clear (though I did find some typos here and there). The methods seemed new in many ways, though they were heavily founded based off existing methods (i.e., clustering by balls on metric graphs).", "weaknesses": "The biggest weakness is that, while the improvement in approximation is significant, I think the problem is somewhat narrow in scope. I noticed the authors only cited one past work on this area (presumably, the one that proposed it), and the applications were not cited. While this does certainly seem like an interesting new problem, I am not sure of what its place is within ML research literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address your concerns and questions below.\n\n> The biggest weakness is that, while the improvement in approximation is significant, I think the problem is somewhat narrow in scope. I noticed the authors only cited one past work on this area (presumably, the one that proposed it), and the applications were not cited. While this does certainly seem like an interesting new problem, I am not sure of what its place is within ML research literature.\n\nWe thank the reviewer for their comments. It is true that individual preference stability is a new concept (though we would argue a rather natural criterion) that was only introduced in ICML’22. However, there are some connections to prior work that we will highlight.\n\nIP stable clustering is closely related to a burgeoning line of work on fairness in machine learning and, relatedly, on individual (rather than global) objectives. In a preliminary version of [1], they formulated the problem as a fair clustering problem (see [2]). Various notions of fairness in clustering have been examined [3, 4] (https://www.fairclustering.com, https://www.fairclustering.com/files/fair-clustering-taxonomy.pdf), and IP stability can be viewed as an alternate definition. We note that the notion of stability is more general than fairness (there may be other reasons to want stability, for example if the actors being clustered are strategic and may try to change clusters if unhappy).\n\nIn terms of applications, to the best of our knowledge, we do not know any published work that uses this notion explicitly, but we do see potential applications. There are cases when we want to incorporate fairness in clustering, e.g., in bank loan, an applicant would be upset if their loan application gets rejected while another individual with similar features has an approved application. Similar applications can be argued for job listings, school applications, et cetera.\n\nApart from [1], a somewhat similar notion was studied in [5]. In particular, in Sect. 1.1 of [5], it is mentioned that in general sense, for any good clustering notion, if $x \\in C$ and $y \\notin C$, then $x$ should be substantially closer to $C$ than $y$. [5] studied the case where the term ``substantially closer’’ is emphasized. Formally, a cluster $C$ is $(\\alpha,\\gamma)$-cluster if $P(x \\in C)>\\alpha$ and for any $y \\notin C$, $d(y,C) \\geq \\gamma d(x,C)$. A $(\\alpha, \\gamma)$-clustering is a clustering where each cluster is an $(\\alpha,\\gamma)$-cluster. This problem becomes tractable when $\\alpha > 0, \\gamma >3$. Our case is corresponding to $(0,1)$-clustering. In fact, our algorithm finds a $(0, O(1))$-clustering.\n\n> I understand that IP was the main focus of the paper, but it would be nice to have an argument for the motivations of Min-IP and Max-IP. Do you know any applications they might work for?\n\nSimilar to what the community does for fairness, we look into several notions of stability. While we do not know any applications yet, we believe that Min-IP, Max-IP, and more generally f-IP, are natural stability definitions.\n\n\nReferences:\n\n[1] Ahmadi, Saba, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, and Ali Vakilian. \"Individual Preference Stability for Clustering.\" In International Conference on Machine Learning. 2022.\n\n[2] Kleindessner, Matthäus, Pranjal Awasthi, and Jamie Morgenstern. \"A notion of individual fairness for clustering.\" arXiv preprint arXiv:2006.04960 (2020).\n\n[3] Brubach, Brian, Deeparnab Chakrabarty, John P. Dickerson, Seyed Esmaeili, Matthäus Kleindessner, Marina Knittel, Jamie Morgenstern, Samira Samadi, Aravind Srinivasan, and Leonidas Tsepenekas. \"Fairness in Clustering.\"\n\n[4] Chhabra, Anshuman, Karina Masalkovaitė, and Prasant Mohapatra. \"An overview of fairness in clustering.\" IEEE Access 9 (2021): 130698-130720.\n\n[5] Daniely, Amit, Nati Linial, and Michael Saks. \"Clustering is difficult only when it does not matter.\" arXiv preprint arXiv:1205.4891 (2012).\n\n"}, {"review_id": "MfRqkOeG16", "reviewer": "Reviewer_F6zy", "summary": "This paper considers the problem of finding stable clusterings under a specific notion of stability - individual-preference stability which roughly requires the clustering produced to have the property where the average distance of any datapoint to points within its own cluster to be smaller than the average distance to points within any other cluster. The clustering is said to be $\\alpha$-stable if the average in-cluster distance to be no more than a multiplicative $\\alpha>1$ factor of the average distance to points assigned to any other cluster. This is a fairly natural problem, and was recently proposed by Ahmadi et. al. (ICML 22), who gave some preliminary results for it, including NP-Hardness of deciding whether the input dataset admits a $1$-stable clustering.\n\nThis paper makes three key contributions - \n\n(a) It shows that given any dataset with $n$ points in a general metric space, and any desired number of clusters $k$, there always exists a  $k$-clustering that is $O(1)$-stable. \n\n(b) This $O(1)$-stable $k$-clustering can be found by a computationally efficient algorithm. Moreover, the resulting clustering produced is a constant factor approximation to the optimal $k$-center objective.\n\n(c) For min and max stability (i.e. where the average is replaced with min and max, respectively), they show that for any dataset in a general metric space, and for any choice of $k$, (i) a min-stable $k$-clustering always exists, and is achieved by the usual early-termination of Kruskals minimum spanning tree algorithm, and (ii) a 3 approximate max-stable $k$-clustering always exists and is achieved by the greedy $k$-center algorithm.", "questions": "I understand that these questions are out of scope of this paper, but im curious about the following thing -\n\nGiven how you say that its only interesting to look at stability when the algorithm additionally gives good approximation guarantees for other natural clustering objective functions, I really want to know what happens when you simultaneously want to optimize for other objective functions such as say $k$-means or $k$-medians. Is it possible to get a clustering that achieves a good approximation for these standard clustering objectives, while simultaneously being approximately stable? Or are there cases where these two objectives of clustering \"quality\" and \"stability\" are at odds of each other - achieving one objective must necessarily incur a large penalty for the other objective?\n\nMy other question is related to your extension of the notion of stability, and one I have raised before in the weaknesses - can you characterize properties of a generic $f$ required such that any instance always admits an $O(1)$-$f$-stable $k$-clustering?", "limitations": "I dont see any obvious limitations of this work. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper considers a very natural question of obtaining a stable clustering, and substantially expands our understanding of this problem. Overall the paper is quite well-written and easy to read, and would be a well-suited for a venue such as NeurIPS. \n\n(a) They show that given a set of any $n$ points in an arbitrary metric space, a $O(1)$-stable $k$-clustering always exists for any choice of $k$. Moreover, the clustering includes all $n$ points. The only known results prior to this work was the existence of a $1$-stable clustering for any set of $n$ points in a $1$-D Euclidean space or metrics induced by a weighted tree, or a bicriteria $O(\\log^2 n/\\epsilon)$ stable clustering achieved by discarding an $\\epsilon$-fraction of the points from the input set. For the stricter requirement of clustering all $n$ points, the only known result was a trivial $O(n)$-stable clustering.\n\n(b) The algorithm that finds this $O(1)$-stable $k$-clustering is simple and quite computationally efficient. The earlier bicriteria approximation result was achieved by applying the HST hammer naively. The new algorithm has the additional desirable property that the resulting clustering produced achieves a constant factor approximation for the $k$-center objective.\n", "weaknesses": "The paper has two main weaknesses, which in my opinion are not deal breakers given its other strengths.\n\n(a) The extension to $f$-stable clusterings is obvious, and the results for $f=$ min and max stable clusterings are also very elementary. It would have been far more interesting had the authors characterized properties of a generic $f$ required such that any instance always admits an $O(1)$-$f$-stable $k$-clustering.\n\n(b) The fact that the algorithm achieves a $O(1)$ approximation to the $k$-center objective seems like an afterthought. It doesnt seem like the algorithm was explicitly designed to additionally achieve good approximation guarantees for this other objective, and more like it happened to be that way.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address your concerns and questions below.\n\n> The extension to f-stable clusterings is obvious, and the results for min and max stable clusterings are also very elementary\n\nIndeed, the results for min and max stable clusterings come from quite straightforward observations, but we think it shows a nice connection between the individual preference objectives and classic algorithm problems (min spanning tree and k-center). The research question about generic f is a nice one for future work. It would be quite interesting to see if a general property holds that admits stable f-clusterings especially since the algorithms we have for min and max-stability use quite different techniques.\n\n> The fact that the algorithm achieves a O(1) approximation to the k-center objective seems like an afterthought\n\nFrom the point of view of our research process, this is correct: our main goal was to develop algorithms with small approximation factors for IP stability. The serendipity of the additional k-center guarantee doesn’t detract from the fact that simultaneously achieving individual and global clustering guarantees seems like it would be very valuable in practice (as we discussed in Section 1.2). A very nice open question (Appendix D and your question) is if good IP stability approximation can be combined with other global objectives.\n\nWe believe our response above also answers your questions."}, {"review_id": "rjFOBsiyO4", "reviewer": "Reviewer_kydQ", "summary": "This paper continues the study of individual preference stability (IP stability) initiated by Ahmadi et. al. (2022). Given a set of points in a metric space, a k-clustering is said to be 1-IP stable if for every point in the set, its average distance to the points in its cluster is at most its average distance to the points in a different cluster; so, in this sense, a point prefers its own cluster to other clusters. There are datasets for which a 1-IP stable clustering does not exist, and further, it is NP-hard to decide whether a dataset admits a 1-IP stable k-clustering. In light of this, it is natural to broaden the definition to approximate IP stability: a k-clustering is \\alpha-IP stable if the average distance of a point to another cluster is at most \\alpha times its average distance to its own cluster. The work of Ahmadi et. al. shows that an O(n)-IP stable clustering always exists and gives an algorithm for computing one. The present work closes the gap between the known lower and upper bounds: the authors propose an algorithm that always outputs an O(1)-stable clustering (so they also prove that one always exists, a fact not already established). Interestingly, the output clustering has the additional property that it is a constant factor approximation for k-center. Indeed, the greedy k-center algorithm of Gonzalez is a phase in their algorithm, and the \"ball-carving\" phase of their algorithm is similar in spirit to another approximation algorithm for k-center (although there are important nuances in the algorithm in the present work that differentiate it). The fact that the algorithm doubles as an approximation algorithm for k-center, the authors note, ensures that the O(1)-IP stable clustering is in some sense meaningful; for, they demonstrate that a random k-coloring a graph will produce an O(1)-IP stable clustering (for certain k), but of course such a clustering is not meaningful in general. \n\nThe authors also introduce two variants of IP stability. For Min-IP stability, in which \"average distance\" is replaced with \"min distance\" in the definition of IP stability, they show that the Single Link algorithm produces an exactly stable (optimal) clustering. For Max-IP stability (defined analogously), they show the greedy k-center algorithm of Gonzalez gives a 3-IP stable clustering. \n\nFinally, the authors show experiments comparing their algorithms to k-means ++ as a baseline. While their algorithm performs slightly worse than k-means ++ for IP stability in general, they claim its robustness by showing a hard instance for which it outperforms k-means ++. They also show that in practice k-means ++ can be up to five times worse than their (optimal) algorithm for Min-IP stability.   ", "questions": "- A variant of Single-Link clustering is used in the work of Awasthi, Blum, and Sheffet (2012) to find optimal clusterings on perturbation stable instances. Given the algorithmic similarities, do you see any connections between these two notions of stability? \n\n- Do you have any intuition as to why k-center approximation algorithms in particular are useful for IP-stability algorithms, given that IP-stability (in its original form) is based on average distances? While k-median and k-center are in general different notions, it is perhaps not clear a priori which objective could help inspire an algorithm for IP-stability. Have you considered the question of finding an algorithm that produces a clustering that is O(1)-IP stable and also constant approximate for other objectives?", "limitations": "Not applicable. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This work closes the (previously large) gap between upper and lower bounds for IP-stability. It demonstrates the existence of constant-stable clusterings and how to find them efficiently. It also provides a convincing argument that a clustering produced by the algorithm is meaningful by showing that it also gives a constant approximation for k-center, which I think is a key contribution given that the authors show, on the flip side, that a clustering can satisfy O(1)-stability but otherwise not uncover meaningful structure. \n\n- The algorithm takes inspiration from approximation algorithms for k-center but there are important subtleties in the adaptation of these algorithms. The Ball-Carving algorithm (Algorithm 1) is a more nuanced version of an approximation algorithm for k-center (in which one guesses the optimal radius, and then repeatedly cuts out balls of that radius until no points remain). In Algorithm 1, more care is taken as to how to choose the center of the ball at each iteration (instead of being chosen arbitrarily as in the approximation algorithm)  as well as how to assign points to centers (instead of just carving out a ball of a certain radius). Finally, the centers from running the algorithm of Gonzalez are used to prune the number of clusters produced in the carving algorithm. \n\n- The authors repurpose existing algorithms (Single Link clustering and the greedy algorithm of Gonzalez) to give guarantees for Min- and Max- IP stability. This is interesting in its own right because it shows that the notion of stability is intimately related to other clustering objectives. ", "weaknesses": "- While Algorithms 1 and 2 are described very clearly, little motivation or intuition is given. For instance, it would be useful to provide examples that show the necessity of the nuances in the Ball-Carving algorithm. \n\n- A discussion of how Algorithms 1/2 differ from or build on the algorithms of Ahmadi et. al. would help highlight the novelty of the contributions. \n\n- A more specific comment: The paragraph on lines 66-70 seems inconsistent with later claims (unless I have misinterpreted something). It seems that if the parameter r is chosen to be anything, then the properties claimed in lines 66-70 hold, but potentially with more than k clusters. Only when r is chosen as a function of r_0  and then the pruning step in Algorithm 2 is performed do the properties seem to hold with k clusters. If this is the case, then I think the current wording in lines 66-70 is easily misinterpreted. Still, the stronger guarantee of uniform IP stability with r chosen as a function of r_0 is noteworthy. \n\n- It seems that Algorithm 3 is simply the well-known algorithm of Single Link clustering. This should be labelled as such and cited. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address your concerns and questions below.\n\n> While Algorithms 1 and 2 are described very clearly, little motivation or intuition is given.\n\nThanks for the suggestion. It did indeed require a good amount of work for us to figure out the details of the ball carving algorithm and we considered several simpler versions of the algorithm which didn’t work. As such, we realize that some motivation is in place. We will include this in the paper and provide some examples showing that various other natural approaches do not work.\n\n> A discussion of how Algorithms 1/2 differ from or build on the algorithms of Ahmadi et. al. would help highlight the novelty of the contributions\n\nOur algorithm is completely different from the algorithm of [Ahmadi et al] and is more sophisticated. Their O(n)-approximation relies on the standard metric embedding result to line metric, together with a simple greedy algorithm for IP-stability on line metric. The discussion of previous results is in line 51-55 of the paper.\n\n> The paragraph on lines 66-70 seems inconsistent with later claims\n\nYou’re correct, Algorithm 1 works for any value of r but provides no guarantee on the number of clusters and we only get the property to hold with exactly k clusters for the right value of r which depends on r_0 (which in turn depends on P and k). We will make it clear in lines 66-70 that r depends on the set of points P and on k.\n\n> It seems that Algorithm 3 is simply the well-known algorithm of Single Link clustering.\n\nYes, we will provide a citation appropriately.\n\n> A variant of Single-Link clustering is used in the work of Awasthi, Blum, and Sheffet (2012) to find optimal clusterings on perturbation stable instances. Given the algorithmic similarities, do you see any connections between these two notions of stability\n\nWhile the line of research on perturbation stability focuses on designing faster or more accurate algorithms utilizing the strong stability (and separability) conditions, here we aim to recover such stability conditions in general metrics approximability. We will expand on the discussion of stability in clustering in the related work section (line 158-165) and add comparison with the result of Awasthi, Blum, and Sheffet (2012).\n\n> Do you have any intuition as to why k-center approximation algorithms in particular are useful for IP-stability algorithms, given that IP-stability (in its original form) is based on average distances?\n\nk-center is particularly useful in the context of uniform approximate IP-stability. After getting said uniform property from the clustering output by Algorithm 1, it is natural to next consider the k-center algorithm. Indeed, for k-center, we have the relation that the minimum distance between clusters is also an upper bound on the distance from any point to its nearest center. This relation gives that when running Algorithm 2, we simultaneously get that each cluster is non-empty and the uniform upper bound on the diameter of each cluster in the final clustering. This property does not necessarily hold for k-median or k-means. We will add a comment on this in the paper.\n\n> Have you considered the question of finding an algorithm that produces a clustering that is O(1)-IP stable and also constant approximate for other objectives?\n\nSimultaneously achieving approximate IP stability as well as a global objective other than k-center is a very nice open question for future work (we also list it in Appendix D). We don’t see a way of directly extending our algorithm to k-median or k-means, for instance, because we use the diameter guarantee which is more specific to k-center.\n"}]

Author rebuttal:

Meta-review: All of the reviewers were positive about this paper. The paper considers an interesting problem recently introduced, individually stable clustering. The paper offers interesting new algorithmic insights into the problem.
Decision: Accept (spotlight)