Research work · 2025

Bridging Theory and Practice in Link Representation with Graph Neural Networks

Veronica Lachi, Francesco Ferrini, Antonio Longa, Bruno Lepri, Andrea Passerini, Manfred Jaeger

neural information processing systems

Abstract

Graph Neural Networks (GNNs) are widely used to compute representations ofnode pairs for downstream tasks such as link prediction. Yet, theoretical understanding of their expressive power has focused almost entirely on graph-levelrepresentations. In this work, we shift the focus to links and provide the firstcomprehensive study of GNN expressiveness in link representation. We introducea unifying framework, the kϕ-kρ-m framework, that subsumes existing messagepassing link models and enables formal expressiveness comparisons. Using thisframework, we derive a hierarchy of state-of-the-art methods and offer theoreticaltools to analyze future architectures. To complement our analysis, we propose asynthetic evaluation protocol comprising the first benchmark specifically designedto assess link-level expressiveness. Finally, we ask: does expressiveness matterin practice? We use a graph symmetry metric that quantifies the difficulty ofdistinguishing links and show that while expressive models may underperformon standard benchmarks, they significantly outperform simpler ones as symmetryincreases, highlighting the need for dataset-aware model selection.

Read free full text

DOI: 10.52202/085713-4090