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

Nicolas Hochuli; Lorenzo Miele; Kristina Shea; Tino Stankovic

cs.LGOct 5, 2026

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

Authors: Nicolas Hochuli, Lorenzo Miele, Kristina Shea, Tino Stankovic

Organizations: Engineering Design and Computing Laboratory ETH Zürich

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.

Figures & tables

Figure 1: Sequential planar graph generation. Starting from an initial graph

G_{0}

, a policy samples rule-based actions

a_{t}\sim\pi(a_{t}\mid G_{t})

from a safe action space, enabling valid graph generation at each step. Actions modify graphs topologically and geometrically based on a predefined graph grammar.

Figure 2: Illustration of the proposed Actor-Critic architecture.

Table 1: Benchmark results across four planar graph generation tasks. Each graph corresponds to the result obtained by our method. The table shows averaged multi-objective reward, the individual metrics, graph sizes and number of satisfied constraints for each benchmark. Evaluations for all 10 baselines are reported in Appendix G , complemented with per-baseline graph visualizations. Relative metric deviations from the targets are additionally provided in Appendix Table 12 .

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Rule set $\mathcal{P}$	Description	New nodes	Merges	$(\#\alpha,\#\ell)$	$\dim\Theta$
$p^{(1)}$	Triple node sprout	3	0	$(4,3)$	7
$p^{(2)}$	Single sprout + two merges	1	2	$(2,1)$	3
$p^{(3)}$	Merge left + double sprout	2	1	$(3,2)$	5
$p^{(4)}$	Merge right + double sprout	2	1	$(3,2)$	5
$p^{(5)}$	Double node sprout	2	0	$(3,2)$	5
$p^{(6)}$	Merge left + single sprout	1	1	$(2,1)$	3

Appendix

Table 2: Summary of grammar rules

\mathcal{P}

. “Merge” refers to connections identified by the connecting procedure (cf. Figure 6 ) and "Sprout" refers to newly added nodes. The table additionally shows the dimensionality of the geometric parametrization.

Figure 5: Schematic illustration of the seven grammar rules in $\mathcal{P}$ . The top row represent a graph state $G_{t}$ and the highlighted left-hand side $L$ (i.e. the match $\bar{v}_{t}^{b}$ ) of a rule $p^{(\cdot)}$ prior to a rule application. The bottom row shows the graph state $G_{t+1}$ after a rule has been applied, with the right-hand side $R$ shown as red outward directed edges, the red outlined newly added nodes, and merged nodes as dashed outlined nodes. Geometric parameters are indicated in the bottom row.

Figure 6: Visualization of the connecting procedure. (a) The connecting procedure identifies a merge-able node, starting from $\bar{v}_{t}^{b}$ . The merge-able node is depicted as the dashed-outlined node. (b) The connecting procedure identifies a boundary edge, depicted by the undirected edge between the highlighted nodes.

Parameter	Value
Discount factor $\gamma$	0.99
GAE parameter $\lambda$	0.95
Clip range $\epsilon_{\mathrm{PPO}}$	0.2
Entropy coefficient $c_{\text{ent}}$	0.01
PPO epochs per update	5
Mini-batch size	675

Appendix

Table 3: PPO hyper-parameters chosen consistently for all experiments.

Figure 7: Impact of CMA-ES optimization with action projection on training performance. Constraint tightness refers to the same constraint set as described in Section 5 . All error-bars refer to 1-sigma standard deviations accross 5 seeds. (a) Wall-clock time per rollout at 50% of training for different graph sizes, with contributions from feature extraction (EGNN) and CMA-ES under loose and tight constraints. (b) Percentage of rollout time spent in CMA-ES during training. (c) Number of CMA-ES invocations per episode for different graph sizes and constraint tightness. (d) Success rate of CMA-ES in resolving geometric constraints. (e) CMA-ES invocations with learned vs. static projection ( $s_{\psi}=1$ , $t_{\psi}=0$ ). (f) Number of topological ( $C_{T}$ ) and geometric ( $C_{G}$ ) constraint violations during PPO (log scale). (g, h) Rejection sampling rate during training using tight and loose constraints.

Metric	Input	Typical Use
Gini coefficient $c_{\mathrm{gini}}$	adjacency	hub dominance / inequality
Triangles $T=\mathrm{tr}(A^{3})/6$	adjacency	closure / community signal
Clustering $c_{\mathrm{cluster}}=3T/\mathrm{Triplets}$	adjacency	local redundancy
Algebraic connectivity $\lambda_{2}(L)$	adjacency	connectivity strength
Angular resolution $\mathrm{AR}$	drawing angles	readability at vertices
Edge uniformity score $S_{\ell}$	drawing lengths	regularity / aesthetics

Appendix

Table 4: Graph- and drawing-level metrics used for evaluation.

Hyperparameter	Value
Unconditional epochs	1000
Unconditional batch size	8
Unconditional learning rate	$2\cdot 10^{-4}$
Diffusion steps	500
Regressor hidden dimension	128
Regressor dropout	0.1

Appendix

Table 5: Hyperparameters for DiGress with property-regressor guidance.

Hyperparameter	Value
Training epochs	2000
Batch size	64
Learning rate	$10^{-2}$
EMA decay	0.999
Diffusion steps	1000
Predictor / Corrector	Euler / Langevin

Appendix

Table 6: Hyperparameters for GDSS with PRODIGY guidance.

Hyperparameter	Value
Diffusion steps	500
Noise schedule	polynomial_2
Diffusion loss	l2
Learning rate	[ $5\cdot 10^{-4},5\cdot 10^{-5}$ ]
Batch size	[2,4]
Training epochs	[400,600]

Appendix

Table 7: Hyperparameters for MuDiff.

	Reward	Geom.	Topological		Spec.	Constraints
Method	$r$	$r_{\mathrm{iso}}$	$c_{\mathrm{gini}}$	$c_{\mathrm{clust}}$	$\lambda_{2}(L)$	$\|G\|$	$\alpha_{\min}$	$c_{\ell}$	$\deg_{\max}$	$c_{\mathrm{pl}}$	Emb.
Target	1.0	1.0	0.1	0.2	1.0	50	$20^{\circ}$	$\ell_{1}$	8	True	True
Ours	0.756	0.960	0.090	0.200	0.050	50	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Ours	$\pm 0.004$	$\pm 0.020$	$\pm 0.002$	$\pm 0.004$	$\pm 0.003$	50	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
HOG	0.382	0.841	0.031	0.000	0.075	47	$\checkmark$	$\checkmark$	$\checkmark$	✗	✗
Delaunay	0.698	0.932	0.182	0.217	0.087	50	✗	✗	$\checkmark$	$\checkmark$	$\checkmark$

Appendix

Table 8: Extended results for power grid in circular hull with 50 nodes. Note that although MuDiff achieves highest spectral gap, this is achieved by not respecting planarity constraints and target graph size. Generally, for smaller graph the spectral gap tends to be higher, as well as for non-planar graphs.

Figure 8: Results for the power grid case for our method and all baselines.

	Reward	Geometric			Topo.	Constraints
Method	$r$	$r_{\mathrm{iso}}$	$S_{l}$	$\mathrm{AR}$	$c_{\mathrm{gini}}$	$\|G\|$	$\alpha_{\min}$	$c_{\ell}$	$\deg_{\max}$	$c_{\mathrm{pl}}$	Emb.
Target	1.0	1.0	0.7	0.8	0.2	80	$20^{\circ}$	$\ell_{1}$	8	True	True
Ours	0.942	0.952	0.82	0.755	0.163	80	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Ours	$\pm 0.011$	$\pm 0.027$	$\pm 0.02$	$\pm 0.019$	$\pm 0.01$	80	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
HOG	0.782	0.403	0.832	0.486	0.158	80	✗	✗	$\checkmark$	✗	✗
Delaunay	0.914	0.952	0.758	0.445	0.200	80	✗	✗	$\checkmark$	$\checkmark$	$\checkmark$

Appendix

Table 9: Extended result for urban road grid in circular hull with 80 nodes. Note that although some baselines marginally improve individual metrics, the combined multi-objective reward is highest for our method that balances the individual metrics closest to the target on average. Additionally, the full constraint set is not respected by most baselines, e.g. ERGM beats the angular resolution metric, but does not satisfy target graph size.

Figure 9: Results for the urban road grid case for our method and all baselines.

	Reward	Geometric	Spectral	Constraints
Method	$r$	$r_{\mathrm{square}}$	$\lambda_{2}(L)$	$\|G\|$	$\alpha_{\min}$	$c_{\ell}$	$\deg_{\max}$	$c_{\mathrm{pl}}$	Emb.
Target	1.0	1.0	0.300	100	$1^{\circ}$	$\ell_{2}$	15	True	True
Ours	0.647	0.887	0.064	100	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Ours	$\pm 0.01$	$\pm 0.06$	$\pm 0.006$	100	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
HOG	0.360	0.543	0.002	101	$\checkmark$	$\checkmark$	$\checkmark$	✗	✗
Delaunay	0.578	0.863	0.039	100	✗	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$

Appendix

Table 10: Extended results for highly connected mesh in square hull with 100 nodes. This benchmark relaxes the constraint set compared to the other benchmarks, providing insights to graph generation closer to an unconstrained setting. Note that in this benchmark, MuDiff achieves highest spectral gap, but does so by strongly dissatisfying planarity constraints.

Figure 10: Results for the mesh in square hull high spectral gap for our method and all baselines.

	Reward	Geom.	Topological	Constraints
Method	$r$	$r_{\mathrm{iso}}$	$T$	$\|G\|$	$\alpha_{\min}$	$c_{\ell}$	$\deg_{\max}$	$c_{\mathrm{pl}}$	Emb.
Target	1.0	1.0	40	60	$20^{\circ}$	$\ell_{1}$	8	True	True
Ours	0.979	0.920	39.91	60	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Ours	$\pm 0.022$	$\pm 0.080$	$\pm 0.09$	60	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
HOG	0.856	0.892	64	60	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	✗
Delaunay	0.759	0.949	107	60	✗	✗	$\checkmark$	$\checkmark$	$\checkmark$

Appendix

Table 11: Extended results for graph in circular hull with 60 nodes and 40 triangles.

Figure 11: Results for the graph in a circular hull with 40 triangles case for our method and all baselines.

Benchmark 1: Resilient Power Grid
Method	Reward	$d_{\mathrm{iso}}$	$d_{\mathrm{gini}}$	$d_{\mathrm{clust}}$	$d_{\lambda_{2}}$
Ours	0.756	0.020	0.053	0.000	0.905
Ours	$\pm 0.004$	$\pm 0.010$	$\pm 0.011$	$\pm 0.010$	$\pm 0.005$
HOG	$0.382$	0.0864	0.5267	1.0000	0.8605
Delaunay	$0.698$	0.0352	0.2908	0.0408	0.8399
Plantri	$0.445$	0.4524	0.4925	0.3517	0.9249

Appendix

Table 12: Per-metric relative deviations

d_{m}

reconstructed from the rounded metrics in Tables 8 – 11 in addition to the absolute reward. Lower is better for the deviation metrics; each metric contributes

d_{m}/|\mathcal{M}|

to the reward.

Explore similar work

May 4, 2026cs.AI

Fine-Grained Graph Generation through Latent Mixture Scheduling

Structure aware graph generation aims to generate graphs that satisfy given topological properties. It has applications in domains such as drug discovery, social network modeling, and knowledge graph construction. Unlike existing methods that only provide coarse control over graph properties, we introduce a novel conditional variational autoencoder for fine-grained structural control in graph generation. The approach refines the decoder's latent space by dynamically aligning graph- and property-driven representations to improve both graph fidelity and control satisfaction. Specifically, the approach implements a mixture scheduler that progressively integrates graph and control priors. Experiments on five real-world datasets show the efficacy of the proposed model compared to recent baselines, achieving high generation quality while maintaining high controllability.

Nidhi Vakil, Hadi Amiri

Department of Computer Science University of Massachusetts Lowell

Conditional Variational Autoencoder Molecular Generation Data Generation Latent Space Mixtures

Ask PDF

Jun 4, 2026cs.AI

DiG-Plan: Mitigating Early Commitment for Tool-Graph Planning via Diffusion Guidance

Generating executable tool plans requires selecting appropriate subsets from tool libraries, a combinatorial search problem with an exponentially large solution space. However, we identify a critical misalignment in predominant approaches: standard autoregressive (AR) decoding suffers from early commitment, where initial token choices rigidly constrain the search trajectory. A controlled study shows that masked denoising raises Pass@10 solution coverage from 0.320 to 0.943 over AR sampling under matched compute. Motivated by this, we propose DiG-Plan, a framework that decouples combinatorial exploration from structural refinement. DiG-Plan employs a diffusion-based proposer to generate diverse tool sets via iterative refinement, followed by an AR refiner for dependency prediction. On TaskBench, DiG-Plan improves over AR baselines by a 10% relative margin, with the largest gains on complex compositional tasks; API-Bank results show that the propose-refine-select design remains effective across domains. Code is available at https://github.com/puddingyeah/DiG-Plan.

Yansi Li, Zhuosheng Zhang

School of Computer Science, Shanghai Jiao Tong University

Classical Planning Planning Autoregressive Generation Iterative Refinement Early Layers

Ask PDF

May 5, 2026cs.AI

Self-Improvement for Fast, High-Quality Plan Generation

Generative models trained on synthetic plan data are a promising approach to generalized planning. Recent work has focused on finding any valid plan, rather than a high-quality solution. We address the challenge of producing high-quality plans, a computationally hard problem, in sub-exponential time. First, we demonstrate that, given optimal data, a decoder-only transformer can generate high-quality plans for unseen problem instances. Second, we show how to self-improve an initial model trained on sub-optimal data. Each round of self-improvement combines multiple model calls with graph search to generate improved plans, used for model fine-tuning. An experimental study on four domains: Blocksworld, Logistics, Labyrinth, and Sokoban, shows on average a 30% reduction in plan length over the source symbolic planner, with over 80% of plans being optimal, where the optimum is known. Plan quality is further improved by inference-time search. The model's latency scales sub-exponentially in contrast to the satisficing and optimal symbolic planners to which we compare. Together, these results suggest that self-improvement with generative models offers a scalable approach for high-quality plan generation.

Robert Gieselmann, Henrike von Huelsen, Mihai Samson +9

Amazon

Classical Planning Planning Generative Models Recursive Self-Improvement Transformer Encoder

Ask PDF