Data Stability in Clustering: A Closer Look

Introduction

Clustering is one of the most widely-used techniques in statistical data analysis. The need to partition, or cluster, data into meaningful categories naturally arises in virtually every domain where data is abundant. Unfortunately, most of the natural clustering objectives, including $k$-median, $k$-means, and min-sum, are NP-hard to optimize . It is, therefore, unsurprising that many of the clustering algorithms used in practice come with few guarantees.

Motivated by overcoming the hardness results, Bilu and Linial consider a perturbation resilience assumption that they argue is often implicitly made when choosing a clustering objective: that the optimum clustering to the desired objective $\Phi$ is preserved under multiplicative perturbations up to a factor $\alpha>1$ to the distances between the points. They reason that if the optimum clustering to an objective $\Phi$ is not resilient, as in, if small perturbations to the distances can cause the optimum to change, then $\Phi$ may have been the wrong objective to be optimizing in the first place. Bilu and Linial show that for max-cut clustering, instances resilient to perturbations of $\alpha=O(\sqrt{n})$ have efficient algorithms for recovering the optimum itself.

Continuing that line of research, Awasthi et al. give a polynomial time algorithm that finds the optimum clustering for instances resilient to multiplicative perturbations of $\alpha=3$ for center-basedFor center-based clustering objectives, the clustering is defined by a choice of centers, and the objective is a function of the distances of the points to their closest center. clustering objectives when centers must come from the data (we call this the proper setting), and $\alpha=2+\sqrt{3}$ when when the centers do not need to (we call this the Steiner setting). Their method relies on a stability property implied by perturbation resilience (see Section 2). For the Steiner case, they also prove an NP-hardness lower bound of $\alpha=3$. Subsequently, Balcan and Liang consider the proper setting and improve the constant past $\alpha=3$ by giving a new polynomial time algorithm for the $k$-median objective for $\alpha=1+\sqrt{2}\approx 2.4$ stable instances.

Our work further delves into the proper setting, for which no lower bounds have previously been shown for the stability property. In Section 3 we show that even in the proper case, where the algorithm is restricted to choosing its centers from the data, for any $\epsilon>0$, it is NP-hard to optimally cluster $(2-\epsilon)$-stable instances, both for the $k$-median and min-sum objectives (Theorems 5 and 7). To prove this for the min-sum objective, we define a new notion of stability that is implied by perturbation resilience, a notion that may be of independent interest.

Then in Section 4, we look at the implications of assuming resilience or stability in the data, even for a constant perturbation parameter $\alpha$. We show that for even fairly small constants, the data begins to have very strong structural properties, as to make the clustering task fairly trivial. When $\alpha$ exceeds $2+\sqrt{3}$, the data begins to show what is called strict separation, where each point is closer to points in its own cluster than to points in other clusters (Theorem 8).

Finally, in Section 5, we look at whether the picture can be improved for clustering data that is stable under additive, rather than multiplicative, perturbations. One hope would be that additive stability is a more useful assumption, where a polynomial time algorithm for $\epsilon$-stable instances might be possible. Unfortunately, this is not the case. We consider a natural additive model and show that severe lower bounds hold for the additive notion as well (Theorems 13 and 17). On the positive side, we show via reductions that algorithms for multiplicatively stable data also work for additively stable data for a different but related parameter.

Our results demonstrate that on the one hand, it is hard to improve the algorithms to work for low stability constants, and that on the other hand, higher stability constants can be quite strong, to the point of trivializing the problem. Furthermore, switching from a multiplicative to an additive stability assumption does not help to circumvent the hardness results, and perhaps makes matters worse. These results, taken together, narrow the range of interesting parameters for theoretical study and highlight the strong role that the choice of constant plays in stability assumptions.

One thing to note that there is some difference between the very related resilience and stability properties (see Section 2), stability being weaker and more general . Some of our results apply to both notions, and some only to stability. This still leaves open the possibility of devising polynomial-time algorithms that, for a much smaller $\alpha$, work on all the $\alpha$-perturbation resilient instances, but not on all $\alpha$-stable ones.

2 Previous work

We examine previous work on stability, both as a data dependent assumption in clustering and in other settings.

In contrast, a more recent direction of research has been to characterize under what conditions we can find a desirable clustering efficiently. Perturbation resilience/stability are such conditions, but they are related to other stability notions in clustering. Ostrovsky et al. demonstrate the effectiveness of Lloyd-type algorithms on instances with the stability property that the cost of the optimal $k$-means solution is small compared to the cost of the optimal $(k-1)$-means solution, and their guarantees have later been improved by Awasthi et al. .

In a different line of work, Balcan et al. consider what stability properties of a similarity function, with respect to the ground truth clustering, are sufficient to cluster well. In a related direction, Balcan et al. argue that, for a given objective $\Phi$, approximation algorithms are most useful when the clusterings they produce are structurally close to the optimum originally sought in choosing to optimize $\Phi$ in the first place. They then show that, for many objectives, if one makes this assumption explicit – that all $c$-approximations to the objective yield a clustering that is $\epsilon$-close to the optimum – then one can recover an $\epsilon$-close clustering in polynomial time, even for values of $c$ below the hardness of approximation constant. The assumptions and algorithms of Balcan et al. have subsequently been carefully analyzed by Schalekamp et al. .

Ackerman and Ben-David also study various notions of resilience, and among their results, introduce a notion of stability similar to the one studied herein, except only the positions of cluster centers are perturbed. Their notion is strictly weaker – i.e. any perturbation resilient instance is also stable in their framework. They show that Euclidean instances stable to perturbations of cluster centers will have polynomial algorithms for finding near-optimal clusterings. However, they require the desired number of clusters to be small compared to the input size: their algorithms have running times exponential in the number of clusters. In this work, we do not make that assumption; this means our positive results are more general, but our lower bounds don’t apply.

2.2 Stability in other settings

Just as the Bilu and Linial notion of stability gives conditions under which efficient clustering is possible, similar concepts have been studied in game theory. Lipton et al. propose a notion of stability for solution concepts of games. They define a game to be stable if small perturbations to the payoff matrix do not significantly change the value of the game, and they show games are generally not stable under this definition. Then, in a similar spirit to the work of Bilu and Linial, Awasthi et al. propose a related stability condition for a game, which can be leveraged in finding its approximate Nash equilibria.

The Bilu and Linial notion of stability has also been studied in the context of the metric traveling salesman problem, for which Mihalák et al. give efficient algorithms for $1.8$-perturbation resilient instances, illustrating another case where a stability assumption can circumvent NP-hardness.

From a different direction, Ben-David et al. consider the stability of clustering algorithms, as opposed to instances. They say an algorithm is stable if it produces similar clusterings for different inputs drawn from the same distribution. They argue that stability is not as useful a notion as had been previously thought in determining various parameters, such as the optimal number of clusters.

Notation and preliminaries

The centers in the optimal clustering are denoted as $c_{1},\dots,c_{k}$. In an optimal solution, each point is assigned to its nearest center.

Now, we define the perturbation resilience notion introduced by Bilu and Linial .

the optimal clustering $\mathcal{C^{\prime}}$ for $\Phi$ under $d^{\prime}$ is equal to the optimal clustering $\mathcal{C}$ for $\Phi$ under $d$.

In this paper, we consider the $k$-median and min-sum objectives, and we thereby investigate the following definitions of stability, which are implied by perturbation resilience, as shown in Sections 3.1 and 3.2. The following definition is adapted from Awasthi et al. .

A clustering instance $(S,d)$ is $\alpha$-center stable for the $k$-median objective if for any optimal cluster $C_{i}\in\mathcal{C}$ with center $c_{i}$, $C_{j}\in\mathcal{C}\ (j\neq i)$ with center $c_{j}$, any point $p\in C_{i}$ satisfies

Next, we define a new analogous notion of stability for the min-sum objective, and we show in Section 3.2 that for the min-sum objective, perturbation resilience implies min-sum stability. To help with exposition for the min-sum objective, we define the distance from a point $p$ to a set of points $A$,

A clustering instance $(S,d)$ is $\alpha$-min-sum stable for the min-sum objective if for all optimal clusters $C_{i},C_{j}\in\mathcal{C}\ (j\neq i)$, any point $p\in C_{i}$ satisfies

This is a useful generalization because, as we shall see, known algorithms working under the perturbation resilience assumption can also be made to work under the weaker notion of min-sum stability.

Lower bounds

Awasthi et al. prove the following connection between perturbation resilience and stability. Both their algorithms and the algorithms of Balcan and Liang crucially use this stability assumption.

Any clustering instance that is $\alpha$-perturbation resilient for the $k$-median objective also satisfies the $\alpha$-center stability.

Awasthi et al. proved that for $\alpha<3-\epsilon$, $k$-median clustering $\alpha$-center stable instances is NP-hard when Steiner points are allowed in the data. Afterwards, Balcan and Liang circumvented this lower bound and achieved a polynomial time algorithm for $\alpha=1+\sqrt{2}$ by assuming the algorithm must choose cluster centers from within the data.

In the theorem below, we prove a lower bound for the center stable property in this more restricted setting, showing there is little hope of progress even for data where each point is nearly twice closer to its own center than to any other.

For any $\epsilon>0$, the problem of solving $(2-\epsilon)$-center stable $k$-median instances is NP-hard.

We reduce from what we call the perfect dominating set promise problem (PDS-PP), which we prove to be NP-hard (see Appendix), where we are promised that the input graph $G=(V,E)$ is such that all of its smallest dominating sets $D$ are perfect, and we are asked to find a dominating set of size at most $d$. The reduction is simple. We take an instance of the NP-hard problem PDS-PP on $G=(V,E)$ on $n$ vertices and reduce it to an $\alpha=2-\epsilon$-center stable instance. Our distance metric as follows. Every vertex $v\in V$ becomes a point in the $k$-center instance. For any two vertices $(u,v)\in E$ we define $d(u,v)=1/2$. When $(u,v)\notin E$, we set $d(u,v)=1$. This trivially satisfies the triangle inequality for any graph $G$, as the sum of the distances along any two edges is at least $1$. We set $k=d$.

We observe that a $k$-median solution of cost $(n-k)/2$ corresponds to a dominating set of size $d$ in the PDS-PP instance, and is therefore NP-hard to find. We also observe that because all solutions of size $\leq d$ in the PDS-PP instance are perfect, each (non-center) point in the $k$-median solution has distance $1/2$ to exactly one (its own) center, and a distance of $1$ to every other center. Hence, this instance is $\alpha=(2-\epsilon)$-center stable, completing the proof. ∎

2 The min-sum objective

Analogously to Lemma 4, we can show that $\alpha$-perturbation resilience implies our new notion of $\alpha$-min-sum stability.

If a clustering instance is $\alpha$-perturbation resilient, then it is also $\alpha$-min-sum stable.

Assume to the contrary that the instance is $\alpha$-perturbation resilient but is not $\alpha$-min-sum stable. Then, there exist clusters $C_{i},C_{j}$ in the optimal solution $\mathcal{C}$ and a point $p\in C_{i}$ such that $\alpha d(p,C_{i})\geq d(p,C_{j})$. We perturb $d$ as follows. We define $d^{\prime}$ such that for all points $q\in C_{i}$, $d^{\prime}(p,q)=\alpha d(p,q)$, and for the remaining distances, $d^{\prime}=d$. Clearly $d^{\prime}$ is an $\alpha$-perturbation of $d$.

We now note that $\mathcal{C}$ is not optimal under $d^{\prime}$. Namely, we can create a cheaper solution $\mathcal{C^{\prime}}$ that assigns point $p$ to cluster $C_{j}$, and leaves the remaining clusters unchanged, which contradicts optimality of $\mathcal{C}$. This shows that $\mathcal{C}$ is not the optimum under $d^{\prime}$ which contradicts the instance being $\alpha$-perturbation resilient. Therefore we can conclude that if a clustering instance is $\alpha$-perturbation resilient, then must also be $\alpha$-min-sum stable. ∎

Moreover, we show in the Appendix that the min-sum algorithm of Balcan and Liang , which requires $\alpha$ to be bounded from below by $3\left(\frac{\max_{C\in\mathcal{C}}|C|}{\min_{C\in\mathcal{C}}|C|-1}\right)$, works with this more general condition. This further motivates following bound.

For any $\epsilon>0$, the problem of finding an optimal min-sum $k$ clustering in $(2-\epsilon)$-min-sum stable instances is NP-hard.

Consider the triangle partition problem. Let graph $G=(V,E)$ and $|V|=n=3k$, and let each vertex have maximum degree of $d=4$. The problem of whether the vertices of $G$ can be partitioned into sets $V_{1},V_{2},\ldots,V_{k}$ such that each $V_{i}$ contains a triangle in $G$ is NP-complete , even with the degree restriction .

We reduce the triangle partition problem to an $(2-\epsilon)$-min-sum stable clustering instance. The metric is as follows. Every vertex $v\in V$ becomes a point in the min-sum instance. For any two vertices $(u,v)\in E$ we define $d(u,v)=1/2$. When $(u,v)\notin E$, we set $d(u,v)=1$. This satisfies the triangle inequality for any graph, as the sum of the distances along any two edges is at least $1$.

Now we show that we can cluster this instance into $k$ clusters such that the cost of the min-sum objective is exactly $n$ if and only if the original instance is a YES instance of triangle partition. This follows from two facts.

A YES instance of triangle partition maps to a clustering into $k=n/3$ clusters of size $3$ with pairwise distances $1/2$, for a total cost of $n$

A cost of $n$ is the best achievable because a balanced clustering with all minimum pairwise intra-cluster distances is optimal. In particular, $\frac{1}{2}\sum_{i}n_{i}(n_{i}-1)$ s.t. $\sum_{i}n_{i}=n$ is a lower bound on the cost of any $k$-clustering with cluster-sizes ${n_{i}}$. By convexity this expression is minimized at $n$.

In the clustering from our reduction, each point has a sum-of-distances to its own cluster of $1$. Now we examine the sum-of-distances of any point to other clusters. A point has two distances of $1/2$ (edges) to its own cluster, and because $d=4$, it can have at most two more distances of $1/2$ (edges) into any other cluster, leaving the third distance to the other cluster to be $1$, yielding a total cost of $\geq 2$ into any other cluster. Hence, it is $(2-\epsilon)$-min-sum stable. ∎

We note that it is tempting to restrict the degree bound to $3$ in order to further improve the lower bound. Unfortunately, the triangle partition problem on graphs of maximum degree $3$ is polynomial-time solvable , and we cannot improve the factor of $2-\epsilon$ by restricting to graphs of degree $3$ in this reduction.

Strong consequences of stability

In Section 3, we showed that $k$-median clustering even $(2-\epsilon)$-center stable instances is $NP$-hard. In this section we show that even for resilience to constant multiplicative perturbations of $\alpha>2+\sqrt{3}\approx 3.7$, the data obtains a property referred to as strict separation, where all points are closer to all other points in their own cluster than to points in any other cluster; this property is known to be helpful in clustering .

Now we prove the following theorem, which shows that even for relatively small multiplicative constants for $\alpha$, center stable, and therefore perturbation resilient, instances exhibit strict separation.

Let $\mathcal{C}=\{C_{1},\ldots,C_{k}\}$ be the optimal clustering of an $\alpha$-center stable instance with $\alpha>2+\sqrt{3}$. Let $p,p^{\prime}\in C_{i}$ and $q\in C_{j}$ ($i\neq j$), then $d(p,q)~{}>~{}d(p,p^{\prime}).$

Let $\mathcal{C}$ be an $\alpha$-center stable clustering. Let $p,p^{\prime}$ have center $c_{1}$ in $\mathcal{C}$ and let $q$ have center $c_{2}$, with $c_{1}\neq c_{2}$. We have

where the second inequality follows from the definition of $\alpha$-center stability. Note that

and subtracting $\frac{1}{\alpha}d(p^{\prime},c_{1})$ from both sides gives

and subtracting $\frac{1}{\alpha^{2}}d(p,c_{2})$ from both sides gives

Thus we get $d(p,p^{\prime})<d(p,q)$ if we set $\alpha$ such that $2\alpha<(\alpha-1)^{2}$. Solving this gives $\alpha>2+\sqrt{3}$. ∎

The strict separation property, however, is quite strong, as can be seen from the following Corollary.

Let $\mathcal{C}=\{C_{1},\ldots,C_{k}\}$ be the optimal clustering of a $2+\sqrt{3}$-center stable instance. Any algorithm that chooses centers $\{c^{\prime}_{1},\ldots,c^{\prime}_{k}\}$ such that $c^{\prime}_{i}\in C_{i}$ induces the partition $\mathcal{C}$ when points are assigned to their closest centers.

In fact, Balcan et al. show that in instances satisfying the strict separation property, a simple “Single Linkage” algorithm will produce a tree, a pruning of which gives the optimal clustering. Such a pruning can be found using dynamic programming to produce the optimal clustering. Recovering the optimum for $2+\sqrt{3}$-resilient instances is not a new result, but is rather meant to illustrate the power of stability assumptions. Balcan and Liang give a more involved polynomial algorithm for finding optima in $1+\sqrt{2}$-resilient instances.

Additive stability

So far, in this paper our notions of stability were defined with respect to multiplicative perturbations. Similarly, we can imagine an instance being resilient with respect to additive perturbations. Consider the following definition.

Let $d:S\times S\rightarrow$, and let $0<\beta\leq 1$. A clustering instance (S, d) is additive $\beta$-perturbation resilient to a given objective $\Phi$ if for any function $d^{\prime}:S\times S\rightarrow R\geq 0$ such that $\forall p,q\in S$,

the optimal clustering $\mathcal{C^{\prime}}$ for $\Phi$ under $d^{\prime}$ is equal to the optimal clustering $\mathcal{C}$ for $\Phi$ under $d$.

We note that in the definition above, we require all pairwise distances between points to be at most $1$. Otherwise, resilience to additive perturbations would be a very weak notion, as the distances in most instances could be scaled as to be resilient to arbitrary additive perturbations.

Especially in light of positive results for other additive stability notions , one possible hope is that our hardness results might only apply to the multiplicative case, and that we might be able to get polynomial time clustering algorithms for instances resilient to arbitrarily small additive perturbations. We show that this is unfortunately not the case – we introduce notions of additive stability, similar to Definitions 2 and 3, and for the $k$-median and min-sum objectives, we show correspondences between multiplicative and additive stability.

Analogously to Definition 2, we can define a notion of additive $\beta$-center stability.

Let $d:S\times S\rightarrow$, and let $0\leq\beta\leq 1$. A clustering instance $(S,d)$ is additive $\beta$-center stable to the $k$-median objective if for any optimal cluster $C_{i}\in\mathcal{C}$ with center $c_{i}$, $C_{j}\in\mathcal{C}\ (j\neq i)$ with center $c_{j}$, any point $p\in C_{i}$ satisfies

We can now prove that perturbation resilience implies center stability.

Any clustering instance satisfying additive $\beta$-perturbation resilience for the $k$-median objective also satisfies additive $\beta$-center stability.

The proof is similar to that of Lemmas 4. We prove that for every point $p$ and its center $c_{i}$ in the optimal clustering of an additive $\beta$-perturbation resilient instance, it holds that $d(p,c_{j})>d(p,c_{i})+\beta$ for any $j\neq i$.

Consider an additive $\beta$-perturbation resilient clustering instance. Assume we blow up all the pairwise distances within cluster $C_{i}$ by an additive factor of $\beta$. As this is a legitimate perturbation of the distance function, the optimal clustering under this perturbation is the same as the original one. Hence, $p$ is still assigned to the same cluster. Furthermore, since the distances within $C_{i}$ were all changed by the same constant factor, $c_{i}$ will remain the center of the cluster. The same holds for any other optimal clusters. Since the optimal clustering under the perturbed distances is unique it follows that even in the perturbed distance function, $p$ prefers $c_{i}$ to $c_{j}$, which implies the lemma. ∎

Now we prove a lower bound that shows that the task of clustering additive $(1/2-\epsilon)$-center stable instances with respect to the $k$-median objective remains NP-hard.

For any $\epsilon>0$, the problem of finding an optimal $k$-median clustering in additive $(1/2-\epsilon)$-center stable instances is NP-hard.

We use the reduction in Theorem 5, in which the metric satisfies the needed property that $d:S\times S\rightarrow$. We observe that the instances from the reduction are additive $(1/2-\epsilon)$-center stable. Hence, an algorithm for solving $k$-median on a $(1/2-\epsilon)$-center stable instance can decide whether a PDS-PP instance contains a dominating set of a given size, completing the proof. ∎

We now consider center stability, as in the multiplicative case. We prove that additive center stability implies multiplicative center stability, and this gives us the property that any algorithm for $\left(\frac{1}{1-\beta}\right)$-center stable instances will work for additive $\beta$-center stable instances.

Any additive $\beta$-center stable clustering instance for the $k$-median objective is also (multiplicative) $\left(\frac{1}{1-\beta}\right)$-center stable.

Let the optimal clustering be $C_{1},\ldots,C_{k}$, with centers $c_{1},\ldots,c_{k}$, of an additive $\beta$-center stabile clustering instance. Let $p\in C_{i}$ and let $i\neq j$. From the stability property,

We also have $d(p,c_{i})<d(p,c_{j})-\beta$, from which we can see

Equation 3 is derived as follows. The middle term, for $d(p,c_{j})\geq\beta$ (which we have from Equation 2), is monotonically decreasing in $d(p,c_{j})$. Using $d(p,c_{j})\leq 1$ bounds it from below. Relating the LHS to the RHS of Equation 3 gives us the needed stability property. ∎

2 The min-sum objective

Here we define additive min-sum stability and prove the analogous theorems for the min-sum objective.

Let $d:S\times S\rightarrow$, and let $0\leq\beta\leq 1$. A clustering instance is additive $\beta$-min-sum stable for the min-sum objective if for every point p in any optimal cluster $C_{i}$, it holds that

If a clustering instance is additive $\beta$-perturbation resilient, then it is also additive $\beta$-min-sum stable.

Assume to the contrary that the instance is $\beta$-perturbation resilient but is not $\beta$-min-sum stable. Then, there exist clusters $C_{i},C_{j}$ in the optimal solution $\mathcal{C}$ and a point $p\in C_{i}$ such that $d(p,C_{i})+\beta(|C_{i}|-1)\geq d(p,C_{j})$. Then, we perturb $d$ as follows. We define $d^{\prime}$ such that for all points $q\in C_{i}$, $d^{\prime}(p,q)=d(p,q)+\beta$, and for the remaining distances $d^{\prime}=d$. Clearly $d^{\prime}$ is a valid additive $\beta$-perturbation of $d$.

We now note that $C$ is not optimal under $d^{\prime}$. Namely, we can create a cheaper solution $\mathcal{C^{\prime}}$ that assigns point $p$ to cluster $C_{j}$, and leaves the remaining clusters unchanged, which contradicts optimality of $\mathcal{C}$. This shows that $\mathcal{C}$ is not the optimum under $d^{\prime}$ which is contradictory to the fact that the instance is additive $\beta$-perturbation resilient. Therefore we conclude that if a clustering instance is additive $\beta$-perturbation resilient, then it is also additive $\beta$-min-sum stable. ∎

As with the $k$-median objective, we show that additive min-sum stability exhibits similar lower bounds as in the multiplicative case.

For any $\epsilon>0$, the problem of finding an optimal min-sum clustering in additive $(1/2-\epsilon)$-min-sum stable instances is NP-hard.

We use the reduction in Theorem 7, in which the metric satisfies the property that $d:S\times S\rightarrow$. The instances from the reduction are additive $(1/2-\epsilon)$-min-sum stable. Hence, an algorithm for clustering a $(1/2-\epsilon)$-min-sum stable instance can solve the triangle partition problem. ∎

Finally, as we did for the $k$-median objective, we can also reduce additive stability to multiplicative stability for the min-sum objective.

Let $t=\frac{\max_{C\in\mathcal{C}}|C|}{\min_{C\in\mathcal{C}}|C|-1}.$ Any additive $\beta$-min-sum stabile clustering instance for the min-sum objective is also (multiplicative) $\left(\frac{1}{1-\beta/t}\right)$-min-sum stable.

Let the optimal clustering be $C_{1},\ldots,C_{k}$ and let $p\in C_{i}$. Let $i\neq j$. From the stability property, we have

Taking reciprocals and multiplying by $d(p,C_{j})$, we get

Equation 5.2 is derived as follows: $d(p,C_{j})\geq\beta(|C_{i}|-1)$ (which we have from Equation 4), is monotonically decreasing in $d(p,C_{j})$. Observing $d(p,c_{j})\leq|C_{j}|$ bounds it from below. Equation 6 gives us the needed property. ∎

Discussion

Our lower bounds, together with the structural properties implied by fairly small constants, illustrate the importance parameter settings play in stability assumptions. These results make us wonder the degree to which the assumptions studied herein hold in practice; empirical study of real datasets is warranted.

Another interesting direction is to relax the assumptions. Awasthi et al. suggest considering stability under random, and not worst-case, perturbations. Balcan and Liang also study a relaxed version of the assumption, where perturbations can change the optimal clustering, but not by much. It is open to what extent, and on what data, any of these approaches will yield practical improvements.

Acknowledgements

We thank Maria-Florina Balcan and Yingyu Liang for helpful discussions, and we appreciate Shai Ben-David’s, Avrim Blum’s and Santosh Vempala’s feedback on the writing. We also especially thank Shai Ben-David for helping us find a bug in the ALT 2012 version of this paper – its claimed one pass streaming result was incorrect.

This work was supported in part by a Simons Postdoctoral Fellowship in Theoretical Computer Science and by ARC while Lev Reyzin was at the Georgia Institute of Technology.

References

Appendix A Dominating set promise problem

A dominating set in a unweighted graph $G=(V,E)$ is a subset $D\subseteq V$ of vertices such that each vertex in $V\setminus D$ has a neighbor in $D$. A dominating set is perfect if each vertex in $D\setminus V$ has exactly one neighbor in $D$. The problems of finding the smallest dominating set and smallest perfect dominating set are NP-hard.

We introduce a related problem, called the perfect dominating set promise problem. In this problem we are promised that the input graph is such that all its dominating sets of size less at most $d$ are perfect, and we are asked to find a set of cardinality at most $d$.

The perfect dominating set promise problem (PDS-PP) is NP-hard.

The $3$d matching problem ($3$DM) is as follows: let $X,Y,Z$ be finite disjoint sets with $m=|X|=|Y|=|Z|$. Let $T$ contain triples $(x,y,z)$ with $x\in X,y\in Y,z\in Z$ with $L=|T|$. $M\subseteq T$ is a perfect $3d$-matching if for any two triples $(x_{1},y_{1},z_{1}),(x_{2},y_{2},z_{2})\in M$, we have $x_{1}\neq x_{2},y_{1}\neq y_{2},z_{1}\neq z_{2}$. We notice that $M$ is a disjoint partition. Determining whether a perfect $3d$-matching exists (YES vs. NO instance) in a $3d$-matching instance is known to be NP-complete.

Now we reduce an instance of the $3$DM problem to PDS-PP on $G=(V,E)$. For $3$DM elements $X$, $Y$, and $Z$ we construct vertices $V_{X}$, $V_{Y}$, and $V_{Z}$, respectively. For each triple in $T$ we construct a vertex in set $V_{T}$. Additionally, we make an extra vertex $v$. This gives $V=V_{X}\cup V_{Y}\cup V_{Z}\cup V_{T}\cup\{v\}$. We make the edge set $E$ as follows. Every vertex in $V_{T}$ (which corresponds to a triple) has an edge to the vertices that it contains in the corresponding $3$DM instance (one in each of $V_{X}$, $V_{Y}$, and $V_{Z}$). Every vertex in $V_{T}$ also has an edge to $v$.

Now we will examine the structure of the smallest dominating set $D$ in the constructed PDS-PP instance. The vertex $v$ must belong to $D$ so that all vertices in $V_{T}$ are covered. Then, what remains is to optimally cover the vertices in $V_{X}\cup V_{Y}\cup V_{Z}$ – the cheapest solution is to use $m$ vertices from $V_{T}$ , and this is precisely the 3DM problem, which is NP-hard. Hence, any solution of size $d=m+1$ for the PDS-PP instance gives a solution to the $3DM$ instance.

We also observe that such a solution makes a perfect dominating set. Each vertex in $V_{T}\setminus D$ has one neighbor in $D$, namely $v$. Each vertex in $V_{X}\cup V_{Y}\cup V_{Z}$ has a unique neighbor in $D$, namely the vertex in $V_{T}$ corresponding to its respective set in the $3$DM instance. ∎

Appendix B Average linkage for min-sum stability

Here, we further support the claim that algorithms designed for $\alpha$-perturbation resilient instances with respect to the min-sum objective can often be made to work for data satisfying the more general $\alpha$-min-sum stability property.

One such algorithm is Algorithm 1. Balcan and Liang proved that Algorithm 1 correctly clusters instances for which the condition in Lemma 20 holds. We can prove the condition indeed holds for $\alpha$-min-sum stable instances (their proof of the lemma holds for the more restricted class of perturbation-resilient instances). To state the lemma, we first define the distance between two point sets, $A$ and $B$:

Assume the optimal clustering is $\alpha$-min-sum stable. For any two different clusters $C$ and $C^{\prime}$ in $\mathcal{C}$ and every $A\subset C$, $\alpha d(A,\bar{A})<d(A,C^{\prime}).$

From the definition of $\alpha d(A,\bar{A})$, we have

The first inequality comes from $\bar{A}\subset C$ and the second by definition of min-sum stability. ∎

This, in addition to Lemma 6, can be used to show their algorithm can be employed for min-sum stable instances.