PaperlayerView exact revision on arXiv

Source-linked AI summary

WorldGraph: Graph-Native World Modeling

Zezhong Ding, Yipeng Li, Xike Xie

arXiv:2609.34159v1cs.LGcs.AIcs.CV

TL;DR

Many environments are relational and observed as evolving graphs, but prior graph-related world models generally use graphs as auxiliary structures rather than modeling graph evolution itself. This paper formulates graph world modeling, introduces GWM-Zero and WorldGraph, and reports consistent gains across three transition granularities, including a 10.77% average model-quality improvement over the strongest baselines.

  • Problem

    Prior graph-related world models use graphs as auxiliary structures, while evolving-graph environments call for modeling graph evolution and heterogeneous transitions as the world dynamics.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces GWM-Zero across eight temporal graph datasets and WorldGraph, which combines a state-aware graph transformer with transition-aware GRPO.

    Source: §1 · p. 2

  • Results

    10.77% average model-quality improvement over the strongest baselines; WorldGraph consistently performs better across node-, edge-, and graph-level transition tasks.

    Source: §1 · p. 2, §5 · p. 10

  • Takeaways & Limitations

    WorldGraph provides a unified framework for graph-native world modeling across node-, edge-, and graph-level transitions.

    Source: §5 · p. 10

    The paper presents an initial conceptualization and says further work is needed to better integrate information from diverse modalities.

    Source: §K.1 · p. 32

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper frames graph world modeling around environments observed as evolving graphs, where graph evolution itself is the prediction target. It introduces GWM-Zero and WorldGraph to address state and heterogeneous-transition modeling, and reports improved benchmark performance.

1 INTRODUCTION

  • Graph world models maintain a latent state of graph evolution and predict heterogeneous transitions across node, edge, and graph levels.These levels are observable projections of the same graph-world dynamics, unlike predefined downstream tasks in typical dynamic graph learning.Source: §1 · p. 2
  • A general graph world state must capture multi-scale structure and historical dynamics, while transition modeling must account for frequency imbalance and structural relevance.The paper notes that rare changes involving structurally important entities may substantially affect subsequent evolution.Source: §1 · p. 2
  • WorldGraph combines a state-aware graph transformer with transition-aware GRPO, using dynamic grouping and structure-aware verifiable rewards.The transformer integrates multi-granularity structural context with preceding transitions; dynamic grouping allocates more training signal to rare transitions.Source: §1 · p. 2
  • WorldGraph improves average model quality by 10.77% over the strongest baselines, with a 50.66% F1 improvement on TGBN-Trade.The paper reports the largest improvement on TGBN-Trade (Huang et al., 2023).Source: §1 · p. 2
  • GWM-Zero covers node-, edge-, and graph-level transition prediction across eight graph datasets.The paper treats evolving graphs as the world itself, unlike prior work that uses graphs as auxiliary structures for planning, representation, or reasoning [1].Source: §1 · pp. 1–2

2 PROBLEM FORMULATION

The formulation represents an evolving graph as observed graph states paired with their changes, then introduces a latent state to summarize structure and prior evolution. It treats node-, edge-, and graph-level predictions as projections of the same transition.

2 PROBLEM FORMULATION

  • An observed graph state comprises entities, relations, and their associated properties, and a transition change may include additions, deletions, or property updates.The evolving graph is represented as a sequence of graph states and associated changes.Source: §2 · p. 3
  • The latent world state summarizes the current graph structure and preceding evolution, and the state and transition models infer that state and predict subsequent graph changes.The state model takes the current graph, preceding change, and previous world state; the transition model predicts the next change from the current graph, preceding change, and inferred state.Source: §2 · p. 3
  • Node-level entity and property changes, edge-level relation changes, and graph-level local-structure changes are observable projections of the same graph transition.The formulation couples latent-state learning with prediction of observable graph transitions.Source: §2 · p. 3

3 WORLDGRAPH

WorldGraph treats evolving graphs as worlds to model, pairing latent-state construction from graph structure and history with transition-aware learning of heterogeneous graph changes.

3.1.1 STAGE 1: MULTI-GRANULARITY GRAPH ENCODER

  • The state-aware graph transformer combines hop-based message passing and random-walk path sampling to represent graph structure at multiple scales.It fuses those structural views into node embeddings and pools them into a graph embedding.Source: §3.1.1 · pp. 3–4

3.1.2 STAGE 2: HISTORY-AWARE STATE ENCODER

  • The history-aware encoder integrates preceding graph changes into the latent state, accounting for their temporal distance and relevance to recent evolution.Its attention query combines current node and graph structure, the latest transition, and the previous latent state.Source: §3.1.2 · pp. 4–5

3.2 TRANSITION-AWARE REINFORCEMENT LEARNING

  • Transition-aware dynamic grouping gives rarer transition types more rollout samples, while structure-aware rewards weigh structural relevance and task-specific structural and property changes.The unified reward is R = λRstructure + (1 − λ)Rproperty.Source: §3.2.1 · pp. 5–6, §3.2.2 · p. 6

3.2.3 THEORETICAL ANALYSIS OF TRANSITION-AWARE RL ALGORITHM

  • For a given transition type, the proposed grouping yields a smaller upper bound on the effective variance ratio than standard GRPO.Group sizes depend on historical transition frequency and the rollout budget.Source: §3.2.3 · p. 6

4.2 OVERALL PERFORMANCE (RQ1)

  • Across node-, edge-, and graph-level tasks, WorldGraph and WorldGraph-Pretrain consistently outperform the baselines.Table 1 covers the three graph-transition task levels and reports F1, Macro-F1, NDCG@10, MAE, and RMSE.Source: Table 1 · p. 7, §4.2 · p. 8

4.3 ABLATION STUDY (RQ2)

  • Removing either encoder component or the RL mechanism and its components reduces performance on TGBN-Trade and Enron.The largest drops follow removal of the multi-granularity graph encoder or history-aware state encoder; dynamic grouping and structure-aware rewards contribute complementarily.Source: Figure 3 · p. 8, §4.3 · p. 8

4.4 SENSITIVITY ANALYSIS (RQ3)

  • On Flights graph-level Macro-F1, performance varies by only 0.31 percentage points across the tested hop counts, random-walk counts, and rollout budgets.Scores range from 58.09% to 58.40%.Source: Figure 4 · p. 9, §4.4 · p. 9

4.5 COMPARISON ON EXISTING GWM PROBLEM SETTINGS (RQ4)

  • In existing world-model settings, WorldGraph improves L3P planning success, C-SWM ranking at every tested horizon, and accuracy in all five reported GWM-E columns.For C-SWM, gains grow at longer horizons; the GWM-E comparison covers node classification, link prediction, and graph classification.Source: Figure 5 · p. 9, §4.5 · p. 9, Table 2 · p. 9

5 CONCLUSION

WorldGraph models graph-native dynamics by combining multi-granularity graph structure with transition-conditioned history, then learns heterogeneous transitions using frequency-aware sampling and structure-aware rewards. Across diverse graph-transition prediction tasks, it consistently achieves stronger performance.

5 CONCLUSION

  • WorldGraph consistently achieves stronger performance across diverse multi-granularity graph-transition prediction tasks.The conclusion identifies GWM-Zero as covering node-, edge-, and graph-level prediction across eight temporal graph datasets.Source: §5 · p. 10

B.1.1 DETAILS OF MULTI-GRANULARITY GRAPH ENCODER

  • The state model combines hop- and path-level structural views with a history-aware encoder that integrates preceding graph evolution.The history-aware state encoder attends over node memories using transition-conditioned queries, then combines the history embedding with structural and previous latent-state information.Source: §B.1.1 · p. 17, §B.1.2 · p. 18

B.2.1 DETAILS OF TRANSITION-AWARE DYNAMIC GROUP SAMPLING

  • Rarer transition groups receive more rollout samples through dynamic allocation of the rollout budget.The budget is apportioned proportionally across groups while retaining a minimum allocation for each group.Source: §B.2.1 · p. 18

B.2.2 STRUCTURE-AWARE REWARD DESIGN

  • The reward weights node and edge changes using node importance, with edge importance derived from its endpoint nodes.The shared task reward balances structural-change correctness with property-change accuracy.Source: §B.2.2 · p. 18

B.3 DETAILS OF TASK-SPECIFIC STRUCTURE-AWARE REWARD CALCULATION

Task-specific rewards combine structural-change localization with property-change accuracy, while transition-aware GRPO allocates rollouts by transition frequency. The theoretical analysis derives a smaller embedding-deviation upper bound for WorldGraph than for SGFormer under its stated assumptions.

B.3 DETAILS OF TASK-SPECIFIC STRUCTURE-AWARE REWARD CALCULATION

  • Node- and edge-level structural rewards average addition, deletion, and property-change localization terms, while graph-level reward equally combines change localization and representation-change magnitude.The graph-level representation includes node count, edge count, density, connected-component count, clustering coefficient, and triangle count; λgraph = 1/2.Source: §B.3 · p. 19

B.4 PSEUDO-CODE OF TRANSITION-AWARE RL

  • Transition-aware GRPO gives relatively more rollout samples to less frequent transition types and compares returns only among rollouts starting with the same edit type.Group-relative reward normalization yields advantages for policy updates, and the task reward combines structural and property components.Source: §B.4 · pp. 19–20

C.1 PROOF OF THEOREM 1

  • Under the stated Lipschitz assumption and consistent attention encoder, WorldGraph has a smaller embedding-deviation upper bound than SGFormer.The proof assumes the message function is C-Lipschitz and uses the same attention encoder across SGFormer, WorldGraph, and the ideal model.Source: §C.1 · p. 21

C.2 PROOF OF THEOREM 2

The proof contrasts GRPO’s fixed group size for each transition type with transition-aware RL’s frequency-based allocation of additional rollout budget. It relates this allocation to the EVR ordering under δ > 1.

C.2 PROOF OF THEOREM 2

  • With fixed group size, the group-size term for each transition type is the constant Ca.Source: §C.2 · p. 21
  • GRPO assigns each transition type a constant group size, whereas transition-aware RL retains a minimum group size and allocates additional rollouts according to transition frequency.The additional budget is allocated among transition types based on their frequency.Source: §C.2 · p. 21
  • The proof considers δ > 1 and uses the fact that EVR(ρ) decreases monotonically with ρ to establish the stated ordering.Source: §C.2 · p. 21

D EXPERIMENTAL VALIDATION OF THEORETICAL RESULTS

The experiments test the theoretical orderings for the graph encoder and transition-aware RL. On Flights and TGBN-Trade, respectively, the reported comparisons align with those orderings.

D.1 VALIDATION OF THE GRAPH-ENCODER BOUND

  • On Graph-level tasks/Flights, the default multi-view SGT has substantially smaller deviations from the full-view reference than SGFormer for both graph and hidden-state representations.The comparison uses five frozen WorldGraph checkpoints and the same test transitions without further training.Source: §D.1 · p. 22

D.2 VALIDATION OF THE RL VARIANCE BOUND

  • 13.02% lower mean EVR is reported for transition-aware RL than standard GRPO on Node-level tasks/TGBN-Trade.The mean EVR is the arithmetic mean over three transition groups, with lower values better.Source: §D.2 · p. 22

E TIME AND SPACE COMPLEXITY ANALYSIS OF WORLDGRAPH.

The analysis divides WorldGraph’s per-transition computation among multi-granularity graph encoding, history-aware state encoding, and transition-aware RL, and specifies the graph-size and candidate-set conditions on its scaling.

E TIME AND SPACE COMPLEXITY ANALYSIS OF WORLDGRAPH.

E.1 MULTI-GRANULARITY GRAPH ENCODING.

  • Multi-granularity graph encoding combines hop-level message passing with random-walk sampling, path encoding, and attention fusion.Sampling M walks of length at most Trw from every node costs O(NMTrw).Source: §E.1 · p. 23

E.2 HISTORY-AWARE STATE ENCODING.

  • History-aware state encoding attends each node’s current query to at most Lhist historical memories, with complexity O(NLhistd^2).Source: §E.2 · p. 23

E.3 TRANSITION-AWARE RL.

  • WorldGraph scales linearly with observed graph size when its listed hyperparameters are bounded, except for the task-dependent candidate set, which may reach O(N^2) for edge tasks.The space analysis accounts for graph storage, representations, historical memories, candidate states, and rollout tensors.Source: §E.3 · p. 23

F.1 STATISTICS OF DATASETS

The experimental design uses eight varied temporal graph datasets, a set of representative baselines, and same-task leave-one-dataset-out pretraining for WorldGraph-Pretrain.

F.2 STATISTICS OF BASELINES

  • Baseline comparisons preserve each model’s representation backbone while giving methods supervised transition and count-prediction heads and the same graph history, splits, and targets.Source: §F.2 · p. 24

F.1 STATISTICS OF DATASETS

  • GWM-Zero uses eight real-world dynamic graph datasets with varied domains, scale, temporal granularity, graph type, and edge semantics for node-, edge-, and graph-level predictions.The datasets range from 74 to 13,169 nodes and approximately 105 to 2.7×10^7 temporal events.Source: Table 7 · p. 24, §F.3 · p. 25

F.3 WHY WE CHOOSE THESE DATASETS AND BASELINES

  • The dataset and baseline selection spans complementary network domains and model families to test evolution across structural granularities rather than one task type.The comparisons cover local and global graph encoders, temporal models, pretraining, graph-structured world modeling, and transition-aware reinforcement learning.Source: §F.3 · pp. 25–26

G.1 DETAILS OF WORLDGRAPH PRETRAINING

  • WorldGraph-Pretrain excludes each target dataset and uses chronological transitions from the remaining datasets for the same node-, edge-, or graph-level task.It uses two graph views, symmetric InfoNCE, and next-step representation alignment to initialize WorldGraph.Source: §G.1 · p. 27

G.2 DETAILS OF TASK INFORMATION

The appendix specifies node-, edge-, and graph-level transition tasks, then details plug-in comparisons, hardware, and shared training settings.

G.2 DETAILS OF TASK INFORMATION

  • Node tasks cover addition, deletion, and property change; edge tasks cover addition and deletion; graph tasks predict six local structural-property changes.Node properties use official dynamic labels and a Jaccard-distance threshold; edge tasks reconstruct the next graph; graph tasks report MAE, RMSE, and macro-F1.Source: §G.2 · p. 27

G.3 DETAILS OF PLUG-IN INTEGRATION AND TRADITIONAL GRAPH PREDICTION

  • For L3P and C-SWM, the plug-in comparison retains each original backbone and decoder while adding WorldGraph components; standalone WorldGraph is also compared with GWM-E.GWM-E values come from its original reported results.Source: §G.3 · p. 27

G.4 DETAILS OF HARDWARE INFORMATION

  • Main experiments use four 16 GB Tesla V100 GPUs, with each training process assigned one GPU.The server also has a 40-logical-core Intel Xeon E5-2698 v4 CPU and 256 GB RAM.Source: §G.4 · p. 27

G.5 DETAILS OF PARAMETER SETUP.

  • All methods share chronological splits, graph inputs, history, and task targets; WorldGraph uses an eight-state history window and five-run averages.Checkpoints are selected on the validation set.Source: §G.5 · p. 28

H.1 EFFICIENCY ANALYSIS OF WORLDGRAPH.

WorldGraph-Pretrain performs best across nearly all reported multi-step graph-level metrics, while the transition-aware RL additions add little runtime over standard GRPO.

H.1 EFFICIENCY ANALYSIS OF WORLDGRAPH.

  • Transition-aware RL adds 1.99 s per epoch over standard GRPO on TGBN-Genre, at 27.54 s versus 25.55 s.The comparison measures mean epoch time over the first five training epochs; the table reports those timing results.Source: §H.1 · p. 29, Table 9 · p. 29

H.2 MULTI-STEP PREDICTION ANALYSIS.

  • WorldGraph-Pretrain is best on all nine Contact and Enron metrics and eight of nine Flights metrics; its Macro-F1 gains over the strongest external baseline span 1.78%–7.60%.The reported gains are 1.78%/3.90%/4.12% on Flights, 6.36%/6.19%/7.60% on Contact, and 1.10%/1.45%/1.28% on Enron for Steps 2/3/5.Source: §H.2 · p. 29
  • Multi-step evaluation recursively feeds predicted graph states for Steps 2, 3, and 5 after standard one-step training.Future ground-truth graphs are used only to construct evaluation targets.Source: §H.2 · p. 29

H.3 ADDITIONAL SENSITIVITY ANALYSIS

The appendix reports hyperparameter sensitivity and an image-to-graph rollout, alongside context on how WorldGraph differs from prior world models and temporal graph learning.

H.3 ADDITIONAL SENSITIVITY ANALYSIS

  • On Flights Macro-F1, the defaults γ = 1.00, θ = 1.00, η = 1.00, and tmax = 8 share a peak of 58.40%.The four sensitivity curves are inverted U-shaped; rarity exponent settings 0.50 and 1.25 yield 57.99% and 58.07%, respectively.Source: §H.3 · p. 29, Figure 6 · p. 30

H.4 IMAGE-TO-GRAPH VISUAL ROLLOUT.

  • In the five-object Shapes rollout, decoded images closely match ground truth, with object positions and temporal changes remaining well aligned across prediction steps.The rollout recursively uses predicted graph states, with the recorded transition sequence supplied from the start.Source: §H.4 · p. 31, Figure 7 · p. 31

I.1 WORLD MODELS.

  • Prior world models improve prediction or expose entities, but often leave evolving relations and structural dependencies implicit.The cited discussion presents graph-structured representations and relational inductive biases as foundations for modeling complex evolving worlds.Source: §I.1 · p. 32

I.2 TEMPORAL GRAPH LEARNING.

  • Temporal graph learners typically encode timestamped events or snapshots for node- or link-oriented tasks, whereas WorldGraph explicitly models structured transitions at node, edge, and graph levels.The cited comparison distinguishes temporal representations from joint state modeling and transition prediction.Source: §I.2 · p. 32

K.1 LIMITATIONS

The paper describes its graph-native world model as an initial conceptualization and identifies integration of diverse modalities as further work.

K.1 LIMITATIONS

  • The work is an initial conceptualization of graph-native world modeling; fuller integration of diverse modalities remains future work.The broader-impact discussion describes potential transfer to multimodal graph world modeling, including images and text.Source: §K.1 · p. 32, §K.2 · p. 32

K.2 BROADER IMPACTS

  • The proposed ideas are presented as potentially transferable to multimodal graph world modeling, where observations such as images and text are fused into an evolving graph representation.Source: §K.2 · p. 32

Related papers

Loading 2609.34159v1…