Spectral redemption: clustering sparse networks
arXiv:1306.5550 · doi:10.1073/pnas.1312486110
Abstract
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
arXiv comment11 pages, 6 figures. Clarified to what extent our claims are rigorous, and to what extent they are conjectures; also added an interpretation of the eigenvectors of the 2n-dimensional version of the non-backtracking matrix
References in corpus (14)
- Community structure in social and biological networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- The phase transition in inhomogeneous random graphs
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Graph spectra and the detectability of community structure in networks
- Pseudo-likelihood methods for community detection in large sparse networks
- Stochastic Block Models and Reconstruction
- Non-backtracking random walks mix faster
- A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
- Random matrices, non-backtracking walks, and orthogonal polynomials
- Comparative Study for Inference of Hidden Classes in Stochastic Block Models
Cited by in corpus (263)
- Machine learning and the physical sciences
- Community detection in networks: A user guide
- Higher-order organization of complex networks
- Influence maximization in complex networks through optimal percolation
- Vital nodes identification in complex networks
- Random walks and diffusion on networks
- The ground truth about metadata and community detection in networks
- Statistical physics of inference: Thresholds and algorithms
- Percolation on complex networks: Theory and application
- Consistency of spectral clustering in stochastic block models
- Fast community detection by SCORE
- Localization and centrality in networks
- Percolation on sparse networks
- Percolation in real interdependent networks
- Fundamentals of spreading processes in single and multilayer complex networks
- Nestedness in complex networks: Observation, emergence, and implications
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Identifying optimal targets of network attack by belief propagation
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Evaluating Overfit and Underfit in Models of Network Community Structure
- The many facets of community detection in complex networks
- Network histograms and universality of blockmodel approximation
- A goodness-of-fit test for stochastic block models
- Supervised Community Detection with Line Graph Neural Networks
- Statistical inference on random dot product graphs: a survey
- Distinct types of eigenvector localization in networks
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Predicting percolation thresholds in networks
- Suppressing epidemic spreading in multiplex networks with social-support
- Phase Transitions in Semidefinite Relaxations
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- Multiway spectral community detection in networks
- A message-passing approach for recurrent-state epidemic models on networks
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Evaluating accuracy of community detection using the relative normalized mutual information
- Leveraging percolation theory to single out influential spreaders in networks
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- Eigenvector localization in real networks and its implications for epidemic spreading
- Block Models and Personalized PageRank
- Finding One Community in a Sparse Graph
- Spectral Theory of Sparse Non-Hermitian Random Matrices
- The Spacey Random Walk: a Stochastic Process for Higher-order Data
- Model of Brain Activation Predicts the Neural Collective Influence Map of the Brain
- Disentangling bipartite and core-periphery structure in financial networks
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Predicting the epidemic threshold of the susceptible-infected-recovered model
- Phase transitions in semisupervised clustering of sparse networks
- Detecting Strong Ties Using Network Motifs
- Belief propagation for networks with loops
- Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
- A Survey on Theoretical Advances of Community Detection in Networks
- Graph neural network initialisation of quantum approximate optimisation
- Community detection in networks using graph embeddings
- Estimating the number of communities in networks by spectral methods
- The localization of non-backtracking centrality in networks and its physical consequences
- Simulating the Sycamore quantum supremacy circuits
- A message-passing approach to epidemic tracing and mitigation with apps
- Information-theoretic thresholds for community detection in sparse networks
- Using higher-order Markov models to reveal flow-based communities in networks
- Belief propagation, robust reconstruction and optimal recovery of block models
- Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
- Message passing methods on complex networks
- A testing based extraction algorithm for identifying significant communities in networks
- Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
- Nonbacktracking expansion of finite graphs
- Sparse random graphs: regularization and concentration of the Laplacian
- Information-theoretic thresholds for community detection in sparse networks
- On the equivalence between graph isomorphism testing and function approximation with GNNs
- Disordered Systems Insights on Computational Hardness
- Phase Transitions in Spectral Community Detection
- Spectral Detection on Sparse Hypergraphs
- Cross-validation estimate of the number of clusters in a network
- Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
- Enhancing transport properties in interconnected systems without altering their structure
- Assessing node risk and vulnerability in epidemics on networks
- Choosing among alternative histories of a tree
- Different approaches to community detection
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- A Mathematical Theory for Clustering in Metric Spaces
- Linear stability analysis for large dynamical systems on directed random graphs
- Hierarchical community structure in networks
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Mean-field theory of graph neural networks in graph partitioning
- Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
- A divisive spectral method for network community detection
- Localization and universality of eigenvectors in directed random graphs
- Finding communities in sparse networks
- Centrality metrics and localization in core-periphery networks
- Universal Phase Transition in Community Detectability under a Stochastic Block Model
- Relevance of backtracking paths in epidemic spreading on networks
- Community Detection in Networks using Graph Distance
- A literature survey of matrix methods for data science
- Improving the performance of algorithms to find communities in networks
- Heterogeneous micro-structure of percolation in sparse networks
- Spectral Detection in the Censored Block Model
- Non-Reconstructability in the Stochastic Block Model
- Influential spreaders for recurrent epidemics on networks
- Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
- Graph Comparison via the Non-backtracking Spectrum
- Influencers identification in complex networks through reaction-diffusion dynamics
- A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
- A Network Science perspective of Graph Convolutional Networks: A survey
- Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
- MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
- Message-Passing Methods for Complex Contagions
- Inference via Message Passing on Partially Labeled Stochastic Block Models
- Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
- Targeted influence maximization in complex networks
- Discovering the hidden community structure of public transportation networks
- Community detection in the sparse hypergraph stochastic block model
- Algorithmic detectability threshold of the stochastic block model
- Spectral community detection in sparse networks
- Spectral density of the non-backtracking operator
- Spectral radii of sparse random matrices
- Eigenvalues of the non-backtracking operator detached from the bulk
- Non-parametric resampling of random walks for spectral network clustering
- Community detection with nodal information
- Micro, Meso, Macro: the effect of triangles on communities in networks
- Comparative analysis on the selection of number of clusters in community detection
- Robust and efficient multi-way spectral clustering
- Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
- Kernel k-Groups via Hartigan's Method
- Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
- Percolation in random graphs with higher-order clustering
- Clustering from Sparse Pairwise Measurements
- On the Fourier transform of a quantitative trait: Implications for compressive sensing
- Community detection based on first passage probabilities
- Localization of eigenvector centrality in networks with a cut vertex
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- Node Immunization with Non-backtracking Eigenvalues
- Weighted Community Detection and Data Clustering Using Message Passing
- Extended-range percolation in complex networks
- Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
- Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
- Spectral estimation of the percolation transition in clustered networks
- Scalable Influence Estimation Without Sampling
- Inference in Deep Networks in High Dimensions
- An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
- Network Cross-Validation for Determining the Number of Communities in Network Data
- Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
- Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
- Multiple phases in modularity-based community detection
- Detectability of the spectral method for sparse graph partitioning
- Orthogonal symmetric non-negative matrix factorization under the stochastic block model
- Statistical test for detecting community structure in real-valued edge-weighted graphs
- Signal processing on graphs: Transforms and tomograms
- A unified framework for spectral clustering in sparse graphs
- Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
- Spectral theory of the non-backtracking Laplacian for graphs
- Finite size analysis of the detectability limit of the stochastic block model
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Matrix Completion with Hierarchical Graph Side Information
- Hierarchical community detection by recursive partitioning
- A Tractable Fully Bayesian Method for the Stochastic Block Model
- Zoo Guide to Network Embedding
- On Graph Neural Networks versus Graph-Augmented MLPs
- Optimal Bipartite Network Clustering
- Voter model on networks partitioned into two cliques of arbitrary sizes
- Graph powering and spectral robustness
- Performance of a community detection algorithm based on semidefinite programming
- Robustness of spectral methods for community detection
- Sparse General Wigner-type Matrices: Local Law and Eigenvector Delocalization
- Correlation detection in trees for planted graph alignment
- Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
- Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
- Decoding communities in networks
- Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
- Topology reveals universal features for network comparison
- Structured networks and coarse-grained descriptions: a dynamical perspective
- Spectral clustering via adaptive layer aggregation for multi-layer networks
- Ornstein-Uhlenbeck diffusion of hermitian and non-hermitian matrices - unexpected links
- Centralities in complex networks
- Eigenvector dynamics under perturbation of modular networks
- Communities in C.elegans connectome through the prism of non-backtracking walks
- Convex Relaxation Methods for Community Detection
- Spectral partitioning in equitable graphs
- Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
- Localization transition in non-Hermitian systems depending on reciprocity and hopping asymmetry
- Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
- Detectability thresholds of general modular graphs
- Move ordering and communities in complex networks describing the game of go
- Observability transition in real networks
- Fast Randomized Semi-Supervised Clustering
- Complete diagrammatics of the single ring theorem
- Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in Time
- Cluster Synchronization via Graph Laplacian Eigenvectors
- Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
- Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
- Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
- An Unsupervised Multivariate Time Series Kernel Approach for Identifying Patients with Surgical Site Infection from Blood Samples
- Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
- Non-Asymptotic Chernoff Lower Bound and Its Application to Community Detection in Stochastic Block Model
- Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
- Vulnerable Connectivity Caused by Local Communities in Spatial Networks
- Estimating Graph Dimension with Cross-validated Eigenvalues
- Adjusted chi-square test for degree-corrected block models
- Graph Distance from the Topological View of Non-backtracking Cycles
- Recovering Structured Probability Matrices
- Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
- The Atlas for the Aspiring Network Scientist
- Towards a robust algorithm to determine topological domains from colocalization data
- Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
- Beyond directed hypergraphs: heterogeneous hypergraphs and spectral centralities
- Neural-prior stochastic block model
- Multi-Frequency Joint Community Detection and Phase Synchronization
- Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
- Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
- AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
- Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
- Bayesian reconstruction of memories stored in neural networks from their connectivity
- Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
- Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
- Cutoff for exact recovery of Gaussian mixture models
- Large deviations of connected components in the stochastic block model
- Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks
- Localization of nonbacktracking centrality on dense subgraphs of sparse networks
- Confidence sets in a sparse stochastic block model with two communities of unknown sizes
- Revisiting Spectral Graph Clustering with Generative Community Models
- Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
- Experimental performance of graph neural networks on random instances of max-cut
- Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
- Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
- K-sets+: a Linear-time Clustering Algorithm for Data Points with a Sparse Similarity Measure
- Nonbacktracking Bounds on the Influence in Independent Cascade Models
- Non-backtracking random walks and a weighted Ihara's theorem
- Fast counting of medium-sized rooted subgraphs
- Contribution of directedness in graph spectra
- Spectral properties of the non-backtracking matrix of a graph
- Maximizing spreading in complex networks with risk in node activation
- Phase Transitions in Spectral Community Detection of Large Noisy Networks
- Spectral community detection in heterogeneous large networks
- Mutual Information in Community Detection with Covariate Information and Correlated Networks
- Construction of optimal spectral methods in phase retrieval
- Sketch-based community detection in evolving networks
- Learning Parametrised Graph Shift Operators
- Chiral Random Matrix Model at Finite Chemical Potential: Characteristic Determinant and Edge Universality
- Fragility of spectral clustering for networks with an overlapping structure
- Faster Clustering via Non-Backtracking Random Walks
- Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
- Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications
- Large Fixed-Diameter Graphs are Good Expanders
- A Compressive Sensing Approach to Community Detection with Applications
- How Well Do Local Algorithms Solve Semidefinite Programs?
- Leaders, Followers, and Community Detection
- Non-Backtracking Centrality Based Random Walk on Networks
- Approximating nonbacktracking centrality and localization phenomena in large networks
- Uncertainty quantification and testing in a stochastic block model with two unequal communities
- Non-backtracking walks reveal compartments in sparse chromatin interaction networks
- The Perron non-backtracking eigenvalue after node addition
- The self-consistent field iteration for p-spectral clustering
- On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
- A Semidefinite Program for Structured Blockmodels
- The emergence of pseudo-stable states in network dynamics
- Local law and Tracy--Widom limit for sparse stochastic block models
- Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
- Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
- Complex non-backtracking matrix for directed graphs
- Detectability threshold in weighted modular networks
- One Node at a Time: Node-Level Network Classification
- Community detection using low-dimensional network embedding algorithms
- Error-Correcting Decoders for Communities in Networks