# Exact Community Recovery over Signed Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 51 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [SPONGE: A generalized eigenproblem for clustering signed networks](https://mlsanity.com/paper/1904.08575/) (2019)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [SNE: Signed Network Embedding](https://mlsanity.com/paper/1703.04837/) (2017)
- [Discovering Polarized Communities in Signed Networks](https://mlsanity.com/paper/1910.02438/) (2019)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Clustering Signed Networks with the Geometric Mean of Laplacians](https://mlsanity.com/paper/1701.00757/) (2017)
- [Spectral Clustering of Signed Graphs via Matrix Power Means](https://mlsanity.com/paper/1905.06230/) (2019)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence](https://mlsanity.com/paper/1509.06418/) (2015)
- [Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery](https://mlsanity.com/paper/1404.4749/) (2014)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Prediction and Clustering in Signed Networks: A Local to Global Perspective](https://mlsanity.com/paper/1302.5145/) (2013)
- [Non-Convex Exact Community Recovery in Stochastic Block Model](https://mlsanity.com/paper/2006.15843/) (2020)
- [On the Troll-Trust Model for Edge Sign Prediction in Social Networks](https://mlsanity.com/paper/1606.00182/) (2016)
- [Node Classification for Signed Social Networks Using Diffuse Interface Methods](https://mlsanity.com/paper/1809.06432/) (2018)

## Built on by (most cited first, 3 of 3)

- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Defensive Alliances in Signed Networks](https://mlsanity.com/paper/2309.06801/) (2023)
- [Correlation Clustering with Random Partial Information](https://mlsanity.com/paper/2608.16315/) (2026)

## Abstract (arXiv)

Signed graphs encode similarity and dissimilarity relationships among different entities with positive and negative edges. In this paper, we study the problem of community recovery over signed graphs generated by the signed stochastic block model (SSBM) with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the SSBM. Unlike many existing approaches, our formulation reveals that the positive and negative edges of a signed graph should be treated unequally. We then propose a simple two-stage iterative algorithm for solving the regularized MLE. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time at the information-theoretic limit. Numerical results on both synthetic and real data are reported to validate and complement our theoretical developments and demonstrate the efficacy of the proposed method.