# Multilayer Correlation Clustering

Atsushi Miyauchi
CENTAI Institute
<EMAIL_ADDRESS>Florian Adriaens
University of Helsinki
<EMAIL_ADDRESS>Francesco Bonchi
CENTAI Institute & Eurecat
<EMAIL_ADDRESS>Nikolaj Tatti
University of Helsinki
<EMAIL_ADDRESS>
###### Abstract

Correlation Clustering, introduced by Bansal et al. (FOCS ’02), is an elegant
optimization model that formulates clustering of objects based on their
similarity information. In the model, we are given a set $V$ of $n$ elements,
where each pair of elements labeled either ‘$+$’ (representing that they are
similar) or ‘$-$’ (representing that they are dissimilar) together with a
nonnegative weight quantifying the degree of similarity/dissimilarity. The
goal is to find a clustering of $V$ that minimizes the so-called
disagreements, i.e., the sum of weights of misclassified pairs in terms of the
given similarity information.

In this paper, we establish Multilayer Correlation Clustering, a novel
generalization of Correlation Clustering to the multilayer setting. In this
model, we are given a series of inputs of Correlation Clustering (called
layers) over the common set $V$. The goal is then to find a clustering of $V$
that minimizes the $\ell_{p}$-norm ($p\geq 1$) of the disagreements vector,
which is defined as the vector (with dimension equal to the number of layers),
each element of which represents the disagreements of the clustering on the
corresponding layer. For this generalization, we first design an $O(L\log
n)$-approximation algorithm, where $L$ is the number of layers, based on the
well-known region growing technique. We then study an important special case
of our problem, namely the problem with the probability constraint, where each
pair of elements in $V$ has both labels ‘$+$’ and ‘$-$’ but the sum of weights
of both labels equals $1$. For this case, we first give an
$(\alpha+2)$-approximation algorithm, where $\alpha$ is any possible
approximation ratio for the single-layer counterpart. For instance, we can
take $\alpha=2.5$ in general (Ailon et al., JACM ’08) and
$\alpha=1.73+\epsilon$ for the unweighted case (Cohen-Addad et al., FOCS ’23).
Furthermore, we design a $4$-approximation algorithm, which improves the above
approximation ratio of $\alpha+2=4.5$ for the general probability-constraint
case. Computational experiments using real-world datasets demonstrate the
effectiveness of our proposed algorithms.

##  1 Introduction

Clustering objects based on the information of their similarity is a
fundamental task in machine learning. _Correlation Clustering_ , introduced in
the seminal paper by Bansal et al. [6, 7], is an elegant optimization model
that mathematically formulates this task. In the model, we are given a set $V$
of $n$ elements, where each pair of elements is labeled either ‘$+$’
(representing that they are similar) or ‘$-$’ (representing that they are
dissimilar) together with a nonnegative weight representing the degree of
similarity/dissimilarity. In general, the goal of Correlation Clustering is to
find a clustering of $V$ that is consistent with the given similarity
information as much as possible. The (in)consistency of a clustering of $V$
can be measured by the so-called _disagreements_ , which is defined as the sum
of weights of misclassified pairs, i.e., pairs with ‘$+$’ label across
clusters and pairs with ‘$-$’ label within the same cluster. The problem of
finding a clustering of $V$ that minimizes the disagreements is called
MinDisagree.

It is known that MinDisagree is not only NP-hard [6] but also APX-hard even if
we consider the unweighted case (i.e., the case where the weights are all
equal to $1$) [16]. A large body of work has been devoted to designing
polynomial-time approximation algorithms for the problem. For the general
weighted case, Charikar et al. [16] and Demaine et al. [25] independently
proposed $O(\log n)$-approximation algorithms, using the well-known _region
growing_ technique [29]. The approximation ratio of $O(\log n)$ is still the
state-of-the-art, and it is also known that improving it is at least as hard
as improving the $O(\log n)$-approximation for Minimum Multicut [29], which is
one of the major open problems in theoretical computer science. For the
unweighted case, Bansal et al. [6] presented the first constant-factor
approximation algorithm, which has been improved by a series of works so far
[16, 5, 17, 20, 19]. Notably, the current-best approximation ratio for the
unweighted case is $1.73+\epsilon$ for any $\epsilon>0$, which was very
recently given by Cohen-Addad et al. [19]. For more details, including
approximation algorithms for other special cases or even generalizations, see
Section 2.

###  1.1 Our contribution

In this study, we establish _Multilayer Correlation Clustering_ , a novel
generalization of Correlation Clustering to the multilayer setting. In the
model, we are given a series of inputs of Correlation Clustering (called
_layers_) over the common set $V$ of $n$ elements. The goal is then to find a
clustering of $V$ that is consistent as much as possible with _all_ layers. To
quantify the (in)consistency of a clustering over layers, we introduce the
concept of _disagreements vector_ (with dimension equal to the number of
layers) of a clustering, each element of which represents the disagreements of
the clustering on the corresponding layer. Using the $\ell_{p}$-norm ($p\geq
1$) of this vector, we can quantify the (in)consistency of the given
clustering in a variety of regimes. In particular, if we set $p=1$, it simply
quantifies the sum of disagreements over all layers, whereas if we set
$p=\infty$, it quantifies the maximal disagreements over the layers. For
$p\geq 1$, our problem aims to find a clustering of $V$ that minimizes the
$\ell_{p}$-norm of the disagreements vector. Obviously the problem is a
generalization of MinDisagree.

Multilayer Correlation Clustering is highly motivated by real-world scenarios.
For example, suppose that we want to find a clustering of users of
$\mathbb{X}$ (previously known as Twitter) using their similarity information.
In this case, various types of similarity can be defined through analysis of
users’ tweets and observations of different types of connections among users
such as follower–followee relations, retweets, and mentions. In the original
framework of Correlation Clustering, we need to deal with that information one
by one and manage to aggregate resulting clusterings. On the other hand,
Multilayer Correlation Clustering enables us to handle that information
simultaneously, directly producing a clustering that is consistent (as much as
possible) with all types of information. As another example scenario, suppose
that we analyze brain networks arising in neuroscience. In a brain network,
nodes correspond to small regions of a brain, and edges usually represent
similarity relations among them. However, it is often the case that the edge
set is not determined uniquely; indeed, there would be at least two types of
similarity based on the structural connectivity and the functional
connectivity (e.g., co-activation) among the small pieces of a brain.
Obviously, Multilayer Correlation Clustering can again find its advantage in
this context. Furthermore, in both of the above scenarios, the similarity
information can be time-dependent and/or uncertain, naturally leading to the
multilayer setting, even if we focus on a specific type of similarity.

For this novel, well-motivated generalization, we present a variety of
algorithmic results. We first design a polynomial-time $O(L\log
n)$-approximation algorithm, where $L$ is the number of layers. Our algorithm
is a generalization of the $O(\log n)$-approximation algorithms for
MinDisagree [16, 25] and thus employs the region growing technique [29]. Our
algorithm first solves a convex programming relaxation of the problem,
particularly a linear programming (LP) relaxation for the case of $p=\infty$.
An important fact is that any feasible solution (and thus any optimal
solution) to the relaxation gives a pseudometric over $V$. Then, the algorithm
iteratively constructs a cluster (and removes it from $V$ as a part of the
output), using the region growing technique based on the pseudometric
computed, until all elements are clustered. Specifically, in each iteration,
the algorithm takes an arbitrary element in $V$ and constructs a ball of
center being that element together with a carefully-selected radius. In the
computation of the radius, the algorithm takes into account the similarity
information over all layers simultaneously, which is a key factor for proving
our approximation ratio of $O(L\log n)$.

We then study an important special case of our problem, namely the problem
with the _probability constraint_. To explain the problem, we briefly review
MinDisagree with the probability constraint [6]. In this model, each pair of
elements in $V$ has _both_ ‘$+$’ and ‘$-$’ labels, each of which is associated
with a nonnegative weight in the interval $[0,1]$. The probability constraint
assures that for each pair of elements, the sum of weights of ‘$+$’ and ‘$-$’
labels is equal to $1$. At first glance, the problem might look tricky, but it
is indeed a quite reasonable setting. According to the definition of
disagreements, for each pair of elements, if they are assigned to the same
cluster, the weight of ‘$-$’ label is charged, whereas if they are assigned to
different clusters, the weight of ‘$+$’ label (i.e., $1$ minus the weight of
‘$-$’ label) is charged. Therefore, we can see that for each pair of elements,
there is essentially only one weight in the interval $[0,1]$ representing the
degree of dissimilarity of them. In particular, MinDisagree of the unweighted
case is a special case of MinDisagree with the probability constraint. Our
problem is a multilayer generalization of MinDisagree with the probability
constraint.

For this problem, we propose several constant-factor approximation algorithms.
We first give a polynomial-time $(\alpha+2)$-approximation algorithm, where
$\alpha$ is any possible approximation ratio for MinDisagree with the
probability constraint or any of its special cases if we consider the
corresponding special case of our problem. For instance, we can take
$\alpha=2.5$ in general [5], $\alpha=1.73+\epsilon$ for the unweighted case
[19], and $\alpha=1.5$ for the case where the weights of ‘$-$’ labels satisfy
the triangle inequality constraint (see Section 3) [17]. In the design of our
algorithm, we introduce a novel optimization problem in a metric space. Let
$(X,d)$ be a metric space and $p\geq 1$. In the problem, given
$x_{1},\dots,x_{L}\in X$ and a candidate set $F\subseteq X$, we are asked to
find $x\in F$ that minimizes
$\left(\sum_{\ell\in[L]}d(x,x_{\ell})^{p}\right)^{1/p}$ if $p<\infty$ and
$\max_{\ell\in[L]}d(x,x_{\ell})$ if $p=\infty$. Intuitively, the problem aims
to find the most _representative_ candidate of the given points
$x_{1},\dots,x_{L}$ in a metric space. We prove that there is a polynomial-
time approximation-preserving reduction from our problem to this problem. To
this end, a key fact is that each layer of our input (i.e., an input of
MinDisagree with the probability constraint) and any clustering of $V$, which
might look different objects, can be dealt with in a unified metric space, by
setting an appropriate metric $d$. Following this reduction, we design an
algorithm for the metric-space problem, producing our algorithm that is
applicable to a variety of cases. We wish to note that our resulting algorithm
is based on a single-layer analysis, meaning that it solves MinDisagree on
each layer and just outputs the best clustering among those seen in the
process; however, we believe that the above metric-space problem and the
algorithm that we design for the problem may be of independent interest.

Furthermore, we design a $4$-approximation algorithm for the general
probability-constraint case, which improves the above approximation ratio of
$\alpha+2=4.5$. Unlike the above, this algorithm constructs a clustering using
the information collected by all layers simultaneously. Therefore, although we
have no better approximation ratio for the unweighted case and the triangle
inequality constraint case, the algorithm is expected to perform better in
practice than the above even for those special cases. Specifically, the
algorithm first solves a convex programming relaxation as in the
aforementioned $O(L\log n)$-approximation algorithm for the general weighted
case, and then constructs a clustering, using some thresholding rule that is
simpler than the region growing technique. Our algorithm is a generalization
of the $4$-approximation algorithm for MinDisagree of the unweighted case,
designed by Charikar et al. [16]. Our result implies that their algorithm can
be extended to the probability constraint case, which has yet to be mentioned
before. Although some approximation ratios better than $4$ are known for the
unweighted case [5, 17, 20, 19], thanks to its simplicity and extendability,
the algorithm by Charikar et al. [16] has been generalized to various settings
of the unweighted case (see Section 2). Our analysis implies that those
results may be further generalized from the unweighted case to the probability
constraint case.

Finally we conduct thorough experiments using a variety of real-world datasets
to evaluate the performance of our proposed algorithms in terms of both
solution quality and running time. We confirm that our algorithms outperform
baseline methods for both Problem 1 of the general weighted case and Problem 1
with the probability constraint.

Our contribution can be summarized as follows:

  * •

We formulate Multilayer Correlation Clustering, a novel generalization of
Correlation Clustering to the multilayer setting (Section 3).

  * •

We design an $O(L\log n)$-approximation algorithm for Problem 1 (Section 4).

  * •

For Problem 1 with the probability constraint, we devise an
$(\alpha+2)$-approximation algorithm, where $\alpha$ is any possible
approximation ratio for MinDisagree with the probability constraint or any of
its special cases if we consider the corresponding special case of our
problem. Moreover, we design a $4$-approximation algorithm, which improves the
above approximation ratio of $\alpha+2=4.5$ for the general case (Section 5).

  * •

We perform thorough computational experiments using various real-world
datasets and demonstrate the practical effectiveness of our proposed
algorithms (Section 6).

##  2 Related Work

Our work focuses on Correlation Clustering, with a particular interest in the
approximability of our generalization, i.e., Multilayer Correlation
Clustering, which is strongly related to the emerging research topic in
network science called multilayer-network analysis.

Special cases of MinDisagree. For MinDisagree of the unweighted case, Bansal
et al. [6, 7] gave the first constant-factor approximation algorithm with the
approximation ratio of 17,429. Then the approximation ratio has been improved
by a series of works. Charikar et al. [16] designed a $4$-approximation
algorithm. The algorithm first solves an LP relaxation of the problem to
obtain a pseudometric over the elements. Then the algorithm iteratively
constructs a cluster, using a simple thresholding rule based on the
pseudometric computed. Ailon et al. [5] gave a purely-combinatorial randomized
$3$-approximation algorithm, which they referred to as KwikCluster. The
algorithm is quite simple; it takes an element, called the _pivot_ , uniformly
at random from the remaining elements and constructs a cluster by collecting
all remaining elements that are similar to the pivot. The algorithm removes
the cluster and repeats the process until the elements are fully clustered.
The authors also proved that a simple randomized construction of the clusters
based on the pseudometric computed by the LP relaxation improves the
approximation ratio from $3$ to $2.5$. Later Chawla et al. [17] demonstrated
that a more sophisticated randomized construction of the clusters achieves a
$2.06$-approximation [17], which almost matches the integrality gap of $2$ of
the LP relaxation [16]. In a recent breakthrough, Cohen-Addad et al. [20]
designed a $(1.994+\epsilon)$-approximation algorithm for any $\epsilon>0$,
using a semidefinite programming relaxation of the problem, particularly the
Sherali–Adams hierarchy. Very recently, Cohen-Addad et al. [19] further
improved the approximation ratio to $1.73+\epsilon$ by inventing a novel
preprocessing algorithm.

For MinDisagree with the probability constraint, Bansal et al. [6, 7] provided
an approximation-preserving reduction from the problem to MinDisagree of the
unweighted case. Specifically, the authors proved that any
$\alpha$-approximation algorithm for MinDisagree of the unweighted case yields
a $(2\alpha+1)$-approximation algorithm for MinDisagree with the probability
constraint. Ailon et al. [5] demonstrated that the counterparts of KwikCluster
and that combined with the pseudometric computed by the LP relaxation achieve
a $5$-approximation and a $2.5$-approximation, respectively, both of which
improved the $9$-approximation based on the above reduction with the
$4$-approximation algorithm for MinDisagree of the unweighted case by Charikar
et al. [16]. In particular, the approximation ratio of $2.5$ is still known to
be the state-of-the-art. It is also known that in the case where the weights
of ‘$-$’ labels satisfy the triangle inequality constraint additionally, the
approximation ratio can be improved. Indeed, Ailon et al. [5] proved that
their above algorithms achieve a $2$-approximation, and later Chawla et al.
[17] improved it to $1.5$.

Gionis et al. [30] studied the problem called _Clustering Aggregation_ , which
is highly related to MinDisagree. In the problem, we are given $L$ clusterings
of the common set $V$, and the goal is to find a clustering of $V$ that is
consistent with the given clusterings as much as possible. The (in)consistency
is measured by the sum of distances between the output clustering and the
given $L$ clusterings, where the distance is defined as the number of pairs of
elements that are clustered in the opposite way. Gionis et al. [30] proved
that Clustering Aggregation is a special case of MinDisagree with the
probability constraint and the triangle inequality constraint. We can also
directly see that Clustering Aggregation is a quite special case of Multilayer
Correlation Clustering of the unweighted case, where each layer already
represents a clustering and the parameter $p$ of the $\ell_{p}$-norm is set to
$1$. The authors also demonstrated that picking up the best clustering among
the given $L$ clusterings gives a $2(1-1/L)$-approximation while an algorithm
similar to the $4$-approximation algorithm for MinDisagree of the unweighted
case, designed by Charikar et al. [16], achieves a $3$-approximation. Finally,
it is worth noting that Clustering Aggregation has also been considered under
a variety of different names such as Clustering Ensemble and Consensus
Clustering [26, 47].

Generalizations of MinDisagree. Here we review a selection of generalizations
that are fairly related to our work among the many available. For a broader
survey, we refer the readers to the recent book [12] and references therein.

The most related would be Multi-Chromatic Correlation Clustering, introduced
by Bonchi et al. [13], as a further generalization of Chromatic Correlation
Clustering [14]. Let $V$ be a set of $n$ elements. Let $L$ be a set of colors.
Each pair of elements in $V$ is associated with a subset of $L$, meaning that
the endpoints are similar in the sense of those colors. The goal is to find a
clustering of $V$ and an assignment of each cluster to a subset of $L$ that is
consistent as much as possible with the given similarity information. The
(in)consistency of a clustering is evaluated as follows: For each pair within
a cluster, a distance between the color subsets of the pair and the cluster is
charged, while for each pair across clusters, a distance between the color
subset of the pair and the emptyset is charged. Varying the definition of the
distance, a number of concrete models can be obtained. It is easy to see that
the input of Multi-Chromatic Correlation Clustering is essentially the same as
that of our problem of the unweighted case. A substantial difference between
those two problems is that Multi-Chromatic Correlation Clustering asks to
specify the colors (i.e., layers in our case) of each cluster for which the
cluster is supposed to be valid. Our problem does not require such an effort,
where all clusters are supposed to be valid on all layers. Our problem has two
concrete advantages over Multi-Chromatic Correlation Clustering. First, the
objective function is more intuitive but can deal with a complex relations
among the (in)consistency over all layers. Indeed, our objective function is
the $\ell_{p}$-norm of the disagreements vector, which is more easily
interpretable; for example, if we set $p=\infty$, we can minimize the maximal
disagreements over all layers. On the other hand, as Multi-Chromatic
Correlation Clustering does not evaluate the inconsistency on each layer
independently, it cannot involve this type of objective. Second, our problem
is capable of the general weighted case, while Multi-Chromatic Correlation
Clustering is defined only for the unweighted case and the way to generalize
it to the weighted case is not trivial. For Multi-Chromatic Correlation
Clustering, Bonchi et al. [13] designed an approximation algorithm with an
approximation ratio proportional to the product of $|L|$ and the maximum
degree of the input (when interpreting it as a graph). Recently, Klodt et al.
[39] introduced a different yet similar generalization of Chromatic
Correlation Clustering to the multi-chromatic case and devised a
$3$-approximation algorithm based on KwikCluster.

Multilayer Correlation Clustering can be seen as Correlation Clustering with
_fairness_ considerations. Indeed, supposing that the similarity information
of each layer is given by an agent (e.g., a crowd worker), we see that the
problem tries not to abandon any similarity information given by the agents.
From a fairness perspective, Puleo and Milenkovic [43, 44] initiated the study
of local objectives for MinDisagree of the unweighted case. In this model, the
disagreements of a clustering are quantified locally rather than globally, at
the level of single elements. Specifically, they considered a disagreements
vector (with dimension equal to the number of elements), where $i$-th element
represents the disagreements incident to the corresponding element $i\in V$.
The goal is then to minimize the $\ell_{p}$-norm ($p\geq 1$) of the
disagreements vector. If we set $p=1$, the problem reduces to MinDisagree of
the unweighted case, whereas if we set $p=\infty$, the problem aims to
minimize the maximal disagreements over the elements. The authors proved that
the model with $p=\infty$ is NP-hard and designed a $48$-approximation
algorithm for any $p\geq 1$ by extending the $4$-approximation algorithm for
MinDisagree of the unweighted case, designed by Charikar et al. [16]. Charikar
et al. [15] then improved the approximation ratio to $7$ by inventing a
different rounding algorithm. The contribution of Charikar et al. [15] is not
limited to the unweighted case; they also studied the above model with
$p=\infty$ of the general weighted case and designed an
$O(\sqrt{n})$-approximation algorithm. Later Kalhan et al. [37] improved the
above approximation ratio of $7$ to $5$, and designed an
$O(n^{\frac{1}{2}-\frac{1}{2p}}\log^{\frac{1}{2}+\frac{1}{2p}}n)$-approximation
algorithm for any $p\geq 1$ of the general weighted case, matching the
current-best approximation ratio of $O(\log n)$ for MinDisagree of the general
weighted case (i.e., the above model with $p=1$) [16, 25], up to a logarithmic
factor. Very recently, Davies et al. [21] gave a purely-combinatorial
$O(n^{\omega})$-time $40$-approximation algorithm for $p=\infty$ of the
unweighted case, where $\omega$ is the exponent of matrix multiplication,
while Heidrich et al. [32] improved the above approximation ratio of $5$ by
Kalhan et al. [37] to $4$ for $p=\infty$. Ahmadi et al. [2] studied the
cluster-wise counterpart of the above model with $p=\infty$ (of the general
weighted case), where the goal is to find a clustering of $V$ that minimizes
the maximal disagreements over the clusters. The authors presented an $O(\log
n)$-approximation algorithm together with an $O(r^{2})$-approximation
algorithm for the $K_{r,r}$-free graphs. Later Kalhan et al. [37]
significantly improved these approximation ratios to $2+\epsilon$ for any
$\epsilon>0$.

Another type of fairness has been considered for Correlation Clustering.
Ahmadian et al. [3] initiated the study of Fair Correlation Clustering (of the
unweighted case), where each element is associated with a color, and each
cluster of the output is required to be not over-represented by any color,
meaning that the fraction of elements with any single color has to be upper
bounded by a specified value. For the model, the authors designed a
$256$-approximation algorithm, based on the notion called fairlet
decomposition. Ahmadi et al. [1] independently studied a similar model of Fair
Correlation Clustering, where the distribution of colors in each cluster has
to be the same as that of the entire set. In particular, for the case of two
colors that have the same number of elements in the entire set, the authors
proposed a $(3\alpha+4)$-approximation algorithm, where $\alpha$ is any known
approximation ratio for MinDisagree of the unweighted case. Friggstad and
Mousavi [27] then gave an approximation ratio of $6.18$, which cannot be
achieved by the above $3\alpha+4$. The authors also studied the model with the
aforementioned local objective for $p=\infty$ and designed a constant-factor
approximation algorithm. Schwartz and Zats [46] proved that the model of
Ahmadi et al. [1] of the general weighted case has no finite approximation
ratio, unless $\text{P}=\text{NP}$. Very recently, Ahmadian et al. [4]
substantially generalized the above models and designed an approximation
algorithm that has constant-factor approximation ratios for some useful
special cases.

Multilayer Correlation Clustering can also be seen as Correlation Clustering
with the _uncertainty_ of input by interpreting each layer as a possible
scenario of the similarity information of the elements. Most works on
Correlation Clustering with uncertainty assume the existence of the ground-
truth clustering of $V$ and aim to recover it, based only on its noisy
observations. In the seminal paper by Bansal et al. [7], this type of problem
had already been considered, while Joachims and Hopcroft [36] gave the first
formal analysis of the problem. Later, a variety of problem settings have been
introduced in a series of works [18, 42, 41]. Very recently, Kuroki et al.
[40] considered another type of problem, which aims to perform as few queries
as possible to an oracle that returns a noisy sample of the similarity between
two elements in $V$, to obtain a clustering of $V$ that minimizes the
disagreements. Specifically, they introduced two novel online-learning
problems rooted in the paradigm of combinatorial multi-armed bandits, and
designed algorithms that combine KwikCluster with adaptive sampling
strategies.

Multilayer-network analysis. Correlation Clustering can be seen as a general
clustering model on networks. A _multilayer network_ is a generalization of
the ordinary network, where we have a number of edge sets (i.e., layers),
which encode different types of connections and/or time-dependent connections
over the common set of vertices. Our problem, Multilayer Correlation
Clustering, can then be viewed as a generalization of Correlation Clustering
to multilayer networks. Recently, multilayer networks have attracted much
attention, and many network-analysis primitives have been generalized from the
ordinary (i.e., single-layer) networks to multilayer networks. Examples
include community detection [9, 22, 33, 48], dense subgraph discovery [28, 35,
38], link prediction [22, 34], analyzing spreading processes [23, 45], and
identifying central vertices [8, 24].

##  3 Problem Formulation

In this section, we formally introduce our problem. Let $V$ be a set of $n$
elements. Let $E$ be the set of unordered pairs of distinct elements in $V$,
i.e., $E=\\{\\{u,v\\}:u,v\in V,\,u\neq v\\}$. Let $L$ be a positive integer,
representing the number of layers. For each $\ell\in[L]$, let
$w^{+}_{\ell}\colon E\rightarrow\mathbb{R}_{\geq 0}$ and $w^{-}_{\ell}\colon
E\rightarrow\mathbb{R}_{\geq 0}$ be the weight functions for ‘$+$’ and ‘$-$’
labels, respectively, on that layer.111Note that to deal with the probability
constraint case in a unified manner, we assume that each pair of elements have
_both_ ‘$+$’ and ‘$-$’ labels. For simplicity, we define
$w^{+}_{\ell}(u,v)=w^{+}_{\ell}(\\{u,v\\})$ and
$w^{-}_{\ell}(u,v)=w^{-}_{\ell}(\\{u,v\\})$ for $\ell\in[L]$ and $\\{u,v\\}\in
E$. Let $\mathcal{C}$ be a clustering (i.e., a partition) of $V$, that is,
$\mathcal{C}=\\{C_{1},\dots,C_{t}\\}$ such that $\bigcup_{i\in[t]}C_{i}=V$ and
$C_{i}\cap C_{j}=\emptyset$ for $i,j\in[t]$ with $i\neq j$. For $v\in V$, we
denote by $\mathcal{C}(v)$ the (unique) element (i.e., cluster) in
$\mathcal{C}$ to which $v$ belongs. Then, for $u,v\in V$,
$\mbox{1}\mbox{l}[\mathcal{C}(u)=\mathcal{C}(v)]=1$ if $u,v$ belong to the
same cluster and $\mbox{1}\mbox{l}[\mathcal{C}(u)\neq\mathcal{C}(v)]=0$
otherwise. The _disagreement_ of $\mathcal{C}$ on layer $\ell\in[L]$ is
defined as the sum of weights of misclassified labels on that layer, i.e.,

$\displaystyle\mathsf{Disagree}_{\ell}(\mathcal{C})=\sum_{\\{u,v\\}\in
E}\left(w^{+}_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}(u)\neq\mathcal{C}(v)]+w^{-}_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}(u)=\mathcal{C}(v)]\right).$

Then the _disagreements vector_ of $\mathcal{C}$ is defined as

$\displaystyle\mathbf{Disagree}(\mathcal{C})=(\mathsf{Disagree}_{\ell}(\mathcal{C}))_{\ell\in[L]}.$

We are now ready to formulate our problem:

######  Problem 1 (Multilayer Correlation Clustering).

Fix $p\in[1,\infty]$. Given $V$ and
$(w^{+}_{\ell},w^{-}_{\ell})_{\ell\in[L]}$, we are asked to find a clustering
$\mathcal{C}$ of $V$ that minimizes the $\ell_{p}$-norm of the disagreement
vector of $\mathcal{C}$, i.e.,

$\displaystyle\|\mathbf{Disagree}(\mathcal{C})\|_{p}=\begin{cases}\left(\sum_{\ell\in[L]}\mathsf{Disagree}_{\ell}(\mathcal{C})^{p}\right)^{1/p}&\textrm{if
}p<\infty,\\\
\max_{\ell\in[L]}\mathsf{Disagree}_{\ell}(\mathcal{C})&\textrm{if
}p=\infty.\end{cases}$

Obviously Problem 1 is a generalization of MinDisagree to the multilayer
setting. Varying the value of $p$, we can obtain a series of objective
functions that evaluate the (in)consistency of the given clustering in a
variety of regimes. If we set $p=1$, the problem just aims to minimize the sum
of disagreements over all layers. It is easy to see that this case can be
reduced to MinDisagree in an approximation-preserving manner; therefore, the
problem is $O(\log n)$-approximable [16, 25]. If we set $p=\infty$, the
problem aims to minimize the maximal disagreements over all layers, which is
an important special case we are particularly interested in.

Similarly to the case of MinDisagree, as long as we consider the most general
case that has no constraint on $w^{+}_{\ell},w^{-}_{\ell}$, we can assume
without loss of generality that at most one of $w^{+}_{\ell}(u,v)$ and
$w^{-}_{\ell}(u,v)$ is nonzero for any $\\{i,j\\}\in E$. Otherwise we can
transform the instance into another one that satisfies the above and is more
easily approximable (see Section 1.4 in Bonchi et al. [12] for details).
Following this, we can obtain a more intuitive representation of our problem
as follows: For each $\ell\in[L]$, introduce two mutually-disjoint sets
$E^{+}_{\ell}=\\{\\{u,v\\}\in E:w^{+}_{\ell}(u,v)>0\\}$ and
$E^{-}_{\ell}=\\{\\{u,v\\}\in E:w^{-}_{\ell}(u,v)>0\\}$, and define
$w_{\ell}\colon E^{+}_{\ell}\cup E^{-}_{\ell}\rightarrow\mathbb{R}_{>0}$ such
that $w_{\ell}(\\{u,v\\})=w^{+}_{\ell}(u,v)$ if $\\{u,v\\}\in E^{+}_{\ell}$
and $w_{\ell}(\\{u,v\\})=w^{-}_{\ell}(u,v)$ if $\\{u,v\\}\in E^{-}_{\ell}$.
Again we write $w_{\ell}(u,v)=w_{\ell}(\\{u,v\\})$ for $\ell\in[L]$ and
$\\{u,v\\}\in E^{+}_{\ell}\cup E^{-}_{\ell}$, for simplicity. Then we can
rewrite the disagreement of $\mathcal{C}$ on layer $\ell\in[L]$ as

$\displaystyle\mathsf{Disagree}_{\ell}(\mathcal{C})=\sum_{\\{u,v\\}\in
E^{+}_{\ell}}w_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}(u)\neq\mathcal{C}(v)]+\sum_{\\{u,v\\}\in
E^{-}_{\ell}}w_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}(u)=\mathcal{C}(v)],$

which will be used throughout Section 4.

An important special case of Problem 1 is that $w^{+}_{\ell},w^{-}_{\ell}$ for
every layer $\ell\in[L]$ satisfy the so-called _probability constraint_ ,
i.e., $w^{+}_{\ell}(u,v)+w^{-}_{\ell}(u,v)=1$ for any $\\{u,v\\}\in E$. Note
that the most fundamental special case, i.e., the unweighted case, is still
contained in this case, where $w^{-}_{\ell}(u,v)=1-w^{+}_{\ell}(u,v)=0$ or
$1$. Another special case, which we also handle in the present paper, is
Problem 1 with the probability constraint and the _triangle inequality
constraint_. The additional constraint, i.e., the triangle inequality
constraint, stipulates that on every layer $\ell\in[L]$,
$w^{-}_{\ell}(u,w)\leq w^{-}_{\ell}(u,v)+w^{-}_{\ell}(v,w)$ holds for any
distinct $u,v,w\in V$. It is easy to see that in the case of $p=1$, Problem 1
with the probability constraint (and the triangle inequality constraint) can
be reduced to MinDisagree with the probability constraint (and the triangle
inequality constraint) in an approximation-preserving manner. Indeed, simply
summing up the weights over all layers for each pair of elements and dividing
them by $L$, we can obtain an equivalent instance of MinDisagree with the
probability constraint (and the triangle inequality constraint). Therefore, we
see that the problem is still $2.5$-approximable [5] in the probability
constraint case and $1.5$-approximable [17] in the probability constraint and
triangle inequality constraint case. However, even if we consider the quite
special case, Problem 1 of the unweighted case, there is no trivial reduction
that can beat the above $2.5$-approximation.

##  4 Algorithm for Problem 1

In this section, we design an $O(L\log n)$-approximation algorithm for Problem
1. Our algorithm first solves a convex programming relaxation and then rounds
the fractional solution, using the region growing technique, to obtain a
clustering. As explained in Section 3, we assume without loss of generality
that at most one of $w^{+}_{\ell}(i,j)$ and $w^{-}_{\ell}(i,j)$ is nonzero for
each $\\{i,j\\}\in E$, and employ the latter representation of our problem
given there.

###  4.1 The proposed algorithm

We first present $0$–$1$ convex programming formulations for Problem 1. For
distinct $i,j\in V$, we introduce $0$–$1$ variables $x_{ij},x_{ji}$, both of
which take $0$ if $i,j$ belong to the same cluster and $1$ otherwise. Then, in
the case of $p<\infty$, Problem 1 can be formulated as follows:

minimize $\displaystyle\left(\sum_{\ell\in[L]}\left(\sum_{\\{i,j\\}\in
E^{+}_{\ell}}w_{\ell}(i,j)x_{ij}+\sum_{\\{i,j\\}\in
E^{-}_{\ell}}w_{\ell}(i,j)(1-x_{ij})\right)^{p}\right)^{1/p}$ subject to
$\displaystyle x_{ij}=x_{ji}\quad(\forall i,j\in V,\ i\neq j),$ $\displaystyle
x_{ik}\leq x_{ij}+x_{jk}\quad(\forall i,j,k\in V,\ i\neq j,\,j\neq k,\,k\neq
i),$ $\displaystyle x_{ij}\in\\{0,1\\}\quad(\forall i,j\in V,\ i\neq j).$

On the other hand, in the case of $p=\infty$, we have the following $0$–$1$ LP
formulation:

minimize $\displaystyle t$ subject to $\displaystyle\sum_{\\{i,j\\}\in
E^{+}_{\ell}}w_{\ell}(i,j)x_{ij}+\sum_{\\{i,j\\}\in
E^{-}_{\ell}}w_{\ell}(i,j)(1-x_{ij})\leq t\quad(\forall\ell\in[L]),$
$\displaystyle x_{ij}=x_{ji}\quad(\forall i,j\in V,\ i\neq j),$ $\displaystyle
x_{ik}\leq x_{ij}+x_{jk}\quad(\forall i,j,k\in V,\ i\neq j,\,j\neq k,\,k\neq
i),$ $\displaystyle x_{ij}\in\\{0,1\\}\quad(\forall i,j\in V,\ i\neq j).$

For the above formulations, by relaxing the constraints $x_{ij}\in\\{0,1\\}$
to $x_{ij}\in[0,1]$ for all distinct $i,j\in V$, we can obtain continuous
relaxations of Problem 1, which we refer to as (CV) and (LP), respectively.
Let $\bm{x}=(x_{ij})_{i,j\in V:\,i\neq j}$. It should be noted that (CV) is a
convex programming problem. Indeed, the objective function is convex, as it is
a vector composition of form
$f(g(\bm{x}))=f(g_{1}(\bm{x}),\dots,g_{L}(\bm{x}))$, where
$f\colon\mathbb{R}_{\geq 0}^{L}\rightarrow\mathbb{R}_{\geq 0}$ is an
$\ell_{p}$-norm of $p\geq 1$, which is convex and non-decreasing in each
argument, and $g_{\ell}\colon\mathbb{R}_{\geq
0}^{E}\rightarrow\mathbb{R}_{\geq 0}$ is linear and thus convex for every
$\ell\in[L]$; moreover, the set of feasible solutions is obviously convex.
Therefore, we can employ an appropriate method for convex programming such as
an interior-point method to solve the problem to arbitrary precision in
polynomial time. Throughout this paper, for the sake of simplicity, we suppose
that (CV) can be solved exactly in polynomial time. On the other hand, (LP) is
indeed an LP, and thus can be solved exactly in polynomial time. Let
$\mathrm{OPT}_{\mathrm{CV}}$ and $\mathrm{OPT}_{\mathrm{LP}}$ be the optimal
values of the above relaxations, respectively.

Our algorithm first solves an appropriate relaxation, (CV) or (LP), depending
on the value of $p$, and obtains its optimal solution
$\bm{x}^{*}=(x^{*}_{ij})_{i,j\in V:\,i\neq j}$. Then the algorithm introduces
$\overline{\bm{x}}^{*}=(x^{*}_{ij})_{i,j\in V}$ by setting $x^{*}_{ii}=0$ for
every $i\in V$. Obviously $\overline{\bm{x}}^{*}$ is a pseudometric over $V$,
i.e., a relaxed metric where a distance between distinct elements may be equal
to $0$. Based on this, the algorithm constructs a clustering in an iterative
manner. The algorithm initially has the entire set $V$. In each iteration, the
algorithm takes an arbitrary element called a _pivot_ in the current set and
constructs a cluster by collecting the pivot itself and the other elements
that are located at distance less than some carefully-chosen value from the
pivot. The algorithm removes the cluster from the current set and repeats the
process until it is left with the emptyset.

To describe the algorithm formally, we introduce some notations. Recall that
$\overline{\bm{x}}^{*}=(x^{*}_{ij})_{i,j\in V}$ is a pseudometric over $V$.
Let $\widehat{V}$ be an arbitrary subset of $V$. For $i\in\widehat{V}$ and
$r\geq 0$, we denote by $B_{\widehat{V}}(i,r)$ the open ball of center $i$ and
radius $r$ in $\widehat{V}$, i.e.,

$\displaystyle B_{\widehat{V}}(i,r)=\\{j\in\widehat{V}:x^{*}_{ij}<r\\}.$

For $B_{\widehat{V}}(i,r)$, we define its cut value
$\text{cut}_{(\widehat{V},\ell)}(B_{\widehat{V}}(i,r))$ within $\widehat{V}$
on layer $\ell\in[L]$ as the sum of weights of ‘$+$’ labels across
$B_{\widehat{V}}(i,r)$ and $\widehat{V}\setminus B_{\widehat{V}}(i,r)$ on
layer $\ell\in[L]$ , i.e.,

$\displaystyle\text{cut}_{(\widehat{V},\ell)}(B_{\widehat{V}}(i,r))=\sum_{\\{j,k\\}\in
E^{+}_{\ell}:\,j\in B_{\widehat{V}}(i,r)\land k\in\widehat{V}\setminus
B_{\widehat{V}}(i,r)}w_{\ell}(j,k).$

For $B_{\widehat{V}}(i,r)$, we define its volume
$\text{vol}_{(\widehat{V},\ell)}(B_{\widehat{V}}(i,r))$ within $\widehat{V}$
on layer $\ell\in[L]$ as

$\displaystyle\text{vol}_{(\widehat{V},\ell)}(B_{\widehat{V}}(i,r))=\frac{F_{\ell}}{n}+\sum_{\\{j,k\\}\in
E^{+}_{\ell}:\,j,k\in
B_{\widehat{V}}(i,r)}w_{\ell}(j,k)x^{*}_{jk}+\sum_{\\{j,k\\}\in
E^{+}_{\ell}:\,j\in B_{\widehat{V}}(i,r)\land k\in\widehat{V}\setminus
B_{\widehat{V}}(i,r)}w_{\ell}(j,k)(r-x^{*}_{ij}),$

where $F_{\ell}=\sum_{\\{j,k\\}\in E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}$.

Based on the above notations, the pseudocode of our algorithm is presented in
Algorithm 1. The feature of our algorithm can be found in the radius
selection: In the $t$-th iteration, the algorithm selects the radius
$r^{*}_{(t)}$ that minimizes the maximal ratio of the cut value to the volume
of the ball of the chosen pivot $i^{(t)}$ over all layers $\ell\in[L]$ with
$F_{\ell}\neq 0$.

Input: $V$, $(E^{+}_{\ell},E^{-}_{\ell})_{\ell\in[L]}$, and
$(w_{\ell})_{\ell\in[L]}$

Output: Clustering of $V$

1 Compute an optimal solution $\bm{x}^{*}=(x^{*}_{ij})_{i,j\in V:\,i\neq j}$
to (CV) if $p<\infty$ and (LP) if $p=\infty$;

2 Construct $\overline{\bm{x}}^{*}=(x^{*}_{ij})_{i,j\in V}$ by setting
$x^{*}_{ii}=0$ for every $i\in V$;

3 Take an arbitrary $c>2$;

4 $\mathcal{B}\leftarrow\emptyset$;

5 $V^{(1)}\leftarrow V$ and $t\leftarrow 1$;

6 while  _$V^{(t)}\neq\emptyset$_ do

7 Take an arbitrary pivot $i^{(t)}\in V^{(t)}$;

8 Compute $\displaystyle r^{*}_{(t)}\in\mathop{\rm
argmin}\left\\{\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\text{cut}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r))}{\text{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r))}\
:\ r\in(0,1/c]\right\\}$;

9
$\mathcal{B}\leftarrow\mathcal{B}\cup\\{B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})\\}$;

10 $V^{(t+1)}\leftarrow V^{(t)}\setminus B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})$;

11 $t\leftarrow t+1$;

12

13return _$\mathcal{B}$_ ;

Algorithm 1 $O(L\log n)$-approximation algorithm for Problem 1

###  4.2 Analysis of Algorithm 1

Here we prove that Algorithm 1 is a polynomial-time $O(L\log n)$-approximation
algorithm for Problem 1. To this end, we have the following key lemma,
verifying the effectiveness of the radius determined by the algorithm:

######  Lemma 1.

In Algorithm 1, for any $t=1,\dots,|\mathcal{B}|$, it holds that

$\displaystyle\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))}{\mathrm{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))}\leq
cL\log(n+1),$

and moreover, $B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})$ can be computed in polynomial
time.

###### Proof.

Fix $t\in\\{1,\dots,|\mathcal{B}|\\}$. For simplicity, for any $r\in[0,1/c]$,
we write $B_{V^{(t)}}(i^{(t)},r)=B(r)$, and moreover, for any $\ell\in[L]$,
$\text{cut}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r))=\text{cut}_{\ell}(r)$ and
$\text{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r))=\text{vol}_{\ell}(r)$. By
the definition of $r^{*}_{(t)}$, it suffices to show that there exists
$r\in(0,1/c]$ that satisfies

$\displaystyle\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\leq cL\log(n+1).$

Suppose, for contradiction, that for any $r\in(0,1/c]$,

$\displaystyle\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}>cL\log(n+1).$

Then we have

$\displaystyle\int_{0}^{1/c}\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\,\mathrm{d}r>\int_{0}^{1/c}cL\log(n+1)\,\mathrm{d}r=L\log(n+1).$
(1)

Now relabel the elements in $V^{(t)}$ that have distance less than $1/c$ from
$i^{(t)}$ (including $i^{(t)}$ itself) as $i^{(t)}=j_{0},\dots,j_{q-1}$ in the
increasing order of the distance. For each $p=0,\dots,q-1$, we denote by
$r_{p}$ the distance from $i^{(t)}$ to $j_{p}$, i.e.,
$r_{p}=x^{*}_{i^{(t)}j_{p}}$. For convenience, we set $r_{q}=1/c$. For any
$\ell\in[L]$, the function $\text{vol}_{\ell}(r)$ is not necessarily
differentiable and even not necessarily continuous at $r_{0},\dots,r_{q}$. On
the other hand, at any point $r\in(0,1/c]$ except for $r_{1},\dots,r_{q}$, the
function $\text{vol}_{\ell}(r)$ is differentiable, and from the definition, we
have

$\displaystyle\frac{\text{d}\,\text{vol}_{\ell}(r)}{\text{d}r}=\text{cut}_{\ell}(r).$
(2)

Moreover, by simple calculation, we have that for any $\ell\in[L]$ with
$F_{\ell}\neq 0$,

$\displaystyle\frac{\text{vol}_{\ell}(1/c)}{\text{vol}_{\ell}(0)}\leq n+1.$
(3)

Indeed, we see that $\text{vol}_{\ell}(0)=F_{\ell}/n$ and

$\displaystyle\text{vol}_{\ell}(1/c)$
$\displaystyle=\frac{F_{\ell}}{n}+\sum_{\\{j,k\\}\in E^{+}_{\ell}:\,j,k\in
B(1/c)}w_{\ell}(j,k)x^{*}_{jk}+\sum_{\\{j,k\\}\in E^{+}_{\ell}:\,j\in
B(1/c)\land k\in V^{(t)}\setminus
B(1/c)}w_{\ell}(j,k)\left(\frac{1}{c}-x^{*}_{i^{(t)}j}\right)$
$\displaystyle\leq\frac{F_{\ell}}{n}+\sum_{\\{j,k\\}\in E^{+}_{\ell}:\,j\in
B(1/c)\land k\in V^{(t)}}w_{\ell}(j,k)x^{*}_{jk}$
$\displaystyle\leq\frac{F_{\ell}}{n}+F_{\ell},$

where the first inequality follows from

$\displaystyle 1/c-x^{*}_{i^{(t)}j}\leq x^{*}_{i^{(t)}k}-x^{*}_{i^{(t)}j}\leq
x^{*}_{i^{(t)}j}+x^{*}_{jk}-x^{*}_{i^{(t)}j}=x^{*}_{jk}$ (4)

for any $\\{j,k\\}\in E^{+}_{\ell}$ such that $j\in B(1/c)$ and $k\in
V^{(t)}\setminus B(1/c)$. Using Equality (2) and Inequality (3), we have

$\displaystyle\int_{0}^{1/c}\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\,\mathrm{d}r$
$\displaystyle\leq\sum_{\ell\in[L]:\,F_{\ell}\neq
0}\int_{0}^{1/c}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\,\mathrm{d}r$
$\displaystyle=\sum_{\ell\in[L]:\,F_{\ell}\neq
0}\sum_{p=0}^{q-1}\int_{r_{p}}^{r_{p+1}}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\,\mathrm{d}r$
$\displaystyle=\sum_{\ell\in[L]:\,F_{\ell}\neq
0}\sum_{p=0}^{q-1}\int_{r_{p}}^{r_{p+1}}\frac{1}{\mathrm{vol}_{\ell}(r)}\,\mathrm{d}\,\text{vol}_{\ell}(r)$
$\displaystyle=\sum_{\ell\in[L]:\,F_{\ell}\neq
0}\sum_{p=0}^{q-1}(\log\text{vol}_{\ell}(r_{p+1})-\log\text{vol}_{\ell}(r_{p}))$
$\displaystyle=\sum_{\ell\in[L]:\,F_{\ell}\neq
0}\log\frac{\text{vol}_{\ell}(1/c)}{\text{vol}_{\ell}(0)}$ $\displaystyle\leq
L\log(n+1),$

where the first inequality follows from the fact that
$\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}$ is nonnegative for any
$\ell\in[L]$ with $F_{\ell}\neq 0$ and $r\in(0,1/c]$. The above contradicts
Inequality (1), meaning that there exists $r\in(0,1/c]$ such that

$\displaystyle\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\mathrm{cut}_{\ell}(r)}{\mathrm{vol}_{\ell}(r)}\leq cL\log(n+1).$

From now on, we show that $B(r^{*}_{(t)})=B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})$
can be computed in polynomial time. To this end, it suffices to show that the
radius $r^{*}_{(t)}\in\mathop{\rm
argmin}\left\\{\max_{\ell\in[L]:\,F_{\ell}\neq
0}\frac{\text{cut}_{\ell}(r)}{\text{vol}_{\ell}(r)}:r\in(0,1/c]\right\\}$ can
be computed in polynomial time. Recall the relabeling of the elements in
$V^{(t)}$. For any $p=0,\dots,q-1$, in the interval $(r_{p},r_{p+1}]$, the
function $\frac{\text{cut}_{\ell}(r)}{\text{vol}_{\ell}(r)}$ for any
$\ell\in[L]$ is monotonically nonincreasing, and thus so is
$\max_{\ell\in[L]}\frac{\text{cut}_{\ell}(r)}{\text{vol}_{\ell}(r)}$. Indeed,
in that interval, $\text{cut}_{\ell}(r)$ is unchanged, while
$\text{vol}_{\ell}(r)$ is monotonically nondecreasing. Therefore, it suffices
to compute
$\max_{\ell\in[L]}\frac{\text{cut}_{\ell}(r)}{\text{vol}_{\ell}(r)}$ for all
$r=r_{1},\dots,r_{q}$ and identify the one that attains the minimum. Clearly
this procedure can be done in polynomial time. ∎

We are now ready to prove our main theorem:

######  Theorem 1.

Algorithm 1 is a polynomial-time $O(L\log n)$-approximation algorithm for
Problem 1.

###### Proof.

By Lemma 1, it is trivial that Algorithm 1 runs in polynomial time. Therefore,
in what follows, we analyze the approximation ratio. Letting $\mathcal{B}$ be
the output of the algorithm, we need to evaluate

$\displaystyle\|\mathsf{Disagree}_{\ell}(\mathcal{B})\|_{p}=\begin{cases}\displaystyle\left(\sum_{\ell\in[L]}\left(\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)\neq\mathcal{B}(k)]+\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)=\mathcal{B}(k)]\right)^{p}\right)^{1/p}\\\
\hskip 284.52756pt\text{if }p<\infty,\\\
\displaystyle\max_{\ell\in[L]}\left(\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)\neq\mathcal{B}(k)]+\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)=\mathcal{B}(k)]\right)\\\
\hskip 284.52756pt\text{if }p=\infty.\end{cases}$

We first evaluate the terms for ‘$+$’ labels. By Lemma 1, we have that for any
$\ell\in[L]$ with $F_{\ell}\neq 0$,

$\displaystyle\mathrm{cut}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))\leq
cL\log(n+1)\cdot\mathrm{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})).$

Based on this, for any $\ell\in[L]$ with $F_{\ell}\neq 0$, we have

$\displaystyle\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)\neq\mathcal{B}(k)]$
$\displaystyle=\sum_{t=1}^{|\mathcal{B}|}\text{cut}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))$
$\displaystyle\leq
cL\log(n+1)\sum_{t=1}^{|\mathcal{B}|}\mathrm{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))$
$\displaystyle\leq
cL\log(n+1)\left(\frac{F_{\ell}}{n}\cdot|\mathcal{B}|+\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}\right)$ $\displaystyle\leq
2cL\log(n+1)\sum_{\\{j,k\\}\in E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}.$ (5)

The second inequality follows from the fact that the balls included in
$\mathcal{B}$ are mutually disjoint. Indeed, for any $\\{j,k\\}\in
E^{+}_{\ell}$ contained in some ball $B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})$, the
value $w_{\ell}(j,k)x^{*}_{jk}$ is produced just once due to
$\mathrm{vol}_{(V^{(t)},\ell)}(B_{V^{(t)}}(i^{(t)},r^{*}_{(t)}))$, while for
any $\\{j,k\\}\in E^{+}_{\ell}$ across distinct balls
$B_{V^{(t^{\prime})}}(i^{(t^{\prime})},r^{*}_{(t^{\prime})})$ and
$B_{V^{(t^{\prime\prime})}}(i^{(t^{\prime\prime})},r^{*}_{(t^{\prime\prime})})$
($t^{\prime}<t^{\prime\prime}$), once removing
$B_{V^{(t^{\prime})}}(i^{(t^{\prime})},r^{*}_{(t^{\prime})})$, all the
incident edges will never appear in the later iterations, and thus at most the
value $w_{\ell}(j,k)(1/c-x^{*}_{i^{(t^{\prime})}j})$ is produced just once due
to
$\mathrm{vol}_{(V^{(t^{\prime})},\ell)}(B_{V^{(t^{\prime})}}(i^{(t^{\prime})},r^{*}_{(t^{\prime})}))$.
Note that without loss of generality, we assumed that
$B_{V^{(t^{\prime})}}(i^{(t^{\prime})},r^{*}_{(t^{\prime})})$ contains only
$j$ among $j,k$. By Inequality (4), we have $1/c-x^{*}_{i^{(t^{\prime})}j}\leq
x^{*}_{jk}$. On the other hand, for any $\ell\in[L]$ with $F_{\ell}=0$, we see
that $x^{*}_{jk}=0$ for any $\\{j,k\\}\in E^{+}_{\ell}$. Therefore, by its
design, the algorithm does not separate any $\\{j,k\\}\in E^{+}_{\ell}$,
meaning that for any $\ell\in[L]$ with $F_{\ell}=0$,

$\displaystyle\sum_{\\{u,v\\}\in
E^{+}_{\ell}}w_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{B}(u)\neq\mathcal{B}(v)]=0.$
(6)

Next we evaluate the terms for ‘$-$’ labels. For any $\ell\in[L]$, we have

$\displaystyle\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\mbox{1}\mbox{l}[\mathcal{B}(j)=\mathcal{B}(k)]$
$\displaystyle=\frac{c}{c-2}\sum_{t=1}^{|\mathcal{B}|}\sum_{\\{j,k\\}\in
E^{-}_{\ell}:\,j,k\in
B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})}w_{\ell}(j,k)\left(1-\frac{2}{c}\right)$
$\displaystyle\leq\frac{c}{c-2}\sum_{t=1}^{|\mathcal{B}|}\sum_{\\{j,k\\}\in
E^{-}_{\ell}:\,j,k\in
B_{V^{(t)}}(i^{(t)},r^{*}_{(t)})}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right)$
$\displaystyle\leq\frac{c}{c-2}\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right),$ (7)

where the first inequality follows from the triangle inequalities in (CV) and
(LP). Indeed, denoting by $i^{(t)}$ the center of the ball containing $j,k$,
we have $x^{*}_{jk}\leq x^{*}_{ji^{(t)}}+x^{*}_{i^{(t)}k}<2/c$.

Let $\mathrm{OPT}$ be the optimal value of Problem 1. Using Inequality (4.2),
Equality (6), and Inequality (4.2), we have that in the case of $p<\infty$,

$\displaystyle\|\mathsf{Disagree}_{\ell}(\mathcal{B})\|_{p}$
$\displaystyle\leq\left(\sum_{\ell\in[L]}\left(2cL\log(n+1)\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}+\frac{c}{c-2}\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right)\right)^{p}\right)^{1/p}$
$\displaystyle\leq\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\left(\sum_{\ell\in[L]}\left(\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}+\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right)\right)^{p}\right)^{1/p}$
$\displaystyle=\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\mathrm{OPT}_{\mathrm{CV}}$
$\displaystyle\leq\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\mathrm{OPT},$

and in the case of $p=\infty$,

$\displaystyle\|\mathsf{Disagree}_{\ell}(\mathcal{B})\|_{p}$
$\displaystyle\leq\max_{\ell\in[L]}\left(2cL\log(n+1)\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}+\frac{c}{c-2}\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right)\right)$
$\displaystyle\leq\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\max_{\ell\in[L]}\left(\sum_{\\{j,k\\}\in
E^{+}_{\ell}}w_{\ell}(j,k)x^{*}_{jk}+\sum_{\\{j,k\\}\in
E^{-}_{\ell}}w_{\ell}(j,k)\left(1-x^{*}_{jk}\right)\right)$
$\displaystyle=\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\mathrm{OPT}_{\mathrm{LP}}$
$\displaystyle\leq\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}\mathrm{OPT}.$

Noting that $\max\left\\{2cL\log(n+1),\,\frac{c}{c-2}\right\\}=O(L\log n)$, we
have the theorem. ∎

Finally we mention the integrality gaps of (CV) and (LP). For MinDisagree of
the general weighted case, the LP relaxation used for designing the $O(\log
n)$-approximation algorithms is known to have the integrality gap of
$\Omega(\log n)$ [16, 25]. As our relaxations, (CV) and (LP), are
generalizations of the above LP relaxation, the integrality gap of
$\Omega(\log n)$ is inherited. This matches our approximation ratio in the
case of $L=O(1)$ but there remains a gap in general.

##  5 Algorithms for Problem 1 with Probability Constraint

In this section, we present our algorithms for Problem 1 with the probability
constraint. The first algorithm has an approximation ratio of $(\alpha+2)$,
where $\alpha$ is any possible approximation ratio for MinDisagree with the
probability constraint or any of its special cases if we consider the
corresponding special case of our problem, while the second algorithm has an
approximation ratio of $4$.

###  5.1 The $(\alpha+2)$-approximation algorithm

To design the algorithm, we reduce Problem 1 with the probability constraint
to a novel optimization problem in a metric space. Let $X$ be a set. Let
$d\colon X\times X\rightarrow\mathbb{R}_{\geq 0}$ be a _metric_ on $V$, i.e.,
$d(x,y)=0$ if and only if $x=y$ for $x,y\in V$, $d(x,y)=d(y,x)$ for $x,y\in
V$, and $d(x,z)\leq d(x,y)+d(y,z)$ for $x,y,z\in V$. In general, $(X,d)$ is
called a _metric space_. We introduce the following problem:

######  Problem 2 (Find the Most Representative Candidate in a Metric Space).

Fix $p\geq 1$. Let $(X,d)$ be a metric space. Given $x_{1},\dots,x_{L}\in X$
and a candidate set $F\subseteq X$, we are asked to find $x\in F$ that
minimizes $\left(\sum_{\ell\in[L]}d(x,x_{\ell})^{p}\right)^{1/p}$ if
$p<\infty$ and $\max_{\ell\in[L]}d(x,x_{\ell})$ if $p=\infty$.

Then we can prove the following key lemma. The proof is based on the fact that
each layer of the input of Problem 1 with the probability constraint (i.e., an
input of MinDisagree with the probability constraint) and any clustering of
$V$ can be dealt with in a unified metric space $(X,d)$ when $X$ and $d$ are
set appropriately.

######  Lemma 2.

There exists a polynomial-time approximation-preserving reduction from Problem
1 with the probability constraint to Problem 2.

###### Proof.

Fix $p\geq 1$. Let $V$ and $(w^{+}_{\ell},w^{-}_{\ell})_{\ell\in[L]}$ be the
input of Problem 1 with the probability constraint, satisfying
$w^{+}_{\ell}(u,v)+w^{-}_{\ell}(u,v)=1$ for any $\ell\in[L]$ and $\\{u,v\\}\in
E$. We construct an instance of Problem 2 as follows: Let $X=[0,1]^{E}$ and
$d\colon X\times X\rightarrow\mathbb{R}_{\geq 0}$ be a metric such that
$d(x,y)\coloneqq\|x-y\|_{1}$ for $x,y\in X$. For $x\in X$ and $\\{u,v\\}\in
E$, we denote by $x(u,v)$ the element of $x$ associated with $\\{u,v\\}$. For
each $\ell\in[k]$, let $x_{\ell}\in X$ be the element such that
$x_{\ell}(u,v)=w^{-}_{\ell}(u,v)$ for $\\{u,v\\}\in E$. Let
$F=\\{x\in\\{0,1\\}^{E}:\text{$x$ induces a clustering of $V$}\\}$. Here $x$
is said to _induce a clustering of_ $V$ if every connected component in
$(V,E_{x})$, where $E_{x}=\\{\\{u,v\\}\in E:x(u,v)=0\\}$, is a clique. Then we
see that there is a one-to-one correspondence between $F$ and the set of
clusterings of $V$. Take an arbitrary element $x\in F$ and let
$\mathcal{C}_{x}$ be the clustering corresponding to $x$. Then we have that
for any $\ell\in[L]$,

$\displaystyle d(x,x_{\ell})$ $\displaystyle=\|x-x_{\ell}\|_{1}$
$\displaystyle=\sum_{\\{u,v\\}\in
E}\left((1-w^{-}_{\ell}(u,v))\mbox{1}\mbox{l}[\mathcal{C}_{x}(u)\neq\mathcal{C}_{x}(v)]+w^{-}_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}_{x}(u)=\mathcal{C}_{x}(v)]\right)$
$\displaystyle=\sum_{\\{u,v\\}\in
E}\left(w^{+}_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}_{x}(u)\neq\mathcal{C}_{x}(v)]+w^{-}_{\ell}(u,v)\mbox{1}\mbox{l}[\mathcal{C}_{x}(u)=\mathcal{C}_{x}(v)]\right)$
$\displaystyle=\mathsf{Disagree}_{\ell}(\mathcal{C}_{x}),$

meaning that the objective function of Problem 2 is equivalent to that of
Problem 1 with the probability constraint. Therefore, $x$ is a
$\beta$-approximate solution to Problem 2 if and only if so is
$\mathcal{C}_{x}$ to Problem 1 with the probability constraint. Noticing that
the above reduction can be done in polynomial time, we have the lemma. ∎

In what follows, we design an approximation algorithm for Problem 2, resulting
in an approximation algorithm for Problem 1 with the probability constraint
with the same approximation ratio. To this end, we introduce the following
subproblem:

######  Problem 3 (Find the Closest Candidate in a Metric Space).

Let $(X,d)$ be a metric space. Given $x\in X$ and a candidate set $F\subseteq
X$, we are asked to find $x^{\prime}\in F$ that minimizes $d(x,x^{\prime})$.

Assume now that we have an $\alpha$-approximation algorithm for Problem 3. Let
$x_{1},\dots,x_{L}\in X$ and $F\subseteq X$ be the input of Problem 2. Our
approximation algorithm for Problem 2 runs as follows: For every $\ell\in[L]$,
the algorithm obtains an $\alpha$-approximate solution $x^{\prime}_{\ell}\in
F$ for Problem 3 with input $x_{\ell}\in X$ and $F\subseteq X$, using the
$\alpha$-approximation algorithm for Problem 3. Then the algorithm outputs the
best solution among $x^{\prime}_{1},\dots,x^{\prime}_{L}$ in terms of the
objective function of Problem 2. The pseudocode is given in Algorithm 2.

Input: $x_{1},\dots,x_{L}\in X$ and $F\subseteq X$

Output: $x\in F$

1 for  _$\ell=1,\dots,L$_ do

2 $x^{\prime}_{\ell}\leftarrow\text{$\alpha$-approximate solution for
Problem~{}\ref{prob:sub} with input $x_{\ell}\in X$ and $F\subseteq X$}$;

3return _$x_{\mathrm{out}}\in\mathop{\rm
argmin}_{x\in\\{x^{\prime}_{1},\dots,x^{\prime}_{L}\\}}\left(\sum_{\ell\in[L]}d(x,x_{\ell})^{p}\right)^{1/p}$
if $p<\infty$ and $x_{\mathrm{out}}\in\mathop{\rm
argmin}_{x\in\\{x^{\prime}_{1},\dots,x^{\prime}_{L}\\}}\max_{\ell\in[L]}d(x,x_{\ell})$
if $p=\infty$_;

Algorithm 2 $(\alpha+2)$-approximation algorithm for Problem 2

###  5.2 Analysis of Algorithm 2

The following theorem gives the approximation ratio of Algorithm 2.

######  Theorem 2.

Algorithm 2 is an $(\alpha+2)$-approximation algorithm for Problem 2.

###### Proof.

Let $x^{*}\in F$ be an optimal solution to Problem 2. Let
$x_{\mathrm{closest}}\in\mathop{\rm
argmin}_{x\in\\{x_{1},\dots,x_{L}\\}}d(x,x^{*})$ and
$x^{\prime}_{\mathrm{closest}}$ be the $\alpha$-approximate solution for
Problem 3 with input $x_{\mathrm{closest}}$ and $F$. By the definition of
$x^{\prime}_{\mathrm{closest}}$ and $x_{\mathrm{closest}}$, we have that for
any $\ell\in[L]$,

$\displaystyle
d(x^{\prime}_{\mathrm{closest}},x_{\mathrm{closest}})\leq\alpha\cdot
d(x^{*},x_{\mathrm{closest}})\leq\alpha\cdot d(x^{*},x_{\ell}).$

Using these inequalities, we have that for any $\ell\in[L]$,

$\displaystyle d(x^{\prime}_{\mathrm{closest}},x_{\ell})$ $\displaystyle\leq
d(x^{\prime}_{\mathrm{closest}},x^{*})+d(x^{*},x_{\ell})$ $\displaystyle\leq
d(x^{\prime}_{\mathrm{closest}},x_{\mathrm{closest}})+d(x_{\mathrm{closest}},x^{*})+d(x^{*},x_{\ell})$
$\displaystyle\leq\alpha\cdot
d(x^{*},x_{\ell})+d(x^{*},x_{\ell})+d(x^{*},x_{\ell})$
$\displaystyle=(\alpha+2)\cdot d(x^{*},x_{\ell}),$

where the first and second inequalities follow from the triangle inequality
for the metric $d$ and the third inequality follows from the definition of
$x_{\mathrm{closest}}$. Noticing that $x^{\prime}_{\mathrm{closest}}$ is one
of the output candidates of Algorithm 2, we can upper bound the objective
value of the output $x_{\mathrm{out}}$ as follows: In the case of $p<\infty$,

$\displaystyle\left(\sum_{\ell\in[L]}d(x_{\mathrm{out}},x_{\ell})^{p}\right)^{1/p}\leq\left(\sum_{\ell\in[L]}d(x^{\prime}_{\mathrm{closest}},x_{\ell})^{p}\right)^{1/p}\leq(\alpha+2)\left(\sum_{\ell\in[L]}d(x^{*},x_{\ell})^{p}\right)^{1/p},$

while in the case of $p=\infty$,

$\displaystyle\max_{\ell\in[L]}d(x_{\mathrm{out}},x_{\ell})\leq\max_{\ell\in[L]}d(x^{\prime}_{\mathrm{closest}},x_{\ell})\leq(\alpha+2)\max_{\ell\in[L]}d(x^{*},x_{\ell}),$

which concludes the proof. ∎

In Algorithm 2, the approximation ratio $\alpha$ for Problem 3 that we can
take depends on the metric space $(X,d)$ and part of input $F\subseteq X$,
inherited from Problem 2. By interpreting Problem 1 with the probability
constraint (or any of its special cases) as Problem 2 with specific metric
space $(X,d)$ and part of input $F\subseteq X$, we can obtain the following
series of approximability results:

######  Corollary 1.

There exists a polynomial-time $4.5$-approximation algorithm for Problem 1
with the probability constraint.

###### Proof.

By Lemma 2, it suffices to show that there exists a polynomial-time
$4.5$-approximation algorithm for Problem 2 with the metric space $(X,d)$ and
the part of input $F\subseteq X$ that correspond to Problem 1 with the
probability constraint. By Theorem 2, Algorithm 2 is an
$(\alpha+2)$-approximation algorithm for Problem 2, where $\alpha$ is the
approximation ratio of the algorithm employed for solving Problem 3 with those
$(X,d)$ and $F\subseteq X$. Based on the reduction in the proof of Lemma 2,
Problem 3 with those $(X,d)$ and $F\subseteq X$ is equivalent to MinDisagree
with the probability constraint, for which there exists a polynomial-time
$2.5$-approximation algorithm [5]. Therefore, we have the corollary. ∎

######  Corollary 2.

For any $\epsilon>0$, there exists a polynomial-time
$(3.73+\epsilon)$-approximation algorithm for Problem 1 of the unweighted
case.

###### Proof.

The proof strategy is the same as the above. In this case, we can specialize
the reduction given in the proof of Lemma 2 by replacing $X=[0,1]^{E}$ with
$X=\\{0,1\\}^{E}$, and we see that Problem 3 with $(X,d)$ and $F\subseteq X$
is equivalent to MinDisagree of the unweighted case, for which there exists a
polynomial-time $(1.73+\epsilon)$-approximation algorithm for any $\epsilon>0$
[19]. ∎

######  Corollary 3.

There exists a polynomial-time $3.5$-approximation algorithm for Problem 1
with the probability constraint and the triangle inequality constraint.

###### Proof.

The proof is again similar. In this case, we can specialize the reduction by
replacing $X=[0,1]^{E}$ with $X=\\{x\in[0,1]^{E}:x(u,w)\leq x(u,v)+x(v,w),\
\forall u,v,w\in V\\}$, and we see that Problem 3 with $(X,d)$ and $F\subseteq
X$ is equivalent to MinDisagree with the probability constraint and the
triangle inequality constraint, for which there exists a polynomial-time
$1.5$-approximation algorithm [17]. ∎

###  5.3 The 4-approximation algorithm

Here we present our $4$-approximation algorithm, which is a generalization of
the $4$-approximation algorithm for MinDisagree of the unweighted case,
designed by Charikar et al. [16]. As in Section 4, we first introduce $0$–$1$
convex programming formulations for Problem 1. In the case of $p<\infty$,
Problem 1 can be formulated as follows:

minimize $\displaystyle\left(\sum_{\ell\in[L]}\left(\sum_{\\{i,j\\}\in
E}\left(w^{+}_{\ell}(i,j)x_{ij}+w^{-}_{\ell}(i,j)(1-x_{ij})\right)\right)^{p}\right)^{1/p}$
subject to $\displaystyle x_{ij}=x_{ji}\quad(\forall i,j\in V,\ i\neq j),$
$\displaystyle x_{ik}\leq x_{ij}+x_{jk}\quad(\forall i,j,k\in V,\ i\neq
j,\,j\neq k,\,k\neq i),$ $\displaystyle x_{ij}\in\\{0,1\\}\quad(\forall i,j\in
V,\ i\neq j).$

On the other hand, in the case of $p=\infty$, we have the following $0$–$1$ LP
formulation:

minimize $\displaystyle t$ subject to $\displaystyle\sum_{\\{i,j\\}\in
E}\left(w^{+}_{\ell}(i,j)x_{ij}+w^{-}_{\ell}(i,j)(1-x_{ij})\right)\leq
t\quad(\forall\ell\in[L]),$ $\displaystyle x_{ij}=x_{ji}\quad(\forall i,j\in
V,\ i\neq j),$ $\displaystyle x_{ik}\leq x_{ij}+x_{jk}\quad(\forall i,j,k\in
V,\ i\neq j,\,j\neq k,\,k\neq i),$ $\displaystyle
x_{ij}\in\\{0,1\\}\quad(\forall i,j\in V,\ i\neq j).$

As in Section 4, we refer to the continuous relaxations of the above problems
as (CV-Pr) and (LP-Pr), respectively. Again (CV-Pr) is a convex programming
problem, and we suppose that (CV-Pr) can be solved exactly in polynomial time.
Let $\mathrm{OPT}_{\textrm{CV-Pr}}$ and $\mathrm{OPT}_{\textrm{LP-Pr}}$ be the
optimal values of (CV-Pr) and (LP-Pr), respectively.

Our algorithm first solves an appropriate relaxation, (CV-Pr) or (LP-Pr),
depending on the value of $p$, and obtains its optimal solution
$\bm{x}^{*}=(x^{*}_{ij})_{i,j\in V:\,i\neq j}$. Then the algorithm introduces
$\overline{\bm{x}}^{*}=(x^{*}_{ij})_{i,j\in V}$ by setting $x^{*}_{ii}=0$ for
every $i\in V$. Based on the pseudometric $\overline{\bm{x}}^{*}$ over $V$,
the algorithm constructs a clustering, using a simple thresholding rule. Let
$\widehat{V}$ be an arbitrary subset of $V$. For $i\in\widehat{V}$ and $r\geq
0$, we denote by $B_{\widehat{V}}(i,r)$ the closed ball of center $i$ and
radius $r$ in $\widehat{V}$, i.e.,

$\displaystyle B_{\widehat{V}}(i,r)=\\{j\in\widehat{V}:x^{*}_{ij}\leq r\\}.$

Our algorithm initially set $\widehat{V}=V$. In each iteration, the algorithm
takes an arbitrary element $i\in\widehat{V}$ and initializes a cluster
$B=\\{i\\}$. Then the algorithm constructs
$C=B_{\widehat{V}}(i,1/2)\setminus\\{i\\}$. If the average distance between
$i$ and the elements in $C$ is less than $1/4$, i.e., $\frac{1}{|C|}\sum_{j\in
C}x^{*}_{ij}<1/4$, then the algorithm updates $B$ by adding all elements in
$C$. The algorithm removes $B$ from $\widehat{V}$ as a cluster of the output,
and repeats this procedure until $\widehat{V}=\emptyset$. The pseudocode is
written in Algorithm 3.

Input: $V$ and $(w^{+}_{\ell},w^{-}_{\ell})_{\ell\in[L]}$

Output: Clustering of $V$

1 Compute an optimal solution $\bm{x}^{*}=(x^{*}_{ij})_{i,j\in V:\,i\neq j}$
to (CV-Pr) if $p<\infty$ and (LP-Pr) if $p=\infty$;

2 Construct $\overline{\bm{x}}^{*}=(x^{*}_{ij})_{i,j\in V}$ by setting
$x^{*}_{ii}=0$ for every $i\in V$;

3 $\mathcal{B}\leftarrow\emptyset$ and $\widehat{V}\leftarrow V$;

4 while  _$\widehat{V}\neq\emptyset$_ do

5 Take an arbitrary $i\in\widehat{V}$ and initialize $B\leftarrow\\{i\\}$;

6 $C\leftarrow B_{\widehat{V}}(i,1/2)\setminus\\{i\\}$;

7 if $\frac{1}{|C|}\sum_{j\in C}x^{*}_{ij}<1/4$ then $B\leftarrow B\cup C$;

8 $\mathcal{B}\leftarrow\mathcal{B}\cup\\{B\\}$ and
$\widehat{V}\leftarrow\widehat{V}\setminus B$;

9

10return _$\mathcal{B}$_ ;

Algorithm 3 $4$-approximation algorithm for Problem 1 with the probability
constraint

###  5.4 Analysis of Algorithm 3

The following theorem gives the approximation ratio of Algorithm 3.

######  Theorem 3.

Algorithm 3 is a $4$-approximation algorithm for Problem 1 with the
probability constraint.

###### Proof.

It suffices to prove that for any layer $\ell\in[L]$, it holds that

$\displaystyle\mathsf{Disagree}_{\ell}(\mathcal{B})\leq 4\sum_{\\{i,j\\}\in
E}\left(w^{+}_{\ell}(i,j)x^{*}_{ij}+w^{-}_{\ell}(i,j)(1-x^{*}_{ij})\right).$
(8)

Indeed, from this inequality, it follows that
$\|\mathbf{Disagree}(\mathcal{B})\|_{p}\leq 4\cdot\mathrm{OPT}_{\textrm{CV-
Pr}}$ if $p<\infty$ and $\|\mathbf{Disagree}(\mathcal{B})\|_{p}\leq
4\cdot\mathrm{OPT}_{\textrm{LP-Pr}}$ if $p=\infty$, which proves the theorem.
Fix $\ell\in[L]$ and consider an arbitrary iteration of the while-loop in
Algorithm 3. Let $B\subseteq\widehat{V}$ be the cluster produced in the
iteration. We define the _cost_ of $B$ as the contribution of all pairs of
elements in $\widehat{V}$ with at least one of them being inside $B$ to the
objective value, i.e., $\sum_{\\{j,k\\}\in E:\,j,k\in
B}w^{-}_{\ell}(j,k)+\sum_{\\{j,k\\}\in E:\,j\in B\land
k\in\widehat{V}\setminus B}w^{+}_{\ell}(j,k)$. In what follows, we upper bound
the cost of $B$ using the corresponding terms in the right-hand-side of
Inequality (8). Recall that $C=B_{\widehat{V}}(i,1/2)\setminus\\{i\\}$
contains all elements in $\widehat{V}$ (except for $i$) within distance of at
most $1/2$ from $i$. There are two cases:

(i) If the average distance between $i$ and the elements in $C$ is no less
than $1/4$, i.e., $\frac{1}{|C|}\sum_{j\in C}x^{*}_{ij}\geq 1/4$, then the
algorithm forms the singleton cluster $B=\\{i\\}$. In this case, the cost of
the cluster reduces to
$\sum_{j\in\widehat{V}\setminus\\{i\\}}w^{+}_{\ell}(i,j)$. For each
$j\in\widehat{V}\setminus\\{i\\}$ with $x^{*}_{ij}>1/2$, we can upper bound
each $w^{+}_{\ell}(i,j)$ using the corresponding term in the right-hand-side
of Inequality (8) because it holds that $w^{+}_{\ell}(i,j)\leq 2\cdot
w^{+}_{\ell}(i,j)x^{*}_{ij}\leq
2\left(w^{+}_{\ell}(i,j)x^{*}_{ij}+w^{-}_{\ell}(i,j)(1-x^{*}_{ij})\right)$. On
the other hand, consider any pair of elements for which $x^{*}_{ij}\leq 1/2$
holds, i.e., the element $j$ is contained in $C$. Then, it holds that
$1-x^{*}_{ij}\geq x^{*}_{ij}$, and thus we have

$\displaystyle\sum_{j\in
C}\left(w^{+}_{\ell}(i,j)x^{*}_{ij}+w^{-}_{\ell}(i,j)(1-x^{*}_{ij})\right)\geq\sum_{j\in
C}\left(w^{+}_{\ell}(i,j)+w^{-}_{\ell}(i,j)\right)x^{*}_{ij}=\sum_{j\in
C}x^{*}_{ij},$

where the equality follows from the probability constraint. Using the above
inequality together with the assumption $\frac{1}{|C|}\sum_{j\in
C}x^{*}_{ij}\geq 1/4$, we have

$\displaystyle\sum_{j\in C}w^{+}_{\ell}(i,j)\leq|C|\leq 4\sum_{j\in
C}x^{*}_{ij}\leq 4\sum_{j\in
C}\left(w^{+}_{\ell}(i,j)x^{*}_{ij}+w^{-}_{\ell}(i,j)(1-x^{*}_{ij})\right).$

(ii) The second case is when the average satisfies $\frac{1}{|C|}\sum_{j\in
C}x^{*}_{ij}<1/4$, where the algorithm forms the cluster $B=\\{i\\}\cup C$.
For the sake of the proof, we assume that the elements in $\widehat{V}$ are
relabeled so that $j<k$ if $x^{*}_{ij}<x^{*}_{ik}$, where ties are broken
arbitrarily.

First consider the pairs of elements contained in $B$. The cost of $B$ charged
by these pairs is $\sum_{\\{j,k\\}\in E:\,j,k\in B}w^{-}_{\ell}(j,k)$. If both
$x^{*}_{ij}<3/8$ and $x^{*}_{ik}<3/8$ hold, then the triangle inequality over
the pseudometric assures that $1-x^{*}_{jk}\geq 1/4$, and therefore each
$w^{-}_{\ell}(j,k)$ can be upper bounded by the corresponding term in the
right-hand-side of Inequality (8) within a factor of $4$. The cost of $B$
charged by the remaining pairs of elements $j,k\in B$ with $j<k$ can be taken
into account by $k$. Obviously we have $x^{*}_{ik}\in[3/8,1/2]$. For a fixed
$k$, define the quantities $p_{k}=\sum_{j<k}w^{+}_{\ell}(j,k)$ and
$n_{k}=\sum_{j<k}w^{-}_{\ell}(j,k)$. The cost taken into account by $k$ is
equal to $n_{k}$. The sum of the terms corresponding to all pairs $j<k$, where
$k$ is fixed, in the right-hand-side of Inequality (8) can be lower bounded as
follows:

$\displaystyle\sum_{j<k}\left(w^{+}_{\ell}(j,k)x^{*}_{jk}+w^{-}_{\ell}(j,k)(1-x^{*}_{jk})\right)$
$\displaystyle\geq\sum_{j<k}\left(w^{+}_{\ell}(j,k)(x^{*}_{ik}-x^{*}_{ij})+w^{-}_{\ell}(j,k)(1-x^{*}_{ik}-x^{*}_{ij})\right)$
$\displaystyle=p_{k}x^{*}_{ik}+n_{k}(1-x^{*}_{ik})-\sum_{j<k}x^{*}_{ij}$
$\displaystyle\geq p_{k}x^{*}_{ik}+n_{k}(1-x^{*}_{ik})-\frac{p_{k}+n_{k}}{4}.$

The last inequality follows from the probability constraint together with the
fact that the average distance between $i$ and the elements in $\\{j:j<k\\}$
must be smaller than $1/4$, as $x^{*}_{ij}\geq 3/8$ for any $j\geq k$.
Therefore, the above is lower bounded by a linear function depending on
$x^{*}_{ik}\in[3/8,1/2]$. It is easy to see that for every $x^{*}_{ik}$ in
this range, the value is always at least $n_{k}/4$. Therefore, the cost
$n_{k}$ is always within a factor of $4$.

Next consider the pairs of elements $j,k\in\widehat{V}$ with exactly one
element being contained in $B=\\{i\\}\cup C$. Without loss of generality, we
assume that $j<k$ and thus we have $j\in B$, $k\in\widehat{V}\setminus B$, and
$x^{*}_{ij}<x^{*}_{ik}$. The cost of $B$ charged by these pairs is
$\sum_{\\{j,k\\}\in E:\,j\in B\land k\in\widehat{V}\setminus
B}w^{+}_{\ell}(j,k)$. If $x^{*}_{ik}\geq 3/4$ holds, then
$x^{*}_{ik}-x^{*}_{ij}\geq 1/4$. Using the triangle inequality over the
pseudometric, we have $x^{*}_{jk}\geq 1/4$, meaning that the cost charged by
those pairs is accounted for within a factor of $4$. The cost of $B$ charged
by the remaining pairs can again be taken into account by $k$. Obviously we
have $x^{*}_{ik}\in(1/2,3/4)$. For a fixed $k$, redefine the quantities
$p_{k}=\sum_{j<k:\,j\in B}w^{+}_{\ell}(j,k)$ and $n_{k}=\sum_{j<k:\,j\in
B}w^{-}_{\ell}(j,k)$. The cost taken into account by $k$ is equal to $p_{k}$.
The rest of the proof is identical to the above. ∎

The above theorem indicates that the $4$-approximation algorithm for
MinDisagree of the unweighted case, designed by Charikar et al. [16], can be
extended to the probability constraint case, which has yet to be mentioned
before. Although some approximation ratios better than $4$ are known for
MinDisagree of the unweighted case, thanks to its simplicity and
extendability, the algorithm has been generalized to various settings of the
unweighted case (see Section 2). Our analysis implies that those results may
be further generalized form the unweighted case to the probability constraint
case.

##  6 Experimental Evaluation

In this section, we report the results of computational experiments performed
on various real-world datasets, evaluating the practical performance of our
proposed algorithms in terms of both solution quality and computation time.

###  6.1 Experimental setup

Table 1: Real-world datasets used in our experiments.

Dataset (abbreviation) | $|V|$ | $L$
---|---|---
aves-sparrow-social (sparrow) | 52 | 2
insecta-ant-colony1 (ant) | 113 | 41
reptilia-tortoise-network (tortoise) | 136 | 4
aves-wildbird-network (wildbird) | 202 | 6
aves-weaver-social (weaver) | 445 | 23
reptilia-tortoise-network-fi (tortoise-fi) | 787 | 9

Datasets. Throughout the experiments, we set $p=\infty$ in Problem 1, meaning
that we aim to minimize the maximal disagreements over all layers. Table 1
lists real-world datasets, each of which is a multilayer network consisting of
$L$ layers with positive edge weights. All datasets were collected by Network
Repository222https://networkrepository.com/index.php. Using the datasets, we
generated our instances of Problem 1. Let
$G=(V,(E_{\ell},w_{\ell})_{\ell\in[L]})$ be a multilayer network at hand,
where $E_{\ell}$ is the set of edges on layer $\ell$ and $w_{\ell}\colon
E_{\ell}\rightarrow\mathbb{R}_{>0}$ is its weight function. We first normalize
all edge weights so that the maximum weight is equal to $1$; that is, we
redefine $w_{\ell}(\\{u,v\\})\leftarrow w_{\ell}(\\{u,v\\})/w_{\mathrm{max}}$
for every $\ell\in[L]$ and $\\{u,v\\}\in E_{\ell}$, where
$w_{\mathrm{max}}=\max_{\ell\in[L]}\max_{\\{u,v\\}\in
E_{\ell}}w_{\ell}(\\{u,v\\})$. For every $\ell\in[L]$, let
$\texttt{weights}(\ell)$ be the multiset of all edge weights on layer $\ell$,
i.e., $\texttt{weights}(\ell)=\\{w_{\ell}(\\{u,v\\}):\\{u,v\\}\in
E_{\ell}\\}$. We generate our instance $V$ and
$(w^{+}_{\ell},w^{-}_{\ell})_{\ell\in[L]}$ as follows: The set $V$ of objects
is exactly the same as the set of vertices in the multilayer network. For
convenience, we define $E=\\{\\{u,v\\}:u,v\in V,\,u\neq v\\}$.

First let us consider Problem 1 of the general weighted case. For each layer
$\ell\in[L]$ and $\\{u,v\\}\in E$, if $\\{u,v\\}\in E_{\ell}$ we set
$w^{+}_{\ell}(u,v)=w_{\ell}(\\{u,v\\})$ and $w^{-}_{\ell}(u,v)=0$; otherwise
we set $w^{+}_{\ell}(u,v)=0$ and
$w^{-}_{\ell}(u,v)=\texttt{random.choice}(\texttt{weights}(\ell))$ with
probability $0.5$, where $\texttt{random.choice}()$ takes an element from a
given multiset uniformly at random, and
$w^{+}_{\ell}(u,v)=w^{-}_{\ell}(u,v)=0$ otherwise. The intuition behind the
above setting is that we actively put ‘$+$’ labels for the pairs of objects
having edges, while for the pairs of objects not having edges, we only
passively put ‘$-$’ labels (i.e., only with probability $0.5$), given the
potential missing of edges in the original network. The weights for ‘$+$’
labels fully respect for the original edge weights, while the weights for
‘$-$’ labels are generated from those for ‘$+$’ labels.

Next consider Problem 1 with the probability constraint. In this case, the
instances are generated with the same intuition as above. For each layer
$\ell\in[L]$ and $\\{u,v\\}\in E$, if $\\{u,v\\}\in E_{\ell}$ we set
$w^{+}_{\ell}(u,v)=0.5+w_{\ell}(\\{u,v\\})/2$ and
$w^{-}_{\ell}(u,v)=1-w^{+}_{\ell}(u,v)$; otherwise we set
$w^{+}_{\ell}(u,v)=1-w^{-}_{\ell}(u,v)$, where
$w^{-}_{\ell}(u,v)=0.5+\texttt{random.choice}(\texttt{weights}(\ell))/2$ with
probability $0.5$, and $w^{+}_{\ell}(u,v)=w^{-}_{\ell}(u,v)=0.5$ otherwise.

Our algorithms and baselines. For Problem 1 of the general weighted case, we
run Algorithm 1. Note that in the algorithm, the way to select a pivot is
arbitrary; in our implementation, the algorithm just takes the object with the
smallest ID. We employ the following baseline methods:

  * •

Pick-a-Best. This method first solves MinDisagree on each layer, using the
state-of-the-art $O(\log n)$-approximation algorithms [16, 25], and then
outputs the best one among them in terms of the objective value of Problem 1.
This method can be seen as a generalization of Algorithm 2 for Problem 1 with
the probability constraint case, but it is not clear if the method has an
approximation ratio such as $O(L\log n)$, achieved by Algorithm 1.

  * •

Aggregate. This method first aggregates the layers. Specifically, the method
constructs $w^{+}\colon E\rightarrow\mathbb{R}_{\geq 0}$ and $w^{-}\colon
E\rightarrow\mathbb{R}_{\geq 0}$ by setting
$w^{+}(u,v)=\sum_{\ell\in[L]}w^{+}_{\ell}(u,v)$ and
$w^{-}(u,v)=\sum_{\ell\in[L]}w^{-}_{\ell}(u,v)$ for every $\\{u,v\\}\in E$.
Then it solves MinDisagree with input $V$ and $(w^{+},w^{-})$, using the
$O(\log n)$-approximation algorithms [16, 25]. As mentioned in Section 3, this
method gives an $O(\log n)$-approximate solution for Problem 1 when $p=1$, but
the approximation ratio for the case of $p=\infty$ is not clear.

For Problem 1 with the probability constraint, we run Algorithms 2 and 3. Note
that Algorithm 2 varies depending on the approximation algorithm for
MinDisagree with the probability constraint employed in the algorithm.
Specifically, we use the $2.5$-approximation algorithm and the
$5$-approximation algorithm, designed by Ailon et al. [5], providing the
approximation ratios of $4.5$ and $7$, respectively, of Algorithm 2. There is
a trade-off between these two selections: The first algorithm has a better
approximation ratio, but it is slower, as it has to solve an LP, which is not
required in the second algorithm. We refer to the two algorithms as Algorithm
2 (LP) and Algorithm 2 ($\overline{\text{LP}}$), respectively. In Algorithm 3,
the way to select a pivot is arbitrary, and we use the same rule as the above.
We employ the following baseline method:

  * •

Aggregate-Pr. This method is the probability-constraint counterpart of the
above Aggregate. Specifically, the method constructs $w^{+}\colon
E\rightarrow\mathbb{R}_{\geq 0}$ and $w^{-}\colon E\rightarrow\mathbb{R}_{\geq
0}$ by setting $w^{+}(u,v)=\left(\sum_{\ell\in[L]}w^{+}_{\ell}(u,v)\right)/L$
and $w^{-}(u,v)=\left(\sum_{\ell\in[L]}w^{-}_{\ell}(u,v)\right)/L$ for every
$\\{u,v\\}\in E$. Then it solves MinDisagree with the probability constraint
with input $V$ and $(w^{+},w^{-})$, using the $2.5$-approximation algorithm or
the $5$-approximation algorithm [5], as in Algorithm 2. We refer to this
baseline as Aggregate-Pr (LP) or Aggregate-Pr ($\overline{\text{LP}}$),
depending on the choice of the above approximation algorithm. As mentioned in
Section 3, Aggregate-Pr (LP) gives a $2.5$-approximate solution for Problem 1
with the probability constraint when $p=1$, but the approximation ratio for
the case of $p=\infty$ is not clear.

Finally we mention the implementation of the LPs. All LPs to be solved by the
algorithms have the $\Theta(n^{3})$ triangle inequality constraints;
therefore, it is inefficient to input the entire program directly. To overcome
this, all algorithms employ the technique called Row Generation [31]. In this
technique, we first solve the program without any triangle inequality
constraint. Then we scan all the constraints: if there are constraints that
are violated by the current optimal solution, we add the constraints to the
program, solve it again, and repeat the process; otherwise we output the
current optimal solution, which is indeed an optimal solution to the original
program.

Machine spec and code. All experiments were conducted on a machine with Apple
M1 Chip and 16 GB RAM. All codes were written in Python 3. LPs were solved
using Gurobi Optimizer 11.0.1 with the default parameter setting.

###  6.2 Results

The results for Problem 1 of the general weighted case are presented in Table
2, where for each instance, the best objective value and running time among
the algorithms are written in bold. The second column, named LB, presents
$\mathrm{OPT}_{\mathrm{LP}}$, i.e., the optimal value of (LP), which is a
lower bound on the optimal value of Problem 1. OT indicates that the algorithm
did not terminate in 3,600 seconds. As can be seen, Algorithm 1 outperforms
the baseline methods in terms of the quality of solutions. Indeed, Algorithm 1
obtains much better solutions than those computed by Pick-a-Best and
Aggregate. Remarkably, the objective value achieved by Algorithm 1 is often
quite close to the lower bound $\mathrm{OPT}_{\mathrm{LP}}$, meaning that the
algorithm tends to obtain a near-optimal solution. As Algorithm 1 solves (LP),
which involves the multilayer structure and thus is more complex than the LP
solved in Aggregate, Algorithm 1 is slower than Aggregate; however, Algorithm
1 is still even faster than Pick-a-Best, as the latter requires to solve $L$
different LPs corresponding to the layers.

The results for Problem 1 with the probability constraint are summarized in
Table 3. Note that for this case, all algorithms except for Algorithm 3 are
performed 10 times, as they contain randomness. OT again indicates that (the
first run of) the algorithm did not terminate in 3,600 seconds. The objective
values are presented using the average value and the standard deviation, while
the running time is just with the average value, because obviously it may not
vary much. The trend of the results is similar to that for the general
weighted case. Indeed, Algorithm 3 with an approximation ratio of $4$
outperforms the baseline methods in terms of the quality of solutions, and the
algorithm succeeds in obtaining near-optimal solutions. Although Algorithm 2
(LP) and Algorithm 2 ($\overline{\text{LP}}$) are also our proposed
algorithms, which have approximation ratios of $4.5$ and $7$, respectively,
their practical performances are not comparable with that of Algorithm 3.
Therefore, we conclude that our proposed algorithm for practical use is
Algorithm 3.

Table 2: Results for Problem 1 of the general weighted case.

|  |  | Algorithm 1 |  | Pick-a-Best |  | Aggregate
---|---|---|---|---|---|---|---
Dataset | LB |  | Obj. val. | Time(s) |  | Obj. val. | Time(s) |  | Obj. val. | Time(s)
sparrow | 13.37 |  | 13.48 | 0.47 |  | 26.79 | 0.34 |  | 13.81 | 0.11
ant | 32.48 |  | 34.30 | 587.94 |  | 42.94 | 1719.11 |  | 47.59 | 48.03
tortoise | 127.14 |  | 151.00 | 2.32 |  | 193.00 | 16.43 |  | 174.00 | 0.91
wildbird | 54.97 |  | 56.50 | 35.78 |  | 98.27 | 129.20 |  | 74.84 | 7.87
weaver | 132.75 |  | 164.00 | 135.22 |  | — | OT |  | 177.00 | 12.19
tortoise-fi | 271.48 |  | 305.00 | 644.07 |  | — | OT |  | 446.00 | 195.40

Table 3: Results for Problem 1 with the probability constraint.

|  |  | Algorithm 2 (LP) |  | Algorithm 2 ($\overline{\text{LP}}$) |  | Algorithm 3 |  |  Aggregate-Pr (LP) |  |  Aggregate-Pr ($\overline{\text{LP}}$)
---|---|---|---|---|---|---|---|---|---|---|---
Dataset | LB |  | Obj. val. | Time(s) |  | Obj. val. | Time(s) |  | Obj. val. | Time(s) |  | Obj. val. | Time(s) |  | Obj. val. | Time(s)
sparrow | 630.8 |  | 635.1$\pm$1.8 | 0.4 |  | 658.0$\pm$1.6 | 0.0 |  | 631.1 | 0.3 |  | 638.1$\pm$1.7 | 0.1 |  | 652.7$\pm$2.1 | 0.0
ant | 3148.2 |  | 3154.5$\pm$0.5 | 1728.4 |  | 3160.7$\pm$1.2 | 1.0 |  | 3150.3 | 674.2 |  | 3154.0$\pm$0.1 | 60.3 |  | 3158.3$\pm$3.4 | 0.0
tortoise | 2387.5 |  | 2683.3$\pm$40.6 | 19.8 |  | 3837.7$\pm$54.6 | 0.0 |  | 2422.5 | 2.9 |  | 2444.5$\pm$13.4 | 0.9 |  | 2601.0$\pm$18.2 | 0.0
wildbird | 9840.2 |  | 9887.9$\pm$2.6 | 142.0 |  | 10077.8$\pm$8.4 | 0.1 |  | 9841.3 | 11.2 |  | 9863.2$\pm$4.7 | 6.2 |  | 9900.9$\pm$17.4 | 0.0
weaver | 24875.7 |  | — | OT |  | 39732.3$\pm$342.5 | 5.3 |  | 24924.5 | 94.1 |  | 24971.5$\pm$0.0 | 10.3 |  | 24971.0$\pm$0.0 | 0.2
tortoise-fi | 77569.5 |  | — | OT |  | 126849.1$\pm$831.5 | 3.2 |  | 77577.5 | 189.5 |  | 77664.7$\pm$5.1 | 123.5 |  | 77740.8$\pm$12.4 | 0.2

##  7 Conclusion

In this paper, we have introduced Multilayer Correlation Clustering, a novel
generalization of Correlation Clustering to the multilayer setting. We first
designed a polynomial-time $O(L\log n)$-approximation algorithm for the
general weighted case. Then, for the probability constraint case, we proposed
a polynomial-time $(\alpha+2)$-approximation algorithm, where $\alpha$ is any
possible approximation ratio for MinDisagree with the probability constraint
or any of its special cases if we consider the corresponding special case of
our problem, and a polynomial-time $4$-approximation algorithm. Computational
experiments using various real-world datasets demonstrate the practical
effectiveness of our proposed algorithms.

Our work opens up several interesting problems. For Problem 1 of the general
weighted case, can we design a polynomial-time algorithm that has an
approximation ratio better than $O(L\log n)$? As Problem 1 contains
MinDisagree as a special case and approximating MinDisagree is known to be
harder than approximating Minimum Multicut [29], it is quite challenging to
obtain an approximation ratio of $o(\log n)$. Therefore, a more reasonable
question is “how much can we make the term $L$ smaller in the current
approximation ratio of $O(L\log n)$?” To answer this, the first step would be
to investigate the integrality gaps of (CV) and (LP). The current integrality
gap of $\Omega(\log n)$, inherited from the LP relaxation used in the $O(\log
n)$-approximation algorithms for MinDisagree [16, 25], leaves the possibility
to improve the approximation ratio of Algorithm 1 to $O(\log n)$. Another
interesting direction is to improve the approximation ratios for Problem 1
with the probability constraint and its special cases. For instance, can we
design a polynomial-time algorithm that has an approximation ratio better than
$4$ for the general case? To this end, one possibility is to improve the
approximation ratio for MinDisagree with the probability constraint from the
current best $2.5$ [5] to some value smaller than $2$. As the integrality gap
of the LP relaxation used in the $2.5$-approximation algorithm (i.e.,
KwikCluster) is known to be $2$ [16], this approach requires to invent a
different technique. Another possibility is to replace the rounding procedure
of Algorithm 3 to that of KwikCluster, but it is not clear how to extend the
analysis focusing on the _bad triplets_ [5] to the multilayer setting. For
Problem 1 of the unweighted case and Problem 1 with the probability constraint
and the triangle inequality constraint, improving the approximation ratio for
the single-layer counterpart directly improves our approximation ratios.
Finally, investigating Multilayer Correlation Clustering in the spirit of
MaxAgree rather than MinDisagree is also an interesting direction. It is worth
mentioning that a closely-related problem called Simultaneous Max-Cut has
recently been studied by Bhangale et al. [11] and Bhangale and Khot [10] from
the approximability and inapproximability points of view, respectively.

## References

  * [1] S. Ahmadi, S. Galhotra, B. Saha, and R. Schwartz.  Fair correlation clustering.  arXiv preprint arXiv:2002.03508, 2020.
  * [2] S. Ahmadi, S. Khuller, and B. Saha.  Min-max correlation clustering via MultiCut.  In IPCO ’19: Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization, pages 13–26, 2019.
  * [3] S. Ahmadian, A. Epasto, R. Kumar, and M. Mahdian.  Fair correlation clustering.  In AISTATS ’20: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 4195–4205, 2020.
  * [4] S. Ahmadian and M. Negahbani.  Improved approximation for fair correlation clustering.  In AISTATS ’23: Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pages 9499–9516, 2023.
  * [5] N. Ailon, M. Charikar, and A. Newman.  Aggregating inconsistent information: Ranking and clustering.  Journal of the ACM, 55(5), 2008.
  * [6] N. Bansal, A. Blum, and S. Chawla.  Correlation clustering.  In FOCS ’02: Proceedings of the 43rd IEEE Annual Symposium on Foundations of Computer Science, pages 238–247, 2002.
  * [7] N. Bansal, A. Blum, and S. Chawla.  Correlation clustering.  Machine learning, 56:89–113, 2004.
  * [8] P. Basaras, G. Iosifidis, D. Katsaros, and L. Tassiulas.  Identifying influential spreaders in complex multilayer networks: A centrality perspective.  IEEE Transactions on Network Science and Engineering, 6(1):31–45, 2019.
  * [9] M. Bazzi, M. A. Porter, S. Williams, M. McDonald, D. J. Fenn, and S. D. Howison.  Community detection in temporal multilayer networks, with an application to correlation networks.  Multiscale Modeling & Simulation, 14(1):1–41, 2016.
  * [10] A. Bhangale and S. Khot.  Simultaneous Max-Cut is harder to approximate than Max-Cut.  In CCC ’20: Proceedings of the 35th Computational Complexity Conference, pages 9:1–9:15, 2020.
  * [11] A. Bhangale, S. Khot, S. Kopparty, S. Sachdeva, and D. Thiruvenkatachari.  Near-optimal approximation algorithm for simultaneous Max-Cut.  In SODA ’18: Proceedings of the 29th Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1407–1425, 2018.
  * [12] F. Bonchi, D. García-Soriano, and F. Gullo.  Correlation Clustering, volume 19 of Synthesis Lectures on Data Mining and Knowledge Discovery.  Morgan & Claypool Publishers, 2022.
  * [13] F. Bonchi, A. Gionis, F. Gullo, C. E. Tsourakakis, and A. Ukkonen.  Chromatic correlation clustering.  ACM Transactions on Knowledge Discovery from Data, 9(4), 2015.
  * [14] F. Bonchi, A. Gionis, F. Gullo, and A. Ukkonen.  Chromatic correlation clustering.  In KDD ’12: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 1321–1329, 2012.
  * [15] M. Charikar, N. Gupta, and R. Schwartz.  Local guarantees in graph cuts and clustering.  In IPCO ’17: Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization, pages 136–147, 2017.
  * [16] M. Charikar, V. Guruswami, and A. Wirth.  Clustering with qualitative information.  Journal of Computer and System Sciences, 71(3):360–383, 2005.
  * [17] S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev.  Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs.  In STOC ’15: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, page 219–228, 2015.
  * [18] Y. Chen, A. Jalali, S. Sanghavi, and H. Xu.  Clustering partially observed graphs via convex optimization.  The Journal of Machine Learning Research, 15(1):2213–2238, 2014\.
  * [19] V. Cohen-Addad, E. Lee, S. Li, and A. Newman.  Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering.  In FOCS ’23: Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, pages 1082–1104, 2023.
  * [20] V. Cohen-Addad, E. Lee, and A. Newman.  Correlation clustering with Sherali-Adams.  In FOCS ’22: Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pages 651–661, 2022.
  * [21] S. Davies, B. Moseley, and H. Newman.  Fast combinatorial algorithms for min max correlation clustering.  In ICML ’23: Proceedings of the 40th International Conference on Machine Learning, pages 7205–7230, 2023.
  * [22] C. De Bacco, E. A. Power, D. B. Larremore, and C. Moore.  Community detection, link prediction, and layer interdependence in multilayer networks.  Physical Review E, 95:042317, 2017.
  * [23] M. De Domenico, C. Granell, M. A. Porter, and A. Arenas.  The physics of spreading processes in multilayer networks.  Nature Physics, 12(10):901–906, 2016.
  * [24] M. De Domenico, A. Solé-Ribalta, E. Omodei, S. Gómez, and A. Arenas.  Ranking in interconnected multilayer networks reveals versatile nodes.  Nature Communications, 6:6868, 2015.
  * [25] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica.  Correlation clustering in general weighted graphs.  Theoretical Computer Science, 361(2):172–187, 2006.
  * [26] X. Z. Fern and C. E. Brodley.  Random projection for high dimensional data clustering: A cluster ensemble approach.  In ICML ’03: Proceedings of the 20th International Conference on Machine Learning, pages 186–193, 2003.
  * [27] Z. Friggstad and R. Mousavi.  Fair correlation clustering with global and local guarantees.  In WADS ’21: Proceedings of the 17th International Symposium on Algorithms and Data Structures, pages 414–427, 2021.
  * [28] E. Galimberti, F. Bonchi, F. Gullo, and T. Lanciano.  Core decomposition in multilayer networks: Theory, algorithms, and applications.  ACM Transactions on Knowledge Discovery from Data, 14(1), 2020.
  * [29] N. Garg, V. V. Vazirani, and M. Yannakakis.  Approximate max-flow min-(multi)cut theorems and their applications.  SIAM Journal on Computing, 25(2):235–251, 1996.
  * [30] A. Gionis, H. Mannila, and P. Tsaparas.  Clustering aggregation.  ACM Transactions on Knowledge Discovery from Data, 1(1), 2007.
  * [31] M. Grötschel and Y. Wakabayashi.  A cutting plane algorithm for a clustering problem.  Mathematical Programming, 45:59–96, 1989.
  * [32] H. Heidrich, J. Irmai, and B. Andres.  A 4-approximation algorithm for min max correlation clustering.  In AISTATS ’24: Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pages 1945–1953, 2024.
  * [33] R. Interdonato, A. Tagarelli, D. Ienco, A. Sallaberry, and P. Poncelet.  Local community detection in multilayer networks.  Data Mining and Knowledge Discovery, 31(5):1444–1479, 2017.
  * [34] M. Jalili, Y. Orouskhani, M. Asgari, N. Alipourfard, and M. Perc.  Link prediction in multiplex online social networks.  Royal Society Open Science, 4(2):160863, 2017.
  * [35] V. Jethava and N. Beerenwinkel.  Finding dense subgraphs in relational graphs.  In ECML PKDD ’15: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 641–654, 2015.
  * [36] T. Joachims and J. Hopcroft.  Error bounds for correlation clustering.  In ICML ’05: Proceedings of the 22nd International Conference on Machine Learning, page 385–392, 2005.
  * [37] S. Kalhan, K. Makarychev, and T. Zhou.  Correlation clustering with local objectives.  In NeurIPS ’19: Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, pages 9341–9350, 2019.
  * [38] Y. Kawase, A. Miyauchi, and H. Sumita.  Stochastic solutions for dense subgraph discovery in multilayer networks.  In WSDM ’23: Proceedings of the 16th ACM International Conference on Web Search and Data Mining, page 886–894, 2023.
  * [39] N. Klodt, L. Seifert, A. Zahn, K. Casel, D. Issac, and T. Friedrich.  A color-blind 3-approximation for chromatic correlation clustering and improved heuristics.  In KDD ’21: Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 882–891, 2021.
  * [40] Y. Kuroki, A. Miyauchi, F. Bonchi, and W. Chen.  Query-efficient correlation clustering with noisy oracle.  arXiv preprint arXiv:2402.01400, 2024.
  * [41] K. Makarychev, Y. Makarychev, and A. Vijayaraghavan.  Correlation clustering with noisy partial information.  In COLT ’15: Proceedings of the 28th Conference on Learning Theory, pages 1321–1342, 2015.
  * [42] C. Mathieu and W. Schudy.  Correlation clustering with noisy input.  In SODA ’10: Proceedings of the 21st Annual ACM–SIAM Symposium on Discrete Algorithms, pages 712–728, 2010.
  * [43] G. Puleo and O. Milenkovic.  Correlation clustering and biclustering with locally bounded errors.  In ICML ’16: Proceedings of the 33rd International Conference on Machine Learning, pages 869–877, 2016.
  * [44] G. J. Puleo and O. Milenkovic.  Correlation clustering and biclustering with locally bounded errors.  IEEE Transactions on Information Theory, 64(6):4105–4119, 2018\.
  * [45] M. Salehi, R. Sharma, M. Marzolla, M. Magnani, P. Siyari, and D. Montesi.  Spreading processes in multilayer networks.  IEEE Transactions on Network Science and Engineering, 2(2):65–83, 2015.
  * [46] R. Schwartz and R. Zats.  Fair correlation clustering in general graphs.  In APPROX/RANDOM ’22: Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation, pages 37:1–37:19, 2022.
  * [47] A. Strehl and J. Ghosh.  Cluster ensembles — A knowledge reuse framework for combining multiple partitions.  Journal of Machine Learning Research, 3:583–617, 2002.
  * [48] A. Tagarelli, A. Amelio, and F. Gullo.  Ensemble-based community detection in multilayer networks.  Data Mining and Knowledge Discovery, 31(5):1506–1543, 2017.