Neural Execution of Graph Algorithms

By Petar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell, Charles Blundell. 2019

201 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Graph Learning

Citations in the corpus

Show Your Work: Scratchpads for Intermediate Computation with Language Models (2021, neutral): “The related problem of neural algorithm induction has attracted considerable interest (Graves et al., 2014; Kurach et al., 2016; Kaiser & Sutskever, 2016; Graves et al., 2016; Reed & de Freitas, 2016; Veliˇckovi´c et al., 2020a;b).”
Neural Execution Engines: Learning to Execute Subroutines (2020, methodology): “We also test on other graph types (including those from [28]) and perform well.”
Learning to Simulate Complex Physics with Graph Networks (2020, background): “, 2019), algorithm execution (Velikovi et al., 2020), and other dynamic graph settings (Trivedi et al.”
PonderNet: Learning to Ponder (2021, background): “This can be useful in learning e.g. how many message-passing steps to do in a graph network (Veličković et al., 2019).”
Neural algorithmic reasoning (2021, background): “Furthermore, a single network may be taught multiple known algorithms and abstract commonalities among them [Veličković et al., 2019], allowing novel algorithms to be derived.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “on neural execution of graph algorithms [133] is among the rst to propose algorithmic learning as a rst-class citizen and suggests several general-purpose modi cations to GNNs to make them stronger combinatorial reasoners.”
Identity-aware Graph Neural Networks (2021, background): “Several models color nodes with augmented features to boost existing GNNs’ performance (Xu et al. 2020; Veličković et al. 2020; Zhang and Chen 2018).”
How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks (2020, methodology): “, 2019), graph algorithms (Battaglia et al., 2018; Velickovic et al., 2020), and symbolic mathematics (Lample & Charton, 2020).”
ETA Prediction with Graph Neural Networks in Google Maps (2021, background): “Improving such an alignment is known to help GNNs generalise better to a diverse distribution of graphs [27].”
Design Space for Graph Neural Networks (2020, methodology): “For example, a GNN model that changes the aggregation function of GraphSAGE to a summation, or adds skip connections [8] across GraphSAGE layers, is not referred to as GraphSAGE model, but it could empirically outperform it in certain tasks [32].”
Principal Neighbourhood Aggregation for Graph Nets (2020, methodology): “STD is not used in the GNN literature.”