# A Graph Dynamics Prior for Relational Inference

arXiv: https://arxiv.org/abs/2306.06041 · HTML: https://mlsanity.com/paper/2306.06041/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 11 of 11)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [Discovering Nonlinear Relations with Minimum Predictive Information Regularization](https://mlsanity.com/paper/2001.01885/) (2020)
- [Inferring Graphs from Cascades: A Sparse Recovery Framework](https://mlsanity.com/paper/1505.05663/) (2015)

## Built on by (most cited first, 2 of 2)

- [From Uniform to Learned Graph Priors: Diffusion for Structure Discovery](https://mlsanity.com/paper/2606.11831/) (2026)
- [On Observation Time for Recovering Latent Hawkes Networks](https://mlsanity.com/paper/2605.08400/) (2026)

## Abstract (arXiv)

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 textiteffective 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 textitgraph 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.