# Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [On the Expressive Power of Geometric Graph Neural Networks](https://mlsanity.com/paper/2301.09308/) (2023)
- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Graph Homomorphism Convolution](https://mlsanity.com/paper/2005.01214/) (2020)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [On the Expressivity of Persistent Homology in Graph Learning](https://mlsanity.com/paper/2302.09826/) (2023)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [Expectation-Complete Graph Representations with Homomorphisms](https://mlsanity.com/paper/2306.05838/) (2023)
- [Homomorphism Counts as Structural Encodings for Graph Learning](https://mlsanity.com/paper/2410.18676/) (2024)
- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)

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

- [Have Graph -- Will Lift? The Case for Higher-Order Benchmarks](https://mlsanity.com/paper/2605.07397/) (2026)

## 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 (pseudo-)metric by showing that i.) it can be efficiently approximated while retaining distinction capabilities, ii.) it provides a granular approach to graph distinction, and, iii.) it serves as a structural encoding, extending the concept of homomorphism-based descriptors to attributed graphs, thus improving the predictive capabilities of graph neural networks.