Research map / Graph learning / Graph self-supervised learning

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

NeurIPS 2026 · Graph learning › Graph self-supervised learning · approach: Diffusion-based graph generation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a dataset-free grammar-based safe RL method (PPO with learned action projection) that generates constrained, goal-directed planar graph embeddings, plus a four-task benchmark suite.

Problem

Goal-directed generation of embedded planar graphs under hard structural and geometric feasibility constraints (edge lengths, sector angles, degree bounds, planarity) is poorly supported by existing classical and deep generative graph generators.

Approach

Formulate parametric graph-grammar rewriting as a constrained MDP whose state/action spaces are induced by the grammar, and combine PPO with a learned, state-dependent tanh-affine action projection supervised by CMA-ES corrections so constraints are satisfied during construction.

Key results

• On the resilient power grid benchmark, the method achieves reward 0.76 vs 0.69 for Delaunay and 0.38 for HOG, satisfying all 4/4 constraints.
• On the urban road grid benchmark, reward 0.94 vs 0.91 (Delaunay) and 0.78 (HOG), satisfying all constraints while Delaunay satisfies 2/4.
• On the 40-triangle mesh benchmark, reward 0.98 with 39.91 triangles on average vs 0.86 for HOG (64 triangles).

Surprising findings

• Delaunay triangulation achieves the highest spectral gap on the power-grid benchmark but fails constraint satisfaction.
• Lattice graphs satisfy squareness perfectly but have lower spectral gap, and a few classical baselines are competitive on individual benchmarks.

Limitations

• Scalability limited by growing combinatorial grammar design space for longer decision horizons (tested up to 150 nodes).
• Generated graphs are restricted to those expressible by the chosen seven-rule grammar, so no completeness claim.
• Diffusion baselines are evaluated with a non-standard protocol that excludes constraint satisfaction from candidate ranking.

Experimental setup

Datasets: House of Graphs (HOG) for baseline comparison only

Benchmarks: Resilient power grid Urban road grid Strongly connected mesh Graph with 40 triangles

Metrics: multi-objective reward isoperimetric ratio Gini coefficient clustering spectral gap squareness angular resolution triangle count constraint satisfaction graph size

Baselines: HOG Delaunay GDSS MuDiff Lattice Boltzmann DiGress

Builds on: PPO EGNN Jumping Knowledge CMA-ES DiGress GDSS MuDiff

Closest papers by meaning

• Embodied Task Planning via Graph-Informed Action Generation with Large Language Models (ICML 2026 · similarity 0.86)
• GraphMimic: Graph-to-Graphs Generative Modeling from Videos for Policy Learning (CVPR 2025 · similarity 0.86)
• Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning (ICML 2025 · similarity 0.85)
• Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
• Breadth-First Exploration on Adaptive Grid for Reinforcement Learning (ICML 2024 · similarity 0.85)
• SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning (NeurIPS 2026 · similarity 0.85)