Community detection thresholds and the weak Ramanujan property

By Laurent Massoulié. Symposium on the Theory of Computing, 2013

452 citations recorded by the source corpus.

Decelle et al. [1] conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mossel, Neeman and Sly [2] established the negative part of the conjecture, proving impossibility of non-trivial reconstruction below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a modified adjacency matrix B which counts self-avoiding paths of a given length ℓ between pairs of nodes. We then prove that for logarithmic length ℓ, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n -- 2 eigenvalues of a lower order O(nε √ρ(B) for all ε 0, ρ(B) denoting B's spectral radius.

Subfields: Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f5755a9b347b06a5275cdc949d6d725a8aafe4d2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Mean-field theory of graph neural networks in graph partitioning (2018, methodology): “In this case, it is rigorously known [21, 22, 23] that detection is impossible by any algorithm for the SBM with a group structure weaker than”
Exact Recovery in the Stochastic Block Model (2014, methodology): “…≥ Ω( √ log(n)/n) [5] Bickel, Chen ’09 N-G modularity (p− q)/ √ p+ q = Ω(log(n)/ √ n) [32] Rohe, Chatterjee, Yu ’11 spectral method p− q = Ω(1) While these algorithmic developments are impressive, we next argue how they do not reveal the sharp behavioral transition that takes place in this model.”
Consistency of spectral clustering in stochastic block models (2013, background): “…optimization (Chen et al., 2012), spectral clustering (Rohe et al., 2011; Balakrishnan et al., 2011; Jin, 2012; Fishkind et al., 2013; Sarkar & Bickel, 2013) and its variants (Coja-Oghlan, 2010; Chaudhuri et al., 2012) and spectral embeddings (Sussman et al., 2012, 2013; Lyzinski et al., 2013).”
The ground truth about metadata and community detection in networks (2016, background): “[25] Laurent Massoulié, “Community detection thresholds and the weak ramanujan property,” in Proc.”
Eigenvalues of random lifts and polynomials of random permutation matrices (2018, methodology): “It relies on a refinement of the trace method Füredi and Komlós [18] which was developed in [29, 8, 7].”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, methodology): “In §2.2, thanks to elementary linear algebra, we will give a deterministic upper bound on this second largest eigenvalue in terms of the operator norms of new matrices, this step is inspired from Massoulié [20] and further developed in [7].”
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery (2015, background): “Such phenomena are commonly used in coding theory for weak recovery [37], [38] and exact recovery [39], [40].”
Supervised Community Detection with Line Graph Neural Networks (2017, background): “In SBM with fewer than 4 communities, it is known that BP provably reaches the information-theoretic threshold (Abbe, 2017; Massoulié, 2014; Coja-Oghlan et al., 2016).”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, methodology): “In Section 5, we give the proof architecture for Theorem 3 on the nonbacktracking spectrum of Erdős–Rényi graphs, and detail a central argument of combinatorial nature, namely a representation of the nonbacktracking matrix B raised to some power as a sum of products of matrices, elaborating on a tec”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “The prediction and location of these phase transition in the stochastic block model from [59, 60] was followed by a remarkable mathematical development where the location of the threshold was made rigorous for q = 2 [158, 177, 178].”