Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction
Link prediction is one important application of graph neural networks (GNNs).
Most existing GNNs for link prediction are based on one-dimensional
Weisfeiler-Lehman (1-WL) test. 1-WL-GNNs first compute node representations by
iteratively passing neighboring node features to the center, and then obtain
link representations by aggregating the pairwise node representations. As
pointed out by previous works, this two-step procedure results in low
discriminating power, as 1-WL-GNNs by nature learn node-level representations
instead of link-level. In this paper, we study a completely different approach
which can directly obtain node pair (link) representations based on
\textit{two-dimensional Weisfeiler-Lehman (2-WL) tests}. 2-WL tests directly
use links (2-tuples) as message passing units instead of nodes, and thus can
directly obtain link representations. We theoretically analyze the expressive
power of 2-WL tests to discriminate non-isomorphic links, and prove their
superior link discriminating power than 1-WL. Based on different 2-WL variants,
we propose a series of novel 2-WL-GNN models for link prediction. Experiments
on a wide range of real-world datasets demonstrate their competitive
performance to state-of-the-art baselines and superiority over plain 1-WL-GNNs.