Introduction
Standard Graph Neural Networks (GNNs) are highly effective at classifying individual nodes or entire graphs. However, they surprisingly struggle with "multi-node" tasks, such as predicting whether a link exists between two specific nodes. This paper introduces the Labeling Trick—a theoretical framework proving that by simply labeling nodes relative to a target set before running a GNN, we can empower these models to learn the most expressive structural representations possible for any set of nodes.
The Problem: The Independence Trap
The common approach for multi-node tasks, such as in Graph AutoEncoders (GAEs), is to compute a representation for node A and node B independently and then combine them. The authors point out a fundamental flaw in this approach: if two nodes are structurally symmetric (isomorphic) within the graph, a standard GNN will give them identical representations.
Consequently, the GNN cannot distinguish between a potential link $(v_1, v_2)$ and $(v_1, v_3)$ if $v_2$ and $v_3$ "look" the same to the network, even if their relationship to $v_1$ is completely different (e.g., one might be a close neighbor while the other is distant). To fix this, researchers previously used node IDs or random features, but these methods break the "inductive" nature of GNNs—they cannot generalize to new, unseen graphs. The core challenge is making GNNs "aware" of the target node set while maintaining their ability to generalize.
The Solution: The Labeling Trick
To overcome the independence trap, the authors propose and formalize the Labeling Trick. Before passing a graph through a GNN, you assign labels to nodes based on their relationship to the target set $S$ (the nodes you want to represent).
Labeling nodes essentially "conditions" the GNN's message-passing on the target set, changing the view of the graph from the perspective of the queried nodes. A valid Labeling Trick must satisfy two key properties:
- Target-nodes-distinguishing: The labels must allow the GNN to identify which nodes belong to the target set $S$.
- Permutation Equivariance: If you reorder the nodes in the graph, the labels must change consistently. This ensures the model remains structural and inductive, relying on relative structural information (like distance to the target) rather than absolute positional identity.
Unifying Previous Methods
This theory unifies several successful but previously disconnected methods:
- SEAL: Uses "Double Radius Node Labeling" (DRNL) based on distances to the two target nodes.
- Distance Encoding (DE): Uses shortest-path distances to the target set.
- ID-GNN: Uses a form of "identity" coloring.
The authors prove Theorem 1: A sufficiently powerful GNN equipped with a valid labeling trick can learn the "most expressive structural representation." It can distinguish between any two node sets that are not structurally identical, effectively solving the multi-node representation problem.
Key Results
The theory was validated using the Open Graph Benchmark (OGB) on four large-scale link prediction datasets (up to 30M edges): ogbl-ppa, ogbl-collab, ogbl-ddi, and ogbl-citation2.
- Massive Performance Gains: On the
ogbl-ppadataset (a protein-protein interaction network), the labeling-based method (SEAL) outperformed standard GAEs by 87% to 195%. - Beating Heuristics: Standard GNNs often perform worse than simple classical heuristics like "Common Neighbors." With the labeling trick, GNNs consistently beat these heuristics by learning to "count" neighbors and capture higher-order paths.
- State-of-the-Art: Methods using the labeling trick achieved top results on 3 out of 4 OGB datasets at the time of publication.
- The Density Exception: On
ogbl-ddi(a very dense drug-drug interaction graph), standard GAEs with trainable embeddings actually performed better. In extremely dense graphs, inductive structural patterns are harder to learn than simple transductive embeddings.
Limitations and Future Work
While powerful, the labeling trick has limitations. Computational complexity is a primary concern, as it requires relabeling the graph (or extracting $h$-hop subgraphs) for every single pair of nodes you want to predict, which is much slower than computing all node representations once. Additionally, its effectiveness may diminish in very dense graphs where structural differentiation is minimal. Future work may explore the theoretical limits of "partial" labeling tricks (like ID-GNN) versus full labeling to balance expressiveness and computational cost.
Summary updated