mlsanityData to 7 Oct 2026

Towards characterizing the value of edge embeddings in Graph Neural Networks

arXiv 2410.09867 ↗First posted 13 Oct 2024cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are the dominant approach to solving machine learning problems defined over graphs. Despite much theoretical and empirical work in recent years, our understanding of finer-grained aspects of architectural design for GNNs remains impoverished. In this paper, we consider the benefits of architectures that maintain and update edge embeddings. On the theoretical front, under a suitable computational abstraction for a layer in the model, as well as memory constraints on the embeddings, we show that there are natural tasks on graphical models for which architectures leveraging edge embeddings can be much shallower. Our techniques are inspired by results on time-space tradeoffs in theoretical computer science. Empirically, we show architectures that maintain edge embeddings almost always improve on their node-based counterparts -- frequently significantly so in topologies that have ``hub'' nodes.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 15 of its 32 references that are in the map. First posted on arXiv 13 Oct 2024.

Builds on

15 of 32 references.

References · 15

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2020Benchmarking Graph Neural Networkscited by 672
  5. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  6. 2019Provably Powerful Graph Networkscited by 385
  7. 2016Benefits of depth in neural networkscited by 248
  8. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  9. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  10. 2023Representational Strengths and Limitations of Transformerscited by 132
  11. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  12. 2020Line Graph Neural Networks for Link Predictioncited by 89
3 more
  1. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  2. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  3. 2023Line Graph Neural Networks for Link Weight Predictioncited by 7

Built on by

Not cited yet.