# Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 65 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Fairness in Machine Learning](https://mlsanity.com/paper/2012.15816/) (2020)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Fair Mixup: Fairness via Interpolation](https://mlsanity.com/paper/2103.06503/) (2021)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Estimating Generalization under Distribution Shifts via Domain-Invariant Representations](https://mlsanity.com/paper/2007.03511/) (2020)
- [On the Stability of Graph Convolutional Neural Networks under Edge Rewiring](https://mlsanity.com/paper/2010.13747/) (2020)
- [A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation](https://mlsanity.com/paper/2101.05380/) (2021)
- [Fast Unbalanced Optimal Transport on a Tree](https://mlsanity.com/paper/2006.02703/) (2020)
- [Unbalanced Optimal Transport: Dynamic and Kantorovich Formulation](https://mlsanity.com/paper/1508.05216/) (2015)
- [Coalgebraic Behavioral Metrics](https://mlsanity.com/paper/1712.07511/) (2017)

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

- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Pairwise Alignment Improves Graph Domain Adaptation](https://mlsanity.com/paper/2403.01092/) (2024)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Limits, approximation and size transferability for GNNs on sparse graphs via graphops](https://mlsanity.com/paper/2306.04495/) (2023)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Subgraph Pooling: Tackling Negative Transfer on Graphs](https://mlsanity.com/paper/2402.08907/) (2024)
- [A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation](https://mlsanity.com/paper/2410.19265/) (2024)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Explaining and Adapting Graph Conditional Shift](https://mlsanity.com/paper/2306.03256/) (2023)
- [Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks](https://mlsanity.com/paper/2401.03350/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs](https://mlsanity.com/paper/2302.00713/) (2023)
- [Beyond Generalization: A Survey of Out-Of-Distribution Adaptation on Graphs](https://mlsanity.com/paper/2402.11153/) (2024)
- [Graph Data Selection for Domain Adaptation: A Model-Free Approach](https://mlsanity.com/paper/2505.17293/) (2025)
- [Few-Shot Causal Representation Learning for Out-of-Distribution Generalization on Heterogeneous Graphs](https://mlsanity.com/paper/2401.03597/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)
- [Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality](https://mlsanity.com/paper/2501.03113/) (2025)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Subsampling Graphs with GNN Performance Guarantees](https://mlsanity.com/paper/2502.16703/) (2025)
- [Distances for Markov Chains, and Their Differentiation](https://mlsanity.com/paper/2302.08621/) (2023)
- [Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessing](https://mlsanity.com/paper/2503.00547/) (2025)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning](https://mlsanity.com/paper/2508.06588/) (2025)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)

## Abstract (arXiv)

Understanding generalization and robustness of machine learning models fundamentally relies on assuming an appropriate metric on the data space. Identifying such a metric is particularly challenging for non-Euclidean data such as graphs. Here, we propose a pseudometric for attributed graphs, the Tree Mover's Distance (TMD), and study its relation to generalization. Via a hierarchical optimal transport problem, TMD reflects the local distribution of node attributes as well as the distribution of local computation trees, which are known to be decisive for the learning behavior of graph neural networks (GNNs). First, we show that TMD captures properties relevant to graph classification: a simple TMD-SVM performs competitively with standard GNNs. Second, we relate TMD to generalization of GNNs under distribution shifts, and show that it correlates well with performance drop under such shifts.