Spectral Clustering and Sparse Networks

To study the effectiveness of spectral algorithms in a specific ensemble of graphs, suppose that a graph G is generated by the stochastic block model (1). There are q groups of vertices, and each vertex v has a group label . Edges are generated independently according to a matrix p of probabilities, with . In the sparse case, we have , where the affinity matrix stays constant in the limit .

For simplicity we first discuss the commonly studied case where c has two distinct entries, if and if . We take with two groups of equal size, and assume that the network is assortative, i.e., . The section More than Two Groups and General Degree Distributions below discusses our results in more general cases.

The group labels are hidden from us, and our goal is to infer them from the graph. Let denote the average degree. The detectability threshold (9⇓–11) states that in the limit , unlessthe randomness in the graph washes out the block structure to the extent that no algorithm can label the vertices better than chance. Moreover, ref. 11 proved that below this threshold it is impossible to identify the parameters and , whereas above the threshold the parameters and are easily identifiable.

The adjacency matrix is defined as the matrix if and 0 otherwise. A typical spectral algorithm assigns each vertex a k-dimensional vector according to its entries in the first k eigenvectors of A for some k, and clusters these vectors according to a heuristic such as the k-means algorithm (often after normalizing or weighting them in some way). In the case , we can simply label the vertices according to the sign of the second eigenvector.

As shown in ref. 8, spectral algorithms succeed all of the way down to the threshold 1 if the graph is sufficiently dense. In that case, A’s spectrum has a discrete part and a continuous part in the limit . Its first eigenvector essentially sorts vertices according to their degree, whereas the second eigenvector is correlated with the communities. The second eigenvalue is given byThe question is when this eigenvalue gets lost in the continuous bulk of eigenvalues coming from the randomness in the graph. This part of the spectrum, like that of a sufficiently dense Erdős–Rényi random graph, is asymptotically distributed according to Wigner’s semicircle law (21), . Thus, the bulk of the spectrum lies in the interval . If , which is equivalent to 1, the spectral algorithm can find the corresponding eigenvector, and it is correlated with the true community structure.

However, in the sparse case where c is constant while n is large, this picture breaks down due to a number of reasons. Most importantly, the leading eigenvalues of A are dictated by the vertices of highest degree, and the corresponding eigenvectors are localized around these vertices (22). As n grows, these eigenvalues exceed , swamping the community-correlated eigenvector, if any, with the bulk of uninformative eigenvectors. As a result, spectral algorithms based on A fail a significant distance from the threshold given by 1. Moreover, this gap grows as n increases: for instance, the largest eigenvalue grows as the square root of the largest degree, which is roughly proportional to for Erdős–Rényi graphs. To illustrate this problem, the spectrum of A for a large graph generated by the block model is depicted in Fig. 1.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 1.

Spectrum of the adjacency matrix of a sparse network generated by the block model (excluding the zero eigenvalues). Here, , , and , and we average over 20 realizations. Even though the eigenvalue given by Eq. 2 satisfies the threshold condition 1 and lies outside the semicircle of radius , deviations from the semicircle law cause it to get lost in the bulk, and the eigenvector of the second largest eigenvalue is uncorrelated with the community structure. As a result, spectral algorithms based on A are unable to identify the communities in this case.

Other popular operators for spectral clustering include the Laplacian , where is the diagonal matrix of vertex degrees, the symmetrically normalized Laplacian , the stochastic random walk matrix , and the modularity matrix . However, like A, these are prey to localized eigenvectors in the sparse case.

Another simple heuristic is to simply remove the high-degree vertices (e.g., ref. 6), but this throws away a significant amount of information; in the sparse case it can even destroy the giant component, causing the graph to fall apart into disconnected pieces (23). Finally, one can also regularize the adjacency matrix by adding a small constant term (24); however, this introduces a tunable parameter, and we have not explored this here.

Nonbacktracking Operator

The main contribution of this paper is to show how to redeem the performance of spectral algorithms in sparse networks by using a different linear operator. The nonbacktracking matrix B is a matrix, defined on the directed edges of the graph. Specifically,Using B rather than A addresses the problem described above. The spectrum of B is not sensitive to high-degree vertices, because a walk starting at v cannot turn around and return to it immediately. Other convenient properties of B are that any tree dangling off the graph, or disconnected from it, simply contributes zero eigenvalues to the spectrum, because a nonbacktracking walk is forced to a leaf of the tree where it has nowhere to go. Similarly, one can show that unicyclic components yield eigenvalues that are either 0, 1, or −1.

As a result, B has the following spectral properties in the limit in the ensemble of graphs generated by the block model. The leading eigenvalue is the average degree . At any point above the detectability threshold 1, the second eigenvalue is associated with the block structure and readsMoreover, the bulk of B’s spectrum is confined to the disk in the complex plane of radius , as shown in Fig. 2. Thus, the second eigenvalue is well-separated from the top of the bulk, i.e., from the third largest eigenvalue in absolute value, as shown in Fig. 3.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 2.

Spectrum of the nonbacktracking matrix B for a network generated by the block model with same parameters as in Fig. 1. The leading eigenvalue is at , the second eigenvalue is close to , and the bulk of the spectrum is confined to the disk of radius . Because is outside the bulk, a spectral algorithm that labels vertices according to the sign of B’s second eigenvector (summed over the incoming edges at each vertex) labels the majority of vertices correctly.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 3.

First, second, and third largest eigenvalues , , and , respectively, of B as functions of . The third eigenvalue is complex, so we plot its modulus. Values are averaged over 20 networks of size and average degree . The green line in the figure represents , and the horizontal lines are c and , respectively. The second eigenvalue is well-separated from the bulk throughout the detectable regime.

The eigenvector corresponding to is strongly correlated with the communities. Because B is defined on directed edges, at each vertex we sum this eigenvector over all its incoming edges. If we label vertices according to the sign of this sum, then the majority of vertices are labeled correctly (up to a change of sign, which switches the two communities). Thus, a spectral algorithm based on B succeeds when , i.e., when 1 holds—but, unlike standard spectral algorithms, this criterion now holds even in the sparse case.

We present arguments for these claims in the next section. We will also see that the important part of B’s spectrum can be obtained from a matrix (16, 25, 26)This lets us work with a 2n-dimensional matrix rather than a 2m-dimensional one, which significantly reduces the computational complexity of our algorithm.

Reconstruction and a Community-Correlated Eigenvector

In this section we sketch justifications of the claims in the previous section regarding B’s spectral properties, showing that its second eigenvector is correlated with the communities whenever 1 holds. We assume that , so that the graph is locally tree-like.

We start by explicitly constructing a vector g which is correlated with the communities and is an approximate eigenvector with eigenvalue , as defined in Eq. 3. We follow ref. 11, which derived a similar result in the case of random regular graphs. For a given integer r, consider the vector defined bywhere denotes u’s community, and denotes the number of steps required to go from to in the graph of directed edges. By the theory of the reconstruction problem on trees (27, 28), if 1 holds, then for every , the correlation is bounded away from zero in the limit .

Next, we argue that if r is large then g is an approximate eigenvector of B with eigenvalue . As long as the radius-r neighborhood of v is a tree, we haveThis is not precisely an eigenvalue equation because ; however, it turns out that they are close with high probability. Indeed, we may write asNow, there are (in expectation) terms in this sum, each of which, conditioned on the s, has mean zero and constant variance. Hence, . Summing over u and v, we have . If 1 holds then and so with high probability the error term tends to zero for large r. Because is bounded above zero, Eq. 6 then becomesso is indeed an approximate eigenvector for B with eigenvalue . Because, as we will discuss shortly, the bulk of B’s spectrum is bounded away from , it follows that the true eigenvector with eigenvalue is close to , and so it may be used for community detection. Specifically, if we label vertices according to the sign of this eigenvector (summed over all incoming edges at each vertex) we obtain the true communities with significant accuracy.

Summing over incoming and outgoing edges also lets us relate B’s spectrum to that of (Eq. 4). Given a 2m-dimensional vector g, define and as the n-dimensional vectorsIf we apply B to g, each incoming edge contributes times to u’s outgoing edges. Similarly, each edge with contributes to the incoming edge . As a result, we haveor more succinctly,Now suppose that . If and are nonzero, then is an eigenvector of with the same eigenvalue μ. In that case, we haveso μ is a root of the quadratic eigenvalue equationThis equation is well known in the theory of graph zeta functions (16, 25, 26). It accounts for 2n of B’s eigenvalues, the other of which are .

Next, we argue that the bulk of B’s spectrum is confined to the disk of radius . First note that for any matrix B,On the other hand, for any fixed r, because G is locally tree-like in the limit , each diagonal entry of is equal to the number of vertices exactly r steps from v, other than those connected via u. In expectation this is , so by linearity of expectation . In that case, the 2rth moment in the spectral measure obeys .

Because this holds for any fixed r, we conclude that almost all of B’s eigenvalues obey . Proving that all the eigenvalues in the bulk are asymptotically confined to this disk requires a more precise argument and is left for future work.

Finally, the singular values of B are easy to derive for any simple graph, i.e., one without self-loops or multiple edges. Namely, BB^T is block-diagonal: for each vertex v, it has a rank-one block of size that connects v’s outgoing edges to each other. As a consequence, B has n singular values , and its other singular values are 1. However, because B is not symmetric, its eigenvalues and its singular values are different—whereas its singular values are controlled by the vertex degrees, its eigenvalues are not. This is precisely why its spectral properties are better than those of A and related operators.

More than Two Groups and General Degree Distributions

The arguments given above regarding B’s spectral properties generalize straightforwardly to other graph ensembles. First, consider block models with q groups, where for group a has fractional size . The average degree of group a is . The hardest case is where is the same for all a, so that we cannot simply label vertices according to their degree.

The leading eigenvector again has eigenvalue c, and the bulk of B’s spectrum is again confined to the disk of radius . Now B has linearly independent eigenvectors with real eigenvalues, and the corresponding eigenvectors are correlated with the true group assignment. If these real eigenvalues lie outside the bulk, we can identify the groups by assigning a vector in to each vertex, and applying a clustering technique such as k means. These eigenvalues are of the form , where ν is a nonzero eigenvalue of the matrixIn particular, if for all a, and for , and for , we have . The detectability threshold is again , orMore generally, if the community-correlated eigenvectors have distinct eigenvalues, we can have multiple transitions where some of them can be detected by a spectral algorithm whereas others cannot.

There is an important difference between the general case and . Whereas for it is literally impossible for any algorithm to distinguish the communities below this transition, for larger q the situation is more complicated. In general (for in the assortative case, and in the disassortative one) the threshold 9 marks a transition from an ‘‘easily detectable’’ regime to a ‘‘hard detectable’’ one. In the hard detectable regime, it is theoretically possible to find the communities, but it is conjectured that any algorithm that does so takes exponential time (9, 10). In particular, we have found experimentally that none of B’s eigenvectors are correlated with the groups in the hard regime. Nonetheless, our arguments suggest that spectral algorithms based on B are optimal in the sense that they succeed all of the way down to this easy–hard transition.

Because a major drawback of the stochastic block model is that its degree distribution is Poisson, we can also consider random graphs with specified degree distributions. Again, the hardest case is where the groups have the same degree distribution. Let denote the fraction of vertices of degree k. The average branching ratio of a branching process that explores the neighborhood of a vertex, i.e., the average number of new edges leaving a vertex v that we arrive at when following a random edge, isWe assume here that the degree distribution has bounded second moment so that this process is not dominated by a few high-degree vertices. The leading eigenvalue of B is , and the bulk of its spectrum is confined to the disk of radius , even in the sparse case where does not grow with the size of the graph. If and the average numbers of new edges linking v to its own group and the other group are and , respectively, then the approximate eigenvector described in the previous section has eigenvalue . The detectability threshold 1 then becomes , or . The threshold 9 for q groups generalizes similarly.

Deriving B by Linearizing Belief Propagation

The matrix B also appears naturally as a linearization of the update equations for belief propagation (BP). This linearization was used previously to investigate phase transitions in the performance of the BP algorithm (5, 9, 10, 29).

We recall that BP is an algorithm that iteratively updates messages along the directed edges. These messages represent the marginal probability that a vertex v belongs to a given community, assuming that the vertex w is absent from the network. Each such message is updated according to the messages that v receives from its other neighbors . The update rule depends on the parameters and of the block model, as well as the expected size of each community. For the simplest case of two equally sized groups, the BP update (9, 10) can be written asHere, + and − denote the two communities. The term , where and is the current estimate of the fraction of vertices in the two groups, represents messages from the nonneighbors of v. In the assortative case, it prevents BP from converging to a fixed point where every vertex is in the same community.

The update in Eq. 10 has a trivial fixed point , where every vertex is equally likely to be in either community. Writing and linearizing around this fixed point gives the following update rule for δ:More generally, in a block model with q communities, an affinity matrix , and an expected fraction of vertices in each community a, linearizing around the trivial fixed point and defining gives a tensor product operatorwhere T is the matrix defined in Eq. 8.

This shows that the spectral properties of the nonbacktracking matrix are closely related to BP. Specifically, the trivial fixed point is unstable, leading to a fixed point that is correlated with the community structure, exactly when has an eigenvalue greater than 1. However, by avoiding the fixed point where all of the vertices belong to the same group, we suppress B’s leading eigenvalue; thus the criterion for instability is , where v is T’s leading eigenvalue and is B’s second eigenvalue. This is equivalent to Eq. 9 in the case where the groups are of equal size.

In general, the BP algorithm provides a slightly better agreement with the actual group assignment, because it approximates the Bayes-optimal inference of the block model. On the other hand, the BP update rule depends on the parameters of the block model, and if these parameters are unknown they need to be learned, which presents additional difficulties (12). In contrast, our spectral algorithm does not depend on the parameters of the block model, giving an advantage over BP in addition to its computational efficiency.