Spectral redemption: clustering sparse networks

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.

11 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 (6)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Random matrices, non-backtracking walks, and orthogonal polynomials
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Cited by in corpus (260)

• 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
• 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
• Distinct types of eigenvector localization in networks
• Statistical inference on random dot product graphs: a survey
• 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
• Phase transitions in semisupervised clustering of sparse networks
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Detecting Strong Ties Using Network Motifs
• Belief propagation for networks with loops
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Graph neural network initialisation of quantum approximate optimisation
• A Survey on Theoretical Advances of Community Detection in Networks
• 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
• Using higher-order Markov models to reveal flow-based communities in networks
• Information-theoretic thresholds for community detection in sparse 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
• Nonbacktracking expansion of finite graphs
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Information-theoretic thresholds for community detection in sparse networks
• Sparse random graphs: regularization and concentration of the Laplacian
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Phase Transitions in Spectral Community Detection
• Disordered Systems Insights on Computational Hardness
• Spectral Detection on Sparse Hypergraphs
• Cross-validation estimate of the number of clusters in a network
• Assessing node risk and vulnerability in epidemics on networks
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Enhancing transport properties in interconnected systems without altering their structure
• Different approaches to community detection
• Choosing among alternative histories of a tree
• Linear stability analysis for large dynamical systems on directed random graphs
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• A Mathematical Theory for Clustering in Metric Spaces
• Mean-field theory of graph neural networks in graph partitioning
• Hierarchical community structure in networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Localization and universality of eigenvectors in directed random graphs
• Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
• A divisive spectral method for network community detection
• Finding communities in sparse networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Centrality metrics and localization in core-periphery networks
• Relevance of backtracking paths in epidemic spreading on networks
• Community Detection in Networks using Graph Distance
• Improving the performance of algorithms to find communities in networks
• A literature survey of matrix methods for data science
• Heterogeneous micro-structure of percolation in sparse networks
• Spectral Detection in the Censored Block Model
• Non-Reconstructability in the Stochastic Block Model
• Graph Comparison via the Non-backtracking Spectrum
• Influential spreaders for recurrent epidemics on networks
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• Influencers identification in complex networks through reaction-diffusion dynamics
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Message-Passing Methods for Complex Contagions
• A Network Science perspective of Graph Convolutional Networks: A survey
• Community detection in the sparse hypergraph stochastic block model
• Algorithmic detectability threshold of the stochastic block model
• Targeted influence maximization in complex networks
• Discovering the hidden community structure of public transportation networks
• 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
• Comparative analysis on the selection of number of clusters in community detection
• Kernel k-Groups via Hartigan's Method
• Community detection with nodal information
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Robust and efficient multi-way spectral clustering
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Localization of eigenvector centrality in networks with a cut vertex
• Percolation in random graphs with higher-order clustering
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Community detection based on first passage probabilities
• Clustering from Sparse Pairwise Measurements
• On the Fourier transform of a quantitative trait: Implications for compressive sensing
• Node Immunization with Non-backtracking Eigenvalues
• Extended-range percolation in complex networks
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Weighted Community Detection and Data Clustering Using Message Passing
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Spectral estimation of the percolation transition in clustered networks
• Scalable Influence Estimation Without Sampling
• Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Multiple phases in modularity-based community detection
• Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• Inference in Deep Networks in High Dimensions
• A unified framework for spectral clustering in sparse graphs
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Detectability of the spectral method for sparse graph partitioning
• Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
• Signal processing on graphs: Transforms and tomograms
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Spectral theory of the non-backtracking Laplacian for graphs
• Matrix Completion with Hierarchical Graph Side Information
• On Graph Neural Networks versus Graph-Augmented MLPs
• Finite size analysis of the detectability limit of the stochastic block model
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Hierarchical community detection by recursive partitioning
• Zoo Guide to Network Embedding
• Optimal Bipartite Network Clustering
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
• Voter model on networks partitioned into two cliques of arbitrary sizes
• Robustness of spectral methods for community detection
• Performance of a community detection algorithm based on semidefinite programming
• Graph powering and spectral robustness
• Sparse General Wigner-type Matrices: Local Law and Eigenvector Delocalization
• Correlation detection in trees for planted graph alignment
• Decoding communities in networks
• Topology reveals universal features for network comparison
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Ornstein-Uhlenbeck diffusion of hermitian and non-hermitian matrices - unexpected links
• Eigenvector dynamics under perturbation of modular networks
• Move ordering and communities in complex networks describing the game of go
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Spectral partitioning in equitable graphs
• Detectability thresholds of general modular graphs
• Convex Relaxation Methods for Community Detection
• Centralities in complex networks
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Localization transition in non-Hermitian systems depending on reciprocity and hopping asymmetry
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Observability transition in real networks
• 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
• Complete diagrammatics of the single ring theorem
• Fast Randomized Semi-Supervised Clustering
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Graph Distance from the Topological View of Non-backtracking Cycles
• Adjusted chi-square test for degree-corrected block models
• Recovering Structured Probability Matrices
• An Unsupervised Multivariate Time Series Kernel Approach for Identifying Patients with Surgical Site Infection from Blood Samples
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• Estimating Graph Dimension with Cross-validated Eigenvalues
• 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
• AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
• Beyond directed hypergraphs: heterogeneous hypergraphs and spectral centralities
• The Atlas for the Aspiring Network Scientist
• Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
• Neural-prior stochastic block model
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
• Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
• Towards a robust algorithm to determine topological domains from colocalization data
• Multi-Frequency Joint Community Detection and Phase Synchronization
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Revisiting Spectral Graph Clustering with Generative Community Models
• Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
• Large deviations of connected components in the stochastic block model
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• Cutoff for exact recovery of Gaussian mixture models
• Fast counting of medium-sized rooted subgraphs
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Experimental performance of graph neural networks on random instances of max-cut
• Sketch-based community detection in evolving networks
• Construction of optimal spectral methods in phase retrieval
• Learning Parametrised Graph Shift Operators
• Non-backtracking random walks and a weighted Ihara's theorem
• Chiral Random Matrix Model at Finite Chemical Potential: Characteristic Determinant and Edge Universality
• Contribution of directedness in graph spectra
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Spectral properties of the non-backtracking matrix of a graph
• Maximizing spreading in complex networks with risk in node activation
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• 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
• Spectral community detection in heterogeneous large networks
• Community detection using low-dimensional network embedding algorithms
• Local law and Tracy--Widom limit for sparse stochastic block models
• How Well Do Local Algorithms Solve Semidefinite Programs?
• The Perron non-backtracking eigenvalue after node addition
• Non-Backtracking Centrality Based Random Walk on Networks
• Uncertainty quantification and testing in a stochastic block model with two unequal communities
• Approximating nonbacktracking centrality and localization phenomena in large networks
• On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
• Error-Correcting Decoders for Communities in Networks
• Fragility of spectral clustering for networks with an overlapping structure
• A Semidefinite Program for Structured Blockmodels
• The emergence of pseudo-stable states in network dynamics
• A Compressive Sensing Approach to Community Detection with Applications
• Faster Clustering via Non-Backtracking Random Walks
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
• Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
• 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
• Large Fixed-Diameter Graphs are Good Expanders
• The self-consistent field iteration for p-spectral clustering