Graph comparison via the nonbacktracking spectrum

The comparison of graphs is a vitally important, yet difficult task which arises across a number of diverse research areas including biological and social networks. There have been a number of approaches to define graph distance, however, often these are not metrics (rendering standard data-mining techniques infeasible) or are computationally infeasible for large graphs. In this work we define a new pseudometric based on the spectrum of the nonbacktracking graph operator and show that it cannot only be used to compare graphs generated through different mechanisms but can reliably compare graphs of varying size. We observe that the family of Watts-Strogatz graphs lie on a manifold in the nonbacktracking spectral embedding and show how this metric can be used in a standard classification problem of empirical graphs.

Figure 1

The nonbacktracking spectrum of real and synthetic networks in the complex plane. Each eigenvalue ${\lambda }_k={\alpha }_k+{\beta }_{k}i$ is represented by the point $({\alpha }_k,{\beta }_k)$. (Top, left to right) The Karate Club graph [28], Davis Southern Women graph [29], and Florentine Families graph [30]. (Bottom, left to right) An Erdős-Rényi graph with edge connection probability $p=0.2$ for 50,100, and 150 vertices. The red circle marks the curve ${\alpha }^2+{\beta }^2=\sqrt{\rho \left(B\right)}$ where $\rho \left(B\right)$ is the spectral radius of $B$.

Figure 2

The rescaled nonbacktracking spectrum of $B^{\prime }$ for Erdős-Rényi graphs of size 50, 100, 150 (left to right) and edge connection probability 0.2 (top) and 0.8 (bottom). The rescaled spectrum is persistent as the number of vertices in the graph increases, however for small graphs there are finite size effects. In this example, the two parameter regimes are distinguished by the range over which the argument of the eigenvalues take.

Figure 3

Graph distance sensitivity for graphs generated from the same model with varying number of vertices. Here the models used are ER with edge connection probability $p=0.25$, WS with $k=4$ neighbor connections and rewiring probability $p=0.1$, and RR graphs with degree $d=5$. Distances are rescaled by the average distance ${\langle d(G_{100}^{*},G_{1000}^{\left(i\right)})\rangle }_i$ so that models can be overlaid and trends are preserved. (a) The average rescaled d-NBD ${\langle d(G_{100}^{*},G_n^{\left(i\right)})\rangle }_i$ between a graph with 100 vertices and graphs with identical model parameters. The distance is both stable and nonincreasing for all graph types considered. (b) Graph distance using only the largest $k$ eigenvalues. Since the smallest graph is of size 50, we must choose $k<100$ to be able to compare all graphs. Here the graph distance increases as $n$ increases, except for the random regular graph.

Figure 4

An embedding of Watts-Strogatz graphs with 200 vertices and with rewiring parameter $p\in [0,1]$ and vertex neighbors $k\in [2,199]$. Each point is the average embedding of 100 samples from a particular model. The three dimensions displayed at the three principle components extracted from a $10000$-dimensional embedding. Note that when $k=199$ we have a complete graph and so $(p,k)=(0,199)$ is identical to $(p,k)=(1,199)$.

Figure 5

A two-dimensional projection of the spectral embedding (6) of the graphs listed in Table 1. The projection was created using the t-SNE algorithm [44]. The samples from each graph collection are well clustered with zero overlap between them.