Graph dynamics model predicts changing networks in uncertain settings
Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies
Machine LearningArtificial IntelligenceSocial and Information Networks
Summary
Many models assume networks (graphs) don’t change over time, but real-world situations often involve networks that evolve unpredictably. This paper presents the Graph Dynamics Model (GDM), which can learn and predict how both the structure and attributes of a network change in environments that have randomness and only partial observations. The authors also introduce a new way to measure how well these models capture the true behavior of evolving networks. Their experiments show that the GDM produces better predictions and can handle larger networks than previous methods.
What this means in practice
- •For robotic system developers: Improve robot planning in environments where connections between objects or agents change unpredictably and cannot be fully observed.
- •For network operations teams: Predict evolving network structures and node states under uncertainty to better maintain and optimize infrastructure.
Authors
Alex Schutz, Nick Hawes, Victor-Alexandru Darvariu
Abstract
Graph-based world models have recently emerged as a means of learning transitions over relational state representations. However, existing approaches are largely limited to fixed-topology graphs or deterministic, fully observable environments. We propose the Graph Dynamics Model (GDM), a world model for graph-structured observations that is designed to handle the more general setting of evolving topologies in stochastic and partially observable environments. The GDM uses a sparse recurrent adjacency matrix to model topology updates and perform message passing, together with a recurrent state-space architecture for modelling stochastic transitions. Furthermore, we identify a gap in the evaluation of graph-based world models, as existing methods do not provide a means of comparing predicted and true distributions over the joint graph state comprising the interdependent topology, node features, and graph features. We therefore introduce the Graph Distribution Distance (GDD) metric, which uses maximum mean discrepancy with a graph kernel to comprehensively compare joint next-state distributions. We evaluate the GDM across several environments, including stochastic and partially observable settings. We demonstrate that GDM outperforms baseline models and displays zero-shot generalisation on large graphs.