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.
The 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.
Finally, 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.
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.
- 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.
- 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.
- 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.
- 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.
- It seems that Algorithm 3 is simply the well-known algorithm of Single Link clustering. This should be labelled as such and cited.
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?
- 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?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Not applicable.