Homomorphism distortion: A metric to distinguish them all and in the latent space bind them

Martin Carrasco, Olga Zaghen, Erik J. Bekkers, Bastian RieckarXiv 2025 · DOI · arXiv

Abstract Graph Neural Networks (GNNs) often struggle with expressivity, particularly in distinguishing non-isomorphic graphs that share similar local structures. Traditional benchmarks like the Weisfeiler-Leman (WL) test provide binary outcomes and often ignore node features. This paper introduces Graph Homomorphism Distortion ($d_{HD}$), a continuous pseudo-metric that measures the minimum feature distortion required to map one vertex-attributed graph to another via a homomorphism. By leveraging $d_{HD}$ as a structural encoding relative to a reference family of graphs, the authors demonstrate a significant leap in discriminative power. Experimental results on the BREC and ZINC-12k datasets show that $d_{HD}$ achieves perfect distinction on hard graph classes and substantially improves regression performance in molecular property prediction.

Introduction

The expressivity of Graph Neural Networks (GNNs) is typically measured by their ability to distinguish non-isomorphic graphs. The Weisfeiler-Leman (WL) test has long served as the standard for this task. However, the WL test is inherently limited: it is a binary classifier that fails to quantify the degree of similarity between graphs and often neglects node-level attributes, such as atomic properties in chemical graphs.

To address these limitations, the authors propose Graph Homomorphism Distortion ($d_{HD}$). This metric shifts the focus from binary isomorphism to a continuous measure of "warping" cost. It integrates both topological structure and node features, providing a more nuanced and robust framework for graph comparison.

The Graph Homomorphism Distortion Metric

The core of the proposal is the concept of attribute distortion. When mapping a graph $G$ to another graph $G'$ through a homomorphism $\varphi$ (a mapping that preserves adjacency), the node features of $G$ are compared to those of their images in $G'$. The distortion of the mapping is defined as the maximum discrepancy between these features. The $d_{HD}$ metric is then the minimum distortion achievable across all possible homomorphisms between the two graphs.

Figure 1: Illustration of graph homomorphism distortion $d_{HD}$, measuring the feature discrepancy when mapping graph $G$ to $G'$.

This approach is inspired by the Gromov–Hausdorff distance used in metric geometry, adapted here for the discrete and attributed nature of graphs. Unlike the 1-WL test, $d_{HD}$ is continuous and feature-aware, allowing it to capture subtle structural differences that combinatorial tests miss.

HD Encoding and Scalability

Calculating $d_{HD}$ directly between two large graphs is computationally prohibitive as it involves finding homomorphisms, an NP-complete problem. To make this metric practical, the authors introduce HD Encoding. Instead of direct comparison, they measure the distance from a target graph $G$ to a "reference family" $\mathcal{F}$ of smaller, simpler graphs (e.g., cycles or trees).

Figure 2: Approximating the incomputable $d_{HD}(G, G')$ by measuring distances to a reference family $\mathcal{F}$.

This process generates a "distance profile" vector for each graph. These profiles serve as high-dimensional structural encodings that can be integrated into standard GNN architectures. The authors provide theoretical guarantees that this approximation remains highly discriminative, effectively "binding" graphs in a latent space defined by their relationships to the reference family.

Experimental Evaluation

The effectiveness of $d_{HD}$ was tested on two major benchmarks:

  • BREC (Bias-Relief Expressivity Benchmark): This dataset contains pairs of non-isomorphic graphs specifically designed to challenge GNNs. The $d_{HD}$ method achieved a 100% distinction rate on several difficult categories, including distance-regular graphs, where 1-WL and even 3-WL tests typically fail.
  • ZINC-12k: In molecular regression tasks, adding HD Encodings to baseline models like GIN significantly reduced the Mean Absolute Error (MAE) from 0.246 to 0.138. This demonstrates that $d_{HD}$ captures critical structural information relevant to real-world chemical properties.

Conclusion

Graph Homomorphism Distortion provides a powerful new lens for graph representation learning. By moving beyond binary isomorphism to a continuous, feature-aware metric, it offers both theoretical depth and practical performance gains. While the choice of reference families remains an area for future optimization, $d_{HD}$ represents a significant step toward GNNs that can truly "distinguish them all."

Summary updated

BibTeX
@misc{carrasco2025homomorphism,
  author = {Martin Carrasco and Olga Zaghen and Erik J. Bekkers and Bastian Rieck},
  title = {{Homomorphism distortion: A metric to distinguish them all and in the latent space bind them}},
  year = {2025},
  eprint = {2511.03068},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.03068},
}
Figure