Do Graph Neural Networks Learn Generalizable Algorithms for Clustering Graphs?

We study the ability of graph neural networks (GNNs) to learn generalizable algorithms for graph clustering. While previous work has shown that GNNs can learn to cluster graphs in-distribution, it is unclear exactly what algorithms these networks are learning, or whether they generalize to unseen graphs that differ significantly from their training data. In this paper, we pick a standard cut-based clustering cost function and train GNNs of various types to minimize this function on a suite of training examples. We then test whether the resulting networks are able to generalize to much larger graphs, or other families of graphs. We complement our empirical findings with a host of theoretical results that illustrate the range of possible heuristics that these different GNNs could be implementing. Finally, we use probes on trained networks to narrow down the heuristics actually being learned. Our findings show that there is generalization across the board but that GNNs of different expressivity---MPNNs versus PPGNs, for instance---learn markedly different algorithms.