Graph neural networks improve link prediction by addressing node role confusion
Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction
Machine LearningComputer Science and Game Theory
Summary
Graph neural networks (GNNs) try to learn patterns in networks by looking at how nodes connect. But when different nodes have the same structural role, standard GNNs treat them as identical, which hurts their ability to predict links. The authors introduce a way to measure how well GNNs can tell these links apart using a new metric called edge automorphism ratio (EAR). They then build a new GNN design called EO-GNN that avoids confusing node roles, helping it predict links more accurately on both made-up and real networks.
What this means in practice
- •For data scientists: Enhance link prediction in network analysis by using EO-GNN to better distinguish structural node roles and improve accuracy in complex graphs.
- •For social network engineers: Improve friend or connection recommendations by deploying GNNs that better differentiate network roles, leading to more precise linking suggestions.
Authors
Chen Shao, Donald Loveland, Tobias Käfer, Danai Koutra
Abstract
Graph Neural Networks (GNNs) are effective for learning node and link embeddings through permutation-equivariant aggregation. However, standard GNNs collapse automorphic nodes, i.e., those with identical structural roles (or orbits) into indistinguishable representations, leading to the node automorphism problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterize GNN expressiveness rely primarily on Weisfeiler-Lehman (WL) analyses, but these methods are typically qualitative and often misaligned with empirical results. To address this gap, we begin by introducing a novel quantitative framework to assess GNN expressiveness for link prediction. We first formalize edge-level automorphism through edge orbits, which capture the set of structural role pairs for nodes that share a link. Then, we introduce the edge automorphism ratio (EAR), a scalar metric that quantifies a GNN's ability to distinguish links in a given graph. We empirically demonstrate that EAR correlates strongly with performance, validating its practical benefit. Building on this insight, we design EDGE-ORBIT EQUIVARIANT GRAPH NEURAL NETWORK (EO-GNN), a GNN architecture that addresses automorphism collapse while preserving equivariance and incurring minimal computational overhead. EO-GNN accomplishes this through two core designs combined with WL-based node hashes: (i) automorphism-aware dropouts and (ii) subgraph orbit-biased aggregation. Empirical evaluations on synthetic and real graphs show improvements of up to 42.36% and 28.44%, respectively, in predicting links in scenarios with high automorphism.