Graph Comparison via the Non-backtracking Spectrum

Abstract

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 metric based on the spectrum of the non-backtracking graph operator and show that it can not 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 non-backtracking spectral embedding and show how this metric can be used in a standard classification problem of empirical graphs.

11 pages, 5 figures, 2 tables

References in corpus (11)

• Cooperative Game Theory Approaches for Network Partitioning
• Social Structure of Facebook Networks
• Spectral redemption: clustering sparse networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Graph Isomorphism in Quasipolynomial Time
• Spectral entropies as information-theoretic tools for complex network comparison
• DELTACON: A Principled Massive-Graph Similarity Function
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Spectral Clustering of Graphs with the Bethe Hessian
• Spectral density of the non-backtracking operator
• Marked length rigidity for one dimensional spaces

Cited by in corpus (3)

• Network comparison and the within-ensemble graph distance
• netrd: A library for network reconstruction and graph distances
• Node Immunization with Non-backtracking Eigenvalues