Can I read Graph Neural Networks Extrapolate Out-of-distribution for Shortest Paths on EtoBox?

Graph Neural Networks Extrapolate Out-of-distribution for Shortest Paths by Nerem, Robert R.; Chen, Samantha; Dasgupta, Sanjoy; Wang, Yusu is a scholarly article available to read on EtoBox.

What is Graph Neural Networks Extrapolate Out-of-distribution for Shortest Paths about?

Neural networks (NNs), despite their success and wide adoption, still struggle to extrapolate out-of-distribution (OOD), i.e., to inputs that are not well-represented by their training dataset. Addressing the OOD generalization gap is crucial when models are deployed in environments significantly different from the training set, such as applying Graph Neural Networks (GNNs) trained on small graphs to large, real-world graphs. One promising approach for achieving robust OOD generalization is the framework of neural algorithmic alignment, which incorporates ideas from classical algorithms by designing neural architectures that resemble specific algorithmic paradigms (e.g. dynamic programming). The hope is that trained models of this form would have superior OOD capabilities, in much the same way that classical algorithms work for all instances. We rigorously analyze the role of algorithmic alignment in achieving OOD generalization, focusing on graph neural networks (GNNs) applied to the canonical shortest path problem. We prove that GNNs, trained to minimize a sparsity-regularized loss over a small set of shortest path instances, exactly implement the Bellman-Ford (BF) algorithm for

Author

Nerem, Robert R.; Chen, Samantha; Dasgupta, Sanjoy; Wang, Yusu

Published

2025

Language

EN