Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction
This addresses the low discriminating power in link prediction for graph analysis, offering a new paradigm that could benefit applications like social network analysis or recommendation systems, though it builds on existing WL tests.
The paper tackles the problem of link prediction in graph neural networks by proposing a novel approach based on two-dimensional Weisfeiler-Lehman (2-WL) tests, which directly compute link representations instead of node-level ones, leading to competitive performance on real-world datasets and proven superior link discriminating power over traditional 1-WL methods.
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.