Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning
cs.LG
Submitted: 2026-10-05
Updated: 2026-10-05
Code: https://github.com/ETHZ-EDAC/constrained-graph-rl
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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
Terminology
Abstract
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.
Sources
- Generative Diffusion Models on Graphs: Methods and Applications
- Generative Modelling of Structurally Constrained Graphs
- Controllable Graph Generation with Diffusion Models via Inference-Time Tree Search Guidance
- GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation
- Optimization of Molecules via Deep Reinforcement Learning
- Reinforced Molecular Optimization with Neighborhood-Controlled Grammars
- Proximal Policy Optimization Algorithms
- Spherical Message Passing for 3D Graph Networks
- Directional Message Passing for Molecular Graphs
- E(n) Equivariant Graph Neural Networks
- Representation Learning on Graphs with Jumping Knowledge Networks
- Graph Matching Networks for Learning the Similarity of Graph Structured Objects
- Variational Inference with Normalizing Flows
- Safe Exploration in Continuous Action Spaces
- Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithm
- Efficient and Scalable Graph Generation through Iterative Local Expansion
- DiGress: Discrete Denoising diffusion for graph generation
- Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations
- MUDiff: Unified Diffusion for Complete Molecule Generation
- Goal-directed graph construction using reinforcement learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks