Bridging Theory and Practice in Link Representation with Graph Neural Networks

Andrea Passerini (University of Trento) · Bruno Lepri (Fondazione Bruno Kessler) · Veronica Lachi (University of Siena) · Francesco Ferrini (University of Trento, Via Calepina 14, 38122, Trento VAT: IT00340520220) · Antonio Longa (University of Trento) · Manfred Jaeger (Aalborg University)

$k_\phi$-$k_\rho$-$m$ frameworkdataset-aware model selectionexpressive powerexpressiveness comparisonsgraph neural networksgraph symmetry metricgraph-level representationshierarchy of methodslink predictionlink representationlink-level expressivenessmessage-passing modelsmodel performancesynthetic evaluation protocoltheoretical tools

Graph Neural Networks (GNNs) are widely used to compute representations of node pairs for downstream tasks such as link prediction. Yet, theoretical understanding of their expressive power has focused almost entirely on graph-level representations. In this work, we shift the focus to links and provide the first comprehensive study of GNN expressiveness in link representation. We introduce a unifying framework, the $k_\phi$-$k_\rho$-$m$ framework, that subsumes existing message-passing link models and enables formal expressiveness comparisons. Using this framework, we derive a hierarchy of state-of-the-art methods and offer theoretical tools to analyze future architectures. To complement our analysis, we propose a synthetic evaluation protocol comprising the first benchmark specifically designed to assess link-level expressiveness. Finally, we ask: does expressiveness matter in practice? We use a graph symmetry metric that quantifies the difficulty of distinguishing links and show that while expressive models may underperform on standard benchmarks, they significantly outperform simpler ones as symmetry increases, highlighting the need for dataset-aware model selection.