Research map / Graph learning / GNN architectures
A Graph Dynamics Prior for Relational Inference
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GDP, a relational inference method that jointly fits a one-step GNN and a polynomial multi-step GNN with shared learnable graph, using polynomial error amplification to escape local minima and recover graphs under undersampling.
Problem
Relational inference: recovering direct interaction graphs from observed dynamics of graph dynamical systems, where low sampling rates make the effective interaction graph non-local and confuse direct with indirect interactions, trapping one-step GNN surrogates in poor local minima.
Approach
Train two parallel surrogates with a shared learnable adjacency: a shallow one-step message-passing model on the adjacency matrix and a polynomial graph-filter model g_theta(A); the polynomial amplifies graph perturbations to steer optimization, while the one-step model keeps the solution close to direct interactions.
Key results
- GDP reaches 98.31±1.41 AUC on Michaelis-Menten ER-50 at delta t=1 versus 54.09±2.22 for NRI and 77.84 for MI.
- On Rössler ER-50 at delta t=1, GDP achieves 99.89±0.23 AUC versus 60.35±4.58 for NRI.
- On Netsim at delta t=1, GDP reaches 95.09±0.68 AUC versus 71.57±1.57 for NRI.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GDP's shared-topology two-scale model instead of the strongest listed baseline | Relational inference · Michaelis–Menten, ER-50, δt=1 | AUC: 77.84 -> 98.31±1.41 | Helped |
| Use GDP instead of NRI | Relational inference · Diffusion, ER-50, δt=4 | AUC: 60.23±6.73 -> 93.39±4.87 | Helped |
| Use GDP instead of NRI | Relational inference · Rössler oscillators, ER-50, δt=1 | AUC: 60.35±4.58 -> 99.89±0.23 | Helped |
| Use GDP instead of MI | Relational inference · Spring, BA-50, δt=40 | AUC: 92.82 -> 83.77±9.14 | Hurt |
| Use GDP instead of MI | Relational inference · Netsim, δt=1 | AUC: 94.73 -> 95.09±0.68 | No clear effect |
| Stack two message-passing layers rather than use the one-step NRI baseline (ablation) | NRI · Spring, ER-50, δt=20 | AUC: 99.84±0.47 -> 51.01±0.64 | Hurt |
| Stack two message-passing layers rather than use the one-step NRI baseline (ablation) | NRI · FJ, ER-50, δt=1 | AUC: 97.67±1.06 -> 53.81±1.64 | Hurt |
| Use only the polynomial model without the parallel adjacency model (ablation) | GDP · Diffusion, ER-50, δt=1, seed 0 | AUC: 85.90; 92.04; 90.47 | Mixed |
| Vary polynomial order K from the tested settings (ablation) | GDP · Michaelis–Menten, ER-20, δt=4 | AUC | Mixed |
| Activate the polynomial model after one-step training plateaus (ablation) | GDP · Kuramoto, ER-50 | AUC | Helped |
Surprising findings
- Simply stacking two message-passing layers degrades NRI to near-chance AUC (about 51-54) under undersampling.
- For discrete linear dynamics, odd sampling hops can yield higher AUC than smaller intervals, so larger sampling intervals do not always worsen recovery.
Limitations
- Works only when effective interaction graph is strongly correlated with direct interactions; weakly correlated regimes are untested.
- Assumes all nodes are fully observed; partial observation and time-varying topology not handled.
- Lacks a precise theory; claims are heuristic and experimental.
Experimental setup
Datasets: Michaelis-Menten simulated Rössler oscillators simulated Diffusion simulated Springs simulated Kuramoto simulated Friedkin-Johnsen simulated Coupled map network simulated Netsim fMRI METR-LA traffic S. cerevisiae gene regulatory network
Benchmarks: Michaelis-Menten simulated Rössler oscillators simulated Diffusion simulated Springs simulated Kuramoto simulated Friedkin-Johnsen simulated Coupled map network simulated Netsim
Metrics: AUC
Baselines: NRI mutual information transfer entropy
Builds on: Neural relational inference (NRI) GPR-GNN ChebyNet Deep image prior
Closest papers by meaning
- Benchmarking Structural Inference Methods for Interacting Dynamical Systems with Synthetic Data (NeurIPS 2024 · similarity 0.89)
- Interpretable Relational Inference with LLM-Guided Symbolic Dynamics Modeling (NeurIPS 2026 · similarity 0.89)
- When Graph Neural Networks Meet Dynamic Mode Decomposition (ICLR 2025 · similarity 0.88)
- Valid Conformal Prediction for Dynamic GNNs (ICLR 2025 · similarity 0.88)
- Online Relational Inference for Evolving Multi-agent Interacting Systems (NeurIPS 2024 · similarity 0.87)
- A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.