Bridging Theory and Practice in Link Representation with Graph Neural Networks
This work addresses a gap in theory for link-level tasks in graph learning, offering tools for model analysis and dataset-aware selection, though it is incremental in extending existing GNN expressiveness studies.
The authors tackled the lack of theoretical understanding of Graph Neural Networks (GNNs) for link representation, introducing a framework to analyze expressiveness and showing that expressive models outperform simpler ones by up to significant margins as graph symmetry increases.
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.