# Simultaneously Approximating All $\ell_{p}$-norms
in Correlation Clustering

Sami Davies Department of EECS and the Simons Institute for the Theory of
Computing, UC Berkeley. Supported by an NSF Computing Innovation Fellowship
while at Northwestern University. Benjamin Moseley Carnegie Mellon University.
Benjamin Moseley and Heather Newman were supported in part by a Google
Research Award, an Inform Research Award, a Carnegie Bosch Junior Faculty
Chair, and NSF grants CCF-2121744 and CCF-1845146. Heather Newman†

###### Abstract

This paper considers correlation clustering on unweighted complete graphs. We
give a combinatorial algorithm that returns a _single_ clustering solution
that is _simultaneously_ $O(1)$-approximate for all $\ell_{p}$-norms of the
disagreement vector; in other words, a combinatorial $O(1)$-approximation of
the _all-norms_ objective for correlation clustering. This is the first proof
that minimal sacrifice is needed in order to optimize different norms of the
disagreement vector. In addition, our algorithm is the first combinatorial
approximation algorithm for the $\ell_{2}$-norm objective, and more generally
the first combinatorial algorithm for the $\ell_{p}$-norm objective when
$1<p<\infty$. It is also faster than all previous algorithms that minimize the
$\ell_{p}$-norm of the disagreement vector, with run-time $O(n^{\omega})$,
where $O(n^{\omega})$ is the time for matrix multiplication on $n\times n$
matrices. When the maximum positive degree in the graph is at most $\Delta$,
this can be improved to a run-time of $O(n\Delta^{2}\log n)$.

##  1 Introduction

Correlation clustering is one of the most prominent problems in clustering, as
it cleanly models community detection problems [37, 35] and provides a way to
decompose complex network structures [38, 31]. The input to the unweighted
correlation clustering problem is a complete graph $G=(V,E)$, where $|V|=n$
and each edge $e\in E$ is labeled positive $(+)$ or negative $(-)$. If the
edge $(u,v)$ is positive, this indicates that $u$ and $v$ are similar, and
analogously if the edge $(u,v)$ is negative, this indicates that $u$ and $v$
are dissimilar. The output of the problem is a partition of the vertex set
into parts $C_{1},C_{2},\ldots$, where each part represents a cluster.

The output should cluster similar vertices together and separate dissimilar
vertices. Specifically, for a fixed clustering (i.e., partition of the
vertices), a positive edge $(u,v)$ is a _disagreement_ with respect to the
clustering if $u$ and $v$ are in different clusters and an _agreement_ if $u$
and $v$ are in the same cluster. Similarly, a negative edge $(u,v)$ is a
disagreement with respect to the clustering if $u$ and $v$ are in the same
cluster and an agreement if $u$ and $v$ are in different clusters. The goal is
to find a clustering that minimizes some objective that is a function of the
disagreements.111Note that the sizes and number of clusters are unspecified.
For example, the most commonly studied objective minimizes the total number of
disagreements.

As an easy example to illustrate the problem, consider a social network. Every
pair of people has an edge between them, and the edge is positive if the two
people have ever met before, and negative otherwise. The goal of correlation
clustering translates to partitioning all the people into clusters so that
people are in the same cluster as their friends/acquaintances and in different
clusters than strangers. The difficulty in constructing a clustering is that
the labels may not be consistent, making disagreements unavoidable. Consider
in the social network what happens when there is one person with two friends
who have never met each other ($u,v,w$ with $(u,v)$ and $(u,w)$ positive but
$(v,w)$ negative). The choice of objective matters in determining the best
clustering.

For a given clustering $\mathcal{C}$, let $y_{\mathcal{C}}(u)$ denote the
number of edges incident to $u$ that are disagreements with respect to
$\mathcal{C}$ (we drop $\mathcal{C}$ and write $y$ when it is clear from
context). The most commonly considered objectives are ${\lVert
y_{\mathcal{C}}\rVert}_{p}=\sqrt[p]{\sum_{u\in V}y_{\mathcal{C}}(u)^{p}}$ for
$p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$, the $\ell_{p}$-norms of the
_disagreement vector_ $y$. Note that the optimal objective values may
drastically vary for different norms too. (For instance, in the example in
Appendix A of [33], $V=A\sqcup B$222$\sqcup$ denotes disjoint union., where
$|A|=|B|=n/2$, and all edges are positive except for a negative matching
between $A$ and $B$. The optimal $\ell_{\infty}$-norm objective value is 1
whereas the optimal for $\ell_{1}$ is $\Theta(n)$.) When $p=1$, this objective
minimizes the total number of disagreements. Setting $p=\infty$ minimizes the
maximum number of disagreements incident to any node, ensuring a type of
worst-case fairness.333In the social network example, minimizing the
$\ell_{1}$-norm corresponds to finding a clustering that minimizes the total
number of friends who are separated plus the total number of strangers who are
in the same cluster. The $\ell_{\infty}$-norm corresponds to finding a
clustering minimizing the number of friends any person is separated from plus
the number of strangers in that person’s same cluster. Balancing these two
extremes—average welfare on one hand and fairness on the other—is the
$\ell_{2}$-norm, which minimizes the variance of the disagreements at each
node.

Correlation clustering was proposed by Bansal, Blum, and Chawla BBC04 with the
objective of minimizing the $\ell_{1}$-norm of the disagreement vector. The
problem is NP-hard and several approximation algorithms have been proposed [7,
4, 16, 18]. Puleo and Milenkovic PM16 proposed studying $\ell_{p}$-norms of
the disagreement vector for $p>1$, and they give a $48$-approximation for any
fixed $p$. Charikar, Gupta, and Schwartz CGS17 introduced an improved
$7$-approximation, which Kalhan, Makarychev, and Zhou KMZ19 further improved
to a $5$-approximation. When $p>1$, up until recently, the only strategies
were LP or SDP rounding, and it has been of interest to develop fast
combinatorial algorithms [36]. Davies, Moseley, and Newman DMN23 introduced a
combinatorial $O(1)$-approximation algorithm for $p=\infty$ (see also [24] for
a different combinatorial algorithm), and leave open the question of
discovering a combinatorial $O(1)$-approximation algorithm for $1<p<\infty$.

In all prior work, solutions obtained for $\ell_{p}$-norms are tailored to
each norm (i.e., $p$ is part of the input to the algorithm), and it was not
well-understood what the trade-offs were between solutions that optimize
different norms. Solutions naively optimizing one norm can be arbitrarily bad
for other norms (see Figure 1). A natural question is whether this loss from
using a solution to one objective for another is avoidable. More specifically:

Figure 1: Two clusterings of the star graph, which has one node ($w$) with
positive edges to all nodes, and the rest of the edges negative. Left:
Clustering assigns all nodes to one (blue) cluster, and is (almost) optimal
for the $\ell_{\infty}$-norm with cost $\Theta(n)$. Right: Clustering assigns
all nodes to different clusters and is (almost) optimal for the
$\ell_{1}$-norm with cost $\Theta(n)$. The left solution is terrible for the
$\ell_{1}$-norm, as the negative clique has $\Theta(n^{2})$ edges that are
disagreements.

_For any graph input to unweighted, complete correlation clustering, does
there exist a partition (clustering) that is simultaneously $O(1)$-approximate
for all $\ell_{p}$-norm objectives?_

Phrased another way, does there exist a _universal algorithm_ for
$\ell_{p}$-norm correlation clustering—one which is guaranteed to produce a
solution that well-approximates many objectives at once? When the goal is to
simultaneously optimize every $\ell_{p}$-norm, this is known as the _all-
norms_ objective444In some of the literature, for instance that of Golovin et
al. [23], it is called the _all- $\ell_{p}$-norms_ objective.. Universal
algorithms and the all-norms objective are well-studied in combinatorial
optimization problems, such as load balancing and set cover (see Section 1.2
for more discussion). In the context of correlation clustering, such an
algorithm outputs a partition that has good global performance (i.e.
$\ell_{1}$-norm) and also has no individual node with too many adjacent
disagreements (i.e. $\ell_{\infty}$-norm). Universal algorithms exist for some
problems and are provably impossible for others. The question looms, what can
be said about universal algorithms for correlation clustering?

As far as we are aware, there are no known results for the all-norms objective
in other clustering problems. In fact, for the popular $k$-median and
$k$-center problems, it is actually impossible to $O(1)$-approximate (or even
$o(\sqrt{n})$-approximate) these two objectives simultaneously [5].

###  1.1 Results

This paper is focused on optimizing all $\ell_{p}$-norms ($p\geq 1$) for
correlation clustering at the same time. The main result of the paper answers
the previous question positively: perhaps surprisingly, there is a single
clustering that simultaneously $O(1)$-approximates the optimal for all
$\ell_{p}$-norms. Further, it can be found through an _efficient combinatorial
algorithm_. This is also the first known combinatorial approximation algorithm
for the $\ell_{2}$-norm objective and more generally $\ell_{p}$-norm objective
for fixed $2\leq p<\infty$.

In what follows, let $O(n^{\omega})$ denote the run-time of $n\times n$ matrix
multiplication.

######  Theorem 1.

Let $G=(V,E)$ be an instance of unweighted, complete correlation clustering on
$|V|=n$ nodes. There exists a combinatorial algorithm returning a single
clustering that is simultaneously an $O(1)$-approximation555Note this is
independent of $p$. for all $\ell_{p}$-norm objectives, for all
$p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$, and its run-time is
$O(n^{\omega})$.

The algorithm gives the _fastest run-time_ of any $O(1)$-approximation
algorithm for the $\ell_{p}$-norm objective when $p\in\mathbb{R}_{>1}$.
Further, the run-time can be improved when the positive degree of the graph is
bounded, as shown in the following corollary.

######  Corollary 1.

Let $\Delta$ denote the maximum positive degree in an instance $G=(V,E)$ of
unweighted, complete correlation clustering on $|V|=n$ nodes. Suppose $G$ is
given as an adjacency list representation of its positive edges. There exists
a combinatorial algorithm returning a single clustering that is simultaneously
an $O(1)$-approximation for all $\ell_{p}$-norm objectives, for all
$p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$, and its run-time is
$O(n\Delta^{2}\log n)$.

The run-time of the algorithm matches the fastest known algorithm for the
$\ell_{\infty}$-norm objective [19], in both the general case and when the
maximum positive degree is bounded. The best-known algorithm before our work
relied on solving a convex relaxation on $|V|^{2}$ variables and $|V|^{3}$
constraints. We improve the run-time by avoiding this bottleneck.

In the setting when the positive edges form a regular graph, the interested
reader may also find a rather beautiful proof (which is much simpler than that
of Theorem 1) in Section 3 showing there is a solution that is simultaneously
$O(1)$-approximate for the $\ell_{1}$-norm and $\ell_{\infty}$-norm
objectives.

###  1.2 Related work

Correlation clustering was introduced by Bansal, Blum, and Chawla BBC04. The
version they introduced also studies the problem on unweighted, complete
graphs, but is concerned with minimizing the $\ell_{1}$-norm of the
disagreement vector. For this problem, Ailon, Charikar, and Newman ACN-pivot
designed the Pivot algorithm, which is a randomized algorithm that in
expectation obtains a 3-approximation. While we know algorithms with better
approximations for $\ell_{1}$ correlation clustering than Pivot [16, 18], the
algorithm remains a baseline in correlation clustering due to its simplicity.
(However, Pivot can perform arbitrarily badly—i.e., give $\Omega(n)$
approximation ratios—for other $\ell_{p}$-norms; see again the example in
Appendix A of [33].) It is an active area of research to develop algorithms
for the $\ell_{1}$-norm that focus on practical scalability [11, 17, 32, 35,
14]. Correlation clustering has also been studied on non-complete, weighted
graphs [15, 28], with conditions on the cluster sizes [34], and with
asymmetric errors [26]. In fact, in recent work Veldt [36] highlighted the
need for deterministic techniques in correlation clustering that do not use
linear programming. Much interest in correlation clustering stems from its
connections to applications, including community detection, natural language
processing, location area planning, and gene expression [37, 35, 38, 31, 9,
20].

Puleo and Milenkovic PM16 introduced correlation clustering with the goal of
minimizing the $\ell_{p}$-norm of the disagreement vector. They show that even
for minimizing the $\ell_{\infty}$-norm on complete, unweighted graphs, the
problem is NP-hard (Appendix C in [33]). Several groups found
$O(1)$-approximation algorithms for minimizing the $\ell_{p}$-norm on
complete, unweighted graphs [33, 15, 28], the best of which is currently the
5-approximation of Kalhan, Makarychev, and Zhou KMZ19. Many other interesting
objectives for correlation clustering focus on finding solutions that are (in
some sense) fair or locally desirable [3, 8, 2, 21, 25, 1]. All of these
previous works that study general $\ell_{p}$-norms or other notions of
fairness or locality rely on solving a convex relaxation. This has two
downsides: (1) the run-time of the algorithms are bottle-necked by the time it
takes to solve the relaxation with at least $\Omega(n^{2})$ many variables and
$\Omega(n^{3})$ constraints; in fact, it is time-consuming to even enumerate
the $\Omega(n^{2})$ variables and $\Omega(n^{3})$ constraints; and (2) the
solution is only guaranteed to be good for one particular value of $p$.

Several problems have been studied with the goal of finding a solution that is
a good approximation for several objectives simultaneously. The all-norms
objective was introduced by Azar et al. [6], where the goal is to design a
$\rho$-approximation algorithm for all $\ell_{p}$-norm objectives of a
problem. They originally introduced the objective for the restricted
assignment load balancing problem and showed an all-norms 2-approximation.
Further follow-up on the all-norms objective has been done for load balancing
[29, 10, 30], and for set cover [23]. The term “universal” algorithm has also
been used for Steiner tree [12, 13], TSP [27], and clustering [22], though in
these settings the goal is different, namely, to find a solution that is good
for any potential input; e.g., in Universal Steiner Tree, the goal is to find
a spanning tree where for any set of terminals, the sub-tree connecting the
root to the terminals is a good approximation of the optimal.

##  2 Preliminaries

We will introduce notation, and then we will discuss two relevant works—the
papers by Kalhan, Makarychev, and Zhou KMZ19 and Davies, Moseley, and Newman
DMN23.

###  2.1 Notation

Recall our input to the correlation clustering problem is $G=(V,E)$, an
unweighted, complete graph on $n$ vertices, and every edge is assigned a label
of either positive $(+)$ or negative $(-)$. Let the set of positive edges be
denoted $E^{+}$ and the set of negative edges $E^{-}$. Then, we can define the
_positive neighborhood_ and _negative neighborhood_ of a vertex $u$ as
$N_{u}^{+}=\\{v\in V\mid(u,v)\in E^{+}\\}$ and $N_{u}^{-}=\\{v\in
V\mid(u,v)\in E^{-}\\}$, respectively. We further assume without loss of
generality that every vertex has a positive self-loop to itself.

A _clustering_ $\mathcal{C}$ is a partition of $V$ into _clusters_
$C_{1},\ldots,C_{k}$ (but recall that $k$ is not pre-specified). Let $C(u)$
denote the cluster that vertex $u$ is in, i.e., if $\mathcal{C}$ has $k$
clusters, there exists exactly one $i\in[k]$ such that $C(u)=C_{i}$. It is
also helpful to consider the vertices in a different cluster than $u$, and so
we let $\overline{C(u)}=V\setminus C(u)$ denote this. We say that a positive
edge $e=(u,v)\in E^{+}$ is a _disagreement_ with respect to $\mathcal{C}$ if
$v\in\overline{C(u)}$. On the other hand, we say that a negative edge
$e=(u,v)\in E^{-}$ is a disagreement with respect to $\mathcal{C}$ if $v\in
C(u)$. For a fixed clustering $\mathcal{C}$, we denote the _disagreement
vector_ of $\mathcal{C}$ as $y_{\mathcal{C}}\in\mathbb{Z}_{\geq 0}^{n}$, where
for $u\in V$, $y_{\mathcal{C}}(u)$ is the number of edges incident to $u$ that
are disagreements with respect to $\mathcal{C}$. We omit the subscript
throughout the proofs when a clustering is clear.

Throughout, we let OPT be the optimal objective value, and the $\ell_{p}$-norm
to which it corresponds will be clear from context. The next fact follows from
the definitions seen so far (recalling also the positive self-loops).

######  Fact 1.

For any $u,v\in V$, possibly with $u=v$, $n=|N_{u}^{+}\cap
N_{v}^{+}|+|N_{u}^{-}\cap N_{v}^{-}|+|N_{u}^{+}\cap N_{v}^{-}|+|N_{u}^{-}\cap
N_{v}^{+}|.$

###  2.2 Summary of work by Kalhan, Makarychev, and Zhou

The standard linear program relaxation for correlation clustering is stated in
LP 2.2.666Technically this is a convex program as the objective is convex. For
simplicity we will refer to it as an LP as the constraints are linear. In the
integer LP, the variable $x_{uv}$ indicates whether vertices $u$ and $v$ will
be in the same cluster (0 for yes, 1 for no), and the disagreement vector is
$y$; the optimal solution to the integer LP has value OPT, while the optimal
solution to the relaxation gives a lower bound on OPT. Note the triangle
inequality is enforced on all triples of vertices, inducing a semi-metric
space on $V$. Throughout this paper, as in [19], we refer to the algorithm by
Kalhan, Makarychev, and Zhou as the KMZ algorithm. The _KMZ algorithm_ has two
phases: it solves LP 2.2, and then uses the KMZ rounding algorithm (Algorithm
1) to obtain an integral assignment of vertices to clusters. See Appendix D
for its formal statement. At a high-level, the KMZ rounding algorithm is an
iterative, ball-growing algorithm that uses the semi-metric to guide its
choices on forming clusters. Their algorithm is a 5-approximation, and
produces different clusterings for different $p$, since the optimal solution
$x^{*}$ to LP 2.2 depends on $p$.

LP 2.2

$\displaystyle\min{\lVert y\rVert}_{p}$ $\displaystyle\textsf{s.t. }y_{u}$
$\displaystyle=\sum_{v\in N_{u}^{+}}x_{uv}+\sum_{v\in N_{u}^{-}}(1-x_{uv})$
$\displaystyle\forall u\in V$ $\displaystyle x_{uv}$ $\displaystyle\leq
x_{uw}+x_{vw}$ $\displaystyle\forall u,v,w\in V$ $\displaystyle 0$
$\displaystyle\leq x_{uv}\leq 1$ $\displaystyle\forall u,v\in V.$

######  Definition 1.

Let $f$ be a semi-metric on $V$, i.e., taking $x=f$ gives a feasible solution
to LP 2.2. The _fractional cost of $f$ in the $\ell_{p}$-norm objective_ is
the value of LP 2.2 that results from setting $x=f$. When $p$ is clear from
context, we will simply call this the fractional cost of $f$.

###  2.3 Summary of work by Davies, Moseley, and Newman

The main take-away from the work of Kalhan, Makarychev, and Zhou KMZ19 is that
one only requires a semi-metric on the set of vertices, whose cost is
comparable to the cost of an optimal solution, as input to the KMZ rounding
algorithm (Algorithm 1). Thus, the insight of Davies, Moseley, and Newman
DMN23 for the $\ell_{\infty}$-norm objective is that one can combinatorially
construct such a semi-metric without solving an LP, and at small loss in the
quality of the fractional solution. They do this by introducing the
_correlation metric_.

######  Definition 2 ([19]).

For all $u,v\in V$, the correlation metric defines the distance between $u$
and $v$ as

$\displaystyle d_{uv}$ $\displaystyle=1-\frac{|N_{u}^{+}\cap
N_{v}^{+}|}{|N_{u}^{+}\cup N_{v}^{+}|}$ $\displaystyle=\frac{|N_{u}^{+}\cap
N_{v}^{-}|+|N_{u}^{-}\cap N_{v}^{+}|}{|N_{u}^{+}\cap N_{v}^{+}|+|N_{u}^{+}\cap
N_{v}^{-}|+|N_{u}^{-}\cap N_{v}^{+}|}.$ (1)

Note that the rewrite in Line (2) is apparent from Fact 1.

The correlation metric captures useful information succinctly. Intuitively, if
$u$ and $v$ have relatively large positive intersection, i.e., $N_{u}^{+}\cap
N_{v}^{+}$ is large compared to their other relevant joint neighborhoods
$\left(N_{u}^{+}\cap N_{v}^{-}\right)\cup\left(N_{u}^{-}\cap
N_{v}^{+}\right)$, then from the perspective of $u$ and $v$, fewer
disagreements are incurred by putting $u$ and $v$ in the same cluster than by
putting them in different clusters. This is because if $u$ and $v$ are in the
same cluster, then they have disagreements on edges $(u,w)$ and $(v,w)$ for
$w\in\left(N_{u}^{+}\cap N_{v}^{-}\right)\cup\left(N_{u}^{-}\cap
N_{v}^{+}\right)$, but if they are in different clusters, then $u$ and $v$
have disagreements on edges $(u,w)$ and $(v,w)$ for $w\in N_{u}^{+}\cap
N_{v}^{+}$. Note that the metric is not normalized by $n$ (the size of the
joint neighborhood), but instead by $n-|N_{u}^{-}\cap
N_{v}^{-}|=|N_{u}^{+}\cap N_{v}^{+}|+|N_{u}^{+}\cap N_{v}^{-}|+|N_{u}^{-}\cap
N_{v}^{+}|$. In addition to the above intuition on the normalization factor,
we also observe that $w\in N_{u}^{-}\cap N_{v}^{-}$ do not necessarily force
disagreements on $(u,w)$ and $(v,w)$, since $w$ can go in a different cluster
than both $u$ and $v$ without penalty. For more on intuition behind the
correlation metric, see Section 2 in [19].

Davies, Moseley, and Newman DMN23 prove that the correlation metric $d$ can be
used as input to the KMZ rounding algorithm by showing that (1) $d$ satisfies
the triangle inequality and (2) the fractional cost of $d$ in the
$\ell_{\infty}$-norm (recall Definition 1) is no more than 8 times the value
of the optimal integral solution (OPT). Since the KMZ rounding algorithm
(Algorithm 1) loses a factor of at most 5, inputting $d$ to that algorithm
returns a 40-approximation algorithm. A benefit of the correlation metric is
that it can be computed in time $O(n^{\omega})$, and even faster when the
subgraph on positive edges is sparse.

###  2.4 Technical overview

It is not hard to see that the correlation metric cannot be used as input to
the KMZ algorithm for $\ell_{p}$-norms other than $p=\infty$, as one cannot
bound the fractional cost of the correlation metric against the optimal with
only an $O(1)$-factor loss. To see why, consider the star again, as in Figure
1. Here, for all $u,v\in\\{v_{1},\ldots,v_{n-1}\\}$,
$d_{uv}=1-1/(n-(n-3))=2/3$, but for the $\ell_{1}$-norm, we need the semi-
metric to have the value $1-d_{uv}$ be close to 0, i.e. $O(1/n)$, for such
$u,v$, in order for the fractional cost to be comparable to the value of OPT
for $p=1$.

There are several possible fixes one could try to make to the correlation
metric. One idea is that since one can interpret the correlation metric as a
coarse approximation of the probability the Pivot algorithm separates $u$ and
$v$777Pivot operates as follows: Choose a random unclustered $u\in V$. Take
$u$ and all its unclustered positive neighbors and let this be the newest
cluster. Continue until all vertices in $V$ are clustered., one could try to
adapt the correlation metric to more accurately approximate this
probability.888If in LP 2.2, $x_{uv}$ is set exactly to the probability that
$u$ and $v$ are separated by Pivot, then $x$ will be a feasible solution with
cost at most 3OPT. However, this probability seems difficult to express in
closed form, even approximately. Another idea, inspired by an observation
below, is that one could define a semi-metric for edges in $E^{+}$ and another
semi-metric for edges in $E^{-}$, but then there is the difficulty of showing
the triangle inequality holds when positive and negative edges are mixed
together. Both of these ideas were, for us, unsuccessful.

Instead, the following two observations of how the correlation metric works
with respect to the $\ell_{1}$-norm led us to an effective adaptation:

  1. 1.

One can bound the fractional cost, restricted to positive edges, of the
correlation metric in the $\ell_{1}$-norm by an $O(1)$-factor times the
optimal solution’s cost (see Claim 1 in Appendix C). Negative edges still pose
a challenge.

  2. 2.

If the subgraph of positive edges is regular, then we show one can bound the
fractional cost of the correlation metric in the $\ell_{1}$-norm on negative
edges as well as positive.999In contrast, one cannot bound the fractional cost
of the correlation metric on the (irregular) star (Figure 1). See Section 3.

These observations led us to ask whether some adjustments to the correlation
metric might yield a semi-metric with bounded fractional cost in the
$\ell_{1}$-norm or even the $\ell_{p}$-norm more generally (while still
remaining bounded in the $\ell_{\infty}$-norm). Moreover, since the KMZ
rounding algorithm does not depend on $p$ (whereas in the KMZ algorithm, the
solution to the LP does depend on $p$), inputting the same semi-metric to the
rounding algorithm produces the same clustering for all $\ell_{p}$-norms!

We are ready to define the _adjusted correlation metric_. Let $\Delta_{u}$
denote the positive degree of $u$ (the degree of $u$ in the subgraph of
positive edges).

######  Definition 3.

Define the _adjusted correlation metric_ $f:E\rightarrow[0,1]$ as follows:

  1. 1.

For $d$ the correlation metric, i.e., $d_{uv}=1-\frac{|N_{u}^{+}\cap
N_{v}^{+}|}{|N_{u}^{+}\cup N_{v}^{+}|}$, initially set $f=d$.

  2. 2.

If $e\in E^{-}$ and $d_{e}>0.7$, set $f_{e}=1$ (round up).

  3. 3.

For $u\in V$ such that $|N_{u}^{-}\cap\\{v:d_{uv}\leq
0.7\\}|\geq\frac{10}{3}\Delta_{u}$, set $f_{uv}=1$ for all $v\in
V\setminus\\{u\\}$.

The idea in Step 3 is that if the fractional cost of negative edges incident
to $u$ is sufficiently large, we instead trade this for the cost of positive
disagreements, as the rounding algorithm will now put $u$ in its own cluster.
For the $\ell_{\infty}$-norm, this trade-off is innocuous. For
$\ell_{p}$-norms in general, a refined charging argument is needed to show
that post-processing $d$ in this way sufficiently curbs the (too large)
fractional cost of $d$.

In Section 3, we start with a warm-up exercise and show that if the graph on
positive edges is regular, then the (original) correlation metric $d$ has
$O(1)$-approximate fractional cost. Note this section is not necessary to
understanding the rest of the paper, but we include it in the main body
because we find the proof here very clever! The main technical result of the
paper is Section 4, where we prove Theorem 1 by showing that the adjusted
correlation metric can be input to the KMZ rounding algorithm. Namely, we will
first show (quite easily) that the adjusted correlation metric satisfies an
approximate triangle inequality. Then, it remains to upper bound the
fractional cost of the adjusted correlation metric against OPT. We tackle this
with a combinatorial charging argument. This argument leverages a somewhat
different approach from that used in [19] and is simpler than their proof for
only the $\ell_{\infty}$-norm. The constant approximation factor obtained from
inputting the adjusted correlation metric to Algorithm 1 is bounded above (and
below) by universal constants for all $p$ (this is the worst case and one can
get better constants for each $p$). While we keep the argument for general
$\ell_{p}$-norms in the main body of the paper, the interested reader may find
a simplified proof for the $\ell_{1}$-norm objective in Appendix C.

##  3 A Special Case: Regular Graphs

In general, the original correlation metric $d$ (Definition 2) does not
necessarily have bounded fractional cost for the $\ell_{1}$-norm objective (or
more generally for $\ell_{p}$-norm objectives). So, we use the adjusted
correlation metric $f$ (Definition 3) as input to the KMZ rounding algorithm
(Appendix D). In this section, we show that if the subgraph of positive edges
is regular, then the correlation metric $d$ can be used as is (i.e., without
the adjustments in Steps 2 and 3 of Definition 3) to yield a clustering that
is constant approximate for the $\ell_{1}$-norm and $\ell_{\infty}$-norm
simultaneously:

######  Theorem 2.

Let $G=(V,E)$ be an instance of unweighted, complete correlation clustering,
and let $E^{+}$ denote the set of positive edges. Suppose that the subgraph
induced by $E^{+}$ is regular. Then the fractional cost of $d$ in the
$\ell_{1}$-norm objective is within a constant factor of OPT:

$\sum_{u\in V}\sum_{v\in N_{u}^{+}}d_{uv}+\sum_{u\in V}\sum_{v\in
N_{u}^{-}}(1-d_{uv})=O(\textsf{OPT}).$

Therefore, the clustering produced by inputting $d$ to the KMZ rounding
algorithm is a constant-factor approximation simultaneously for the
$\ell_{1}$-norm and $\ell_{\infty}$-norm objectives.

While this proof is quite different than the one for arbitrary-degree graphs,
we include it because we find it beautiful, and it gives useful intuition for
where the correlation metric breaks down for irregular graphs.

###### Proof.

Let $\Delta$ be the (common) degree of the positive subgraph. To show that the
fractional cost of $d$ in the $\ell_{1}$-norm objective is $O(\textsf{OPT})$
for regular graphs, we will use a dual fitting argument. The LP relaxation we
consider is from [4], which uses a dual fitting argument to show constant
approximation guarantees for Pivot (although the proof here does not otherwise
resemble the proof for Pivot). The primal is given by

$\min\Big{\\{}\sum_{e\in E}x_{e}\mid x_{ij}+x_{jk}+x_{ki}\geq 1,\forall
ijk\in\mathcal{T},x\geq 0\Big{\\}}$ ($P$)

where $\mathcal{T}$ is the set of bad triangles (i.e. triangles with exactly
two positive edges and one negative edge). For $x\in\\{0,1\\}^{|E|}$, $x$
corresponds to disagreements in a clustering: we set $x_{e}=1$ if $e$ is a
disagreement and $x_{e}=0$ otherwise. The constraints state that every
clustering must make a disagreement on every bad triangle. Thus, ($P$) is a
relaxation for the $\ell_{1}$-norm objective. In fact, we will prove the
stronger statement that the fractional cost is $O(\textsf{OPT}_{P})$, where
$\textsf{OPT}_{P}$ is the optimal objective value of ($P$).

The dual is given by

$\max\Big{\\{}\sum_{T\in\mathcal{T}}y_{T}\mid\sum_{T\in\mathcal{T}:T\ni
e}y_{T}\leq 1,\forall e\in E,y\geq 0\Big{\\}}.$ ($D$)

We show that by setting $y_{T}=\frac{1}{2\Delta}$ for all $T\in\mathcal{T}$,
$y$ satisfies the following properties:

  1. 1.

$y$ is feasible in ($D$).

  2. 2.

The fractional cost of $d$ is at most $6\cdot\sum_{T\in\mathcal{T}}y_{T}$.

Letting $\textsf{OPT}_{D}$ be the optimal objective value of ($D$), we have
$6\cdot\sum_{T\in\mathcal{T}}y_{T}\leq
6\cdot\textsf{OPT}_{D}=6\cdot\textsf{OPT}_{P}\leq 6\cdot\textsf{OPT}$, which
will conclude the proof.

To prove feasibility, we case on whether $e$ is positive or negative.

If $e\in E^{-}$, then $|\\{T\in\mathcal{T}:T\ni e\\}|=|N_{u}^{+}\cap
N_{v}^{+}|\leq\Delta$, where equality is by the definition of a bad triangle.
So

$\sum_{T\in\mathcal{T}:T\ni e}y_{T}\leq\frac{\Delta}{2\Delta}\leq 1.$

If $e\in E^{+}$, then $|\\{T:T\ni e\\}|=|(N_{u}^{+}\cap
N_{v}^{-})\cup(N_{u}^{-}\cap N_{v}^{+})|\leq 2\Delta$. We conclude $y$ is
feasible, since

$\sum_{T\in\mathcal{T}:T\ni e}y_{T}\leq\frac{2\Delta}{2\Delta}=1.$

Now we need to show that the fractional cost of $d$ is bounded in terms of the
objective value of $(D)$. First we bound the fractional cost of the negative
edges:

$\sum_{(u,v)\in E^{-}}(1-d_{uv})\leq\sum_{(u,v)\in E^{-}}|N_{u}^{+}\cap
N_{v}^{+}|/\Delta=\sum_{e\in E^{-}}\sum_{T\in\mathcal{T}:T\ni
e}1/\Delta=\sum_{e\in E^{-}}\sum_{T\in\mathcal{T}:T\ni e}2y_{T},$

where in the first inequality we have used that $|N_{u}^{+}\cup
N_{v}^{+}|\geq\Delta$. Next we bound the fractional cost of the positive
edges:

$\sum_{(u,v)\in E^{+}}d_{uv}\leq\sum_{(u,v)\in E^{+}}(|N_{u}^{+}\cap
N_{v}^{-}|+|N_{u}^{-}\cap N_{v}^{+}|)/\Delta=\sum_{e\in
E^{+}}\sum_{T\in\mathcal{T}:T\ni e}1/\Delta=\sum_{e\in
E^{+}}\sum_{T\in\mathcal{T}:T\ni e}2y_{T}.$

So the total fractional cost is bounded by $\sum_{e\in
E}\sum_{T\in\mathcal{T}:T\ni e}2y_{T}=6\cdot\sum_{T\in\mathcal{T}}y_{T},$
since each triangle contains three edges. This is what we sought to show.
Since the fractional cost of $d$ is bounded for the $\ell_{1}$-norm objective
(and the $\ell_{\infty}$-norm objective by [19]), using $d$ as input to KMZ
rounding algorithm produces a clustering that is simultaneously
$O(1)$-approximate for the $\ell_{1}$\- and $\ell_{\infty}$-norm objectives. ∎

##  4 Proof of Theorem 1

The goal of this section is to prove Theorem 1 and the subsequent Corollary 1.
We begin by outlining that the adjusted correlation metric satisfies an
approximate triangle inequality in Subsection 4.1. Then in Subsection 4.2, we
prove the fractional cost of the adjusted correlation metric in any
$\ell_{p}$-norm objective is an $O(1)$ factor away from the optimal solution’s
value. We tie it all together to prove Theorem 1 and Corollary 1 in Subsection
4.3.

Before all that, we prove a proposition that will be key in several settings.
Loosely, it states that if two vertices are close to each other according to
$d$, then they have a large shared positive neighborhood.

######  Proposition 1.

Fix vertices $u,v\in V$ and a clustering $\mathcal{C}$ on $V$ such that
$d_{uv}\leq 0.7$ and $|N_{u}^{+}\cap C(u)|\hskip 2.84526pt/\hskip
2.84526pt|N_{u}^{+}|\geq 0.85$. Then $|N_{u}^{+}\cap N_{v}^{+}\cap C(u)|\geq
0.15\cdot|N_{u}^{+}|$.

###### Proof.

Since $d_{uv}\leq 0.7$, $\frac{|N_{u}^{+}\cap
N_{v}^{+}|}{|N_{u}^{+}|}\geq\frac{|N_{u}^{+}\cap N_{v}^{+}|}{|N_{u}^{+}\cup
N_{v}^{+}|}\geq 0.3.$ Using the assumption on $u$ together with the above
inequality implies that $|N_{v}^{+}\cap N_{u}^{+}\cap C(u)|\hskip
2.84526pt/\hskip 2.84526pt|N_{u}^{+}|\geq 0.85+0.3-1=0.15.$ ∎

###  4.1 Triangle inequality

Recall that the correlation metric $d$ satisfies the triangle inequality (see
Section 4.2 in [19]). We will show that the adjusted correlation metric $f$
satisfies an approximate triangle inequality, which is sufficient for the KMZ
rounding algorithm. Formally, we say that a function $g$ is a _$\delta$ -semi-
metric_ on some set $S$ if it is a semi-metric on $S$, except instead of
satisfying the triangle inequality, $g$ satisfies
$g(u,v)\leq\delta\cdot(g(u,w)+g(v,w))$ for all $u,v,w\in S$.

######  Lemma 1 (Triangle Inequality).

The adjusted correlation metric $f$ is a $\frac{10}{7}$-semi-metric.

The proof of Lemma 1 is straightforward given that $d$ satisfies the triangle
inequality; see Appendix A.

Lemma 3 in [19] proves that one can input a semi-metric that satisfies an
approximate triangle inequality (instead of the exact triangle inequality) to
the KMZ rounding algorithm (with some loss in the approximation factor). We
summarize the main take-away below.

######  Lemma 2 ([19]).

If $g$ is a $\delta$-semi-metric on the set $V$, instead of a true semi-metric
(i.e., $1$-semi-metric), then the KMZ algorithm loses a factor of
$1+\delta+\delta^{2}+\delta^{3}+\delta^{4}$.101010When $\delta=1$, this factor
equals 5, which is the loss in the KMZ algorithm.

Since we show in Lemma 1 that $f$ is a $\frac{10}{7}$-semi-metric, we lose a
factor of 12 in inputting $f$ to the KMZ algorithm (along with the factor loss
from the fractional cost).

###  4.2 Bounding the fractional cost of $\ell_{p}$-norms

This section bounds the fractional cost of the adjusted correlation metric for
the $\ell_{p}$-norms. The following lemma considers the case where $p=\infty$.
The general case is handled in the subsequent lemma.

######  Lemma 3.

The fractional cost of the adjusted correlation metric $f$ in the
$\ell_{\infty}$-norm objective is at most $56\cdot\textsf{OPT}$, where OPT is
the cost of the optimal integral solution in the $\ell_{\infty}$-norm.

The lemma follows from the fact that the fractional cost of the correlation
metric $d$ in the $\ell_{\infty}$-norm is known to be bounded by [19], and
that it only decreases when $d$ is replaced by $f$ due to Definition 3. For
completeness, we include a proof in Appendix B.

For finite $p\in\mathbb{R}_{\geq 1}$, our techniques hold for any
$\ell_{p}$-norm, as we only require the convexity of $x^{p}$. As far as we
know, there has been no study initiated on the problem for $0\leq p<1$. We use
two primary lemmas—one for the positive edge fractional cost and one for the
negative edge fractional cost—to show that the adjusted correlation metric
well approximates the optimal for general $\ell_{p}$-norms.

######  Lemma 4.

The fractional cost of the adjusted correlation metric $f$ in the
$\ell_{p}$-norm objective is a constant factor (independent of $p$) away from
the cost of the optimal integral solution in the $\ell_{p}$-norm.

###### Proof.

Let $y$ be the disagreement vector for an optimal clustering $\mathcal{C}$ in
the $\ell_{p}$-norm, for any $p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$. When
$p=\infty$, see Lemma 3. For $p\in\mathbb{R}_{\geq 1}$, by definition
$\textsf{OPT}^{p}=\sum_{w\in V}(y(w))^{p},$ and the $p$th power of the
fractional cost of $f$ is given by

$cost(f)^{p}=\sum_{u\in V}\Big{[}\sum_{v\in N_{u}^{+}}f_{uv}+\sum_{v\in
N_{u}^{-}}(1-f_{uv})\Big{]}^{p}.$ $\text{Observe that }\quad cost(f)^{p}\leq
2^{p}\underbrace{\sum_{u\in V}\Big{(}\sum_{v\in
N_{u}^{+}}f_{uv}\Big{)}^{p}}_{(S^{+})^{p}}+2^{p}\underbrace{\sum_{u\in
V}\Big{(}\sum_{v\in N_{u}^{-}}(1-f_{uv})\Big{)}^{p}}_{(S^{-})^{p}}.$

We refer to bounding $(S^{+})^{p}$ as bounding the fractional cost of the
positive edges, and likewise $(S^{-})^{p}$ for the negative edges. The first
sum, $(S^{+})^{p}$, is bounded in Lemma 5 and the second sum, $(S^{-})^{p}$,
is bounded in Lemma 6. Using those two bounds, together we have
$cost(f)\leq[2^{p}((S^{+})^{p}+(S^{-})^{p})]^{1/p}\leq 529,$ for
$p\in[1,\infty)$. Specifically, the middle term is maximized at $p=1$, giving
the bound of 529, and tends to below 214 as $p\rightarrow\infty$. (A more
tailored analysis in Appendix C gives a constant of 74 for $p=1$.) ∎

We note that, as our main interest is determining whether a simultaneous
constant approximation is even possible (and a combinatorial one, at that), we
did not pay particular attention to optimizing constants, but suspect these
could be greatly reduced.

####  4.2.1 Fractional cost of positive edges in $\ell_{p}$-norms

Bounding the fractional cost of the positive edges in the $\ell_{p}$-norm will
be similar to in the simpler $\ell_{1}$-norm (see Appendix C), only there will
be an extra step in which we apply Jensen’s inequality.

######  Lemma 5.

For $p\in\mathbb{R}_{\geq 1}$, the fractional cost of the adjusted correlation
metric $f$ in the $\ell_{p}$-norm objective for the set of positive edges is a
constant factor approximation to the optimal, i.e.,

$(S^{+})^{p}=\sum_{u\in V}\Big{(}\sum_{v\in N_{u}^{+}}f_{uv}\Big{)}^{p}\leq
2^{p}\cdot[(8^{p}/2+1)((20/3)^{p}+2+2\cdot
4^{p})+8^{p}+1]\cdot\textsf{OPT}^{p}.$

One of the challenges in bounding the cost of $f$ is that disagreements in the
$\ell_{p}$-norm objective for $p\neq 1$ are asymmetric, in that a disagreeing
edge charges $y(u)$ and $y(v)$ (whereas for $p=1$ we can just sum the number
of disagreeing edges). Step 3 rounds up the edges incident to $u$ when the
tradeoff is good from $u$’s perspective. However, an edge $(u,v)$ may be
rounded up to 1 when this tradeoff is good from $v$’s perspective, but not
from $u$’s perspective. The high-level idea for why this is fine is that if
$u$ and $v$ are close under $d$, their positive neighborhoods overlap
significantly and, in some average sense, $u$ can charge to $v$. Proving this
requires a double counting argument using a bipartite auxiliary graph. If $u$
and $v$ are far under $d$, on the other hand, we can charge to the cost of the
correlation metric, which will be bounded on an appropriate subgraph.

The second challenge is showing that the $\ell_{p}$-norm of the disagreement
vector, restricted to vertices $u$ that are made singletons in Step 3, is
bounded. This again requires a double counting argument.

###### Proof.

Fix an optimal clustering $\mathcal{C}$. We partition vertices based on
membership in $C(u)$ or $\overline{C(u)}$ (as defined in Subsection 2.1). Let
$y$ denote the disagreement vector of $\mathcal{C}$. We have

$\displaystyle(S^{+})^{p}$ $\displaystyle=\sum_{u\in V}\Big{(}\sum_{v\in
N_{u}^{+}}f_{uv}\Big{)}^{p}\leq 2^{p}\underbrace{\sum_{u\in
V}\Big{(}\sum_{v\in N_{u}^{+}\cap
C(u)}f_{uv}\Big{)}^{p}}_{S_{1}^{+}}+2^{p}\underbrace{\sum_{u\in
V}\Big{(}\sum_{v\in
N_{u}^{+}\cap\overline{C(u)}}f_{uv}\Big{)}^{p}}_{S_{2}^{+}}.$

It is easy to bound $S_{2}^{+}$ by using the trivial upper bound $f_{uv}\leq
1$:

$\boxed{S_{2}^{+}=\sum_{u\in V}\Big{(}\sum_{v\in
N_{u}^{+}\cap\overline{C(u)}}f_{uv}\Big{)}^{p}\leq\sum_{u\in
V}\Big{(}\sum_{v\in N_{u}^{+}\cap\overline{C(u)}}1\Big{)}^{p}\leq\sum_{u\in
V}(y(u))^{p}=\textsf{OPT}^{p},}$

where we have used that every edge $(u,v)\in E^{+}$ with $v\not\in C(u)$ is a
disagreement incident to $u$.

Next, we bound $S_{1}^{+}$. Let $R_{1}$ be the set of $u$ for which Step 3 of
Definition 3 applies. For these $u$, we have $f_{uv}=1$ for all $v\in
V\setminus\\{u\\}$. Let $R_{2}=V\setminus R_{1}$. For $u\in R_{2}$ and $v\in
N_{u}^{+}$, we have that either $v\in R_{2}$, in which case $f_{uv}=d_{uv}$;
or $v\in R_{1}$, in which case $f_{uv}=1$. (Note that $V$ is the disjoint
union of $R_{1}$ and $R_{2}$.) So

$\displaystyle S_{1}^{+}=\underbrace{\sum_{u\in R_{1}}\Big{(}\sum_{v\in
N_{u}^{+}\cap C(u),v\neq u}1\Big{)}^{p}}_{S_{11}^{+}}+\underbrace{\sum_{u\in
R_{2}}\Big{(}\sum_{v\in N_{u}^{+}\cap C(u)}f_{uv}\Big{)}^{p}}_{S_{12}^{+}},$

and in particular

$\displaystyle S_{12}^{+}$ $\displaystyle=\sum_{u\in R_{2}}\Big{(}\sum_{v\in
N_{u}^{+}\cap C(u)\cap R_{1}}1+\sum_{v\in N_{u}^{+}\cap C(u)\cap
R_{2}}d_{uv}\Big{)}^{p}$ $\displaystyle=\sum_{u\in
R_{2}}\Big{(}\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap C(u)\cap R_{1}\\\
d_{uv}\leq 1/4\end{subarray}}1+\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap
C(u)\cap R_{1}\\\ d_{uv}\geq 1/4\end{subarray}}1+\sum_{v\in N_{u}^{+}\cap
C(u)\cap R_{2}}d_{uv}\Big{)}^{p}$ $\displaystyle\leq\sum_{u\in
R_{2}}\Big{(}\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap C(u)\cap R_{1}\\\
d_{uv}\leq 1/4\end{subarray}}1+\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap
C(u)\cap R_{1}\\\ d_{uv}\geq 1/4\end{subarray}}4\cdot d_{uv}+\sum_{v\in
N_{u}^{+}\cap C(u)\cap R_{2}}d_{uv}\Big{)}^{p}$ $\displaystyle\leq\sum_{u\in
R_{2}}\Big{(}\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap C(u)\cap R_{1}\\\
d_{uv}\leq 1/4\end{subarray}}1+\sum_{v\in N_{u}^{+}\cap C(u)}4\cdot
d_{uv}\Big{)}^{p}\leq 2^{p}\underbrace{\sum_{u\in
R_{2}}\Big{(}\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap R_{1}\\\ d_{uv}\leq
1/4\end{subarray}}1\Big{)}^{p}}_{S_{13}^{+}}+8^{p}\cdot\underbrace{\sum_{u\in
R_{2}}\Big{(}\sum_{v\in N_{u}^{+}\cap C(u)}d_{uv}\Big{)}^{p}}_{S_{14}^{+}}.$

First we will bound $S_{13}^{+}$. To do so, we will strongly use that
$d_{uv}\leq 1/4$ in the inner sum. In particular, we will make use of the
following easy proposition.

######  Proposition 2.

Let $d$ be the correlation metric, and suppose $d_{uv}\leq 1/4$. Then
$|N_{u}^{+}|\leq\frac{7}{3}\cdot|N_{v}^{+}|$.

###### Proof of Proposition 2.

Since $d_{uv}\leq 1/4$ implies $1-d_{uv}\geq 3/4$, we see that

$\frac{|N_{u}^{+}\cap N_{v}^{+}|}{|N_{u}^{+}|+|N_{v}^{+}|-|N_{u}^{+}\cap
N_{v}^{+}|}\geq 3/4,$

and we complete the proof since $7\cdot|N_{v}^{+}|\geq 7\cdot|N_{u}^{+}\cap
N_{v}^{+}|\geq 3\cdot|N_{u}^{+}|+3\cdot|N_{v}^{+}|\geq 3\cdot|N_{u}^{+}|.$ ∎

Next, we will need to create a bipartite auxiliary graph $H=(R_{2},R_{1},F)$
with $R_{2}$ and $R_{1}$ being the sides of the partition, and $F$ being the
edge set. We will then use a double counting argument. Place an edge between
$u\in R_{2}$ and $v\in R_{1}$ if $uv\in E^{+}$ and $d_{uv}\leq 1/4$. Then we
have precisely that

$S_{13}^{+}=\sum_{u\in R_{2}}\text{deg}_{H}(u)^{p}.$

We will show that

$\boxed{S_{13}^{+}=\sum_{u\in R_{2}}\text{deg}_{H}(u)^{p}\leq
4^{p-1}\cdot\sum_{v\in R_{1}}|N_{v}^{+}|^{p}\leq
4^{p-1}\cdot\left((20/3)^{p}+2+2\cdot 4^{p}\right)\cdot\textsf{OPT}^{p}}$ (2)

where the last bound follows from Proposition 3, which we establish separately
below. We will bound via double counting the quantity $L$, defined below. Let
$N_{H}(\cdot)$ denote the neighborhoods in $H$ of the vertices.

$\displaystyle L$ $\displaystyle:=\sum_{f=uv\in
F}\left(\text{deg}_{H}(u)+\text{deg}_{H}(v)\right)^{p-1}\leq\sum_{v\in
R_{1}}\sum_{u\in
N_{H}(v)}\left(\text{deg}_{H}(v)+\text{deg}_{H}(u)\right)^{p-1}$
$\displaystyle\leq\sum_{v\in R_{1}}\sum_{u\in
N_{H}(v)}\left(|N_{v}^{+}|+|N_{u}^{+}|\right)^{p-1}\leq\sum_{v\in
R_{1}}\sum_{u\in N_{H}(v)}4^{p-1}\cdot|N_{v}^{+}|^{p-1}$ (3)
$\displaystyle\leq 4^{p-1}\cdot\sum_{v\in
R_{1}}|N_{v}^{+}|\cdot|N_{v}^{+}|^{p-1}=4^{p-1}\cdot\sum_{v\in
R_{1}}|N_{v}^{+}|^{p}$

where in (3) we’ve used Proposition 2. Note that $L$ is upper bounded by the
right-hand side in (2). Now it just remains to show that $L$ is lower bounded
by the left-hand side in (2).

$\displaystyle L$ $\displaystyle=\sum_{f=uv\in
F}\left(\text{deg}_{H}(u)+\text{deg}_{H}(v)\right)^{p-1}=\sum_{u\in
R_{2}}\sum_{v\in
N_{H}(u)}\left(\text{deg}_{H}(u)+\text{deg}_{H}(v)\right)^{p-1}$
$\displaystyle\geq\sum_{u\in R_{2}}\sum_{v\in
N_{H}(u)}\text{deg}_{H}(u)^{p-1}=\sum_{u\in
R_{2}}\text{deg}_{H}(u)\cdot\text{deg}_{H}(u)^{p-1}=\sum_{u\in
R_{2}}\text{deg}_{H}(u)^{p},$

which is what we sought to show. Now we bound $S_{14}^{+}$.

$\displaystyle S_{14}^{+}$ $\displaystyle\leq\sum_{u\in V}\Bigg{(}\sum_{v\in
N_{u}^{+}\cap C(u)}\frac{|N_{u}^{+}\cap N_{v}^{-}|+|N_{u}^{-}\cap
N_{v}^{+}|}{|N_{u}^{+}\cup N_{v}^{+}|}\Bigg{)}^{p}$
$\displaystyle\leq\sum_{u\in V}\Bigg{(}\sum_{v\in
N_{u}^{+}}\frac{y(u)+y(v)}{|N_{u}^{+}\cup
N_{v}^{+}|}\Bigg{)}^{p}\leq\sum_{u\in V}|N_{u}^{+}|^{p-1}\sum_{v\in
N_{u}^{+}}\frac{(y(u)+y(v))^{p}}{|N_{u}^{+}\cup N_{v}^{+}|^{p}}$
$\displaystyle\leq 2^{p}\sum_{u\in V}\sum_{v\in
N_{u}^{+}}|N_{u}^{+}|^{p-1}\cdot\frac{y(u)^{p}}{|N_{u}^{+}\cup
N_{v}^{+}|^{p}}+2^{p}\sum_{u\in V}\sum_{v\in
N_{u}^{+}}|N_{u}^{+}|^{p-1}\cdot\frac{y(v)^{p}}{|N_{u}^{+}\cup
N_{v}^{+}|^{p}}.$

In the second line, the first inequality uses the fact that for
$w\in(N_{u}^{+}\cap N_{v}^{-})\cup(N_{u}^{-}\cap N_{v}^{+})$, then at least
one of $(u,w),(v,w)$ is a disagreement, since $v\in C(u)$ in the inner
summation of the first line. The second inequality in the second line uses
Jensen’s inequality.

To bound the first double sum above, we use an averaging argument:

$\sum_{u\in V}\sum_{v\in
N_{u}^{+}}|N_{u}^{+}|^{p-1}\cdot\frac{y(u)^{p}}{|N_{u}^{+}\cup
N_{v}^{+}|^{p}}\leq\sum_{u\in V}\sum_{v\in
N_{u}^{+}}\frac{y(u)^{p}}{|N_{u}^{+}|}=\sum_{u\in
V}y(u)^{p}=\textsf{OPT}^{p}.$

To bound the second double sum, we first have to flip it:

$\displaystyle\sum_{u\in V}\sum_{v\in
N_{u}^{+}}|N_{u}^{+}|^{p-1}\cdot\frac{y(v)^{p}}{|N_{u}^{+}\cup
N_{v}^{+}|^{p}}$ $\displaystyle=\sum_{v\in V}\sum_{u\in
N_{v}^{+}}|N_{u}^{+}|^{p-1}\cdot\frac{y(v)^{p}}{|N_{u}^{+}\cup
N_{v}^{+}|^{p}}$ $\displaystyle\leq\sum_{v\in V}\sum_{u\in
N_{v}^{+}}|N_{u}^{+}|^{p-1}\frac{y(v)^{p}}{|N_{u}^{+}|^{p-1}\cdot|N_{v}^{+}|}=\sum_{v\in
V}y(v)^{p}=\textsf{OPT}^{p}.$

In total, we have

$\boxed{S_{14}^{+}\leq 2\cdot
2^{p}\cdot\textsf{OPT}^{p}=2^{p+1}\cdot\textsf{OPT}^{p}}$

$\text{and }\quad\boxed{S_{12}^{+}\leq 2^{p}\cdot S_{13}^{+}+8^{p}\cdot
S_{14}^{+}\leq 2^{p}\cdot 4^{p-1}\cdot\left((20/3)^{p}+2+2\cdot
4^{p}\right)\cdot\textsf{OPT}^{p}+8^{p}\cdot\textsf{OPT}^{p}.}$

Next we turn to bounding $S_{11}^{+}$. Recall that
$R_{1}=\\{u:|N_{u}^{-}\cap\\{v:d_{uv}\leq
0.7\\}|\geq\frac{10}{3}\cdot\Delta_{u}\\}$ and

$S_{11}^{+}\leq\sum_{u\in R_{1}}|N_{u}^{+}\cap C(u)|^{p}\leq\sum_{u\in
R_{1}}|N_{u}^{+}|^{p}.$

So it suffices to bound the right-hand side, which we do in the following
proposition.

######  Proposition 3.

Let $R_{1}$ be the set of $u$ for which Step 3 of Definition 3 applies. Then

$\sum_{u\in R_{1}}|N_{u}^{+}|^{p}\leq\left((20/3)^{p}+2+2\cdot
4^{p}\right)\cdot\textsf{OPT}^{p}.$

###### Proof of Proposition 3.

For $u\in R_{1}$, define $R_{1}(u)=N_{u}^{-}\cap\\{v:d_{uv}\leq 0.7\\},$ so in
particular $|R_{1}(u)|\geq\frac{10}{3}\cdot\Delta_{u}$. Fix a vertex $u\in
R_{1}$. We consider a few cases. The crux of the argument is Case 2a(ii).

##### Case 1:

_At least a 0.15 fraction of $N_{u}^{+}$ is in clusters other than $C(u)$._
Let $u\in V^{1}$ be the vertices in this case. This means that
$0.15\cdot|N_{u}^{+}|\leq y(u)$, so

$\boxed{\sum_{u\in V^{1}}|N_{u}^{+}|^{p}\leq\sum_{u\in
V^{1}}\frac{1}{0.15^{p}}y(u)^{p}\leq(20/3)^{p}\cdot\textsf{OPT}^{p}.}$

##### Case 2:

_At least a 0.85 fraction of $N_{u}^{+}$ is in $C(u)$. _
We further partition the cases based on how much $R_{1}(u)$ intersects $C(u)$.

Figure 2: Left: Case 2a(i). For $v\in|N_{u}^{-}\cap C(u)|$, $(u,v)$ is a
disagreement. Right: Case 2a(ii). For $w\in|N_{u}^{+}\cap C(u)|$ and $v\in
N_{w}^{+}\cap R_{1}^{\prime}(u)$, $(w,v)$ is a disagreement.

Case 2a: _At least half of $R_{1}(u)$ is in clusters other than $C(u)$._
We partition into cases (just one more time!) based on the size of
$N_{u}^{-}\cap C(u)$. See Figure 2.

  * •

Case 2a(i): _At least half of $R_{1}(u)$ is in clusters other than $C(u)$ and
$|N_{u}^{-}\cap C(u)|\geq\Delta_{u}$. _
Let $u\in V^{2a(i)}$ be the vertices in this case. Note that
$y(u)\geq|N_{u}^{-}\cap C(u)|$. Then

$\displaystyle\boxed{\sum_{u\in V^{2ai}}|N_{u}^{+}|^{p}=\sum_{u\in
V^{2ai}}\Delta_{u}^{p}\leq\sum_{u\in V^{2ai}}|N_{u}^{-}\cap
C(u)|^{p}\leq\sum_{u\in V^{2ai}}y(u)^{p}\leq\textsf{OPT}^{p}.}$

  * •

Case 2a(ii):_At least half of $R_{1}(u)$ is in clusters other than $C(u)$ and
$|N_{u}^{-}\cap C(u)|\leq\Delta_{u}$._

Let $u\in V^{2a(ii)}$ be the vertices in this case. Denote the vertices in
$R_{1}(u)$ that are in clusters other than $C(u)$ by $R_{1}^{\prime}(u)$. By
definition of Case 2a(ii),
$|R_{1}^{\prime}(u)|\geq\frac{5}{3}\cdot\Delta_{u}$. A key fact we will use is
that $|C(u)|\leq 2\cdot\Delta_{u}$:

$|C(u)|=|N_{u}^{-}\cap C(u)|+|N_{u}^{+}\cap
C(u)|\leq\Delta_{u}+\Delta_{u}=2\cdot\Delta_{u}.$

For $u\in V^{2a(ii)}$ and $w\in N_{u}^{+}\cap C(u)$, define
$\varphi(u,w)=|R_{1}^{\prime}(u)\cap N_{w}^{+}|.$

Each $w\in N_{u}^{+}\cap C(u)$ dispenses $\varphi(u,w)^{p}/|C(u)|$ charge to
$u$. Also, observe that for $v\in R_{1}^{\prime}(u)$, we have that $d_{uv}\leq
0.7$, so we know by Proposition 1 that $|N_{u}^{+}\cap N_{v}^{+}\cap C(u)|\geq
0.15\cdot|N_{u}^{+}|$. This implies that

$\displaystyle\sum_{w\in N_{u}^{+}\cap C(u)}|R_{1}^{\prime}(u)\cap N_{w}^{+}|$
$\displaystyle=\sum_{w\in N_{u}^{+}\cap C(u)}\sum_{v\in R_{1}^{\prime}(u)\cap
N_{w}^{+}}1=\sum_{v\in R_{1}^{\prime}(u)}\sum_{\underset{\cap C(u)\cap
N_{u}^{+}}{w\in\cap N_{v}^{+}}}1$ $\displaystyle=\sum_{v\in
R_{1}^{\prime}(u)}|C(u)\cap N_{u}^{+}\cap N_{v}^{+}|\geq\sum_{v\in
R_{1}^{\prime}(u)}0.15\cdot|N_{u}^{+}|$
$\displaystyle=0.15\cdot|N_{u}^{+}|\cdot|R_{1}^{\prime}(u)|\geq
0.15\cdot\Delta_{u}\cdot\frac{5}{3}\Delta_{u}=0.25\cdot\Delta_{u}^{2}.$

First we lower bound the amount of charge each $u$ satisfying Case 2a(ii)
receives, which is at least

$\displaystyle\frac{1}{|C(u)|}\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)^{p}$
$\displaystyle\geq\frac{1}{|C(u)|}\cdot\frac{1}{|N_{u}^{+}\cap
C(u)|^{p-1}}\cdot\Big{(}\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)\Big{)}^{p}$
$\displaystyle\geq\frac{1}{2\Delta_{u}}\cdot\frac{1}{\Delta_{u}^{p-1}}\cdot\Big{(}0.25\cdot\Delta_{u}^{2}\Big{)}^{p}\geq\frac{1}{2}\cdot
0.25^{p}\cdot|N_{u}^{+}|^{p},$

where in the first inequality we have applied Jensen’s inequality.

Next we need to upper bound the amount of charge dispensed in total to all $u$
satisfying Case 2a(ii). Note by definition that $\varphi(u,w)\leq y(w)$. Each
vertex $w\in V$ dispenses at most $y(w)^{p}/|C(u)|=y(w)^{p}/|C(w)|$ charge to
each $u\in C(w)\cap N_{w}^{+}$. So in total each $w$ dispenses at most
$|C(w)|\cdot y(w)^{p}/|C(w)|=y(w)^{p}$ charge to all $u$ satisfying Case
2a(ii).

Now we put together the lower and upper bounds on the total charge dispensed:

$\displaystyle\sum_{w\in V}y(w)^{p}$ $\displaystyle\geq\text{charge
dispensed}\geq\sum_{u\in V^{2a(ii)}}\frac{1}{|C(u)|}\sum_{w\in N_{u}^{+}\cap
C(u)}\varphi(u,w)^{p}\geq\sum_{u\in V^{2a(ii)}}\frac{1}{2}\cdot
0.25^{p}\cdot|N_{u}^{+}|^{p}.$ $\text{ In all, }\quad\boxed{\sum_{u\in
V^{2a(ii)}}|N_{u}^{+}|^{p}\leq 2\cdot 4^{p}\cdot\sum_{w\in V}y(w)^{p}\leq
2\cdot 4^{p}\cdot\textsf{OPT}^{p}.}$

Case 2b: _At least half of $R_{1}(u)$ is in $C(u)$._
Let $u\in V^{2b}$ be the vertices in this case. Denote the vertices in
$R_{1}(u)$ that are in $C(u)$ by $R_{1}^{\prime\prime}(u)$. By definition of
Case 2b, $|R_{1}^{\prime\prime}(u)|\geq\frac{5}{3}\cdot\Delta_{u}$. Since
every vertex in $R^{\prime\prime}(u)$ is in $N_{u}^{-}$, there are at least
$|R^{\prime\prime}(u)|$ disagreements incident to $u$. So
$y(u)\geq|R^{\prime\prime}(u)|\geq\frac{5}{3}\cdot\Delta_{u},$ which gives
that

$\boxed{\sum_{u\in V^{2b}}|N_{u}^{+}|^{p}=\sum_{u\in
V^{2b}}\Delta_{u}^{p}\leq\sum_{u\in V^{2b}}y(u)^{p}\leq\textsf{OPT}^{p}.}$

Adding the terms in the boxed expressions across all cases, the proposition
follows. ∎

$\text{So we have}\quad\boxed{S_{11}^{+}\leq\sum_{u\in
R_{1}}|N_{u}^{+}|^{p}\leq\left((20/3)^{p}+2+2\cdot
4^{p}\right)\cdot\textsf{OPT}^{p}.}$

Adding together all the cases, we conclude that

$(S^{+})^{p}\leq 2^{p}\cdot(S_{1}^{+}+S_{2}^{+})\leq
2^{p}\cdot(S_{11}^{+}S_{12^{+}}+S_{2}^{+})\leq
2^{p}\cdot[(8^{p}/2+1)((20/3)^{p}+2+2\cdot
4^{p})+8^{p}+1]\cdot\textsf{OPT}^{p}.$

∎

####  4.2.2 Fractional cost of negative edges in $\ell_{p}$-norms

This section bounds the cost of negative edges. The meanings of $\mathcal{C}$,
$C(\cdot)$, and $y$ are as in the previous subsection.

######  Lemma 6.

For $p\in\mathbb{R}_{\geq 1}$, the fractional cost of the adjusted correlation
metric $f$ in the $\ell_{p}$-norm objective for the set of negative edges is a
constant factor approximation to the optimal, i.e.,

$(S^{-})^{p}=\sum_{u\in V}\Big{(}\sum_{v\in
N_{u}^{-}}(1-f_{uv})\Big{)}^{p}\leq
2^{p}((200/9)^{p}+1+(10/3)^{p}+2\cdot(20/3)^{p})\cdot\textsf{OPT}^{p}.$

###### Proof.

We have

$\displaystyle(S^{-})^{p}$ $\displaystyle=\sum_{u\in V}\Big{(}\sum_{v\in
N_{u}^{-}}(1-f_{uv})\Big{)}^{p}\leq 2^{p}\underbrace{\sum_{u\in
V}\Big{(}\sum_{v\in N_{u}^{-}\cap
C(u)}(1-f_{uv})\Big{)}^{p}}_{S_{1}^{-}}+2^{p}\underbrace{\sum_{u\in
V}\Big{(}\sum_{v\in
N_{u}^{-}\cap\overline{C(u)}}(1-f_{uv})\Big{)}^{p}}_{S_{2}^{-}}.$

It is easy to bound $S_{1}^{-}$ by using the trivial upper bound $1-f_{uv}\leq
1$:

$\boxed{S_{1}^{-}=\sum_{u\in V}\Big{(}\sum_{v\in N_{u}^{-}\cap
C(u)}(1-f_{uv})\Big{)}^{p}\leq\sum_{u\in V}\Big{(}\sum_{v\in N_{u}^{-}\cap
C(u)}1\Big{)}^{p}\leq\sum_{u\in V}y(u)^{p}=\textsf{OPT}^{p},}$

where we have used that every edge $(u,v)\in E^{-}$ with $v\in C(u)$ is a
disagreement incident to $u$. Next, we bound $S_{2}^{-}$. Let $R_{1}$ and
$R_{2}$ be as in the previous subsection:
$R_{1}=\\{u:|N_{u}^{-}\cap\\{v:d_{uv}\leq
0.7\\}|\geq\frac{10}{3}\cdot\Delta_{u}\\}$ and $R_{2}=V\setminus R_{1}$. For
$u\in R_{2}$, define

$V_{u}=\\{v:v\in N_{u}^{-}\cap\overline{C(u)},d_{uv}\leq 0.7\\}.$

Note that the definition of $V_{u}$ is the same as $R^{\prime}_{1}(u)$ in the
previous subsection, but here $V_{u}$ is only defined for $u\in R_{2}$, while
$R^{\prime}_{1}(u)$ was defined for $u\in R_{1}$. For $u\in R_{1}$, we have
$1-f_{uv}=0$ for every $v\in V\setminus\\{u\\}$. So the outer sum in
$S_{2}^{-}$ only need be taken over $u\in R_{2}$:

$\displaystyle S_{2}^{-}$ $\displaystyle=\sum_{u\in R_{2}}\Big{(}\sum_{v\in
N_{u}^{-}\cap\overline{C(u)}}(1-f_{uv})\Big{)}^{p}\leq\sum_{u\in
R_{2}}\Big{(}\sum_{\begin{subarray}{c}v:v\in N_{u}^{-}\cap\overline{C(u)},\\\
d_{uv}\leq 0.7\end{subarray}}(1-d_{uv})\Big{)}^{p}\leq\sum_{u\in
R_{2}}|V_{u}|^{p}$

In the second equality, we have used that if $u\in R_{2}$ and $v\in
N_{u}^{-}$, then $f_{uv}=d_{uv}$, unless $f_{uv}$ was rounded up to 1 in Step
2 of Definition 3 (which happens when $d_{uv}>0.7$), or $f_{uv}$ was rounded
up to 1 in Step 3 (in which case $1-f_{uv}=0\leq 1-{d_{uv}}$).

A key observation is that since $u\in R_{2}$, it is the case that
$|V_{u}|\leq\frac{10}{3}\cdot\Delta_{u}$.

Fix a vertex $u\in R_{2}$. We consider a few cases.

##### Case 1:

_At least a 0.15 fraction of $N_{u}^{+}$ is in clusters other than $C(u)$._
Define $V^{1}$ to be the set of $u\in R_{2}$ that satisfy Case 1. Then for
$u\in V^{1}$, $0.15\cdot|N_{u}^{+}|\leq y(u)$, and further

$|V_{u}|\leq\frac{10}{3}\Delta_{u}\leq\frac{1}{0.15}\cdot\frac{10}{3}y(u)=\frac{200}{9}y(u).$

It follows that

$\boxed{\sum_{u\in V^{1}}|V_{u}|^{p}\leq(200/9)^{p}\cdot\sum_{u\in
V^{1}}y(u)^{p}\leq(200/9)^{p}\cdot\textsf{OPT}^{p}.}$

##### Case 2:

_At least a 0.85 fraction of $N_{u}^{+}$ is in $C(u)$. _
Define $V^{2}$ to be the set of $u\in R_{2}$ that satisfy Case 2. Fix $u\in
V^{2}$ and $v\in V_{u}$. Define $N_{u,v}=N_{u}^{+}\cap N_{v}^{+}\cap C(u)$.
Since $d_{uv}\leq 0.7$ and by the assumption of this case, using Proposition 1
we have

$|N_{u,v}|=|N_{u}^{+}\cap N_{v}^{+}\cap C(u)|\geq 0.15\cdot\Delta_{u}.$

Observe that since $v\not\in C(u)$ for $v\in V_{u}$, $(v,w)$ is a (positive)
disagreement for all $w\in N_{u,v}$.

Case 2a: _$|N_{u}^{-}\cap C(u)|\geq\Delta_{u}$._

Define $V^{2a}$ to be the set of $u\in V^{2}$ that satisfy Case 2a. Since all
edges $(u,v)$ with $v\in N_{u}^{-}\cap C(u)$ are disagreements, we have
$y(u)\geq\Delta_{u}$. Recalling that $|V_{u}|\leq\frac{10}{3}\cdot\Delta_{u}$
for $u\in R_{2}$, we have

$\boxed{\sum_{u\in V^{2a}}|V_{u}|^{p}\leq\sum_{u\in
V^{2a}}(10/3\cdot\Delta_{u})^{p}\leq(10/3)^{p}\cdot\sum_{u\in
V^{2a}}y(u)^{p}\leq(10/3)^{p}\cdot\textsf{OPT}^{p}.}$

Case 2b: _$|C(u)|\leq 2\Delta_{u}$._

Define $V^{2b}$ to be the $u\in V^{2}$ satisfying Case 2b. Fix $w\in
N_{u}^{+}\cap C(u)$ and $u\in V^{2b}$. Define

$\varphi(u,w)=|V_{u}\cap N_{w}^{+}|,$

i.e. $\varphi(u,w)$ is the number of $v\in V_{u}$ with $w\in N_{u,v}$. Each
$w\in N_{u}^{+}\cap C(u)$ dispenses $\frac{\varphi(u,w)^{p}}{|C(u)|}$ charge
to $u$. Also,

$\displaystyle\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)$
$\displaystyle=\sum_{w\in N_{u}^{+}\cap C(u)}|V_{u}\cap N_{w}^{+}|=\sum_{w\in
N_{u}^{+}\cap C(u)}\sum_{v\in V_{u}\cap N_{w}^{+}}1$ $\displaystyle=\sum_{v\in
V_{u}}\sum_{w\in N_{u,v}}1=\sum_{v\in V_{u}}|N_{u,v}|\geq|V_{u}|\cdot
0.15\cdot\Delta_{u}.$

Now we can lower bound the amount of charge each $u$ satisfying Case 2b
receives, which is at least

$\displaystyle\frac{1}{|C(u)|}\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)^{p}$
$\displaystyle\geq\frac{1}{|C(u)|}\cdot\frac{1}{|N_{u}^{+}\cap
C(u)|^{p-1}}\Big{(}\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)\Big{)}^{p}$
$\displaystyle\geq\frac{1}{2\Delta_{u}}\cdot\frac{1}{\Delta_{u}^{p-1}}\left(|V_{u}|\cdot
0.15\cdot\Delta_{u}\right)^{p}=\frac{1}{2}\cdot 0.15^{p}\cdot|V_{u}|^{p},$

where in the first line we used Jensen’s inequality.

To upper bound the amount of charge dispensed in total to all $u$ satisfying
Case 2b, first note that $\varphi(u,w)\leq y(w)$. Also, each vertex $w\in V$
only distributes charge to $u\in C(w)\cap N_{w}^{+}$, and the amount of charge
distributed to each such $u$ is

$\frac{\varphi(u,w)^{p}}{|C(u)|}=\frac{\varphi(u,w)^{p}}{|C(w)|}\leq\frac{y(w)^{p}}{|C(w)|},$

so that in total each $w$ dispenses at most
$\frac{y(w)^{p}}{|C(w)|}\cdot|C(w)|\leq y(w)^{p}$ charge. Putting together the
lower and upper bounds on the amount of charge dispensed:

$\displaystyle\sum_{w\in V}y(w)^{p}$ $\displaystyle\geq\text{total charge
dispensed}\geq\sum_{u\in V^{2b}}\frac{1}{|C(u)|}\sum_{w\in N_{u}^{+}\cap
C(u)}\varphi(u,w)^{p}\geq\sum_{u\in V^{2b}}\frac{1}{2}\cdot
0.15^{p}\cdot|V_{u}|^{p}.$

So in all,

$\boxed{\sum_{u\in V^{2b}}|V_{u}|^{p}\leq 2\cdot(20/3)^{p}\cdot\sum_{w\in
V}y(w)^{p}=2\cdot(20/3)^{p}\cdot\textsf{OPT}^{p}.}$

Adding together all the cases, we see that $(S^{-})^{p}\leq
2^{p}((200/9)^{p}+1+(10/3)^{p}+2\cdot(20/3)^{p})\cdot\textsf{OPT}^{p}.$ ∎

###  4.3 Proofs of Theorem 1 and Corollary 1

Here we show that Theorem 1 and Corollary 1 follow directly from the preceding
lemmas.

###### Proof of Theorem 1.

First we show that Lemma 4 implies that the clustering resulting from
inputting $f$ into the KMZ rounding algorithm is $O(1)$-approximate in any
$\ell_{p}$-norm. Since the rounding algorithm does not depend on $p$, the
clustering will be the same for all $p$. Let $\mathcal{C^{*}}$ be the
clustering produced by running the KMZ rounding algorithm with the adjusted
correlation metric $f$ as input. Let $\textsf{ALG}(u)$ be the number of edges
incident to $u$ that are disagreements with respect to $\mathcal{C}^{*}$. From
[28] and Lemmas 1 and 2, we have that for every $u\in V$, $\textsf{ALG}(u)\leq
12\cdot y_{u}$ where $y_{u}$ is as in LP 2.2 when taking $x=f$. So $||y||_{p}$
is the fractional cost of $f$ in the $\ell_{p}$-norm. In what follows,
$||\textsf{ALG}||_{p}$ is the objective value of $\mathcal{C}^{*}$ in the
$\ell_{p}$-norm and $\textsf{OPT}(p)$ is the optimal objective value in the
$\ell_{p}$-norm. Thus using Lemma 4 in the last inequality, we have

$||\textsf{ALG}||_{p}\leq 12\cdot||y||_{p}\leq 12\cdot
529\cdot\textsf{OPT}(p)=6348\cdot\textsf{OPT}(p).$

We show the overall run-time is $O(n^{\omega})$. Recall from the analysis in
[19] that computing the correlation metric takes time $O(n^{\omega})$, and the
KMZ rounding algorithm takes time $O(n^{2})$. We just have to show the post-
processing of $d$ in Steps 2 and 3 of Definition 3 that were done in order to
obtain the adjusted correlation metric $f$ can be done quickly. Indeed, Step 2
takes $O(n^{2})$ time as it simply iterates through the edges. Step 3 also
takes $O(n^{2})$ time, since it visits each vertex and iterates through the
neighbors. Thus, the run-time remains $O(n^{\omega})$. ∎

###### Proof of Corollary 1.

In [19], they observe that to reduce the run-time from $O(n^{\omega})$ to
$O(n\Delta^{2}\log n)$ for graphs with maximum positive degree bounded by
$\Delta$, one can compute the correlation metric $d$ in $O(n\Delta^{2})$ time
and then run the KMZ rounding algorithm in $O(n\Delta^{2}\log n)$ time (see
the proof of Corollary 1.2 in Appendix D of [19]). We need only compute
$f_{uv}$ when $f_{uv}<1$. Otherwise, we can handle $f_{uv}=1$ implicitly. As
in [19], for each $u\in V$, we can maintain a list of $d_{uv}$ for all $v$
with $d_{uv}<1$. Computing these lists takes $O(n\Delta^{2})$ time in total.
(This is because there are at most $\Delta^{2}$ vertices $v$ that are distance
two away from $u$ in the positive subgraph.) Steps 2 and 3 only prune these
lists further, since some distances that are below 1 may be raised to 1;
importantly, no distance that is already equal to 1 under $d$ will be reduced
in Steps 2 and 3. To carry out Step 2, for each vertex $u$ it takes
$O(\Delta^{2})$ time to iterate through the list for $u$ and raise the
appropriate $d_{uv}$ to 1. Similarly, to carry out Step 3, for each vertex $u$
it takes $O(\Delta^{2})$ time to determine whether the condition in Step 3 is
satisfied; if it is, we just handle the vertex $u$ implicitly, as all
distances $f_{uv}$ are set to 1.

Since each vertex’s list still has size at most $\Delta^{2}$ after the post-
processing in Steps 2 and 3, the KMZ rounding algorithm with $f$ as input
takes time $O(n\Delta^{2}\log n)$, by the exact same argument as in [19]. ∎

##  5 Conclusion

This paper considered correlation clustering on unweighted, complete graphs, a
problem that arises in many settings including community detection and the
study of large networks. All previous works that study minimizing the
$\ell_{p}$-norm (for $p\in\mathbb{R}_{>1}$) of the disagreement vector rely on
solving a large, convex relaxation (which is costly to the algorithm’s run-
time) and produce a solution that is only $O(1)$-approximate for one specific
value of $p$. We innovate upon this rich line of work by (1) giving the first
combinatorial algorithm for the $\ell_{p}$-norms for $p\in\mathbb{R}_{>1}$,
(2) designing scalable algorithms for this practical problem, and (3)
obtaining solutions that are $O(1)$-approximate for all $\ell_{p}$-norms (for
$p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$) simultaneously. We note this last
point is particularly important, as such solutions are good in both global and
local senses, and thus may be more desirable than typical optimal or
approximate solutions for correlation clustering. The existence of these
solutions reveals a surprising structural property of correlation clustering.

One question is whether there is a simpler existential (not necessarily
algorithmic) proof that there exists an $O(1)$-approximation for the all-norm
objective for correlation clustering.

It is also of interest to implement the KMZ algorithm with the adjusted
correlation metric as input, and empirically gain an understanding of how good
the adjusted correlation metric is for different $\ell_{p}$-norms. We suspect
that our analysis is lossy (for instance, we did not attempt to optimize
constants), and that the approximation obtained would be of much better
quality than our analysis guarantees.

Finally, it would be interesting if an analogous result can be obtained for
weighted correlation clustering.

## References

  * [1] Saba Ahmadi, Samir Khuller and Barna Saha  “Min-max correlation clustering via multicut”  In _International Conference on Integer Programming and Combinatorial Optimization_ , 2019, pp. 13–26  Springer
  * [2] Saba Ahmadi, Sainyam Galhotra, Barna Saha and Roy Schwartz  “Fair correlation clustering”  In _arXiv preprint arXiv:2002.03508_ , 2020
  * [3] Sara Ahmadian, Alessandro Epasto, Ravi Kumar and Mohammad Mahdian  “Fair correlation clustering”  In _International Conference on Artificial Intelligence and Statistics_ , 2020, pp. 4195–4205  PMLR
  * [4] Nir Ailon, Moses Charikar and Alantha Newman  “Aggregating inconsistent information: ranking and clustering”  In _Journal of the ACM (JACM)_ 55.5 ACM New York, NY, USA, 2008, pp. 1–27
  * [5] Soroush Alamdari and David Shmoys  “A bicriteria approximation algorithm for the k-center and k-median problems”  In _Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Vienna, Austria, September 7–8, 2017, Revised Selected Papers 15_ , 2018, pp. 66–75  Springer
  * [6] Yossi Azar, Leah Epstein, Yossi Richter and Gerhard J Woeginger  “All-norm approximation algorithms”  In _Journal of Algorithms_ 52.2 Elsevier, 2004, pp. 120–133
  * [7] Nikhil Bansal, Avrim Blum and Shuchi Chawla  “Correlation clustering”  In _Machine learning_ 56.1 Springer, 2004, pp. 89–113
  * [8] Mohammadhossein Bateni, Vincent Cohen-Addad, Alessandro Epasto and Silvio Lattanzi  “Scalable and Improved Algorithms for Individually Fair Clustering”  In _Workshop on Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022_
  * [9] Amir Ben-Dor and Zohar Yakhini  “Clustering gene expression patterns”  In _Proceedings of the third annual international conference on computational molecular biology_ , 1999, pp. 33–42
  * [10] Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat and Clifford Stein  “Simultaneously load balancing for every p-norm, with reassignments”  In _8th Innovations in Theoretical Computer Science Conference (ITCS 2017)_ , 2017  Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
  * [11] Francesco Bonchi, David Garcia-Soriano and Edo Liberty  “Correlation clustering: from theory to practice.”  In _KDD_ , 2014, pp. 1972
  * [12] Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman and Srivathsan Srinivasagopalan  “Split and join: Strong partitions and universal steiner trees for graphs”  In _2012 IEEE 53rd Annual Symposium on Foundations of Computer Science_ , 2012, pp. 81–90  IEEE
  * [13] Ostas Busch, Arnold Filtser, Daniel Hathcock, D Ellis Hershkowitz and Rajmohan Rajaraman  “One tree to rule them all: Poly-logarithmic universal steiner tree”  In _2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2023, pp. 60–76  IEEE
  * [14] Sayak Chakrabarty and Konstantin Makarychev  “Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!”  In _arXiv preprint arXiv:2305.13560_ , 2023
  * [15] Moses Charikar, Neha Gupta and Roy Schwartz  “Local Guarantees in Graph Cuts and Clustering”  In _Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings_ 10328, Lecture Notes in Computer Science  Springer, 2017, pp. 136–147  DOI: 10.1007/978-3-319-59250-3“˙12
  * [16] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm and Grigory Yaroslavtsev  “Near optimal lp rounding algorithm for correlationclustering on complete and complete k-partite graphs”  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , 2015, pp. 219–228
  * [17] Flavio Chierichetti, Nilesh Dalvi and Ravi Kumar  “Correlation clustering in mapreduce”  In _Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining_ , 2014, pp. 641–650
  * [18] Vincent Cohen-Addad, Euiwoong Lee and Alantha Newman  “Correlation Clustering with Sherali-Adams”  In _Symposium on Foundations of Computer Science (FOCS)._ , 2022
  * [19] Sami Davies, Benjamin Moseley and Heather Newman  “Fast Combinatorial Algorithms for Min Max Correlation Clustering”  In _International Conference on Machine Learning_ , 2023  PMLR
  * [20] Erik D Demaine and Nicole Immorlica  “Correlation clustering with partial information”  In _Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques_ Springer, 2003, pp. 1–13
  * [21] Zachary Friggstad and Ramin Mousavi  “Fair correlation clustering with global and local guarantees”  In _Workshop on Algorithms and Data Structures_ , 2021, pp. 414–427  Springer
  * [22] Arun Ganesh, Bruce M Maggs and Debmalya Panigrahi  “Universal algorithms for clustering problems”  In _ACM Transactions on Algorithms_ 19.2 ACM New York, NY, 2023, pp. 1–46
  * [23] Daniel Golovin, Anupam Gupta, Amit Kumar and Kanat Tangwongsan  “All-norms and all-l_p-norms approximation algorithms”  In _IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science_ , 2008  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [24] Holger Heidrich, Jannik Irmai and Bjoern Andres  “A 4-approximation algorithm for min max correlation clustering”  In _arXiv preprint arXiv:2310.09196_ , 2023
  * [25] Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev and Yury Makarychev  “Local correlation clustering with asymmetric classification errors”  In _International Conference on Machine Learning_ , 2021, pp. 4677–4686  PMLR
  * [26] Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev and Yury Makarychev  “Local Correlation Clustering with Asymmetric Classification Errors”  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 4677–4686  URL: http://proceedings.mlr.press/v139/jafarov21a.html
  * [27] Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman and Ravi Sundaram  “Universal approximations for TSP, Steiner tree, and set cover”  In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing_ , 2005, pp. 386–395
  * [28] Sanchit Kalhan, Konstantin Makarychev and Timothy Zhou  “Correlation clustering with local objectives”  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2019, pp. 9341–9350
  * [29] Jon Kleinberg, Yuval Rabani and Éva Tardos  “Fairness in routing and load balancing”  In _40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)_ , 1999, pp. 568–578  IEEE
  * [30] Zach Langley, Aaron Bernstein and Sepehr Assadi  “Improved bounds for distributed load balancing”  In _34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik_ , 2020
  * [31] Andrew McCallum and Ben Wellner  “Conditional models of identity uncertainty with application to noun coreference”  In _Advances in neural information processing systems_ 17, 2004
  * [32] Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran and Michael I Jordan  “Scaling up correlation clustering through parallelism and concurrency control”  In _DISCML Workshop at International Conference on Neural Information Processing Systems_ , 2014
  * [33] Gregory J. Puleo and Olgica Milenkovic  “Correlation Clustering and Biclustering with Locally Bounded Errors”  In _Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016_ 48, JMLR Workshop and Conference Proceedings  JMLR.org, 2016, pp. 869–877  URL: http://proceedings.mlr.press/v48/puleo16.html
  * [34] Gregory J Puleo and Olgica Milenkovic  “Correlation clustering with constrained cluster sizes and extended weights bounds”  In _SIAM Journal on Optimization_ 25.3 SIAM, 2015, pp. 1857–1872
  * [35] Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lacki and Vahab S. Mirrokni  “Scalable Community Detection via Parallel Correlation Clustering”  In _Proc. VLDB Endow._ 14, 2021, pp. 2305–2313
  * [36] Nate Veldt  “Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds”  In _International Conference on Machine Learning_ , 2022, pp. 22060–22083  PMLR
  * [37] Nate Veldt, David F Gleich and Anthony Wirth  “A correlation clustering framework for community detection”  In _Proceedings of the 2018 World Wide Web Conference_ , 2018, pp. 439–448
  * [38] Anthony Wirth  “Correlation Clustering”  In _Encyclopedia of Machine Learning and Data Mining_ Springer, 2017, pp. 280–284  DOI: 10.1007/978-1-4899-7687-1“˙176

##  Appendix A Triangle Inequality

Below is the proof that the adjusted correlation metric $f$ satisfies an
approximate triangle inequality.

###### Proof of Lemma 1.

Note that after Step 1 of Definition 3, $f$ satisfies the triangle inequality,
since $f=d$ here and for any $u,v,w$, $d_{uv}\leq d_{uw}+d_{vw}.$ We then
consider the execution of Step 2 in Definition 3. The triangle inequality on
the adjusted correlation metric holds if either of $(u,w)$ or $(w,v)$ have
distance 1 with respect to the adjusted correlation metric, and it also
clearly holds if the three edges have the same distance as in the correlation
metric. It follows that the only case to check is when $f_{uv}=1$,
$f_{uw}=d_{uw}$, and $f_{wv}=d_{wv}$. If $f_{uv}=1$ at the end of Step 2, by
the definition of $f$ it must be that $d_{uv}>0.7$. Since $d_{uv}\leq
d_{uw}+d_{vw}$, we have that $0.7\leq d_{uw}+d_{vw}$, and so
$f_{uv}=1\leq\frac{10}{7}(d_{uw}+d_{vw})\leq\frac{10}{7}(f_{uw}+f_{vw})$ at
the end of Step 2.

Finally, Step 3 of Definition 3 also preserves this approximate triangle
inequality. The $f$ values on the edges leaving a vertex are raised to 1
together, and any triangle involving one of these edges necessarily involves
another. ∎

##  Appendix B $\ell_{\infty}$-norm Approximation

Below we include the proof that the adjusted correlation metric $f$ has
bounded fractional cost in the $\ell_{\infty}$-norm.

###### Proof of Lemma 3.

The fractional cost of the correlation metric $d$ is at most
$8\cdot\textsf{OPT}$ by [19]. That is,

$\sum_{v\in N_{u}^{+}}d_{uv}+\sum_{v\in N_{u}^{-}}(1-d_{uv})\leq
8\cdot\textsf{OPT}\hskip 8.5359pt\text{for all }u\in V.$ (4)

Consider any $u\in V$. Observe that the second sum in (4) can only decrease if
Step 2 in Definition 3 is executed for any of the negative edges incident to
$u$. Now let $R_{1}$ denote the set of vertices $u$ such that Step 3 is
executed on $u$. For $u\in R_{1}$, the second sum decreases by at least
$\frac{3}{10}\cdot\frac{10}{3}\cdot\Delta_{u}=\Delta_{u}$, since there are at
least $\frac{10}{3}\cdot\Delta_{u}$ negative edges $(u,v)$ with
$1-d_{uv}\geq\frac{3}{10}$, and these edges are all rounded up to 1 in $f$, so
$1-d_{uv}$ is rounded down to 0. On the other hand, the first sum increases by
at most $\Delta_{u}$, since there are $\Delta_{u}$ positive edges incident to
$u$ and each gets rounded up to 1 in $f$. Therefore, we know that (4) does not
increase when we replace $d$ with $f$ when $u\in R_{1}$.

Finally, it is possible that (4) increases even when $u\not\in R_{1}$. This is
because $u$ may have neighbors $v$ such that $v\in R_{1}$. For such $v$,
$d_{uv}$ is raised to $f_{uv}=1$. This is only better for the second sum in
(4). Now we consider what happens to the first sum in (4) when we replace $d$
with $f$. Let $R_{2}=V\setminus R_{1}$. Fix $u\in R_{2}$. Then

$\displaystyle\sum_{v\in N_{u}^{+}}f_{uv}$ $\displaystyle=\sum_{v\in
N_{u}^{+}\cap R_{1}}1+\sum_{v\in N_{u}^{+}\cap R_{2}}d_{uv}$
$\displaystyle=\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap R_{1}\\\ d_{uv}\leq
1/4\end{subarray}}1+\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap R_{1}\\\
d_{uv}>1/4\end{subarray}}1+\sum_{v\in N_{u}^{+}\cap R_{2}}d_{uv}$
$\displaystyle\leq\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap R_{1}\\\
d_{uv}\leq 1/4\end{subarray}}1+\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap
R_{1}\\\ d_{uv}>1/4\end{subarray}}4\cdot d_{uv}+\sum_{v\in N_{u}^{+}\cap
R_{2}}d_{uv}$ $\displaystyle\leq\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap
R_{1}\\\ d_{uv}\leq 1/4\end{subarray}}1+4\cdot\sum_{v\in N_{u}^{+}}d_{uv}$

The second term above is bounded by $32\cdot\textsf{OPT}$ by (4). To bound the
first term, let $w^{*}$ be an arbitrary vertex in $N_{u}^{+}\cap R_{1}$ (if
this set is empty, we just ignore the first term). Since $d_{uw^{*}}\leq 1/4$,
we know by Proposition 2 that $\Delta_{u}\leq\frac{7}{3}\cdot\Delta_{w^{*}}$.
Also,

$\sum_{v\in N_{w^{*}}^{+}}f_{w^{*}v}+\sum_{v\in
N_{w^{*}}^{-}}(1-f_{w^{*}v})\leq\Delta_{w}^{*}$

since $w^{*}\in R_{1}$, and by the argument in the previous paragraph we have
that $\Delta_{w^{*}}\leq 8\cdot\textsf{OPT}$. So

$\sum_{\begin{subarray}{c}v\in N_{u}^{+}\cap R_{1}\\\ d_{uv}\leq
1/4\end{subarray}}1\leq\Delta_{u}\leq\frac{7}{3}\cdot\Delta_{w^{*}}\leq\frac{7}{3}\cdot
8\cdot\textsf{OPT}.$

This concludes the proof. ∎

##  Appendix C $\ell_{1}$-norm Approximation

The next lemma proves that the adjusted correlation metric well approximates
the optimal in the $\ell_{1}$-norm. We will show that the fractional cost of
the adjusted correlation metric $f$ in the $\ell_{1}$-norm is a constant
factor approximation to the optimal, i.e.,

$\sum_{u\in V}\sum_{v\in N_{u}^{+}}f_{uv}+\sum_{u\in V}\sum_{v\in
N_{u}^{-}}(1-f_{uv})=O(\textsf{OPT}).$

We argue the second sum—over the negative edges—has a constant factor
approximation in the first lemma (Lemma 9), then show the first sum—over the
positive edges—does too in the second lemma (Lemma 8). Combining these lemmas
gives the following approximation guarantee for the $\ell_{1}$-norm.

######  Lemma 7.

The fractional cost of the adjusted correlation metric $f$ in the
$\ell_{1}$-norm objective is a constant factor away from the cost of the
optimal integral solution in the $\ell_{1}$-norm

###### Proof.

The fractional cost in the $\ell_{1}$-norm is

$\sum_{u\in V}\sum_{v\in N_{u}^{+}}f_{uv}+\sum_{u\in V}\sum_{v\in
N_{u}^{-}}(1-f_{uv})\leq 74\cdot\textsf{OPT}.$

The first sum is bounded by $34\cdot\textsf{OPT}$ by Lemma 8 and the second
sum is bounded by $40\cdot\textsf{OPT}$ by Lemma 9. ∎

######  Lemma 8.

The fractional cost of the adjusted correlation metric $f$ in the
$\ell_{1}$-norm objective for the set of positive edges is a constant factor
approximation to the optimal, i.e.,

$\sum_{u\in V}\sum_{v\in N_{u}^{+}}f_{uv}=34\cdot\textsf{OPT}.$

###### Proof of Lemma 8.

Fix an optimal clustering $\mathcal{C}$. We partition vertices based on
membership in $C(u)$ or $\overline{C(u)}$ and let $y$ denote the disagreement
vector of $\mathcal{C}$. We prove in the following claim that the total
fractional cost of edges $e\in E^{+}$ such that $f_{e}=d_{e}$ is bounded.
Then, it just remains to bound the fractional cost of positive edges whose
distances are raised to 1 in Step 3 of Definition 3.

######  Claim 1.

The total fractional cost of positive edges for the $\ell_{1}$-norm objective
when $f_{e}=d_{e}$ is a $3$-approximation.

###### Proof of Claim 1.

For the $\ell_{1}$-norm, $\textsf{OPT}=\sum_{u\in V}y(u)$. So for a fixed
vertex $u$, we partition the fractional cost of disagreements from positive
edges incident to $u$, i.e. $(u,v)\in E^{+}$, based on whether vertices $v$
are in $C(u)$ or not:

$\displaystyle\sum_{u\in V}\sum_{v\in N_{u}^{+}}f_{uv}$
$\displaystyle=\sum_{u\in V}\sum_{v\in N_{u}^{+}\cap C(u)}d_{uv}+\sum_{u\in
V}\sum_{v\in N_{u}^{+}\cap\overline{C(u)}}d_{uv}$ $\displaystyle=\sum_{u\in
V}\sum_{v\in N_{u}^{+}\cap C(u)}\frac{|N_{u}^{+}\cap N_{v}^{-}|+|N_{u}^{-}\cap
N_{v}^{+}|}{n-|N_{u}^{-}\cap N_{v}^{-}|}+\sum_{u\in V}\sum_{v\in
N_{u}^{+}\cap\overline{C(u)}}d_{uv}.$

The right-hand sum is easy as we can just use that $d_{uv}$ is at most 1.

$\boxed{\sum_{u\in V}\sum_{v\in
N_{u}^{+}\cap\overline{C(u)}}d_{uv}\leq\sum_{u\in V}\sum_{v\in
N_{u}^{+}\cap\overline{C(u)}}1\leq\sum_{u\in V}y(u)=\textsf{OPT}}$

For the left-hand sum, we will exploit that $d_{uv}$ is symmetric, and
specifically that we can bound the denominator by $|N_{u}^{+}|$ or
$|N_{v}^{+}|$.

$\displaystyle\sum_{u\in V}\sum_{v\in N_{u}^{+}\cap C(u)}\frac{|N_{u}^{+}\cap
N_{v}^{-}|+|N_{u}^{-}\cap N_{v}^{+}|}{n-|N_{u}^{-}\cap
N_{v}^{-}|}\leq\sum_{u\in V}\sum_{v\in N_{u}^{+}\cap
C(u)}\frac{y(u)+y(v)}{n-|N_{u}^{-}\cap N_{v}^{-}|}$
$\displaystyle\leq\sum_{u\in V}\sum_{v\in
N_{u}^{+}}\frac{y(u)+y(v)}{n-|N_{u}^{-}\cap N_{v}^{-}|}=\sum_{u\in
V}\sum_{v\in N_{u}^{+}}\frac{y(u)}{n-|N_{u}^{-}\cap N_{v}^{-}|}+\sum_{u\in
V}\sum_{v\in N_{u}^{+}}\frac{y(v)}{n-|N_{u}^{-}\cap N_{v}^{-}|}$
$\displaystyle=\sum_{u\in V}\sum_{v\in N_{u}^{+}}\frac{y(u)}{n-|N_{u}^{-}\cap
N_{v}^{-}|}+\sum_{v\in V}\sum_{u\in N_{v}^{+}}\frac{y(v)}{n-|N_{u}^{-}\cap
N_{v}^{-}|}$ $\displaystyle\leq\sum_{u\in
V}\frac{y(u)}{|N_{u}^{+}|}\cdot|N_{u}^{+}|+\sum_{v\in
V}\frac{y(v)}{|N_{v}^{+}|}\cdot|N_{v}^{+}|\leq 2\cdot\textsf{OPT}.$

All in all:

$\boxed{\sum_{u\in V}\sum_{v\in N_{u}^{+}\cap C(u)}\frac{|N_{u}^{+}\cap
N_{v}^{-}|+|N_{u}^{-}\cap N_{v}^{+}|}{n-|N_{u}^{-}\cap N_{v}^{-}|}\leq
2\cdot\textsf{OPT}}$

∎

Now, we must bound the cost of the positive edges whose distances were raised
in Step 3 of Definition 3. Let $R_{1}=\\{u:|\\{N_{u}^{-}\cap\\{v:d_{uv}\leq
0.7\\}|\geq\frac{10}{3}\cdot\Delta_{u}\\}$. For any vertex $u$, define the
shorthand $R_{1}(u)=\\{N_{u}^{-}\cap\\{v:d_{uv}\leq 0.7\\}\\}$ 111111The use
of a subscript may not be clear here, but it is helpful in the $\ell_{p}$-norm
proof.; recall that $u\in R_{1}$ is put in its own cluster by the adjusted
correlation metric. Then, our next goal is to show that

$2\cdot\sum_{u\in R_{1}}|N_{u}^{+}|=O(\textsf{OPT}).$ (5)

Note that the factor of 2 comes from the observation that even if $u\not\in
R_{1}$, $u$ may have neighbors $v\in R_{1}\cap N_{u}^{+}$, in which cases
$f_{uv}$ is raised to 1 even though Step 3 is not executed on $u$. Fix a $u\in
R_{1}$. We subdivide into several cases based on $\mathcal{C}$.

##### Case 1:

_At least a 0.15 fraction of $N_{u}^{+}$ is in clusters other than $C(u)$._
Let $u\in V^{1}$ be the vertices in this case. There are at least
$0.15\cdot|N_{u}^{+}|$ disagreements incident to $u$, so

$\boxed{\sum_{u\in V^{1}}|N_{u}^{+}|\leq\sum_{u\in V^{1}}\frac{1}{0.15}\cdot
y(u)\leq\frac{20}{3}\cdot\textsf{OPT}.}$

##### Case 2:

_At least a 0.85 fraction of $N_{u}^{+}$ is in $C(u)$._
We subdivide Case 2 into two cases depending on how much of $R_{1}(u)$ is in
$\overline{C(u)}$.

Case 2a: _At least half of $R_{1}(u)$ is in clusters other than $C(u)$._
Let $u\in V^{2a}$ be the vertices in this case. Denote this subset of
$R_{1}(u)$ by $R^{\prime}_{1}(u)=R_{1}(u)\cap\overline{C(u)}$, and note that
$|R^{\prime}_{1}(u)|\geq\frac{5}{3}\cdot\Delta_{u}$. If the number of negative
edges incident to $u$ that are contained in $C(u)$ is more than $\Delta_{u}$,
then charge $|N_{u}^{+}|=\Delta_{u}$ to $y(u)$, since these negative edges are
disagreements. These $u\in V^{2a}$ thus contribute OPT to (5).

Otherwise, $|C(u)|\leq 2\Delta_{u}$. Consider $v\in R^{\prime}_{1}(u)$. Again,
let $N_{u,v}=N_{u}^{+}\cap N_{v}^{+}\cap C(u)$. Since $d_{uv}\leq 0.7$ and by
the assumption bringing us into Case 2, we apply Proposition 1 to see that
$|N_{u,v}|\geq 0.15\cdot|N_{u}^{+}|$. For each $v\in R^{\prime}_{1}(u)$ and
$w\in N_{u,v}$, the positive edge $(w,v)$ is a disagreement.

For $u\in V^{2a}$ and $w\in N_{u}^{+}\cap C(u)$, define

$\varphi(u,w)=|R_{1}^{\prime}(u)\cap N_{w}^{+}|.$

Let each $w\in N_{u}^{+}\cap C(u)$ dispense charge $\varphi(u,w)/|C(u)|$ to
$u$. First, observe that $u$ receives $\Omega(|N_{u}^{+}|)$ charge;
specifically, $u$ receives charge at least

$\displaystyle\sum_{w\in N_{u}^{+}\cap C(u)}\frac{\varphi(u,w)}{|C(u)|}$
$\displaystyle=\sum_{w\in N_{u}^{+}\cap C(u)}\frac{|R_{1}^{\prime}(u)\cap
N_{w}^{+}|}{|C(u)|}$ $\displaystyle=\frac{1}{|C(u)|}\cdot\sum_{w\in
N_{u}^{+}\cap C(u)}\sum_{v\in R_{1}^{\prime}(u)\cap
N_{w}^{+}}1=\frac{1}{|C(u)|}\cdot\sum_{v\in
R_{1}^{\prime}(u)}\sum_{\underset{\cap C(u)\cap N_{u}^{+}}{w\in\cap
N_{v}^{+}}}1$ $\displaystyle=\frac{1}{|C(u)|}\cdot\sum_{v\in
R_{1}^{\prime}(u)}|C(u)\cap N_{u}^{+}\cap
N_{v}^{+}|\geq\frac{1}{|C(u)|}\cdot\sum_{v\in
R_{1}^{\prime}(u)}0.15\cdot|N_{u}^{+}|$
$\displaystyle\geq\frac{1}{|C(u)|}\cdot
0.15\cdot|N_{u}^{+}|\cdot|R_{1}^{\prime}(u)|\geq\frac{1}{2\Delta_{u}}\cdot
0.15\cdot\Delta_{u}\cdot\frac{5}{3}\Delta_{u}=\frac{1}{8}\cdot\Delta_{u}.$

Next we upper bound the charge dispensed in total to _all_ $u\in V^{2a}$. Note
by definition that $\varphi(u,w)\leq y(w)$. Every vertex $w\in V$ dispenses at
most

$\frac{y(w)}{|C(u)|}=\frac{y(w)}{|C(w)|}$

charge to each $u\in C(w)\cap N_{w}^{+}$. So each $w$ dispenses a total of
charge at most

$\frac{y(w)}{|C(w)|}\cdot|C(w)|=y(w)$

to all $u\in V^{2a}$. Putting the lower and upper bounds together:

$\displaystyle\sum_{w\in V}y(w)$ $\displaystyle\geq\text{total charge
dispensed}$ $\displaystyle\geq\sum_{u\in V^{2a}:|C(u)|\leq
2\Delta_{u}}\frac{1}{|C(u)|}\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)$
$\displaystyle\geq\sum_{u\in V^{2a}:|C(u)|\leq
2\Delta_{u}}\frac{1}{8}\cdot|N_{u}^{+}|$

so

$\boxed{\sum_{u\in V^{2a}}|N_{u}^{+}|\leq\textsf{OPT}+8\cdot\sum_{w\in
V}y(w)\leq 9\cdot\textsf{OPT}.}$

Case 2b: _At least half of $R_{1}(u)$ is in $C(u)$._
Let $u\in V^{2b}$ be the vertices in this case. There are at least
$\frac{5}{3}\Delta_{u}$ negative disagreeing edges incident to $u$ (those
edges $(u,w)$ with $w\in R_{1}(u)$). So we may charge $|N_{u}^{+}|$ to $y(u)$:

$\boxed{\sum_{u\in V^{2b}}|N_{u}^{+}|\leq\textsf{OPT}}$

This concludes the bounding of the fractional cost of the negative edges, and
our constant in the approximation factor is $3+20/3+9+1<20$ (adding together
the boxed upper bounds). ∎

######  Lemma 9.

The fractional cost of the adjusted correlation metric $f$ in the
$\ell_{1}$-norm objective for the set of negative edges is a constant factor
approximation to the optimal, i.e.,

$\sum_{u\in V}\sum_{v\in N_{u}^{-}}(1-f_{uv})\leq 40\cdot\textsf{OPT}.$

###### Proof of Lemma 9.

First observe that negative edges that have been rounded up to 1 contribute 0
to the fractional cost. So we may focus on the fractional cost of negative
edges $e=(u,v)$ with $d_{uv}=f_{uv}\leq 0.7$.

Fix an optimal clustering $\mathcal{C}$, whose value is OPT. If $d_{uv}\leq
0.7$ but $u$ and $v$ are in the same cluster in $\mathcal{C}$, then $(u,v)$ is
a disagreement with respect to $\mathcal{C}$, so we can charge the fractional
cost $1-f_{e}=1-d_{e}\leq 1$ to OPT.

Now we need to consider the negative edges whose endpoints are in different
clusters in $\mathcal{C}$. Recall $C(u)$ is the cluster of $\mathcal{C}$
containing vertex $u$. We define the set of _cut edges_ incident to $u$ to be

$E_{u}=\\{(u,v):(u,v)\in E^{-},d_{uv}\leq 0.7,C(u)\neq C(v)\\}.$

By Step 3 in the definition of the adjusted correlation metric, $|E_{u}|\leq
10/3\cdot\Delta_{u}$. Since the fractional cost of each cut edge is
$1-f_{uv}=1-d_{uv}\geq 0.3=\Omega(1)$, we need to show that the total number
of cut edges is bounded by OPT, i.e., $\sum_{u\in V}|E_{u}|=O(\textsf{OPT}).$
We let $V_{u}=\\{v:(u,v)\in E_{u}\\}$, so our goal is equivalent to showing
that $\sum_{u\in V}|V_{u}|=O(\textsf{OPT}).$ The definition of $V_{u}$ is the
same as $R^{\prime}_{1}(u)$ in the proof of the previous lemma, but
$R_{1}^{\prime}(u)$ was only defined for $u\in R_{1}$.

We will charge the value of $\sum_{u\in V}|V_{u}|$ to disagreements in
$\mathcal{C}$. We use $y(u)$ to denote the number of disagreements incident to
$u$ with respect to $\mathcal{C}$.

Fix a vertex $u$. We consider several cases based on the clustering
$\mathcal{C}$.

##### Case 1:

_At least a 0.15 fraction of $N_{u}^{+}$ is in clusters other than $C(u)$._
Let $V^{1}$ be the vertices of $V$ in this case. For any such $u\in V^{1}$,
there are at least $0.15\cdot\Delta_{u}$ disagreements incident to $u$ in
$\mathcal{C}$, so $0.15\cdot\Delta_{u}\leq y(u).$ Combining this with the fact
that $|V_{u}|\leq\frac{10}{3}\cdot\Delta_{u}$, we see that

$|V_{u}|\leq\frac{10}{3}\cdot\Delta_{u}\leq\frac{200}{9}\cdot y(u).$

Summing over all $u\in V^{1}$, we see that

$\boxed{\sum_{u\in V^{1}}|V_{u}|\leq\frac{200}{9}\cdot\sum_{u\in
V}y(u)=\frac{200}{9}\cdot\textsf{OPT}.}$

##### Case 2:

_At least a 0.85 fraction of $N_{u}^{+}$ is in $C(u)$._
Let $V^{2}$ be the vertices of $V$ in this case. For any such $u\in V^{2}$, we
will show that for every $v\in V_{u}$, there is large overlap between $C(u)$,
$N_{u}^{+}$, and $N_{v}^{+}$. Proposition 1 will help us as we further refine
Case 2 into two settings:

Case 2a: _At least 0.85 fraction of $N_{u}^{+}$ is in $C(u)$, and there are at
least $\Delta_{u}$ negative edges incident to $u$ with both endpoints in
$C(u)$._
Let $V^{2a}$ be the vertices of $V^{2}$ in this case. Since these negative
edges are disagreements, we may charge $|V_{u}|$ to $y(u)$:

$\boxed{\sum_{u\in V^{2a}}|V_{u}|\leq\frac{10}{3}\cdot\sum_{u\in
V}\Delta_{u}\leq\frac{10}{3}\cdot\sum_{u}y(u)=\frac{10}{3}\cdot\textsf{OPT}.}$

Case 2b: _At least 0.85 fraction of $N_{u}^{+}$ is in $C(u)$, and $|C(u)|\leq
2\cdot\Delta_{u}$._
Observe Cases 2a and 2b cover the full range of Case 2. This is because we can
write $|C(u)|=|C(u)\cap N_{u}^{+}|+|C(u)\cap N_{u}^{-}|$, and if there are at
_most_ $\Delta_{u}$ negative edges incident to $u$ with both endpoints in
$C(u)$, this is equivalent to saying $|C(u)\cap N_{u}^{-}|\leq\Delta_{u}$. So,
both $|C(u)\cap N_{u}^{+}|$ and $|C(u)\cap N_{u}^{-}|$ are upper bounded by
$\Delta_{u}$ (since $\Delta_{u}=|N_{u}^{+}|$).

Let $V^{2b}$ be the vertices of $V^{2}$ in this case. Let
$N_{u,v}:=N_{v}^{+}\cap N_{u}^{+}\cap C(u)$. We know from Proposition 1 (for
$v\in R_{1}(u)^{\prime}$ and using the assumption bringing us into Case 2)
that $|N_{u,v}|\geq 0.15\cdot\Delta_{u}$. Observe that for $v\in
V_{u}\subseteq N_{u}^{-}\cap\overline{C(u)}$ and $w\in N_{u,v}$, the positive
edge $(w,v)$ is a disagreement.

Fix $w\in N_{u}^{+}\cap C(u)$ and $u\in V^{2b}$. Define
$\varphi(u,w)=|V_{u}\cap N_{w}^{+}|$. We say that $w$ dispenses
$\varphi(u,w)/|C(u)|$ charge to $u$. We would like to show that each $u\in
V^{2b}$ receives $\Omega(|V_{u}|)$ charge, and that each $w$ dispenses at most
$y(w)$ charge. By double counting,

$\sum_{w\in N_{u}^{+}\cap C(u)}\varphi(u,w)\geq|V_{u}|\cdot 0.15\Delta_{u}$

where we have used that $\varphi(u,w)$ is equal to the number of $v\in V_{u}$
such that $w\in N_{u,v}$, and we know that $|N_{u,v}|$ is at least
$0.15\Delta_{u}$. So, the total amount of charge that $u\in V^{2b}$ receives
is

$\sum_{w\in N_{u}^{+}\cap C(u)}\frac{\varphi(u,w)}{|C(u)|}\geq|V_{u}|\cdot
0.15\Delta_{u}/|C(u)|\geq 3/40\cdot|V_{u}|$

since $|C(u)|\leq 2\Delta_{u}$ by assumption of the case.

Now we need to upper bound the amount of charge that each $w\in V$ dispenses
in total. Note that $\varphi(u,w)\leq y(w)$, and $w$ only dispenses to
vertices $u\in C(w)\cap N_{w}^{+}$. Further, $C(u)=C(w)$. So $w$ dispenses at
most $|C(w)|\cdot y(w)/|C(u)|=y(w)$ charge in total. Putting everything
together:

$\displaystyle\sum_{w\in V}y(w)$ $\displaystyle\geq\text{total charge
dispensed}$ $\displaystyle\geq\sum_{u\in V^{2b}}\sum_{w\in N_{u}^{+}\cap
C(u)}\frac{\varphi(u,w)}{|C(u)|}\geq\sum_{u\in
V^{2b}}\frac{3}{40}\cdot|V_{u}|.$

So in all,

$\boxed{\sum_{u\in V^{2b}}|V_{u}|\leq\frac{40}{3}\cdot\sum_{w\in
V}y(w)=\frac{40}{3}\cdot\textsf{OPT}.}$

This concludes the bounding of the fractional cost of the negative edges, and
our constant in the approximation factor is $1+200/9+10/3+40/3<40$ (adding
together the boxed upper bounds).

∎

##  Appendix D KMZ Rounding Algorithm and Run-time

We construct a fractional solution with our adjusted correlation metric
(recall we use this in place of an LP solution), and then input this solution
to a rounding algorithm by Kalhan, Makarychev, and Zhou KMZ19.

First, we set up some notation for the rounding algorithm, mainly following
the example set by Kalhan, Makarychev, and Zhou. Let the ball of radius
$\rho$, with respect to the distance defined by any semi-metric $z$ on $V$,
around vertex $u\in V$ be denoted $\textsf{Ball}(u,\rho)=\\{v\in V\mid
z_{uv}\leq\rho\\}$. The algorithm is iterative, and continues to find new
clusters until every vertex is clustered. Let the set of unclustered vertices
at time $t$ be denoted by $V_{t}\subseteq V$. The cluster center in $V_{t}$ is
the vertex maximizing the quantity

$L_{t}(u)=\sum_{v\in\textsf{Ball}(u,r)\cap V_{t}}(r-z_{uv})$

for $r$ a parameter input to the algorithm. Note that when $L_{t}$ is large,
vertices in $\textsf{Ball}(u,r)\cap V_{t}$ are closely clustered together.

######  Algorithm 1.

[Rounding algorithm]

Input: Semi-metric $z$ on $V$.

Output: Clustering $\mathcal{C}$.

  1. 1.

Let $V_{0}=V$, $r=1/5$, $t=0$.

  2. 2.

while ($V_{t}\neq\emptyset$)

     * •

Find $u^{*}_{t}=\arg\max_{u\in V_{t}}L_{t}(u)=\arg\max_{u\in
V_{t}}\sum_{v\in\text{Ball}(u,r)\cap V_{t}}{r-z_{uv}}$.

     * •

Create ${C_{t}=\text{Ball}(u^{*}_{t},2r)\cap V_{t}}$.

     * •

Set $V_{t+1}=V_{t}\setminus C_{t}$ and $t=t+1$.

  3. 3.

Return ${\mathcal{C}=(C_{0},\dots,C_{t-1})}$.

We define $\textsf{LP}(u,v)$ to be $(u,v)$’s cost to LP 2.2 in the objective,
i.e., $x_{uv}=\textsf{LP}(u,v)$ for $(u,v)\in E^{+}$ and
$x_{uv}=1-\textsf{LP}(u,v)$ if $(u,v)\in E^{-}$. Similarly, we define a cost
for each edge with respect to Algorithm 1,
$\textsf{ALG}(u,v)=\mathds{1}((u,v)\text{ is a disagreement})$. Then summing
over all edges incident to vertex $u$, we obtain the disagreements to each
vertex, $\textsf{ALG}(u)=\sum_{v\in V}\textsf{ALG}(u,v)$.

The technical work of Kalhan, Makarychev, and Zhou KMZ19 is in showing that

$\textsf{ALG}(u)=\sum_{v\in V}\textsf{ALG}(u,v)\leq 5\cdot\sum_{v\in
V}\textsf{LP}(u,v)=5y(u).$ (6)

Davies, Moseley, and Newman DMN23 discuss the run-time of Algorithm 1 (see
Appendix A in their paper). The rounding algorithm has run-time $O(n^{2})$ for
general graphs, and the full run-time of the KMZ algorithm is dominated by the
time to solve the LP.