Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them

This paper introduces a novel graph homomorphism distortion metric that quantifies the minimal worst-case distortion of node features during graph mapping, thereby addressing the limitations of structure-only expressivity measures by enabling efficient graph comparison, complementing existing methods like 1-WL, and facilitating the creation of structural encodings that enhance graph neural network performance.

The Gist

Imagine you are trying to teach a computer to understand the difference between two complex structures, like two different cities or two different social networks. In the world of Graph Neural Networks (GNNs), these structures are called graphs (dots connected by lines).

For a long time, computers have been very good at checking if two graphs are identical (isomorphic). It's like checking if two fingerprints are a perfect match. If they are, great. If not, the computer says, "Different."

The Problem:
But real life isn't binary. Two cities might look 99% the same, with just one street changed, or two social networks might have the same number of people but slightly different friendships. Old methods treat these "almost the same" graphs as completely different, or they ignore the actual content (the features) of the dots and only look at the shape of the lines. It's like judging two books solely by their cover design, ignoring the story inside.

The Solution: "Graph Homomorphism Distortion"
This paper introduces a new way to measure how similar two graphs are, called Graph Homomorphism Distortion. Here is how it works, using some everyday analogies:

1. The "Stretched Rubber Sheet" Analogy

Imagine you have two rubber sheets with patterns drawn on them.

• Graph A is one sheet.
• Graph B is another sheet.

To compare them, you try to stretch and map Graph A onto Graph B. You try to line up the dots (nodes) and the lines (edges) as best as you can.

• The "Homomorphism": This is the act of mapping one graph onto the other. It's like trying to fit a puzzle piece into a slot.
• The "Distortion": When you stretch Graph A to fit Graph B, the features (like the color or weight of the dots) might get stretched or squished.
  • If the dots on Graph A are "Red" and the matching dots on Graph B are "Red," there is zero distortion.
  • If the dots on Graph A are "Red" but the matching dots on Graph B are "Blue," there is high distortion.

The Graph Homomorphism Distortion measures the maximum amount of "stretching" or "squishing" required to make the features of one graph fit onto the other.

2. Why is this better than the old way?

The old method (called the Weisfeiler-Leman test) is like a strict bouncer at a club.

• Old Method: "Do you have the exact same ID? Yes? You're in. No? You're out." It can't tell the difference between a perfect twin and a cousin who looks 99% like them.
• New Method (Distortion): It's like a tailor measuring a suit. "This suit is 2 inches too long in the arm, and 1 inch too short in the leg." It gives you a score of how different they are. It captures "slight differences" that the old method misses.

3. The "Travel Guide" Analogy (How they calculate it)

Calculating the perfect distortion between two giant graphs is mathematically impossible to do perfectly (it's too hard, like counting every grain of sand on a beach).

So, the authors came up with a clever shortcut. Instead of trying to map Graph A directly to Graph B, they use a Travel Guide (a family of smaller, simpler graphs like trees or loops).

• They ask: "How hard is it to fit Graph A into this small Tree?"
• They ask: "How hard is it to fit Graph B into this small Tree?"
• If Graph A fits the Tree easily (low distortion) but Graph B struggles (high distortion), then A and B are different.

By testing against many different "Travel Guides" (small graphs), they can build a unique "fingerprint" for every graph. If two graphs have the same fingerprint, they are essentially the same. If the fingerprints differ, the distortion score tells you how different they are.

4. What did they prove?

• It's a Ruler: They proved this new measure acts like a real ruler (a metric). It follows the rules of geometry: the distance from A to B is the same as B to A, and the distance from A to C is never longer than going A -> B -> C.
• It's Smarter: It can distinguish between graphs that the old "bouncer" method thinks are identical.
• It Helps AI Learn: When they used this new "ruler" to help AI models learn (specifically for predicting chemical properties of molecules), the AI got much better at its job. It was like giving the AI a better pair of glasses.

Summary

Think of Graph Homomorphism Distortion as a new, ultra-sensitive ruler for the internet of connections. Instead of just asking "Are these two things identical?", it asks, "How much would I have to stretch and squish one to make it look like the other?"

This allows computers to understand the nuance in data, distinguishing between things that are "almost the same" versus things that are "completely different," leading to smarter and more accurate AI.

Technical Summary

1. Problem Statement

Graph Neural Networks (GNNs) rely on the interplay between graph structure and node features. However, existing methods for assessing GNN expressivity (the ability to distinguish between different graphs) suffer from two major limitations:

• Binary Nature: The standard benchmark, the Weisfeiler-Leman (WL) hierarchy, provides a binary output (isomorphic or not). It cannot quantify "how different" two non-isomorphic graphs are, nor can it capture slight structural or feature-based differences.
• Feature Ignorance: Most expressivity measures focus solely on graph topology, ignoring node features. While some extensions exist for geometric graphs, they often fail to account for approximate similarity or handle general vertex attributes effectively.

The authors argue that there is a need for a metric that is continuous (measuring degrees of difference), feature-aware, and structurally rigorous to better distinguish graphs and improve GNN performance.

2. Methodology: Graph Homomorphism Distortion (GHD)

The paper introduces a novel (pseudo-)metric called Graph Homomorphism Distortion ($d_{HD}$). It is inspired by the Gromov–Hausdorff distance from metric geometry but adapted for graphs using homomorphisms.

Core Definitions

• Attribute Distortion: For two attributed graphs $G=(V, E, f)$ and $G'=(V', E', f')$, and a homomorphism $\phi: V \to V'$, the attribute distortion is the maximum norm of the difference between a node's feature and its mapped counterpart:
  $$\text{dis}(\phi) := \max_{v \in V} \|f(v) - f'(\phi(v))\|$$
• Graph Homomorphism Distortion ($d_{HD}$): Defined as the maximum of the infimum distortions in both directions (from $G$ to $G'$ and $G'$ to $G$):
  $$d_{HD}(G, G') := \max \left( \inf_{\phi \in \text{Hom}(G, G')} \text{dis}(\phi), \inf_{\phi' \in \text{Hom}(G', G)} \text{dis}(\phi') \right)$$
  If no homomorphisms exist, the infimum is set to $\infty$.

Theoretical Properties

• Pseudo-Metric: $d_{HD}$ satisfies non-negativity, symmetry, and the triangle inequality. It is a true metric on the quotient space of graphs modulo isomorphism (i.e., $d_{HD}(G, G') = 0$ if and only if $G \cong G'$ under specific conditions on the feature functions).
• Completeness: Under assumptions that feature functions are injective and permutation-invariant (often relying on local neighborhood information), $d_{HD}$ can distinguish any pair of non-isomorphic graphs.
• Discriminative Power: The authors prove that the topology induced by $d_{HD}$ is strictly finer than that of the 1-WL test. This means $d_{HD}$ can distinguish graphs that 1-WL cannot, and it provides a continuous measure of distance rather than a binary one.
• Lipschitz Continuity: The metric is 1-Lipschitz continuous with respect to changes in attribute functions, ensuring stability.

Practical Approximation

Since computing exact homomorphism counts/distortions is NP-complete, the authors propose an Expectation-Complete approximation:

1. Random Graph Encoding: Instead of enumerating all graphs, they sample a finite family of reference graphs $\mathcal{F}$ (e.g., trees or cycles with bounded treewidth).
2. Sampling Homomorphisms: They sample homomorphisms between the input graph and the reference family.
3. Encoding: The graph is encoded as a vector of distortions to these sampled references. Theoretically, as the number of samples increases, this encoding becomes complete (able to distinguish any non-isomorphic pair).

3. Key Contributions

1. Novel Metric: Introduction of Graph Homomorphism Distortion, a continuous metric that jointly considers graph structure and node features.
2. Theoretical Guarantees: Proof that $d_{HD}$ is a complete metric (under specific conditions) and strictly more discriminative than the 1-WL hierarchy.
3. Structural Encoding: Development of a graph encoding based on $d_{HD}$ that serves as a powerful inductive bias.
4. Empirical Validation: Demonstration that this encoding improves GNN performance on both graph classification (distinguishing hard non-isomorphic classes) and regression tasks.

4. Experimental Results

The authors evaluated their method on two primary benchmarks:

A. Non-Learning Scenarios (BREC Dataset)

• Task: Distinguishing non-isomorphic graphs in hard classes (e.g., CFI graphs, strongly regular graphs) where 1-WL and 3-WL often fail.
• Findings:
  • $d_{HD}$ achieved 100% distinction on several difficult classes where 3-WL and Persistent Homology (PH) failed or performed poorly.
  • The method is robust to different feature encodings (Random Walk Positional Encodings vs. Shortest Path Encodings).
  • It successfully validated the "Expectation-Completeness" hypothesis, showing that sampling a small number of reference graphs is sufficient for high discrimination.

B. Learning Scenarios (ZINC-12K Dataset)

• Task: Graph regression (predicting molecular properties) using GAT, GCN, and GIN architectures.
• Findings:
  • Using $d_{HD}$ as an inductive bias (concatenated with standard features) significantly reduced Mean Absolute Error (MAE) compared to baseline models.
  • Synergy: Combining $d_{HD}$ with traditional homomorphism counts yielded the best results, suggesting the two measures capture complementary structural information.
  • The method outperformed state-of-the-art baselines using homomorphism counts alone (e.g., Spasm).

5. Significance and Impact

• Beyond Binary Classification: The paper moves the field away from binary "isomorphic/not-isomorphic" thinking toward a continuous spectrum of graph similarity, which is more aligned with real-world data where graphs are rarely perfectly identical but often structurally similar.
• Feature-Structure Integration: It provides a principled mathematical framework for measuring how structural mappings distort node features, addressing a gap in current GNN expressivity theory.
• Practical Utility: By proving that this theoretically complex metric can be approximated efficiently and used as a learnable encoding, the authors offer a practical tool to boost the performance of existing GNN architectures without requiring fundamental architectural changes.
• Future Directions: The work suggests that current benchmarks relying solely on structural isomorphism are insufficient and calls for new metrics that account for feature geometry and approximate similarity.

In summary, the paper proposes a rigorous, continuous metric for graph comparison that unifies structural and feature information, proving both theoretically superior to WL tests and empirically effective in improving GNN predictive capabilities.