Learning to Execute Graph Algorithms Exactly with Graph Neural Networks

Muhammad Fetrat Qharabagh, Artur Back De Luca, George Giapitzakis, Kimon Fountoulakis
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:30992-31124, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-fetrat-qharabagh26a, title = {Learning to Execute Graph Algorithms Exactly with Graph Neural Networks}, author = {Fetrat Qharabagh, Muhammad and Back De Luca, Artur and Giapitzakis, George and Fountoulakis, Kimon}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {30992--31124}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/fetrat-qharabagh26a/fetrat-qharabagh26a.pdf}, url = {https://proceedings.mlr.press/v306/fetrat-qharabagh26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning to Execute Graph Algorithms Exactly with Graph Neural Networks %A Muhammad Fetrat Qharabagh %A Artur Back De Luca %A George Giapitzakis %A Kimon Fountoulakis %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-fetrat-qharabagh26a %I PMLR %P 30992--31124 %U https://proceedings.mlr.press/v306/fetrat-qharabagh26a.html %V 306 %X 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.
APA
Fetrat Qharabagh, M., Back De Luca, A., Giapitzakis, G. & Fountoulakis, K.. (2026). Learning to Execute Graph Algorithms Exactly with Graph Neural Networks. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:30992-31124 Available from https://proceedings.mlr.press/v306/fetrat-qharabagh26a.html.

Related Material