Learning Graph Algorithms With Recurrent Graph Neural Networks
This addresses a scalability challenge for researchers and practitioners using GNNs in graph algorithm learning, though it is incremental as it builds on existing GNN methods.
The paper tackled the problem of graph neural networks (GNNs) struggling to generalize and scale to larger graph instances by proposing a recurrent architecture with three techniques—skip connections, state regularization, and edge convolutions—to enable training on small graphs and extrapolation to larger ones, empirically validating this on algorithmic datasets.
Classical graph algorithms work well for combinatorial problems that can be thoroughly formalized and abstracted. Once the algorithm is derived, it generalizes to instances of any size. However, developing an algorithm that handles complex structures and interactions in the real world can be challenging. Rather than specifying the algorithm, we can try to learn it from the graph-structured data. Graph Neural Networks (GNNs) are inherently capable of working on graph structures; however, they struggle to generalize well, and learning on larger instances is challenging. In order to scale, we focus on a recurrent architecture design that can learn simple graph problems end to end on smaller graphs and then extrapolate to larger instances. As our main contribution, we identify three essential techniques for recurrent GNNs to scale. By using (i) skip connections, (ii) state regularization, and (iii) edge convolutions, we can guide GNNs toward extrapolation. This allows us to train on small graphs and apply the same model to much larger graphs during inference. Moreover, we empirically validate the extrapolation capabilities of our GNNs on algorithmic datasets.