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

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

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.

A symmetric graph illustrating how standard GNNs fail to distinguish structurally identical nodes.

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).

Applying the labeling trick to target node sets breaks structural symmetry, allowing the GNN to learn distinct joint representations.

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:

  1. Target-nodes-distinguishing: The labels must allow the GNN to identify which nodes belong to the target set $S$.
  2. 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-ppa dataset (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

Abstract

In this paper, we provide a theory of using graph neural networks (GNNs) for multi-node representation learning (where we are interested in learning a representation for a set of more than one node, such as link). We know that GNN is designed to learn single-node representations. When we want to learn a node set representation involving multiple nodes, a common practice in previous works is to directly aggregate the single-node representations obtained by a GNN into a joint node set representation. In this paper, we show a fundamental constraint of such an approach, namely the inability to capture the dependence between nodes in the node set, and argue that directly aggregating individual node representations does not lead to an effective joint representation for multiple nodes. Then, we notice that a few previous successful works for multi-node representation learning, including SEAL, Distance Encoding, and ID-GNN, all used node labeling. These methods first label nodes in the graph according to their relationships with the target node set before applying a GNN. Then, the node representations obtained in the labeled graph are aggregated into a node set representation. By investigating their inner mechanisms, we unify these node labeling techniques into a single and most general form---labeling trick. We prove that with labeling trick a sufficiently expressive GNN learns the most expressive node set representations, thus in principle solves any joint learning tasks over node sets. Experiments on one important two-node representation learning task, link prediction, verified our theory. Our work explains the superior performance of previous node-labeling-based methods, and establishes a theoretical foundation of using GNNs for multi-node representation learning.
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 Representation Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Hcr9mgBG6ds},
}
Figure