acceptodds
Under review as a conference paper at ICLR 2027

WorldGraph: Graph-Native World Modeling

Abstract

World models infer latent states of an environment to capture its underlying dynamics and predict future evolution. Many real-world environments, however, are inherently relational and observed as evolving graphs, where entities, relations, and their properties change over time. Prior graph-related world models use graph structures to organize internal states or support task-specific reasoning, rather than treating an evolving graph itself as the modeled world. We instead study graph world modeling (GWM), where graph evolution itself constitutes the world dynamics. We formulate graph world modeling over observed graph evolution, latent graph states, and heterogeneous graph-transition predictions. Based on this formulation, we construct GWM-Zero, a benchmark covering node-, edge-, and graph-level transitions over eight temporal graph datasets. We propose WorldGraph, which combines a state-aware graph transformer for multi-granularity structural and transition-conditioned evolution modeling with transition-aware GRPO using dynamic grouping and structure-aware verifiable rewards. Extensive experiments on GWM-Zero show that WorldGraph consistently outperforms representative graph representation, temporal graph learning, graph pretraining, and graph world-model baselines across all three transition granularities.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
World Models, Graph Representation Learning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_vNJxOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses temporal graph learning. It proposes WorldGraph, a method inspired by world models that model temporal graph learning as heterogeneous graph-transition prediction: the goal is to predict the evolution of the temporal graph as a whole, including node-, edge-, and graph-level transitions. The approach has two main parts: a state model and a transition model. The state model uses a graph transformer backbone that encodes graph topology and prior evolution into a latent world state. Conditioned on that latent state, the transition model predicts the next graph transition via reinforcement learning.

Critical strengths
  • WorldGraph’s effectiveness is supported by both theoretical analysis and experiments on eight datasets. The empirical results demonstrate clear gains over baselines on node-, edge-, and graph-level tasks.

  • The paper proposes a novel world-model paradigm for temporal graph learning.

  • Whereas most existing temporal graph methods target a single task type (link prediction only, node classification only, or graph-level prediction only), WorldGraph addresses all three and outperforms the baselines on each.

Critical weaknesses
  • Several design choices, such as the node importance score and the pooling function, appear cherry-picked without sufficient justification. See the questions below.

  • The main text and the appendix feel disconnected. For example, Section 4.2 (experimental setup) does not describe task formulation; readers must use the table of contents and infer which appendix section has that detail. Explicit pointers from the main text to the relevant appendix sections would help connect the two.

Questions for authors
  • Could the authors report the frequency distribution of predicted transitions? Is there a dominant transition among all available transition types?

  • At timestamp tt , can WorldGraph predict interactions involving new nodes (nodes that have not appeared before tt), links among new nodes and links between new and existing nodes?

  • In Stage 1 (multi-granularity graph encoder), how effective are hop-based message passing and random-walk sampling for structural representations that support different graph transitions? Could the authors add an ablation on each component’s contribution to performance across transition types?

  • In Stage 1, WorldGraph uses mean pooling for multi-granularity attention fusion. Could the authors justify this choice versus median, sum, or attention pooling?

  • Lines 250–253: group assignment at time tt is biased toward rare historical transitions. How much does this affect performance on high-frequency transitions? In settings where ground truth is dominated by frequent transition types, is overall performance harmed by this bias?

  • Will B\mathcal{B} be fixed or adaptive? How would B\mathcal{B}adapt when the number of transitions per timestamp grows or shrinks over time (common in real networks, e.g., more activity as a network becomes more popular)? A fixed B\mathcal{B} might lead to over- or under-prediction of transitions.

  • In structure-aware reward design, node importance uses node degree. Could the authors justify this choice? Degree does not always reflect importance; other measures (e.g., centrality) might also be relevant.

  • Could the authors report transition-type frequencies for each evaluation dataset? Do these datasets share similar dominant transitions by frequency?

4 comments
AuthorsOpenReview ↗

Response to Weakness 1, Weakness 2, Question 4, and Question 7

Response to Weakness 1 and Question 4 (Pooling Function):

Thank you for your suggestions.

We compared mean pooling with median, sum, and attention pooling in terms of both predictive performance and computational efficiency to justify this design choice.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
WorldGraph(Median Pooling)0.9487 ± 0.02220.6587 ± 0.01370.7373 ± 0.00600.6437 ± 0.0027
WorldGraph(Sum Pooling)0.9252 ± 0.04910.6320 ± 0.06580.7327 ± 0.00650.6315 ± 0.0130
WorldGraph(Attention Pooling)0.9690 ± 0.01050.6566 ± 0.01750.7380 ± 0.00400.6435 ± 0.0012
WorldGraph(Mean Pooling)0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Edge-Level Tasks / UN Vote

MethodAdd. F1 ↑Rem. F1 ↑Macro-F1 ↑
WorldGraph(Median Pooling)0.3954 ± 0.01080.5886 ± 0.01680.4920 ± 0.0030
WorldGraph(Sum Pooling)0.3801 ± 0.01020.5595 ± 0.00970.4698 ± 0.0003
WorldGraph(Attention Pooling)0.3846 ± 0.03940.6043 ± 0.04040.4945 ± 0.0005
WorldGraph(Mean Pooling)0.4165 ± 0.00950.5996 ± 0.02190.5080 ± 0.0071

Graph-Level Tasks / Contact

MethodMAE ↓RMSE ↓Macro-F1 ↑
WorldGraph(Median Pooling)0.5801 ± 0.00100.9109 ± 0.00350.5466 ± 0.0024
WorldGraph(Sum Pooling)0.6138 ± 0.00450.9221 ± 0.00090.5380 ± 0.0046
WorldGraph(Attention Pooling)0.5611 ± 0.00780.8858 ± 0.01230.5504 ± 0.0002
WorldGraph(Mean Pooling)0.5540 ± 0.00290.8865 ± 0.00420.5547 ± 0.0090

Runtime analysis: We keep the real input features fixed for each dataset, repeat the combined forward and backward passes 100 times for each of the four pooling methods, and report the GPU execution time per call as mean ± sample standard deviation in milliseconds (ms).

MethodNode-Level Tasks / TGBN-TradeEdge-Level Tasks / UN VoteGraph-Level Tasks / Contact
WorldGraph(Median Pooling)0.0460 ± 0.00160.0514 ± 0.00090.0491 ± 0.0013
WorldGraph(Sum Pooling)0.0053 ± 0.00110.0125 ± 0.00440.0082 ± 0.0020
WorldGraph(Attention Pooling)0.0181 ± 0.00070.0227 ± 0.00040.0215 ± 0.0006
WorldGraph(Mean Pooling)0.0056 ± 0.00120.0127 ± 0.00450.0083 ± 0.0020

Overall, Mean Pooling achieves the strongest predictive performance while maintaining low computational overhead, offering a good balance between performance and efficiency. Sum Pooling is slightly faster but yields lower predictive performance, while Attention Pooling achieves competitive performance but is slower.

We have added these experiments in Appendix H.11 (lines 2247-2294) of the revised manuscript.

Response to Weakness 1 and Question 7 (Node Importance):

Thank you for your advice.

We compared node degree with PageRank centrality in terms of both predictive performance and computational efficiency to justify our choice of node importance measure.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
WorldGraph (PageRank Centrality)0.9713 ± 0.01390.6667 ± 0.00000.7346 ± 0.00410.6412 ± 0.0070
WorldGraph (Node Degree)0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Edge-Level Tasks / UN Vote

MethodAdd. F1 ↑Rem. F1 ↑Macro-F1 ↑
WorldGraph (PageRank Centrality)0.3935 ± 0.00560.6108 ± 0.01400.5022 ± 0.0098
WorldGraph (Node Degree)0.4165 ± 0.00950.5996 ± 0.02190.5080 ± 0.0071

Graph-Level Tasks / Contact

MethodMAE ↓RMSE ↓Macro-F1 ↑
WorldGraph (PageRank Centrality)0.5661 ± 0.00470.8949 ± 0.00180.5557 ± 0.0013
WorldGraph (Node Degree)0.5540 ± 0.00290.8865 ± 0.00420.5547 ± 0.0090

Runtime analysis: We compute importance weights using node degree and PageRank on the same current graph, repeat each computation 100 times, and synchronize the GPU before and after each timed computation. The table below reports the mean runtime per computation in milliseconds (ms).

MethodNode-Level Tasks / TGBN-TradeEdge-Level Tasks / UN VoteGraph-Level Tasks / Contact
PageRank Centrality6.166.446.98
Node Degree3.243.103.56

Overall, the two methods achieve similar predictive performance, but PageRank incurs higher computational overhead, with per-computation runtime up to approximately 2.08 times that of node degree.

We have added these experiments in Appendix H.12 (lines 2295-2338) of the revised manuscript.

Response to Weakness 2 (Explicit References to the Appendix):

Thank you for your advice. We have added explicit pointers from the main text in the revised manuscript.

AuthorsOpenReview ↗

Response to Question 1 and Question 8 (Transition-Type Frequency Distributions Across Datasets):

Response to Question 1 and Question 8 (Transition-Type Frequency Distributions Across Datasets):

Thank you for your advice. We reported the ground-truth transition-type frequencies alongside predictions from WorldGraph and the top three baselines in the papers (GraphGPS, TGN, and TIDFormer) for each evaluation dataset.

Node-Level Tasks / TGBN-Trade

MethodAdd NodeRemove NodeModify Property
Ground Truth0.14360.05850.7979
GraphGPS0.13300.01250.8545
TGN0.08610.01070.9032
TIDFormer0.09530.05580.8489
WorldGraph0.12870.05670.8145

Node-Level Tasks / TGBN-Genre

MethodAdd NodeRemove NodeModify Property
Ground Truth0.36340.36840.2683
GraphGPS0.24570.36760.3866
TGN0.23850.37810.3834
TIDFormer0.24150.36040.3982
WorldGraph0.25130.39300.3557

Node-Level Tasks / TGBN-Reddit

MethodAdd NodeRemove NodeModify Property
Ground Truth0.34390.34720.3089
GraphGPS0.30970.28930.4010
TGN0.31040.29190.3977
TIDFormer0.30800.28380.4082
WorldGraph0.31170.29400.3942

Edge-Level Tasks / TGBN-Trade

MethodAdd EdgeRemove Edge
Ground Truth0.52070.4793
GraphGPS0.49910.5009
TGN0.51530.4847
TIDFormer0.55140.4486
WorldGraph0.51680.4832

Edge-Level Tasks / UN Vote

MethodAdd EdgeRemove Edge
Ground Truth0.52530.4747
GraphGPS0.43360.5664
TGN0.39900.6010
TIDFormer0.63100.3690
WorldGraph0.54570.4543

Edge-Level Tasks / Contact

MethodAdd EdgeRemove Edge
Ground Truth0.46100.5390
GraphGPS0.74570.2543
TGN0.50960.4904
TIDFormer0.50630.4937
WorldGraph0.44100.5590

Edge-Level Tasks / SocialEvo

MethodAdd EdgeRemove Edge
Ground Truth0.48210.5179
GraphGPS0.67230.3277
TGN0.61260.3874
TIDFormer0.60840.3916
WorldGraph0.50410.4959

Graph-Level Tasks / Flights

MethodAdd NodeRemove NodeAdd EdgeRemove Edge
Ground Truth0.08780.08810.41220.4119
GraphGPS0.09470.16310.33380.4084
TGN0.13110.12540.36550.3780
TIDFormer0.08530.09340.36020.4611
WorldGraph0.07830.11310.35680.4518

Graph-Level Tasks / Contact

MethodAdd NodeRemove NodeAdd EdgeRemove Edge
Ground Truth0.04010.04740.39780.5147
GraphGPS0.07340.07110.37060.4849
TGN0.03970.02270.40330.5343
TIDFormer0.03830.06400.32900.5687
WorldGraph0.03720.04880.34600.5680

Graph-Level Tasks / Enron

MethodAdd NodeRemove NodeAdd EdgeRemove Edge
Ground Truth0.13350.19390.34820.3244
GraphGPS0.12870.01660.56980.2850
TGN0.14360.01670.57600.2637
TIDFormer0.16310.01190.62890.1961
WorldGraph0.13580.05710.48570.3214

The ground-truth distributions vary across datasets.

In Node-Level Tasks / TGBN-Trade, Modify Property events clearly dominate, accounting for approximately 79.79% of transitions.

In Graph-Level Tasks / Flights and Graph-Level Tasks / Contact, Add Edge and Remove Edge events jointly account for approximately 82.41% and 91.25%, respectively.

The remaining datasets exhibit comparatively more balanced distributions across their available transition types.

To quantify the agreement between predicted and ground-truth distributions, the following table reports KL(Ground Truth∥Prediction) as mean ± sample standard deviation across runs. Lower values indicate closer alignment with the ground-truth distribution of transition types.

MethodNode-Level Tasks / TGBN-TradeNode-Level Tasks / TGBN-GenreNode-Level Tasks / TGBN-RedditEdge-Level Tasks / TGBN-TradeEdge-Level Tasks / UN VoteEdge-Level Tasks / ContactEdge-Level Tasks / SocialEvoGraph-Level Tasks / FlightsGraph-Level Tasks / ContactGraph-Level Tasks / Enron
GraphGPS0.0504 ± 0.00680.0449 ± 0.00140.0188 ± 0.00040.0010 ± 0.00080.0171 ± 0.00500.2767 ± 0.32480.0878 ± 0.07580.0298 ± 0.00850.0257 ± 0.01380.3576 ± 0.0587
TGN0.0988 ± 0.00750.0476 ± 0.00060.0174 ± 0.00160.0012 ± 0.00070.0336 ± 0.01640.0228 ± 0.02630.0352 ± 0.00900.0189 ± 0.00450.0208 ± 0.00290.3639 ± 0.0090
TIDFormer0.0181 ± 0.00400.0511 ± 0.00120.0222 ± 0.00840.0020 ± 0.00110.0249 ± 0.01690.0047 ± 0.00440.0326 ± 0.00030.0214 ± 0.00300.0161 ± 0.00150.5253 ± 0.2548
WorldGraph0.0013 ± 0.00020.0346 ± 0.00010.0161 ± 0.00100.0001 ± 0.00010.0011 ± 0.00120.0011 ± 0.00150.0011 ± 0.00090.0105 ± 0.00480.0066 ± 0.00220.1297 ± 0.0506

We have added these experiments in Appendix H.13 (lines 2340-2477) of the revised manuscript.

AuthorsOpenReview ↗

Response to Question 2 (Interaction Prediction for Previously Unseen Nodes) and Question 3 (Component Ablations of the Multi-Granularity Graph Encoder)

Response to Question 2 (Interaction Prediction for Previously Unseen Nodes):

Thank you for your insightful advice. Since relatively few nodes first appear in the test split of the original dataset, we conducted an additional experiment using a node-holdout protocol to simulate previously unseen nodes. Specifically, we mask the historical information of a subset of nodes and their incident edges. Under this protocol, we compare WorldGraph with the strongest baseline, TGN, and report prediction performance separately for new–new and new–existing links.

Edge-Level Tasks / UN Vote

MethodNew–New F1 ↑New–Existing F1 ↑Combined F1 ↑
TGN0.0888 ± 0.01960.0919 ± 0.00830.0920 ± 0.0075
WorldGraph0.1033 ± 0.00020.1445 ± 0.00180.1421 ± 0.0017

These results suggest that WorldGraph can effectively predict interactions involving previously unseen nodes, including both new–new and new–existing links.

We have added these experiments in Appendix H.14 (lines 2478-2494) of the revised manuscript.

Response to Question 3 (Component Ablations of the Multi-Granularity Graph Encoder):

Thank you. We have conducted separate ablations of hop-based message passing and random-walk sampling on three datasets covering node-, edge-, and graph-level tasks. As shown below, removing either component results in lower mean performance across all reported metrics, suggesting that both components contribute useful structural information for modeling different graph transitions.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
w/o Hop-based Message Passing0.8520 ± 0.04990.5727 ± 0.06860.7271 ± 0.00750.6416 ± 0.0050
w/o Random-walk Sampling0.8648 ± 0.01320.5847 ± 0.03430.7346 ± 0.00450.6420 ± 0.0045
WorldGraph0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Edge-Level Tasks / UN Vote

MethodAdd. F1 ↑Rem. F1 ↑Macro-F1 ↑
w/o Hop-based Message Passing0.3924 ± 0.01460.5071 ± 0.04370.4497 ± 0.0236
w/o Random-walk Sampling0.3905 ± 0.01910.4982 ± 0.07660.4444 ± 0.0335
WorldGraph0.4165 ± 0.00950.5996 ± 0.02190.5080 ± 0.0071

Graph-Level Tasks / Contact

MethodMAE ↓RMSE ↓Macro-F1 ↑
w/o Hop-based Message Passing0.5620 ± 0.00660.8907 ± 0.00400.5289 ± 0.0073
w/o Random-walk Sampling0.5584 ± 0.01150.8879 ± 0.00940.5364 ± 0.0063
WorldGraph0.5540 ± 0.00290.8865 ± 0.00420.5547 ± 0.0090

We have added these experiments in Appendix H.15 (lines 2496-2526) of the revised manuscript.

AuthorsOpenReview ↗

Response to Question 5 (Impact of Rare-Transition Prioritization on Frequent Transitions) and Question 6 (Fixed versus Adaptive Rollout Budgets)

Response to Question 5 (Impact of Rare-Transition Prioritization on Frequent Transitions):

Thank you. We separately evaluated high- and low-frequency transition types on three datasets with imbalanced transition distributions, comparing WorldGraph with its variant without Transition-Aware Dynamic Group Sampling and TGN.

Node-Level Tasks / TGBN-Trade

According to the distribution in Q1: high-frequency type: Modify property (semantic change); low-frequency types: Add node and Remove node.

MethodHigh-frequency F1 ↑Low-frequency F1 ↑
TGN0.6666 ± 0.00850.4525 ± 0.0337
WorldGraph w/o Transition-Aware Dynamic Group Sampling0.7063 ± 0.01030.7061 ± 0.0239
WorldGraph0.7117 ± 0.01520.7838 ± 0.0130

Graph-Level Tasks / Flights

According to the distribution as shown in the response to Q1: high-frequency types: Add edge and Remove edge; low-frequency types: Add node and Remove node.

MethodHigh-frequency F1 ↑Low-frequency F1 ↑
TGN0.2966 ± 0.00020.5195 ± 0.0037
WorldGraph w/o Transition-Aware Dynamic Group Sampling0.3643 ± 0.02020.5246 ± 0.0152
WorldGraph0.3713 ± 0.03050.5425 ± 0.0144

Graph-Level Tasks / Contact

According to the distribution in Q1: high-frequency types: Add edge and Remove edge; low-frequency types: Add node and Remove node.

MethodHigh-frequency F1 ↑Low-frequency F1 ↑
TGN0.2690 ± 0.01450.4967 ± 0.0199
WorldGraph w/o Transition-Aware Dynamic Group Sampling0.3120 ± 0.03720.5270 ± 0.0234
WorldGraph0.3192 ± 0.01160.5729 ± 0.0032

As shown in the results, prioritizing rare transitions does not compromise predictive performance on high-frequency types, while substantially improving performance on low-frequency types. Furthermore, WorldGraph consistently outperforms the strongest baseline (TGN) across both high- and low-frequency categories, regardless of whether Transition-Aware Dynamic Group Sampling is enabled.

We have added these experiments in Appendix H.16 (lines 2529-2580) of the revised manuscript.

Response to Question 6 (Fixed versus Adaptive Rollout Budgets):

Thank you for your insightful advice.

In our default setting, we keep the total rollout budget fixed and dynamically allocate rollouts across transition types. This setting achieved state-of-the-art overall performance in our main experiments.

Our design naturally supports dynamic budget allocation. We use a lightweight MLP that adjusts the total rollout budget using current graph features and historical transition statistics. As shown below, the budget generally increases during periods with more transition events and decreases during less active periods, enabling adaptation to changing network activity. This extension aims to further improve predictive performance by matching the sampling effort to the anticipated transition volume.

Timestamp tNumber of Transition EventsActual Rollout Count
198771.0012.00
198971.4013.00
199186.0013.60
199392.0015.00
199587.0012.40
199796.0013.17
199994.0012.00
200177.0011.00
200368.0010.00
200559.009.00
200764.008.00

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
WorldGraph (Adaptive Budget)0.9712 ± 0.01830.6715 ± 0.02140.7372 ± 0.00300.6466 ± 0.0052
WorldGraph (Fixed Budget)0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

We have included this discussion in Appendix H.17 (lines 2582-2620) of the revised manuscript.

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

The paper frames graph world modeling as learning a latent state from a sequence of graph snapshots and predicting the next change at the node, edge and local-subgraph levels. It introduces the GWM-Zero benchmark, built from eight temporal-graph datasets, and proposes WorldGraph, which combines a history-aware graph encoder with an edit controller. The controller is trained by GRPO, with more rollouts allocated to rare transition types. Two theorems justify the encoder and the RL scheme, and experiments report gains over many baselines.

Critical strengths
  • Evaluating node-, edge- and local-structure changes within one benchmark is a useful idea.
  • Giving more training signal to rare transition types is a reasonable response to strongly imbalanced graph changes.
  • The paper compares against ten baselines from four model families.
Critical weaknesses
  • The theorems do not support the claims they are used for:
    • Theorem 2: The GRPO comparison gives WorldGraph more rollouts per group than standard GRPO), which may have bias and only shows that more samples reduce variance, not that rarity-based allocation helps under the same budget.
    • Theorem 1: Its key assumption, that each subgraph contributes identically across encoders, contradicts the softmax normalization in Eq. (9).
  • Because natural node additions and deletions are sparse, the authors add nodes whose past activity is rising or falling and mask them as "changes" (App. G.2). A history-aware model like WorldGraph may simply learn this construction rule. The paper reports no breakdown of natural versus constructed event.
  • WorldGraph is trained with an RL reward aligned with the F1 evaluation metric, while the baselines use ordinary supervised heads. The "w/o RL" ablation does not say what replaces RL. As a result, the improvements cannot be attributed to the proposed RL design rather than to metric-aligned training.
Questions for authors
  • What fraction of the node additions and deletions are natural, and what fraction are constructed by the activity-trend rule? How do WorldGraph and the baselines perform on natural changes alone?
  • How does WorldGraph compare when trained with an ordinary supervised loss, re-weighted by transition rarity, instead of GRPO?
  • With the same total number of rollouts, does rarity-based allocation still beat uniform allocation, in both accuracy and measured gradient variance?
3 comments
AuthorsOpenReview ↗

Response to Weakness 1 (Theorems 1 and 2) and Question 3:

Response to Weakness 1 (Theorems 1 and 2) and Question 3: Thank you for your comments.

For Theorem 2, in our design, we start with the same fixed number of rollouts per transition as in standard GRPO and supplement them with additional rollouts to increase diversity. As a result, transition-aware RL uses more rollouts overall than standard GRPO.

We additionally provide the experiments and theoretical analysis under the same total rollout budget.

Experiments: Values are reported as mean ± sample standard deviation. For node-level tasks, performance is computed for each run as the arithmetic mean of the four metrics reported in the paper: Add. F1, Rem. F1, Sem. F1, and NDCG@10. For edge-level tasks, performance is measured by Macro-F1. Lower EVR and higher performance are better.

Node-Level /TGBN-Genre(EVR)↓Node-Level /TGBN-Genre(Performance)↑Edge-Level /TGBN-Trade(EVR)↓Edge-Level /TGBN-Trade(Performance)↑
GRPO1.8567 ± 0.04430.6643 ± 0.00121.2050 ± 0.06600.4468 ± 0.0039
Transition-aware RL1.6110 ± 0.00780.6864 ± 0.00051.0548 ± 0.00670.4646 ± 0.0010

As shown above, under the same total rollout budget, rarity-based allocation achieves higher predictive performance and lower measured gradient variance than uniform allocation.

Theoretical Anlaysis: We added an analysis comparing rollout waste between GRPO and our method under the same rollout budget. The results show that our method produces more effective rollouts than GRPO.

Theorem 3 (Zero-advantage rollout waste under the same total budget).

Let ft(ρ)f_t(\rho) denote the expected number of rollouts wasted in zero-advantage groups under GRPO [3, 4], larger values indicate lower effective sample utilization. For integer allocations ρi=Bt(Ji)≥Ca≥2\rho_i=B_t(J_i)\ge C_a\ge2, ∑iρi=B\sum_i\rho_i=\mathcal{B}, and integer B/Kt\mathcal{B}/K_t, the total expected waste satisfies

\mathcal{W}(\boldsymbol{\rho}) &:=\sum_{i=1}^{K_t}f_t(\rho_i) \\ &\le K_t f_t(\mathcal{B}/K_t) =\mathcal{W}(\boldsymbol{\rho}^{\mathrm{GRPO}}), \end{aligned}$$ where $\rho_i^{\mathrm{GRPO}}=\mathcal{B}/K_t$. Uniform allocation uniquely maximizes this waste, and any feasible nonuniform WorldGraph allocation has strictly smaller waste. **Proof.** For the equal-budget analysis, we fix time $t$ and the observed history. We consider $K_t=|\mathcal{J}_t|\ge2$ groups with conditionally i.i.d. rewards within each group. Identical rewards yield zero advantages under GRPO normalization [3], including nonzero rewards [4]. Let $q_{t,i}(c)=\Pr(R=c\mid J_i)$. By conditional independence, the identical-reward probability at integer $\rho\ge2$, and its real-valued extension, are $$\chi_{t,i}(\rho)=\sum_{c:q_{t,i}(c)>0}q_{t,i}(c)^\rho.$$ The sum runs over reward atoms. In the common-function setting $\chi_{t,i}=\chi_t$, multiplying this probability by $\rho$ gives $f_t(\rho)$, and summing across groups gives $\mathcal{W}$. With the same total budget, we have $$\begin{aligned} \rho_i^{\mathrm{GRPO}} &= \frac{\mathcal{B}}{K_t}, \\ \rho_i^{\mathrm{OURS}} &= C_a+(\mathcal{B}-K_tC_a)\mathrm{Prob}(J_i)+\varepsilon_{t,i}, \end{aligned}$$ where $\varepsilon_{t,i}$ denotes largest-remainder rounding errors with $\sum_i\varepsilon_{t,i}=0$. Both allocations satisfy $C_a\le\rho_i\le\rho_{\max}=\mathcal{B}-(K_t-1)C_a$. By strict concavity of $f_t$ and Jensen's inequality, $$\begin{aligned} \mathcal{W}(\boldsymbol{\rho}) &=\sum_{i=1}^{K_t}f_t(\rho_i) \le K_t f_t\left(\frac{\mathcal{B}}{K_t}\right) \\ &=\mathcal{B}\chi_t(\mathcal{B}/K_t) =\mathcal{W}(\boldsymbol{\rho}^{\mathrm{GRPO}}). \end{aligned}$$ Equality holds if and only if every $\rho_i=\mathcal{B}/K_t$. Hence uniform allocation uniquely maximizes $\mathcal{W}$, and any nonuniform WorldGraph allocation strictly reduces this waste. $\square$ **Experimental validation of Theorem 3:** Under a fixed total rollout budget of 12, we repeatedly sample rollouts, count those belonging to groups with identical total rewards as wasted, and report the percentage of the budget wasted as mean ± sample standard deviation (%, lower is better). || Node-Level / TGBN-Trade | Graph-Level / Enron | | :-: | :-: | :-: | |GRPO|88.6667 ± 2.5142|25.3889 ± 0.1203| | **Transition-aware RL** |**59.1042 ± 3.8007**|**20.0833 ± 0.1964**| **For Theorem 1**, in **Equation 9**, we apply the weight bound ($\tilde{\alpha_i} \leq 1$) (as shown in line **1102** of the manuscript) to obtain an upper bound on the embedding. Therefore, the upper bound on the embedding expression takes the form of a sum. In the revised manuscript, we: (1) added the comparison between GRPO and our Transition-aware RL under the same rollout budget in **Appendix D.2** (**lines 1325-1344**); (2) added the theoretical comparison under the same rollout budget in **Theorem 3** (**lines 335-350**); and (3) added the experimental validation of **Theorem 3** in **Appendix D.3** (**lines 1335-1365**).
AuthorsOpenReview ↗

Response to Weakness 2 and Question 1

Response to Weakness 2 and Question 1: Thank you. We would like to respectfully point that our algorithm do not have access to the future-window activity statistics used to construct the labels. Therefore, the same heuristics are not implicitly exploited by our history encoder. Following prior work [1], our history encoder uses historical change frequencies solely as a predictive signal for future graph events.

We also conduct an experiment in which the baselines received the same historical change-frequency information as our method. The results are shown below.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
TGN0.8492 ± 0.07950.0559 ± 0.05150.6666 ± 0.00850.6181 ± 0.0117
TGN + History Statistics0.8471 ± 0.02720.0893 ± 0.01160.6848 ± 0.01520.6258 ± 0.0017
WorldGraph0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Our method still outperforms the augmented baselines, indicating that access to change-frequency information alone is insufficient to close the performance gap. This result supports the value of our overall design, which combines a graph transformer with RL.

We report below the proportions of naturally occurring and rule-constructed events separately for node additions and deletions, using all events in GWM-Zero and all events in the node-level tasks as the two denominators. The results show that naturally occurring events account for most of the evaluation set.

DenominatorNatural (%)Constructed Add (%)Constructed Remove (%)Constructed Total (%)
Node-Level Events83.938.068.0116.07
GWM-Zero Events92.403.813.797.60

We also evaluate WorldGraph and the best-performing baseline separately on naturally occurring changes and rule-constructed changes, as shown below.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
TGN0.5761 ± 0.14930.3414 ± 0.14540.6656 ± 0.01210.6469 ± 0.0017
WorldGraph0.8850 ± 0.05200.6540 ± 0.10290.7190 ± 0.00520.6518 ± 0.0061

Node-Level Tasks / Genre

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
TGN0.6673 ± 0.00430.8127 ± 0.00190.5888 ± 0.00040.3353 ± 0.0019
WorldGraph0.7162 ± 0.00650.8730 ± 0.00200.6294 ± 0.00090.4483 ± 0.0004

Node-Level Tasks / Reddit

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
TGN0.9581 ± 0.00210.9260 ± 0.00390.6160 ± 0.00080.3056 ± 0.0105
WorldGraph1.0000 ± 0.00001.0000 ± 0.00000.6210 ± 0.00410.4003 ± 0.0013

Average Absolute Improvements

TaskTypeAverage Gain
Node-Level TasksConstructed9.41%
Edge-Level TasksNatural15.62%
Graph-Level TasksNatural8.10%
Node-Level TasksNatural9.65%

On natural node-level tasks, WorldGraph achieves an average improvement of 9.65 percentage points over TGN, which is on par with the 9.41 percentage points gain on the rule-constructed node tasks. This improvement is also of a comparable magnitude to the gains observed on edge-level and graph-level tasks in our original manuscript, which inherently consist of naturally occurring events.

In the revised manuscript, we have added these experiments in Appendix H.5 (lines 1869-1935).

[1] Temporal Knowledge Graph Reasoning with Historical Contrastive Learning. AAAI 2023

AuthorsOpenReview ↗

Response to Weakness 3 and Question 2

Response to Weakness 3 and Question 2: Thank you for your comments. A graph world model learns how a graph evolves over time. In WorldGraph, the Controller predicts each graph transition by generating a sequence of edits. Errors can accumulate within this sequence. RL can mitigate this error accumulation by assigning rewards based on the completed outputs [2].

In the "w/o RL" ablation study, we directly remove the GRPO reinforcement learning updates and continue training the model solely with the original supervised prediction loss, without introducing any alternative algorithms or weighted losses.

We also evaluate the same WorldGraph architecture trained with (1) a transition rarity-weighted supervised loss (Rarity-Weighted SL) and (2) a metric-aligned supervised variant (Metric-aligned SL), where we remove reinforcement learning while retaining the original supervised loss, additionally incorporating a soft-F1 loss corresponding to the reward objective and a normalized MAE loss for regression tasks. The results are shown below:

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
Rarity-Weighted SL0.8343 ± 0.10860.4628 ± 0.07580.7303 ± 0.00550.6464 ± 0.0051
Metric-aligned SL0.8756 ± 0.04740.4609 ± 0.08610.7256 ± 0.00400.6454 ± 0.0042
WorldGraph0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Edge-Level Tasks / UN Vote

MethodAdd. F1 ↑Rem. F1 ↑Macro-F1 ↑
Rarity-Weighted SL0.3950 ± 0.01200.4935 ± 0.03650.4442 ± 0.0124
Metric-aligned SL0.3975 ± 0.01280.5289 ± 0.08180.4632 ± 0.0358
WorldGraph0.4165 ± 0.00950.5996 ± 0.02190.5080 ± 0.0071

Graph-Level Tasks / Contact

MethodMAE ↓RMSE ↓Macro-F1 ↑
Rarity-Weighted SL0.6024 ± 0.01460.9055 ± 0.00150.5218 ± 0.0037
Metric-aligned SL0.5937 ± 0.01010.9407 ± 0.00800.5380 ± 0.0013
WorldGraph0.5540 ± 0.00290.8865 ± 0.00420.5547 ± 0.0090

The model trained with our RL strategy outperforms both supervised variants, demonstrating the benefit of our RL strategy in this setting.

We added the analysis and corresponding experiments in Appendix H.10 (lines 2181-2245).

[2] Sequence Level Training with Recurrent Neural Networks. ICLR 2016

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

The paper introduces "graph world modeling" (GWM), the task of modeling an environment that is itself an evolving graph. A latent world state is inferred from the current snapshot and the previous change, and a transition model predicts the next graph change. Node-, edge- and graph-level prediction tasks are presented as different projections of the same transition. The contributions are: (i) the formulation and a benchmark, GWM-Zero, built from eight TGB / dynamic-graph datasets, with node addition/deletion/property change, edge addition/deletion, and change of local-subgraph statistics as targets; (ii) WorldGraph, which combines a "state-aware graph transformer" with a "transition-aware GRPO"; (iii) two theorems, one claiming a tighter deviation bound than SGFormer and one claiming a lower effective variance ratio than standard GRPO. Experiments on GWM-Zero report consistent gains over MPNNs, graph transformers, TGN/TIDFormer and pretrained graph models.

Critical strengths
  1. Unified multi-granularity evaluation. Treating node-, edge- and graph-level changes as observations of one transition, and building a benchmark that tests all three on the same datasets, is a reasonable and potentially useful framing for discrete-time dynamic graph prediction. If the benchmark construction were made transparent and the labels were natural, rather than partly synthetic (see weaknesses), GWM-Zero could be useful to the community independently of the proposed model.

  2. Broad empirical coverage. The paper compares against many families of baselines on eight datasets. It adds ablations, sensitivity studies, multi-step rollouts, an efficiency table and plug-in experiments in three existing world-model settings. The reported improvements are large and consistent across tables, which, if they hold up under a fair protocol, would be a meaningful result.

Critical weaknesses
  1. The theoretical results are close to vacuous and do not support the claims built on them.
  • Theorem 1 (App. C.1) models the node embedding as a sum over sampled subgraphs, assumes every ψ(gi)\psi(g_i) is bounded by the same constant CpC_p, and then compares (ζ−(Lmax+M))⋅Cp(\zeta − (L_max+M))\cdot C_p with (ζ−1)⋅Cp(\zeta − 1)\cdot C_p. The result says only that a method using more subgraphs has a smaller upper bound on the number of missing subgraphs. It does not depend on the architecture, on the attention, or on any property of the data, and a smaller upper bound says nothing about the actual deviation. It also contradicts Eq. 9, where the embedding is a softmax-weighted convex combination, not a sum. The "Lipschitz message function" assumption is not justified.
  • Theorem 2 compares a group size Ca+Prob(Ji)⋅BC_a + Prob(J_i)\cdot B with a group size CaC_a. In other words, the proposed method uses strictly more rollouts per group than the GRPO baseline it is compared with, so a lower variance follows trivially. The fair comparison is at a matched total rollout budget. These theorems are presented as contributions, so their weakness directly affects the paper's value.
  1. The experimental protocol does not convincingly establish the claimed gains.
  • Benchmark labels are partly synthetic and threshold-defined. Node additions and deletions are "supplemented" with nodes whose activity is rising or declining, by masking the node and its edges. This makes it hard to interpret the task as "world dynamics". It also needs to be checked that the same heuristics are not implicitly exploited by the proposed history encoder, which sees change frequencies.
  • The baselines appear under-tuned. It is unclear whether hyperparameter search budgets were comparable. Discrete-time dynamic GNNs that are the natural competitors for snapshot-to-snapshot prediction are missing.
  • No standard deviations or significance tests are given anywhere, although results are said to be averaged over five runs. The ablation uses only two datasets.

The positioning relative to the dynamic-graph-learning literature should be made more carefully.

Questions for authors

Clarifications:

  1. In Theorem 2 / App. D.2, is the total rollout budget the same for standard GRPO and transition-aware RL?
  2. Why is RL needed at all? All targets are fully observed, and the reward is a weighted F1/MAE against ground truth. What is the performance of the same architecture trained with a supervised, importance-weighted loss? This is the most informative missing ablation.
  3. How were baseline hyperparameters tuned, and what is the variance over the five runs ?

Suggestions (would strengthen the paper, not necessarily required): 4. Add discrete-time dynamic-graph baselines (EvolveGCN, ROLAND, WinGNN, DyGFormer through DyGLib) and report significance across seeds. 5. Either substantially strengthen Theorems 1–2 or reframe them as informal motivation.

9 comments
AuthorsOpenReview ↗

Response to Weakness 1 (Theorem 1)

Response to Weakness 1 (Theorem 1): Thank you for your comments.

In Theorem 1, we compare WorldGraph with other methods primarily in terms of their sampling mechanisms, following prior work [1] that evaluates model quality by analyzing sampled subgraphs. Therefore, the smaller upper bound gives our sampling mechanism a stronger theoretical guarantee on the deviation. In Table 5 of the appendix, our experiments also show that our sampling mechanism yields lower deviations in practice.

For Equation 9, we apply the weight bound (αi~≤1\tilde{\alpha_i} \leq 1) (as shown in line 1211 of the manuscript) to obtain an upper bound on the embedding. Therefore, the upper bound on the embedding expression takes the form of a sum.

The "Lipschitz" assumption is widely used in existing works [2]. To evaluate the validity of the Lipschitz message function assumption, we examine whether variations in the hidden states remain bounded when small perturbations are introduced to the structural representations. This assumption requires the existence of a finite constant CLC_L such that the change in the output does not exceed CLC_L times the change in the input.

In our experiments, we perturb the current structural representation zv,t\mathbf z_{v,t} of a single node at a time along a random unit direction ξ\boldsymbol{\xi}:

= \varepsilon_{\mathrm{pert}} \max\left(\lVert\mathbf{z}_{v,t}\rVert_2, 1\right) \boldsymbol{\xi}, \qquad \lVert\boldsymbol{\xi}\rVert_2 = 1, \quad \varepsilon_{\mathrm{pert}} \in \lbrace 10^{-4}, 10^{-3}, 10^{-2}, 10^{-1} \rbrace.$$ Subsequently, we compute the hidden states corresponding to the original and perturbed representations, respectively, and record the variation ratio: $$r = \frac{\lVert \mathcal{F}(\mathbf{z}_{v,t} + \Delta\mathbf{z}_{v,t}) - \mathcal{F}(\mathbf{z}_{v,t}) \rVert_{2}}{\lVert \Delta\mathbf{z}_{v,t} \rVert_{2}}.$$ For each independent evaluation, we first take the maximum ratio across all tested perturbations, and then report the mean ± sample standard deviation of these maximum values. | Dataset | Maximum ratio (mean ± standard deviation) | | :---------------------: | :---------------------------------------: | | Node-Level / TGBN-Trade | 0.8432 ± 0.0905 | | Edge-Level / UN Vote | 1.0909 ± 0.6105 | | Graph-Level / Flights | 0.8377 ± 0.3164 | Across the three datasets, the average maximum amplification ratios observed are 0.8432, 1.0909, and 0.8377, respectively, indicating that the output variations do not drastically amplify the input perturbations. This confirms the input-output stability of the message mapping within the evaluated regime, providing empirical support for adopting the Lipschitz message function assumption. In the revised manuscript, we have include the validation of the Lipschitz assumption in **Appendix D (lines 1312-1390)**. [1] LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence. ICLR 2023 [2] On the Stability of Expressive Positional Encodings for Graphs. ICLR 2024
AuthorsOpenReview ↗

Response to Weakness 1 (Theorem 2), Clarifications 1 and 5

Response to Weakness 1 (Theorem 2), Clarifications 1 and 5:

Thank you for your comments.

In our design, we start with the same fixed number of rollouts per transition as in standard GRPO and supplement them with additional rollouts to increase diversity. As a result, transition-aware RL uses more rollouts overall than standard GRPO.

We have added theoretical and empirical comparisons between our transition-aware RL method and standard GRPO under the same rollout budget, as shown below.

Values are reported as Mean EVR ↓ (mean ± sample standard deviation).

MethodNode-Level Tasks / TGBN-GenreEdge-Level Tasks / TGBN-Trade
Standard GRPO1.8567 ± 0.04431.2050 ± 0.0660
Transition-aware RL1.6110 ± 0.00781.0548 ± 0.0067

More Theoretical Analysis:

We added an analysis comparing rollout waste between GRPO and our method under the same rollout budget. The results show that our method produces more effective rollouts than GRPO.

Theorem 3 (Zero-advantage rollout waste under the same total budget).

Let ft(ρ)f_t(\rho) denote the expected number of rollouts wasted in zero-advantage groups under GRPO [3, 4], larger values indicate lower effective sample utilization. For integer allocations ρi=Bt(Ji)≥Ca≥2\rho_i=B_t(J_i)\ge C_a\ge2, ∑iρi=B\sum_i\rho_i=\mathcal{B}, and integer B/Kt\mathcal{B}/K_t, the total expected waste satisfies

\mathcal{W}(\boldsymbol{\rho}) &:=\sum_{i=1}^{K_t}f_t(\rho_i) \\ &\le K_t f_t(\mathcal{B}/K_t) =\mathcal{W}(\boldsymbol{\rho}^{\mathrm{GRPO}}), \end{aligned}$$ where $\rho_i^{\mathrm{GRPO}}=\mathcal{B}/K_t$. Uniform allocation uniquely maximizes this waste, and any feasible nonuniform WorldGraph allocation has strictly smaller waste. **Proof.** For the equal-budget analysis, we fix time $t$ and the observed history. We consider $K_t=|\mathcal{J}_t|\ge2$ groups with conditionally i.i.d. rewards within each group. Identical rewards yield zero advantages under GRPO normalization [3], including nonzero rewards [4]. Let $q_{t,i}(c)=\Pr(R=c\mid J_i)$. By conditional independence, the identical-reward probability at integer $\rho\ge2$, and its real-valued extension, are $$\chi_{t,i}(\rho)=\sum_{c:q_{t,i}(c)>0}q_{t,i}(c)^\rho.$$ The sum runs over reward atoms. In the common-function setting $\chi_{t,i}=\chi_t$, multiplying this probability by $\rho$ gives $f_t(\rho)$, and summing across groups gives $\mathcal{W}$. With the same total budget, we have $$\begin{aligned} \rho_i^{\mathrm{GRPO}} &= \frac{\mathcal{B}}{K_t}, \\ \rho_i^{\mathrm{OURS}} &= C_a+(\mathcal{B}-K_tC_a)\mathrm{Prob}(J_i)+\varepsilon_{t,i}, \end{aligned}$$ where $\varepsilon_{t,i}$ denotes largest-remainder rounding errors with $\sum_i\varepsilon_{t,i}=0$. Both allocations satisfy $C_a\le\rho_i\le\rho_{\max}=\mathcal{B}-(K_t-1)C_a$. By strict concavity of $f_t$ and Jensen's inequality, $$\begin{aligned} \mathcal{W}(\boldsymbol{\rho}) &=\sum_{i=1}^{K_t}f_t(\rho_i) \le K_t f_t\left(\frac{\mathcal{B}}{K_t}\right) \\ &=\mathcal{B}\chi_t(\mathcal{B}/K_t) =\mathcal{W}(\boldsymbol{\rho}^{\mathrm{GRPO}}). \end{aligned}$$ Equality holds if and only if every $\rho_i=\mathcal{B}/K_t$. Hence uniform allocation uniquely maximizes $\mathcal{W}$, and any nonuniform WorldGraph allocation strictly reduces this waste. $\square$ [3] DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arXiv 2024 [4] DAPO: An Open-Source LLM Reinforcement Learning System at Scale. NeurIPS 2026 **Experimental validation of Theorem 3:** Under a fixed total rollout budget of 12, we repeatedly sample rollouts, count those belonging to groups with identical total rewards as wasted, and report the percentage of the budget wasted as mean ± sample standard deviation (%, lower is better). | Method | Node-Level Tasks / TGBN-Trade | Graph-Level Tasks / Enron | | :---------------------: | :---------------------------: | :-----------------------: | | Standard GRPO | 88.6667 ± 2.5142 | 25.3889 ± 0.1203 | | **Transition-aware RL** | **59.1042 ± 3.8007** | **20.0833 ± 0.1964** | In the revised manuscript, we: (1) added the comparison between GRPO and our Transition-aware RL under the same rollout budget in **Appendix D.2** (**lines 1325-1344**); (2) added the theoretical comparison under the same rollout budget in **Theorem 3** (**lines 335-350**); and (3) added the experimental validation of **Theorem 3** in **Appendix D.3** (**lines 1335-1365**).
AuthorsOpenReview ↗

Response to Weakness 2.1

Response to Weakness 2.1: Thank you for your advice.

We include node addition and deletion as prediction tasks to capture how entities enter and leave real-world.

For example, in a communication network, predicting node addition means forecasting when a newly deployed device will come online and connect to the network. Predicting node deletion means forecasting when an existing device will go offline and stop communicating with other devices.

Because existing temporal graph datasets provide limited coverage of node addition and deletion events, we use node activity thresholds to generate synthetic examples of these events.

We would like to respectfully point that our algorithm do not have access to the future-window activity statistics used to construct the labels. Therefore, the same heuristics are not implicitly exploited by our history encoder. Following prior work [5], our history encoder uses historical change frequencies solely as a predictive signal for future graph events.

We additionally provide an additional experiment in which we provided the baselines with the same historical change-frequency information used by our method. The results are shown below.

Node-Level Tasks / TGBN-Trade

MethodAdd. F1 ↑Rem. F1 ↑Sem. F1 ↑NDCG@10 ↑
TGN0.8492 ± 0.07950.0559 ± 0.05150.6666 ± 0.00850.6181 ± 0.0117
TGN + History Statistics0.8471 ± 0.02720.0893 ± 0.01160.6848 ± 0.01520.6258 ± 0.0017
WorldGraph0.9696 ± 0.01050.6606 ± 0.01360.7354 ± 0.00750.6469 ± 0.0023

Our method still outperforms the augmented baselines, indicating that access to change-frequency information alone is insufficient to close the performance gap. This result supports the value of our overall design, which combines a graph transformer with RL.

In the revised manuscript, we have added these experiments in Appendix H.5 (lines 1869-1899).

[5] Temporal Knowledge Graph Reasoning with Historical Contrastive Learning. AAAI 2023

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

The paper propose the problem of predicting changes in dynamic graphs. That is, we have a sequence of graphs, where consecutive graphs differer by adding/removing nodes/edges or changing node embeddings. We want to predict the next graph in the sequence (equivalently to predict the changes). Models which do so are called graph world models (GWM).

Two challenges fro GWM: 1) actually remembering the history, not only current graph 2) be able to catch rare but structurally important changes.

For solving 1) the paper introduces the world-state s, which is a vector summarizing the current graph and all previous history. For solving 2) the paper uses dynamic grouping which allow to focus more on rare changes. The proposed model is state-aware graph transformer called WorldGraph.

Paper proposes a benchmark GWM-Zero, which is a combination of several previously existing benchmarks (grouped as node-level, edge-level and graph-level). These benchmarks (like TGBNTrade) have a natural interpretation as graphs changing with time.

Experiments show that WorldGraph outperforms all previous methods on these benchmarks, including methods specifically used for time-stamped interactions, like TGN and TIDFormer

Critical strengths

The paper proposes an interesting framework for studying graphs that change with time. The proposed method outperforms existing methods on several benchmarks.

Critical weaknesses

The exposition is sometimes hard to follow. Also, the motivation is not immediately clear - maybe including in the introduction some informal description of the datasets and what is predicted could help with that (we have data on all previous transactions; we aim to predict all transactions that will happen in the next hour).

Questions for authors

For me the term "heterogeneous transitions" is somewhat confusing. Why we need to specify that the transition is "heterogeneous"? Are there non-heterogeneous transitions?

2 comments
AuthorsOpenReview ↗

Response to Weakness and Question

Response to Weakness: We appreciate your advice. Below, we provide a detailed description of the datasets.

In the Contact dataset, nodes represent people and edges represent contacts between them. Given historical contact records, we aim to predict which pairs of people will form new contacts six hours later, which existing contacts will have disappeared by then, and whether each person’s local contact network will have become denser or sparser. This requires the model to capture both the current network structure and the patterns in how it has evolved over time.

In the revised manuscript, we have added this description in the introduction (lines 33-38) to better motivate our work.

Response to Question:

Sorry for the confusion. In this paper, “heterogeneous transitions” refer to different types of graph changes, such as node additions, node deletions, edge additions, edge deletions, and attribute modifications. The term describes the diversity of change operations and is independent of whether the input graph contains multiple node or relation types. A setting involving only one type of change, such as predicting edge additions alone, can be regarded as a single-type, or “homogeneous,” transition setting.

We model transitions as heterogeneous so that the model can handle more complex scenarios and better capture how the world evolves over time.

In the revised manuscript, we have added definitions of heterogeneous and homogeneous transitions in footnote 1 (lines 105-107).

Thank you for your response. I will keep my score unchanged for now while I follow the rest of the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.