Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911411797491712 |
|---|---|
| author | Qharabagh, Muhammad Fetrat de Luca, Artur Back Giapitzakis, George Fountoulakis, Kimon |
| author_facet | Qharabagh, Muhammad Fetrat de Luca, Artur Back Giapitzakis, George Fountoulakis, Kimon |
| contents | Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms under bounded-degree and finite-precision constraints. Our approach follows a two-step process. First, we train an ensemble of multi-layer perceptrons (MLPs) to execute the local instructions of a single node. Second, during inference, we use the trained MLP ensemble as the update function within a graph neural network (GNN). Leveraging Neural Tangent Kernel (NTK) theory, we show that local instructions can be learned from a small training set, enabling the complete graph algorithm to be executed during inference without error and with high probability. To illustrate the learning power of our setting, we establish a rigorous learnability result for the LOCAL model of distributed computation. We further demonstrate positive learnability results for widely studied algorithms such as message flooding, breadth-first and depth-first search, and Bellman-Ford. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_23207 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning to Execute Graph Algorithms Exactly with Graph Neural Networks Qharabagh, Muhammad Fetrat de Luca, Artur Back Giapitzakis, George Fountoulakis, Kimon Machine Learning Artificial Intelligence Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms under bounded-degree and finite-precision constraints. Our approach follows a two-step process. First, we train an ensemble of multi-layer perceptrons (MLPs) to execute the local instructions of a single node. Second, during inference, we use the trained MLP ensemble as the update function within a graph neural network (GNN). Leveraging Neural Tangent Kernel (NTK) theory, we show that local instructions can be learned from a small training set, enabling the complete graph algorithm to be executed during inference without error and with high probability. To illustrate the learning power of our setting, we establish a rigorous learnability result for the LOCAL model of distributed computation. We further demonstrate positive learnability results for widely studied algorithms such as message flooding, breadth-first and depth-first search, and Bellman-Ford. |
| title | Learning to Execute Graph Algorithms Exactly with Graph Neural Networks |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2601.23207 |