# Network comparison and the within-ensemble graph distance

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2020.

## Built on by (most cited first, 7 of 7)

- [Challenges of Generating Structurally Diverse Graphs](https://mlsanity.com/paper/2409.18859/) (2024)
- [Adaptive Dependency Learning Graph Neural Networks](https://mlsanity.com/paper/2312.03903/) (2023)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [Causal Temporal Graph Convolutional Neural Networks (CTGCN)](https://mlsanity.com/paper/2303.09634/) (2023)
- [GINA: Neural Relational Inference From Independent Snapshots](https://mlsanity.com/paper/2105.14329/) (2021)
- [Cognitive modelling with multilayer networks: Insights, advancements and future challenges](https://mlsanity.com/paper/2210.00500/) (2022)
- [Random Similarity Isolation Forests](https://mlsanity.com/paper/2502.19122/) (2025)

## Abstract (arXiv)

Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years a multitude of diverse, ad hoc solutions to this problem have been introduced. Here we propose that simple and well-understood ensembles of random networks (such as ErdHos-R'enyi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model, and preferential attachment networks) are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.