Multilayer Correlation Clustering
Atsushi Miyauchi Florian Adriaens Francesco Bonchi Nikolaj Tatti


Multimodal Semantic-Aware Automatic Colorization with Diffusion Prior
    Lijing Shao
    April 29, 2024
=====================================================================




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 ℓ_p-norm (p≥ 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(Llog 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 (α+2)-approximation algorithm, where α is any possible approximation ratio 
for the single-layer counterpart. 
For instance, we can take α=2.5 in general (Ailon et al., JACM '08) and α=1.73+ϵ for the unweighted case (Cohen-Addad et al., FOCS '23). 
Furthermore, we design a 4-approximation algorithm, which improves the above approximation ratio of α+2=4.5 for the general probability-constraint case. 
Computational experiments using real-world datasets demonstrate the effectiveness of our proposed algorithms. 




§ 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. <cit.>, 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 <cit.> but also APX-hard
even if we consider the unweighted case (i.e., the case where the weights are all equal to 1) <cit.>.
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. <cit.> and Demaine et al. <cit.> independently proposed O(log n)-approximation algorithms,
using the well-known region growing technique <cit.>.
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 <cit.>,
which is one of the major open problems in theoretical computer science.
For the unweighted case, Bansal et al. <cit.> presented the first constant-factor approximation algorithm,
which has been improved by a series of works so far <cit.>.
Notably, the current-best approximation ratio for the unweighted case is 1.73+ϵ for any ϵ >0, which was very recently given by Cohen-Addad et al. <cit.>.
For more details, including approximation algorithms for other special cases or even generalizations, see Section <ref>.



 §.§ 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 ℓ_p-norm (p≥ 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=∞, it quantifies the maximal disagreements over the layers.
For p≥ 1, our problem aims to find a clustering of V that minimizes the ℓ_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 𝕏 (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(Llog n)-approximation algorithm, where L is the number of layers.
Our algorithm is a generalization of the O(log n)-approximation algorithms for MinDisagree <cit.>
and thus employs the region growing technique <cit.>.
Our algorithm first solves a convex programming relaxation of the problem,
particularly a linear programming (LP) relaxation for the case of p=∞.
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(Llog 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 <cit.>.
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 (α+2)-approximation algorithm,
where α 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 α=2.5 in general <cit.>,
α=1.73+ϵ for the unweighted case <cit.>,
and α=1.5 for the case where the weights of `-' labels satisfy the triangle inequality constraint (see Section <ref>) <cit.>.
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≥ 1.
In the problem, given x_1,…, x_L∈ X and a candidate set F⊆ X,
we are asked to find x∈ F that minimizes (∑_ℓ∈ [L]d(x,x_ℓ)^p)^1/p if p<∞ and max_ℓ∈ [L]d(x,x_ℓ) if p=∞.
Intuitively, the problem aims to find the most representative candidate of the given points x_1,…, 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 α+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(Llog 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. <cit.>.
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 <cit.>, thanks to its simplicity and extendability,
the algorithm by Charikar et al. <cit.> has been generalized to various settings of the unweighted case (see Section <ref>).
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 <ref> of the general weighted case and Problem <ref> 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 <ref>).

  * We design an O(Llog n)-approximation algorithm for Problem <ref> (Section <ref>). 

  * For Problem <ref> with the probability constraint, we devise an (α+2)-approximation algorithm, 
where α 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 α+2=4.5 for the general case (Section <ref>). 

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




§ 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. <cit.> 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. <cit.> 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. <cit.> 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. <cit.> demonstrated that
a more sophisticated randomized construction of the clusters achieves a 2.06-approximation <cit.>,
which almost matches the integrality gap of 2 of the LP relaxation <cit.>.
In a recent breakthrough, Cohen-Addad et al. <cit.> designed a (1.994+ϵ)-approximation algorithm for any ϵ >0,
using a semidefinite programming relaxation of the problem, particularly the Sherali–Adams hierarchy.
Very recently, Cohen-Addad et al. <cit.> further improved the approximation ratio to 1.73+ϵ by inventing a novel preprocessing algorithm.

For MinDisagree with the probability constraint,
Bansal et al. <cit.> provided an approximation-preserving reduction from the problem to MinDisagree of the unweighted case.
Specifically, the authors proved that any α-approximation algorithm for MinDisagree of the unweighted case
yields a (2α+1)-approximation algorithm for MinDisagree with the probability constraint.
Ailon et al. <cit.> 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. <cit.>.
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. <cit.> proved that their above algorithms achieve a 2-approximation,
and later Chawla et al. <cit.> improved it to 1.5.

Gionis et al. <cit.> 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. <cit.> 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 ℓ_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. <cit.>, 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 <cit.>. 


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 <cit.> and references therein.

The most related would be Multi-Chromatic Correlation Clustering, introduced by Bonchi et al. <cit.>,
as a further generalization of Chromatic Correlation Clustering <cit.>.
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 ℓ_p-norm of the disagreements vector, which is more easily interpretable;
for example, if we set p=∞, 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. <cit.> 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. <cit.> 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 <cit.> 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∈ V.
The goal is then to minimize the ℓ_p-norm (p≥ 1) of the disagreements vector.
If we set p=1, the problem reduces to MinDisagree of the unweighted case, whereas if we set p=∞, the problem aims to minimize the maximal disagreements over the elements.
The authors proved that the model with p=∞ is NP-hard
and designed a 48-approximation algorithm for any p≥ 1
by extending the 4-approximation algorithm for MinDisagree of the unweighted case, designed by Charikar et al. <cit.>.
Charikar et al. <cit.> then improved the approximation ratio to 7 by inventing a different rounding algorithm.
The contribution of Charikar et al. <cit.> is not limited to the unweighted case;
they also studied the above model with p=∞ of the general weighted case and designed an O(√(n))-approximation algorithm.
Later Kalhan et al. <cit.> improved the above approximation ratio of 7 to 5,
and designed an O(n^1/2-1/2plog^1/2+1/2pn)-approximation algorithm for any p≥ 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) <cit.>, up to a logarithmic factor.
Very recently, Davies et al. <cit.> gave a purely-combinatorial O(n^ω)-time 40-approximation algorithm for p=∞ of the unweighted case, where ω is the exponent of matrix multiplication,
while Heidrich et al. <cit.> improved the above approximation ratio of 5 by Kalhan et al. <cit.> to 4 for p=∞.
Ahmadi et al. <cit.> studied the cluster-wise counterpart of the above model with p=∞ (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. <cit.> significantly improved these approximation ratios to 2+ϵ for any ϵ>0.

Another type of fairness has been considered for Correlation Clustering.
Ahmadian et al. <cit.> 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. <cit.> 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α+4)-approximation algorithm, where α is any known approximation ratio for MinDisagree of the unweighted case.
Friggstad and Mousavi <cit.> then gave an approximation ratio of 6.18, which cannot be achieved by the above 3α+4.
The authors also studied the model with the aforementioned local objective for p=∞ and designed a constant-factor approximation algorithm.
Schwartz and Zats <cit.> proved that the model of Ahmadi et al. <cit.> of the general weighted case has no finite approximation ratio, unless P=NP.
Very recently, Ahmadian et al. <cit.> 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. <cit.>, this type of problem had already been considered,
while Joachims and Hopcroft <cit.> gave the first formal analysis of the problem.
Later, a variety of problem settings have been introduced in a series of works <cit.>.
Very recently, Kuroki et al. <cit.> 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 <cit.>, dense subgraph discovery <cit.>, 
link prediction <cit.>, analyzing spreading processes <cit.>, and identifying central vertices <cit.>. 



§ 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∈ V,  u≠ v}. 
Let L be a positive integer, representing the number of layers.
For each ℓ∈ [L], let w^+_ℓ E→ℝ_≥ 0 and w^-_ℓ E→ℝ_≥ 0 
be the weight functions for `+' and `-' labels, respectively, on that layer.[Note 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^+_ℓ(u,v)=w^+_ℓ({u,v}) and w^-_ℓ(u,v)=w^-_ℓ({u,v}) for ℓ∈ [L] and {u,v}∈ E.
Let 𝒞 be a clustering (i.e., a partition) of V, that is, 𝒞={C_1,…, C_t} such that ⋃_i∈ [t]C_i=V and C_i∩ C_j=∅ for i,j∈ [t] with i≠ j. For v∈ V, we denote by 𝒞(v) the (unique) element (i.e., cluster) in 𝒞 to which v belongs. 
Then, for u,v∈ V, [𝒞(u)=𝒞(v)]=1 if u,v belong to the same cluster and [𝒞(u)≠𝒞(v)]=0 otherwise.
The disagreement of 𝒞 on layer ℓ∈ [L] is defined as the sum of weights of misclassified labels on that layer, i.e., 

    _ℓ(𝒞)=∑_{u,v}∈ E (w^+_ℓ(u,v)[𝒞(u)≠𝒞(v)]+w^-_ℓ(u,v)[𝒞(u)= 𝒞(v)]).

Then the disagreements vector of 𝒞 is defined as

    𝐃𝐢𝐬𝐚𝐠𝐫𝐞𝐞(𝒞) = (_ℓ(𝒞))_ℓ∈ [L].


We are now ready to formulate our problem: 
[Multilayer Correlation Clustering]
Fix p∈ [1,∞].
Given V and (w^+_ℓ, w^-_ℓ)_ℓ∈ [L],
we are asked to find a clustering 𝒞 of V that minimizes 
the ℓ_p-norm of the disagreement vector of 𝒞, i.e., 

    𝐃𝐢𝐬𝐚𝐠𝐫𝐞𝐞(𝒞)_p =
    (∑_ℓ∈ [L]_ℓ(𝒞)^p)^1/p   if  p<∞,
    max_ℓ∈ [L]_ℓ(𝒞)    if  p=∞.



Obviously Problem <ref> 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 <cit.>. 
If we set p=∞, 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^+_ℓ, w^-_ℓ,  
we can assume without loss of generality that at most one of w^+_ℓ(u,v) and w^-_ℓ(u,v) is nonzero for any {i,j}∈ 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. <cit.> for details). 
Following this, we can obtain a more intuitive representation of our problem as follows: 
For each ℓ∈ [L], introduce two mutually-disjoint sets E^+_ℓ={{u,v}∈ E: w^+_ℓ(u,v)>0} and E^-_ℓ={{u,v}∈ E: w^-_ℓ(u,v)>0}, 
and define w_ℓ E^+_ℓ∪ E^-_ℓ→ℝ_>0 
such that w_ℓ({u,v})=w^+_ℓ(u,v) if {u,v}∈ E^+_ℓ and w_ℓ({u,v})=w^-_ℓ(u,v) if {u,v}∈ E^-_ℓ. 
Again we write w_ℓ(u,v)=w_ℓ({u,v}) for ℓ∈ [L] and {u,v}∈ E^+_ℓ∪ E^-_ℓ, for simplicity. 
Then we can rewrite the disagreement of 𝒞 on layer ℓ∈ [L] as 

    _ℓ(𝒞)=∑_{u,v}∈ E^+_ℓw_ℓ(u,v)[𝒞(u)≠𝒞(v)]+∑_{u,v}∈ E^-_ℓw_ℓ(u,v)[𝒞(u)= 𝒞(v)],

which will be used throughout Section <ref>. 


An important special case of Problem <ref> is that 
w^+_ℓ, w^-_ℓ for every layer ℓ∈ [L] satisfy the so-called probability constraint, 
i.e., w^+_ℓ(u,v)+w^-_ℓ(u,v)=1 for any {u,v}∈ E. 
Note that the most fundamental special case, i.e., the unweighted case, is still contained in this case, where w^-_ℓ(u,v)=1-w^+_ℓ(u,v)=0 or 1. 
Another special case, which we also handle in the present paper, is Problem <ref> with the probability constraint and the triangle inequality constraint. 
The additional constraint, i.e., the triangle inequality constraint, stipulates that on every layer ℓ∈ [L], 
w^-_ℓ(u,w)≤ w^-_ℓ(u,v)+w^-_ℓ(v,w) holds for any distinct u,v,w∈ V.
It is easy to see that in the case of p=1, Problem <ref> 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 <cit.> in the probability constraint case 
and 1.5-approximable <cit.> in the probability constraint and triangle inequality constraint case. 
However, even if we consider the quite special case, Problem <ref> of the unweighted case, there is no trivial reduction that can beat the above 2.5-approximation. 




§ ALGORITHM FOR PROBLEM <REF>


In this section, we design an O(Llog n)-approximation algorithm for Problem <ref>. 
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 <ref>, we assume without loss of generality that at most one of w^+_ℓ(i,j) and w^-_ℓ(i,j) is nonzero for each {i,j}∈ E, 
and employ the latter representation of our problem given there. 



 §.§ The proposed algorithm

We first present 0–1 convex programming formulations for Problem <ref>. 
For distinct i,j∈ 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<∞, Problem <ref> can be formulated as follows: 

   minimize           (∑_ℓ∈[L](∑_{i,j}∈E^+_ℓw_ℓ(i,j)x_ij+∑_{i,j}∈E^-_ℓw_ℓ(i,j)(1-x_ij))^p)^1/p

   subject to           x_ij=x_ji   (∀i,j∈V, i≠j),

                               x_ik≤x_ij+x_jk   (∀i,j,k∈V, i≠j,  j≠k,  k≠i),

                               x_ij∈{0,1}         (∀i,j∈V, i≠j).

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

   minimize           t

   subject to           ∑_{i,j}∈E^+_ℓw_ℓ(i,j)x_ij+∑_{i,j}∈E^-_ℓw_ℓ(i,j)(1-x_ij) ≤t   (∀ℓ∈[L]),

                               x_ij=x_ji   (∀i,j∈V, i≠j),

                               x_ik≤x_ij+x_jk   (∀i,j,k∈V, i≠j,  j≠k,  k≠i),

                               x_ij∈{0,1}         (∀i,j∈V, i≠j).

For the above formulations, by relaxing the constraints x_ij∈{0,1} to x_ij∈ [0,1] for all distinct i,j∈ V, 
we can obtain continuous relaxations of Problem <ref>, which we refer to as (CV) and (LP), respectively. 
Let x=(x_ij)_i,j∈ V: i≠ 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(x)) = f(g_1(x),…, g_L(x)), 
where fℝ_≥ 0^L→ℝ_≥ 0 is an ℓ_p-norm of p≥ 1, which is convex and non-decreasing in each argument, 
and g_ℓℝ_≥ 0^E→ℝ_≥ 0 is linear and thus convex for every ℓ∈ [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 OPT_CV and OPT_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 x^*=(x^*_ij)_i,j∈ V:  i≠ j. 
Then the algorithm introduces x^*=(x^*_ij)_i,j∈ V by setting x^*_ii=0 for every i∈ V. 
Obviously 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 x^*=(x^*_ij)_i,j∈ V is a pseudometric over V. 
Let V be an arbitrary subset of V. 
For i∈V and r≥ 0, 
we denote by B_V(i,r) the open ball of center i and radius r in V, i.e., 

    B_V(i,r)={j∈V:x^*_ij<r}.

For B_V(i,r), we define its cut value cut_(V,ℓ)(B_V(i,r)) within V on layer ℓ∈ [L] as the sum of weights of `+' labels across B_V(i,r) and V∖ B_V(i,r) on layer ℓ∈ [L] , i.e., 

    cut_(V,ℓ)(B_V(i,r))
    =∑_{j,k}∈ E^+_ℓ: j∈ B_V(i,r) k∈V∖ B_V(i,r)w_ℓ(j,k).

For B_V(i,r), we define its volume vol_(V,ℓ)(B_V(i,r)) within V on layer ℓ∈ [L] as 

    vol_(V,ℓ)(B_V(i,r))
    =F_ℓ/n+∑_{j,k}∈ E^+_ℓ:  j,k∈ B_V(i,r)w_ℓ(j,k)x^*_jk
    +∑_{j,k}∈ E^+_ℓ: j∈ B_V(i,r) k∈V∖ B_V(i,r)w_ℓ(j,k)(r-x^*_ij),

where F_ℓ=∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk. 

Based on the above notations, the pseudocode of our algorithm is presented in Algorithm <ref>. 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 ℓ∈ [L] with F_ℓ≠ 0. 






 §.§ Analysis of Algorithm <ref>

Here we prove that Algorithm <ref> is a polynomial-time O(Llog n)-approximation algorithm for Problem <ref>. 
To this end, we have the following key lemma, verifying the effectiveness of the radius determined by the algorithm: 

In Algorithm <ref>, for any t=1,…, |ℬ|, it holds that  

    max_ℓ∈ [L]: F_ℓ≠ 0cut_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t)))/vol_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t)))≤ cLlog(n+1),

and moreover, B_V^(t)(i^(t),r^*_(t)) can be computed in polynomial time. 


Fix t∈{1,…, |ℬ|}. 
For simplicity, for any r∈ [0,1/c], 
we write B_V^(t)(i^(t),r)=B(r), 
and moreover, for any ℓ∈ [L], 
cut_(V^(t),ℓ)(B_V^(t)(i^(t),r))=cut_ℓ(r) 
and vol_(V^(t),ℓ)(B_V^(t)(i^(t),r))=vol_ℓ(r). 
By the definition of r^*_(t), it suffices to show that there exists r∈ (0,1/c] that satisfies 

    max_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r)≤ cLlog(n+1).

Suppose, for contradiction, that for any r∈ (0,1/c], 

    max_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r)> cLlog(n+1).

Then we have 

    ∫_0^1/cmax_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r) dr
    >∫_0^1/ccLlog(n+1) dr
    =Llog(n+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,…, j_q-1 in the increasing order of the distance. 
For each p=0,…, 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 ℓ∈ [L], the function vol_ℓ(r) is not necessarily differentiable and even not necessarily continuous at r_0,…, r_q. 
On the other hand, at any point r∈ (0,1/c] except for r_1,…, r_q, the function vol_ℓ(r) is differentiable, 
and from the definition, we have 

    d vol_ℓ(r)/dr=cut_ℓ(r).

Moreover, by simple calculation, we have that for any ℓ∈ [L] with F_ℓ≠ 0, 

    vol_ℓ(1/c)/vol_ℓ(0)≤ n+1.

Indeed, we see that vol_ℓ(0)=F_ℓ/n and 

    vol_ℓ(1/c)
       =F_ℓ/n+∑_{j,k}∈ E^+_ℓ: j,k∈ B(1/c)w_ℓ(j,k)x^*_jk
    +∑_{j,k}∈ E^+_ℓ: j∈ B(1/c) k∈ V^(t)∖ B(1/c)w_ℓ(j,k)(1/c-x^*_i^(t)j)
       ≤F_ℓ/n+∑_{j,k}∈ E^+_ℓ: j∈ B(1/c) k∈ V^(t)w_ℓ(j,k)x^*_jk
       ≤F_ℓ/n+F_ℓ,

where the first inequality follows from 

    1/c-x^*_i^(t)j≤ x^*_i^(t)k-x^*_i^(t)j≤ x^*_i^(t)j+x^*_jk-x^*_i^(t)j=x^*_jk

for any {j,k}∈ E^+_ℓ such that j∈ B(1/c) and k∈ V^(t)∖ B(1/c).  
Using Equality (<ref>) and Inequality (<ref>), we have 

    ∫_0^1/cmax_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r) dr
       ≤∑_ℓ∈ [L]: F_ℓ≠ 0∫_0^1/ccut_ℓ(r)/vol_ℓ(r) dr
       = ∑_ℓ∈ [L]: F_ℓ≠ 0∑_p=0^q-1∫_r_p^r_p+1cut_ℓ(r)/vol_ℓ(r) dr
       = ∑_ℓ∈ [L]: F_ℓ≠ 0∑_p=0^q-1∫_r_p^r_p+11/vol_ℓ(r) d vol_ℓ(r)
       = ∑_ℓ∈ [L]: F_ℓ≠ 0∑_p=0^q-1(logvol_ℓ(r_p+1)-logvol_ℓ(r_p))
       = ∑_ℓ∈ [L]: F_ℓ≠ 0logvol_ℓ(1/c)/vol_ℓ(0)
       ≤ Llog(n+1),

where the first inequality follows from the fact that cut_ℓ(r)/vol_ℓ(r) is nonnegative for any ℓ∈ [L] with F_ℓ≠ 0 and r∈ (0,1/c]. 
The above contradicts Inequality (<ref>), meaning that there exists r∈ (0,1/c] such that 

    max_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r)≤ cLlog(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)∈{max_ℓ∈ [L]: F_ℓ≠ 0cut_ℓ(r)/vol_ℓ(r): r∈ (0,1/c]} can be computed in polynomial time. 
Recall the relabeling of the elements in V^(t). 
For any p=0,…,q-1, in the interval (r_p,r_p+1], 
the function cut_ℓ(r)/vol_ℓ(r) for any ℓ∈ [L] is monotonically nonincreasing, 
and thus so is max_ℓ∈ [L]cut_ℓ(r)/vol_ℓ(r). 
Indeed, in that interval, cut_ℓ(r) is unchanged, while vol_ℓ(r) is monotonically nondecreasing. 
Therefore, it suffices to compute max_ℓ∈ [L]cut_ℓ(r)/vol_ℓ(r) for all r=r_1,…, 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: 

Algorithm <ref> is a polynomial-time O(Llog n)-approximation algorithm for Problem <ref>. 


By Lemma <ref>, it is trivial that Algorithm <ref> runs in polynomial time. 
Therefore, in what follows, we analyze the approximation ratio. 
Letting ℬ be the output of the algorithm, we need to evaluate 

    _ℓ(ℬ)_p=
    (∑_ℓ∈ [L](∑_{j,k}∈ E^+_ℓw_ℓ(j,k)[ℬ(j)≠ℬ(k)]+∑_{j,k}∈ E^-_ℓw_ℓ(j,k)[ℬ(j)=ℬ(k)])^p)^1/p
    if  p<∞,
    max_ℓ∈ [L](∑_{j,k}∈ E^+_ℓw_ℓ(j,k)[ℬ(j)≠ℬ(k)]+∑_{j,k}∈ E^-_ℓw_ℓ(j,k)[ℬ(j)=ℬ(k)]) 
    if p=∞.


We first evaluate the terms for `+' labels. 
By Lemma <ref>, we have that for any ℓ∈ [L] with F_ℓ≠ 0, 

    cut_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t)))≤ cLlog(n+1)·vol_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t))).

Based on this, for any ℓ∈ [L] with F_ℓ≠ 0, we have 

    ∑_{j,k}∈ E^+_ℓw_ℓ(j,k)[ℬ(j)≠ℬ(k)]
       =∑_t=1^|ℬ|cut_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t)))
       ≤ cLlog(n+1)∑_t=1^|ℬ|vol_(V^(t),ℓ)(B_V^(t)(i^(t),r^*_(t)))
       ≤ cLlog(n+1)(F_ℓ/n· |ℬ| + ∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk)
       ≤ 2cLlog(n+1)∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk.

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

    ∑_{u,v}∈ E^+_ℓw_ℓ(u,v)[ℬ(u)≠ℬ(v)]=0.


Next we evaluate the terms for `-' labels. For any ℓ∈ [L], we have 

    ∑_{j,k}∈ E^-_ℓw_ℓ(j,k)[ℬ(j)=ℬ(k)]
       =c/c-2∑_t=1^|ℬ|∑_{j,k}∈ E^-_ℓ: j,k∈ B_V^(t)(i^(t),r^*_(t))w_ℓ(j,k)(1-2/c)
       ≤c/c-2∑_t=1^|ℬ|∑_{j,k}∈ E^-_ℓ: j,k∈ B_V^(t)(i^(t),r^*_(t))w_ℓ(j,k)(1-x^*_jk)
       ≤c/c-2∑_{j,k}∈ E^-_ℓw_ℓ(j,k)(1-x^*_jk),

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≤ x^*_ji^(t)+x^*_i^(t)k<2/c. 

Let OPT be the optimal value of Problem <ref>. 
Using Inequality (<ref>), Equality (<ref>), and Inequality (<ref>), 
we have that in the case of p<∞, 

    _ℓ(ℬ)_p 
       ≤(∑_ℓ∈ [L](2cLlog(n+1)∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk
    +c/c-2∑_{j,k}∈ E^-_ℓw_ℓ(j,k)(1-x^*_jk))^p)^1/p
       ≤max{2cLlog(n+1), c/c-2}(∑_ℓ∈ [L](∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk+∑_{j,k}∈ E^-_ℓw_ℓ(j,k)(1-x^*_jk))^p)^1/p
       = max{2cLlog(n+1), c/c-2}OPT_CV
       ≤max{2cLlog(n+1), c/c-2}OPT,

and in the case of p=∞, 

    _ℓ(ℬ)_p 
       ≤max_ℓ∈ [L](2cLlog(n+1)∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk
    +c/c-2∑_{j,k}∈ E^-_ℓw_ℓ(j,k)(1-x^*_jk))
       ≤max{2cLlog(n+1), c/c-2}max_ℓ∈ [L](∑_{j,k}∈ E^+_ℓw_ℓ(j,k)x^*_jk+∑_{j,k}∈ E^-_ℓw_ℓ(j,k)(1-x^*_jk))
       = max{2cLlog(n+1), c/c-2}OPT_LP
       ≤max{2cLlog(n+1), c/c-2}OPT.

Noting that max{2cLlog(n+1), c/c-2}=O(Llog 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 Ω(log n) <cit.>. 
As our relaxations, (CV) and (LP), are generalizations of the above LP relaxation, the integrality gap of Ω(log n) is inherited. 
This matches our approximation ratio in the case of L=O(1) but there remains a gap in general. 




§ ALGORITHMS FOR PROBLEM <REF> WITH PROBABILITY CONSTRAINT


In this section, we present our algorithms for Problem <ref> with the probability constraint. 
The first algorithm has an approximation ratio of (α+2), where α 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. 



 §.§ The (α+2)-approximation algorithm

To design the algorithm, we reduce Problem <ref> with the probability constraint to a novel optimization problem in a metric space. 
Let X be a set. 
Let d  X× X→ℝ_≥ 0 be a metric on V, 
i.e., d(x,y)=0 if and only if x=y for x,y∈ V, d(x,y)=d(y,x) for x,y∈ V, and d(x,z)≤ d(x,y)+d(y,z) for x,y,z∈ V. 
In general, (X,d) is called a metric space. 
We introduce the following problem: 
[Find the Most Representative Candidate in a Metric Space]
Fix p≥ 1. 
Let (X,d) be a metric space.
Given x_1,…, x_L ∈ X and a candidate set F⊆ X, 
we are asked to find x∈ F that minimizes (∑_ℓ∈ [L]d(x,x_ℓ)^p)^1/p if p<∞ and max_ℓ∈ [L]d(x,x_ℓ) if p=∞. 


Then we can prove the following key lemma. 
The proof is based on the fact that each layer of the input of Problem <ref> 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. 

There exists a polynomial-time approximation-preserving reduction from Problem <ref> with the probability constraint to Problem <ref>. 


Fix p≥ 1. 
Let V and (w^+_ℓ,w^-_ℓ)_ℓ∈ [L] be the input of Problem <ref> with the probability constraint, 
satisfying w^+_ℓ(u,v)+w^-_ℓ(u,v)=1 for any ℓ∈ [L] and {u,v}∈ E. 
We construct an instance of Problem <ref> as follows: 
Let X = [0,1]^E and d X× X→ℝ_≥ 0 be a metric such that d(x,y)x-y_1 for x,y∈ X. 
For x∈ X and {u,v}∈ E, we denote by x(u,v) the element of x associated with {u,v}. 
For each ℓ∈ [k], let x_ℓ∈ X be the element such that x_ℓ(u,v)=w^-_ℓ(u,v) for {u,v}∈ E. 
Let F={x∈{0,1}^E : 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}∈ 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∈ F 
and let 𝒞_x be the clustering corresponding to x. 
Then we have that for any ℓ∈ [L], 

    d(x,x_ℓ)   =x-x_ℓ_1
       =∑_{u,v}∈ E((1-w^-_ℓ(u,v))[𝒞_x(u)≠𝒞_x(v)]+w^-_ℓ(u,v)[𝒞_x(u)=𝒞_x(v)])
       =∑_{u,v}∈ E(w^+_ℓ(u,v)[𝒞_x(u)≠𝒞_x(v)]+w^-_ℓ(u,v)[𝒞_x(u)=𝒞_x(v)])
       =_ℓ(𝒞_x),

meaning that the objective function of Problem <ref> is equivalent to that of Problem <ref> with the probability constraint. 
Therefore, x is a β-approximate solution to Problem <ref> 
if and only if so is 𝒞_x to Problem <ref> 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 <ref>, 
resulting in an approximation algorithm for Problem <ref> 
with the probability constraint with the same approximation ratio. 
To this end, we introduce the following subproblem: 
[Find the Closest Candidate in a Metric Space]
Let (X,d) be a metric space. 
Given x ∈ X and a candidate set F⊆ X, we are asked to find x'∈ F that minimizes d(x,x'). 


Assume now that we have an α-approximation algorithm for Problem <ref>. 
Let x_1,…, x_L∈ X and F⊆ X be the input of Problem <ref>. 
Our approximation algorithm for Problem <ref> runs as follows: 
For every ℓ∈ [L], the algorithm obtains an α-approximate solution x'_ℓ∈ F 
for Problem <ref> with input x_ℓ∈ X and F⊆ X, 
using the α-approximation algorithm for Problem <ref>.
Then the algorithm outputs the best solution among x'_1,…, x'_L 
in terms of the objective function of Problem <ref>. 
The pseudocode is given in Algorithm <ref>. 






 §.§ Analysis of Algorithm <ref>


The following theorem gives the approximation ratio of Algorithm <ref>. 

Algorithm <ref> is an (α+2)-approximation algorithm for Problem <ref>. 


Let x^*∈ F be an optimal solution to Problem <ref>. 
Let x_closest∈_x∈{x_1,…,x_L}d(x,x^*) 
and x'_closest be the α-approximate solution for Problem <ref> with input x_closest and F. 
By the definition of x'_closest and x_closest, we have that for any ℓ∈ [L], 

    d(x'_closest,x_closest)≤α· d(x^*,x_closest)≤α· d(x^*,x_ℓ).

Using these inequalities, we have that for any ℓ∈ [L], 

    d(x'_closest,x_ℓ)
       ≤ d(x'_closest,x^*) + d(x^*,x_ℓ)
       ≤ d(x'_closest,x_closest) + d(x_closest,x^*) + d(x^*,x_ℓ)
       ≤α· d(x^*,x_ℓ)  + d(x^*,x_ℓ) + d(x^*,x_ℓ)
       =(α+2)· d(x^*,x_ℓ),

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_closest. 
Noticing that x'_closest is one of the output candidates of Algorithm <ref>, 
we can upper bound the objective value of the output x_out as follows: 
In the case of p<∞, 

    (∑_ℓ∈ [L]d(x_out,x_ℓ)^p)^1/p≤(∑_ℓ∈ [L]d(x'_closest,x_ℓ)^p)^1/p≤ (α+2)(∑_ℓ∈ [L]d(x^*,x_ℓ)^p)^1/p,

while in the case of p=∞, 

    max_ℓ∈ [L]d(x_out,x_ℓ)
    ≤max_ℓ∈ [L]d(x'_closest,x_ℓ)≤ (α+2)max_ℓ∈ [L]d(x^*,x_ℓ),

which concludes the proof. 



In Algorithm <ref>, the approximation ratio α for Problem <ref> that we can take 
depends on the metric space (X,d) and part of input F⊆ X, inherited from Problem <ref>. 
By interpreting Problem <ref> with the probability constraint (or any of its special cases) 
as Problem <ref> with specific metric space (X,d) and part of input F⊆ X, 
we can obtain the following series of approximability results: 

There exists a polynomial-time 4.5-approximation algorithm for Problem <ref> with the probability constraint. 


By Lemma <ref>, 
it suffices to show that there exists a polynomial-time 4.5-approximation algorithm for Problem <ref> 
with the metric space (X,d) and the part of input F⊆ X that correspond to Problem <ref> with the probability constraint. 
By Theorem <ref>, Algorithm <ref> is an (α+2)-approximation algorithm for Problem <ref>, where α is the approximation ratio of the algorithm employed for solving Problem <ref> with those (X,d) and F⊆ X. 
Based on the reduction in the proof of Lemma <ref>, 
Problem <ref> with those (X,d) and F⊆ X is equivalent to MinDisagree with the probability constraint, 
for which there exists a polynomial-time 2.5-approximation algorithm <cit.>. Therefore, we have the corollary. 



For any ϵ>0, there exists a polynomial-time (3.73+ϵ)-approximation algorithm for Problem <ref> of the unweighted case. 


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



There exists a polynomial-time 3.5-approximation algorithm for Problem <ref> with the probability constraint and the triangle inequality constraint. 


The proof is again similar. 
In this case, we can specialize the reduction by replacing X=[0,1]^E with X={x∈ [0,1]^E: x(u,w)≤ x(u,v)+x(v,w), ∀ u,v,w∈ V}, 
and we see that Problem <ref> with (X,d) and F⊆ 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 <cit.>. 







 §.§ 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. <cit.>. 
As in Section <ref>, we first introduce 0–1 convex programming formulations for Problem <ref>.
In the case of p<∞, Problem <ref> can be formulated as follows:

   minimize           (∑_ℓ∈[L](∑_{i,j}∈E(w^+_ℓ(i,j)x_ij+w^-_ℓ(i,j)(1-x_ij)))^p)^1/p

   subject to           x_ij=x_ji   (∀i,j∈V, i≠j),

                               x_ik≤x_ij+x_jk   (∀i,j,k∈V, i≠j,  j≠k,  k≠i),

                               x_ij∈{0,1}         (∀i,j∈V, i≠j).

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

   minimize           t

   subject to           ∑_{i,j}∈E(w^+_ℓ(i,j)x_ij+w^-_ℓ(i,j)(1-x_ij)) ≤t   (∀ℓ∈[L]),

                               x_ij=x_ji   (∀i,j∈V, i≠j),

                               x_ik≤x_ij+x_jk   (∀i,j,k∈V, i≠j,  j≠k,  k≠i),

                               x_ij∈{0,1}         (∀i,j∈V, i≠j).

As in Section <ref>, 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 OPT_CV-Pr and OPT_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 x^*=(x^*_ij)_i,j∈ V: i≠ j. Then the algorithm introduces x^*=(x^*_ij)_i,j∈ V by setting x^*_ii=0 for every i∈ V. Based on the pseudometric x^* over V, the algorithm constructs a clustering, using a simple thresholding rule. 
Let V be an arbitrary subset of V. 
For i∈V and r≥ 0, we denote by B_V(i,r) the closed ball of center i and radius r in V, i.e., 

    B_V(i,r)={j∈V:x^*_ij≤ r}.

Our algorithm initially set V=V. 
In each iteration, the algorithm takes an arbitrary element i∈V and initializes a cluster B= {i}. 
Then the algorithm constructs C=B_V(i,1/2)∖{i}. 
If the average distance between i and the elements in C is less than 1/4, i.e., 1/|C|∑_j∈ Cx^*_ij<1/4, 
then the algorithm updates B by adding all elements in C. 
The algorithm removes B from V as a cluster of the output, and repeats this procedure until V=∅. 
The pseudocode is written in Algorithm <ref>. 







 §.§ Analysis of Algorithm <ref>

The following theorem gives the approximation ratio of Algorithm <ref>.



Algorithm <ref> is a 4-approximation algorithm for Problem <ref> with the probability constraint.


It suffices to prove that for any layer ℓ∈ [L], it holds that

    _ℓ(ℬ) ≤ 4 ∑_{i,j}∈ E(w^+_ℓ(i,j)x^*_ij+w^-_ℓ(i,j)(1-x^*_ij)).

Indeed, from this inequality, it follows that 
𝐃𝐢𝐬𝐚𝐠𝐫𝐞𝐞(ℬ)_p ≤ 4·OPT_CV-Pr if p<∞ 
and 𝐃𝐢𝐬𝐚𝐠𝐫𝐞𝐞(ℬ)_p ≤ 4·OPT_LP-Pr if p=∞, 
which proves the theorem.
Fix ℓ∈ [L] and consider an arbitrary iteration of the while-loop in Algorithm <ref>. 
Let B⊆V be the cluster produced in the iteration. 
We define the cost of B as the contribution of all pairs of elements in V 
with at least one of them being inside B to the objective value, 
i.e., ∑_{j,k}∈ E: j,k∈ Bw^-_ℓ(j,k)+∑_{j,k}∈ E: j∈ B k∈V∖ Bw^+_ℓ(j,k). 
In what follows, we upper bound the cost of B using the corresponding terms in the right-hand-side of Inequality (<ref>). 
Recall that C=B_V(i,1/2)∖{i} contains all elements in 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., 1/|C|∑_j ∈ C x^*_ij≥ 1/4, then the algorithm forms the singleton cluster B={i}.
In this case, the cost of the cluster reduces to ∑_j ∈V∖{i} w^+_ℓ(i,j). 
For each j∈V∖{i} with x^*_ij>1/2, 
we can upper bound each w^+_ℓ(i,j) using the corresponding term in the right-hand-side of Inequality (<ref>)
because it holds that w^+_ℓ(i,j) ≤ 2· w^+_ℓ(i,j)x^*_ij≤ 2(w^+_ℓ(i,j)x^*_ij+w^-_ℓ(i,j)(1-x^*_ij)).
On the other hand, consider any pair of elements for which x^*_ij≤ 1/2 holds, i.e., the element j is contained in C. 
Then, it holds that 1-x^*_ij≥ x^*_ij, and thus we have 

    ∑_j ∈ C(w^+_ℓ(i,j)x^*_ij+w^-_ℓ(i,j)(1-x^*_ij)) 
    ≥∑_j ∈ C(w^+_ℓ(i,j)+w^-_ℓ(i,j))x^*_ij 
    = ∑_j ∈ C x^*_ij,

where the equality follows from the probability constraint. 
Using the above inequality together with the assumption 1/|C|∑_j ∈ C x^*_ij≥ 1/4, we have 

    ∑_j ∈ C w^+_ℓ(i,j) ≤ |C| 
    ≤ 4 ∑_j ∈ C x^*_ij≤ 4 ∑_j ∈ C(w^+_ℓ(i,j)x^*_ij+w^-_ℓ(i,j)(1-x^*_ij)).


(ii) The second case is when the average satisfies 1/|C|∑_j ∈ C x^*_ij < 1/4, 
where the algorithm forms the cluster B = {i}∪ C.
For the sake of the proof, we assume that the elements in 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 ∑_{j,k}∈ E: j,k∈ B w^-_ℓ(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≥ 1/4, 
and therefore each w^-_ℓ(j,k) can be upper bounded by the corresponding term 
in the right-hand-side of Inequality (<ref>) within a factor of 4.
The cost of B charged by the remaining pairs of elements j,k∈ B with j<k can be taken into account by k. 
Obviously we have x^*_ik∈ [3/8,1/2]. 
For a fixed k, define the quantities p_k = ∑_j<k w^+_ℓ(j,k) and n_k = ∑_j<k w^-_ℓ(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 (<ref>) 
can be lower bounded as follows: 

    ∑_j<k(w^+_ℓ(j,k)x^*_jk+w^-_ℓ(j,k)(1-x^*_jk)) 
       ≥∑_j<k(w^+_ℓ(j,k)(x^*_ik-x^*_ij)+w^-_ℓ(j,k)(1-x^*_ik-x^*_ij)) 
       = p_k x^*_ik+n_k(1-x^*_ik) -∑_j<kx^*_ij
       ≥ p_k x^*_ik+n_k(1-x^*_ik)-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≥ 3/8 for any j≥ k. 
Therefore, the above is lower bounded by a linear function depending on x^*_ik∈ [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∈V with exactly one element being contained in B={i}∪ C. 
Without loss of generality, we assume that j<k and thus we have j∈ B, k∈V∖ B, and x^*_ij<x^*_ik. 
The cost of B charged by these pairs is ∑_{j,k}∈ E: j∈ B k∈V∖ B w^+_ℓ(j,k). 
If x^*_ik≥ 3/4 holds, then x^*_ik-x^*_ij≥ 1/4. 
Using the triangle inequality over the pseudometric, we have x^*_jk≥ 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∈ (1/2,3/4). 
For a fixed k, redefine the quantities p_k = ∑_j<k: j∈ B w^+_ℓ(j,k) and n_k = ∑_j<k: j∈ B w^-_ℓ(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. <cit.>, 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 <ref>). 
Our analysis implies that those results may be further generalized form the unweighted case to the probability constraint case. 




§ 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. 



 §.§ Experimental setup




Datasets.
Throughout the experiments, we set p=∞ in Problem <ref>, 
meaning that we aim to minimize the maximal disagreements over all layers. 
Table <ref> 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 Repository[<https://networkrepository.com/index.php>]. 
Using the datasets, we generated our instances of Problem <ref>. 
Let G=(V,(E_ℓ,w_ℓ)_ℓ∈ [L]) be a multilayer network at hand, 
where E_ℓ is the set of edges on layer ℓ and w_ℓ E_ℓ→ℝ_>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_ℓ({u,v})← w_ℓ({u,v})/w_max for every ℓ∈ [L] and {u,v}∈ E_ℓ, 
where w_max=max_ℓ∈ [L]max_{u,v}∈ E_ℓw_ℓ({u,v}). 
For every ℓ∈ [L], let (ℓ) be the multiset of all edge weights on layer ℓ, 
i.e., (ℓ)={w_ℓ({u,v}): {u,v}∈ E_ℓ}. 
We generate our instance V and (w^+_ℓ,w^-_ℓ)_ℓ∈ [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∈ V,  u≠ v}. 

First let us consider Problem <ref> of the general weighted case. 
For each layer ℓ∈ [L] and {u,v}∈ E, 
if {u,v}∈ E_ℓ we set w^+_ℓ(u,v)=w_ℓ({u,v}) and w^-_ℓ(u,v)=0; 
otherwise we set w^+_ℓ(u,v)=0 and w^-_ℓ(u,v)=((ℓ)) with probability 0.5, 
where () takes an element from a given multiset uniformly at random, 
and w^+_ℓ(u,v)=w^-_ℓ(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 <ref> with the probability constraint. 
In this case, the instances are generated with the same intuition as above. 
For each layer ℓ∈ [L] and {u,v}∈ E, 
if {u,v}∈ E_ℓ we set w^+_ℓ(u,v)=0.5+w_ℓ({u,v})/2 and w^-_ℓ(u,v)=1-w^+_ℓ(u,v); 
otherwise we set w^+_ℓ(u,v)=1-w^-_ℓ(u,v), where w^-_ℓ(u,v)=0.5+((ℓ))/2 with probability 0.5, 
and w^+_ℓ(u,v)=w^-_ℓ(u,v)=0.5 otherwise. 

Our algorithms and baselines.
For Problem <ref> of the general weighted case, we run Algorithm <ref>. 
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: 


  * . This method first solves MinDisagree on each layer, 
using the state-of-the-art O(log n)-approximation algorithms <cit.>, 
and then outputs the best one among them in terms of the objective value of Problem <ref>. 
This method can be seen as a generalization of Algorithm <ref> for Problem <ref> with the probability constraint case, 
but it is not clear if the method has an approximation ratio such as O(Llog n), achieved by Algorithm <ref>. 

  * . This method first aggregates the layers. 
Specifically, the method constructs w^+ E→ℝ_≥ 0 and w^- E→ℝ_≥ 0 by setting 
w^+(u,v)=∑_ℓ∈ [L]w^+_ℓ(u,v) and w^-(u,v)=∑_ℓ∈ [L]w^-_ℓ(u,v) for every {u,v}∈ E. 
Then it solves MinDisagree with input V and (w^+,w^-), using the O(log n)-approximation algorithms <cit.>. 
As mentioned in Section <ref>, this method gives an O(log n)-approximate solution for Problem <ref> when p=1, 
but the approximation ratio for the case of p=∞ is not clear. 


For Problem <ref> with the probability constraint, we run Algorithms <ref> and <ref>. 
Note that Algorithm <ref> 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. <cit.>, 
providing the approximation ratios of 4.5 and 7, respectively, of Algorithm <ref>. 
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 <ref> (LP) and Algorithm <ref> (LP), respectively. 
In Algorithm <ref>, the way to select a pivot is arbitrary, and we use the same rule as the above. 
We employ the following baseline method: 


  * . This method is the probability-constraint counterpart of the above . 
Specifically, the method constructs w^+ E→ℝ_≥ 0 and w^- E→ℝ_≥ 0 by setting 
w^+(u,v)=(∑_ℓ∈ [L]w^+_ℓ(u,v))/L and w^-(u,v)=(∑_ℓ∈ [L]w^-_ℓ(u,v))/L for every {u,v}∈ 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 <cit.>, as in Algorithm <ref>. 
We refer to this baseline as  (LP) or  (LP), depending on the choice of the above approximation algorithm. 
As mentioned in Section <ref>, 
 (LP) gives a 2.5-approximate solution for Problem <ref> with the probability constraint when p=1, 
but the approximation ratio for the case of p=∞ is not clear. 


Finally we mention the implementation of the LPs. 
All LPs to be solved by the algorithms have the Θ(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 <cit.>.
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.  




 §.§ Results

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

The results for Problem <ref> with the probability constraint are summarized in Table <ref>. 
Note that for this case, all algorithms except for Algorithm <ref> 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 <ref> 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 <ref> (LP) and Algorithm <ref> (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 <ref>. 
Therefore, we conclude that our proposed algorithm for practical use is Algorithm <ref>. 









§ 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(Llog n)-approximation algorithm for the general weighted case. 
Then, for the probability constraint case, we proposed a polynomial-time (α+2)-approximation algorithm, 
where α 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 <ref> of the general weighted case, 
can we design a polynomial-time algorithm that has an approximation ratio better than O(Llog n)?
As Problem <ref> contains MinDisagree as a special case 
and approximating MinDisagree is known to be harder than approximating Minimum Multicut <cit.>, 
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(Llog n)?”
To answer this, the first step would be to investigate the integrality gaps of (CV) and (LP). 
The current integrality gap of Ω(log n), 
inherited from the LP relaxation used in the O(log n)-approximation algorithms for MinDisagree <cit.>, 
leaves the possibility to improve the approximation ratio of Algorithm <ref> to O(log n). 
Another interesting direction is to improve the approximation ratios for Problem <ref> 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 <cit.> 
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 <cit.>, 
this approach requires to invent a different technique. 
Another possibility is to replace the rounding procedure of Algorithm <ref> to that of KwikCluster, 
but it is not clear how to extend the analysis focusing on the bad triplets <cit.> to the multilayer setting. 
For Problem <ref> of the unweighted case and Problem <ref> 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. <cit.> and Bhangale and Khot <cit.> from the approximability and inapproximability points of view, respectively. 


abbrv


