Robust Correlation Clustering with Asymmetric Noise
arXiv:2110.08385
Abstract
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{$\ell_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.
References in corpus (6)
- A Simpler Approach to Matrix Completion
- Clustering Partially Observed Graphs via Convex Optimization
- More Algorithms for Provable Dictionary Learning
- Information-theoretic thresholds for community detection in sparse networks
- Local Correlation Clustering with Asymmetric Classification Errors
- Facial Reduction for Symmetry Reduced Semidefinite Doubly Nonnegative Programs