# An embedding-based distance for temporal graphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 99 references that are in the map.
- First posted on arXiv 23 Jan 2024.

## Builds on (most cited first, 30 of 32)

- [T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction](https://mlsanity.com/paper/1811.05320/) (2018)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Parametric UMAP embeddings for representation and semi-supervised learning](https://mlsanity.com/paper/2009.12981/) (2020)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Understanding graph embedding methods and their applications](https://mlsanity.com/paper/2012.08019/) (2020)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [Deep Graph Generators: A Survey](https://mlsanity.com/paper/2012.15544/) (2020)
- [Deep Graph Similarity Learning: A Survey](https://mlsanity.com/paper/1912.11615/) (2019)
- [DELTACON: A Principled Massive-Graph Similarity Function](https://mlsanity.com/paper/1304.4657/) (2013)
- [Contact patterns among high school students](https://mlsanity.com/paper/1409.5318/) (2014)
- [Can co-location be used as a proxy for face-to-face contacts?](https://mlsanity.com/paper/1712.06346/) (2017)
- [Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach](https://mlsanity.com/paper/1308.0723/) (2013)
- [Community Discovery in Dynamic Networks: a Survey](https://mlsanity.com/paper/1707.03186/) (2017)
- [An information-theoretic, all-scales approach to comparing networks](https://mlsanity.com/paper/1804.03665/) (2018)
- [Measuring large-scale social networks with high resolution](https://mlsanity.com/paper/1401.7233/) (2014)
- [Network comparison and the within-ensemble graph distance](https://mlsanity.com/paper/2008.02415/) (2020)
- [The Resistance Perturbation Distance: A Metric for the Analysis of Dynamic Networks](https://mlsanity.com/paper/1605.01091/) (2016)
- [Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian](https://mlsanity.com/paper/2006.04510/) (2020)
- [Detecting sequences of system states in temporal networks](https://mlsanity.com/paper/1803.04755/) (2018)
- [Gender and collaboration patterns in a temporal scientific authorship network](https://mlsanity.com/paper/2005.13512/) (2020)
- [Temporal networks of face-to-face human interactions](https://mlsanity.com/paper/1305.3532/) (2013)
- [Comparing Temporal Graphs Using Dynamic Time Warping](https://mlsanity.com/paper/1810.06240/) (2018)
- [Detecting social (in)stability in primates from their temporal co-presence network](https://mlsanity.com/paper/1909.09090/) (2019)
- [Measuring and utilizing temporal network dissimilarity](https://mlsanity.com/paper/2111.01334/) (2021)
- [Learning distributed representations with efficient SoftMax normalization](https://mlsanity.com/paper/2303.17475/) (2023)
- [Exploring Temporal Networks with Greedy Walks](https://mlsanity.com/paper/1508.00693/) (2015)
- [Graph Distance from the Topological View of Non-backtracking Cycles](https://mlsanity.com/paper/1807.09592/) (2018)

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

- [Predicting clinical outcomes from patient care pathways represented with temporal knowledge graphs](https://mlsanity.com/paper/2502.21138/) (2025)
- [Transfer Learning for Temporal Link Prediction](https://mlsanity.com/paper/2504.10925/) (2025)
- [Filtration-Based Representation Learning for Temporal Graphs](https://mlsanity.com/paper/2502.10076/) (2025)
- [A temporal graph dissimilarity measure capturing epidemic spreading behavior](https://mlsanity.com/paper/2610.16456/) (2026)

## Abstract (arXiv)

Temporal graphs are commonly used to represent time-resolved relations between entities in many natural and artificial systems. Many techniques were devised to investigate the evolution of temporal graphs by comparing their state at different time points. However, quantifying the similarity between temporal graphs as a whole is an open problem. Here, we use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We study the case of a matched pair of graphs, when a known relation exists between their nodes, and the case of unmatched graphs, when such a relation is unavailable and the graphs may be of different sizes. We use empirical and synthetic temporal network data to show that the distance we introduce discriminates graphs with different topological and temporal properties. We provide an efficient implementation of the distance computation suitable for large-scale temporal graphs.