A statistical test for network similarity

Abstract 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.