# Combinatorial Correlation Clustering

Vincent Cohen-Addad Google Research. Email<EMAIL_ADDRESS>David
Rasmussen Lolck University of Copenhagen. Email<EMAIL_ADDRESS>Marcin
Pilipczuk University of Warsaw. Email<EMAIL_ADDRESS>Mikkel Thorup
University of Copenhagen. Email<EMAIL_ADDRESS>Shuyi Yan University of
Copenhagen. Email<EMAIL_ADDRESS>Hanwen Zhang University of Copenhagen.
Email<EMAIL_ADDRESS>
Correlation Clustering is a classic clustering objective arising in numerous
machine learning and data mining applications. Given a graph $G=(V,E)$, the
goal is to partition the vertex set into clusters so as to minimize the number
of edges between clusters plus the number of edges missing within clusters.

The problem is APX-hard and the best known polynomial time approximation
factor is 1.73 by Cohen-Addad, Lee, Li, and Newman [FOCS’23]. They use an LP
with $|V|^{1/\epsilon^{\Theta(1)}}$ variables for some small $\epsilon$.
However, due to the practical relevance of correlation clustering, there has
also been great interest in getting more efficient sequential and parallel
algorithms.

The classic combinatorial _pivot_ algorithm of Ailon, Charikar and Newman
[JACM’08] provides a 3-approximation in linear time. Like most other
algorithms discussed here, this uses randomization. Recently, Behnezhad,
Charikar, Ma and Tan [FOCS’22] presented a $3+\epsilon$-approximate solution
for solving problem in a constant number of rounds in the Massively Parallel
Computation (MPC) setting. Very recently, Cao, Huang, Su [SODA’24] provided a
2.4-approximation in a polylogarithmic number of rounds in the MPC model and
in $\tilde{O}(|E|^{1.5})$ time in the classic sequential setting. They asked
whether it is possible to get a better than 3-approximation in near-linear
time?

We resolve this problem with an efficient combinatorial algorithm providing a
drastically better approximation factor. It achieves a $\sim
2-2/13<1.847$-approximation in sub-linear ($\tilde{O}(|V|)$) sequential time
or in sub-linear ($\tilde{O}(|V|)$) space in the streaming setting, and it
uses only a constant number of rounds in the MPC model.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Techniques
    3. 1.3 Further Related Work
  2. 2 Preliminaries
    1. 2.1 Sublinear, streaming and MPC models
  3. 3 Local Search with Flips
    1. 3.1 Warm-up: $(2-\frac{1}{8})$-approximation
    2. 3.2 Iterative version of local search
  4. 4 Polynomial-Time Implementation of Local Search
  5. 5 Faster Implementation of Local Search
  6. 6 MPC implementation of local search
  7. 7 Sublinear and Streaming Implementations of Local Search
  8. 8 Acknowledgements

##  1 Introduction

Correlation clustering is a fundamental clustering objective that models a
large number of machine learning and data mining applications. Given a set of
data elements, represented as vertices $V$ in a graph $G$, and a set of pairs
of similar elements, represented as edges $E$ in the graph, the goal is to
find a partition of the vertex sets that minimizes the number of missing edges
within the parts of the partition plus the number of edges across the parts of
the partition. An alternative formulation is that we want a graph consisting
of disjoint cliques, minimizing the symmetric difference to the input graph.
Below $n=|V|$ and $m=|E|$.

The problem was originally introduced by Bansal, Blum, and Chawla in the early
2000 [6] and has since then found a large variety of applications ranging from
finding clustering ensembles [12], duplicate detection [4], community mining
[30], disambiguation tasks [33], to automated labelling [3, 22] and many more.

Thanks to its tremendous modelling success, Correlation clustering has been
widely studied in the algorithm design, machine learning and data mining
communities. From a complexity standpoint, the problem was shown to be APX-
Hard [18] and Bansal, Blum, and Chawla [6] gave the first $O(1)$-approximation
algorithm. The constant was later improved to 4 by Charikar, Guruswami, and
Wirth [18].

In a landmark paper, Ailon, Charikar and Newman [2] gave two very important
pivot-based algorithms. First, they presented a _combinatorial_ – in the sense
that it does not rely on solving a linear program – pivot algorithm that
iteratively picks a random vertex uniformly at random in the set of
unclustered vertices and clusters it with all its unclustered neighbors. They
showed that this algorithm achieves a 3 approximation (and their analysis is
tight). Next, they improved the approximation factor to 2.5 using a standard
linear program (LP) which was shown to have an integrality gap of at least 2.
They still used a random pivot, but instead of creating a cluster containing
all the unclustered neighbors of the pivot, they randomly assigned each vertex
to the cluster of the pivot based on the LP solution.

A better rounding of this LP of Ailon, Charikar and Newman [2] was later
presented by Chawla, Makarychev, Schramm and Yaroslavtev [29] who achieved a
2.06-approximation still relying on a pivot-based approach to round, hence
coming close to a nearly-optimal rounding given its integrality gap of at
least 2.

Since the integrality gap of this LP is at least 2, 2 has appeared as a strong
barrier for approximating Correlation Clustering, and 3 has remained the best-
known non-LP-based algorithm to this day. Recently, different LP formulations
have been used to get better than 2 approximations. Cohen-Addad, Lee and
Newman [26] showed that the Sherali-Adams hierarchy helps bypass the standard
LP integrality gap of 2 by providing a $1.995$ approximation which was very
recently improved to $1.73$ by Cohen-Addad, Lee, Li and Newman [23] using a
new linear programming formulation and relying on the Sherali-Adams hierarchy
too. However, these improvements have happened at an even greater
computational cost: While the pivot-rounding algorithm required to solve a
linear program on $n^{2}$ variables, the above two algorithms require
$n^{1/\epsilon^{\Theta(1)}}$ variables and running time for some small
$\epsilon$.

#### Efficient algorithms

Motivated by the large number of applications in machine learning and data
mining applications, researchers have put an intense effort in _efficiently_
approximating Correlation Clustering: From obtaining linear time algorithm
[2], to dynamic algorithms [10], distributed (Map-Reduce or Massively Parallel
Computation (MPC) models) [7, 24], streaming [8, 27, 21, 5, 24], or sublinear
time [5]. In most of these models, the LP-based approaches have remained
unsuccessful and the state-of-the-art algorithm remains the combinatorial
pivot algorithm. Arguably, the modularity and simplicity of the combinatorial
pivot algorithm and its analysis have been key to obtaining these results.

Thus, the question of _how fast and well and in which model_ one can
approximate Correlation Clustering better than a factor 3 has naturally
emerged. At one end of the spectrum, we have the above $1.73$ in time
$n^{1/\epsilon^{\Theta(1)}}$. At the other end of the spectrum, Cohen-Addad,
Lattanzi, Mitrovic, Norouzi-Fard, Parotsidis, and Tarnawski [24] and Assadi
and Wang [5] showed that Correlation Clustering can be approximated to an
$O(1)$-factor in linear time (i.e.: $O(m)$ time) and in fact in sublinear time
(i.e.: $n\log^{O(1)}n$) using random sampling of neighbors. However, the
constant proven in these works is larger than 500. In a very recent work, [19]
showed that one can approximately solve and round the standard LP in time
$O(m^{1.5})$ and achieve a $2.4$-approximation, coming close to the linear
time-bound. In the streaming model, [7] gave a $3+\epsilon$-approximation
using $O(1/\epsilon)$ passes. Later [8] gave a 1-pass algorithm achieving a
5-approximation. Very recently, [21] and [28] independently provided a 1-pass
$3+\epsilon$-approximation. [19] thus asks: _How fast and in which models can
one approximate Correlation Clustering within a factor 3 and beyond?_

###  1.1 Our Results

Our main contribution is a novel combinatorial algorithm that we show achieves
a $2-2/13$-approximation. Our new algorithm alternates between performing a
local search and a certain flip. The flip takes all cut edges in the current
solution and aims to make them internal, doing so by increasing the cost of
cutting them in the objective for the next local search. One can think of this
as a very systematic method to escape a bad local minimum, leading to strong
theoretical guarantees.

We highlight that despite the fact that the number of local search iterations
could be close to linear in the worst-case, we show that with a minor loss in
approximation factor, the whole local search can be implemented in near-linear
total time. In fact, using random sampling of neighbors, we can implement it
in sublinear time, improving over the state-of-the-art sublinear-time
$>500$-approximation [5, 24]. On top of that, we can implement it in the MPC
model with a constant number of rounds, and also in the streaming model, as
stated in the following theorem:

######  Theorem 1.

For any $\epsilon>0$, there is an algorithm that w.h.p., achieves a
$2-2/13+\epsilon$-approximation for Correlation Clustering in time
$O(2^{\epsilon^{-O(1)}}n\log n)$, or in space $O(2^{\epsilon^{-O(1)}}n\log n)$
in the streaming setting.

In addition, for any $\delta=\Omega(1)$, this algorithm can be implemented to
terminate in $(\epsilon\delta)^{-O(1)}$ rounds in the MPC model with
$n^{\delta}$ memory per machine and total memory $O(\epsilon^{-O(1)}m\log n)$.

Fixing $\epsilon=0.0008$, we get an approximation factor of
$2-2/13+\epsilon<1.847$ and $2^{\epsilon^{-O(1)}}=O(1)$ though with a very
large hidden constant. Our approach thus opens up the possibility of achieving
a better than 2 approximation in other models such as streaming, dynamic or
CONGEST, and it is an interesting direction to see whether this can be
achieved.

###  1.2 Techniques

The local search framework we consider maintains a clustering. At each
iteration, the algorithm tries to swap in a cluster (i.e.: a set of vertices
of arbitrary size), creating it as a new cluster and removing its elements
from the clusters they belonged to. The swap is improving if the resulting
clustering has a smaller cost, and we keep doing improving swaps until no more
are found.

Of course, as described above the algorithm would have a running time
exponential in the input size since it for potential swaps needs to consider
all subsets of vertices of the input but let’s first put aside the running
time consideration and focus on the approximation guarantee. We first discuss
that the algorithm achieves a 2-approximation; this serves as a backbone for
our further improvements. We further discuss how we can implement the above
variant of the above algorithm in polynomial time while losing only a
$(1+\epsilon)$ factor in the approximation guarantee.

##### Achieving a 2-approximation using a simple (exponential time) local
search

The analysis of the above algorithm simply consists of the following steps:
Let $S$ be the solution output by the algorithm and Opt the optimum solution.
For each cluster $C$ in Opt we will consider the solution $S_{C}$ which is
created from $S$ by inserting $C$ as a cluster (by creating cluster $C$ and
removing its elements from the clusters they belong to in $S$).

By local optimality, we know that the cost of solution $S$ is no larger than
the cost of the solution $S_{C}$. The difference in cost between the two
solutions is only coming from edges that are adjacent to at least one vertex
in $C$. More concretely, denote by $E^{+}_{S}$ the set of edges cut by $S$ and
by $E^{-}_{S}$ the set of non-edges that are not cut by $S$, i.e.: the cost of
$S$ is equal to $|E^{+}_{S}|+|E^{-}_{S}|$. Then the cost of solution $S_{C}$
minus the cost of solution $S$ is positive and equal to

$\displaystyle 0\leq|\\{(u,v)\mid(u,v)\in E\setminus E^{+}_{S}\text{ and
either }u\text{ or }v\in C\\}|+|\\{(u,v)\mid(u,v)\notin E\cup E^{-}_{S}\text{
and both }u,v\in C\\}|$ $\displaystyle-|\\{(u,v)\mid(u,v)\in E^{+}_{S}\text{
and both }u,v\in C\\}|-|\\{(u,v)\mid(u,v)\in E^{-}_{S}\text{ and either
}u\text{ or }v\in C\\}|$

This statement holds for any cluster $C$ of the optimum solution and so
summing up the above inequality over all these clusters shows that on the
left-hand side, the cost of the local search solution is no more than twice
the cost of the optimum solution. This hence provides a simple (exponential
time) 2 approximation algorithm for Correlation Clustering.

Equipped with the above analysis, our work then moves in two complementary
directions: (1) Improving over the approximation bound of 2 with certain
flips; and (2) showing how to implement the above algorithm while losing at
most a $(1+\epsilon)$ factor in the overall guarantee.

##### Flips between local searches

Let us first focus on (1). When considering the above analysis, one can note
that the factor of 2 arises when summing over all clusters and so each edge
$(u,v)\in E\setminus E^{+}_{S}$ where $u\in C$ and $v\in C^{\prime}\neq C$ in
the optimum solution. Indeed, in this case, the edge $(u,v)$ appears twice in
the sum: once when upper bounding the cost of the vertices in $C$ and once
when upper bounding the cost of the vertices in $C^{\prime}$. On the other
hand, the ratio coming from either the non-edges or the pairs $(u,v)\in
E^{+}_{S}\cup E^{-}_{S}$ that are also paid by Opt is in fact 1.

It follows that the solution $S$ obtained by local search is only close to a 2
approximation if a, say, .99 fraction of the cost of the optimum solution is
due to the edges (and not the non-edges) cut by the optimum solution and that
are not in $E^{+}_{S}$.

Hence, for the ratio of 2 to be tight, the solution $S$, the optimum solution
and the underlying graph must be very peculiar and satisfy the following:

  * •

.99 fraction of the cost of the optimum solution is due to edges (and not non-
edges)

  * •

$S$ and the optimum solution must have at most .01 fraction of their cost
shared (i.e.: intersection of the edges and non-edges paid by the Opt and $S$
must be at most a .01 fraction of their overall cost).

Under our assumptions, we see that Opt and $S$ share very few cut edges, so to
get closer to Opt, it would make sense to _flip_ the cut edges of $S$; seeking
a solution where they are no longer cut. We do this by increasing the cost of
cutting these edges.

The above may seem a bit naive, but it turns out to yield an approximation
factor substantially below 2. More precisely, after having found the first
local search solution $S$, we double the cost of cutting the weight of the cut
edges of $S$. This is called the _flip_. Then we run a new local search on
this modified input; yielding a new local optimum $S^{\prime}$. Finally, we
return the one of $S$ and $S^{\prime}$ that minimizes the original cost.
Magically, it turns out that this local-search-flip-local-search always
provides a $15/8$-approximation. We provide a description of this algorithm
and its approximation ratio as a warm-up in Section 3.1.

##### Iterated-flipping Local Search

We then go one step beyond and analyze the bad instances for the solution
output after we perform the flip (i.e.: the weighting of the edges cut by the
initial solution $S$). Our first new ingredient is to start iterating the flip
process with different adaptive weights on the edges cut by the solutions
output by the local search algorithm on the different weighted graphs (the
motivation is again that the bad case in these scenarios is when the above two
assumptions are nearly satisfied). In this case, we use the sequence of
solutions found by applying the local search to further and further refine our
weighting scheme. The second key ingredient is a procedure that pivots over
three clusterings to output a new clustering that combines them. The pivot
procedure iteratively creates a new clustering by taking the largest set of
vertices that are together in all three clusterings, and creating a new
cluster consisting of vertices that are together with the chosen ones in at
least two out of three clusterings, and repeating on the remaining vertices.
We then build a sequence of solutions that iteratively modify the weights of
the edges of the graph and pivot on the three last solutions created. We show
that the best solution among the ones created achieves our final bound of
$2-2/13$.

##### Efficient implementations

In the previous paragraph, we have worked with the idealistic local search
algorithm that can swap in and out clusters of arbitrary sizes.

A striking phenomenon here is that it is impossible to approximate the cost of
the optimum solution up to any $o(n)$ factor on graphs with $n$ vertices in
the sublinear memory regime; hence all previous algorithms on this model
output a solution without estimating its cost. In light of this, it may seem
hopeless to use a local-search-based approach that requires estimating the
cost of swapping in and out clusters to improve the cost of the current
solution. Yet, we show that thanks to the coarse preclustering, sampling
techniques are enough to estimate the cost of potential swaps and implement
our approach.

Another crucial feature of our local-search-based approach is that it can also
be implemented in a distributed environment and allow to perform local search
iterations in parallel.

We now discuss the main ideas that led to achieving a linear running time, and
derive algorithms for the sublinear time and massively-parallel computation
models. Let’s focus on implementations for the simple local search presented
at the beginning of this section. To implement our approach we need to show
how to implement the following key primitive: Given a clustering $S$, is there
a cluster $C$ such that the solution $S_{C}$ has a better cost than $S$.
Assume first that we are in the case where the optimum solution has cost at
least $\epsilon$ times the total number of edges of the graph. In this case,
we can tolerate an additive cost proportional to $\epsilon^{2}$ times the sum
of the degrees of the vertices in $C$ and our analysis would be unchanged up
to an additive term of $2\epsilon$ times the cost of Opt.

In this context, we make use of the fact that the clusters of any optimum
solution are dense (i.e.: each cluster $C$ of Opt contains at least
$|C|(|C|-1)/2-1$ edges since otherwise, the vertices could be placed into a
singleton and the cost would improve). This means that we can pick uniformly
at random a set of, say, $\text{poly}(1/\epsilon)$ vertices from the cluster
and this provides an accurate estimate of the fraction of neighbors in the
cluster for any other vertex $v$ in the graph, up to an additive $\epsilon|C|$
term. Moreover, we show that there exists a near-optimal solution
$\textsc{Opt}^{*}$ where each vertex in $C$ has degree proportional to $|C|$.
Our algorithm then aims at sampling a set of $\text{poly}(1/\epsilon)$
vertices from $C$, and places these vertices in a tentative cluster
$C^{\prime}$. It then iterates over a set of _candidate_ vertices that could
tentatively be included in $C^{\prime}$ (and that contains the vertices in
$C$). We would then like to show that the total amount of mistakes made by the
algorithm is proportional to the sum of the degrees of the vertices in $C$. To
achieve this, we require two more ingredients: (1) the candidate vertices have
degree proportional to $|C|$ and their number is proportional to $|C|$; and
(2) that these greedy steps are consistent with the uniform sample we have
selected, namely that the uniform sample we are using to make our decisions is
also a uniform sample of $C^{\prime}$ (since otherwise the decisions made are
not relevant w.r.t. the final cluster produced).

To both achieve (1) and ensure that we can tolerate an error of $\epsilon$
times the sum of the edges in the instance, we use the Preclustering algorithm
recently introduced in [23] which merges vertices that they prove can be
clustered together in a near-optimal solution.

To achieve (2), we use an iterated approach where the cluster is constructed
in batches of size $\epsilon^{q}|C|$ for some constant $q$ and the sampling is
“updated” after each batch. Decisions made for the $i$th batch are based on a
sample obtained by sampling the set of vertices that have already joined
$C^{\prime}$ and the set of vertices that we would like to join $C^{\prime}$.
The mistakes for the $i$th batched are thus proportional to $\epsilon^{2q}|C|$
and since the total number of batches is $O(1/\epsilon^{q})$ (thanks to (1))
the final mistake obtained is $\epsilon^{q}|C|$.

Finally, we then show that the algorithm can be implemented in linear time and
in fact sublinear time and MPC models. The key observation here is that when
looking for a new cluster $C$ to swap in, one can focus on a vertex $v$ of $C$
and look at the set of vertices with similar degree to $v$ and that are
adjacent to $v$ or to a neighbor of $v$ with degree similar to $v$. The size
of this set is proportional to the degree of $v$ and so proportional to the
cluster $C$. Thus, in time proportional to the degree of $v$ one can run the
above procedure to build the cluster $C$.

###  1.3 Further Related Work

If the number of clusters is a hard constraint and a constant, then a
polynomial-time approximation scheme exists [32, 34] (the running time depends
exponentially on the number of clusters). As hinted at in the introduction,
there is a large body of on Correlation Clustering in other computation
models: there exists online algorithms [37, 36, 25], dynamic algorithms [10],
distributed or parallel algorithms [14, 1, 24, 38, 13, 40, 41, 7, 19],
differentially-private algorithms [11, 35, 16], sublinear time algorithms [5],
and streaming algorithms [9, 5, 21, 24]. Note that recently, [15, 17] have
establish a connection between Correlation Clustering and metric and
ultrametric embeddings.

In the case where the edges of the graph are arbitrarily weighted, and so the
cost induced by violating an edge is its weight, the problem is as hard to
approximate as the Multicut problem (and in fact “approximation equivalent”)
and an $O(\log n)$-approximation is known [31]. The work of Chawla,
Krauthgamer, Kumar, Rabani, and Sivakumar thus implies that there is no
polynomial-time constant factor approximation algorithm for weighted
Correlation Clustering assuming the Unique Game Conjecture [20].

If we flip the objective and aim at maximizing the number of non-violated
edges, a PTAS has been given by Bansal, Blum and Chawla [6], and a
.77-approximation if the edges of the graph are weighted was given by
Charikar, Guruswami and Wirth [18] and Swamy [39].

##  2 Preliminaries

##### Graph notation.

We will work with simple undirected edges. For a graph $G$, by $V(G)$ and
$E(G)$ we denote its vertex and edge set, respectively. If the graph is clear
from the context, we denote $E^{+}=E(G)$ and $E^{-}=\binom{V(G)}{2}\setminus
E(G)$, that is, the set of edges and nonedges of $G$.

Let $d(v)$ the degree of vertex $v$, and for any subset $C$ of vertices let
$d(v,C)$ be the number of neighbors of $v$ in $C$.

Some of the graphs will be accompanied by a weight function
$w:\binom{V(G)}{2}\to\mathbb{R}_{+}$. The unweighted setting corresponds to
$w\equiv 1$. For any set $D\subseteq\binom{V(G)}{2}$, $w(D)$ denotes the total
weight of pairs in $D$. When the graph is unweighted, $w(D)=|D|$.

##### Correlation clustering.

A _clustering scheme_ in $G$ is a partition of $V(G)$. Every set in a
clustering scheme is called a _cluster_. For a clustering scheme
$\mathcal{C}$, let $\textsc{Int}(\mathcal{C})$ be the set of pairs of vertices
that are in the same cluster of $\mathcal{C}$ and $\textsc{Ext}(\mathcal{C})$
be the set of edges across different clusters.
$\textsc{Cost}_{w}^{+}(\mathcal{C})=w(E^{+}\cap\textsc{Ext}(\mathcal{C}))$
denotes the “$+$” cost of $\mathcal{C}$.
$\textsc{Cost}_{w}^{-}(\mathcal{C})=w(E^{-}\cap\textsc{Int}(\mathcal{C}))$
denotes the “$-$” cost of $\mathcal{C}$.
$\textsc{Cost}_{w}(\mathcal{C})=\textsc{Cost}_{w}^{+}(\mathcal{C})+\textsc{Cost}_{w}^{-}(\mathcal{C})$
denotes the total cost of $\mathcal{C}$. We drop the subscript if the weight
function $w$ is clear from the context.

The input to Correlation Clustering is a simple undirected graph $G$, with
additionally a weight function $w$ in the weighted variant. We ask for a
clustering scheme of the minimum possible cost.

We will also use the notation Int and Ext for individual clusters $C\subseteq
V(G)$. Then, $\textsc{Int}(C)=\binom{C}{2}$ and
$\textsc{Ext}(C)=\\{uv\in\binom{V(G)}{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ |\\{u,v\\}\cap C|=1\\}$.

##### Preclustering.

Let $G$ be an unweighted instance to Correlation Clustering and let Opt be a
clustering scheme of minimum cost. Note that every $v\in V(G)$ is in a cluster
of size at most $2d(v)+1$, as otherwise it would be cheaper to cut $v$ out
into a single-vertex cluster. However, $v$ can be put in Opt in a cluster much
smaller than $d(v)$.

We can ensure that $v$ is put in a cluster of size comparable with $d(v)$
allowing a small slack in the quality of the solution. Let $\varepsilon>0$ be
an accuracy parameter. Note that if the cluster of $v$ in Opt is of size
smaller than $\frac{\varepsilon}{1+\varepsilon}d(v)$, then one can cut out $v$
into a single-vertex cluster and charge the cost to at least
$\frac{1}{1+\varepsilon}d(v)$ already cut edges incident with $v$. That is,
there exists a $(1+\varepsilon)$-approximate solution with the following
property: every $v\in V(G)$ is either in a single-vertex cluster or in a
cluster of size between $\frac{\varepsilon}{1+\varepsilon}d(v)$ and $2d(v)+1$.
For fixed $\varepsilon>0$, this is of order $d(v)$.

Preprocessing introduced in [23] takes the above approach further and also
identifies some pairs of vertices that can be safely assumed to be together or
separate in a $(1+\varepsilon)$-approximate clustering scheme. The crux lies
in the following guarantee: the number of vertex pairs of “unknown” status is
comparable with the cost of the optimum solution.

We now formally state the outcome of this preprocessing.

######  Definition 2.

For an unweighted Correlation Clustering instance $G$, a preclustered instance
is a pair $(\mathcal{K},E_{\text{adm}})$, where $\mathcal{K}$ is a family of
disjoint subsets of $V(G)$ (not necessarily a partition), and
$E_{\text{adm}}\subseteq\binom{V(G)}{2}$ is a set of pairs called _admissible
pairs_ such that for every $uv\in E_{\text{adm}}$, at least one of $u$ and $v$
is not in $\bigcup\mathcal{K}$.

Each set $K\in\mathcal{K}$ is called an atom. We use
$V_{\mathcal{K}}:=\bigcup\mathcal{K}$ to denote the set of all vertices in
atoms. A pair $uv\in\binom{V(G)}{2}$ with $u$ and $v$ in the same
$K\in\mathcal{K}$ is called an _atomic pair_. A pair $(u,v)$ between two
vertices $u,v$ in the same $K\in\mathcal{K}$ is called an atomic edge. A pair
that is neither an atomic pair nor an admissible pair is called a _non-
admissible pair_.

For a vertex $u$, let $d^{\text{adm}}(u)$ denote the number of $v\in V(G)$
such that $uv$ is an admissible pair. Note that $\sum_{u\in
V(G)}d^{adm}(u)=2|E_{\text{adm}}|$.

######  Definition 3.

Let $G$ be an unweighted Correlation Clustering instance, let
$(\mathcal{K},E_{\text{adm}})$ be a preclustered instance for $G$, and let
$\varepsilon>0$ be an accuracy parameter. We say that
$(\mathcal{K},E_{\text{adm}})$ is a _$\varepsilon$ -good_ preclustered
instance if the following holds:

  1. 1.

for every $v\in V(G)$, we have $d^{\text{adm}}(v)\leq 2\varepsilon^{-3}\cdot
d(v)$, and

  2. 2.

for every $uv\in E_{\text{adm}}$, we have $d(u)\leq 2\varepsilon^{-1}\cdot
d(v)$.

  3. 3.

for every atom $K\in\mathcal{K}$, for every vertex $v\in K$, we have that $v$
is adjacent to at least a $(1-O(\epsilon))$ fraction of the vertices in $K$
and has at most $O(\epsilon|K|)$ neighbors not in $K$.

Therefore, in a preclustered instance, the set $\binom{V(G)}{2}$ is
partitioned into atomic, admissible, and non-admissible pairs. By the
definition of $E_{\text{adm}}$, a pair $uv$ between two different atoms is
non-admissible.

######  Definition 4 (Good clusters and good clustering schemes).

Let $G$ be an unweighted Correlation Clustering instance, let
$(\mathcal{K},E_{\text{adm}})$ be a preclustered instance for $G$, and let
$\varepsilon>0$ be an accuracy parameter. Assume that
$(\mathcal{K},E_{\text{adm}})$ is $\varepsilon$-good. For a real $\delta>0$, a
set $C\subseteq V(G)$ is called a _$(\varepsilon,\delta)$ -good_ cluster with
respect to $(\mathcal{K},E_{\text{adm}})$ if

  * •

for any $u$ in $C$, for any $v$, if $uv$ is an atomic pair, then $v$ is also
in $C$.

  * •

for any distinct $u,v$ in $C$, we have that $uv$ is not a non-admissible pair.

  * •

for any vertex $v$ in $C$, if $|C|>1$, then $|C|\geq\delta d(v)$.

Moreover, a clustering scheme $\mathcal{C}$ is called
$(\varepsilon,\delta)$-good with respect to $(\mathcal{K},E_{\text{adm}})$ if
all clusters $C\in\mathcal{C}$ are $(\varepsilon,\delta)$-good. We will also
say a cluster/clustering scheme is $\varepsilon$-good if it is
$(\varepsilon,\varepsilon)$-good.

That is, a good cluster can not break an atom, or join a non-admissible pair.
As a result, two atoms can not be in the same cluster as the pairs between
them are non-admissible.

We consider the following algorithm to compute a preclustering due to [23]

Preclustering($G,\varepsilon$) • Run Algorithm 1 of [24]. Each non-singleton
cluster is an atom. let $\mathcal{K}$ be the set of atoms produced. • A pair
$uv$ is _degree-similar_ if $\varepsilon d(v)\leq d(u)\leq d(v)/\varepsilon$.
A pair $uv$ is _admissible_ if (1) either $u$ or $v$ belongs to
$V(G)\setminus{V_{\mathcal{K}}}$, and (2) it is degree-similar, and (3) the
number of common neighbors that are degree-similar to both $u$ and $v$ is at
least $\varepsilon\cdot\text{min}\\{d(u),d(v)\\}$. We let $E_{\text{adm}}$ be
the set of all admissible pairs in $\binom{V(G)}{2}$. • Output the pair
$(\mathcal{K},E_{\text{adm}})$.

The following theorem is in fact a restatement from [23]: The only addition
from the Theorem 4 of [23] (arXiv version) is that we require the instance to
be $\varepsilon$-good: Namely that the 3 bullets of Definition 3 hold. The
last two bullets are shown to be true in the proof of Theorem 4 of [23] (arXiv
version) while the last bullet follows from the description of Algorithm 1 of
[24].

######  Theorem 5 (Preclustering [23, 24]).

Let $\varepsilon>0$ be a sufficiently small accuracy parameter. Then, given an
unweighted Correlation Clustering instance $G$, the algorithm
Preclustering($G,\varepsilon$) produces a $\varepsilon$-good preclustered
instance $(\mathcal{K},E_{\text{adm}})$ that admits an (unknown to the
algorithm) $\varepsilon$-good clustering scheme
$\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$ with the following
properties:

  * •

$\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})$ is at most
$(1+\varepsilon)$ times the minimum cost of a clustering scheme in $G$;

  * •

$\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})$ is at least
$(\varepsilon^{12}/2)\cdot|E_{\text{adm}}|$.

###  2.1 Sublinear, streaming and MPC models

We further define the sublinear, streaming and MPC models. Let $G=(V,E)$ be a
graph.

######  Definition 6.

In the _sublinear_ model, the algorithm can query the following information in
$O(1)$ time:

  * •

Degree queries: What is the degree of vertex $v$?

  * •

Neighbor queries: What is the $i$-th neighbor of $v\in V$ for $i$ less or
equal to the degree of $v$?

######  Definition 7.

In the _streaming_ model, the algorithm knows the vertices of the graph in
advance, and the edges arrive in a stream. The algorithm only has
$O(n\operatorname{polylog}(n))$ space and can only read the stream once.

In the MPC model, the set of edges is distributed to a set of machines.
Computation then proceeds in synchronous rounds. In each round, each machine
first receives messages from the other machines (if any), then performs some
computation based on this information and its own internal allocated memory,
and terminates the round by sending messages to other machines that will be
received by the machine at the start of the next round. Each message has size
$O(1)$ words. Each machine has limited local memory, which restricts the total
number of messages it can receive or send in a round.

For the Correlation Clustering problem, the algorithm’s output at the end of
the final computation round is that each machine is required to store in its
local memory the IDs of the cluster of the vertices that it initially had
edges adjacent to.

We consider the strictly sublinear MPC regime where each machine has local
memory $O(n^{\delta})$, where $\delta>0$ is a constant that can be made
arbitrarily small, and $\tilde{O}(m)$ total space.

The theorem below is immediate from Theorem 1 in [24].

######  Theorem 8 (Preclustering in the MPC and sublinear time model – [24]
Theorem 1).

For any constant $\delta>0$, Preclustering$(G,\epsilon)$ can be implemented in
the MPC model in $O(1)$ rounds. Letting $n=|V|$, this algorithm succeeds with
probability at least $1-1/n$ and requires $O(n^{\delta})$ memory per machine.
Moreover, the algorithm uses a total memory of $O(|E|\log n)$.

The following sampling techniques will be used in our implementations in the
sublinear and streaming models.

######  Lemma 9 ([5]).

In $O(n\log n)$ time (in the sublinear model) or in $O(n\log n)$ space (in the
streaming model), we can sample $\Theta(\log n)$ neighbors (with repetition)
of each vertex $v$.

######  Lemma 10 ([5]).

In $O(n\log n)$ time (in the sublinear model) or in $O(n\log n)$ space with
high probability (in the streaming model), we can sample each vertex $v$ with
probability $\Theta(\log n/d(v))$ and store all edges incident to sampled
vertices.

We remark that in the streaming model, we can also get several independent
realizations of the above sampling schemes in one pass which only increases
the space complexity.

The next theorem follows the decomposition theorem and the framework of Assadi
and Wang [5, 24, 23].

######  Theorem 11 ([5, 24, 23]).

In $O(n\log^{2}n)$ time (in the sublinear model) or in $O(n\log n)$ space (in
the streaming model), one can compute a partition $\mathcal{K}$ of the
vertices and a data structure such that there exists an $\epsilon$-good
preclustering $(\mathcal{K},E_{\text{adm}})$ satisfying the conditions of
Theorem 5 with

  * •

$\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})$ is at most
$(1+\varepsilon)$ times the minimum cost of a clustering scheme in $G$;

  * •

$\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})>(\varepsilon^{12}/2^{13})\cdot|E_{\text{adm}}|$

and such that with success probability at least $1-1/n^{2}$, for any pair of
vertices, the data structure can answer in $O(\log n)$ time whether the edge
is in $E_{\text{adm}}$ or not, and for any vertex $v$, the data structure can
list all vertices admissible to $v$ in $O(d(v)\log^{2}n)$ time.

The proof of the above statement follows from the following observation: The
set $\mathcal{K}$ is partitioned into disjoint dense vertex set computed by
the framework of Assadi and Wang. We initialize one realization of Lemma 10,
which samples each vertex $v$ with probability $40\varepsilon^{-2}\log
n/d(v)$. With high probability, each vertex $v$ will only have $O(\log n)$
degree-similar sampled neighbors. Then, when the data structure is queried
with a pair $u,v$ it can implement the second step of the preclustering by (1)
verifying that none of $u,v$ belong to $\mathcal{K}$ in $O(1)$ time, (2)
verifying that $u,v$ are degree similar with two degree queries, and (3)
looking at the degree-similar sampled neighbors of $u$ and $v$ in total time
$O(\log n)$ and verifying that the intersection is at least
$\varepsilon\min\\{d(u),d(v)\\}/2$ of the Preclustering algorithm. An
immediate application of Chernoff bound implies that the probability of
misreporting that an edge is not admissible is at most $1/n^{4}$. Then by a
union bound, with probability $1-1/n^{2}$ it can correctly answer all queries.
On the other hand, the number of edges reported is the same as in Theorem 5
applied to an $\varepsilon$ twice smaller. Then, when we want to list all
vertices admissible to $v$, we look at every degree-similar sampled neighbor
$u$ of $v$. For each neighbor of $u$, we query whether it is admissible to
$v$. Given that the data structure can correctly answer all queries, we must
find all candidates in this way, and the total number of queries we make is
$O(d(v)\log n)$.

##  3 Local Search with Flips

In this section, we present and analyse a few local search based approaches to
Correlation Clustering.

First, we present a simple warm-up $(2-\frac{1}{8})$-approximation. Here, we
will not discuss the implementation of a local search step, but only
properties of a local optimum. Then, we present a more involved
$(2-\frac{2}{13}+\varepsilon)$-approximation, where we in the analysis also
care to leave placeholders for our implementation of a local search step. This
implementation will be via sampling, and can only guarantee being in an
“$(1+\varepsilon)$-approximate” local optimum.

Let $\mathcal{C}$ be a clustering scheme in a graph $G$ with weight function
$w$ and let $C\subseteq V(G)$. By $\mathcal{C}+C$ we denote the clustering
scheme obtained from $\mathcal{C}$ by first removing the vertices of $C$ from
all clusters and then creating a new cluster $C$.

###  3.1 Warm-up: $(2-\frac{1}{8})$-approximation

As a warm-up, to show our techniques, we present an analysis of a local
optimum of a simple local search.

######  Definition 12.

A clustering scheme Ls is a _local optimum_ if for every $C\subseteq V(G)$ we
have $\textsc{Cost}(\textsc{Ls}+C)\geq\textsc{Cost}(\textsc{Ls})$.

We will analyse the following algorithm.

Local-Search-Flip-Local-Search • Let $\textsc{Ls}1$ be a local optimum of
$(G,w)$. • Double the weight of edges in $E^{+}\cap\textsc{Ext}(\textsc{Ls}1)$
to get a new weight function $w^{\prime}$. • Let $\textsc{Ls}2$ be a local
optimum of $(G,w^{\prime})$. • Output the best of $\textsc{Ls}1$ and
$\textsc{Ls}2$ with respect to the original cost function.

The remainder of this section is devoted to the proof of the following
theorem.

######  Theorem 13.

The Local-Search-Flip-Local-Search algorithm applied to an instance with
uniform weight ($w\equiv 1$) outputs a solution of cost within a
$(2-\frac{1}{8})$ ratio of the optimum solution.

We start the proof with a few observations about local optimum.

######  Lemma 14.

Let Ls be a local optimum and let $\mathcal{C}$ be a clustering scheme. Then,
the following holds.

$\displaystyle\textsc{Cost}^{-}(\mathcal{C})+2\textsc{Cost}^{+}(\mathcal{C})$
$\displaystyle\geq
w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))+2w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))$
$\displaystyle\quad+w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))+2w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C})),$
(1) $\displaystyle\textsc{Cost}(\textsc{Ls})$ $\displaystyle\leq
2\textsc{Cost}(\mathcal{C})-\textsc{Cost}^{-}(\mathcal{C})-w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))$
$\displaystyle\quad-w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C})),$
(2) $\displaystyle\textsc{Cost}(\textsc{Ls})$ $\displaystyle\leq
2\textsc{Cost}(\mathcal{C})-\textsc{Cost}^{-}(\mathcal{C})-w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C})),$
(3) $\displaystyle\textsc{Cost}(\textsc{Ls})$ $\displaystyle\leq
2\textsc{Cost}(\mathcal{C})-\textsc{Cost}^{-}(\textsc{Ls})-w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C})).$
(4)

###### Proof.

Since Ls is a local optimum, for every cluster $C$ of $\mathcal{C}$ it holds
that $\textsc{Cost}(\textsc{Ls}+C)\geq\textsc{Cost}(\textsc{Ls})$. That is,

$\displaystyle w(E^{-}\cap\textsc{Int}(C))+w(E^{+}\cap\textsc{Ext}(C))$
$\displaystyle\geq
w(E^{+}\cap\textsc{Int}(C)\cap\textsc{Ext}(\textsc{Ls}))+w(E^{+}\cap\textsc{Ext}(C)\cap\textsc{Ext}(\textsc{Ls}))$
$\displaystyle\quad+w(E^{-}\cap\textsc{Int}(C)\cap\textsc{Int}(\textsc{Ls}))+w(E^{-}\cap\textsc{Ext}(C)\cap\textsc{Int}(\textsc{Ls})).$

Summing the above over every cluster $C$ of $\mathcal{C}$ proves (1), as every
pair of $\textsc{Ext}(\mathcal{C})$ will appear twice and every pair of
$\textsc{Int}(\mathcal{C})$ will appear once in the summands.

Inequality (2) follows from (1) by simple algebraic manipulation, noting that
$\textsc{Cost}(\mathcal{C})=\textsc{Cost}^{+}(\mathcal{C})+\textsc{Cost}^{-}(\mathcal{C})$
and
$\textsc{Cost}(\textsc{Ls})=w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))+w(E^{+}\cap\textsc{Ext}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))++w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))+w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))$.

Inequality (3) is just (2) with the nonnegative term
$w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))$ dropped.

For (4), we use the following immediate estimate:

$w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))\leq\textsc{Cost}^{-}(\mathcal{C}).$
(5)

Inequality (4) follows from (2) by first adding (5) to the sides and then
observing that
$\textsc{Cost}^{-}(\textsc{Ls})=w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Int}(\mathcal{C}))+w(E^{-}\cap\textsc{Int}(\textsc{Ls})\cap\textsc{Ext}(\mathcal{C}))$.
∎

Let $\delta=\frac{1}{8}$. In the proof, it is instructive to think about
$\delta$ as a small constant; only in the end we will observe that setting
$\delta=\frac{1}{8}$ gives the best result.

Let Opt be an optimum solution. We say that a clustering scheme $\mathcal{C}$
is _$\alpha$ -competitive_ if
$\textsc{Cost}(\mathcal{C})\leq\alpha\textsc{Cost}(\textsc{Opt})$.

The structure of the proof of Theorem 13 is as follows: assuming that both
$\textsc{Ls}1$ and $\textsc{Ls}2$ are not $(2-\delta)$-competitive, we
construct a solution which is better than $8\delta$-competitive. This finishes
the proof, as we cannot have a solution better than the optimum one.

To execute this line, we analyse in detail costs of various sets of (non)edges
of $G$ using inequalities of Lemma 14.

######  Lemma 15.

If $\textsc{Ls}1$ is not $(2-\delta)$-competitive, then the following holds.

$\displaystyle\textsc{Cost}^{-}(\textsc{Opt})+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt}))$
$\displaystyle<\delta\textsc{Cost}(\textsc{Opt}),$
$\displaystyle\textsc{Cost}^{-}(\textsc{Ls}1)+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt}))$
$\displaystyle<\delta\textsc{Cost}(\textsc{Opt}).$

###### Proof.

Immediately from (3) and (4) for $\textsc{Ls}1$ and Opt. ∎

Here we use $\textsc{Cost}^{\prime}$ to denote the cost on the instance
$(G,w^{\prime})$. By the definition of $w^{\prime}$, for any clustering scheme
$\mathcal{C}$,

$\textsc{Cost}^{\prime}(\mathcal{C})=\textsc{Cost}(\mathcal{C})+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\mathcal{C})).$
(6)

We remark that Opt still denotes the optimal solution of $(G,w)$, and the
“$-$” cost for any clustering scheme remains the same in $(G,w^{\prime})$.

######  Lemma 16.

If $\textsc{Ls}2$ is not $(2-\delta)$-competitive, then

$\displaystyle\textsc{Cost}^{-}(\textsc{Ls}2)+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}2)\cap\textsc{Ext}(\textsc{Opt}))+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Ls}2))$
$\displaystyle\qquad<\delta\textsc{Cost}(\textsc{Opt})+2w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt})).$

###### Proof.

By Equation (6), we have:

$\displaystyle\textsc{Cost}^{\prime}(\textsc{Opt})$
$\displaystyle=\textsc{Cost}(\textsc{Opt})+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt})),\mathrm{\
and}$ $\displaystyle\textsc{Cost}^{\prime}(\textsc{Ls}2)$
$\displaystyle=\textsc{Cost}(\textsc{Ls}2)+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Ls}2)).$

By applying (4) to $\textsc{Ls}2$ and Opt in $(G,w^{\prime})$, we obtain:

$\displaystyle\textsc{Cost}^{\prime}(\textsc{Ls}2)$ $\displaystyle\leq
2\textsc{Cost}^{\prime}(\textsc{Opt})-\textsc{Cost}^{-}(\textsc{Ls}2)-w^{\prime}(E^{+}\cap\textsc{Ext}(\textsc{Ls}2)\cap\textsc{Ext}(\textsc{Opt}))$
$\displaystyle\leq
2\textsc{Cost}^{\prime}(\textsc{Opt})-\textsc{Cost}^{-}(\textsc{Ls}2)-w(E^{+}\cap\textsc{Ext}(\textsc{Ls}2)\cap\textsc{Ext}(\textsc{Opt})).$

Here, the last inequality follows from the fact that all weights of $w$ are
nonnegative and after the flip $w^{\prime}$ is $w$ with some weights doubled.

Combining them, we get:

$\displaystyle\textsc{Cost}(\textsc{Ls}2)\leq$ $\displaystyle\
2(\textsc{Cost}(\textsc{Opt})+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt})|))-\textsc{Cost}^{-}(\textsc{Ls}2)$
$\displaystyle-w(E^{+}\cap\textsc{Ext}(\textsc{Ls}2)\cap\textsc{Ext}(\textsc{Opt}))-w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Ls}2)).$

The lemma follows. ∎

We combine the estimates of Lemmata 15 and 16 into the following.

######  Lemma 17.

If both $\textsc{Ls}1$ and $\textsc{Ls}2$ are not $(2-\delta)$-competitive,
then

$\displaystyle\textsc{Cost}^{-}(\textsc{Opt})+\textsc{Cost}^{-}(\textsc{Ls}1)+\textsc{Cost}^{-}(\textsc{Ls}2)+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt}))$
$\displaystyle+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}2)\cap\textsc{Ext}(\textsc{Opt}))+w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Ls}2))$
$\displaystyle\qquad<4\delta\textsc{Cost}(\textsc{Opt}).$

###### Proof.

By Lemma 16, the left-hand-side is at most

$\textsc{Cost}^{-}(\textsc{Opt})+\textsc{Cost}^{-}(\textsc{Ls}1)+3w(E^{+}\cap\textsc{Ext}(\textsc{Ls}1)\cap\textsc{Ext}(\textsc{Opt}))+\delta\textsc{Cost}(\textsc{Opt}),$

which, by Lemma 15, is at most

$4\delta\textsc{Cost}(\textsc{Opt}).$

∎

We now use Lemma 17 to show a clustering scheme of cost strictly less than
$8\delta\textsc{Cost}(\textsc{Opt})$.

To this end, we will need the following _Pivot_ operation. Let
$\mathcal{C}_{x}$, $\mathcal{C}_{y}$, $\mathcal{C}_{z}$ be three clustering
schemes of $G$. Within each clustering scheme, number the clusters with
positive integers. For each vertex of $G$, we associate it with a
3-dimensional vector $(x,y,z)\in\mathbb{Z}_{+}^{3}$ if it is in $x$-th cluster
in $\mathcal{C}_{x}$, in the $y$-th cluster in $\mathcal{C}_{y}$, and in the
$z$-th cluster in $\mathcal{C}_{z}$. We define the distance between two
vertices $u$ and $v$, denoted $d(u,v)$, to be the Hamming distance of their
coordinate vectors.

The operation
$\mathrm{Pivot}(\mathcal{C}_{x},\mathcal{C}_{y},\mathcal{C}_{z})$ produces a
new clustering scheme $\mathcal{C}$ as follows. Initially, all vertices of $G$
are unassigned to clusters, that is, we start with $\mathcal{C}=\emptyset$.
While $\bigcup\mathcal{C}\neq V(G)$, that is, not all vertices of $G$ are
assigned into clusters, we define a new cluster in $G$ and add to
$\mathcal{C}$. The new cluster is found as follows: we take a coordinate
$(x,y,z)$ with the maximum number of vertices of
$V(G)\setminus\bigcup\mathcal{C}$ assigned to it (breaking ties arbitrarily),
and creates a new cluster consisting of all vertices of
$V(G)\setminus\bigcup\mathcal{C}$ within distance at most $1$ from $(x,y,z)$.
This concludes the definition of the _Pivot_ operation.

The following lemma encapsulates the crux of the analysis of the _Pivot_
operation.

######  Lemma 18.

Let $G$ be an unweighted Correlation Clustering instance, let
$\mathcal{C}_{x}$, $\mathcal{C}_{y}$, $\mathcal{C}_{z}$ be three clustering
schemes, and let
$\mathcal{C}:=\mathrm{Pivot}(\mathcal{C}_{x},\mathcal{C}_{y},\mathcal{C}_{z})$.
Divide each of $E^{+}$ and $E^{-}$ into 4 sets by the distances. $E^{+}_{i}$
denotes the set of pairs of $E^{+}$ with distance $i$, and $E^{-}_{i}$ denotes
the set of pairs of $E^{-}$ with distance $i$. Call pairs in $E^{+}_{0}\cup
E^{+}_{1}\cup E^{-}_{3}$ _normal_ , and call other pairs _special_. Then,
$(E^{+}\cap\textsc{Ext}(\mathcal{C}))$ contains no edges of $E^{+}_{0}$ and
$(E^{-}\cap\textsc{Int}(\mathcal{C}))$ contains no pairs of $E^{-}_{3}$.
Furthermore, the number of special edges is at least half of the size of
$(E^{+}\cap\textsc{Ext}(\mathcal{C}))\cup(E^{-}\cap\textsc{Int}(\mathcal{C}))$.

###### Proof.

The first claim follows immediately by definition: two vertices with distance
$0$ will always be put into the same cluster, while two vertices with distance
$3$ will never be put into the same cluster.

Hence, all pairs in $E^{-}\cap\textsc{Int}(\mathcal{C})$ are special, and the
only edges of $E^{+}\cap\textsc{Ext}(\mathcal{C})$ that are normal are from
$E_{1}^{+}$. Observe that, while creating a cluster with a pivot in $(x,y,z)$,
an edge $uv\in E_{1}^{+}$ ends up in $\textsc{Ext}(\mathcal{C})$ if
$d(u,(x,y,z))=1$ and $d(v,(x,y,z))=2$ (or vice versa). We will charge such
edges to pairs of $E_{2}:=E_{2}^{-}\cup E_{2}^{+}$ with at least one endpoint
in the newly created cluster. Note that $E_{2}$ consists only of special
pairs.

Consider a step of the
$\mathrm{Pivot}(\mathcal{C}_{x},\mathcal{C}_{y},\mathcal{C}_{z})$ operation
creating a cluster $C$ with pivot $(x,y,z)$. To finish the proof of the lemma,
it suffices to show that the number of edges $uw\in E^{+}_{1}$ where $u\in C$
and $w\notin C$ remains in the graph is not larger than the number of pairs
$u^{\prime}w^{\prime}\in E_{2}$ with $|\\{u^{\prime},w^{\prime}\\}\cap C|\geq
1$ (i.e., the number of edges of $E_{2}$ that will be deleted when deleting
the cluster $C$.)

To this end, for coordinate vector $(x^{\prime},y^{\prime},z^{\prime})$, let
$n_{(x^{\prime},y^{\prime},z^{\prime})}$ be the number of vertices at
coordinate $(x^{\prime},y^{\prime},z^{\prime})$ that are unassigned to
clusters just before the cluster $C$ is created.

We say that an edge $uw\in E_{1}^{+}$ is _cut_ if one endpoint of $uw$ is in
$C$, and the second endpoint is outside $C$ and unassigned to any cluster at
the moment of creating $C$.

If an edge from $E_{1}^{+}$ is cut, its endpoint not in $C$ has coordinate
vector at distance $2$ to $(x,y,z)$, say $(x^{\prime},y^{\prime},z)$. The
number of $E^{+}_{1}$ edges cut to this coordinate is at most
$v_{(x^{\prime},y^{\prime},z)}(v_{(x^{\prime},y,z)}+v_{(x,y^{\prime},z)})$. We
charge them to the $E_{2}$ edges between $(x,y,z)$ and
$(x^{\prime},y^{\prime},z)$ and the $E_{2}$ edges between $(x^{\prime},y,z)$
and $(x,y^{\prime},z)$. Because these edge sets are complete, it suffices to
show that

$n_{(x^{\prime},y^{\prime},z)}(n_{(x^{\prime},y,z)}+n_{(x,y^{\prime},z)})\leq
n_{(x^{\prime},y^{\prime},z)}n_{(x,y,z)}+n_{(x^{\prime},y,z)}n_{(x,y^{\prime},z)}.$

This easily follows from the fact that
$n_{(x,y,z)}\geq\max\\{n_{(x^{\prime},y^{\prime},z)},n_{(x^{\prime},y,z)},n_{(x,y^{\prime},z)}\\}$.
This finishes the proof of the lemma. ∎

Lemma 18 suggests to bound the number of the special pairs. This is how we
will do it.

######  Lemma 19.

Let $G$, $\mathcal{C}_{x}$, $\mathcal{C}_{y}$, $\mathcal{C}_{z}$,
$\mathcal{C}$, $E^{+}_{i}$, and $E^{-}_{i}$ for $i=0,1,2,3$ be as in Lemma 18.
Then,

$w(E^{-}_{0}\cup E^{-}_{1}\cup E^{-}_{2})\leq
w(E^{-}\cap\textsc{Int}(\mathcal{C}_{x}))+w(E^{-}\cap\textsc{Int}(\mathcal{C}_{y}))+w(E^{-}\cap\textsc{Int}(\mathcal{C}_{z})),$

and

$w(E^{+}_{2}\cup E^{+}_{3})\leq
w(E^{+}\cap\textsc{Ext}(\mathcal{C}_{x})\cap\textsc{Ext}(\mathcal{C}_{y}))+w(E^{+}\cap\textsc{Ext}(\mathcal{C}_{y})\cap\textsc{Ext}(\mathcal{C}_{z}))+w(E^{+}\cap\textsc{Ext}(\mathcal{C}_{z})\cap\textsc{Ext}(\mathcal{C}_{x})).$

###### Proof.

Every pair in $E^{-}_{0}\cup E^{-}_{1}\cup E^{-}_{2}$ is present in at least
once in $\textsc{Int}(\mathcal{C}_{x})$, $\textsc{Int}(\mathcal{C}_{y})$, and
$\textsc{Int}(\mathcal{C}_{z})$. Every edge in $E^{+}_{2}\cup E^{+}_{3}$ is
present at least once in
$\textsc{Ext}(\mathcal{C}_{x})\cap\textsc{Ext}(\mathcal{C}_{y})$,
$\textsc{Ext}(\mathcal{C}_{y})\cap\textsc{Ext}(\mathcal{C}_{z})$, and
$\textsc{Ext}(\mathcal{C}_{z})\cap\textsc{Ext}(\mathcal{C}_{x})$. ∎

We show that if $\textsc{Ls}1$ and $\textsc{Ls}2$ are both not
$(2-\delta)$-competitive, then
$\mathcal{C}:=\mathrm{Pivot}(\textsc{Opt},\textsc{Ls}1,\textsc{Ls}2)$ returns
a clustering of cost strictly less than $8\delta\textsc{Cost}(\textsc{Opt})$.
This will be a contradiction with the optimality of Opt for
$\delta=\frac{1}{8}$. That is, we will use $\mathcal{C}_{x}=\textsc{Opt}$,
$\mathcal{C}_{y}=\textsc{Ls}1$, and $\mathcal{C}_{z}=\textsc{Ls}2$.

Combining Lemmata 17 and 19 gives immediately the following.

######  Lemma 20.

If both $\textsc{Ls}1$ and $\textsc{Ls}2$ are not $(2-\delta)$-competitive,
then the total weight of special pairs is less than
$4\delta\textsc{Cost}(\textsc{Opt})$.

The final lemma below is the first place where we use that $w\equiv 1$ in
Theorem 13. This is necessary for Lemma 18 to be useful, as it considers the
number of pairs, not their weight.

######  Lemma 21.

Assume $w\equiv 1$. If both $\textsc{Ls}1$ and $\textsc{Ls}2$ are not
$(2-\delta)$-competitive, then there exists a solution with cost less than
$8\delta\textsc{Cost}(\textsc{Opt})$.

###### Proof.

Recall that $\mathcal{C}$ is the clustering scheme being the result of
$\mathrm{Pivot}(\textsc{Opt},\textsc{Ls}1,\textsc{Ls}2)$. By Lemma 18, the
number of normal pairs accounted in $\textsc{Cost}(\mathcal{C})$ is not larger
than the number of special pairs. By Lemma 20 and the assumption $w\equiv 1$,
the cost of $\mathcal{C}$ on normal pairs and on special pairs are both less
than $4\delta\textsc{Cost}(\textsc{Opt})$. Hence,
$\textsc{Cost}(\mathcal{C})<8\delta\textsc{Cost}(\textsc{Opt})$. ∎

Since Opt is an optimum solution, Lemma 21 gives a contraction for
$\delta=\frac{1}{8}$. Hence, at least one of $\textsc{Ls}1$ and $\textsc{Ls}2$
is $(2-\frac{1}{8})$-competitive. This completes the proof of Theorem 13.

##### A remark on a hard instance.

We finish this section with an example that the Local-Search-Flip-Local-Search
algorithm can be as bad as $\frac{14}{9}$-competitive. Consider a graph of
$3\times 5\times 5$ vertices, where the vertices have coordinates from
$(1,1,1)$ to $(3,5,5)$. There is an edge between two vertices if and only if
their Hamming distance is at most 2. The optimal solution is to cluster
vertices which have the same $x$-coordinate, and the cost is
$(3-1)(5+5-1)/2=9$ per vertex. It can be checked that $\textsc{Ls}1$ and
$\textsc{Ls}2$ may respectively cluster vertices which have the same
$y$-coordinate/$z$-coordinate, and the cost is $(5-1)(3+5-1)/2=14$ per vertex.
The ratio is $\frac{14}{9}\approx 1.56$.

###  3.2 Iterative version of local search

In this section we present a more complicated iterative local search algorithm
that achieves an approximation ratio of $(2-\frac{2}{13}+\varepsilon)$ for any
$\varepsilon>0$. We also present it in full generality, where we are not able
to find an exact local optimum, but only an approximate one. We start with
defining what this “approximate one” means.

Similarly as in the warm-up section, we will solve unweighted Correlation
Clustering instances, but use local search on instances with some of the edge
weights increased from the flips. The increase from the flips will be small:
we will use a constant $\beta>0$ (set to $\beta=0.5$ in the end) and increase
the weight of some edges by $\beta$ at most twice. Hence, the following
definition needs to include weight functions
$w:\binom{V(G)}{2}\to\mathbb{Z}_{+}$. We say that the weight function $w$ is
_normal_ if $w(uv)=1$ for $uv\notin E(G)$ and $w(uv)\geq 1$ for $uv\in E(G)$.

######  Definition 22.

Let $G$ be an unweighted Correlation Clustering instance, let $\varepsilon>0$
be an accuracy parameter, and let $(\mathcal{K},E_{\text{adm}})$ be a
preclustered instance for $G$ returned by Theorem 5 for $(G,\varepsilon)$.
That is, $(\mathcal{K},E_{\text{adm}})$ is $\varepsilon$-good and let
$\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$ be the (unknown)
$\varepsilon$-good clustering scheme in $(\mathcal{K},E_{\text{adm}})$ whose
existence is promised by Theorem 5.

Let $0<\gamma<\varepsilon^{13}/4$ be a constant and
$w:\binom{V(G)}{2}\to\mathbb{Z}_{+}$ be a normal weight function. Then, a
clustering scheme $\mathcal{C}$ is a _$\gamma$ -good local optimum for $w$_ if
for every cluster $C$ of $\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$ it
holds that

$\sum_{C\in\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}}(\textsc{Cost}_{w}(\mathcal{C})-\textsc{Cost}_{w}(\mathcal{C}+C))\leq
2\gamma|E_{\text{adm}}|.$

We are now ready to present our algorithm. It is parameterized by an accuracy
parameter $\varepsilon>0$, a constant $0<\gamma<\varepsilon^{13}/4$, a
constant $\beta>0$, and a number of iterations $k$. (We will set $\beta=0.5$
and $0<\gamma\ll\varepsilon$ to be small constants in the end.) The input
consists of an unweighted Correlation Clustering instance $G$ and the
algorithm starts with computing an $\varepsilon$-good preclustered instance
$(\mathcal{K},E_{\text{adm}})$ for $G$ using Theorem 5.

The algorithm uses two operations that are worth recalling. First, it
explicitly uses the _Pivot_ operation described in the previous section.
Second, for a weight function $w$ and clustering scheme $\mathcal{C}$, it
performs the flip by computing a new weight function
$w^{\prime}:=w+\beta(E^{+}\cap\textsc{Ext}(\mathcal{C}))$, which is a
shorthand for adding weight $\beta$ to all edges of $G$ that connect different
clusters of $\mathcal{C}$.

Iterated-flipping Local Search($G$) • Let $(\mathcal{K},E_{\text{adm}})$ be
the preclustering obtained via Theorem 5 on $G$ and $\varepsilon$. • Let
$w_{0}\equiv 1$ be the uniform weight function. • Let
$\mathcal{C}_{0}^{\prime}$ be a $\gamma$-good local optimum for $w_{0}$. • For
$i=1,2,\ldots,k$ –
$w_{i}:=w_{0}+\beta(E^{+}\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime}))$. – Let
$\mathcal{C}_{i}$ be a $\gamma$-good local optimum for $w_{i}$. –
$w_{i}^{\prime}:=w_{i}+\beta(E^{+}\cap\textsc{Ext}(\mathcal{C}_{i}))$. – Let
$\mathcal{C}_{i}^{\prime}$ be a $\gamma$-good local optimum for
$w_{i}^{\prime}$. –
$\mathcal{C}_{i}^{\prime\prime}:=\mathrm{Pivot}(\mathcal{C}_{i-1}^{\prime},\mathcal{C}_{i},\mathcal{C}_{i}^{\prime})$
Output best of
$\mathcal{C}_{1},\ldots,\mathcal{C}_{k},\mathcal{C}_{0}^{\prime},\ldots,\mathcal{C}_{k}^{\prime},\mathcal{C}_{1}^{\prime\prime},\ldots,\mathcal{C}_{k}^{\prime\prime}$
with respect to the original cost function.

We prove in this section the following theorem.

######  Theorem 23.

For every $0\leq\alpha<\frac{2}{13}$ there exists a positive integer $k$ and a
real $\varepsilon_{0}>0$ such that for every
$0<\varepsilon\leq\varepsilon_{0}$ and for every
$0<\gamma<\varepsilon^{13}/4$, the Iterated-flipping Local Search Algorithm
returns a $(2-\alpha)$-approximation to Correlation Clustering on an
unweighted input $G$ if run on parameters $\varepsilon$, $\gamma$,
$\beta=0.5$, and $k$.

Let $\varepsilon_{0}^{\prime}>0$ be sufficiently small such that every
$0\leq\varepsilon\leq\varepsilon_{0}^{\prime}$ is fine for Theorem 5 to work.
We set $\varepsilon_{0}$ and $k$ as follows:

$\varepsilon_{0}=\min\left(\varepsilon_{0}^{\prime},\frac{1}{12}\left(\frac{2}{13}-\alpha\right)\right)\quad\mathrm{and}\quad
k=1+\left\lceil\frac{2}{\frac{2}{13}-\alpha}\right\rceil.$

Let $0<\varepsilon\leq\varepsilon_{0}$ and $0<\gamma<\varepsilon^{13}/4$ be
arbitrary.

Let $(\mathcal{K},E_{\text{adm}})$ the $\varepsilon$-good preclustered
instance returned by Theorem 5 and let
$\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}$ be the $\varepsilon$-good
clustering scheme promised by Theorem 5.

Recall that by $\textsc{Cost}(\mathcal{C})$ we mean the cost of $\mathcal{C}$
with regards to the uniform weight $w_{0}\equiv 1$. If we want to use a
different weight function $w$, we denote it by
$\textsc{Cost}_{w}(\mathcal{C})$.

We set $\hat{\alpha}:=(\frac{2}{13}+\alpha)/2$. We will aim at a solution of
cost
$(2-\hat{\alpha})\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$.
By the properties promised by Theorem 5 and by our choice of
$\varepsilon_{0}$, this is enough to obtain a $(2-\alpha)$-approximation.
Hence, for contradiction we assume that the costs of all clustering schemes
$\mathcal{C}_{i}$, $\mathcal{C}_{i}^{\prime}$, and
$\mathcal{C}_{i}^{\prime\prime}$ generated by the algorithm are larger than
$(2-\hat{\alpha})\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$.
We will reach a contradiction.

We start with an analog of Lemma 14.

######  Lemma 24.

Let $\mathcal{C}$ be a $\gamma$-good local optimum for $G$ and a weight
function $w$. Then,

$\displaystyle
w(E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+\varepsilon\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\geq$
$\displaystyle
w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle+w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$

###### Proof.

Let $C$ be a cluster of $\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}$.
By the optimality of $\mathcal{C}$, we have

$\sum_{C\in\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}}\textsc{Cost}_{w}(\mathcal{C}+C)+2\gamma|E_{\text{adm}}|\geq\sum_{C\in\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}}\textsc{Cost}_{w}(\mathcal{C}).$

Equivalently,

$\displaystyle\sum_{C\in\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}}(w(E^{+}\cap\textsc{Ext}(C))+w(E^{-}\cap\textsc{Int}(C)))+2\gamma|E_{\text{adm}}|\geq$
$\displaystyle\sum_{C\in\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}}(w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Int}(C))+w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(C))$
$\displaystyle\qquad\qquad\quad+w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(C))+w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(C))).$

The lemma follows from observing that

$\displaystyle
2\gamma|E_{\text{adm}}|\leq\frac{4\gamma}{\varepsilon^{12}}\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\leq\varepsilon\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}).$

Here, the first inequality uses the properties of
$(\mathcal{K},E^{\text{adm}})$ promised by Theorem 5 while the last inequality
uses the assumption $\gamma<\varepsilon^{13}/4$. ∎

We now proceed to the analogs of Lemmata 15 and 16.

######  Lemma 25.

Let $\mathcal{C}_{1},\ldots,\mathcal{C}_{\ell}$ be clustering schemes and

$w:=w_{0}+\sum_{i=1}^{\ell}\beta(E^{+}\cap\textsc{Ext}(\mathcal{C}_{i})).$

(That is, for every $1\leq i\leq\ell$, we add a weight of $\beta$ to every
edge connecting two distinct clusters of $\mathcal{C}_{i}$.) Let $\mathcal{C}$
be a $\gamma$-good local optimum of $G$ and $w$. If
$\textsc{Cost}(\mathcal{C})>(2-\hat{\alpha})\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$,
then

$\displaystyle\left(\hat{\alpha}+\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$
$\displaystyle+2\beta\left(\sum_{i=1}^{k}|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i})|\right)\geq$
$\displaystyle\beta\sum_{i=1}^{k}|E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}_{i})|$
$\displaystyle+|E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|$
$\displaystyle+|E^{-}\cap\textsc{Int}(\mathcal{C})|.$

###### Proof.

The assumption
$\textsc{Cost}(\mathcal{C})>(2-\hat{\alpha})\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$
expands as

$|E^{+}\cap\textsc{Ext}(\mathcal{C})|+|E^{-}\cap\textsc{Int}(\mathcal{C})|\geq(2-\hat{\alpha})\left(|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|+|E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|\right).$

Rearranging this, we get

$\displaystyle\hat{\alpha}\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$
$\displaystyle\geq
2|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|+2|E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|$
$\displaystyle\quad-|E^{+}\cap\textsc{Ext}(\mathcal{C})|-|E^{-}\cap\textsc{Int}(\mathcal{C})|.$

Applying now the definition of
$w(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$, we get

$\displaystyle\hat{\alpha}\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$
$\displaystyle\geq
2w(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})-2\beta\sum_{i=1}^{k}|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(C_{i})|$
$\displaystyle-|E^{+}\cap\textsc{Ext}(\mathcal{C})|-|E^{-}\cap\textsc{Int}(\mathcal{C})|.$

Adding the inequality of Lemma 24 to both sides, we obtain

$\displaystyle\left(\hat{\alpha}+\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+2\beta\sum_{i=1}^{k}|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(C_{i})|\geq$
$\displaystyle\quad
w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle\quad+w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle\quad+w(E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))-|E^{+}\cap\textsc{Ext}(\mathcal{C})|-|E^{-}\cap\textsc{Int}(\mathcal{C})|.$

The lemma now follows from the above and the following three simple
observations:

$\displaystyle
w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle\quad=|E^{-}\cap\textsc{Int}(\mathcal{C})|+|E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|,$
$\displaystyle
w(E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))=|E^{-}\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|\geq|E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|,$

and

$\displaystyle
w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Int}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))+2w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle\quad=w(E^{+}\cap\textsc{Ext}(\mathcal{C}))+w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})}))$
$\displaystyle\quad\geq
w(E^{+}\cap\textsc{Ext}(\mathcal{C}))+|E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|$
$\displaystyle\quad=|E^{+}\cap\textsc{Ext}(\mathcal{C})|+\beta\sum_{i=1}^{\ell}|E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}_{i})|+|E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})|.$

∎

Fix $1\leq i\leq k$. By Lemmata 18 and 19, we have

$\displaystyle\textsc{Cost}(\mathcal{C}_{i}^{\prime\prime})$
$\displaystyle\leq
2\left(|E^{-}\cap\textsc{Int}(\mathcal{C}_{i-1}^{\prime})|+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i})|+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|\right)$
$\displaystyle\quad+2\big{(}|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i})|+|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|$
$\displaystyle\quad\qquad+|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|\big{)}.$
(7)

Recall $\beta=0.5$. Lemma 25 applied to $\mathcal{C}_{i}$ gives

$\displaystyle\left(\hat{\alpha}+\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|$
$\displaystyle\quad\geq
0.5|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|$
$\displaystyle\quad+|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i})|+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i})|.$
(8)

Lemma 25 applied to $\mathcal{C}_{i}^{\prime}$ gives

$\displaystyle\left(\hat{\alpha}+\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|+|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i})|$
$\displaystyle\quad\geq
0.5|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|+0.5|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i})|$
$\displaystyle\quad+|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|.$
(9)

To bound the right hand side of (7), we add twice (8) with twice (9),
obtaining the following.

$\displaystyle\left(4\hat{\alpha}+4\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+4|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|$
$\displaystyle\quad\geq
2|E^{-}\cap\textsc{Int}(\mathcal{C}_{i})|+2|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|$
$\displaystyle\quad+|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i})|+|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|$
$\displaystyle\quad+|E^{+}\cap\textsc{Ext}(\mathcal{C}_{i})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|+2|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|.$

Combining the above with (7), we obtain

$\displaystyle\left(4\hat{\alpha}+4\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i-1}^{\prime})|+4|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|$
$\displaystyle\quad\geq
0.5\textsc{Cost}(\mathcal{C}_{i}^{\prime\prime})+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|+2|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|.$

Using the assumption
$\textsc{Cost}(\mathcal{C}_{i}^{\prime\prime})>(2-\hat{\alpha})\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})$,
we get

$\displaystyle\left(4.5\hat{\alpha}+4\varepsilon-1\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})+|E^{-}\cap\textsc{Int}(\mathcal{C}_{i-1}^{\prime})|+4|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i-1}^{\prime})|$
$\displaystyle\quad>|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|+2|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|.$
(10)

The above estimate motivates us to define the following value for $0\leq i\leq
k$:

$b_{i}:=\frac{|E^{-}\cap\textsc{Int}(\mathcal{C}_{i}^{\prime})|+2|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{i}^{\prime})|}{\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})}.$

Rewriting (10), we obtain

$b_{i-1}+4.5\hat{\alpha}+4\varepsilon-1>b_{i}-b_{i-1}.$ (11)

Applying Lemma 25 to $\mathcal{C}_{0}^{\prime}$, we have

$\left(\hat{\alpha}+\varepsilon\right)\textsc{Cost}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\geq|E^{+}\cap\textsc{Ext}(\mathcal{C}^{\ast}_{(\mathcal{K},E_{\text{adm}})})\cap\textsc{Ext}(\mathcal{C}_{0}^{\prime})|+|E^{-}\cap\textsc{Int}(\mathcal{C}_{0}^{\prime})|.$

Hence,

$b_{0}\leq 2\hat{\alpha}+2\varepsilon<1.$ (12)

Since every $b_{i}$ is nonnegative, by the choice of $k$ there exists $i$ such
that $b_{i}>b_{i-1}-(\frac{2}{13}-\hat{\alpha})$. Let $1\leq i_{0}\leq k$ be
minimum such that

$b_{i_{0}}>b_{i_{0}-1}-\left(\frac{2}{13}-\hat{\alpha}\right).$

By (12) and the definition of $i_{0}$, for every $0\leq i<i_{0}$ it holds that

$b_{i}\leq 2\hat{\alpha}+2\varepsilon.$

Hence, by combining (11) with the definition of $i_{0}$, we have

$6.5\hat{\alpha}+6\varepsilon-1>\hat{\alpha}-\frac{2}{13}.$

Equivalently,

$5.5\hat{\alpha}+6\varepsilon>\frac{11}{13}.$

Plugging in the definition of $\hat{\alpha}$,

$5.5\alpha+12\varepsilon>\frac{11}{13}.$

This is a contradiction with the assumption $\alpha<\frac{2}{13}$ and the
choice of $\varepsilon_{0}$. This finishes the proof of Theorem 23.

##  4 Polynomial-Time Implementation of Local Search

In this section we provide a polynomial-time implementation of the local
search routine needed in Section 3.2. That is, given a Correlation Clustering
instance $G$ with a preclustering $(\mathcal{K},E_{\text{adm}})$ obtained via
Theorem 5 (with the implicit $\varepsilon$-good clustering scheme
$\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$) and a weight function $w$,
we are to find a $\gamma$-good local optimum for $w$.

The usage in Section 3.2 takes $\varepsilon>0$ as a sufficiently small
accuracy parameter and $0<\gamma<\varepsilon^{13}/4$ as a second parameter.
The weight function $w$ is equal to $1$ on non-edges and takes values
$w(e)\in[1,2]$ for edges $e\in E^{+}$. It will be a bit cleaner to consider a
slightly more general variant where $w(e)\in[1,W]$ for a constant parameter
$W\geq 1$, but one can keep in mind that we actually only need the case $W=2$.
In our algorithm, the weight of a pair can be computed in constant time by
checking whether they are neighbors and whether they are in the same cluster
in some previous local search solution(s).

######  Lemma 26.

Let $w$ be a weight function that equals $1$ on nonedges and takes values in
$[1,W]$ on edges. Consider two clusterings $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ and assume that for each cluster
$C_{i}\in\mathcal{C}^{\prime}$,

$\textsc{Cost}_{w}(\mathcal{C}+C_{i})+\gamma\sum_{u\in
C_{i}}d^{adm}(u)+\Delta_{i}\geq\textsc{Cost}_{w}(\mathcal{C}).$ (13)

Then $\textsc{Cost}_{w}(\mathcal{C})\leq
2\textsc{Cost}_{w}(\mathcal{C}^{\prime})+\varepsilon\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})+\sum_{i}\Delta_{i}$.

###### Proof.

Equivalently to (13) we have

$\displaystyle
w(E^{+}\cap\textsc{Ext}(C_{i}))+|E^{-}\cap\textsc{Int}(C_{i})|+\gamma\sum_{u\in
C_{i}}d^{\text{adm}}(u)+\Delta_{i}\geq$ $\displaystyle\quad
w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Int}(C_{i}))+w(E^{+}\cap\textsc{Ext}(\mathcal{C})\cap\textsc{Ext}(C_{i}))$
$\displaystyle\quad+|E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Int}(C_{i})|+|E^{-}\cap\textsc{Int}(\mathcal{C})\cap\textsc{Ext}(C_{i})|.$

The theorem follows from summing the above inequality for every cluster
$C_{i}$ of $\mathcal{C}^{\prime}$ and observing that

$\displaystyle\sum_{C_{i}\in\mathcal{C}^{\prime}}\gamma\sum_{u\in
C}d^{\text{adm}}(u)$ $\displaystyle=\gamma\sum_{u\in
V(G)}d^{\text{adm}}(u)=2\gamma|E^{\text{adm}}|$
$\displaystyle\leq\frac{4\gamma}{\varepsilon^{12}}\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})})\leq\varepsilon\textsc{Cost}(\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}).$

Here, the penultimate inequality uses the properties of
$(\mathcal{K},E^{\text{adm}})$ promised by Theorem 5 while the last inequality
uses the assumption $\gamma<\varepsilon^{13}/4$. ∎

We will need the following weight-adjusted variants of previously introduced
graph notation.

######  Definition 27.

Let $d_{w}(v)=\sum_{u\mid(u,v)\in E^{+}}w(u,v)$ be the weighted degree of $v$
under $w$. Similarly, we define

$d_{w}(v,S)=\sum_{u\mid u\in S\land(u,v)\in E^{+}}w(u,v).$

where $S$ is a multiset of vertices.

######  Observation 28.

The following statements follow directly from the properties of
$(\mathcal{K},E_{\text{adm}})$.

  * •

$\forall v\in V,d(v)\leq d_{w}(v)\leq Wd(v)$.

  * •

$d^{\text{adm}}(v)\leq 2\varepsilon^{-3}d_{w}(v)$.

  * •

If $(u,v)$ is an admissible pair, then $\frac{1}{2W}\varepsilon d_{w}(v)\leq
d_{w}(u)\leq 2W\varepsilon^{-1}d_{w}(v)$.

We define the neighborhood function $N(v)$ as follows, which is slightly
different from $N_{v}$, the admissible neighborhood.

$N(v)=\begin{cases}N_{v}\setminus\bigcup_{K\in\mathcal{K}}K&\mathrm{if\
}v\mathrm{\ does\ not\ belong\ to\ any\ atom,}\\\ K\cup\left(\bigcap_{u\in
K}N_{u}\right)&\mathrm{if\ }v\mathrm{\ belongs\ to\ an\ atom\ }K.\end{cases}$

We define

$K(v)=\begin{cases}\\{v\\}&\mathrm{if\ }v\mathrm{\ does\ not\ belong\ to\ any\
atom},\\\ K^{\prime}&\mathrm{if\ }v\mathrm{\ belongs\ to\ an\ atom\
}K^{\prime}.\end{cases}$ $D(v)=N(v)\setminus K(v)\leavevmode\nobreak\ .$

##### Estimates of set sizes.

We will need a few estimates of sizes of various neighborhood-like sets.

######  Lemma 29.

For all $v\in V$, $|N(v)|\leq 6\varepsilon^{-3}d(v)$.

###### Proof.

Since $|N_{v}|=d^{adm}(v)+1\leq 2\varepsilon^{-3}d(v)+1$, we only need to
upper bound $|K|$ when $v$ belongs to atom $K$. According to the definition 3,
for sufficient small $\epsilon$, at least half of vertices in $K$ are
neighbors of $v$, so $|K|\leq 2d(v)+1$. Therefore $|N(v)|\leq|N_{v}|+|K|\leq
6\varepsilon^{-3}d(v)$. ∎

######  Lemma 30.

For all $r\in V,v\in N(r)$, $|N(r)|\leq 12\varepsilon^{-4}d(v)$.

###### Proof.

Since $v\in N(r)$, either $v$ and $r$ are in the same cluster, or $v$ is
admissible to $r$. In the former case, $N(r)=N(v)$, according to lemma 29,
$|N(r)|=|N(v)|\leq 6\varepsilon^{-3}d(v)$. In the latter case, we have degree
similarity between $r$ and $v$. According to lemma 29, $|N(r)|\leq
6\varepsilon^{-3}d(r)\leq 12\varepsilon^{-4}d(v)$. ∎

All clusters in the clustering scheme maintained by our algorithm will be
_almost good clusters_ in the following sense.

######  Definition 31 (Almost good clusters).

We say a cluster $C$ is almost good if there exists a vertex $r\in V$ (not
necessarily in $C$) such that $C\subseteq N(r)$.

######  Lemma 32.

For any vertex $v$ and any almost good cluster $C$ containing $v$, $|C|\leq
12\varepsilon^{-4}d(v)$.

###### Proof.

Since $C$ is almost good, there exists $r\in V$ such that $C\subseteq N(r)$.
According to lemma 30, $|C|\leq|N(r)|\leq 12\varepsilon^{-4}d(v)$. ∎

Since every cluster considered by our local search algorithm will be an almost
good cluster, we have the following corollary.

######  Corollary 33.

Let $\mathcal{C}$ be a clustering maintained by the local search algorithm,
then for any $C\in\mathcal{C},v\in C$, $|C|\leq 12\varepsilon^{-4}d(v)$.

The last estimate we need is the following.

######  Lemma 34.

For any vertex $v$ and any $(\varepsilon,\varepsilon/2)$-good cluster $C$
containing $v$,

$\frac{1}{576}\varepsilon^{8}|D(v)|\cdot|N(v)|\leq\sum_{u\in
C}d^{adm}(u)\leavevmode\nobreak\ .$

###### Proof.

Since $C$ is a $(\varepsilon,\varepsilon/2)$-good cluster, we have
$|C|\geq\frac{1}{2}\varepsilon d(v)\geq\frac{1}{12}\varepsilon^{4}|N(v)|$. The
second inequality follows from lemma 29.

If $|K(v)|\geq\alpha|N(v)|$, then

$\sum_{u\in C}d^{\text{adm}}(u)\geq\sum_{u\in
K(v)}d^{\text{adm}}(u)\geq\alpha|N(v)|\cdot|D(v)|\leavevmode\nobreak\ .$

If $|K(v)|\leq\alpha|N(v)|$, then

$\displaystyle\sum_{u\in C}d^{\text{adm}}(u)$ $\displaystyle\geq\sum_{u\in
C\setminus K(v)}d^{\text{adm}}(u)$ $\displaystyle\geq(|C|-|K(v)|)(|C|-1)$
$\displaystyle\geq\frac{1}{2}|C|(|C|-|K(v)|)$
$\displaystyle\geq\frac{1}{24}\varepsilon^{4}\left(\frac{1}{12}\varepsilon^{4}-\alpha\right)|N(v)|^{2}$

Let $\alpha=\frac{1}{24}\varepsilon^{8}$, the lemma always holds. ∎

##### Costs and estimated costs.

As discussed in the introduction, we try to find a cluster that improves our
local search solution with the help of sampling. We will sample a number of
vertices from the sought cluster and then, for every other vertex $v$, we try
to guess whether $v$ is in the sought cluster by looking at how many vertices
from the sample are adjacent to $v$. To this end, we will need the following
definitions.

######  Definition 35.

Consider a clustering $\mathcal{C}$ of the graph and let $v$ be a vertex,
$C(v)\in\mathcal{C}$ be its cluster and $K$ be an arbitrary set of vertices.
Under weight $w$, we define $\mathrm{CostStays}_{w}(K,v)$ to be the total
weight of edges $(u,v)$ that are violated in $\mathcal{C}+(K\setminus\\{v\\})$
and $\mathrm{CostMoves}_{w}(K,v)$ to be the total weight of edges $(u,v)$ that
are violated in $\mathcal{C}+(K\cup\\{v\\})$. By definition,

  1. 1.

$\mathrm{CostStays}_{w}(K,v)=d_{w}(v)-d_{w}(v,C(v))+d_{w}(v,C(v)\cap
K)+|C(v)|-|C(v)\cap K|-d(v,C(v))+d(v,C(v)\cap K)-1$.

  2. 2.

$\mathrm{CostMoves}_{w}(K,v)=d_{w}(v)-d_{w}(v,K)+|K|-d(v,K)-1$.

######  Lemma 36.

Let $\eta_{0}>1$. Consider a clustering $\mathcal{C}$ of the graph and let $v$
be a vertex, $C(v)$ be its cluster and $K$ be an arbitrary set of vertices of
size $s$. Furthermore, let $S=\\{u_{1},\dots,u_{\eta_{0}}\\}$ be a sequence of
uniform sample of $K$. Consider the clustering $\mathcal{C}+K$ We define the
following random variables

  * •

$\mathrm{EstCostStays}_{w}(S,s,v)$ :=
$d_{w}(v)-d_{w}(v,C(v))-1+\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}[u_{i}\in
C(v)](d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1)$.

  * •

$\mathrm{EstCostMoves}_{w}(S,s,v)$ :=
$d_{w}(v)+s-1-\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\}))$.

where $[\text{boolean expression}]$ is the indicator function.

We have that

  1. 1.

ExpCostStays($s,v$) := $\mathbb{E}_{S}[\text{EstCostStays($S,s,v$)}]=$
CostStays, and

  2. 2.

ExpCostMoves($s,v$) := $\mathbb{E}_{S}[\text{EstCostMoves($S,s,v$)}]=$
CostMoves.

The next two lemmata say that looking at the estimated costs indeed
approximates the real cost well, even if we know the actual size of the
cluster only approximately.

######  Lemma 37.

Let $\eta_{0}=\eta^{5}>0$. Consider the setting of Lemma 36, a vertex $v$ in
cluster $C(v)$, an arbitrary cluster $K$ of size $s$ and a sequence $S$ of
random uniform sample of $K$ of length $\eta_{0}$. Then, with probability at
least $1-4\exp\left(-\frac{1}{2}\eta\right)$ we have that the following two
inequalities hold:

$\mathrm{EstCostStays}_{w}(S,s,v)\in\mathrm{ExpCostStays}_{w}(s,v)\pm\frac{1}{\eta^{2}}Ws$
(14)
$\mathrm{EstCostMoves}_{w}(S,s,v)\in\mathrm{ExpCostMoves}_{w}(s,v)\pm\frac{1}{\eta^{2}}Ws$
(15)

###### Proof.

Let $X_{i}=\frac{s}{\eta_{0}}[u_{i}\in
C(v)](d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1)$ be an random variable, we have
$X_{i}\in\left[-\frac{s}{\eta_{0}},\frac{s}{\eta_{0}}W\right]$. Equation 14
holds if and only if

$\left|\sum_{i=1}^{\eta_{0}}(X_{i}-E[X_{i}])\right|\leq\frac{1}{\eta^{2}}Ws\leavevmode\nobreak\
.$

According to Hoeffding’s inequality, we have

$\displaystyle\mathbf{Pr}\left[\left|\sum_{i=1}^{\eta_{0}}(X_{i}-E[X_{i}])\right|\geq\frac{1}{\eta^{2}}Ws\right]$
$\displaystyle\leq
2\exp\left(-\frac{2\left(\frac{1}{\eta^{2}}Ws\right)^{2}}{\eta_{0}\left(\frac{s}{\eta_{0}}(W+1)^{2}\right)}\right)$
$\displaystyle\leq
2\exp\left(-\frac{2\eta_{0}W^{2}}{\eta^{4}(W+1)^{2}}\right)$
$\displaystyle\leq 2\exp\left(-\frac{1}{2}\eta\right)$

So eq. 14 holds with probability at least
$1-2\exp\left(-\frac{1}{2}\eta\right)$.

Similarly, let
$Y_{i}=\frac{s}{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\}))$. Equation 15
holds if and only if

$\left|\sum_{i=1}^{\eta_{0}}(Y_{i}-E[Y_{i}])\right|\leq\frac{1}{\eta^{2}}Ws\leavevmode\nobreak\
.$

According to Hoeffding’s inequality, we have

$\displaystyle\mathbf{Pr}\left[\left|\sum_{i=1}^{\eta_{0}}(Y_{i}-E[Y_{i}])\right|\geq\frac{1}{\eta^{2}}Ws\right]$
$\displaystyle\leq
2\exp\left(-\frac{2\left(\frac{1}{\eta^{2}}Ws\right)^{2}}{\eta_{0}\left(\frac{s}{\eta_{0}}(W+1)^{2}\right)}\right)$
$\displaystyle\leq
2\exp\left(-\frac{2\eta_{0}W^{2}}{\eta^{4}(W+1)^{2}}\right)$
$\displaystyle\leq 2\exp\left(-\frac{1}{2}\eta\right)$

So eq. 15 holds with probability at least
$1-2\exp\left(-\frac{1}{2}\eta\right)$.

By union bound, both eq. 15 and eq. 14 hold with probability at least
$1-4\exp\left(-\frac{1}{2}\eta\right)$. ∎

######  Lemma 38.

Let $\eta_{0}=\eta^{5}>0$. Consider the setting of Lemma 36, a vertex $v$ in
cluster $C(v)$, an arbitrary cluster $K$ of size $s$ and a sequence $S$ of
random uniform sample of $K$ of length $\eta_{0}$. Let
$\tilde{s}\in(1\pm\epsilon^{\prime})s$. Then, with probability at least
$1-4\exp\left(-\frac{1}{2}\eta\right)$ we have that the following two
inequalities hold:

$\mathrm{EstCostStays}_{w}(S,\tilde{s},v)\in\mathrm{ExpCostStays}_{w}(s,v)\pm\left(\frac{1}{\eta^{2}}Ws+2\epsilon^{\prime}Ws\right)$
(16)
$\mathrm{EstCostMoves}_{w}(S,\tilde{s},v)\in\mathrm{ExpCostMoves}_{w}(s,v)\pm\left(\frac{1}{\eta^{2}}Ws+2\epsilon^{\prime}Ws\right)$
(17)

###### Proof.

$\displaystyle|\mathrm{EstCostStays}_{w}(S,s,v)-\mathrm{EstCostStays}_{w}(S,\tilde{s},v)|$
$\displaystyle=\left|\frac{s-\tilde{s}}{\eta_{0}}\sum_{i=1}^{\eta_{0}}[u_{i}\in
C(v)](d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1)\right|$
$\displaystyle\leq\frac{|s-\tilde{s}|}{\eta_{0}}\sum_{i=1}^{\eta_{0}}|d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1|$
$\displaystyle\leq\frac{\epsilon^{\prime}s}{\eta_{0}}\eta_{0}W$
$\displaystyle<2\epsilon^{\prime}Ws$

So eq. 14 implies eq. 16. Similarly,

$\displaystyle|\mathrm{EstCostMoves}_{w}(S,s,v)-\mathrm{EstCostMoves}_{w}(S,\tilde{s},v)|$
$\displaystyle=\left|\frac{s-\tilde{s}}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\}))\right|$
$\displaystyle\leq\frac{|s-\tilde{s}|}{\eta_{0}}\sum_{i=1}^{\eta_{0}}|d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})|$
$\displaystyle\leq\frac{\epsilon^{\prime}s}{\eta_{0}}\eta_{0}(W+1)$
$\displaystyle<2\epsilon^{\prime}Ws$

So eq. 15 implies eq. 17. Therefore this lemma holds from lemma 37. ∎

######  Corollary 39.

In the setting of lemma 38, let $\epsilon^{\prime}=\frac{1}{\eta^{2}}$, with
probability at least $1-4\exp\left(-\frac{1}{2}\eta\right)$ we have that the
following two inequalities hold:

$\mathrm{EstCostStays}_{w}(S,\tilde{s},v)\in\mathrm{ExpCostStays}_{w}(s,v)\pm\frac{3}{\eta^{2}}Ws$
(18)
$\mathrm{EstCostMoves}_{w}(S,\tilde{s},v)\in\mathrm{ExpCostMoves}_{w}(s,v)\pm\frac{3}{\eta^{2}}Ws$
(19)

In the remainder of this section, we fix
$\epsilon^{\prime}=\frac{1}{\eta^{2}}$ for simplicity.

##### The algorithm.

The algorithm maintains a tentative solution $\mathcal{C}$ and iteratively
tries to find an improving cluster. The algorithm is parameterized by an
integer parameter $\eta>0$, which we will fix later. In one step, the
algorithm invokes the following GenerateCluster routine for any choice of
$r\in V(G)$, multisets $(S^{i})_{i=1}^{\eta}$ of vertices in $N(r)$ of size
$\eta^{5}$ each, and integers $(s^{i})_{i=1}^{\eta}\in[|V|]^{\eta}$. If any of
the run finds a cluster $S^{\prime}$ such that
$\textsc{Cost}_{w}(\mathcal{C}+S^{\prime})<\textsc{Cost}_{w}(\mathcal{C})$, it
picks $S^{\prime}$ that minimizes $\textsc{Cost}_{w}(\mathcal{C}+S^{\prime})$,
replaces $\mathcal{C}:=\mathcal{C}+S^{\prime}$ and restarts. If no such
$S^{\prime}$ is found, the algorithm terminates and returns the current
solution $\mathcal{C}$ as the final output.

Polynomial-Time-Local-Search($\eta$) • Compute an atomic pre-clustering
$(\mathcal{K},E^{\text{adm}})$ using the Precluster algorithm. •
$\mathcal{C}\leftarrow\\{K\mid K\in\mathcal{K}\\}\cup\\{\\{v\\}\mid v\in
V\setminus(\cup_{K\in\mathcal{K}}K)\\}$. • Do – For each vertex $r$, for each
collection of $\eta$ (not necessarily disjoint) multisets
$\mathcal{S}=S^{1},\ldots,S^{\eta}$ each of $\eta_{0}=\eta^{5}$ vertices in
$N(r)$, and each collection of $\eta$ integers
$\vec{s}=s^{1},\ldots,s^{\eta}\in[|V|]$,
$\mathcal{C}(\mathcal{S},\vec{s})\leftarrow\mathcal{C}+$
GenerateCluster($\mathcal{C},r,S^{1},\ldots,S^{\eta},s^{1},\ldots,s^{\eta}$).
– Let $\mathcal{S}^{*},\vec{s}^{*}$ be the pair such that the cost of
$\mathcal{C}(\mathcal{S}^{*},\vec{s}^{*})$ is minimized. – If the
$\textsc{Cost}(\mathcal{C}+\mathcal{S}^{*})<\textsc{Cost}(\mathcal{C})$: *
has_improved $\leftarrow$ true; *
$\mathcal{C}\leftarrow\mathcal{C}(\mathcal{S}^{*},\vec{s}^{*})$; – Else
has_improved $\leftarrow$ false • While has_improved • Output $\mathcal{C}$

GenerateCluster($\mathcal{C},r,S^{1},\ldots,S^{\eta},s^{1},\ldots,s^{\eta}$) •
$S^{\prime}\leftarrow K(r)$. • Let $D_{r}^{1},\ldots,D_{r}^{\eta}$ be an
arbitrary partition of the vertices of $D(r)$ into equal-size parts, • For
$i=1,\ldots,\eta$: – For each vertex $v\in D_{r}^{i}$, * Let $C(v)$ be the
current cluster of $v$. * If EstCostStays($S^{i},s_{i},v$) $>$
EstCostMoves($S^{i},s_{i},v$) + $6\eta^{-1}W|N(r)|$,
then $S^{\prime}\leftarrow S^{\prime}\cup\\{v\\}$. • Return $S^{\prime}$.

Note that in section 3.2, we only use $\\{1,1.5,2\\}$ in the weight, and
therefore we only have polynomial many possible cost for a clustering scheme.
Therefore, Polynomial-Time-Local-Search runs in polynomial iterations and
takes polynomial time, as $\eta,\epsilon$ be some constants. In the next
sections, we will remove this assumption and consider arbitrary bounded weight
function. And the following lemma shows that for sufficiently large integer
$\eta$, the above algorithm indeed finds a $\gamma$-good local optimum. Note
that for the polynomial-time implementation, we would only need a weaker
statement saying that there exists a choice of $(S^{i})_{i=1}^{\eta}$ and
$(\tilde{s}^{i})_{i=1}^{\eta}$ for which the statement holds, as we iterate
over all possible choices. However, the fact that a vast majority of choices
leads generating an improving cluster $S^{\prime}$ is crucial for subsequent
running time improvements, where we will only sample sets $S^{i}$ and integers
$\tilde{s}^{i}$.

######  Lemma 40.

Let $0<\gamma<\varepsilon^{13}/4$ and $\eta>4608W\varepsilon^{-8}\gamma^{-1}$
be a sufficiently large constant so that $\exp(\eta)>400\eta\varepsilon^{-6}$.

Consider a clustering $\mathcal{C}$ maintained by the local search algorithm
and assume that there exists a vertex $r$, and a
$(\varepsilon,\varepsilon/2)$-good cluster $C$ with $K(r)\subseteq C\subseteq
N(r)$ such that $|C|>1$ and

$\textsc{Cost}_{w}(\mathcal{C}+C)+\gamma\sum_{u\in
C}d^{\text{adm}}(u)\leq\textsc{Cost}_{w}(\mathcal{C})\leavevmode\nobreak\ .$

Then there exists a collection of sets $C^{*}_{1},\dots,C^{*}_{\eta}$ of
vertices with the following properties. First, $K(r)\subseteq
C^{*}_{i}\subseteq N(r)$,
$|C^{*}_{i}|\geq\frac{1}{112896W}\gamma\varepsilon^{14}|N(r)|$. Second, let
$\mathcal{S}=S^{1},\ldots,S^{\eta}$, where $S^{i}$ is an uniform sample of
$C^{*}_{i}$ of size $\eta^{5}$, let
$\vec{s}=(\tilde{s}^{1},\ldots,\tilde{s}^{\eta})\in[|V|]^{\eta^{5}}$ such that
$\tilde{s}\in(1\pm\epsilon^{\prime})|C^{*}_{i}|$. Then with probability at
least $1-2\eta\exp(-\eta)$, the cluster $S^{\prime}$ output by
GenerateCluster($\mathcal{C},r,K(r),\mathcal{S},\vec{s})$ satisfies

$\textsc{Cost}_{w}(\mathcal{C}+S^{\prime})\leq\textsc{Cost}_{w}(\mathcal{C}+C)+\frac{\gamma}{2}\sum_{u\in
C}d^{\text{adm}}(u).$

###### Proof.

Fix $r$ as in the lemma statement and let

$C^{*}=\text{argmin}_{K(r)\subseteq Q\subseteq
N(r)}\textsc{Cost}_{w}(\mathcal{C}+Q).$

That is, $C^{\ast}$ is the most improving cluster in $N(r)$ containing $K(r)$.
Since $C$ is $(\varepsilon,\varepsilon/2)$-good cluster containing $r$, and
that each $(\varepsilon,\varepsilon/2)$-good cluster contains at most one
atom, we have that $C\subseteq N(r)$. Thus, we have that
$\textsc{Cost}_{w}(\mathcal{C}+C^{*})\leq\textsc{Cost}_{w}(\mathcal{C}+C)\leq\textsc{Cost}_{w}(\mathcal{C})-\gamma\sum_{u\in
C}d^{\text{adm}}(u)$, so it is enough to show that GenerateCluster outputs a
cluster of cost at most
$\textsc{Cost}(\mathcal{C}+C^{*})+\frac{\gamma}{2}\sum_{u\in
C}d^{\text{adm}}(u)$.

Since $C$ is a $(\varepsilon,\varepsilon/2)$-good cluster containing $K(r)$,
$|C|\geq\varepsilon d(v)$ for all $v\in K(r)$, therefore
$|N(r)|\geq|C|\geq\frac{1}{2}\varepsilon d(v)$.

######  Claim 41.

For any $v\in N(r)$,

$d(v)\leq 4\varepsilon^{-2}|N(r)|\quad\mathrm{and}\quad d^{\text{adm}}(v)\leq
8\varepsilon^{-5}|N(r)|.$

###### Proof.

We first prove the first inequality.

If $r\in K(r)$, then $|N(r)|\geq|C|\geq\frac{1}{2}\varepsilon d(v)$;
otherwise, $v$ is admissible to $r$, therefore $d(v)\leq
2\varepsilon^{-1}d(r)\leq 4\varepsilon^{-2}|N(r)|$.

The second inequality follows from the first and the condition
$d^{\text{adm}}(v)\leq 2\varepsilon^{-3}d(v)$. ∎

Let $s^{*}=|C^{*}|$. Next, we will prove a lower bound on $s^{*}$. To this
end, we show a quite brute-force estimate that adding one new cluster to a
clustering scheme cannot improve the cost by too much.

######  Claim 42.

Let $\mathcal{C}$ be a clustering maintained by the local search algorithm,
$C\subseteq|N(r)|$ is any cluster, then

$\textsc{Cost}_{w}(\mathcal{C})-49W\varepsilon^{-6}|C|\cdot|N(r)|\leq\textsc{Cost}_{w}(\mathcal{C}+C).$

###### Proof.

We split the cost improvement into two terms. The first term is the
improvement on $E^{+}$, which is at most $W\cdot\frac{1}{2}|C|(|C|-1)\leq
W\cdot|C|\cdot|N(r)|$. The second term is the improvement on $E^{-}$, which is
at most the maximum amount of cost we paid before. Let $v$ be an arbitrary
vertex in $C$, $C_{i}$ be the cluster in $\mathcal{C}$ containing $v$, the
minus cost we pay in $\mathcal{C}$ at $v$ is at most $|C_{i}|-1$. According to
Corollary 33, $|C_{i}|\leq 12\varepsilon^{-4}d(v)$. According to claim 41, for
all $v\in N(r)$, $d(v)\leq 4\varepsilon^{-2}|N(r)|$. So we have the total
improvement on $E^{-}$ is at most
$12\varepsilon^{-4}|C|\cdot(4\varepsilon^{-2}|N(r)|)=48\varepsilon^{-6}|C|\cdot|N(r)|$.
Together with the improvement in the first part, the whole claim holds. ∎

Observe that by Lemma 34, we have

$\sum_{u\in
C}d^{\text{adm}}(u)\geq\frac{1}{576}\varepsilon^{8}|D(r)|\cdot|N(r)|$

Hence,

$\textsc{Cost}_{w}(\mathcal{C}+C^{*})\leq\textsc{Cost}_{w}(\mathcal{C})-\gamma\sum_{u\in
C}d^{\text{adm}}(u)\leq\textsc{Cost}(\mathcal{C})-\frac{1}{576}\gamma\varepsilon^{8}|D(r)|\cdot|N(r)|.$

Together with Claim 42 for $C^{*}$, it follows that

$s^{*}=|C^{*}|\geq\frac{1}{28224W}\gamma\varepsilon^{14}|D(r)|.$ (20)

Let $v$ be a vertex in $D(r)$, according to the optimality of $C^{*}$, we have

  1. 1.

if $v$ in $C^{*}$, then
$\textsc{Cost}_{w}(\mathcal{C}+(C^{*}\setminus\\{v\\}))\geq\textsc{Cost}_{w}(\mathcal{C}+C^{*})$;
and

  2. 2.

if $v$ is not in $C^{*}$ then
$\textsc{Cost}_{w}(\mathcal{C}+(C^{*}\cup\\{v\\}))\geq\textsc{Cost}_{w}(\mathcal{C}+C^{*})$.

To analyze the algorithm, let $S^{\prime 1},\ldots,S^{\prime\eta}$ be the set
of elements in set $S^{\prime}$ at the beginning of the $i$th iteration of the
for loop. We define

$C^{*}_{i}=S^{\prime
i}\cup\mathrm{argmin}\left\\{\textsc{Cost}_{w}(\mathcal{C}+(S^{\prime i}\cup
T))\leavevmode\nobreak\ \Big{|}\leavevmode\nobreak\
T\subseteq\bigcup_{j=i}^{\eta}D_{r}^{i}\right\\}.$

Let $S^{i}$ be a uniform sample of the cluster $C^{*}_{i}$ and
$s_{i}=|C^{*}_{i}|$. We want to show the following claim.

######  Claim 43.

With probability at least $1-2\exp(-\frac{1}{2}\eta)$,

$\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i+1})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})\leq
4W\eta^{-2}|D(r)|\cdot|N(r)|.$

Assuming the claim is true, with probability at least
$1-2\eta\exp(-\frac{1}{2}\eta)$, this claim holds for all $i=1,\dots,\eta$.
Then the lemma follows by observing that $S^{\prime}=C^{*}_{\eta+1}$ and
$C^{*}_{1}=C^{*}$. By telescoping and Lemma 34, we have

$\displaystyle\textsc{Cost}_{w}(\mathcal{C}+S^{\prime})$
$\displaystyle=\textsc{Cost}_{w}(\mathcal{C}+C^{*})+\sum_{i=1}^{\eta}(\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i+1})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i}))$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C}+C^{*})+4W\eta^{-1}\cdot|D(r)|\cdot|N(r)|$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C}+C^{*})+4W\eta^{-1}\cdot
576\varepsilon^{-8}\sum_{u\in C}d^{\text{adm}}(u)$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C}+C)+\frac{\gamma}{2}\sum_{u\in
C}d^{\text{adm}}(u)$

The last inequality follows from the assumption
$\eta>4608W\varepsilon^{-8}\gamma^{-1}$.

The only thing we miss is to show a lower bound on $|C^{*}_{i}|$. By
telescoping, we have

$\displaystyle\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})$
$\displaystyle=\textsc{Cost}_{w}(\mathcal{C}+C^{*})+\sum_{j=1}^{i-1}(\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{j+1})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i}))$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C}+C^{*})+(i-1)\cdot
4W\eta^{-2}|D(r)|\cdot|N(r)|$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C})-\frac{1}{576}\gamma\varepsilon^{8}|D(r)|\cdot|N(r)|+4W\eta^{-1}|D(r)|\cdot|N(r)|$
$\displaystyle\leq\textsc{Cost}_{w}(\mathcal{C})-\frac{1}{1152}\gamma\varepsilon^{8}|D(r)|\cdot|N(r)|$

The last inequality holds from the assumption
$\eta>4608W\varepsilon^{-8}\gamma^{-1}$ and $\varepsilon<1$. Together with
claim 42 for $C^{*}_{i}$, it follows that
$|C^{*}_{i}|\geq\frac{1}{56448W}\gamma\varepsilon^{14}|D(r)|$. Since
$K(r)\subseteq C^{*}_{i}$ and $|N(r)|=|D(r)|+|K(r)|$, we have

$|C^{*}_{i}|\geq\frac{1}{112896W}\gamma\varepsilon^{14}|N(r)|.$ (21)

###### Proof of Claim 43.

Let

$Q_{i}=S^{\prime
i+1}\cup\left(C_{i}^{\ast}\cap\bigcup_{j=i+1}^{\eta}D_{r}^{j}\right).$

By the definition of $C^{*}_{i+1}$, we have

$\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i+1})\leq\textsc{Cost}_{w}(\mathcal{C}+Q_{i}),$

so it is sufficient to prove that

$\textsc{Cost}_{w}(\mathcal{C}+Q_{i})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})\leq
4W\eta^{-2}|D(r)|\cdot|N(r)|.$

We observe that

$\textsc{Cost}_{w}(\mathcal{C}+Q_{i})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})\leq
W|Q_{i}\Delta C^{*}_{i}|^{2}+\sum_{v\in Q_{i}\Delta
C^{*}_{i}}\left(\textsc{Cost}_{w}(\mathcal{C}+Q_{i},v)-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i},v)\right)\leavevmode\nobreak\
,$

where $\Delta$ denote the symmetric difference of two sets. Fix a vertex $v\in
Q_{i}\Delta C^{*}_{i}$ and let $C\in\mathcal{C}$ be the cluster containing
$v$. We have

$\textsc{Cost}_{w}(\mathcal{C}+Q_{i},v)-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i},v)\leq
W(|C|+|Q_{i}|+|C^{*}_{i}|)\leavevmode\nobreak\ ,$

where $\textsc{Cost}_{w}(\mathcal{C},v)$ is the total cost paid by clustering
scheme $\mathcal{C}$ for all edges or non-edges incident to $v$. According to
Corollary 33, $|C|\leq 12\varepsilon^{-4}d(v)\leq 48\varepsilon^{-6}|N(r)|$.
Since $Q_{i},C^{*}_{i}$ are subsets of $N(r)$, $|Q_{i}|\leq|N(r)|$,
$|C^{*}_{i}|\leq|N(r)|$, therefore

$\textsc{Cost}_{w}(\mathcal{C}+Q_{i},v)-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i},v)\leq
W(|C|+|Q_{i}|+|C^{*}_{i}|)\leq 50\varepsilon^{-6}W|N(r)|.$

A vertex $v\in Q_{i}\Delta C^{*}_{i}$ can be one of the following three types.

  * •

$v$ is a _missing_ node if $v\in Q_{i}$ and $v\notin C^{*}_{i}$.

  * •

$v$ is a _core_ node if $v\in C^{*}_{i},v\notin Q_{i}$ and

$\mathrm{CostMoves}(C^{*}_{i},v)+12\eta^{-2}W|N(r)|<\mathrm{CostStays}(C^{*}_{i},v).$

  * •

$v$ is a _non-core_ node if $v\in C^{*}_{i},v\notin Q_{i}$ and

$\mathrm{CostMoves}(C^{*}_{i},v)+12\eta^{-2}W|N(r)|\geq\mathrm{CostStays}(C^{*}_{i},v).$

In the following part, we will split the cost difference into vertices of the
three types, and give a bound separately.

Missing nodes. If $v\notin C^{*}_{i}$, by definition of $C^{*}_{i}$,
$\mathrm{CostMoves}(C^{*}_{i},v)\geq\mathrm{CostStays}(C^{*}_{i},v)$.
According to Corollary 39, with probability at most
$4\exp\left(-\frac{1}{2}\eta\right)$, we have

$\mathrm{EstCostMoves}(S^{i},\tilde{s}^{i},v)+6\eta^{-2}W|N(r)|<\mathrm{EstCostStays}(S^{i},\tilde{s}^{i},v).$

Therefore $v\in Q_{i}$ with probability at most
$4\exp\left(-\frac{1}{2}\eta\right)$, and the expected size of $Q_{i}\setminus
C^{*}_{i}$ is bounded by $4\exp\left(-\frac{1}{2}\eta\right)\eta^{-1}|D(r)|$.
Hence, there are more than $4\exp\left(-\eta\right)\eta^{-1}|D(r)|$ missing
nodes with probability at most $\exp\left(-\frac{1}{2}\eta\right)$.

Core nodes. If $v\in C^{*}_{i}$ is a core node, by definition of core node,

$\mathrm{CostMoves}(C^{*}_{i},v)+12\eta^{-2}W|N(r)|<\mathrm{CostStays}(C^{*}_{i},v).$

According to corollary 39, we have

$\mathrm{EstCostMoves}(S^{i},\tilde{s}^{i},v)+6\eta^{-2}W|N(r)|\geq\mathrm{EstCostStays}(S^{i},\tilde{s}^{i},v)$

with probability at most $4\exp\left(-\frac{1}{2}\eta\right)$. Therefore
$v\notin Q_{i}$ with probability at most $4\exp\left(-\frac{1}{2}\eta\right)$.
Similarly as before, there are more than
$4\exp\left(-\eta\right)\eta^{-1}|D(r)|$ core nodes with probability at most
$\exp\left(-\frac{1}{2}\eta\right)$.

Non-core nodes. If $v\in C^{*}_{i}$ is a non-core node, then

$\displaystyle\textsc{Cost}_{w}(\mathcal{C}+Q_{i},v)-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i},v)$
$\displaystyle\qquad\leq\mathrm{CostStays}(C^{*}_{i},v)-\mathrm{CostMoves}(C^{*}_{i},v)+W|Q_{i}\Delta
C^{*}_{i}|$ $\displaystyle\qquad\leq 12\eta^{-2}W|N(r)|+W\eta^{-1}|D(r)|$
$\displaystyle\qquad\leq 2\eta^{-1}W|N(r)|.$

In the inequalities, we use the fact that $Q_{i}\Delta C_{i}^{\ast}\subseteq
D_{i}^{r}$, $|D_{i}^{r}|=\eta^{-1}|D(r)|$ and $\eta<1/12,W>1$.

Summing up the total cost difference over all vertices of the three types, we
have

$\displaystyle\textsc{Cost}_{w}(\mathcal{C}+Q_{i})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})$
$\displaystyle\qquad\leq W|Q_{i}\Delta C_{i}^{\ast}|^{2}+\sum_{v\in
Q_{i}\Delta
C^{*}_{i}}\left(\textsc{Cost}_{w}(\mathcal{C}+Q_{i},v)-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i},v)\right)$
$\displaystyle\qquad\leq W\eta^{-2}|D(r)|^{2}+2\cdot
4\exp(-\eta)\eta^{-1}|D(r)|\cdot
50\varepsilon^{-6}W|N(r)|+\eta^{-1}|D(r)|\cdot 2\eta^{-1}W|N(r)|$
$\displaystyle\qquad\leq 4\eta^{-2}W|D(r)|\cdot|N(r)|.$

The last inequality holds since $\exp(\eta)>400\eta\varepsilon^{-6}$. This
finishes the proof of the claim. ∎

This finishes the proof of the lemma. ∎

######  Corollary 44.

Under the setting of lemma 40, Polynomial-Time-Local-Search will output a
$\gamma$-good local optimum $\mathcal{C}$ with probability at least
$1-2\eta\exp(-\eta)$.

###### Proof.

By contradiction, suppose the output $\mathcal{C}$ from Polynomial-Time-Local-
Search is not a $\gamma$-good local optimum, let
$\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$ be the (unknown)
$\epsilon$-good clustering scheme in $(\mathcal{K},E_{\text{adm}})$ from
theorem 5, by definition

$\sum_{C\in\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}}(\textsc{Cost}_{w}(\mathcal{C})-\textsc{Cost}_{w}(\mathcal{C}+C))>2\gamma|E_{\text{adm}}|\leavevmode\nobreak\
.$

Since $\sum_{C\in\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}}\sum_{u\in
C}d^{\text{adm}}(u)=2|E_{\text{adm}}|$, we have

$\sum_{C\in\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}}(\textsc{Cost}_{w}(\mathcal{C})-\textsc{Cost}_{w}(\mathcal{C}+C)-\gamma\sum_{u\in
C}d^{\text{adm}}(u))>0\leavevmode\nobreak\ .$

According to pigeonhole principle, there exists a cluster
$C^{*}_{i}\in\mathcal{C}^{*}_{(\mathcal{K},E_{\text{adm}})}$ such that

$\textsc{Cost}_{w}(\mathcal{C})-\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})-\gamma\sum_{u\in
C^{*}_{i}}d^{\text{adm}}(u)>0$

According to lemma 40, in this case, with probability at least
$1-2\eta\exp(-\eta)$, in the last iteration, the cluster $S^{\prime}$ output
by GenerateCluster($\mathcal{C},r,K(r),\mathcal{S},\vec{s})$ in the last
iteration satisfies

$\textsc{Cost}_{w}(\mathcal{C}+S^{\prime})\leq\textsc{Cost}_{w}(\mathcal{C}+C^{*}_{i})+\frac{\gamma}{2}\sum_{u\in
C^{*}_{i}}d^{\text{adm}}(u)<\textsc{Cost}_{w}(\mathcal{C})-\frac{\gamma}{2}\sum_{u\in
C^{*}_{i}}d^{\text{adm}}(u)\leavevmode\nobreak\ ,$

so the iteration will continue, which lead to a contradiction. ∎

##  5 Faster Implementation of Local Search

In this section, we show a faster implementation of the local search
algorithm, by using sampling to find new improving clusters instead of
enumerating a lot. This is not the end, but both the algorithm and the
analysis are important preparations for our following improvements. We define
$d^{adm}(C)=\sum_{u\in C}d^{adm}(u)$. We will consider the following local
search algorithm, with parameters $\eta,\gamma$ and $s$.

Faster-Local-Search($\eta,\gamma,s$) • Compute an atomic pre-clustering
$(\mathcal{K},E^{\text{adm}})$ using the Precluster algorithm. •
$\mathcal{C}\leftarrow\\{K\mid K\in\mathcal{K}\\}\cup\\{\\{v\\}\mid v\in
V\setminus(\cup_{K\in\mathcal{K}}K)\\}$. • Do many rounds of the following
until $\mathcal{C}$ does not change in $\Theta(n\log n)$ consecutive rounds: –
Sample a vertex $r^{\prime}$ with probability $\frac{1}{n}$ and try to improve
the clustering by the singleton $\\{r^{\prime}\\}$. – Sample a vertex $r$ with
probability $\frac{1}{n\cdot d(r)}$, or instantly finish this round with
probability $1-\sum_{r\in V}\frac{1}{n\cdot d(r)}$. – Uniformly sample $\eta$
subsets $T^{1},\dots,T^{\eta}$ of size $s$ from $N(r)$. – For each collection
of $\eta$ (not necessarily disjoint) multisets
$\mathcal{S}=S^{1},\ldots,S^{\eta}$ each of $\eta^{5}$ vertices in $T^{i}$
respectively, and each collection of $\eta$ integers
$\vec{s}=s^{1},\ldots,s^{\eta}\in\\{\epsilon
d(r)(1+\epsilon^{\prime})^{k}/2|0\leq
k\leq\log_{1+\epsilon^{\prime}}(4/\epsilon)\\}$,
$\mathcal{C}(\mathcal{S},\vec{s})\leftarrow\mathcal{C}+$
GenerateCluster($\mathcal{C},r,S^{1},\ldots,S^{\eta},s^{1},\ldots,s^{\eta}$).
– Let $\mathcal{S}^{*},\vec{s}^{*}$ be the pair such that the cost of
$\mathcal{C}(\mathcal{S}^{*},\vec{s}^{*})$ is minimized. – If the cost of
$\mathcal{C}(\mathcal{S}^{*},\vec{s}^{*})$ is at least
$\gamma|E_{\text{adm}}|/n$ less than the cost of $\mathcal{C}$: *
$\mathcal{C}\leftarrow\mathcal{C}(\mathcal{S}^{*},\vec{s}^{*})$; • Output
$\mathcal{C}$

##### The size of the sampled set $S$.

For GenerateCluster to work, we need $S^{i}$ to be a uniform sample of
$C_{i}^{*}$. When $|T^{i}\cap C^{*}_{i}|\geq\eta^{5}$ for all $i$, we have at
least one valid sample $\mathcal{S}$. Since each $T^{i}$ is uniformly sampled
from a superset of $C_{i}^{*}$, the samples we get are uniform.

######  Lemma 45.

If $s>10^{6}\eta^{6}\epsilon^{-27}$, then $|S\cap C^{*}_{i}|\geq\eta^{5}$ for
all $i$ with probability at least $\frac{1}{2}$.

###### Proof.

By Lemma 40, $|C^{*}_{i}|\geq\frac{\epsilon^{27}}{451584}|N(r)|$. It follows
by a Chernoff bound for each $i$ and then a union bound over $i$. ∎

##### The number of rounds.

We know that the cost of our clustering will be improved by at least
$\gamma|E_{\text{adm}}|/n$ per $\Theta(n\log n)$ rounds. On the other hand,
the following lemma provides an upper bound of the initial cost.

######  Lemma 46.

The cost of our initial solution which consists of atoms and singletons is at
most $\textsc{Cost}(\textsc{Opt})+\frac{4}{\epsilon}|E_{adm}|$.

###### Proof.

First, the minus cost paid by our initial solution comes from atoms, so it is
also paid by Opt. The plus cost we paid induced by edges between atoms, or
incident to a singleton in Opt, is again also paid by Opt. So our extra cost
is the number of edges incident to vertices which does not belong to any atom
and is not singleton in Opt. For any such vertex $v$, since there is a good
cluster containing it, $d^{adm}(v)+1\geq\epsilon d(v)$. Hence the additional
cost is at most
$\sum_{v}\frac{d^{adm}(v)+1}{\epsilon}\leq\sum_{v}\frac{2d^{adm}(v)}{\epsilon}\leq\frac{4}{\epsilon}|E_{adm}|$.
∎

So, taking e.g. $\gamma=\epsilon^{20}$, the algorithm stops in
$O_{\epsilon}(n^{2}\log n)$ rounds.

##### Time complexity.

The number of rounds is $O_{\epsilon}(n^{2}\log n)$. In each round, each
vertex $r$ is sampled with probability $\frac{1}{n\cdot d(r)}$. If $r$ is
sampled, in each time calling GenerateCluster, we need to go through its
neighbors and for each neighbor $u$, it takes $O(d(u))$ time to estimate the
costs of moving and staying, so it takes $O_{\epsilon}(d(r)^{2})$ time in
total. There are only constant many $\mathcal{S}$’s and $\vec{s}$’s. So the
total time complexity is $O_{\epsilon}(n^{2}\log n\sum_{r}\frac{1}{n\cdot
d(r)}d(r)^{2})=O_{\epsilon}(mn\log n)$.

##### Correctness.

In each round, we sample each vertex $r$ with probability $\frac{1}{n\cdot
d(r)}$. Suppose the optimal good clustering is
$\textsc{Opt}=\\{C_{1},\dots,C_{k}\\}$. For each cluster $C_{i}$, if it
contains an atom $K$ such that
$\frac{|K|}{|C_{i}|}<\frac{\epsilon^{21}}{576}$, we split the cluster into $K$
and $C_{i}\setminus K$. Let $\textsc{Opt}^{\prime}$ be the new clustering we
get. By the following lemmas, it suffices to compare our solution with
$\textsc{Opt}^{\prime}$ instead of Opt.

######  Lemma 47.

$\textsc{Opt}^{\prime}$ is $(\epsilon,\frac{\epsilon}{2})$-good.

###### Proof.

Consider any cluster $C_{i}\in\textsc{Opt}$. If $C_{i}$ is not split, then
it’s $(\epsilon,\epsilon)$-good and hence
$(\epsilon,\frac{\epsilon}{2})$-good. Otherwise it is split into an atom $K$
and $C_{i}\setminus K$, where $K$ is $(\epsilon,\frac{\epsilon}{2})$-good
since it’s an atom, and $C_{i}\setminus K$ is
$(\epsilon,\frac{\epsilon}{2})$-good because $|C_{i}\setminus
K|\geq\frac{|C_{i}|}{2}$. ∎

######  Lemma 48.

$\textsc{Cost}(\textsc{Opt}^{\prime})\leq(1+\epsilon)\textsc{Cost}(\textsc{Opt})$.

###### Proof.

Consider any cluster $C_{i}\in\textsc{Opt}$. If we split $C_{i}$ into $K$ and
$C_{i}\setminus K$, we can only increase the cost by at most
$|K|\cdot|C_{i}\setminus
K|\leq\frac{\epsilon^{21}}{576}|C_{i}|\cdot|C_{i}\setminus
K|\leq\frac{\epsilon^{21}}{576}|N(K)|\cdot|D(K)|$ since $C_{i}\subseteq N(K)$.
Then by Lemma 34, this is at most $\frac{\epsilon^{13}}{4}d^{adm}(C_{i})$.
Summing over all clusters, the lemma follows from Theorem 5. ∎

Consider any cluster $C_{i}^{\prime}\in\textsc{Opt}^{\prime}$ of size larger
than $1$. If it contains an atom $K$, we will hit $K$ with probability at
least $\frac{\epsilon|K|}{n|C_{i}^{\prime}|}\geq\frac{\epsilon^{22}}{576n}$;
otherwise we will hit some vertex in $C_{i}^{\prime}$ with probability at
least $\frac{\epsilon}{n}$. For $|C_{i}^{\prime}|=1$, we will hit it with
probability $\frac{1}{n}$.

Define
$\Delta_{i}=\max\\{\textsc{Cost}(\mathcal{C})-\textsc{Cost}(\mathcal{C}+C_{i}^{\prime})-\gamma
d^{adm}(C_{i}^{\prime}),0\\}$ for $0<\gamma<\frac{\epsilon^{13}}{4}$, and
$\Delta=\sum_{i}\Delta_{i}$. If we hit $C_{i}^{\prime}$, by Lemma 40, we can
improve the cost by $\Delta_{i}$ with constant probability. So, if some
$\Delta_{i}$’s are at least $\gamma|E_{adm}|/n$, then in the following
$\Theta_{\epsilon}(n\log n)$ rounds, with high probability we can observe one
of them and improve $\mathcal{C}$. Hence with high probability we won’t stop
with some $\Delta_{i}\geq\gamma|E_{adm}|/n$ at any round $t$. By an union
bound over (a polynomial number of) rounds, we know that with high
probability, we will get a clustering with $\Delta\leq\gamma|E_{adm}|$.

######  Lemma 49.

When $\Delta\leq\gamma|E_{adm}|$, the clustering we have is a
$\frac{3}{2}\gamma$-good local optimum (with respect to
$\textsc{Opt}^{\prime}$).

###### Proof.

By the definition of $\Delta$,
$\sum_{i}(\textsc{Cost}(\mathcal{C})-\textsc{Cost}(\mathcal{C}+C_{i}^{\prime}))\leq\sum_{i}(\Delta_{i}+\gamma
d^{adm}(C_{i}^{\prime}))=\Delta+2\gamma|E_{adm}|$. The lemma simply follows. ∎

We summarize our conclusion in the following theorem.

######  Theorem 50.

With high probability, the clustering $\mathcal{C}$ returned by our faster
implementation is a $\frac{3}{2}\gamma$-good local optimum.

##### Further improvements.

In the remaining sections, we show how to implement our local search algorithm
in MPC, sublinear and streaming models. In each round, our algorithm can be
viewed as two steps:

  * •

Randomly sample at most one pivot vertex;

  * •

Try to improve the current clustering by sampling a constant number of
(possibly dependent) clusters containing the pivot.

In Section 6, we show how to sample multiple pivots in one round, reducing the
number of rounds to a constant, while a similar result with Lemma 40 still
holds.

In Sections 7, we show another way of sampling clusters for each pivot and
estimating the costs, which work in the sublinear and streaming models.

##  6 MPC implementation of local search

In this section we will show how to implement the local search in the MPC
model.

MPC-Local-Search($\eta,\gamma,\gamma^{\prime},s$) • Compute an atomic pre-
clustering using the Precluster algorithm. • $\mathcal{C}\leftarrow\\{K\mid
K\in\mathcal{K}\\}\cup\\{\\{v\\}\mid v\in
V\setminus(\cup_{K\in\mathcal{K}}K)\\}$. • While $\mathcal{C}$ improves: – Do
the following $\Theta_{\epsilon}(\log n)$ times in parallel: * For each
vertex, try to improve the clustering by the singleton. * Select each vertex
$r$ with probability $\frac{\epsilon^{4}\gamma^{\prime}}{24d(r)}$. For each
selected vertex: · Mark all its neighbors. · Check the proportion of its
neighbors that are marked by other selected vertices. Stop if this proportion
is at least $\gamma^{\prime}$. * Uniformly sample $\eta$ subsets
$T^{1},\dots,T^{\eta}$ of size $s$ from $N(r)$. * For each collection of
$\eta$ (not necessarily disjoint) multisets
$\mathcal{S}=S^{1},\ldots,S^{\eta}$ each of at most $\eta^{5}$ vertices in
$T^{i}$ respectively, and each collection of $\eta$ integers
$\vec{s}=s^{1},\ldots,s^{\eta}\in\\{\epsilon
d(r)(1+\epsilon^{\prime})^{k}/2\mid 0\leq
k\leq\log_{1+\epsilon^{\prime}}(4/\epsilon)\\}$,
$f(\mathcal{S},\vec{s})\leftarrow$
GenerateCluster($\mathcal{C},r,S^{1},\ldots,S^{\eta},s^{1},\ldots,s^{\eta}$).
* Find the $(\mathcal{S}^{*},\vec{s}^{*})$ that maximises the improvement
$f(\mathcal{S},\vec{s})$. * If the improvement is at least
$\gamma|E_{\text{adm}}|$: · Update $\mathcal{C}$ by all the new found clusters
using $(\mathcal{S}^{*},\vec{s}^{*})$ in the same way as we generate the
clusters. – Choose the best of the $\Theta(\log n)$ improvements to improve
$\mathcal{C}$ • Output $\mathcal{C}$

Now GenerateCluster only returns the improvement.

GenerateCluster($\mathcal{C},r,S^{1},\ldots,S^{\eta},s^{1},\ldots,s^{\eta}$) •
Let $D_{r}^{1},\ldots,D_{r}^{\eta}$ be an arbitrary partition of the vertices
of $D(r)$ into equal-size parts, • For $i=1,\ldots,\eta$, send $(S^{i},s^{i})$
to every vertex $v\in D_{r}^{i}$. • For each vertex $v\in D_{r}^{i}$ which is
not double-marked: – Let $C(v)$ be the current cluster of $v$. – Compute
EstCostStays($S^{i},s_{i},v$) and EstCostMoves($S^{i},s_{i},v$) parallel from
the neighbors of $v$. – If EstCostStays($S^{i},s_{i},v$) $>$
EstCostMoves($S^{i},s_{i},v$) + $6\eta^{-1}W|N(r)|$,
decide moving to the new cluster. • For each vertex $v\in D_{r}^{i}$ which
decides to move: – Compute the individual improvement parallel from the
neighbors of $v$. • Collect the individual improvements and return.

Previously when sampling, we have sampled each vertex $r$ with probability of
$1/nd(r)$. We will instead sample each vertex $r$ with probability of
$\frac{\epsilon^{4}\gamma^{\prime}}{24d(r)}$. The idea is that this ensures we
hit each cluster with constant probability, while still not having too much
overlap with other vertices that was selected.

######  Lemma 51.

Let $G$ be a graph with an $\epsilon$-good preclustered instance
$(\mathcal{K},E_{adm})$. Let each vertex be selected with probability
$\epsilon^{4}\gamma^{\prime}/24d(r)$. Let $X_{u}$ for each $u\in V(G)$ be the
number of neighbours of $u$ in $D(u)$, that has a neighbour in $E_{adm}$ that
was selected. Then for all $u\in V(G)$

$\mathbf{Pr}[X_{u}\geq\gamma^{\prime}|D(u)|]\leq\frac{1}{2}$

###### Proof.

First, we calculate the expected value of $X_{u}$:

$\displaystyle E[X_{u}]$ $\displaystyle=\sum_{v\in D(u)}\sum_{w\in
N_{v}}\frac{\epsilon^{4}\gamma^{\prime}}{24d(w)}$ $\displaystyle\leq\sum_{v\in
D(u)}\sum_{w\in N_{v}}\frac{\epsilon^{4}\gamma^{\prime}}{12\epsilon d(v)}$
$\displaystyle\leq\sum_{v\in
D(u)}|N_{v}|\frac{\epsilon^{4}\gamma^{\prime}}{12\epsilon d(v)}$
$\displaystyle\leq\sum_{v\in
D(u)}6\epsilon^{-3}d(v)\frac{\epsilon^{4}\gamma^{\prime}}{12\epsilon d(v)}$
$\displaystyle\leq\frac{\gamma^{\prime}|D(u)|}{2}$

by a union bound and degree similarity of neighbours in $E_{adm}$. Then the
lemma follows from Markov’s inequality. ∎

The result of this lemma is that we are only going to stop due to having a too
large amount of the neighbours selected with probability at most $1/2$.

To argue that this algorithm works in MPC model, we first note that each
vertex only needs to broadcast information to its neighbors, or aggregate the
information from its neighbors. When each machine have memory $O(m^{\delta})$,
we can have $O(m^{1-\delta}+n)$ machines each taking care of $O(m^{\delta})$
edges incident to the same vertex. For each vertex with degree larger than
$m^{\delta}$, we can build a $O(\frac{1}{\delta})$-level B-tree with fan-out
$O(m^{\delta})$ to connect all machines related to this vertex. Then the
broadcasting and aggregating can be done in $O(\frac{1}{\delta})$ rounds.

######  Lemma 52.

Let $\mathcal{C}$ be a clustering, let $C$ be the optimal improvement for the
clustering, let $S^{\prime}$ be the improving cluster computed by the near
linear time local search with $r$ as the starting vertex. Let
$S_{mpc}^{\prime}$ be the improving cluster computed by the MPC local search
with $r$ as the selected vertex. Let
$\gamma^{\prime}\leq\frac{1}{2304}\varepsilon^{8}\gamma$ and $\eta$ and
$\gamma$ as defined in lemma 40. Then with probability at least
$\frac{1}{4}-2\eta\exp(-\eta)$

$\textsc{Cost}(\mathcal{C}+S_{mpc}^{\prime})\leq\textsc{Cost}(\mathcal{C}+S^{\prime})+\frac{\gamma}{4}\sum_{u\in
C}d^{adm}(u)$

###### Proof.

It is clear that the setting of this algorithm is the same as in lemma 40,
except that we have possibly lost a $\gamma^{\prime}$ fraction of the optimal
cluster. We therefore compare our solution to the optimal one selected in
lemma 40. We only continue if we have lost less than a $\gamma^{\prime}$
fraction of the neighbors. Using this we can determine how much additional
cost this introduces.

$\displaystyle\textsc{Cost}(\mathcal{C}+S_{mpc}^{\prime})-\textsc{Cost}(\mathcal{C}+S^{\prime})$
$\displaystyle\leq|S_{mpc}^{\prime}||S^{\prime}\setminus S_{mpc}^{\prime}|$
$\displaystyle\leq\gamma^{\prime}|N(r)||D(r)|$

using the fact that $S_{mpc}^{\prime}$ is constructed from the same initial
vertex $r$ and so shares the same atoms as $S^{\prime}$. Furthermore,
$S_{mpc}^{\prime}$ is contained in $N(r)$ while $S^{\prime}\setminus
S_{mpc}^{\prime}$ is contained in $D(r)$. Applying lemma 34, we get that

$\textsc{Cost}(\mathcal{C}+S_{mpc}^{\prime})-\textsc{Cost}(\mathcal{C}+S)\leq
576\varepsilon^{-8}\gamma^{\prime}\sum_{u\in
C}d^{adm}(u)=\frac{\gamma}{4}\sum_{u\in C}d^{adm}(u),$

by the definition of $\gamma^{\prime}$.

With regards to the probability of this happening, observe that the event of
getting enough samples, as described in lemma 45 and lemma 51 are independent
and both with probability $1/2$. By a union bound with the probability of
success from lemma 40 we get the probability of success being
$\frac{1}{4}-2\eta\exp(-\eta)$. ∎

From this we see that each time we select a vertex to construct a cluster
from, with constant probability we are going to get a constant fraction of the
possible improvement for each cluster. Since we can hit a
$\Omega_{\epsilon}(1)$ fraction (instead of $\Omega_{\epsilon}(\frac{1}{n})$
in previous sections) of the clusters in $\textsc{Opt}^{\prime}$ in one round,
a single round will in expectation achieves a constant fraction of the
improvement. This means that between the $\Theta(\log n)$ parallel executions,
at least one will with high probability achieve the improvement if it is
possible.

######  Theorem 53.

When $\Delta\leq\gamma|E_{\text{adm}}|$, the clustering $\mathcal{C}$ returned
by the MPC implementation of local search is a $\frac{3}{2}\gamma$-good local
optimum with high probability.

###### Proof.

Since the setting is essentially the same as in theorem 50, the proof is the
same too. ∎

##  7 Sublinear and Streaming Implementations of Local Search

Recall Lemmas 9, 10 and Theorem 11, which allow us to sample neighbors,
(globally) sample vertices, query admissible pairs, and traverse admissible
neighbors, in both of the sublinear and streaming models.

We start from our MPC implementation which only has $O(\log n)$ rounds and in
each round, we may create multiple disjoint new clusters from multiple
selected “pivots”. There are two operations we need to change to make the
algorithm work in sublinear and streaming models:

  * •

When we estimate CostStays and CostMoves, we cannot enumerate all neighbors of
$v$. Instead, we need to sample a constant-size set of its neighbors, and use
one more Chernoff bound in Lemma 38;

  * •

For each cluster outputted by GenerateCluster, we need to estimate the
improvement, and then choose the most (estimated) improving one. We need a
concentration bound for the improvement of each round in Section 5.

##### Estimating CostStays and CostMoves.

Here we rewrite the subroutine that estimates CostStays. Let $N_{G}(v)=\\{u\in
V\mid(u,v)\in E^{+}\\}$ be the neighborhood of $v$ in the original graph $G$.

$\mathrm{EstCostStays}^{\prime}_{w}(S=\\{u_{1},\dots,u_{\eta_{0}}\\},s,v)$ •
Draw $\eta^{\prime}$ i.i.d uniformly random samples
$x_{1},\dots,x_{\eta^{\prime}}$ from $N_{G}(v)$. • return
$d_{w}(v)-\frac{|N_{G}(v)|}{\eta^{\prime}}\sum_{i=1}^{\eta^{\prime}}[x_{i}\in
C(v)]w(x_{i},v)-1+\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1)$

Recall the subroutine that estimates CostMoves.

$\mathrm{EstCostMoves}_{w}(S=\\{u_{1},\dots,u_{\eta_{0}}\\},s,v)$ • return
$d_{w}(v)+s-1-\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\}))$

In our algorithm, we only care about the difference between
$\mathrm{EstCostStays}$ and $\mathrm{EstCostMoves}$, so instead of computing
them individually, we can implement the following function that compute the
difference between the two, to avoid computing $d_{w}(v)$.

$\mathrm{EstCostDiff}^{\prime}_{w}(S=\\{u_{1},\dots,u_{\eta_{0}}\\},s,v)$ •
$\mathrm{CostStays}=s-1-\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\}))$
• Draw $\eta^{\prime}$ i.i.d uniformly random samples
$x_{1},\dots,x_{\eta^{\prime}}$ from $N_{G}(v)$. •
$\mathrm{CostMoves}=-\frac{|N_{G}(v)|}{\eta^{\prime}}\sum_{i=1}^{\eta^{\prime}}[x_{i}\in
C(v)]w(x_{i},v)-1+\frac{s}{\eta_{0}}\sum_{i=1}^{\eta_{0}}(d_{w}(v,\\{u_{i}\\})+d(v,\\{u_{i}\\})-1)$
• return $\mathrm{CostStays}-\mathrm{CostMoves}$

To compute $w(x_{i},v)$, we only need to check whether $x_{i}$ and $v$ are in
the same cluster in previous local search solution(s), which we can store in
$O(n)$ space. Note that since $x_{i}$ is sampled from $N_{G}(v)$, we don’t
need to query whether it is a neighbor of $v$. Thus we can use Lemma 9 to
sample $x_{i}$’s. In each round, since each vertex only samples a constant
number of times, we only need a constant number of realizations of Lemma 9.

It’s a litter more tricky to sample $u_{i}$’s. When computing
$d_{w}(v,\\{u_{i}\\})$, we need to query whether $v$ and $u_{i}$ are
neighbors. Hence we need to have access to the neighborhood of $u_{i}$. We do
the sampling as follows. We first use Lemma 10 to sample some vertices. Let’s
call them special vertices. For the pivot vertex $r$ where we want to sample
$u_{i}$’s from the admissible neighborhood $N(r)$, we know that with high
probability, $\Omega(\log n)$ vertices in $N(r)$ are special, since
$|N(r)|=\Omega(d(r))$ (when there exists the improving cluster) and vertices
in $N(r)$ are degree-similar to $r$. Notice that vertices in $N(r)$ are
sampled with similar but not exactly the same probabilities in Lemma 10, so we
need to further discard each vertex with some (constant) probability to get
independent samples. In the end, we sample $u_{i}$’s from these remaining
special vertices. By Lemma 10, we can entirely store the neighborhood of all
special vertices, so we can answer each neighbor query in $O(1)$ time. In each
round, since each pivot only samples a constant number of times and different
pivots sample from disjoint sets, we only need a constant number of
realizations of Lemma 10.

Note that we do not need to store the $\eta^{\prime}$ samples in the previous
algorithms, since we can work with them one by one. So we do not introduce
extra space cost here. The running time of this estimation is now
$O_{\epsilon}(1)$.

######  Lemma 54.

Consider the setting of lemma 38, let
$\eta^{\prime}>\frac{W^{2}\eta^{5}}{4\epsilon^{4}}$, with probability
$1-6\exp(-\frac{1}{2}\eta)$, the following two inequalities hold:

$\mathrm{EstCostStays}_{w}(S,s,v)\in\mathrm{ExpCostStays}_{w}(s,v)\pm\frac{1}{\eta^{2}}Ws$
(22)
$\mathrm{EstCostMoves}^{\prime}_{w}(S,s,v)\in\mathrm{ExpCostMoves}_{w}(s,v)\pm\left(\frac{1}{\eta^{2}}Ws+\frac{\epsilon^{2}}{\eta^{2}}d_{w}(v)\right)$
(23)

If the lemma holds, we can replace $\mathrm{EstCostMoves}$ by
$\mathrm{EstCostMoves}^{\prime}$ in GenerateCluster, since they introduce the
same asymptotic bound on the failure probability and error under the setting
of lemma 38, the same proof still holds.

###### Proof.

Let $Z_{i}=\frac{|N_{G}(v)|}{\eta^{\prime}}[u_{i}\in C(v)]w(u_{i},v)$. By
definition,

$\mathrm{EstCostMoves}^{\prime}_{w}(S,s,v)-\mathrm{EstCostMoves}_{w}(S,s,v)=\sum_{i=1}^{\eta^{\prime}}Z_{i}-\mathbf{E}[\sum_{i=1}^{\eta^{\prime}}Z_{i}]\leavevmode\nobreak\
.$

Since $Z_{i}\in[0,\frac{|N_{G}(v)|}{\eta^{\prime}}W]$, according to
Hoeffding’s inequality,

$\displaystyle\mathbf{Pr}\left[\left|\mathrm{EstCostMoves}^{\prime}_{w}(S,s,v)-\mathrm{EstCostMoves}_{w}(S,s,v)\right|\geq\frac{\epsilon^{2}}{\eta^{2}}d_{w}(v)\right]$
$\displaystyle\qquad\leq
2\exp\left(-\frac{2\left(\frac{\epsilon^{2}}{\eta^{2}}d_{w}(v)\right)^{2}}{\eta^{\prime}\left(\frac{|N_{G}(v)|}{\eta^{\prime}}W\right)^{2}}\right)$
$\displaystyle\qquad\leq
2\exp\left(-\frac{2\eta^{\prime}\epsilon^{4}d_{w}(v)^{2}}{\eta^{4}|N_{G}(v)|^{2}W^{2}}\right)$
$\displaystyle\qquad\leq
2\exp\left(-\frac{2\eta^{\prime}\epsilon^{4}}{\eta^{4}W^{2}}\right)$
$\displaystyle\qquad\leq 2\exp\left(-\frac{1}{2}\eta\right)$

The second last line holds from the fact that $d_{w}(v)\geq|N_{G}(v)|$, and
the last line holds from $\eta^{\prime}>\frac{W^{2}\eta^{5}}{4\epsilon^{4}}$.
By union bound, with probability $1-6\exp(-\frac{1}{2}\eta)$, the three
inequalities, (16), (17) and

$\left|\mathrm{EstCostMoves}^{\prime}_{w}(S,s,v)-\mathrm{EstCostMoves}_{w}(S,s,v)\right|\leq\frac{\epsilon^{2}}{\eta^{2}}d_{w}(v)$
(24)

holds. Combining (17) and (24), we get $\eqref{eq:costmove-concentration-
sampling}$. This finishes the proof of this lemma. ∎

##### Estimating the improvement.

Then we show how to estimate the improvement,
$\textsc{Cost}(\mathcal{C}+S^{\prime})-\textsc{Cost}(\mathcal{C})$, in
$O_{\epsilon}(d(r))$ time, where $r$ is the selected vertex and
$S^{\prime}\subseteq N(r)$.

$\mathrm{EstImprovement}_{w}(\mathcal{C},S^{\prime},r)$ • Let
$C(r)\in\mathcal{C}$ be the cluster containing $r$ • $I\leftarrow 0$ • For
$j=1,\dots,\eta^{\prime}$: – Uniformly randomly sample $u_{j}\in
S^{\prime}\Delta C(r)$ – $I\leftarrow
I+\mathrm{CostStays}_{w}(S^{\prime},u_{j})-\mathrm{CostMoves}_{w}(S^{\prime},u_{j})$
1.1cm $-\frac{1}{2}\sum_{v\in
S^{\prime}}\left(\textsc{Cost}_{w}(\mathcal{C},u_{j}v)-\textsc{Cost}_{w}(\mathcal{C}+S^{\prime},u_{j}v)\right)$
where $\textsc{Cost}_{w}(\mathcal{C},u_{j}v)$ is the cost paid by the
clustering scheme $\mathcal{C}$ for the edge or non-edge $u_{j}v$. • return
$I|S^{\prime}\Delta C(r)|/\eta^{\prime}$