Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.09867 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917801891987456 |
|---|---|
| author | Rohatgi, Dhruv Marwah, Tanya Lipton, Zachary Chase Lu, Jianfeng Moitra, Ankur Risteski, Andrej |
| author_facet | Rohatgi, Dhruv Marwah, Tanya Lipton, Zachary Chase Lu, Jianfeng Moitra, Ankur Risteski, Andrej |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09867 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards characterizing the value of edge embeddings in Graph Neural Networks Rohatgi, Dhruv Marwah, Tanya Lipton, Zachary Chase Lu, Jianfeng Moitra, Ankur Risteski, Andrej Machine Learning 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. |
| title | Towards characterizing the value of edge embeddings in Graph Neural Networks |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.09867 |