Source-linked AI summary
Neural Execution of Graph Algorithms
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, Charles Blundell
TL;DR
Many important real-world tasks use graph-structured inputs, while some problems remain intractable from the perspective of classical algorithms. The approach encodes current and previous latent features with neural networks and aggregation mechanisms, achieving strong generalisation and positive transfer between reachability and shortest-path tasks.
Problem
Many important real-world tasks can be formulated over graph-structured inputs, but some problems remain intractable from the perspective of classical algorithms.
Method
For each algorithm, an encoder network processes current input features and previous latent features, using learnable message-passing and aggregation components.
Results
The MPNN-max model exhibits superior generalisation on reachability and shortest-path predecessor prediction, while joint learning with reachability improves shortest-path performance.
Takeaways & Limitations
Positive transfer and distance supervision improve this algorithm-learning setup, which also applies to sequential algorithm execution.
Takeaways & Limitations
Performance assessment lacks an ideal single-number metric, and experiments exclude corner cases such as negative weight cycles.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) are a powerful representational tool for solving problems on graph-structured inputs. In almost all cases so far, however, they have been applied to directly recovering a final solution from raw inputs, without explicit guidance on how to structure their problem-solving. Here, instead, we focus on learning in the space of algorithms: we train several state-of-the-art GNN architectures to imitate individual steps of classical graph algorithms, parallel (breadth-first search, Bellman-Ford) as well as sequential (Prim's algorithm). As graph algorithms usually rely on making discrete decisions within neighbourhoods, we hypothesise that maximisation-based message passing neural networks are best-suited for such objectives, and validate this claim empirically. We also demonstrate how learning in the space of algorithms can yield new opportunities for positive transfer between tasks---showing how learning a shortest-path algorithm can be substantially improved when simultaneously learning a reachability algorithm.
1 INTRODUCTION
The paper proposes learning graph algorithms as sequences of supervised intermediate computations rather than directly predicting final solutions. It focuses on shared algorithmic subroutines, maximisation-based message passing, and transfer across graph tasks.
- Graph-structured tasks span navigation, web search, protein folding, and game-playing, while some problems remain intractable for classical algorithmic approaches.
- The approach supervises neural networks to imitate classical algorithms, including intermediate outputs, providing explicit guidance for solving graph-structured problems.
- Shortest-path computation and breadth-first search share the subroutine of enumerating edges adjacent to a node.
- A message-passing neural network with a maximisation aggregator is proposed for discrete neighbourhood decisions and evaluated on reachability, shortest paths, and minimum spanning trees.
- Simultaneously learning breadth-first search and Bellman-Ford yields clear performance benefits, while the setup also supports algorithmic transfer without explicitly denoting subroutines.
2 PROBLEM SETUP
The neural executor represents graph algorithms as repeated encode-process-decode steps over node and edge features. Algorithm-specific encoders and decoders surround a shared processor that performs message passing, predicts outputs, and controls termination.
- 2.1 GRAPH ALGORITHMS: Graphs G = (V, E) consist of nodes V and edges E, and serve both as algorithm inputs and as inputs to the graph neural network.
- 2.2 LEARNING TO EXECUTE GRAPH ALGORITHMS: At each sequence step, node and edge features are provided to the network, which produces node-level outputs that may be reused as inputs at the next step.
- 2.2 LEARNING TO EXECUTE GRAPH ALGORITHMS: The target algorithm A is supplied to a shared encode-process-decode executor that can learn one or more algorithms simultaneously.
- 2.2 LEARNING TO EXECUTE GRAPH ALGORITHMS: For each algorithm, an encoder combines current input features with previous latent features before the shared processor transforms the encoded inputs.
- 2.2 LEARNING TO EXECUTE GRAPH ALGORITHMS: Algorithm-specific decoders produce node outputs, while termination networks predict whether execution should continue and permit iterative reuse of outputs.
- 2.2 LEARNING TO EXECUTE GRAPH ALGORITHMS: The processor compares GAT and MPNN layers; MPNNs use neural networks to form vector messages and an elementwise aggregation operator such as maximisation, summation, or averaging.
3 EXPERIMENTAL SETUP
The experiments train neural executors to imitate parallel and sequential graph algorithms across varied graph structures and graph sizes. They compare message-passing architectures and supervision signals for reachability, shortest paths, and minimum spanning trees.
- Data splits: Training uses 20-node graphs, with testing on additional graphs of 20, 50, and 100 nodes for each category.Each category has 100 training and 5 validation graphs, plus 5 test graphs at each test size.
- Parallel algorithms: Breadth-first search predicts one-bit node reachability, whereas Bellman-Ford predicts scalar source distances and predecessor nodes for shortest-path reconstruction.Both algorithms begin from a randomly selected source node and update node-level state during execution.
- Parallel algorithms: The executor learns both parallel algorithms simultaneously by concatenating their relevant step inputs and supervising intermediate algorithm outputs.The Bellman-Ford update propagates minimum neighbor-based distances, while reachability propagates whenever any neighbor is reachable.
- Sequential algorithms: Prim’s algorithm tests sequential execution by repeatedly selecting the lightest edge connecting a new node to the partially constructed minimum spanning tree.Only the selected node’s state is modified at each step, creating a sequential analogue to the parallel execution setting.
- Neural architectures: Architectural comparisons include MPNNs with maximisation, mean, or summation aggregation, GAT variants with sharp attention, and an LSTM processing serialized edge lists.The models use separate losses for reachability, distances, predecessors, termination, and Prim’s next-node prediction; MPNN-max is motivated by neighborhood-level discrete decisions.
4 RESULTS AND DISCUSSION
MPNN-max consistently generalises best when executing parallel and sequential graph algorithms, including joint reachability and shortest-path learning and tests on graphs up to 75× larger. The results also show positive transfer from reachability supervision, benefits from intermediate distance supervision, and limitations in the available aggregate metrics.
- Parallel algorithm execution: MPNN-max achieves superior generalisation for reachability and shortest-path predecessor prediction, with its performance gap widening as test graphs grow.This advantage remains when comparing against hardened attention-based GAT-like models.
- Parallel algorithm execution: MPNN-max is the only model providing reasonable intermediate distance mean-squared error at the 100-node generalisation level.By contrast, MPNN-sum can produce exploding message magnitudes on larger graphs.
- Transfer and supervision: Jointly learning reachability improves shortest-path prediction, while supervising intermediate distance information further improves performance over supervising only final outputs.Training shortest paths without reachability causes a significant drop in MPNN-max predictive power.
- Transfer and supervision: Curriculum learning, which trains reachability first and then fine-tunes Bellman-Ford, performs worse than learning both algorithms simultaneously.The curriculum strategy is therefore excluded from further experiments.
- Evaluation: Last-step and mean-step metrics do not fully measure algorithmic faithfulness, motivating per-timestep evaluation and future work on a better single-number metric.Mean-step scores may be artificially improved by delaying termination.
- Evaluation: Per-timestep plots help detect executors that cheat by immediately predicting every node reachable, revealing a characteristic initially weak but steadily improving curve.These plots complement aggregate metrics for reachability and predecessor accuracy on 100-node graphs.
- Sequential algorithm execution: For Prim’s algorithm, MPNN-max strongly outperforms alternatives in generalisation, whereas directly predicting predecessors without sequential node selection generalises poorly.The non-sequential no-algo model performs worse than even the LSTM sequential baseline.
5 CONCLUSIONS
The paper presents neural graph algorithm execution as imitation of individual steps and intermediate outputs for parallel and sequential classical algorithms. It identifies maximisation-based message passing neural networks as highly suitable for these tasks.
- Neural graph algorithm execution trains networks to imitate individual steps and all intermediate outputs of classical graph algorithms.
- The evaluated algorithms span parallel reachability and shortest paths, plus sequential minimum spanning trees.
- Maximisation-based message passing neural networks are identified as a highly suitable architecture.
A SUMMARY OF ALGORITHM INPUTS AND SUPERVISION SIGNALS
Table 7 summarizes the inputs and supervision signals used for breadth-first search, Bellman-Ford, and Prim’s algorithm.
- Table 7 provides an overview of all inputs and supervision signals for breadth-first search, Bellman-Ford, and Prim.
B THEORETICAL INSIGHTS
The theoretical insight explains positive transfer between algorithms that share subroutines. Conditional mutual information formalizes why supplying one algorithm’s output can reduce uncertainty about another’s output.
- The analysis considers learning algorithm A from x with and without algorithm B’s output yB provided.
- Shared subroutines imply information preserved between the outputs of algorithms A and B given the same input.
- Because I(YA; YB|X) > 0, providing yB reduces uncertainty in yA from H(YA|X) to H(YA|YB, X).
C LARGER-SCALE STUDIES
Larger-scale experiments test BFS and Bellman-Ford models trained on 100-node graphs and evaluated on 1000-node graphs. MPNN-based models continue to outperform other models beyond the studied “programmer” regime.
- The experiments train BFS and Bellman-Ford executors on 100-node graphs and test them on 1000-node graphs.
- MPNN-based models continue to outperform other models in this larger-scale setting.
D PERFORMANCE PER GRAPH TYPE
The paper evaluates MPNN-max across graph categories and examines how graph structure affects predictive performance. Trees are easiest, while grids and community graphs pose greater challenges for different structural reasons.
- Task assumptions: The transfer setup assumes the auxiliary target yB is simple enough to learn independently and provide to the model.This is a stricter formulation of treating algorithm B as simpler than algorithm A.
- Performance by graph category: Performance is roughly evenly distributed across graph categories, with trees easiest and grids and community graphs hardest for MPNN-max.The results are reported for reachability and predecessor prediction on 100-node graphs after training on 20-node graphs.
- Performance by graph category: In trees, shortest-path-tree computation reduces to rooting the input tree at the source vertex.This simpler equivalent task may be readily learned by the model.
- Performance by graph category: Long decision trajectories make grids difficult because an early poor choice can compromise retrieval of the overall shortest path tree.The same issue applies to ladder graphs, although their product-of-paths structure limits trajectory complexity.
- Performance by graph category: Community graphs challenge generalization because increasing graph size can drastically change node-degree distributions and require aggregation over larger neighborhoods than seen during training.These graphs consist of four dense Erdős-Rényi components with within-component edge probability p = 0.7.
E EXPLAINING GNN PREDICTIONS
The paper explains neural execution by optimizing an adjacency mask around each node and identifying the most influential predecessor edge. Applying this recursively can reconstruct a source-to-node path and expose explanation errors.
- Explanation method: A GNNExplainer-like procedure asks which neighboring node influences a given node’s reachability prediction during neural execution.The analysis focuses on decisions made by the best-performing MPNN-max architecture.
- Explanation method: The method fixes model parameters, optimizes an adjacency mask initialized on edges incident to u, and feeds the masked adjacency A ⊙ σ(M) to the model.The mask is optimized for a trained model on 20-node graphs.
- Path reconstruction: The maximum-weight masked edge is selected as u’s predecessor, and recursively explaining predecessors should produce a path to the BFS source.A disconnection indicates either an incorrect model prediction or an incorrect explanation.
- Path reconstruction: Figure 4 visualizes identified reachability paths with purple predecessor edges and yellow remaining graph edges.The visualization compares the explanatory predecessor structure with the rest of the graph.