  Relational inference aims to identify interactions between parts of a
dynamical system from the observed dynamics. Current state-of-the-art methods
fit the dynamics with a graph neural network (GNN) on a learnable graph. They
use one-step message-passing GNNs -- intuitively the right choice since
non-locality of multi-step or spectral GNNs may confuse direct and indirect
interactions. But the \textit{effective} interaction graph depends on the
sampling rate and it is rarely localized to direct neighbors, leading to poor
local optima for the one-step model. In this work, we propose a \textit{graph
dynamics prior} (GDP) for relational inference. GDP constructively uses error
amplification in non-local polynomial filters to steer the solution to the
ground-truth graph. To deal with non-uniqueness, GDP simultaneously fits a
``shallow'' one-step model and a polynomial multi-step model with shared graph
topology. Experiments show that GDP reconstructs graphs far more accurately
than earlier methods, with remarkable robustness to under-sampling. Since
appropriate sampling rates for unknown dynamical systems are not known a
priori, this robustness makes GDP suitable for real applications in scientific
machine learning. Reproducible code is available at
https://github.com/DaDaCheng/GDP.
