Neural Execution of Graph Algorithms

2019/10/23 by Petar Veličković, Rex Ying, Veličković, Petar +7 · 10 citations
Computer Science · #Advanced Graph Neural Networks #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1910.10593

openalex publication_date 2019/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Learning to Execute
• Networks, Dynamics, and the Small‐World Phenomenon
• Neural GPUs Learn Algorithms
• Semi-Supervised Classification with Graph Convolutional Networks
• Categorical Reparameterization with Gumbel-Softmax
• Geometric Deep Learning: Going beyond Euclidean data
• Learning a SAT Solver from Single-Bit Supervision
• Attention, Learn to Solve Routing Problems!

Cited by

• HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers
• Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
• Neuro-Symbolic Constrained Optimization for Cloud Application Deployment via Graph Neural Networks and Satisfiability Modulo Theory
• Neural Graph Navigation for Intelligent Subgraph Matching
• Enhancing Graph Representations with Neighborhood-Contextualized Message-Passing
• Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
• KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems
• Automated discovery of finite volume schemes using Graph Neural Networks
• Learning neuro-symbolic convergent term rewriting systems
• Principal Neighbourhood Aggregation for Graph Nets

Related

• Theory of Graph Neural Networks: Representation and Learning
• Graph Neural Networks are Dynamic Programmers
• A Practical Tutorial on Graph Neural Networks
• Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems
• Computing Graph Neural Networks: A Survey from Algorithms to Accelerators