Community detection thresholds and the weak Ramanujan property

DOI10.1145/2591796.2591857zbMATH Open1315.68210arXiv1311.3085OpenAlexW2023348178MaRDI QIDQ5259605FDOQ5259605

Laurent Massoulié

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: Decelle et al.cite{Decelle11} conjectured the existence of a sharp threshold for community detection in sparse random graphs drawn from the stochastic block model. Mossel et al.cite{Mossel12} established the negative part of the conjecture, proving impossibility of meaningful detection below the threshold. However the positive part of the conjecture remained elusive so far. Here we solve the positive part of the conjecture. We introduce a modified adjacency matrix $B$ that counts self-avoiding paths of a given length $ell$ between pairs of nodes and prove that for logarithmic $ell$, the leading eigenvectors of this modified matrix provide non-trivial detection, thereby settling the conjecture. A key step in the proof consists in establishing a {em weak Ramanujan property} of matrix $B$. Namely, the spectrum of $B$ consists in two leading eigenvalues $ho(B)$, $lambd{a}_2$ and $n-2$ eigenvalues of a lower order $O(n^{epsilon}sqrtho(B))$ for all $epsilon>0$, $ho(B)$ denoting $B$'s spectral radius. $d$-regular graphs are Ramanujan when their second eigenvalue verifies $|lambda|le2sqrtd-1$. Random $d$-regular graphs have a second largest eigenvalue $lambda$ of $2sqrtd-1+o(1)$ (see Friedmancite{friedman08}), thus being {em almost} Ramanujan. ErdH{o}s-R'enyi graphs with average degree $d$ at least logarithmic ($d=Omega(logn)$) have a second eigenvalue of $O(sqrtd)$ (see Feige and Ofekcite{Feige05}), a slightly weaker version of the Ramanujan property. However this spectrum separation property fails for sparse ($d=O(1)$) ErdH{o}s-R'enyi graphs. Our result thus shows that by constructing matrix $B$ through neighborhood expansion, we regularize the original adjacency matrix to eventually recover a weak form of the Ramanujan property.

Full work available at URL: https://arxiv.org/abs/1311.3085

zbMATH Keywords

community detectionphase transitionspectral clusteringspectral separation

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Social networks; opinion dynamics (91D30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (84)

• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Notes on computational-to-statistical gaps: predictions using statistical physics
• The spectral gap of sparse random digraphs
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
• Asymptotic mutual information for the balanced binary stochastic block model
• Optimization via low-rank approximation for community detection in networks
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Title not available (Why is that?)
• Optimal rates for community estimation in the weighted stochastic block model
• Community detection in the sparse hypergraph stochastic block model
• Bethe states of random factor graphs
• Exact recovery in the Ising blockmodel
• Phase transitions in semidefinite relaxations
• On semidefinite relaxations for the block model
• Community detection in degree-corrected block models
• Information-theoretic thresholds from the cavity method
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• Graph Powering and Spectral Robustness
• Random Laplacian matrices and convex relaxations
• Charting the replica symmetric phase
• Entrywise eigenvector analysis of random matrices with low expected rank
• Spectral norm bounds for block Markov chain random matrices
• Hidden Hamiltonian Cycle Recovery via Linear Programming
• Non-convex exact community recovery in stochastic block model
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Maximum likelihood estimation of sparse networks with missing observations
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Clustering in block Markov chains
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Charting the replica symmetric phase
• Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks
• Concentration and stability of community-detecting functions on random networks
• Detecting a planted community in an inhomogeneous random graph
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Bootstrap percolation on the stochastic block model
• Title not available (Why is that?)
• Community detection with dependent connectivity
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Optimal Bipartite Network Clustering
• On model selection for dense stochastic block models
• Title not available (Why is that?)
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Estimating the number of communities by spectral methods
• Network Cross-Validation for Determining the Number of Communities in Network Data
• The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
• On the computational tractability of statistical estimation on amenable graphs
• Title not available (Why is that?)
• Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time
• The number of solutions for random regular NAE-SAT
• Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Detection thresholds in very sparse matrix completion
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• How robust are reconstruction thresholds for community detection?
• Community detection in sparse networks via Grothendieck's inequality
• A survey on theoretical advances of community detection in networks
• Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
• Mean-field theory of graph neural networks in graph partitioning
• Mutual information for the sparse stochastic block model
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Recovering Structured Probability Matrices
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Spectral gap in random bipartite biregular graphs and applications
• Asymptotic uncertainty quantification for communities in sparse planted bi-section models
• Title not available (Why is that?)
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Eigenvalues of the non-backtracking operator detached from the bulk
• PageRank Nibble on the sparse directed stochastic block model
• Inference in balanced community modulated recursive trees
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Joint Community Detection and Rotational Synchronization via Semidefinite Programming
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Searching for (sharp) thresholds in random structures: where are we now?
• Pair-matching: link prediction with adaptive queries
• Computational lower bounds for graphon estimation via low-degree polynomials
• Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
• Sparse random hypergraphs: non-backtracking spectra and community detection

Uses Software

• SuLQ

This page was built for publication: Community detection thresholds and the weak Ramanujan property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259605)