Abstract
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 shortest paths. In fact, if a GNN minimizes this loss within an error of $\epsilon$, it implements the BF algorithm with an error of $O(\epsilon)$. Consequently, despite limited training data, these GNNs are guaranteed to extrapolate to arbitrary shortest-path problems, including instances of any size. Our empirical results support our theory by showing that NNs trained by gradient descent are able to minimize this loss and extrapolate in practice.
Introduction
Neural networks frequently fail to extrapolate—performing poorly on data outside the training distribution. In graph learning, this is often seen as a size generalization problem: GNNs trained on small graphs fail on large ones. While "neural algorithmic alignment"—designing architectures to mimic classical algorithms—is a popular heuristic, rigorous proof that a trained model will converge to a generalizable algorithm rather than memorizing training patterns has been lacking. This work bridges that gap by demonstrating that GNNs can provably learn the Bellman-Ford algorithm for shortest paths and extrapolate to graphs of arbitrary size.
Methods: Algorithmic Alignment and Sparsity
The researchers focus on the Bellman-Ford (BF) algorithm, which solves the shortest path problem via the dynamic programming update: $d_v^{(k)} = \min_{u \in \mathcal{N}(v)} \{d_u^{(k-1)} + w_{uv}\}$. To learn this, they employ two critical components:
- Min-Aggregation GNN (MinAgg GNN): The architecture uses a
minfunction for aggregation, aligning the network's structure with the BF update rule. - Sparsity Regularization: The authors prove that while many parameter settings can solve shortest paths on small graphs, only a sparse set implements the general BF algorithm. By adding an $L_1$ penalty, the optimizer is forced toward the algorithmic solution.
The theoretical core is a proof showing that a MinAgg GNN minimizing a sparsity-regularized loss on a small set of "certificate" graphs is guaranteed to implement the BF algorithm with an error proportional to the training loss.
Empirical Evaluation
The model was trained on a minimal set of tiny "certificate" graphs, including path graphs and specific instances designed to distinguish node and edge features. It was then tested on 200 OOD graphs with diverse topologies (cycles, complete graphs, Erdős-Rényi).
Key results include:
- Perfect Extrapolation: $L_1$-regularized models achieved a test loss of 0.006, compared to 0.288 for unregularized models.
- Size Invariance: Error remained constant as graph size increased from 100 to 1,000 nodes.
- Iterative Robustness: The model maintained accuracy when iterated more times than seen during training, confirming it learned the underlying iterative logic.
Conclusion
This work provides the first rigorous proof that non-linear neural models can be guaranteed to extrapolate OOD via algorithmic alignment and sparsity. While currently focused on shortest paths and the min aggregator, the framework suggests a path forward for other dynamic programming tasks and architectures like Transformers. Future work will explore broader classes of algorithms and "generalization certificates."
Summary updated