Revisiting Graph Neural Networks for Link Prediction

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

TL;DR

This paper introduces the "labeling trick" as a theoretical framework for improving Graph Neural Networks (GNNs) in multi-node representation learning tasks like link prediction. By strategically labeling nodes within a graph, GNNs can overcome limitations of simply aggregating node embeddings and learn more expressive representations, achieving state-of-the-art results on several benchmark datasets.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are excellent at learning representations for individual nodes or entire graphs. However, applying them to tasks involving multiple nodes, such as predicting links between nodes (link prediction), has been less understood. A common approach, exemplified by Graph Autoencoders (GAEs), is to learn individual node representations and then combine them. The paper argues that this simple aggregation fails to capture crucial dependencies between nodes in a set, leading to suboptimal performance. This is particularly problematic for tasks like link prediction where understanding the relationship between the two nodes is paramount. The paper aims to bridge this gap by providing a theoretical foundation for how GNNs can effectively learn representations for sets of nodes.

Methods

The core contribution of this paper is the "labeling trick" framework. This trick involves augmenting the input graph with additional node labels before feeding it to a GNN. These labels are designed to be:

  1. Target-nodes-distinguishing: Labels clearly differentiate the nodes involved in the target set (e.g., the two nodes of a link) from other nodes.
  2. Permutation equivariant: The labeling scheme remains consistent under graph permutations, ensuring that isomorphic structures are treated similarly.

The paper proves that when a GNN is equipped with a labeling trick and is sufficiently expressive (a "node-most-expressive GNN"), it can learn structural representations for node sets. This means that isomorphic node sets will receive identical representations, and non-isomorphic sets will receive distinct ones. The paper also shows that existing successful methods like SEAL inherently employ a form of this labeling trick.

Datasets

The paper evaluates its proposed theory and methods on four link existence prediction datasets from the Open Graph Benchmark (OGB):

  • ogbl-ppa (protein-protein association)
  • ogbl-collab (author collaboration)
  • ogbl-ddi (drug-drug interaction)
  • ogbl-citation2 (paper citation)

These datasets are noted for being large-scale, having realistic train/validation/test splits, and using standard evaluation metrics.

Key Insights and Ideas

  • Simple aggregation is insufficient: Directly aggregating individual node representations learned by a GNN does not capture the complex dependencies within a set of nodes, hindering performance on multi-node tasks like link prediction.
  • The "Labeling Trick" is key: By strategically labeling nodes (especially the target nodes), GNNs can be made aware of the relationships between nodes in a set, enabling them to learn more expressive representations.
  • Structural representations are achievable: With a labeling trick and a powerful enough GNN, it's possible to learn representations that are truly "structural," meaning they perfectly distinguish isomorphic node sets from non-isomorphic ones.
  • SEAL's success explained: The paper provides a theoretical explanation for why methods like SEAL, which use node labeling on subgraphs, outperform simpler GAE approaches.
  • Inductive learning preserved: Unlike methods that use node-discriminating features which can harm generalization, the labeling trick preserves the inductive learning capabilities of GNNs.

Key Results

  • The proposed "labeling trick" framework, when combined with a node-most-expressive GNN, theoretically enables learning structural representations for node sets.
  • Experiments on four OGB link prediction datasets demonstrate that methods employing labeling tricks (like SEAL) significantly outperform GAE methods that simply aggregate node embeddings.
  • SEAL achieved new state-of-the-art results on 3 out of 4 OGB datasets, showing performance gains of up to 195% over GAE methods on the challenging ogbl-ppa dataset.
  • Ablation studies showed that even a simple "zero-one labeling trick" can significantly improve performance, though more sophisticated labeling schemes like DRNL and DE offer further benefits.

Limitations and Future Work

  • GNN expressiveness: While the theory holds for "node-most-expressive" GNNs, practical GNNs have limitations. The paper shows that using more expressive GNNs (like GIN) with simple labeling tricks can yield better results, suggesting that GNN architecture plays a role.
  • Dense graphs: Labeling trick methods did not perform as well on the very dense ogbl-ddi dataset. The authors suggest this might be due to the difficulty of learning inductive structural patterns in such graphs and that transductive methods might be more suitable.
  • Computational complexity: Labeling tricks can introduce extra computational complexity as graphs need to be relabeled for each prediction. However, this cost can be comparable to GAEs in mini-batch settings.
  • Future work: The authors suggest exploring partial labeling tricks, investigating the effectiveness of labeling tricks on dense graphs, and further studying the impact of subgraph-level readouts and the number of message-passing layers relative to subgraph hops.

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{zhang2021revisiting,
  author = {Muhan Zhang and Pan Li and Yinglong Xia and Kai Wang and Long Jin},
  title = {{Revisiting Graph Neural Networks for Link Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Hcr9mgBG6ds},
}
Figure