Introduction
Complex systems—ranging from social networks and neural activity to physical particle interactions—are naturally represented as graphs. However, these systems are rarely static; their structures evolve as connections are formed or broken. While Graph Gaussian Processes (GGPs) provide a powerful framework for modeling such data with inherent uncertainty quantification, most existing formulations assume a fixed graph topology. This limitation hinders their application in dynamic environments where structural changes are frequent.
Problem Statement
Modeling dynamic graphs presents unique challenges. Deep learning models for dynamic graphs exist but often require large amounts of data and lack reliable uncertainty estimates—a critical requirement for safety-critical applications like robotics or physical simulations. There is a pressing need for a model that can handle time-varying connectivity while maintaining the data efficiency and probabilistic rigor of Gaussian Processes.
Methodology: Evolving-Graph Gaussian Processes (e-GGPs)
The authors introduce Evolving-Graph Gaussian Processes (e-GGPs), an autoregressive framework designed to learn transition functions over dynamic graphs. The model predicts the "velocity" of a node based on its current state and its local neighborhood.
The "secret sauce" of e-GGP is the Attributed Sub-tree Kernel. Instead of relying on a global adjacency matrix, the kernel measures similarity by comparing local 1-hop neighborhoods (sub-trees). This local focus allows the model to naturally accommodate nodes being added or removed and enables generalization to unseen graph structures. By learning local interaction rules, the model can apply its knowledge to larger or differently structured clusters.
Experimental Evaluation
The e-GGP model was evaluated on two complex physical simulations where connectivity changes dynamically:
- Graph Interaction (GI): A MuJoCo simulation of an elastic rope falling onto a static ball, where connectivity changes upon contact.
- Evolving Isolated Sub-graphs (EIs): A Taichi-MPM simulation of 2D fluid particles that merge and split into various clusters.
Results and Discussion
The e-GGP was benchmarked against standard GP Regression (GPR), Gaussian Process Autoregressive (GPAR) models, and Deep Graph Gaussian Processes (DGPG).
A key finding is the model's exceptional performance in "data-poor" regimes. In the Graph Interaction task, e-GGP achieved an RMSE of 0.049 with only 10 training timepoints, significantly outperforming GPR (0.121). In the fluid simulation (EIs), e-GGP maintained a consistently low RMSE (~0.18), whereas other graph-based methods struggled with the highly dynamic connectivity. Furthermore, the model provides a probability distribution for its predictions, allowing for clear identification of regions where the simulation enters "uncharted territory."
Conclusion and Future Work
e-GGPs represent a significant step forward in modeling dynamic systems with Gaussian Processes. By leveraging local neighborhood kernels, the model achieves high accuracy and robust uncertainty quantification even with minimal training data. While the current $O(N^3)$ complexity poses scalability challenges for very large graphs, future work involving variational inference and deeper neighborhood exploration promises to extend the reach of this framework to even more complex real-world systems.
Summary updated