Community detection thresholds and the weak Ramanujan property

DOI10.1145/2591796.2591857MaRDI QIDQ5259605zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Community detection in the sparse hypergraph stochastic block model
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• A proof of the block model threshold conjecture
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(85)

• Eigenvalues of random lifts and polynomials of random permutation matrices
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Non-convex exact community recovery in stochastic block model
• Community detection in the sparse hypergraph stochastic block model
• Strong consistency, graph Laplacians, and the stochastic block model
• Bethe states of random factor graphs
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• 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
• Asymptotic mutual information for the balanced binary stochastic block model
• Community detection on Euclidean random graphs
• scientific article; zbMATH DE number 7626732 (Why is no real title available?)
• Spectral norm bounds for block Markov chain random matrices
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Exact recovery in the Ising blockmodel
• Community detection with dependent connectivity
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Matched bipartite block model with covariates
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Detection thresholds for the \(\beta\)-model on sparse graphs
• Phase transitions in semidefinite relaxations
• Optimal rates for community estimation in the weighted stochastic block model
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• On semidefinite relaxations for the block model
• Graph powering and spectral robustness
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Resilience: a criterion for learning in the presence of arbitrary outliers
• Optimization via low-rank approximation for community detection in networks
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Estimating the number of communities by spectral methods
• Non-backtracking spectrum of degree-corrected stochastic block models
• Maximum likelihood estimation of sparse networks with missing observations
• Detection thresholds in very sparse matrix completion
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• On model selection for dense stochastic block models
• Concentration and stability of community-detecting functions on random networks
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Network cross-validation for determining the number of communities in network data
• Charting the replica symmetric phase
• The number of solutions for random regular NAE-SAT
• Bootstrap percolation on the stochastic block model
• How robust are reconstruction thresholds for community detection?
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Hidden Hamiltonian cycle recovery via linear programming
• Random Laplacian matrices and convex relaxations
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Average whenever you meet: opportunistic protocols for community detection
• On the computational tractability of statistical estimation on amenable graphs
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Community detection in degree-corrected block models
• Community detection in sparse networks via Grothendieck's inequality
• The spectral gap of sparse random digraphs
• Optimal bipartite network clustering
• Clustering in block Markov chains
• Entrywise eigenvector analysis of random matrices with low expected rank
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Mutual information for the sparse stochastic block model
• Inference in balanced community modulated recursive trees
• Joint community detection and rotational synchronization via semidefinite programming
• A survey on theoretical advances of community detection in networks
• scientific article; zbMATH DE number 7415091 (Why is no real title available?)
• Pair-matching: link prediction with adaptive queries
• Computational lower bounds for graphon estimation via low-degree polynomials
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Spectral gap in random bipartite biregular graphs and applications
• Searching for (sharp) thresholds in random structures: where are we now?
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• PageRank Nibble on the sparse directed stochastic block model
• Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
• Mean-field theory of graph neural networks in graph partitioning
• Charting the replica symmetric phase
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Recovering structured probability matrices
• Asymptotic uncertainty quantification for communities in sparse planted bi-section models
• Eigenvalues of the non-backtracking operator detached from the bulk

Describes a project that uses

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)