# Graph Similarity Description: How Are These Graphs Similar?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 29 May 2021.

## Builds on (most cited first, 6 of 6)

- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Deep Graph Similarity Learning: A Survey](https://mlsanity.com/paper/1912.11615/) (2019)
- [Measuring Law Over Time: A Network Analytical Framework with an Application to Statutes and Regulations in the United States and Germany](https://mlsanity.com/paper/2101.11284/) (2021)
- [An information-theoretic, all-scales approach to comparing networks](https://mlsanity.com/paper/1804.03665/) (2018)
- [VoG: Summarizing and Understanding Large Graphs](https://mlsanity.com/paper/1406.3411/) (2014)

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

- [Differentially Describing Groups of Graphs](https://mlsanity.com/paper/2201.04064/) (2021)
- [Towards Learning in Grey Spatiotemporal Systems: A Prophet to Non-consecutive Spatiotemporal Dynamics](https://mlsanity.com/paper/2208.08878/) (2022)
- [BoolSkeleton: Boolean Network Skeletonization via Homogeneous Pattern Reduction](https://mlsanity.com/paper/2511.02196/) (2025)

## Abstract (arXiv)

How do social networks differ across platforms? How do information networks change over time? Answering questions like these requires us to compare two or more graphs. This task is commonly treated as a measurement problem, but numerical answers give limited insight. Here, we argue that if the goal is to gain understanding, we should treat graph similarity assessment as a description problem instead. We formalize this problem as a model selection task using the Minimum Description Length principle, capturing the similarity of the input graphs in a common model and the differences between them in transformations to individual models. To discover good models, we propose Momo, which breaks the problem into two parts and introduces efficient algorithms for each. Through an extensive set of experiments on a wide range of synthetic and real-world graphs, we confirm that Momo works well in practice.