Relative Distance Labeling for Graph Neural Networks

32 concepts30 papers1 proposal

Graph Neural Networks (GNNs) are remarkably effective at learning representations of nodes by aggregating information from their local neighborhoods. However, when tasked with predicting relationships between nodes—such as link prediction, motif detection, or inductive reasoning—standard message-passing architectures hit a fundamental theoretical wall. They suffer from a structural blind spot caused by graph symmetry.

Relative distance labeling resolves this limitation by transforming abstract graph topologies into localized, structural coordinate systems.

The Blind Spot of Standard Message Passing

To understand why distance labeling is necessary, consider the task of link prediction: determining whether an edge should exist between two target nodes, $u$ and $v$.

In a standard GNN, message passing computes an embedding for node $u$ and an embedding for node $v$ independently, based on their respective neighborhoods. The model then combines these two embeddings to predict the link. However, as demonstrated by Muhan Zhang et al. in Link Prediction Based on Graph Neural Networks, if the graph contains structural symmetries, two entirely different pairs of nodes can yield identical pairs of embeddings.

Standard message passing is invariant to node permutations and bounded by the 1-Weisfeiler-Leman (1-WL) isomorphism test. It counts the features within a neighborhood but does not inherently know which specific nodes are being evaluated for a link during the aggregation process. If a neighboring node is two hops away from $u$ and one hop away from $v$, a standard GNN treats it merely as a neighbor, losing the joint spatial context relative to the $(u, v)$ pair. To make accurate topological predictions, the network must break this symmetry.

The Structural Coordinate System

Relative distance labeling solves this problem by conditioning the node features on the target query. Before running message passing, every node $x$ within a local subgraph is assigned a label based on its shortest-path (geodesic) distance to the target nodes.

For a target pair $(u, v)$, each node $x$ receives a coordinate-like label:

$$\ell(x) = (d(x, u), d(x, v))$$

where $d(x, u)$ is the shortest path distance between $x$ and $u$.

    Target U (0, 2)  ------- Neighbor X (1, 1) ------- Target V (2, 0)

In this structural coordinate system:

  • The target node $u$ itself is labeled $(0, d(u,v))$.
  • The target node $v$ itself is labeled $(d(v,u), 0)$.
  • A mutual immediate neighbor is labeled $(1, 1)$.

As Komal K. Teru et al. show in Inductive Relation Prediction by Subgraph Reasoning, this simple labeling mechanism completely changes how the GNN processes the graph. Instead of learning static node identities, the GNN learns to recognize structural configurations. The message-passing layers now track how information flows relative to the target pair, allowing the model to explicitly identify the target nodes and capture the exact topology of the enclosing subgraph.

Why Distance Labeling Enables Inductive Generalization

Traditional graph algorithms rely heavily on transductive node embeddings (like Node2Vec or matrix factorization), which assign a unique vector to every specific node ID. These models fail completely in inductive settings—such as when a model trained on a social network of one company must immediately predict links in a completely different company's network.

Distance labeling bypasses node identities entirely. Because the labels are purely topological integers representing relative distances, they serve as a universal structural language.

This property enables powerful zero-shot and in-context learning capabilities across completely disparate graphs:

Theoretical Expressivity and the Power of Paths

The intuition behind why this works is deeply tied to graph theory. By injecting distance labels, we condition the message-passing process on the query, transforming a standard GNN into a more expressive variant.

In A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs, Xingyue Huang et al. mathematically prove that conditioning message passing on a source node allows the network to compute pairwise representations that match the expressive power of the Relational Weisfeiler-Leman test.

Furthermore, integrating these distance metrics directly into path sequences allows models to overcome classic 1-WL failures. Caterina Graziani et al. demonstrate in The Expressive Power of Path-Based Graph Neural Networks that path-based architectures utilizing shortest-path distance labels can successfully count cycles and perfectly distinguish highly symmetrical structures (such as circular skip links) that leave standard message-passing models entirely confused.

Variations: Rooted Subgraphs and Global Anchors

While distance labeling originally flourished in pairwise link prediction, the core mechanism has been adapted to several other graph learning paradigms:

Rooted Subgraphs

Instead of calculating distances to a pair of nodes, models can calculate distances to a single "root" node to learn better local context. Muhan Zhang et al. introduce this in Nested Graph Neural Networks, augmenting node features with their geodesic distance to a central root node to capture the functional roles of nodes within local motifs. This concept is extended to attention mechanisms by Guy Bar-Shalom et al. in Subgraphormer: Subgraph GNNs meet Graph Transformers, using root-distance marking to provide structural context to transformer layers.

Global Anchors

Instead of restricting distances to a local subgraph, distances can be calculated relative to global reference points. Jianxin Li et al. apply this in Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing, utilizing labeled nodes as global anchors. This creates a spatial map that prevents supervision signals from being "squashed" or lost over long topological distances.

Broad Applications

Because relative distance labeling exposes the underlying structural roles of nodes, it has become a vital tool across diverse domains:

  • Explainability: Wanyu Lin et al. utilize relative distance labeling in Generative Causal Explanations for Graph Neural Networks to preserve spatial context when identifying the most causal subgraphs behind a GNN's predictions.
  • Hardware Security: In netlist analysis, attacks like MuxLink and UNTANGLE successfully break advanced circuit obfuscation defenses by extracting h-hop subgraphs and applying distance-based node labeling to identify the exact structural roles of hidden logic gates.

Key Foundational Work

Link Prediction Based on Graph Neural Networks (2018) — contributed 2 concept elements to this direction.
A Multi-Scale Approach for Graph Link Prediction (2020) — contributed 1 concept elements to this direction.
Inductive Relation Prediction by Subgraph Reasoning (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_distance_based_node_labeling_c255fd1e,
  title = {distance-based node labeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distance-based-node-labeling/rdr_c255fd1ee5514f8ead4700d5822e5229},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_distance_based_node_labeling_c255fd1e_v1,
  title = {distance-based node labeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distance-based-node-labeling/rdr_c255fd1ee5514f8ead4700d5822e5229/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake