Metrics for Graph Comparison: A Practitioner's Guide

Abstract

Comparison of graph structure is a ubiquitous task in data analysis and machine learning, with diverse applications in fields such as neuroscience, cyber security, social network analysis, and bioinformatics, among others. Discovery and comparison of structures such as modular communities, rich clubs, hubs, and trees in data in these fields yields insight into the generative mechanisms and functional properties of the graph. Often, two graphs are compared via a pairwise distance measure, with a small distance indicating structural similarity and vice versa. Common choices include spectral distances (also known as $\lambda$ distances) and distances based on node affinities. However, there has of yet been no comparative study of the efficacy of these distance measures in discerning between common graph topologies and different structural scales. In this work, we compare commonly used graph metrics and distance measures, and demonstrate their ability to discern between common topological features found in both random graph models and empirical datasets. We put forward a multi-scale picture of graph structure, in which the effect of global and local structure upon the distance measures is considered. We make recommendations on the applicability of different distance measures to empirical graph data problem based on this multi-scale view. Finally, we introduce the Python library NetComp which implements the graph distances used in this work.

References in corpus (14)

• Semi-Supervised Classification with Graph Convolutional Networks
• Graph Neural Networks: A Review of Methods and Applications
• Kernel method for nonlinear Granger causality
• Graph analysis of functional brain networks: practical issues in translational neuroscience
• A Survey on Graph Kernels
• Graph Matching Networks for Learning the Similarity of Graph Structured Objects
• NetSimile: A Scalable Approach to Size-Independent Network Similarity
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• State-dependent changes of connectivity patterns and functional brain network topology in Autism Spectrum Disorder
• Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
• Matrix versions of the Hellinger distance
• Multiscale Network Generation
• Detecting Topological Changes in Dynamic Community Networks
• Perturbation of the Eigenvectors of the Graph Laplacian: Application to Image Denoising

Cited by in corpus (12)

• Scalar Field Comparison with Topological Descriptors: Properties and Applications for Scientific Visualization
• Network comparison and the within-ensemble graph distance
• Criminal Networks Analysis in Missing Data scenarios through Graph Distances
• On a linear fused Gromov-Wasserstein distance for graph structured data
• Embedding and trajectories of temporal networks
• Finding Proper Time Intervals for Dynamic Network Extraction
• Learning common structures in a collection of networks. An application to food webs
• Nodal statistics-based equivalence relation for graph collections
• Atomistic Global Optimization X: A Python package for optimization of atomistic structures
• Magnitude and Topological Entropy of Digraphs
• Resistance distance distribution in large sparse random graphs
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling