Source-linked AI summary
Graph Neural Ordinary Differential Equations
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, Jinkyoo Park
TL;DR
GDEs address how to combine graph structure with continuous system dynamics in GNNs. They define ODEs parameterized by GNNs and generalize them to static and autoregressive models. The framework offers numerical-solver advantages in static settings and improves dynamic modeling by representing evolving graph dynamics.
Problem
Existing graph models impose relational inductive biases, while continuous versus discrete temporal behavior provides a separate modeling consideration.
Method
GDEs define continuous-depth ODEs parameterized by GNNs and extend them to static and autoregressive graph models.
Results
GDEs outperform their discrete GNN analogues, provide numerical-method advantages in static settings, and improve dynamic forecasting by exploiting underlying dynamics.
Takeaways & Limitations
GDEs provide a data-driven framework for dynamical networks while embedding black-box numerical solvers in static GNN forward passes.
Takeaways & Limitations
The well-posedness guarantee assumes Lipschitz continuity in H and uniform continuity in s; the hybrid-model formalization omits technical details beyond the paper’s scope.
Abstract
from arXiv · showhide
We introduce the framework of continuous--depth graph neural networks (GNNs). Graph neural ordinary differential equations (GDEs) are formalized as the counterpart to GNNs where the input-output relationship is determined by a continuum of GNN layers, blending discrete topological structures and differential equations. The proposed framework is shown to be compatible with various static and autoregressive GNN models. Results prove general effectiveness of GDEs: in static settings they offer computational advantages by incorporating numerical methods in their forward pass; in dynamic settings, on the other hand, they are shown to improve performance by exploiting the geometry of the underlying dynamics.
1 Introduction
GDEs combine graph-based relational inductive biases with continuous-depth differential-equation dynamics. The framework supports static and dynamic graph settings, with numerical-solver benefits in static models and dynamical-system modeling in temporal ones.
- Framework scope: GDEs model vector fields on graphs whose structure may remain fixed or change over time through a continuum of GNN layers.
- Blending graphs and differential equations: GDEs define graph neural ordinary differential equations by parameterizing ODE vector fields with GNNs.They retain relational inductive biases while adopting a continuous-depth model perspective.
- Sequences of graphs: The framework extends to spatio-temporal graph sequences by modeling autoregressive GDEs as hybrid dynamical systems.The learned structure-dependent vector field is intended for nonlinear dynamical networked systems.
- GDEs as general-purpose models: GDEs can serve as general-purpose models without assuming that the data-generating process is continuous.Their forward pass can embed classic numerical schemes for GNN computation.
2 Graph Neural Ordinary Differential Equations
The GDE framework replaces discrete layer propagation with a graph-conditioned continuous-depth ODE. Its formulation supports numerical integration, multiple training strategies, and well-posed solutions under mild regularity conditions.
- 2 Graph Neural Ordinary Differential Equations: A GDE propagates an embedded input through a continuum of graph neural layers represented by a graph-conditioned vector field.The vector field may vary with depth and operates on node-feature matrices.
- Well-posedness: Under Lipschitz continuity in H and uniform continuity in s, each embedded input has a unique solution over S.This establishes the mapping from embedded inputs to absolutely continuous solution trajectories.
- Input and output mappings: The input embedding Xe can be produced from X using a linear layer or another GNN layer, and an output layer may process Y downstream.
- Integration domain: The integration interval is normalized to S = [0, 1], while application-specific intervals can evolve dynamics between irregular observation times.Numerical function evaluations serve as a proxy for model depth.
- GDE training: GDEs support standard backpropagation, adjoint sensitivity training, and backpropagation through relaxed spectral-elements discretizations.
3 Taxonomy of GDEs
GDEs are taxonomized into static and spatio–temporal autoregressive variants, extending graph convolution and other GNN architectures into continuous-depth models. In temporal settings, GDEs combine continuous latent evolution with discrete transitions for graph-sequence prediction.
- GDEs distinguish static models from spatio–temporal autoregressive variants.
- Static Models: GCDEs provide a continuous counterpart to residual GCNs by defining the vector field as a multilayer graph convolution.The graph convolution operator uses the graph Laplacian and trainable layer parameters.
- Static Models: Continuous-depth formulations also support diffusion-type convolution layers, while continuous counterparts of GATs and general message-passing GNNs are derived in supplementary material.
- Spatio–Temporal Models: For temporal data, GDE depth coincides with time and the integration interval can be adapted to the required prediction window.
- Spatio–Temporal Models: Autoregressive GDEs model graph sequences by combining a GDE that smoothly evolves latent node features with a discrete operator that produces a jump between time instants.
- Spatio–Temporal Models: The autoregressive formulation applies a continuous vector field between observations, a discrete transition at each observation time, and an output layer to produce predictions.The operators F, G, and K are GNN-like operators or general neural-network layers.
4 Experiments
The experiments evaluate GDEs across static node classification, multi-agent trajectory extrapolation, and traffic forecasting. Results indicate benefits from numerical integration in static settings and graph-structured continuous dynamics in forecasting and extrapolation.
- Experimental setup: The evaluation covers static node classification on Cora, Citeseer, and Pubmed, synthetic multi-agent trajectory extrapolation, and undersampled PeMS traffic forecasting.The static task compares GCNs with fixed-step and adaptive-solver GCDEs; the dynamic tasks compare GDEs with Neural ODEs and other baselines.
- Continuous-depth models in static tasks: Fixed-step GCDE variants outperform or match GCN* across all static datasets, with the largest improvements on Cora and Citeseer.GCDE-rk2 and GCDE-rk4 provide the most significant accuracy increases on denser graphs or with larger training sets.
- Continuous-depth models in static tasks: Higher-order GCDE-rk4 is generally more effective than GCDE-rk2 when graphs are sufficiently dense to benefit from additional computation.Adaptive-step GCDEs can produce deeper models, whereas GCDE-dpr5 may overfit because its high number of function evaluations is needed to satisfy solver tolerances.
- Resilience to integration time: GCDE-dpr5 remains resilient across integration times S ∈ [1, 5, 10], although longer integrations require more training epochs to reach comparable accuracy.The reported result is presented as evidence that GDEs are immune to node oversmoothing.
- Multi-agent trajectory extrapolation: GCDEs effectively leverage relational information to track the synthetic multi-particle system, while Static fails beyond one-step extrapolation and Neural ODE error grows rapidly.Second-order GCDE-II models outperform first-order GCDEs because their structure captures relative positions and velocities.
- Traffic forecasting: GCDE-GRUs outperform GCGRUs and GRUs in every PeMS undersampling regime, addressing changing prediction horizons caused by non-constant timestamp differences.The comparison uses structurally matched GCDE-GRU and GCGRU models.
5 Related work
The paper positions GDEs as a unified system-theoretic framework for continuous-depth GNNs across static and spatio-temporal models, with experiments aimed at identifying their performance advantages.
- GDEs unify continuous-depth GNN variants for static and spatio-temporal tasks within a system-theoretic framework.
- The framework differs from concurrent work by targeting a broad range of static and autoregressive GNN models rather than a single specialized formulation.
- Experiments evaluate GDEs on both static and dynamic tasks to investigate the sources of their performance improvements.
6 Discussion
GDEs extend to dynamically changing graph sequences and can accommodate topology variation while modeling structure-dependent continuous dynamics.
- Sequences of graphs: Autoregressive GDEs model spatio-temporal graph sequences as hybrid dynamical systems with structure-dependent vector fields.
- Sequences of graphs: The learned vector field provides a data-driven approach for networked systems whose governing equations may be highly nonlinear and difficult to derive analytically.
- Addition or removal of nodes: GDE variants can directly accommodate node additions or removals without changing the formulation when the node count remains constant during flows.
- Addition or removal of nodes: The parameter matrix Θ depends only on node feature dimension, supporting resilience to a varying number of nodes.
7 Conclusion
GDEs provide a general continuous-depth counterpart to GNNs, supporting irregular-time forecasting and numerical-solver integration while outperforming discrete counterparts in the reported evaluations.
- GDEs propagate inputs through a continuum of GNN layers and can adapt to many static and autoregressive GNN models.
- In sequential forecasting, GDEs accommodate irregular timestamps and track underlying continuous dynamics.
- In static settings, GDEs embed black-box numerical solvers in the forward pass, offering computational advantages.
- GDEs are reported to outperform their discrete counterparts on both static and dynamic tasks.
Equations Supplementary Material
The supplementary material defines graph and continuous-depth notation, formulates GDEs and their message-passing and attention variants, and discusses solver-dependent computational overhead.
- Graph notation: A graph G consists of a finite node set V and edge set E, with adjacency encoded by a matrix A.
- Graph notation: Attributed graphs associate each node with a feature vector, collected into a feature matrix X that may vary over time.
- General formulation: The static GDE formulation evolves hidden states H(s) from an embedded input Xe through a graph-conditioned vector field and maps them to outputs Y(s).
- Computational overhead: GDE computational overhead depends primarily on the numerical solver, with fixed-step complexity O(nk) for a k-th-order method.
- Computational overhead: Adaptive-step solver overhead depends on error tolerances and has no bounded worst-case computation, although a maximum step count can usually be imposed.
- Additional GDEs: Message-passing and attention GDEs provide continuous-depth counterparts to MPNN and GAT updates, respectively.
C Additional experimental details
The experiments use GPU-trained GDE variants with shared architectural and optimization choices, including smooth activations intended to reduce ODE stiffness and function evaluations.
- All experiments were trained on a cluster of 4×12GB NVIDIA Titan Xp GPUs using CUDA 10.1.
- GCDEs for node classification share a general architecture whose vector field is parameterized by two GCN layers.GCDEs–dopri5 omits the GDE–2 GCN component.
- Training used Adam for 2000 epochs, with learning rates of 10^-3 on Cora and Citeseer and 10^-2 on Pubmed.Reported results selected the lowest validation-loss model after convergence, without using test metrics during setup.
- SoftPlus activations were used for GDEs because smooth activations can reduce stiffness and the number of function evaluations needed for acceptable tolerances.Other activation functions were ReLUs.
C.2 Multi–Agent System Dynamics
The multi-agent experiment models interacting particles whose time-varying adjacency encodes reciprocal forces, then evaluates GDE extrapolation over multiple steps.
- System setup: The system is a planar multi-agent model with n = 10 particles and second-order dynamics.A single rollout uses T = 5 and dt = 1.95 · 10^-3.
- Evaluation: Across ten multi-particle dynamical-system experiments, MAPE_i reports performance after i extrapolation steps on the full test trajectory.
- System setup: The interaction force resembles a spatial spring with drag, while −x_i stabilizes trajectories and avoids phase-space explosion.Forces are reciprocal, with f_ij = −f_ji.
- Graph construction: The adjacency matrix A_t is computed along the trajectory, yielding an undirected graph whose edges indicate reciprocal forces between particles.Figure 8 visualizes snapshots of A_t during the dynamics.
- Results: After five-step extrapolation, GDEs closely track particle positions and velocities, whereas Neural ODEs fail particularly where interaction forces strongly affect dynamics.The nominal state is fed to the model after each extrapolation segment.
C.3 Traffic Forecasting
The traffic experiments evaluate graph-based continuous-depth forecasting under irregular timestamp gaps and undersampling, comparing GCDE–GRU with recurrent baselines.
- Data and evaluation: Timestamp differences vary because of undersampling, with distributions reported for 30%, 50%, and 70% undersampling.The varying time scale changes the prediction interval across the task.
- Models and metrics: GRU receives 230-dimensional vectors, while GCGRU and GCDE–GRU use graph inputs with three-dimensional node features.The additional time features are excluded from loss computations.
- Models and metrics: The traffic models are evaluated with MAPE and RMSE test measurements.
- Training results: The traffic training curves use 50% undersampling, and all models reach nearly 13 RMSE during training.
- Model design: GCDE–GRU adds a flow F to GCGRU for evolving hidden features between arrival times.
- Optimization: Traffic models are trained for 40 epochs with Adam, cosine-annealed learning rate scheduling, and mean squared error loss.The initial learning rate is 10^-2 and T_0 = 10.
- Training results: Despite fitting the training data, GRUs fail to generalize to the test set and produce a mean-value prediction because they lack dedicated spatial modeling modules.
- Prediction results: GCDE–GRUs evolve latent representations between timestamps, providing a more accurate fit in the 50%-undersampled prediction results.