Spectral redemption in clustering sparse networks

By Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborov'a, Pan Zhang. 2013

660 citations recorded by the source corpus.

Significance Spectral algorithms are widely applied to data clustering problems, including finding communities or partitions in graphs and networks. We propose a way of encoding sparse data using a “nonbacktracking” matrix, and show that the corresponding spectral algorithm performs optimally for some popular generative models, including the stochastic block model. This is in contrast with classical spectral algorithms, based on the adjacency matrix, random walk matrix, and graph Laplacian, which perform poorly in the sparse case, failing significantly above a recently discovered phase transition for the detectability of communities. Further support for the method is provided by experiments on real networks as well as by theoretical arguments and analogies from probability theory, statistical physics, and the theory of random matrices. 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 present a class of spectral algorithms based on a nonbacktracking 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 of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Scalable detection of statistically significant communities and hierarchies, using message passing for modularity (2014, methodology): “Retrieval modularity, overlap between the retrieval partition and the ground truth, the number of groups q* as determined by our algorithm, the inverse temperature β* defined in [3], and the convergence time measured in seconds and iterations for several real-world networks (2, 33–37)”
Spectral radii of sparse random matrices (2017, background): “It is inspired by [23] and generalizes ideas from [21].”
Machine learning and the physical sciences (2019, methodology): “The statistical physics understanding of the stochastic block model and the conjecture about belief propagation algorithm being optimal among all polynomial ones inspired the discovery of a new class of spectral algorithms for sparse data (i.e. when the matrix X is sparse) (Krzakala et al., 2013b).”
Random walks and diffusion on networks (2016, background): “including percolation [259, 260], network centralities [261], community detection [262–264], and efficient “immunization” algorithms [265].”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, background): “In particular, the singular values of B contain only information on the degree sequence of the underlying graph G as noted in [20].”
Community Detection with Graph Neural Networks (2017, background): “Despite the appeal of graph Laplacian spectral approaches, it is well known (Krzakala et al., 2013) that these methods fail in sparsely connected graphs.”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “Integrating the non-backtracking operator with belief propagation’s message-passing rules [72], LGNN learns node represented features in directed networks.”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, background): “Our spectral methods may not be optimal for stochastic models [50, 52] but they are very useful, in that they rely on well-optimized computational methods, can be implemented quickly in many standard languages, extend readily to other models, and serve as a foundation for more complex analyses.”
Community detection in networks: A user guide (2016, methodology): “(15) was introduced to address this problem (Krzakala et al., 2013).”
Supervised Community Detection with Line Graph Neural Networks (2017, methodology): “Despite the appeal of graph Laplacian spectral approaches, it is known that these methods fail in sparsely connected graphs (Krzakala et al., 2013) .”
Consistency of spectral clustering in stochastic block models (2013, background): “…case, where the maximum degree is of order O (1), consistent community recovery is impossible and one can only hope to recover the communities up to a constant fraction (see Coja-Oghlan, 2010; Decelle et al., 2011; Mossel et al., 2012; Krzakala et al., 2013; Massoulie, 2013; Mossel et al., 2013).”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “This procedure was suggested in [242] and works nicely, in particular in conjunction with the best known spectral clustering techniques [137] as will be discussed in sec.”
Mean-field theory of graph neural networks in graph partitioning (2018, background): “The matrix M = B = [Bj→k,i→j ] is the so-called non-backtracking matrix [14], and the softmax function represents the normalization of the state xσ,i→j .”