# Multilayer Correlation Clustering

arXiv: https://arxiv.org/abs/2404.16676 · HTML: https://mlsanity.com/paper/2404.16676/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 69 references that are in the map.
- First posted on arXiv 25 Apr 2024.

## Builds on (most cited first, 20 of 20)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Community detection, link prediction, and layer interdependence in multilayer networks](https://mlsanity.com/paper/1701.01369/) (2017)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Spreading processes in Multilayer Networks](https://mlsanity.com/paper/1405.4329/) (2014)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Improved Approximation for Fair Correlation Clustering](https://mlsanity.com/paper/2206.05050/) (2022)
- [Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering](https://mlsanity.com/paper/2309.17243/) (2023)
- [Min-Max Correlation Clustering via MultiCut](https://mlsanity.com/paper/1907.00117/) (2019)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Centrality in Interconnected Multilayer Networks](https://mlsanity.com/paper/1311.2906/) (2013)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (2023)
- [Combinatorial Correlation Clustering](https://mlsanity.com/paper/2404.05433/) (2024)
- [Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks](https://mlsanity.com/paper/2211.03306/) (2022)
- [Near-optimal approximation algorithm for simultaneous Max-Cut](https://mlsanity.com/paper/1801.04497/) (2018)

## Abstract (arXiv)

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 of n elements. The goal is to find a clustering of V that minimizes the ℓp-norm (p≥ 1) of the multilayer-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. We then study an important special case of our problem, namely the problem with the so-called probability constraint. For this case, we first give an (α+2)-approximation algorithm, where α is any possible approximation ratio for the single-layer counterpart. 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 support our theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.