Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node
  Representation Learning
  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.
