mlsanityData to 14 Oct 2026

Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning

arXiv 2610.06244 ↗First posted 5 Oct 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations also fits: RL with diffusion and flow models

Abstract (arXiv)

Planar graphs are central to applications across science and engineering, yet existing generators provide limited support for goal-directed generation under hard structural and geometric feasibility constraints. We propose a dataset-free method for generating planar graph embeddings by combining parametric graph grammars with safe reinforcement learning to optimize generic task-specific objectives while satisfying constraints during construction. We formulate the generation process as a constrained Markov decision process, where the graph grammar defines the state and action spaces. We further introduce an action projection that maps sampled actions toward state-dependent safe sets, improving constraint satisfaction during training. In contrast to classical graph generators and deep generative models, which typically offer limited goal-directed control or rely on weak constraint satisfaction, our method constructs feasible planar graph embeddings directly during generation. We also introduce a benchmark suite for constrained and goal-directed planar graph generation, together with classical and deep generative baselines. Across all benchmark tasks, our method consistently outperforms baselines while satisfying the formulated constraints.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 28 of its 65 references that are in the map. First posted on arXiv 5 Oct 2026.

Builds on

28 of 65 references.

References · 28

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  4. 2015Variational Inference with Normalizing Flowscited by 2,170
  5. 2021E(n) Equivariant Graph Neural Networkscited by 965
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  7. 2020Directional Message Passing for Molecular Graphscited by 561
  8. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 520
  9. 2022GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generationcited by 516
  10. 2020GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generationcited by 305
  11. 2022Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equationscited by 283
  12. 2018Safe Exploration in Continuous Action Spacescited by 247
16 more
  1. 2019Graph Matching Networks for Learning the Similarity of Graph Structured Objectscited by 205
  2. 2018Optimization of Molecules via Deep Reinforcement Learningcited by 200
  3. 2021Spherical Message Passing for 3D Graph Networkscited by 168
  4. 2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generatorscited by 99
  5. 2023Generative Diffusion Models on Graphs: Methods and Applicationscited by 81
  6. 2018NeVAE: A Deep Generative Model for Molecular Graphscited by 67
  7. 2023MUDiff: Unified Diffusion for Complete Molecule Generationcited by 42
  8. 2022evosax: JAX-based Evolution Strategiescited by 41
  9. 2023Efficient and Scalable Graph Generation through Iterative Local Expansioncited by 36
  10. 2024Generative Modelling of Structurally Constrained Graphscited by 19
  11. 2020Goal-directed graph construction using reinforcement learningcited by 14
  12. 2020Reinforced Molecular Optimization with Neighborhood-Controlled Grammarscited by 10
  13. 2025Controllable Graph Generation with Diffusion Models via Inference-Time Tree Search Guidancecited by 7
  14. 2018Grammars and reinforcement learning for molecule optimizationcited by 3
  15. 2024Random Graph Modeling: A survey of the conceptscited by 2
  16. 2023Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithmcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations
  2. 2026Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint
  3. 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization
  4. 2020World Model as a Graph: Learning Latent Landmarks for Planning
  5. 2026Embodied Task Planning via Graph-Informed Action Generation with Large Language Models
  6. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  7. 2025When Diffusion Breaks Constraints: Sequential Autoregressive Generation with RL and MCTS
  8. 2025Test-Time Graph Search for Goal-Conditioned Reinforcement Learning