Standard Graph Neural Networks (GNNs) often struggle with a fundamental paradox: they are designed to be permutation-invariant, yet link prediction is an inherently "position-aware" task. To predict if a connection exists between node $u$ and node $v$, a model must distinguish these two target nodes from the rest of the graph.
Historically, researchers solved this by learning unique "identity embeddings" for every node. However, this approach fails in inductive settings—where the model encounters entirely new nodes at test time—because it cannot learn an embedding for an identity it has never seen. A growing body of research, exemplified by GraIL and UniLP, has shifted the focus from who a node is to where a node is relative to the potential link.
The Structural Coordinate System
The core mechanism behind this shift is Relative Distance Labeling. Instead of using global IDs, models extract a local subgraph (often an $h$-hop "enclosing subgraph") around the target pair $(u, v)$. Every node $i$ in this subgraph is then assigned a label based on its shortest-path distance to $u$ and $v$.
As Komal K. Teru, Etienne G. Denis, and William L. Hamilton demonstrate in GraIL, this creates a "structural coordinate system." For example, node $u$ might be labeled $(0, 2)$ and node $v$ labeled $(2, 0)$, while a common neighbor might be $(1, 1)$.
This labeling serves two critical purposes:
- Symmetry Breaking: It allows a GNN to distinguish the target nodes from auxiliary neighbors, even if they have identical features.
- Inductive Generalization: Because the labels depend only on local topology, a model trained on one graph can immediately reason about a completely different graph, as seen in the "zero-shot" capabilities of UniLP by Kaiwen Dong and colleagues.
Why Distance Labeling Works
The intuition for why this works lies in the expressive power of the GNN. Standard message-passing is limited by the Weisfeiler-Leman (WL) test, which cannot distinguish certain symmetrical structures. By "conditioning" the message passing on the distance to the source node—a concept formalized by Xingyue Huang and Ismail Ilkan Ceylan as Conditional Message Passing (C-MPNNs)—the model gains the ability to compute pairwise representations that are much more expressive than simple node-level aggregations.
In A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs, the authors prove that designating a query entity as a fixed reference point allows the GNN to capture complex path-based logical rules. This is why models like RED-GNN by Yongqi Zhang and quanming yao can outperform traditional embedding methods: they aren't just memorizing facts; they are learning the "shape" of logical relationships.
Generalizing Across Domains
This structural approach has proven remarkably robust across diverse applications:
- Recommendation Systems: In LGCF and ADAPT, Yiqi Wang and Chaozhuo Li show that structural labeling allows models to transfer knowledge between different user-item graphs, even when there are no shared users or items.
- Hardware Security: Lilas Alrahis uses distance-based labeling in MuxLink to identify hidden connections in logic-locked circuits, proving that structural roles are consistent even in highly engineered topologies.
- Higher-Order Patterns: Pan Li 0005 extends this to temporal networks in HIT, using asymmetric distance encoding to predict not just pairs, but complex motifs of three or more nodes.
Overcoming the Efficiency Wall
The primary drawback of labeling-based methods is computational cost. Extracting a unique subgraph and re-labeling nodes for every single potential link is expensive.
To solve this, researchers like Lecheng Kong and Yixin Chen introduced GDGNN, which uses geodesics (shortest paths) as a coordinate system without explicit subgraph extraction. Similarly, ESC-GNN by Zuoyu Yan precomputes structural embeddings based on node distances, achieving the substructure-counting power of subgraph GNNs at the speed of standard message passing.
By replacing rigid node identities with fluid structural roles, this research direction has transformed link prediction from a task of "lookup and retrieval" into one of "geometric reasoning."