2014/04/18 by Emmanuel Abbe, Emmanuel Abbé, Afonso S. Bandeira +6 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Statistical Methods and Inference #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1404.4749
will appear in the IEEE Transactions on Network Science and Engineering
openalex publication_date 2014/04/18 · arxiv created 2014/11/04 · arxiv updated 2014/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⊕ 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(ε) 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 Erdős-Rényi 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-2ε)2+ o(1/(1-2ε)2). In other words, 2/(1-2ε)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-2ε)2+ o(1/(1-2ε)2), where 1-λ is the spectral gap of the graph G.