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 的性能。

利用标签技巧在多节点任务中提高图神经网络的性能

Improving Graph Neural Networks on Multi-node Tasks with Labeling Tricks

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.

该论文介绍了使用图神经网络（GNN）进行多节点表示学习的理论，指出之前的方法不能有效地捕捉节点集中节点之间的依赖关系，探究了节点标注技巧，证明其是解决节点集合联合学习任务的最通用方法。