2025/06/30 by Veronica Lachi, Francesco Ferrini, Lachi, Veronica +9 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Complex Network Analysis Techniques #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2506.24018
openalex publication_date 2025/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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ϕ-kρ-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.