Bridging Theory and Practice in Link Representation with Graph Neural Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912458177773568 |
|---|---|
| author | Lachi, Veronica Ferrini, Francesco Longa, Antonio Lepri, Bruno Passerini, Andrea Jaeger, Manfred |
| author_facet | Lachi, Veronica Ferrini, Francesco Longa, Antonio Lepri, Bruno Passerini, Andrea Jaeger, Manfred |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_24018 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bridging Theory and Practice in Link Representation with Graph Neural Networks Lachi, Veronica Ferrini, Francesco Longa, Antonio Lepri, Bruno Passerini, Andrea Jaeger, Manfred Machine Learning Artificial Intelligence 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. |
| title | Bridging Theory and Practice in Link Representation with Graph Neural Networks |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2506.24018 |