# Robust Correlation Clustering with Asymmetric Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 15 Oct 2021.

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

- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations](https://mlsanity.com/paper/1607.00084/) (2016)
- [Average-case Hardness of RIP Certification](https://mlsanity.com/paper/1605.09646/) (2016)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [More Algorithms for Provable Dictionary Learning](https://mlsanity.com/paper/1401.0579/) (2014)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [ADMM for the SDP relaxation of the QAP](https://mlsanity.com/paper/1512.05448/) (2015)
- [Exact recovery in the Ising blockmodel](https://mlsanity.com/paper/1612.03880/) (2016)
- [Facial Reduction for Symmetry Reduced Semidefinite Doubly Nonnegative Programs](https://mlsanity.com/paper/1912.10245/) (2019)
- [Provable Overlapping Community Detection in Weighted Graphs](https://mlsanity.com/paper/2004.07150/) (2020)

## Abstract (arXiv)

Graph clustering problems typically aim to partition the graph nodes such that two nodes belong to the same partition set if and only if they are similar. Correlation Clustering is a graph clustering formulation which: (1) takes as input a signed graph with edge weights representing a similarity/dissimilarity measure between the nodes, and (2) requires no prior estimate of the number of clusters in the input graph. However, the combinatorial optimization problem underlying Correlation Clustering is NP-hard. In this work, we propose a novel graph generative model, called the Node Factors Model (NFM), which is based on generating feature vectors/embeddings for the graph nodes. The graphs generated by the NFM contain asymmetric noise in the sense that there may exist pairs of nodes in the same cluster which are negatively correlated. We propose a novel Correlation Clustering algorithm, called anormd, using techniques from semidefinite programming. Using a combination of theoretical and computational results, we demonstrate that textttℓ2-norm-diag recovers nodes with sufficiently strong cluster membership in graph instances generated by the NFM, thereby making progress towards establishing the provable robustness of our proposed algorithm.