# Metrics for Graph Comparison: A Practitioner's Guide

arXiv: https://arxiv.org/abs/1904.07414 · HTML: https://mlsanity.com/paper/1904.07414/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2019.

## Built on by (most cited first, 30 of 38)

- [Advancing Agentic Systems: Dynamic Task Decomposition, Tool Integration and Evaluation using Novel Metrics and Dataset](https://mlsanity.com/paper/2410.22457/) (2024)
- [MM-DAG: Multi-task DAG Learning for Multi-modal Data -- with Application for Traffic Congestion Analysis](https://mlsanity.com/paper/2306.02831/) (2023)
- [On a linear fused Gromov-Wasserstein distance for graph structured data](https://mlsanity.com/paper/2203.04711/) (2022)
- [A Framework for Large Scale Synthetic Graph Dataset Generation](https://mlsanity.com/paper/2210.01944/) (2022)
- [Bures-Wasserstein Means of Graphs](https://mlsanity.com/paper/2305.19738/) (2023)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Geometry-Aware Edge Pooling for Graph Neural Networks](https://mlsanity.com/paper/2506.11700/) (2025)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [Backdoor Attacks on Discrete Graph Diffusion Models](https://mlsanity.com/paper/2503.06340/) (2025)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Prior-RadGraphFormer: A Prior-Knowledge-Enhanced Transformer for Generating Radiology Graphs from X-Rays](https://mlsanity.com/paper/2303.13818/) (2023)
- [Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2401.09953/) (2024)
- [Absolute Evaluation Measures for Machine Learning: A Survey](https://mlsanity.com/paper/2507.03392/) (2025)
- [On the Number of Edges of the Frechet Mean and Median Graphs](https://mlsanity.com/paper/2105.14397/) (2021)
- [Hypergraph Dissimilarity Measures](https://mlsanity.com/paper/2106.08206/) (2021)
- [A Supervised Learning Approach to Rankability](https://mlsanity.com/paper/2203.07364/) (2022)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [A General-Purpose Transferable Predictor for Neural Architecture Search](https://mlsanity.com/paper/2302.10835/) (2023)
- [Tipping Points of Evolving Epidemiological Networks: Machine Learning-Assisted, Data-Driven Effective Modeling](https://mlsanity.com/paper/2311.00797/) (2023)
- [Active Causal Learning for Decoding Chemical Complexities with Targeted Interventions](https://mlsanity.com/paper/2404.04224/) (2024)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [Improving Counterfactual Truthfulness for Molecular Property Prediction through Uncertainty Quantification](https://mlsanity.com/paper/2504.02606/) (2025)
- [Finding Counterfactual Evidences for Node Classification](https://mlsanity.com/paper/2505.11396/) (2025)
- [Generator-based Graph Generation via Heat Diffusion](https://mlsanity.com/paper/2602.03612/) (2026)
- [Approximate Fr'echet Mean for Data Sets of Sparse Graphs](https://mlsanity.com/paper/2105.04062/) (2021)
- [Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling](https://mlsanity.com/paper/2111.09696/) (2021)
- [Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models](https://mlsanity.com/paper/2207.02168/) (2022)
- [One Node at a Time: Node-Level Network Classification](https://mlsanity.com/paper/2208.02162/) (2022)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)
- [Higher-Order DeepTrails: Unified Approach to *Trails](https://mlsanity.com/paper/2310.04477/) (2023)

## Abstract (arXiv)

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