# Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2014.

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

- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [On the Fundamental Limits of Exact Inference in Structured Prediction](https://mlsanity.com/paper/2102.08895/) (2021)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)

## Abstract (arXiv)

We consider the problem of clustering a graph G into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables Y=BG x oplus Z, where BG is the incidence matrix of a graph G, x is the vector of unknown vertex variables (with a uniform prior) and Z is a noise vector with Bernoulli(varepsilon) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of x is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n)/n for ErdHos-R'enyi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α =np/log(n), it is shown that exact recovery is possible if and only if α >2/(1-2varepsilon)2+ o(1/(1-2varepsilon)2). In other words, 2/(1-2varepsilon)2 is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph G, defining the degree rate as α=d/log(n), where d is the minimum degree of the graph, it is shown that the proposed method achieves the rate α> 4((1+λ)/(1-λ)2)/(1-2varepsilon)2+ o(1/(1-2varepsilon)2), where 1-λ is the spectral gap of the graph G.