Learning Algorithmic Tasks with Graph Neural Networks: Generalization and Extrapolation

Graph Neural Networks (GNNs) have become a popular tool for learning algorithmic tasks, in particular related to combinatorial optimization. In this talk, we will focus on the “algorithmic reasoning” task of learning a full algorithm. While GNNs have shown promising empirical results, their generalization properties are less well understood. In particular, the results are affected by the representational power, task and data properties, and inductive biases from architectural structure and learning algorithm. The talk summarizes effects of all of these. For instance, empirically, we observe an interplay between the structure of the task — or target algorithm — and the inductive biases of the architecture: although many networks may be able to represent a task, some architectures learn it better than others. We formalize this relationship via “algorithmic alignment”, and study empirical and theoretical implications for generalization within and out of the training distribution. Our results suggest different alignment conditions for within-distribution generalization and for extrapolation, where, for extrapolation with ReLU GNNs, nonlinearities play an important role.

This talk is based on joint work with Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, Vikas Garg and Tommi Jaakkola.