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

(87)

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

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)