In this paper, we establish Multilayer Correlation Clustering, a novel
generalization of Correlation Clustering (Bansal et al., FOCS '02) 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. 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.

我们在这篇论文中建立了多层相关聚类，这是对相关聚类（Bansal 等人，FOCS'02）在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法（其中 L 是层数），然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法，该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。

多层关联聚类

Multilayer Correlation Clustering

In the Correlation Clustering problem, we are given a complete weighted graph
$G$ with its edges labeled as "similar" and "dissimilar" by a noisy binary
classifier. For a clustering $\mathcal{C}$ of graph $G$, a similar edge is in
disagreement with $\mathcal{C}$, if its endpoints belong to distinct clusters;
and a dissimilar edge is in disagreement with $\mathcal{C}$ if its endpoints
belong to the same cluster. The disagreements vector, $\text{dis}$, is a vector
indexed by the vertices of $G$ such that the $v$-th coordinate $\text{dis}_v$
equals the weight of all disagreeing edges incident on $v$. The goal is to
produce a clustering that minimizes the $\ell_p$ norm of the disagreements
vector for $p\geq 1$. We study the $\ell_p$ objective in Correlation Clustering
under the following assumption: Every similar edge has weight in the range of
$[\alpha\mathbf{w},\mathbf{w}]$ and every dissimilar edge has weight at least
$\alpha\mathbf{w}$ (where $\alpha \leq 1$ and $\mathbf{w}>0$ is a scaling
parameter). We give an
$O\left((\frac{1}{\alpha})^{\frac{1}{2}-\frac{1}{2p}}\cdot
\log\frac{1}{\alpha}\right)$ approximation algorithm for this problem.
Furthermore, we show an almost matching convex programming integrality gap.

研究了具有加权图的相关聚类问题，在此问题下，通过加权边标记为相似或不相似，通过最小化不同意向量的 l_p 规范的目标函数，提供了一个近似算法。