Deep learning long-range information in undirected graphs with wave
  networks
  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).
