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

arXiv:2511.03068 · cs.LG · Submitted 2025-11-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Graph Homomorphism Distortion".

Jane: The gist The graph homomorphism distortion aims to encode a measure of similarity between two attributed graphs based on individual attribute distances through homomorphisms,

Tom: First, who's behind it and why it matters.

Paper summary: Jane: So to wrap up on this paper, "Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs". What’s the biggest thing we’re getting from this work?

Tom: They’ve developed a way to measure how different two graphs are by looking at how much their node features get warped when you try to map one onto the other using graph homomorphisms. It moves beyond just counting edges or checking if two graphs have the same basic topology.

Lu: The authors show that this distortion is actually a pseudo-metric on these vertex-attributed graphs under certain conditions, which means we can treat graph similarity like distance in some mathematical space, which is pretty powerful for learning.

Meng: But what about the practical side? If I have a massive graph, computing this distortion seems computationally intensive. How much does that actually add to the training pipeline?

Jane: So it’s a tool that helps us build more informed representations, even if we have to be careful about when we apply it and what assumptions are holding true. That’s the core idea behind "Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs."

Tom: Exactly. It gives us a concrete way to quantify that closeness in terms of feature distortion across the graph structure.

Conclusion: SEGMENT: Conclusion - Title and Implications**

Tom: So we're wrapping up on this paper, "Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs." The authors essentially developed a mathematical way to measure how much two graphs are different based on the feature distortion required when mapping one onto the other.

Jane: That sounds like a lot of math. So in simple terms, what's the big deal with this specific title and these authors? What do we need to know about this paper for our work?

Tom: The core idea is moving beyond just looking at the graph shape or structure when node features are also involved. This distortion captures a continuous idea of dissimilarity that depends on those individual attributes, not just the connections.

Lu: The authors showed this distortion acts like a pseudo-metric under specific conditions, which means we can treat graph similarity like distance in some mathematical space that is useful for learning.

Meng: But they had to be careful with the requirements for it to be a true metric, those conditions about the attribute functions being injective and permutation invariant. Does that mean this whole structural encoding thing might not work on messy data?

Lalam: The paper points out exactly that when those mathematical conditions are perfectly met, it becomes a proper metric. But the current work shows its utility even when those assumptions aren't perfectly satisfied; it’s a strong tool for encoding but you have to be aware of the context.

Jane: So what does this mean for us right now in building our AI models? If we use this distortion as an encoding, how does that change the way we build and train them?

Tom: It acts as an inductive bias. If this measure captures meaningful differences between graphs based on their features, it should help models like GCNs or GATs perform better across different tasks. The authors showed it improves performance when you use this encoding along with standard counts.

Lu: It does suggest a necessary shift toward representation learning where we need these kinds of measures to truly capture the underlying relationships between data and structure, moving beyond just binary similarity checks.

Meng: I still have my reservations about those completeness conditions they mentioned for it to be a true metric—the injective and permutation invariant parts. If we use this in production, do we really trust that those assumptions hold up on our messy real-world traffic data?

Lalam: The authors are pretty clear that when those conditions are met, it becomes a proper metric. But the current work shows its utility as a pseudo-metric even when those assumptions aren't perfectly satisfied; it’s a strong tool for encoding, but you have to be aware of the context.

Jane: So it's a tool that helps us build more informed representations, even if we have to be careful about when we apply it and what assumptions are holding true. Next up, we’re going to look at some of those experimental results where they tested this against other methods.

University of Fribourg · AMLAB, University of Amsterdam

cs.LG

Submitted: 2025-11-04

Updated: 2026-10-15

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 83/100

The gist: The gist The graph homomorphism distortion aims to encode a measure of similarity between two attributed graphs based on individual attribute distances through homomorphisms, providing a new metric

Key concepts

Attribute Distortion (dis($δ$))
This measures the maximum distance between the features of corresponding nodes in two graphs after applying a specific mapping (homomorphism). It quantifies how much individual node attributes are stretched or moved when transforming one graph structure into another, focusing purely on feature differences.
Graph Homomorphism Distortion (dHD)
This is the core metric, defined as the maximum distortion over all possible homomorphisms between two graphs. It represents the minimal worst-case feature distortion required to map one graph onto another, providing a single value to compare attributed graphs based on their structural and attribute similarities.
Structural Encoding ($Γ(G)F$)
This concept uses the homomorphism distortion to create a complete representation of a graph. By calculating dHD between the graph and a set of reference graphs (like $G_n$), it generates an encoding that can distinguish non-isomorphic graphs, effectively turning structural similarity into a usable feature for machine learning.
Pseudo-metric Properties
dHD satisfies key properties like being zero when comparing a graph to itself ($dHD(G, G) = 0$) and being symmetric. Furthermore, it is 1-Lipschitz continuous, meaning the distortion between two graphs is bounded by the distance between their feature functions, ensuring it behaves predictably in metric spaces.

Summary

The gist The graph homomorphism distortion aims to encode a measure of similarity between two attributed graphs based on individual attribute distances through homomorphisms, providing a new metric to distinguish them all and in the latent space bind them

Introduction and Motivation

Existing approaches to assessing the expressivity of graph neural networks often ignore features in favor of structure, making it difficult to compare graphs with close features The paper addresses this by developing a new (pseudo-)metric based on graph homomorphisms, which measures the minimal worst-case distortion that node features are subjected to when mapping one graph to another This measure is inspired by concepts from metric geometry and aims to study expressivity in a more fine-grained manner than existing binary measures

Definition of Graph Homomorphism Distortion

The core of the paper is the definition of homomorphism distortion, which involves defining attribute distortion first Attribute distortion dis(φ) is defined as max v∈V∥f(v) − f′(φ(v))∥ when homomorphisms φ and φ′ exist between two attributed graphs G and G' Graph homomorphism distortion dHD(G, G') is then defined as max inf φ∈G dis(φ), inf φ′∈G′ dis(φ') This measure studies the distortion of vertex attributes via graph homomorphisms

Theoretical Properties of the Distortion

The homomorphism distortion is shown to be a pseudo-metric on vertex-attributed graphs, satisfying properties such as dHD(G, G) = 0 and symmetry It is also 1-Lipschitz continuous, meaning dHD((V, E, f),(V, E, g)) ≤∥f − g∥∞ The paper further demonstrates that the distortion is complete when attribute functions f and f′ are injective and permutation invariant under certain conditions Specifically, Lemma 3.7 shows that provided attribute functions are injective, permutation-invariant, and equal according to Definition 3.4, the function dHD is a metric

Discriminative Power and Encoding

The paper establishes the completeness of the homomorphism distortion as a graph encoding by defining Γ(G)F = [dHD(G, F)]F ∈F Lemma 4.9 proves that if F = Gn, then Γ(G)F is complete, meaning it distinguishes non-isomorphic graphs To handle the incomputability of computing dHD between arbitrary graphs, the authors propose an expectation-complete random graph encoding where ςF is defined as dHD(G, F)eF Lemma 4.12 shows that if D has full support on Gn and F ∼ D, then ςF is expectation-complete

Experimental Validation

Empirical validation confirms the utility of the distortion measure in several scenarios In non-learning scenarios, the dHD distinguishes non-isomorphic graphs in hard k-WL classes, achieving a high distinction rate on BREC data compared to 1-WL and 3-WL tests In learning scenarios, using the homomorphism distortion encoding as an inductive bias improves performance across GAT, GCN, and GIN models compared to standard homomorphism counts The best performance is achieved when complementing the distortion encoding with either Hom or Sub counts

Conclusion

The paper concludes that the graph homomorphism distortion captures a continuous notion of dissimilarity and fully characterizes graphs under certain assumptions, inducing a metric on the space of isomorphism equivalence classes It serves as both a structural encoding and an inductive bias that improves predictive performance in graph learning tasks The work suggests a necessary shift in graph representation learning to move beyond restricted expressivity measurements

--- Page 1 ---

The gist The graph homomorphism distortion aims to encode a measure of similarity between two attributed graphs based on individual attribute distances through homomorphisms, providing a new metric to distinguish them all and in the latent space bind them

Conclusion

The paper concludes that the graph homomorphism distortion captures a continuous notion of dissimilarity and fully characterizes graphs under certain assumptions, inducing a metric on the space of isomorphism equivalence classes It serves as both a structural encoding and an inductive bias that improves predictive performance in graph learning tasks

--- Page 2 ---

The gist The graph homomorphism distortion aims to encode a measure of similarity between two attributed graphs based on individual attribute distances through homomorphisms, providing a new metric to distinguish them all and in the latent space bind them

Theoretical Properties of the Distortion

The homomorphism distortion is shown to be a pseudo-metric on vertex-attributed graphs, satisfying properties such as dHD(G, G) = 0 and symmetry It is also 1-Lipschitz continuous, meaning dHD((V, E, f),(V, E, g)) ≤∥f − g∥∞ The paper further demonstrates that the distortion is complete when attribute functions f and f′ are injective and permutation invariant under certain conditions<ref:

Improvements for AI systems

  1. Bold structural encoding for graph neural networks: The homomorphism distortion encoding, defined as Γ(G)F = [dHD(G, F)]F ∈F, can be used as a novel inductive bias, yielding in better performance than homomorphism counts across all models in learning scenarios. This allows GNNs to incorporate fine-grained structural similarity measures beyond traditional graph isomorphism tests.

  2. Improved discriminative power for hard graph classes: The metric's extension, dHD, provides the highest discriminative power, outperforming the WL metric where it shows TWL ⊆ THD, enabling a finer distinction between non-isomorphic graphs in challenging k-WL classes.

  3. Feature-structure coupling analysis: By examining how distortion changes with different attribute functions, the system can identify that graph structure and feature-structure relationships are intrinsically coupled, providing insight into how features influence structural roles in graph representation learning.

  4. Expectation-complete encoding for robust classification: The random graph encoding based on homomorphism distortion, denoted as ςF is expectation-complete, allows for the creation of representations that are robust to sampling and can be used as a novel inductive bias for graph regression tasks.

Abstract

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.

Sources

Related papers