Pure Message Passing Can Estimate Common Neighbor for Link Prediction
This addresses a fundamental limitation in graph representation learning for link prediction, offering a novel method to improve MPNNs' performance, though it appears incremental as it builds on existing MPNN frameworks.
The paper tackles the problem of Message Passing Neural Networks (MPNNs) struggling with link prediction compared to simple heuristics like Common Neighbor (CN), and introduces the Message Passing Link Predictor (MPLP) that uses quasi-orthogonal vectors to estimate link-level structural features, consistently outperforming baseline methods on benchmark datasets.
Message Passing Neural Networks (MPNNs) have emerged as the {\em de facto} standard in graph representation learning. However, when it comes to link prediction, they often struggle, surpassed by simple heuristics such as Common Neighbor (CN). This discrepancy stems from a fundamental limitation: while MPNNs excel in node-level representation, they stumble with encoding the joint structural features essential to link prediction, like CN. To bridge this gap, we posit that, by harnessing the orthogonality of input vectors, pure message-passing can indeed capture joint structural features. Specifically, we study the proficiency of MPNNs in approximating CN heuristics. Based on our findings, we introduce the Message Passing Link Predictor (MPLP), a novel link prediction model. MPLP taps into quasi-orthogonal vectors to estimate link-level structural features, all while preserving the node-level complexities. Moreover, our approach demonstrates that leveraging message-passing to capture structural features could offset MPNNs' expressiveness limitations at the expense of estimation variance. We conduct experiments on benchmark datasets from various domains, where our method consistently outperforms the baseline methods.