mlsanityData to 7 Oct 2026

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

arXiv 2210.01906 ↗First posted 4 Oct 2022cs.LG stat.MLcited by 39

Not on the map. Why?

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.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 28 of its 65 references that are in the map. First posted on arXiv 4 Oct 2022.

Builds on

28 of 65 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,618
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  5. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  6. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  7. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  8. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  9. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  10. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  11. 2020Fairness in Machine Learningcited by 194
  12. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
16 more
  1. 2018Optimal Transport for structured data with application on graphscited by 170
  2. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  3. 2019Stability Properties of Graph Neural Networkscited by 125
  4. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  5. 2021Fair Mixup: Fairness via Interpolationcited by 109
  6. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
  7. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  8. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  9. 2020Graph Kernels: State-of-the-Art and Future Challengescited by 63
  10. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  11. 2020Estimating Generalization under Distribution Shifts via Domain-Invariant Representationscited by 56
  12. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25
  13. 2021A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimationcited by 17
  14. 2020Fast Unbalanced Optimal Transport on a Treecited by 16
  15. 2015Unbalanced Optimal Transport: Dynamic and Kantorovich Formulationcited by 6
  16. 2017Coalgebraic Behavioral Metricscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 15; 2025: 12; 2026: 2.

39 papers.

Sort:

  1. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 82
  2. 2023Mind the Label Shift of Augmentation-based Graph OOD Generalizationcited by 34
  3. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  4. 2024Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Treescited by 30
  5. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  6. 2024Pairwise Alignment Improves Graph Domain Adaptationcited by 25
  7. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
  8. 2024Learning Long Range Dependencies on Graphs via Random Walkscited by 18
  9. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
  10. 2024Subgraph Pooling: Tackling Negative Transfer on Graphscited by 17
  11. 2024A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptationcited by 16
  12. 2025No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasetscited by 16
27 more
  1. 2023Explaining and Adapting Graph Conditional Shiftcited by 14
  2. 2024Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networkscited by 8
  3. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  4. 2023The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNscited by 7
  5. 2025Graph Data Selection for Domain Adaptation: A Model-Free Approachcited by 7
  6. 2024Few-Shot Causal Representation Learning for Out-of-Distribution Generalization on Heterogeneous Graphscited by 6
  7. 2024Beyond Generalization: A Survey of Out-Of-Distribution Adaptation on Graphscited by 6
  8. 2024Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficientlycited by 6
  9. 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
  10. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  11. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  12. 2025Subsampling Graphs with GNN Performance Guaranteescited by 4
  13. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  14. 2023Distances for Markov Chains, and Their Differentiationcited by 2
  15. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  16. 2025Understanding Generalization in Node and Link Predictioncited by 2
  17. 2025Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learningcited by 2
  18. 2023Learning for Transductive Threshold Calibration in Open-World Recognitioncited by 1
  19. 2025What Expressivity Theory Misses: Message Passing Complexity for GNNscited by 1
  20. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  21. 2023Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networkscited by 0
  22. 2024A Spectral Framework for Evaluating Geodesic Distances Between Graphscited by 0
  23. 2024Energy Guided smoothness to improve Robustness in Graph Classificationcited by 0
  24. 2025On the Lipschitz Continuity of Set Aggregation Functions and Neural Networks for Setscited by 0
  25. 2025WILTing Trees: Interpreting the Distance Between MPNN Embeddingscited by 0
  26. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  27. 2026Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependencecited by 0