Evolving-Graph Gaussian Processes

David Blanco Mulero, Markus Heinonen, Ville KyrkiarXiv 2021 · arXiv

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.

Conceptual overview of the e-GGP model, illustrating how node states and local neighborhoods ($V_i$) evolve over time under a Gaussian Process transition.

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:

  1. Graph Interaction (GI): A MuJoCo simulation of an elastic rope falling onto a static ball, where connectivity changes upon contact.
  2. 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).

Performance comparison across Graph Interaction and Evolving Isolated Sub-graphs tasks, showing e-GGP's superiority in RMSE, MAPE, and NLL metrics across various training sizes (N).

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

Abstract

Graph Gaussian Processes (GGPs) provide a data-efficient solution on graph structured domains. Existing approaches have focused on static structures, whereas many real graph data represent a dynamic structure, limiting the applications of GGPs. To overcome this we propose evolving-Graph Gaussian Processes (e-GGPs). The proposed method is capable of learning the transition function of graph vertices over time with a neighbourhood kernel to model the connectivity and interaction changes between vertices. We assess the performance of our method on time-series regression problems where graphs evolve over time. We demonstrate the benefits of e-GGPs over static graph Gaussian Process approaches.
BibTeX
@misc{mulero2021evolving,
  author = {David Blanco Mulero and Markus Heinonen and Ville Kyrki},
  title = {{Evolving-Graph Gaussian Processes}},
  year = {2021},
  eprint = {2106.15127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.15127},
}
Figure