A Tropical View of Graph Neural Networks

Learning dynamic programming algorithms with Graph Neural Networks (GNNs) is a research direction which is increasingly gaining popularity. Prior work has demonstrated that in order to learn such algorithms, it is necessary to have an ``alignment'' between the neural architecture and the dynamics of the target algorithms, and that GNNs align, in fact, with dynamic programming. Here, we provide a different view of this alignment, studying it through the lens of tropical algebra. We show that GNNs can approximate dynamic programming algorithms up to arbitrary precision, provided that their input and output are appropriately pre- and post-processed.