Post #658

The Exact Class of Graph Functions Generated by Graph Neural Networks by Mohammad Fereydounian (UPenn), Hamed Hassani (UPenn), Javid Dadashkarimi (Yale), and Amin Karbasi (Yale). ArXiv: https://arxiv.org/abs/2202.08833 A recent pre-print discussing the connections between Graph Neural Networks (GNNs) and Dynamic Programming (DP). The paper asks: Given a graph function, defined on an arbitrary set of edge weights and node features, is there a GNN whose output is identical to the graph function? They show that many graph problems, e.g. min-cut value, max-flow value, and max-clique size, can be represented by a GNN. Additionally, there exist simple graphs for which no GNN can correctly find the length of the shortest paths between all nodes (a classic DP problem). The paper's main claim is that this negative example shows that DP and GNNs are misaligned, even though (conceptually) they follow very similar iterative procedures. This claim has been hotly debated by Graph ML Twitter, with many interesting perspectives, e.g. see the original Tweet and subsequent discussions by L. Cotta and P. Veličković.