Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node\n Representation Learning

Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, Long Jin

Graph Neural Networks (GNNs) have become the gold standard for learning from structured data. They excel at classifying individual nodes or entire graphs. However, there is a "middle ground" where they often stumble: multi-node representation learning. This is the foundation of link prediction—predicting whether a relationship exists between two specific nodes.

In their NeurIPS 2021 paper, Muhan Zhang and colleagues introduce a formal theory for the "Labeling Trick," a simple yet powerful technique that allows GNNs to capture the complex dependencies required for multi-node tasks.

TL;DR

Standard GNNs fail at link prediction because they learn node representations independently, making them "blind" to the relationship between specific pairs. The "Labeling Trick" fixes this by tagging target nodes before running the GNN, providing a theoretical guarantee that the model can learn the most expressive structural representations possible for sets of nodes.

What Problem Does This Paper Address?

Most GNNs are designed to learn a representation for a single node by aggregating information from its neighbors. To predict a link between node $A$ and node $B$, the standard approach (like Graph Autoencoders or GAEs) is to compute embeddings for $A$ and $B$ separately and then combine them (e.g., via a dot product).

The authors point out a fundamental flaw: Independence. If two nodes have identical local neighborhoods, a standard GNN will give them the exact same embedding. However, their relationship to a third node might be completely different.

Imagine a perfectly symmetrical social network. If you and your twin have the exact same friends, a standard GNN can't tell the difference between "your relationship with a new person" and "your twin's relationship with that same person." To predict a link, the GNN needs to be aware of the specific pair it is investigating during the message-passing process, not just at the very end.

Methods: The Labeling Trick

The authors unify several successful but disparate methods (like SEAL, Distance Encoding, and ID-GNN) into a single framework called the Labeling Trick.

How it works:

  1. Identify the Target Set: Suppose you want to predict a link between nodes $u$ and $v$.
  2. Label the Nodes: Before running the GNN, assign labels to all nodes in the graph based on their relationship to $u$ and $v$.
  3. The simplest version is the Zero-One Labeling Trick: give $u$ and $v$ a label of "1" and all other nodes a "0".
  4. More advanced versions, like Double Radius Node Labeling (DRNL) used in SEAL, label nodes based on their shortest-path distances to the target pair.
  5. Run the GNN: The GNN now treats these labels as additional node features.
  6. Aggregate: Finally, aggregate the representations of the target nodes to make a prediction.

Why it’s novel:

While researchers had used node labeling before, this paper provides the first rigorous theory proving why it works. They prove that with a valid labeling trick, a sufficiently powerful GNN can distinguish between any two sets of nodes that are not structurally identical (isomorphic). This effectively "solves" the joint learning problem that standard GAEs cannot handle.

Datasets

The authors evaluated their theory using the Open Graph Benchmark (OGB), which provides massive, real-world datasets for link prediction:

  • ogbl-ppa: A protein-protein association graph (576k nodes).
  • ogbl-collab: An author collaboration network (235k nodes).
  • ogbl-ddi: A drug-drug interaction network (4k nodes, but very dense).
  • ogbl-citation2: A paper citation network (2.9M nodes).

Key Insights and Ideas

  • Multi-node tasks are "unbreakable": You cannot decompose a link prediction task into two independent node-representation tasks. The representation of node $A$ must be conditioned on the existence of node $B$.
  • Structural vs. Positional: The labeling trick allows GNNs to learn structural representations (how nodes relate to each other) rather than just positional embeddings (where nodes are in the graph). This makes the models more "inductive"—they can generalize to entirely new graphs they haven't seen before.
  • The Power of 1-WL: Even standard GNNs (which are limited by the 1-Weisfeiler-Lehman test) become significantly more powerful when combined with the labeling trick. The authors prove that labeling allows 1-WL GNNs to distinguish links that are otherwise indistinguishable.
  • Local Isomorphism: In practice, we don't need the whole graph. Extracting a small "enclosing subgraph" around the target nodes and applying the labeling trick there is often enough to achieve state-of-the-art results.

Key Results

The experiments confirmed the theory with dramatic performance jumps:

  • Massive Gains: On the ogbl-ppa dataset, the SEAL method (which uses the labeling trick) outperformed plain GAE methods by 87% to 195%.
  • Beating Heuristics: Plain GNNs often perform worse than simple heuristics like "Common Neighbors." However, once the labeling trick is added, GNNs consistently beat these heuristics, proving they have finally learned the underlying structural patterns.
  • State of the Art: Labeling-based methods achieved new SOTA results on 3 out of 4 OGB datasets at the time of publication.

Limitations and Future Work

  • Computational Complexity: The labeling trick requires relabeling the graph (or subgraphs) for every single link you want to predict. This is much slower than computing node embeddings once and reusing them.
  • Dense Graphs: On the ogbl-ddi dataset, labeling tricks actually performed worse than standard methods. The authors suspect that in extremely dense graphs, structural patterns are harder to learn inductively, and simple "memorization" (transductive learning) might work better.
  • Scaling: Finding ways to implement the labeling trick more efficiently on massive graphs remains an open challenge. The authors suggest "partial labeling" (only labeling the source node) as a potential area for future research.

Summary updated

Abstract

In this paper, we provide a theory of using graph neural networks (GNNs) for\nmulti-node representation learning (where we are interested in learning a\nrepresentation for a set of more than one node, such as link). We know that GNN\nis designed to learn single-node representations. When we want to learn a node\nset representation involving multiple nodes, a common practice in previous\nworks is to directly aggregate the single-node representations obtained by a\nGNN into a joint node set representation. In this paper, we show a fundamental\nconstraint of such an approach, namely the inability to capture the dependence\nbetween nodes in the node set, and argue that directly aggregating individual\nnode representations does not lead to an effective joint representation for\nmultiple nodes. Then, we notice that a few previous successful works for\nmulti-node representation learning, including SEAL, Distance Encoding, and\nID-GNN, all used node labeling. These methods first label nodes in the graph\naccording to their relationships with the target node set before applying a\nGNN. Then, the node representations obtained in the labeled graph are\naggregated into a node set representation. By investigating their inner\nmechanisms, we unify these node labeling techniques into a single and most\ngeneral form -- labeling trick. We prove that with labeling trick a\nsufficiently expressive GNN learns the most expressive node set\nrepresentations, thus in principle solves any joint learning tasks over node\nsets. Experiments on one important two-node representation learning task, link\nprediction, verified our theory. Our work explains the superior performance of\nprevious node-labeling-based methods, and establishes a theoretical foundation\nof using GNNs for multi-node representation learning.\n
BibTeX
@inproceedings{zhang2021labeling,
  author = {Muhan Zhang and Pan Li and Yinglong Xia and Kai Wang and Long Jin},
  title = {{Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node\textbackslash\{\}n Representation Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Hcr9mgBG6ds},
}

Loading related content...

Figure