Deep learning long-range information in undirected graphs with wave networks
This addresses a bottleneck in graph algorithms for fields like science and technology by enabling better long-range information propagation, though it is incremental as it builds on a recently proposed architecture.
The paper tackles the problem of efficiently propagating long-range information in undirected graphs, which existing deep learning architectures often fail at due to local aggregation. It shows that the wave network architecture learns three graph-based tasks with greater efficiency and accuracy, such as labeling paths and solving mazes, and can extrapolate from small training examples to larger ones.
Graph algorithms are key tools in many fields of science and technology. Some of these algorithms depend on propagating information between distant nodes in a graph. Recently, there have been a number of deep learning architectures proposed to learn on undirected graphs. However, most of these architectures aggregate information in the local neighborhood of a node, and therefore they may not be capable of efficiently propagating long-range information. To solve this problem we examine a recently proposed architecture, wave, which propagates information back and forth across an undirected graph in waves of nonlinear computation. We compare wave to graph convolution, an architecture based on local aggregation, and find that wave learns three different graph-based tasks with greater efficiency and accuracy. These three tasks include (1) labeling a path connecting two nodes in a graph, (2) solving a maze presented as an image, and (3) computing voltages in a circuit. These tasks range from trivial to very difficult, but wave can extrapolate from small training examples to much larger testing examples. These results show that wave may be able to efficiently solve a wide range of problems that require long-range information propagation across undirected graphs. An implementation of the wave network, and example code for the maze problem are included in the tflon deep learning toolkit (https://bitbucket.org/mkmatlock/tflon).