Clustering under Perturbation Resilience

Introduction

Problems of clustering data from pairwise distance information are ubiquitous in science. A common approach for solving such problems is to view the data points as nodes in a weighted graph (with the weights based on the given pairwise information), and then to design algorithms to optimize various objective functions such as $k$-median or min-sum. For example, in the $k$-median clustering problem the goal is to partition the data into $k$ clusters $C_{i}$, giving each a center $c_{i}$, in order to minimize the sum of the distances of all data points to the centers of their cluster. In the min-sum clustering approach the goal is to find $k$ clusters $C_{i}$ that minimize the sum of all intra-cluster pairwise distances. Yet unfortunately, for most natural clustering objectives, finding the optimal solution to the objective function is NP-hard. As a consequence, there has been substantial work on approximation algorithms with both upper and lower bounds on the approximability of these objective functions on worst case instances.

Recently, Bilu and Linial suggested an exciting, alternative approach aimed at understanding the complexity of clustering instances which arise in practice. Motivated by the fact that distances between data points in clustering instances are often based on a heuristic measure, they argue that interesting instances should be resilient to small perturbations in these distances. In particular, if small perturbations can cause the optimum clustering for a given objective to change drastically, then that probably is not a meaningful objective to be optimizing. Bilu and Linial specifically define an instance to be $\alpha$-perturbation resilientBilu and Linial refer to such instances as perturbation stable instances. for an objective $\Phi$ if perturbing pairwise distances by multiplicative factors in the range $[1,\alpha]$ does not change the optimum clustering under $\Phi$. They consider in detail the case of Max-Cut clustering and give an efficient algorithm to recover the optimum when the instance is resilient to perturbations on the order of $\alpha>\min\{n/2,\sqrt{n\Delta}\}$ where $\Delta$ is the maximal degree of the graph. They also give an efficient algorithm for unweighted Max-Cut instances that are resilient to perturbations on the order of $\alpha\geq 4n/\delta$ where $\delta$ is the minimal degree of the graph.

Two important questions raised by the work of Bilu and Linial are: (1) the degree of resilience needed for their algorithm to succeed is quite high: can one develop algorithms for important clustering objectives that require much less resilience? (2) the resilience definition requires the optimum solution to remain exactly the same after perturbation: can one succeed under weaker conditions? In the context of center-based clustering objectives such as $k$-median and $k$-center, Awasthi et al. partially address the first of these questions and show that an algorithm based on the single-linkage heuristic can be used find the optimal clustering for $\alpha$-perturbation-resilient instances for $\alpha=3$. They also conjecture it to be NP-hard to beat $3$ and prove beating $3$ is NP-hard for a related but weaker notion (see the $\alpha$-center proximity property in Definition 5).

In this work, we address both questions raised by and additionally improve over . First, for the center-based objectives we design a polynomial time algorithm for finding the optimum solution for instances resilient to perturbations of value $\alpha=1+\sqrt{2}$, thus beating the previously best known factor of $3$ of Awasthi et al . Second, for $k$-median (which is a specific center-based objective), we consider a weaker, relaxed, and more realistic notion of perturbation-resilience where we allow the optimal clustering of the perturbed instance to differ from the optimal of the original in a small $\epsilon$ fraction of the points. Compared to the original perturbation resilience assumption, this is arguably a more natural though also more difficult condition to deal with. We give positive results for this case as well, showing for somewhat larger values of $\alpha$ that we can still achieve a near-optimal clustering on the given instance (see Section 1.1 below for precise results). We additionally give positive results for min-sum clustering which is typically a harder objective than center-based objectives from approximability standpoint. For example, the best known guarantee for min-sum clustering on worst-case instances is an $O(\upsilon^{-1}\log^{1+\upsilon}n)$-approximation algorithm that runs in time $n^{O(1/\upsilon)}$ for any $\upsilon>0$ due to Bartal et al. ; by contrast, the best guarantee known for $k$-median is factor $1+\sqrt{3}+\epsilon$ for any $\epsilon>0$.

Our results are achieved by carefully deriving structural properties of perturbation resilience. At a high level, all the algorithms we introduce work by first running appropriate linkage procedures to produce a hierarchical clustering, and then running dynamic programming to retrieve the best $k$-clustering present in the tree. To ensure that (under perturbation resilient instances) the hierarchy output in the first step has a pruning of low cost, we derive new linkage procedures (closure linkage and robust average linkage) which are of independent interest. While the overall analysis is quite involved, the clustering algorithms we devise are simple and robust. This simplicity and robustness allow us to show how our algorithms can be made sublinear-time by returning an implicit clustering from only a small random sample of the input.

From a learning theory perspective, the resilience parameter, $\alpha$, can also be seen as an analog to a margin for clustering. In supervised learning, the margin of a data point is the distance, after scaling, between the data point and the decision boundary of its classifier, and many algorithms have stronger guarantees when the smallest margin over the entire data set is sufficiently large . The $\alpha$ parameter, similarly controls the magnitude of the perturbation the data can withstand before being clustered differently, which is, in essence, the data’s distance to the decision boundary for the given clustering objective. Hence, perturbation resilience is also a natural and interesting assumption to study from a learning theory perspective.

In this paper, we advance the line of work of by solving several important problems of clustering perturbation-resilient instances under metric center-based and min-sum objectives.

In Section 3 we improve on the bounds of for $\alpha$-perturbation resilient instances for center-based objectives, giving an algorithm that efficientlyFor clarity, in this paper efficient means polynomial in both $n$ (the number of points) and $k$ (the number of clusters). finds the optimum clustering for $\alpha=1+\sqrt{2}$. Most of the frequently used center-based objectives, such as $k$-median, are NP-hard to even approximate, yet we can recover the exact solution for perturbation resilient instances. Our algorithm is based on a new linkage procedure using a new notion of distance (closure distance) between sets that may be of independent interest.

In Section 4 we consider the more challenging and more general notion of $(\alpha,\epsilon)$-perturbation resilience for $k$-median, where we allow the optimal solution after perturbation to be $\epsilon$-close to the original. We provide an efficient algorithm which for $\alpha>2+\sqrt{3}$ produces $(1+O(\epsilon/\rho))$-approximation to the optimum, where $\rho$ is the fraction of the points in the smallest cluster. The key structural property we derive and exploit is that, except for $\epsilon n$ bad points, most points are $\alpha$ times closer to their own center than to any other center. To eliminate the noise introduced by the bad points, we carefully partition the points into a list of sufficiently large blobs, each of which contains only good points from one optimal cluster. This then allows us to construct a tree on the blobs with a low-cost pruning that is a good approximation to the optimum.

In Section 5 we provide the first efficient algorithm for optimally clustering $\alpha$-perturbation resilient min-sum instances. We show that when $\alpha$ in the order of the ratio between the sizes of the largest and smallest clusters, there exists an algorithm that can output the optimal clustering in polynomial time. Our algorithm is based on an appropriate modification of average linkage that exploits the structure of min-sum perturbation resilient instances.

We also provide sublinear-time algorithms both for the $k$-median and min-sum objectives (Sections 4.3 and 5.1), showing algorithms that can return an implicit clustering from only access to a small random sample.

Several recent papers have showed how to exploit the structure of perturbation resilient instances in order to obtain better approximation guarantees (than those possible on worst case instances) for other difficult optimization problems. These include the game theoretic problem of finding Nash equilibria and the classic traveling salesman problem .

In the context of objective based clustering, several recent papers have showed how to exploit other notions of stability for overcoming the existing hardness results on worst case instances. The ORSS stability notion of Ostrovsky, Rabani, Schulman and Swamy assumes that the cost of the optimal $k$-means solution is small compared to the cost of the optimal $(k-1)$-means solution. The BBG $(c,\epsilon)$-approximation stability condition of Balcan, Blum and Gupta assumes that every $c$-approximation solution is close to the target clustering. We note that when the target clustering is the optimal clustering for the clustering objective, $(c,\epsilon)$-approximation stability implies $(c,\epsilon)$-perturbation resilience.

Awasthi, Sheffet and Blum proposed a stability condition called weak-deletion stability, and showed that it is implied by both the ORSS stability and the BBG stability. Kumar and Kannan proposed a proximity condition which assumes that in the target clustering, most data points satisfy that they are closer to their center than to any other center by an additive factor in the order of the maximal standard variance of their clusters in any direction. Their results are improved by Awasthi and Sheffet , which proposed a weaker version of the proximity condition called center separation, and designed algorithms achieving stronger guarantees under this weaker condition. These notions are not directly comparable to the perturbation resilience property.

Notation and Preliminaries

Note that in the definition, $d^{\prime}$ need not be a metric. Also note that the definition depends on the objective. In this paper, we focus on the center-based and min-sum objectives. For the center-based objectives, we consider separable center-based objectives defined by .

A clustering objective is center-based if the optimal solution can be defined by $k$ points $c_{1},\cdots,c_{k}$ in the metric space called centers such that every data point is assigned to its nearest center. Such a clustering objective is separable if it furthermore satisfies the following two conditions:

The objective function value of a given clustering is either a (weighted) sum or the maximum of the individual cluster scores.

Given a proposed single cluster, its score can be computed in polynomial time.

One particular center-based objective is the $k$-median objective. We partition $S$ into $k$ disjoint subsets $\mathcal{P}=\{P_{1},P_{2},\dots,P_{k}\}$ and assign a set of centers $\mathbf{p}=\{p_{1},p_{2},\dots,p_{k}\}\subseteq S$ for the subsets. The objective is $\Phi(\mathcal{P},\mathbf{p})=\sum_{i=1}^{k}\sum_{p\in P_{i}}d(p,p_{i})$. The centers in the optimal clustering are denoted as $\mathbf{c}=\{c_{1},\dots,c_{k}\}$. Clearly, in an optimal solution, each point is assigned to its nearest center. In such cases, the objective is denoted as $\Phi(\mathbf{c})$.

For the min-sum objective, we partition $S$ into $k$ disjoint subsets denoted as $\mathcal{P}=\{P_{1},P_{2},\dots,P_{k}\}$, and the goal is to minimize $\Phi(\mathcal{P})=\sum_{i=1}^{k}\sum_{p\in P_{i}}\sum_{q\in P_{i}}d(p,q)$. Note that we sometimes denote $\Phi$ as $\Phi_{S}$ in the case where the distinction is necessary, such as in Section 4.3.

In Section 4 we consider a generalization of perturbation resilience where we allow a small difference between the original optimum and the new optimum after perturbation. Formally:

Let $\mathcal{C}$ be the optimal $k$-clustering and $\mathcal{C^{\prime}}$ be another $k$-clustering of a set of $n$ points. We say $\mathcal{C^{\prime}}$ is $\epsilon$-close to $\mathcal{C}$ if $\min_{\sigma\in\mathcal{S}_{k}}\sum_{i=1}^{k}|C_{i}\setminus C^{\prime}_{\sigma(i)}|\leq\epsilon n$, where $\sigma$ is a matching between indices of clusters of $\mathcal{C^{\prime}}$ and those of $\mathcal{C}$.

For simplicity, we assume $\epsilon n$ is an integer and assume that $\min_{i}|C_{i}|$ is known (otherwise, we can simply search over the $n$ possible different values).

α𝛼\alpha-Perturbation Resilience for Center-based Objectives

In this section we show that, for $\alpha\geq 1+\sqrt{2}$, if the clustering instance is $\alpha$-perturbation resilient for center-based objectives, then we can in polynomial time find the optimal clustering. This improves on the $\alpha\geq 3$ bound of and stands in sharp contrast to the NP-Hardness results on worst-case instances. Our algorithm succeeds for an even weaker property, the $\alpha$-center proximity, introduced in .

A clustering instance $(S,d)$ satisfies the $\alpha$-center proximity property 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 $\alpha d(p,c_{i})<d(p,c_{j})$.

Any clustering instance that is $\alpha$-perturbation resilient to center-based objectives also satisfies the $\alpha$-center proximity.

The proof follows easily by constructing a specific perturbation that blows up all the pairwise distances within cluster $C_{i}$ by a factor of $\alpha$. By $\alpha$-perturbation resilience, the optimal clustering remains the same after this perturbation. This then implies the desired result. The full proof appears in . In the remainder of this section, we prove our results for $\alpha$-center proximity, but because it is a weaker condition, our upper bounds also hold for $\alpha$-perturbation resilience.

We begin with some key properties of $\alpha$-center proximity instances.

For any points $p\in C_{i}$ and $q\in C_{j}(j\neq i)$ in the optimal clustering of an $\alpha$-center proximity instance, we have

$d(c_{i},q)>\frac{\alpha(\alpha-1)}{\alpha+1}d(c_{i},p)$,

$d(p,q)>(\alpha-1)\max\{d(p,c_{i}),d(q,c_{j})\}$.

Consequently, when $\alpha\geq 1+\sqrt{2}$, we have

(1) Lemma 6 gives us that $d(q,c_{i})>\alpha d(q,c_{j})$. By the triangle inequality, we have $d(c_{i},c_{j})\leq d(q,c_{j})+d(q,c_{i})<(1+1/\alpha)d(q,c_{i})$. On the other hand, $d(p,c_{j})>\alpha d(p,c_{i})$ and therefore $d(c_{i},c_{j})\geq d(p,c_{j})-d(p,c_{i})>(\alpha-1)d(p,c_{i})$. Combining these inequalities, we get (1).

(2) The proof first appears in , and we include it for completeness. Without loss of generality, we can assume that $d(p,c_{i})\geq d(q,c_{j})$. By the triangle inequality we have $d(p,q)\geq d(p,c_{j})-d(q,c_{j})$. From Lemma 6 we have $d(p,c_{j})>\alpha d(p,c_{i})$. Hence $d(p,q)>\alpha d(p,c_{i})-d(q,c_{j})\geq(\alpha-1)d(p,c_{i})\geq(\alpha-1)d(q,c_{j})$. ∎

Lemma 7 implies for any optimal cluster $C_{i}$, the ball of radius $\max_{p\in C_{i}}d(c_{i},p)$ around the center $c_{i}$ contains only points from $C_{i}$, and moreover, points inside the ball are each closer to the center than to any point outside the ball. Inspired by this structural property, we define the notion of closure distance between two sets as the radius of the minimum ball that covers the sets and has some margin from points outside the ball. We show that any (strict) subset of an optimal cluster has smaller closure distance to another subset in the same cluster than to any subset of other clusters or to unions of other clusters. Using this, we will be able to define an appropriate linkage procedure that, when applied to the data, produces a tree on subsets that will all be laminar with respect to the clusters in the optimal solution. This will then allow us to extract the optimal solution using dynamic programming applied to the tree.

The closure distance $d_{S}(A,A^{\prime})$ between two disjoint nonempty subsets $A$ and $A^{\prime}$ of point set $S$ is the minimum $d\geq 0$ such that there is a point $c\in A\cup A^{\prime}$ satisfying the following requirements:

Note that $d_{S}(A,A^{\prime})=d_{S}(A^{\prime},A)\leq\max_{p,q\in S}d(p,q)$ for any $A$ and $A^{\prime}$. Furthermore, it can be computed in polynomial time.

For $(1+\sqrt{2})$-center proximity instances, Algorithm 1 outputs the optimal clustering in polynomial time.

The proof follows immediately from the following key property of the Phase 1 of Algorithm 1. The details of dynamic programming are presented in Appendix A, and an efficient implementation of the algorithm is presented in Appendix B.

For $(1+\sqrt{2})$-center proximity instances, Algorithm 1 constructs a binary tree $\mathcal{T}$ such that the optimal clustering is a pruning of this tree.

We prove correctness by induction. In particular, assume that our current clustering is laminar with respect to the optimal clustering. That is, for each cluster $A$ in our current clustering and each $C$ in the optimal clustering, we have either $A\subseteq C$, or $C\subseteq A$, or $A\cap C=\varnothing$. This is clearly true at the start. To prove that the merge steps keep the laminarity, we need to show the following: if $A$ is a strict subset of an optimal cluster $C_{i}$, $A^{\prime}$ is a subset of another optimal cluster or the union of one or more other clusters, then there exists $B$ from $C_{i}\setminus A$, such that $d_{S}(A,B)<d_{S}(A,A^{\prime})$.

Our factor of $\alpha=1+\sqrt{2}$ beats the NP-hardness lower bound of $\alpha=3$ of for center-proximity instances. The reason is that the lower bound of requires the addition of Steiner points that can act as centers but are not part of the data to be clustered (though the upper bound of does not allow such Steiner points). One can also show a lower bound for center-proximity instances without Steiner points. In particular for any $\epsilon>0$, the problem of solving $(2-\epsilon)$-center proximity $k$-median instances is NP-hard . There is also a low bound for perturbation resilience. Balcan, Haghtalab and White recently showed that there is no polynomial time algorithm for $k$-center instances under $(2-\epsilon)$-perturbation resilience, unless NP= RP. They also showed that closure linkage solves $k$-center instances under 2-perturbation resilience in polynomial time.

The first condition in our definition of closure distance is similar to the minimax linkage criteria . More precisely, our closure distance definition has two conditions: coverage condition and margin condition. If the margin condition is removed from the definition, then the closure distance reduces to the minimax linkage distance. For our purposes however, the margin condition is crucial — in particular, we can provably argue that when the center promixity condition is satisfied Algorithm 1 produces a tree such that the optimal clustering is a pruning of the tree (Theorem 9).

(α,ϵ)𝛼italic-ϵ(\alpha,\epsilon)-Perturbation Resilience for the k𝑘k-Median Objective

In this section we consider a natural relaxation of the $\alpha$-perturbation resilience, the $(\alpha,\epsilon)$-perturbation resilience property, that requires the optimum after perturbation of up to a multiplicative factor $\alpha$ to be $\epsilon$-close to the original (one should think of $\epsilon$ as sub-constant). We show that if the instance is $(\alpha,\epsilon)$-perturbation resilient with $\alpha>2+\sqrt{3}$, then we can in polynomial time output a clustering that provides a $(1+5\epsilon/\rho)$-approximation to the optimum, where $\rho$ is the fraction of the points in the smallest cluster. Thus this improves over the best worst-case approximation guarantees known when $\epsilon\leq\sqrt{3}\rho/5$ and also beats the lower bound of $(1+1/e)$ on the best approximation achievable on worst case instances for the metric $k$-median objective when $\epsilon\leq\rho/(5e)$.

The key idea is to understand and leverage the structure implied by $(\alpha,\epsilon)$-perturbation resilience. We show that perturbation resilience implies that there exists only a small fraction of points that are bad in the sense that their distance to their own center is not $\alpha$ times smaller than their distance to any other centers in the optimal solution. We then use this bounded number of bad points in our clustering algorithm.

Throughout this section we will assume that $|C_{i}|$ is sufficiently large compared to $\epsilon n$, since for interesting practical clustering instances, one would expect that a large fraction of a optimal cluster will remain the same after small perturbation. The exact bound will be stated explicitly in our main theorems. For now we can simply assume $|C_{i}|>2\epsilon n$ for all $i$.

To understand the structure of $(\alpha,\epsilon)$-perturbation resilience, we need to consider the difference between the optimal clustering $\mathcal{C}$ under $d$ and the optimal clustering $\mathcal{C^{\prime}}$ under a perturbation $d^{\prime}$, defined as $\min_{\sigma\in\mathcal{S}_{k}}\sum_{i=1}^{k}|C_{i}\setminus C^{\prime}_{\sigma(i)}|$. Since $\sum_{i=1}^{k}|C_{i}\setminus C^{\prime}_{\sigma(i)}|\leq\epsilon n$ by assumption, we clearly have separately for each $i$ that $|C_{i}\setminus C^{\prime}_{\sigma(i)}|\leq\epsilon n$. Since $|C_{i}|>2\epsilon n$ this implies that $C^{\prime}_{\sigma(i)}$ is the unique cluster in ${\cal C^{\prime}}$ such that $|C_{i}\cap C^{\prime}_{\sigma(i)}|>\frac{1}{2}|C_{i}|$. Without loss of generality, let us index $\cal C^{\prime}$ so that $\sigma$ is the identity. We denote by $c^{\prime}_{i}$ the center of $C^{\prime}_{i}$.

In the following we introduce the notions of bad points and good points, and then show that under perturbation resilience we do not have too many bad points.

Define bad points for $k$-median to be those that are not $\alpha$ times closer to its own center than to any other center in the optimal clustering. That is,

The other points $G:=S\setminus B$ are called good points. Let $G_{i}:=G\cap C_{i}$ denote the good points in cluster $C_{i}$.

Suppose the clustering instance is $(\alpha,\epsilon)$-perturbation resilient and $\min_{i}|C_{i}|>6\left(\frac{\alpha+1}{\alpha-1}\right)(\epsilon n+\alpha+1)$. Then $|B|\leq\epsilon n$.

Assume for contradiction that $|B|>\epsilon n$. The main idea is to select a subset of $(\epsilon n+1)$ bad points and then construct a specific perturbation so that in the new optimal clustering these (and only these) selected bad points move to new clusters, leading to a clustering that is $\epsilon$ far from the original optimal clustering. This is contradictory to the $(\alpha,\epsilon)$-perturbation resilience property, and thus there are at most $\epsilon n$ bad points.

The selected bad points and the perturbation are defined as follows. Select an arbitrary subset $\hat{B}$ of $(\epsilon n+1)$ bad points from $B$, and let $\hat{B}_{i}=\hat{B}\cap C_{i}$ denote the selected bad points in $C_{i}$. Let $c(p)$ denote the second nearest center for $p\in\hat{B}_{i}$ and the nearest center for $p\in C_{i}\setminus\hat{B}_{i}$. That is, for any $1\leq i\leq k$ and any $p\in C_{i}$, let

The perturbation blows up all distances by a factor of $\alpha$ except for those distances between $p$ and $c(p)$. Formally,

The key challenge in showing the contradiction is to show that $c^{\prime}_{i}=c_{i}$ for all $i$, that is, the optimal centers do not change after the perturbation. Once this is shown it is then immediate that in the optimum clustering under $d^{\prime}$ each point $p$ is assigned to the center $c(p)$, and thus the selected bad points $\hat{B}$ will move from their original optimal clusters and all others will not. So the distance between the new clustering and the original clustering is $|\hat{B}|>\epsilon n$, which is contradictory to the $(\alpha,\epsilon)$-perturbation resilience property.

It will now be convenient to define a few quantities. Let $A_{i}=C_{i}^{\prime}\setminus C_{i}$ (the points added when switching from $C_{i}$ to $C_{i}^{\prime}$), $M_{i}=C_{i}\setminus C_{i}^{\prime}$ (the points removed), $W_{i}=(C_{i}\cap C_{i}^{\prime})\setminus\hat{B}_{i}$ (the common points excluding selected bad points), and $V_{i}=(C_{i}\cap C_{i}^{\prime})\cap\hat{B}_{i}$ (the selected bad points in common). So, $C_{i}=W_{i}\cup V_{i}\cup M_{i}$ and $C_{i}^{\prime}=W_{i}\cup V_{i}\cup A_{i}$. See Figure 3. Note that $|A_{i}|\leq\epsilon n$, $|M_{i}|\leq\epsilon n$, and $|V_{i}|\leq\epsilon n+1$, with the bulk of the points in $W_{i}$.

If $\min_{i}|C_{i}|>(\frac{2}{\alpha-1}+3)\epsilon n+1$, then $c^{\prime}_{i}\neq c_{j}(\forall j\neq i)$.

Assume for contradiction that $c^{\prime}_{i}=c_{j}$. We first need to show $c^{\prime}_{j}\neq c_{l}(\forall l)$. Clearly, $c^{\prime}_{j}\neq c_{j}$, since otherwise, moving all the points in $C^{\prime}_{j}$ to $C^{\prime}_{i}$ will not increase the cost, which violates $(\alpha,\epsilon)$-perturbation resilience. We also know that $c^{\prime}_{j}\neq c_{l}(l\neq j)$ since otherwise, there is $p\in W_{j}$, $d(c_{l},p)=d(c^{\prime}_{j},p)\leq d^{\prime}(c^{\prime}_{j},p)<d^{\prime}(c^{\prime}_{i},p)=d(c_{j},p)$, which contradicts the fact that $p\in C_{j}$.

First, since points in $W_{j}$ are $\alpha$ time closer to $c^{\prime}_{j}$ than to $c_{j}$, the distance between $c^{\prime}_{j}$ and $c_{j}$ is small:

Second, since $c_{j}$ is the optimal center for $C_{j}=W_{j}\cup V_{j}\cup M_{j}$, it should save a lot of cost on $M_{j}$ compared to $c^{\prime}_{j}$, which suggests that $c_{j}$ and $c^{\prime}_{j}$ would be far apart. Formally,

When $|C_{j}|>(\frac{2}{\alpha-1}+3)\epsilon n+1$, we have $(1-1/\alpha)|W_{j}|>(1+1/\alpha)|M_{j}|$. Then Inequalities 3 and 2 lead to $d(c_{j},c^{\prime}_{j})=0$. This means $c_{j}=c^{\prime}_{j}$ which is a contradiction to the assumptions. ∎

Suppose $\min_{i}|C_{i}|>(\frac{2}{\alpha-1}+3)\epsilon n+1$. If $c_{i}\neq c^{\prime}_{i}$, then we have

These translations from $d^{\prime}$ to $d$ can be verified by the definition of $d^{\prime}$. In most cases, $d^{\prime}(\cdot,\cdot)=\alpha d(\cdot,\cdot)$; the only exceptions are the distances between $p$ and $c(p)$. The detailed verification is presented below.

(1) Since $c^{\prime}_{i}\neq c_{i}$, and by Claim 4.1, we know $c^{\prime}_{i}\neq c_{j}(\forall j)$. So we only need to check if $c(c^{\prime}_{i})\in A_{i}$. We have

(2) If $c(c^{\prime}_{i})\not\in A_{i}$, then the inequality is trivial. If $c(c^{\prime}_{i})\in A_{i}$, then

We are now ready to present the complete proofs of the two key claims.

which implies the desired result when $|C_{i}|>5\epsilon n+2\alpha+6$. ∎

For each $i$, if $c_{i}^{\prime}\neq c_{i}$ then $d(c_{i},c^{\prime}_{i})\geq\left(\frac{\alpha-1}{2\alpha}\right)\frac{d(c_{i},W_{i})}{\epsilon n+\alpha+1}.$

On $C_{i}\setminus M_{i}$, the cost of $c_{i}$ is smaller than that of $c_{i}^{\prime}$. Specifically, from (8) we have:

Combining the upper bound of Claim 4.3 with the lower bound of Claim 4.4 when $c_{i}^{\prime}\neq c_{i}$, we get a contradiction for sufficiently large $|C_{i}|$ as given in the theorem statement, yielding $c_{i}^{\prime}=c_{i}$.

The bound in Theorem 12 is optimal in the sense that for any $\alpha>1$ and $0<\epsilon<1/5$, we can easily construct an $(\alpha,\epsilon)$-perturbation resilient $2$-median instance which has $\epsilon n$ bad points.

The instance is shown in Figure 4. It has $3$ groups of points: $G_{1},G_{2}$, and $B$. Both $G_{1}$ and $G_{2}$ have $(1-\epsilon)n/2$ points, and $B$ has $\epsilon n$ points. Let $M$ be a sufficiently large constant, say, $M>n^{2}/\epsilon$. The distances within the same group are $1$, while those between the points in $G_{1}$ and $G_{2}$ are $M$, those between the points in $B$ and $G_{1}$ are $\frac{M}{\alpha+1}+1$, and those between the points in $B$ and $G_{2}$ are $\frac{\alpha M}{\alpha+1}-1$. The instance satisfies the triangle inequality, which can be verified by a case analysis. The optimal clustering before perturbation has one center in $G_{1}$ and the other in $G_{2}$. Then $B$ are trivially bad points, and thus we have $\epsilon n$ bad points in this instance.

Now we show that the instance is $(\alpha,\epsilon)$-perturbation resilient. To prove that the optimal clustering after perturbation $\mathcal{C}^{\prime}$ is $\epsilon$-close to the original optimal clustering, it suffices to show that $\mathcal{C}^{\prime}$ has one center from $G_{1}\cup B$ and the other center from $G_{2}$. Assume for contradiction that this is not true. If both centers come from $G_{2}$, the cost of points in $G_{1}$ is $\frac{(1-\epsilon)n}{2}M$. On the other hand, the optimal cost before perturbation is $(1-\epsilon)n-2+\epsilon n(\frac{M}{\alpha+1}+1)$, so the optimal cost after perturbation is no more than $\alpha((1-\epsilon)n-2+\epsilon n(\frac{M}{\alpha+1}+1))$. But this is smaller than $\frac{(1-\epsilon)n}{2}M$, which is a contradiction. Similarly, we get a contradiction if both centers come from $G_{1}\cup B$.

2 Approximation Bound

Now, we consider the problem of approximating the cost of the optimum clustering. We can see that after removing the bad points, the optimal clusters are far apart from each other. In order to get rid of the influence of the bad points, we generate a list of blobs, which form a partition of the data points, and each of which contains only good points from one optimal cluster. Then we construct a tree on the list of blobs with a pruning that assigns all good points correctly. We will show that this pruning has low cost, so the lowest cost pruning of the tree is a good approximation. The details are described in Algorithm 2.

A key step is to generate the list of almost “pure” blobs, which is described in Algorithm 3. Suppose for any $i$ and any good point $p\in G_{i}$, its $\gamma|G_{i}|$ nearest neighbors contain no good points outside $C_{i}$. Also suppose the algorithm knows the value of $\gamma$. Informally, the algorithm maintains a threshold $t$. At each threshold, for each point $p$ that has not been added to the list, the algorithm checks its $\gamma t$ nearest neighbors $N_{\gamma t}(p)$. It constructs a graph $F_{t}$ by connecting any two points that have sufficiently many common neighbors. It then builds another graph $H_{t}$ by connecting any two points that have sufficiently many common neighbors in $F_{t}$, and adds sufficiently large components in $H_{t}$ to the list. Finally, for each remaining point $p$, it checks if most of $p$’s neighbors are in the list and if there are blobs containing a significant amount of $p$’s neighbors. If so, it inserts $p$ into such a blob with the smallest median distance. Then the threshold is increased and the above steps are repeated.

The intuition behind Algorithm 3 is as follows. As mentioned above, the algorithm works when for any $i$ and any good point $p\in G_{i}$, the $\gamma|G_{i}|$ nearest neighbors of $p$ contain no good points outside $C_{i}$ ($\gamma=1$ for the $k$-median instances considered in this section, as shown in Lemma 13; $\gamma=\frac{4}{5}$ for the min-sum instances considered in Section 6, as shown in Claim 6.3). Without loss of generality, assume $|C_{1}|\leq|C_{2}|\leq\dots\leq|C_{k}|$. When $t\leq|C_{1}|$, good points in different clusters do not have most neighbors in common and thus are not connected in $F_{t}$. However, they may be connected by a path of bad points. So we further build the graph $H_{t}$ to disconnect such paths, which ensures that the blobs added into the list contain only good points from one optimal cluster. The final insert step (Step 6) makes sure that when $t=|C_{1}|$, all remaining good points in $C_{1}$ will be added to the list and will not affect the construction of blobs from other optimal clusters. We can show by induction that, at the end of the iteration $t=|C_{i}|$, all good points in $C_{j}(j\leq i)$ are added to the list. When $t$ is large enough, any remaining bad points are inserted into the list, so the points are partitioned into a list of almost pure blobs. The formal guarantee for Algorithm 3 is stated in Lemma 14.

In the following, we prove that Algorithm 2 outputs a good approximation. We first prove a key property of the good points in $(\alpha,\epsilon)$-perturbation resilience instances in Lemma 13 and show in Lemma 14 that the property ensures the success of Algorithm 3, and then prove a property of the bad points in Lemma 15. Finally, we use these lemmas to prove the approximation bound in Theorem 16.

When $\alpha>2+\sqrt{3}$, for any good points $p_{1},p_{2}\in G_{i},q\in G_{j}(j\neq i)$, we have $d(p_{1},p_{2})<d(p_{1},q)$. Consequently, for any good point $p\in G_{i}$, all its $|G_{i}|$ nearest neighbors belong to $C_{i}\cup B$.

The following proof is implicit in and we include it for completeness. We rephrase it slightly so that it is more intuitive. By the triangle inequality and the definition of good points,

Now, to compare $d(p_{1},q)$ and $d(p_{1},p_{2})$, we need to get rid of the extra terms $d(q,c_{j})$ and $d(p_{1},c_{i})$. By the same proof in Lemma 7(2),

So when $\alpha>2+\sqrt{3}$, $d(p_{1},q)>d(p_{1},p_{2})$. ∎

Suppose the number of bad points is bounded by $u_{B}$, and for any $i$ and any good point $p\in G_{i}$, all its $\gamma|G_{i}|$ nearest neighbors in $S$ are from $C_{i}\cup B$. If $\min_{i}|C_{i}|>30u_{B}$, then Algorithm 3 generates a list $\mathcal{L}$ of blobs each of size at least $\frac{1}{2}\min_{i}|C_{i}|$ such that:

The blobs in $\mathcal{L}$ form a partition of $S$.

Each blob in $\mathcal{L}$ contains good points from only one optimal cluster.

Without loss of generality, assume $|C_{1}|\leq|C_{2}|\leq\dots\leq|C_{k}|$. We prove the following two claims by induction on $i\leq k$:

For any $t\leq|G_{i}|$, any blob in the list $\mathcal{L}$ only contains good points from only one optimal cluster; all blobs have size at least $\frac{1}{2}\min_{i}|C_{i}|$.

At the beginning of the iteration $t=|G_{i}|+1$, any good point $p\in G_{j},j\leq i$ has already been assigned to a blob in the list that contains good points only from $C_{j}$.

The first two claims imply that each blob in the list contains good points from only one optimal cluster. Moreover, at the beginning of the iteration $t=|G_{k}|+1$, all good points have been assigned to one of the blobs in $\mathcal{L}$, so there are only bad points left, the number of which is smaller than $\frac{1}{2}\min_{i}|C_{i}|$. These remaining points will eventually be assigned to the blobs before $\gamma t>n$, so the blobs form a partition of $S$.

The claims are clearly both true initially. We show now that as long as $t\leq|G_{1}|$, the graphs $F_{t}$ and $H_{t}$ have the following properties.

No good point $p_{i}$ in cluster $C_{i}$ is connected in $F_{t}$ to a good point $p_{j}$ in a different cluster $C_{j}$. By assumption, $p_{i}$ has no neighbors outside $C_{i}\cup B$ and $p_{j}$ has no neighbors outside $C_{j}\cup B$, so they share at most $u_{B}<(2\gamma-1)t-2u_{B}$ neighbors.

No point $q$ is connected in $F_{t}$ to both a good point $p_{i}$ in $C_{i}$ and a good point $p_{j}$ in a different cluster $C_{j}$. If $q$ is connected to $p_{i}$, then $|N_{\gamma t}(p_{i})\cap N_{\gamma t}(q)|>(2\gamma-1)t-2u_{B}$. Since $p_{i}$ has no neighbors outside $C_{i}\cup B$, $N_{\gamma t}(q)$ contains more than $(2\gamma-1)t-3u_{B}\geq\gamma t/2$ points from $G_{i}$. Similarly, if $q$ is connected to $p_{j}$, then $N_{\gamma t}(q)$ contains more than $\gamma t/2$ points from $G_{j}$, which is contradictory. Thus, the graph $F_{t}$ looks like the illustration in Figure 5.

All the components in $H_{t}$ of size at least $\frac{1}{2}\min_{i}|C_{i}|$ will only contain good points from one optimal cluster. As there are at most $u_{B}$ bad points, any two points connected in $H_{t}$ must be connected in $F_{t}$ to at least one good point. Then by the above two properties, points on a path in $H_{t}$ must be connected in $F_{t}$ to good points in the same cluster, so there is no path connecting good points from different clusters.

We can use the three properties to argue the first claim: as long as $t\leq|G_{1}|$, each blob in $\mathcal{L}$ contains good points from at most one optimal cluster. This is true at the beginning and by the third property, for any $t\leq|G_{1}|$, anytime we insert a whole new blob in the list in Step 5, that blob must contain point from at most one optimal cluster. We now argue that this property is never violated as we assign points to blobs already in the list in Step 6. Suppose a good point $p\in C_{i}$ is inserted into $C\in\mathcal{L}$. Then $C\in\mathcal{L}_{p}$, which means $|N_{\gamma t}(p)\cap C|\geq|C|/5>u_{B}$. So $N_{\gamma t}(p)\cap C$ contains at least one good point, which must be from $C_{i}$ since $N_{\gamma t}(p)$ contains no good points outside $C_{i}$. Then by induction $C$ must contain only good points from $C_{i}$, and thus adding $p$ to $C$ does not violate the first claim.

We now show the second claim: after the iteration $t=|G_{1}|$, all the good points in $C_{1}$ have already been assigned to a blob in the list that only contains good points from $C_{1}$. There are two cases. First, if at the beginning of the iteration $t=|G_{1}|$, there are still at least $\frac{1}{2}\min_{i}|C_{i}|$ points from the good point set $G_{1}$ that do not belong to blobs in the list. Any such good point has all $\gamma|G_{1}|$ neighbors in $C_{1}\cup B$. Then any two such good points share at least $2\gamma|G_{1}|-|C_{1}\cup B|\geq(2\gamma-1)|G_{1}|-|B|\geq(2\gamma-1)t-2u_{B}$ neighbors. So they will connect to each other in $F_{t}$ and then in $H_{t}$, and thus we will add one blob to $\mathcal{L}$ containing all these points. Second, it could be that at the beginning of the iteration $t=|G_{1}|$, all but less than $\frac{1}{2}\min_{i}|C_{i}|$ good points in $G_{1}$ have been assigned to a blob in the list. Denote the points that have not yet been assigned as $E$. Any point $p\in E$ has no neighbors outside $C_{1}\cup B$. Then $|N_{\gamma t}(p)\setminus\mathcal{L}|\leq|E|+|B|\leq\frac{1}{2}\min_{i}|C_{i}|+2u_{B}$. Also, there exists a blob $C$ containing good points from $C_{1}$ such that $C\in\mathcal{L}_{p}$. Otherwise, $N_{\gamma t}(p)$ contains at most $(\gamma-\frac{3}{5})(|C_{1}\cup B|)<\gamma|C_{1}|-\frac{1}{2}|C_{1}|-2u_{B}$ points in $C_{1}\cap\mathcal{L}$, while it contains at most $|E|$ good points in $C_{1}\setminus\mathcal{L}$ and contains no points outside $C_{1}\cup B$. In total, $N_{\gamma t}(p)$ has less than $\gamma t$ points, which is contradictory. So $\mathcal{L}_{p}\neq\emptyset$ and $p$ will be added to the list in Step 6.

We then iterate the argument on the remaining set $A_{S}$. The key point is that for $t\geq|G_{i}|,i>1$, we have that all the good points in $C_{1},C_{2},\dots,C_{i}$ have already been assigned to blobs in $\mathcal{L}$. ∎

Lemma 13 and 14 show that Algorithm 3 with parameters $u_{B}=\epsilon n$ and $\gamma=1$ produces a list of sufficiently large, almost pure blobs. Then the robust linkage procedure in can build a tree on these blobs with a pruning that assigns all good points correctly. Now it suffices to show that this pruning is a good approximation, for which we need to bound the cost increased by the bad points assigned incorrectly. The following property of these bad points turns out to be useful. Intuitively, Algorithm 3 is designed such that whenever a bad point is added to a blob containing good points from a different cluster, it must be closer to a significant number of points in that cluster than to a significant number of points in its own cluster. Then the cost increased by incorrectly assigning each such bad point is small, resulting in a good approximation.

Suppose for any good point $p\in G_{i}$, all its $|G_{i}|$ nearest neighbors in $S$ are from $C_{i}\cup B$, and $\min_{i}|C_{i}|>30u_{B}$. When running Algorithm 3 with $\gamma=1$, if a bad point $q\in B_{i}$ is assigned to a blob $C$ containing good points from a different optimal clustering $C_{j}$, then there exist $m=\frac{1}{5}\min_{i}|C_{i}|$ points $Z_{i}$ from $C_{i}$, and $m$ points $Z_{j}$ from $C_{j}$, such that $d(q,Z_{i})\geq d(q,Z_{j})$.

There are two cases: $q$ is added into $C$ in (1) Step 5 or (2) Step 6.

There must be a path in $H_{t}$ connecting $q$ to a good point in $C_{j}$ at threshold $t$. For any edge $(x,y)$ in $H_{t}$, since $x,y$ share at least $\epsilon n$ neighbors in $F_{t}$ and there are at most $\epsilon n$ bad points, they share at least one good point as neighbor in $F_{t}$. As shown in the proof of Lemma 14, no point can connect to good points from different clusters, so in $F_{t}$ all points on the path must connect to good points in $C_{j}$. In particular, $q$ is connected in $F_{t}$ to a good point $p\in G_{j}$. Then $|N_{t}(p)\cap N_{t}(q)|>t-2u_{B}$. Since $p$ is still in $A_{S}$, $t\leq|G_{j}|$, and thus $N_{t}(p)$ contains no points outside $C_{j}\cup B$. This means that at least $t-3u_{B}\geq m$ points in $N_{t}(q)$ are good points in $C_{j}$, then we can select $m$ points $Z_{j}$ from $N_{t}(q)\cap G_{j}$. We also have that at most $2u_{B}$ points in $N_{t}(q)$ are points in $C_{i}$, so we can select $m$ points $Z_{i}$ from $C_{i}\setminus N_{t}(q)$.

There are three subcases when $q$ is inserted into $C$ at threshold $t$.

There is no good points from $C_{i}$ in the list. Since $|N_{t}(q)\setminus\mathcal{L}|\leq\frac{1}{2}\min_{i}|C_{i}|+2u_{B}$, $N_{t}(q)$ contains at most this number of good points in $C_{i}$. This means at least $\frac{1}{2}\min_{i}|C_{i}|-2u_{B}>m$ good points in $C_{i}$ are outside $N_{t}(q)$, from which we can select $Z_{i}$. On the other hand, we can select $Z_{j}$ as follows. When inserting $q$ into $C$, we have $|N_{t}(q)\cap C|\geq\frac{2}{5}|C|\geq m+u_{B}$. Since $C$ contains only good points from $C_{j}$ and some bad points, $N_{t}(q)\cap C$ contains at least $m$ good points in $C_{j}$, from which we can select $Z_{j}$. Since $Z_{j}$ are from $N_{t}(q)$ and $Z_{i}$ are outside $N_{t}(q)$, we have $d(q,Z_{i})\geq d(q,Z_{j})$.

There exists $C^{\prime}\in\mathcal{L}$ containing good points from $C_{i}$, but $C^{\prime}\not\in\mathcal{L}_{p}$. This means $|B(q,t)\cap C^{\prime}|\leq\frac{2}{5}|C^{\prime}|$, so there are at least $\frac{3}{5}|C^{\prime}|\geq m+u_{B}$ points in $C^{\prime}$ are outside $N_{t}(q)$. At least $m$ of these points are good points from $C_{i}$, since $C^{\prime}$ contains only good points from $C_{i}$ and at most $u_{B}$ bad points. So, we can select $Z_{i}$ from them. On the other hand, we can select $Z_{j}$ as in the first subcase.

There exists $C^{\prime}\in\mathcal{L}_{p}$ containing good points from $C_{i}$. Since $q$ is assigned to $C$ rather than $C^{\prime}$ according to median distances, we know that at least half of the points $Z^{\prime}_{j}$ from $C$ are closer to $q$ than at least half of the points $Z^{\prime}_{i}$ from $C^{\prime}$. Since there are at most $u_{B}$ bad points, we can select $m$ good points $Z_{j}$ from $Z^{\prime}_{j}$ and select $m$ good points $Z_{i}$ from $Z^{\prime}_{i}$. Note that $Z_{j}$ are all from $G_{j}$ and $Z_{i}$ are all from $G_{i}$, so $d(q,Z_{i})\geq d(q,Z_{j})$.

Therefore, the statement is true in all cases. ∎

If the clustering instance is $(\alpha,\epsilon)$-perturbation resilient for $\alpha>2+\sqrt{3}$ and $\epsilon\leq\rho/30$ where $\rho=\frac{\min_{i}|C_{i}|}{n}$, then Algorithm 2 produces a clustering which is $(1+\frac{5\epsilon}{\rho})$-approximation to the optimal clustering with respect to the $k$-median objective in polynomial time.

By Lemma 13 and 14, Algorithm 3 partitions the points into a list of blobs, each of which has size at least $\frac{1}{2}\min_{i}|C_{i}|$ and contains only good points from one optimal cluster. Let $B^{\prime}_{i}$ denote the bad points that are assigned to blobs containing good points in $C_{i}$. By Lemma 13, Theorem 9 in can be applied to $\mathcal{L}$, by which we know that $\{(C_{i}\cap G)\cup B^{\prime}_{i}\}$ is a pruning of the tree. Suppose the cost of the optimum is $\mathcal{OPT}$. We now show that this pruning, using the original centers $\{c_{i}\}$, is a $(1+\frac{5\epsilon}{\rho})$-approximation to $\mathcal{OPT}$.

Suppose a bad point $q\in C_{i}$ is assigned to a blob $C$ containing good points from a different optimal cluster $C_{j}$. By Lemma 15, there exist $m=\frac{1}{5}\min_{i}|C_{i}|$ points $Z_{i}$ from $C_{i}$, and $m$ points $Z_{j}$ from $C_{j}$, such that $d(q,Z_{i})\geq d(q,Z_{j})$. Then the increase in cost due to $q$ is bounded as follows:

As there are at most $\epsilon n$ bad points and $m=\frac{\min_{i}|C_{i}|}{5}$, the increase of cost is at most $\frac{\epsilon n}{m}\mathcal{OPT}=\frac{5\epsilon}{\rho}\mathcal{OPT}$.

In Algorithm 3, for each $p\in S$, we first sort all the other points in ascending order of distances in time $O(n^{2}\log n)$. At each threshold $t$, think of a directed $t$-regular graph $E_{t}$, where, for each point $q$ in the $t$ nearest neighbors of a point $p$, there is a directed edge from $p$ to $q$ in $E_{t}$. Let $A_{E}$ denote the adjacency matrix for $E_{t}$, and let $N=A_{E}A^{\top}_{E}$. Then $N_{pq}$ is the number of common neighbors between $p$ and $q$, which can be used in constructing $F_{t}$. Computing $N$ takes time $O(n^{\omega})$, where $\omega$ is the matrix multiplication exponent. The same method can be used to compute the number of common neighbors in $F_{t}$ and construct $H_{t}$. Since there are $O(n)$ thresholds, the total time for constructing $F_{t}$ and $H_{t}$ is $O(n^{\omega+1})$. For the other steps, adding a blob takes time $O(n^{2})$ and inserting a point takes time $O(n^{2})$. These steps can be performed at most $O(n)$ times, so they take $O(n^{3})$ time. In total, Algorithm 3 takes time $O(n^{\omega+1})$. Since the robust linkage algorithm takes time at most $O(n^{\omega+1})$, and the dynamic programming takes time $O(n^{3})$ (Appendix A), the running time of Algorithm 2 is $O(n^{\omega+1})$. ∎