Neural Execution of Graph Algorithms
This work addresses the challenge of making GNNs more structured and interpretable for graph algorithm execution, which is incremental as it builds on existing GNN architectures but applies them in a novel way.
The paper tackled the problem of training Graph Neural Networks (GNNs) to imitate steps of classical graph algorithms, such as breadth-first search and Prim's algorithm, rather than directly solving problems from raw inputs. The result showed that maximisation-based message passing GNNs are best-suited for this task, and learning multiple algorithms simultaneously improved performance, as demonstrated by substantial gains in learning a shortest-path algorithm when combined with a reachability algorithm.
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.