In this paper, we provide a theory of using graph neural networks (GNNs) for
\textit{multi-node representation learning}, where we are interested in
learning a representation for a set of more than one node such as a link.
Existing GNNs are mainly 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. In this paper, we show a fundamental
limitation of such an approach, namely the inability to capture the dependence
among multiple nodes in a node set, and argue that directly aggregating
individual node representations fails to produce an effective joint
representation for multiple nodes. A straightforward solution is to distinguish
target nodes from others. Formalizing this idea, we propose \text{labeling
trick}, which first labels nodes in the graph according to their relationships
with the target node set before applying a GNN and then aggregates node
representations obtained in the labeled graph for multi-node representations.
The labeling trick also unifies a few previous successful works for multi-node
representation learning, including SEAL, Distance Encoding, ID-GNN, and NBFNet.
Besides node sets in graphs, we also extend labeling tricks to posets, subsets
and hypergraphs. Experiments verify that the labeling trick technique can boost
GNNs on various tasks, including undirected link prediction, directed link
prediction, hyperedge prediction, and subgraph prediction. Our work explains
the superior performance of previous node-labeling-based methods and
establishes a theoretical foundation for using GNNs for multi-node
representation learning.

本文提出了使用图神经网络（GNN）进行多节点表示学习的理论，介绍和证明了直接聚合单个节点表示无法捕捉节点集中节点间依赖性的弊端，提出了一种区分目标节点和其他节点的标记技巧（Labeling trick）以及将其扩展应用到偏序集、子集和超图中，通过实验证明了该技术可在无向 / 有向链接预测、超边预测、子图预测等多个任务中提升 GNN 的性能。