acceptodds
Under review as a conference paper at ICLR 2027

Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
World Models, Graph Neural Networks, Model-Based Reinforcement Learning, Graph Representation Learning, Dynamic Graphs, Graph World Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_JJ7UOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes GDM, an RSSM-style world model for graph environments whose edges change over time. It keeps per-node and graph-level deterministic and stochastic states, plus a recurrent sampled adjacency matrix updated by Hard Concrete edge flips, and runs message passing on the predicted topology. It also proposes GDD, an MMD with a characteristic kernel over (topology, node features, graph features) for comparing predicted and true next-state distributions. On four synthetic environments (RGC, OD, SAR, CF), trained on 15–25 nodes and tested up to 1000 nodes, GDM outperforms Vanilla GWM, EA-GWM and G-RSSM on single- and multi-step GDD in most settings.

Critical strengths
  1. This paper proposes a clear and clean edge dynamic design.

  2. The experimental results show the performance of the proposed model against several baselines.

  3. The gap between the proposed model and baselines is carefully analyzed.

Critical weaknesses
  1. In Figure 5, GDM has much lower topology MMD than the baselines, while the node feature results are often similar. For CF at larger graph sizes, its graph feature result is worse. The comparison is difficult to interpret because the GWM baselines do not explicitly use the previous adjacency when predicting the next one. Since much of the graph usually stays the same between steps, I would like to see a simple baseline that copies the previous adjacency for topology evaluation, or GWM baselines that condition adjacency predictions on the previous adjacency. This would help show how much improvement comes from GDM’s architecture.

  2. The paper argues that the joint-kernel term captures dependencies between topology and features. I could not find an empirical example where GDD gives a different useful conclusion from the separate MMD terms. Please compare GDD with an additive-only version and show how the joint-term weight affects the results.

  3. In Table 5, setting β_h = 0 gives lower mean GDD at every tested size on SAR, including 0.835 versus 0.878 at 200 nodes. It also improves several CF and RGC results. Removing the graph state improves RGC at 100–200 nodes. Section 6.3 acknowledges these patterns, but more discussion about when these components help would be useful.

  4. The size generalization result is mixed. SAR is the clearest positive case. On CF, it ties Vanilla GWM at 200 nodes. On RGC at 200 nodes, its mean is slightly higher than Vanilla GWM’s (1.175 versus 1.167), with substantial uncertainty. GDM remains better than the baselines on OD.

Questions for authors

Please respond to the above weaknesses.

6 comments

Thank you for your careful review and recognition of the contributions of our work. We welcome the opportunity to clarify these points below. We respectfully note that, while they were listed as Critical Weaknesses (perhaps due to the format of the review form), they mostly concern an additional baseline (W1) and the interpretation of experimental results (W2-W4).

W1: Previous-state baseline

Thank you for this suggestion as it really helps contextualise the GDD values. We have added a baseline which simply copies the previous observation, including the topology, node and graph features, reward, and continuation signal. We have updated Table 1 and Figures 5, 6 in the manuscript to include the new baseline.

This baseline performs poorly in partially observable environments, but achieves strong results in RGC, particularly at larger graph sizes. This is likely because RGC modifies at most one edge per transition, regardless of graph size. As the graph grows, the proportion of unchanged edges increases, while learned models have more opportunities to make prediction errors. When evaluating topology predictions using Jaccard similarity, the copy baseline performs particularly well in OD, and this is the only environment where the copied topology outperforms GDM's topology predictions.

We have also implemented additional GWM variants as baselines which condition adjacency predictions on the previous adjacency, using the same update head as GDM. Please see our response to Reviewer 1txk for our discussion of these results.

W2: Joint kernel in GDD

The joint kernel is the primary component of GDD, and is essential to the theoretical properties of GDD. Unlike an additive-only kernel, it is characteristic, guaranteeing that GDD is zero if and only if the predicted and true distributions are identical. We include the additive terms in the calculation of GDD as it is useful to discriminate between models with similar joint predictions, as discussed in Section 5. This is why each additive MMD term receives only a third of the weighting of the joint term.

To illustrate the importance of the joint term, consider a simple environment with one binary node feature and one binary graph feature. Suppose the true distribution assigns probability 0.5 each to (0,0)(0,0) and (1,1)(1,1), while the model assigns probability 0.5 each to (0,1)(0,1) and (1,0)(1,0). Both marginal distributions are identical, so MMDadd\mathrm{MMD}_{\mathrm{add}} is exactly zero, despite the predicted joint distribution being entirely incorrect. Using our categorical joint kernel with λn=λg=1\lambda_n=\lambda_g=1, we obtain MMDjoint≈0.632\mathrm{MMD}_{\mathrm{joint}}\approx 0.632, clearly demonstrating the poor fit of the model, unlike MMDadd\mathrm{MMD}_{\mathrm{add}}.

In the revised version of the paper, we have added an additional row of plots to Figure 5 showing the additive component of GDD only. From the plots, we see that the GDD curves are similar in both shape and conclusion to both the joint terms and the additive terms, but the range of scores for joint MMD is much more compressed than in GDD. For example, in SAR the joint MMD score shows G-RSSM and the GWM models performing very similarly, while including the additive term distinguishes that G-RSSM performs worse at a per-factor level.

W3: Ablation results

The usefulness of individual architectural components (naturally) depends on the environment. βh\beta_h controls the alignment between deterministic prior and posterior states. Removing this term improves performance in SAR and some CF and RGC settings, suggesting that enforcing alignment is not always beneficial. We didn’t include βh\beta_h in our hyperparameter search, instead fixing it to 11. These results indicate that it is an impactful hyperparameter which should be tuned for each environment, potentially improving performance further. We have added clarifications to Section 6.3.

W4: Size generalisation

GDM outperforms or matches (i.e., is within reported uncertainty of) all originally reported baselines when evaluated across all evaluated graph sizes, despite being trained exclusively on graphs with 15-25 nodes. The differences highlighted for CF and RGC at 200 nodes are negligible relative to the uncertainty, and do not demonstrate a meaningful performance disadvantage. RGC is deterministic and fully observable, so we would expect the deterministic GWM baselines to perform well in this environment. In contrast, GDM achieves substantial improvements in the stochastic OD and SAR environments, while remaining competitive on CF. These are the key environments where a learned model that predicts distributions is useful.

We do not claim that performance is invariant to graph size. Some deterioration is expected due to distribution shift when evaluating on graphs substantially larger than those encountered during training. Nevertheless, GDM retains competitive performance on graphs up to 1000 nodes without retraining, demonstrating its ability to generalise to substantially larger environments.

The additional comparators added during this rebuttal (variants of Vanilla GWM / EA-GWM with GDM’s adjacency module added, copying the previous observation, and the standard Dreamer RSSM) provide additional context. The interpretation in Section 6.1 was revised to be more nuanced in light of these new results.

Dear Authors,

Thank you for the response. I would like to have more details about your response to my first weakness (previous state baseline). I found it is quite hard to understand the revised part in your paper. I would like to have a detailed introduction about: 1. which baselines are added, together with more analysis about the results. Please also introduce the setting of the copy baseline. 2. Please provide more discussion and justification about your claim "This is likely because RGC modifies at most one edge per transition, regardless of graph size." 3. I would also like to know if the code can be provided, especially for the implementation of the added experiment in the rebuttal.

Reviewer_RHkWOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The authors present Graph Dynamics Model (GDM), a world model for graph data that also handles partially observed data and stochasticity. Furthermore, a novel evaluation metric is defined and experiments show the merit of these methods.

Critical strengths
  • Novel evaluation metric. Dynamic (learned) graphs field should benefit from better evaluation practices.
Critical weaknesses
  • I have trouble finding real-world use of these proposed methods. The paper would benefit from embedding the methods more into real-world, useful tasks, for which these methods are ideal and optimal. By which I mean, also the overarching 'graph' construct, can these problems also be solved by other representations.
  • Evaluations are on synthetic toy-problems, and quite limited in scope. I would like to see real problems being attacked, and comparison to non-graph methods as well.
Questions for authors
  • Can you add comparisons of your methods to non-graph methods?
2 comments

Thank you for your review and for recognising the value of our proposed evaluation metric. We respond to your comments regarding real-world applications and comparisons to non-graph methods below.

Real-world applications and evaluation

We envisage GDM being useful in a range of real-world applications where the underlying system can be naturally represented as a dynamic graph. Examples include understanding the dynamics of power grids and predicting how traffic patterns respond to changes in road network layouts. There is already a substantial body of work applying reinforcement learning to such problems, for example in power grid control through the Learning to Run a Power Network (L2RPN) challenge [1], and in traffic network optimisation [2]. These are just a few examples, but graphs are a very versatile representation used in various domains and scientific fields [3].

Dynamic processes over graphs are also of wide interest [4]. This motivates the development of graph-based world models which can learn the underlying dynamics and generalise to unseen graph structures. Graph representations are useful because they primarily model the entities and their interactions without artificially introducing, for example, orderings which are not present in the underlying problem. Using non-graph approaches can tie the learned models to arbitrary node orderings or inhibit useful properties like generalisation to different structures / sizes.

We have extended our experiments to include RGC and CF on real-world infrastructure topologies (power grids and road networks) in order to evaluate the zero-shot transfer capabilities of GDM in more realistic settings. Please see Section 6.4 of the updated manuscript for these additional results.

We acknowledge that these environments remain mathematical abstractions and simplifications of the underlying real-world problems, rather than complete simulations. Unfortunately, the lack of publicly available action-conditioned dynamic graph datasets currently limits our ability to directly evaluate GDM on granular trajectories. We therefore began with simpler, synthetic benchmarks in order to validate the approach under controlled conditions.

In particular, these environments allow us to systematically vary properties such as partial observability and the level of stochasticity, and isolate their effects. Achieving strong performance across these different conditions provides evidence of a model's potential in more complex real-world environments. Nevertheless, we agree that evaluation on more realistic problems is an important next step, and intend to pursue this in future work.

[1]: Marot, A., Donnot, B., Dulac-Arnold, G., Kelly, A., O’Sullivan, A., Viebahn, J., Awad, M., Guyon, I., Panciatici, P. & Romero, C. "Learning to run a Power Network Challenge: a Retrospective Analysis". In Proceedings of the NeurIPS 2020 Competition and Demonstration Track, 2021.
[2]: F. -X. Devailly, D. Larocque and L. Charlin, "Model-Based Graph Reinforcement Learning for Inductive Traffic Signal Control," in IEEE Open Journal of Intelligent Transportation Systems, vol. 5, pp. 238-250, 2024.
[3]: Newman, M. (2018). Networks (Second edition). Oxford University Press.
[4]: Barrat, A., Barthelemy, M., & Vespignani, A. (2013). Dynamical processes on complex networks. Cambridge University Press.

Comparison to non-graph methods

We have implemented DreamerV3 as a non-graph baseline, using the same training procedure as GDM. In this implementation, we use an MLP encoder which takes the flattened adjacency matrix as input. Since this requires a fixed input dimensionality, we set the maximum graph size to 30 nodes. The results are shown below, and have been added to the manuscript in Table 1 and Figures 5 and 6.

EnvBaseline∥V∥=20\|V\|=20∥V∥=30\|V\|=30
RGCGDM0.950 ± 0.0070.880 ± 0.012
RGCVanilla GWM1.168 ± 0.0021.158 ± 0.003
RGCEA-GWM1.167 ± 0.0021.161 ± 0.005
RGCG-RSSM1.226 ± 0.0091.229 ± 0.007
RGCDreamer RSSM1.185 ± 0.0051.244 ± 0.016
ODGDM0.449 ± 0.0420.426 ± 0.041
ODVanilla GWM0.916 ± 0.0050.913 ± 0.004
ODEA-GWM0.920 ± 0.0110.920 ± 0.009
ODG-RSSM1.034 ± 0.0021.024 ± 0.002
ODDreamer RSSM1.020 ± 0.0031.017 ± 0.002
SARGDM0.917 ± 0.0230.917 ± 0.028
SARVanilla GWM1.122 ± 0.0041.131 ± 0.003
SAREA-GWM1.126 ± 0.0061.133 ± 0.005
SARG-RSSM1.139 ± 0.0051.164 ± 0.005
SARDreamer RSSM1.165 ± 0.0051.190 ± 0.005
CFGDM0.914 ± 0.0380.890 ± 0.043
CFVanilla GWM1.179 ± 0.0021.198 ± 0.003
CFEA-GWM1.171 ± 0.0021.193 ± 0.003
CFG-RSSM1.240 ± 0.0101.277 ± 0.010
CFDreamer RSSM1.202 ± 0.0061.299 ± 0.008

The results demonstrate that Dreamer performs substantially worse than GDM in these environments. However, beyond the difference in performance, a fundamental limitation of this approach is its inapplicability on graphs of different sizes. Since the adjacency matrix is flattened into a fixed-dimensional vector, the model cannot be directly applied to graphs larger than those encountered during training. In contrast, graph-native architectures operate on individual nodes and edges using shared parameters, allowing the same model to be applied to graphs of arbitrary sizes. Furthermore, graph neural networks are permutation-equivariant by construction, meaning that their predictions are consistent under arbitrary relabellings of the nodes. A standard MLP operating on a flattened adjacency matrix does not have this property, and must instead learn these symmetries from data.

We hope that these additional experiments and clarifications address your concerns. We would also welcome any suggestions regarding specific non-graph methods that you believe would be informative within the scope of this experimental setup.

Reviewer_1txkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes GDM, an RSSM-style world model for graphs whose topology changes over time. GDM carries the adjacency matrix as a recurrent state and updates it by sampling edge flips. The paper also proposes GDD, an MMD-based metric over the joint distribution of topology, node features and graph features. Models trained on small graphs from four synthetic environments are compared with adapted EA-GWM, Vanilla GWM and G-RSSM on graphs of up to 1k nodes.

Critical strengths
  • Predicting edge flips relative to the previous adjacency suits graphs whose topology changes incrementally. The ablation shows that this design drives most of the gain.
  • Stochastic world models should be judged on predicted distributions rather than point errors. GDD is a promising attempt at this.
  • The experiments use 10 seeds with confidence intervals and test graphs up to 40× larger than the largest training graph. The gains on OD and SAR are large at every size.
Critical weaknesses
  • The target distribution is generated from the full simulator state, including variables the model cannot observe (App. D), and per-step GDD is averaged. In this setting, always predicting the most likely outcome can score better than predicting the correct belief. This undermines the comparison exactly in the stochastic, partially observable environments (SAR, CF) that the paper targets.
  • The proposed metric GDD is less interpretable: almost all baselines score between 0.9 and 1.5 on a 0–2 scale, even on the deterministic RGC environment. Without simple reference predictors, it is impossible to tell whether differences such as 1.17 vs. 1.23 are meaningful.
  • GDM predicts changes relative to the previous adjacency, whereas the adapted baselines must reconstruct the whole adjacency from node embeddings; App. F.3 notes that they "struggle especially with static edges". The ablations suggest this difference explains much of the gain, thus it's hard to tell if/how much the rest of the architecture contributes.
Questions for authors
  • Suppose the baselines are given the same adjacency head as GDM, i.e., one that predicts edge changes relative to At−1A_{t-1}. How large is GDM's remaining advantage?
  • In SAR and CF, the target distribution is sampled with the hidden variables (e.g., ξ\xi in CF) fixed at their true values. Do the model rankings stay the same if the targets are instead sampled from the belief given the observed history?
2 comments

Thank you for your careful review and recognition of the contributions of our work. Please see below for our responses to your concerns.

W1: Evaluation under partial observability

The goal of our evaluation is to measure how accurately a world model predicts the true transition distribution, including when the environment is partially observable. This is why we sample the target distribution from the full simulator state, including unobserved variables. Different models may have different abilities to infer hidden state from the observation history, and we aim to evaluate how effectively they capture the resulting dynamics.

We acknowledge that this differs from evaluating the model's prediction against the belief distribution conditioned on the observation history. However, the true belief distribution is generally intractable to obtain. If a model that predicts the most likely outcome scores better than a model conditioned on the belief, then it indicates that the domain is either very simple or that the observations are not informative. We therefore respectfully disagree that using the true simulator state undermines the comparison. Rather, it provides a consistent reference against which to evaluate the predictions of all models.

W2: Interpretability of GDD

We acknowledge that GDD is less directly interpretable than conventional prediction error metrics, as discussed in Section 7. Unfortunately, there is a trade-off between constructing a metric which captures the full joint distribution of graph states and one whose numerical values have a simple interpretation. This arises from the fact that the problem is inherently multi-objective, and several considerations need to be collapsed to a single number.

The advantage of GDD is that, by using a characteristic kernel, it is zero iff the predicted distribution matches the true distribution. To provide additional context for interpreting the scores, we have added a simple baseline which copies the previous observation, including the topology, node and graph features, reward, and continuation signal. This provides a reference for assessing the predictive performance of the learned models relative to a naive predictor, helping build some intuition about the GDD values.

The results can be found in Table 1 and Figures 5, 6 in the paper. This baseline demonstrates that the deterministic RGC environment is simple and changes slowly, making the naive method very strong compared to error-prone learned baselines. Conversely, partially observable environments are not captured well by the naive baseline. Please see our response to Reviewer JJ7U for further discussion.

W3: Contribution of recurrent adjacency prediction

We agree that conditioning adjacency predictions on the previous adjacency is a major contributor to GDM's performance. Indeed, this is one of the primary innovations of our work. Existing graph world models either do not incorporate the adjacency into the recurrent dynamics or attempt to reconstruct it from node embeddings without explicitly accounting for the persistence of edges. Our work identifies this limitation and demonstrates the importance of modelling topology updates explicitly.

To further isolate this contribution, we have implemented new variants of the GWM baselines equipped with the same delta-based adjacency prediction head as GDM. These variants were not part of the original methods, and their implementation provides a more direct comparison of the remaining architectural differences. We have updated Table 1 and Figures 5, 6 in the manuscript to include these new variants.

The results show several interesting patterns across environments:

  • RGC: The modified GWM baselines improve substantially and outperform GDM. This is unsurprising in our opinion given that RGC is deterministic and fully observable, making it better-suited to the state-space formulation of GWM. Additionally, the strong performance of the trivial baseline mentioned above in the response to W2 (which simply copies the previous observation) contextualises the poor performance of all learning methods.
  • OD: GDM retains an advantage at graph sizes closer to the training distribution, while the modified Vanilla GWM baseline achieves similar performance to GDM at very large sizes. However, at these sizes, all learned models are outperformed by the naive copy baseline, suggesting limitations in their ability to generalise the dynamics to substantially larger graphs.
  • SAR: The modified baselines improve considerably over the original methods but do not outperform GDM. In particular, they appear to struggle with accurately modelling topology changes at larger graph sizes, showing that GDM retains architectural advantages beyond the recurrent adjacency prediction mechanism.
  • CF: The modified baselines also improve, with modified Vanilla GWM outperforming GDM at out-of-distribution graph sizes. This suggests that certain aspects of the CF dynamics may interact unfavourably with GDM's architecture as graph size increases, while being better captured by the GWM formulation.

Overall, our results highlight the importance of explicitly modelling recurrent adjacency updates, while also demonstrating that the remaining components of GDM provide benefits in stochastic and partially observable environments. In particular, the results on SAR show that simply equipping an existing GWM with the same adjacency update mechanism is insufficient to match GDM's performance. Nevertheless, the results also highlight limitations in size generalisation for certain environments, which we intend to investigate in future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.