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

arXiv: https://arxiv.org/abs/2010.16103 · HTML: https://mlsanity.com/paper/2010.16103/

## Key facts

- Cited by 149 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2020.

## Built on by (most cited first, 30 of 149)

- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [One for All: Towards Training One Graph Model for All Classification Tasks](https://mlsanity.com/paper/2310.00149/) (2023)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders](https://mlsanity.com/paper/2205.10053/) (2022)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [GOFA: A Generative One-For-All Model for Joint Graph Language Modeling](https://mlsanity.com/paper/2407.09709/) (2024)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [Neighborhood-aware Scalable Temporal Network Representation Learning](https://mlsanity.com/paper/2209.01084/) (2022)
- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights](https://mlsanity.com/paper/2406.10727/) (2024)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [Fully-inductive Node Classification on Arbitrary Graphs](https://mlsanity.com/paper/2405.20445/) (2024)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs](https://mlsanity.com/paper/2302.02209/) (2023)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization](https://mlsanity.com/paper/2210.00102/) (2022)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [Inductive Logical Query Answering in Knowledge Graphs](https://mlsanity.com/paper/2210.08008/) (2022)

## Abstract (arXiv)

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.