Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them
Not on the map. Why?
Abstract (arXiv)
A large driver of the complexity of graph learning is the interplay between structure and features. When analyzing the expressivity of graph neural networks, however, existing approaches ignore features in favor of structure, making it nigh-impossible to assess to what extent two graphs with close features should be considered similar. We address this by developing a new (pseudo-)metric based on graph homomorphisms. Inspired by concepts from metric geometry, our graph homomorphism distortion measures the minimal worst-case distortion that node features of one graph are subjected to when mapping one graph to another. We demonstrate the utility of our novel measure by showing that (i.) it can be efficiently calculated under some additional assumptions, (ii.) it complements existing expressivity measures like 1-WL, and (iii.) it permits defining structural encodings, which improve the predictive capabilities of graph neural networks.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 17 of its 33 references that are in the map. First posted on arXiv 4 Nov 2025.
Builds on
17 of 33 references.
References · 17
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2020Benchmarking Graph Neural Networkscited by 672
- 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
- 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
- 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
- 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
- 2023An Empirical Study of Realized GNN Expressivenesscited by 33
- 2020Graph Homomorphism Convolutioncited by 27
- 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
- 2023On the Expressivity of Persistent Homology in Graph Learningcited by 18
- 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
5 more
- 2025No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasetscited by 16
- 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
- 2023Expectation-Complete Graph Representations with Homomorphismscited by 10
- 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 6
- 2023Structural Node Embeddings with Homomorphism Countscited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.