A statistical test for network similarity

In this article, we revisit and expand our prior work on graph similarity. As with our earlier work, we focus on a view of similarity which does not require node correspondence between graphs under comparison. Our work is suited to the temporal study of networks, change-point and anomaly detection and simple comparisons of static graphs. It provides a similarity metric for the study of (weakly) connected graphs. Our work proposes a metric designed to compare networks and assess the (dis)similarity between them. For example, given three different graphs with possibly different numbers of nodes, G _1 , G _2 and G _3 , we aim to answer two questions: a) ‘How different is G _1 from G _2 ?’ and b) ‘Is graph G _3 more similar to G _1 or to G _2 ?’. We illustrate the value of our test and its accuracy through several new experiments, using synthetic and real-world graphs.