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

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

## 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.

## 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, 28 of 28)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Directional Message Passing for Molecular Graphs](https://mlsanity.com/paper/2003.03123/) (2020)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation](https://mlsanity.com/paper/2203.02923/) (2022)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Optimization of Molecules via Deep Reinforcement Learning](https://mlsanity.com/paper/1810.08678/) (2018)
- [Spherical Message Passing for 3D Graph Networks](https://mlsanity.com/paper/2102.05013/) (2021)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)
- [NeVAE: A Deep Generative Model for Molecular Graphs](https://mlsanity.com/paper/1802.05283/) (2018)
- [MUDiff: Unified Diffusion for Complete Molecule Generation](https://mlsanity.com/paper/2304.14621/) (2023)
- [evosax: JAX-based Evolution Strategies](https://mlsanity.com/paper/2212.04180/) (2022)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [Goal-directed graph construction using reinforcement learning](https://mlsanity.com/paper/2001.11279/) (2020)
- [Reinforced Molecular Optimization with Neighborhood-Controlled Grammars](https://mlsanity.com/paper/2011.07225/) (2020)
- [Controllable Graph Generation with Diffusion Models via Inference-Time Tree Search Guidance](https://mlsanity.com/paper/2510.10402/) (2025)
- [Grammars and reinforcement learning for molecule optimization](https://mlsanity.com/paper/1811.11222/) (2018)
- [Random Graph Modeling: A survey of the concepts](https://mlsanity.com/paper/2403.14415/) (2024)
- [Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithm](https://mlsanity.com/paper/2303.00635/) (2023)

## 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.