2023/09/02 by Kaiwen Dong, Dong, Kaiwen, Zhichun Guo +3 · 4 citations
Computer Science · Neuroscience · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Functional Brain Connectivity Studies #Information Retrieval (cs.IR) #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2309.00976
openalex publication_date 2023/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.