# Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement

arXiv: https://arxiv.org/abs/2509.09219 · HTML: https://mlsanity.com/paper/2509.09219/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 11 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Neural Enhanced Belief Propagation on Factor Graphs](https://mlsanity.com/paper/2003.01998/) (2020)
- [Playing Text-Adventure Games with Graph-Based Deep Reinforcement Learning](https://mlsanity.com/paper/1812.01628/) (2018)
- [Interpretable and Explainable Logical Policies via Neurally Guided Symbolic Abstraction](https://mlsanity.com/paper/2306.01439/) (2023)
- [Belief Propagation Neural Networks](https://mlsanity.com/paper/2007.00295/) (2020)
- [Beyond CAGE: Investigating Generalization of Learned Autonomous Network Defense Policies](https://mlsanity.com/paper/2211.15557/) (2022)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Deep Explainable Relational Reinforcement Learning: A Neuro-Symbolic Approach](https://mlsanity.com/paper/2304.08349/) (2023)
- [Size Independent Neural Transfer for RDDL Planning](https://mlsanity.com/paper/1902.03081/) (2019)
- [Entity-based Reinforcement Learning for Autonomous Cyber Defence](https://mlsanity.com/paper/2410.17647/) (2024)
- [Structural Generalization in Autonomous Cyber Incident Response with Message-Passing Neural Networks and Reinforcement Learning](https://mlsanity.com/paper/2407.05775/) (2024)
- [Learning More Expressive General Policies for Classical Planning Domains](https://mlsanity.com/paper/2403.11734/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)

## Built on by (most cited first, 2 of 2)

- [A Cyber Range Evaluation of Autonomous Network Incident Response Agents](https://mlsanity.com/paper/2609.16541/) (2026)
- [The MAL Simulator: Cyber Operations Simulation based on Attack & Defense Graphs](https://mlsanity.com/paper/2609.16563/) (2026)

## Abstract (arXiv)

We present and evaluate Vejde; a framework which combines data abstraction, graph neural networks and reinforcement learning to produce inductive policy functions for decision problems with richly structured states, such as object classes and relations. MDP states are represented as data bases of facts about entities, and Vejde converts each state to a bipartite graph, which is mapped to latent states through neural message passing. The factored representation of both states and actions allows Vejde agents to handle problems of varying size and structure. We tested Vejde agents on eight problem domains defined in RDDL, with ten problem instances each, where policies were trained using both supervised and reinforcement learning. To test policy generalization, we separate problem instances in two sets, one for training and the other solely for testing. Test results on unseen instances for the Vejde agents were compared to MLP agents trained on each problem instance, as well as the online planning algorithm Prost. Our results show that Vejde policies in average generalize to the test instances without a significant loss in score. Additionally, the inductive agents received scores on unseen test instances that on average were close to the instance-specific MLP agents.