PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nicolas Hochuli, Lorenzo Miele, Kristina Shea, Tino Stankovic

arXiv:2610.06244v1cs.LG

TL;DR

Generating embedded planar graphs toward user-defined objectives while enforcing hard structural and geometric constraints remains limited. This paper combines parametric graph grammars with safe reinforcement learning and action projection for constrained generation. Across four benchmarks, its method satisfies all constraints and achieves the best overall multi-objective reward.

  • Problem

    Existing methods provide limited support for goal-directed generation of embedded planar graphs that meets task-specific objectives under hard structural and geometric constraints.

    Source: §1 · p. 1

  • Method

    The method formulates grammar-based graph generation as a CMDP and uses safe reinforcement learning with action projection toward state-dependent safe sets.

    Source: §1 · p. 2, §2.3 · p. 4, §3.4 · p. 6

  • Results

    Across four benchmarks, the method generates graphs with exact prescribed node counts, satisfies all constraints, and achieves the best overall multi-objective reward.

    Source: §7 · p. 10

  • Takeaways & Limitations

    The method constructs graph topology and geometry jointly while enforcing feasibility through grammar-induced admissibility and learned action projection.

    Source: §7 · p. 10

    Scalability is limited by the growing combinatorial grammar design space, and generation is restricted to graphs expressible by the chosen rule set.

    Source: §6 · pp. 9–10

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses limited support for generating embedded planar graphs toward user-defined objectives while enforcing hard structural and geometric constraints. It proposes a dataset-free, grammar-based reinforcement learning approach and a benchmark suite for this task.

1 Introduction

  • Existing generators offer limited goal-directed control over embedded planar graphs subject to hard structural and geometric constraints.The need spans applications including urban planning, engineering design, and computational mesh generation.Source: §1 · pp. 1–2
  • The method combines parametric graph grammars with safe reinforcement learning, formulating generation as a CMDP and projecting actions toward state-dependent safe sets.It constructs feasible embeddings during generation and can target an exact prescribed node count.Source: §1 · p. 2
  • The paper introduces a benchmark suite covering geometric, topological, and spectral graph metrics for constrained, goal-directed planar graph generation.The authors also compare against classical and deep generative baselines.Source: §1 · p. 2

2 Preliminaries

The preliminaries define graph construction through parametric rewriting rules and frame each rewriting step as a constrained decision. This yields a CMDP in which graph states and rule applications support safe sequential generation.

2.1 Graph Grammars

  • A parametric graph grammar represents generation through an initial graph, rewriting rules, and continuous parameters governing edge lengths and sector angles.A rule replaces a matched subgraph; admissible matches identify boundary nodes, where rewriting may occur.Source: §2.1 · p. 3
  • Each rewriting step selects a rule, an admissible match, and continuous parameters, then updates graph topology and planar coordinates.Generation terminates when a criterion such as a prescribed node count is met.Source: §2.1 · p. 3

2.2 Constrained Markov Decision Processes

  • A CMDP seeks a policy that maximizes expected discounted reward while respecting constraints; here, actions are admissible only when all constraints are satisfied.The constraints are instantaneous and define state-dependent safe action sets.Source: §2.2 · p. 3

2.3 Graph Grammars as CMDPs

  • Grammar-based graph generation is a CMDP with graph states and rule-application actions, subject to hard instantaneous constraints.The graph transition depends only on the current graph and action, and the formulation underpins safe RL that preserves feasibility during generation.Source: §2.3 · pp. 3–4

3 Planar Graph Generation

The method uses PPO to choose grammar-based actions for planar graph generation and introduces action projection to help satisfy hard constraints. It encodes graph structure and embedding for decision-making, then rewards progress toward user-defined metric targets.

3 Planar Graph Generation

  • PPO learns a policy over grammar-based actions, coordinating the match, rule, and parameter choices to optimize user-specified objectives.A differentiable action projection maps actions onto a learned safe set during learning and inference.Source: §3 · p. 4

3.1 General Setup

  • The actor and critic use separate geometry-aware GNN encodings of the graph state, which includes topology, frontier, embedding, and node features.The initial graph consists of two boundary nodes joined by an edge of length 1.Source: §3.1 · p. 4

3.2 Constraint Taxonomy

  • Feasibility constraints cover edge-length bounds, minimum sector angles, maximum node degree, and absence of edge intersections.Topological violations are handled by rejection sampling, while frequent geometric violations motivate explicit action projection.Source: §3.2 · pp. 4–5

3.3 State, Feature Extraction and Critic

  • Node features combine boundary indicators, degree, local sector-angle encodings, and absolute coordinates; an E(2)-equivariant GNN processes graph structure and embedding.Jumping Knowledge and attention and mean pooling produce node-wise and global representations.Source: §3.3 · p. 5

3.4 Agent Design

  • The hybrid policy selects a boundary node, then a rewriting rule, then continuous parameters, with the continuous policy bounded through a tanh-affine map.The map also approximates projection of nominal samples into the geometric safe set; rejection sampling handles rare topological violations.Source: §3.4 · pp. 5–6

3.5 Action Projection Learning

  • CMA-ES searches for constraint-satisfying parameter corrections; accepted corrections train the projector alongside PPO, while unsuccessful searches fall back to rejection sampling.CMA-ES finds a valid correction in 70–90% of cases.Source: §3.5 · p. 6

3.6 Reward Design

  • The reward uses symmetric relative deviation from each user-defined metric target, with lower deviation preferred, to encourage joint satisfaction of the selected objectives.A positive epsilon ensures numerical stability.Source: §3.6 · p. 7

4 Related Works

The related-work section contrasts graph generators and deep generative models with sequential reinforcement-learning approaches. It positions the paper around hybrid discrete-continuous actions for goal-directed generation of embedded planar graphs under constraints.

4 Related Works

  • Classical and specialized planar graph generators provide random models or planar graph-family samplers, but are not designed for goal-directed multi-objective optimization under hard embedding constraints [11, 12, 13].Deep generative models offer distributional fidelity or property conditioning, but enforcing exact size, planarity, and hard constraints remains difficult [16] [17] [18].Source: §4 · p. 7
  • Prior grammar-based reinforcement learning demonstrates structured action spaces, mainly for discrete or domain-specific construction; this work targets embedded planar graphs with joint discrete and continuous actions [23] [46].The policy selects a graph match, rewriting rule, and safe geometric parameters under state-dependent topological and geometric constraints.Source: §4 · p. 7

5 Experiments

Across four benchmarks, the method balances competing objectives while satisfying constraints. The experiments also find benefits from action projection and generate feasible square-like graphs up to 150 nodes.

5 Experiments

  • Results average five seeds across four tasks; deep-baseline selection ranks 1,000 generated candidates without using constraint satisfaction.Source: §5 · p. 7, §5.1 · p. 8

5.1 Benchmarks

  • Across four benchmarks, the method balances competing objectives and satisfies constraints, including where Delaunay or HOG baselines miss trade-offs or triangle targets.Source: §5.1 · p. 8, Table 1 · p. 9
  • For the power-grid task, the idealized spectral-gap target pressures connectivity; Delaunay achieves the highest gap but sacrifices clustering and constraint satisfaction.Source: §5.1 · p. 8
  • For the road-grid task, Delaunay matches two metrics better but underperforms on angular resolution, has lower total reward, and fails 2/4 constraints.Source: §5.1 · p. 8
  • For the square-hull mesh, lattice graphs achieve perfect squareness but lower spectral gap, while the method offers the best trade-off and satisfies all constraints.Source: §5.1 · p. 8
  • For the 40-triangle task, the method closely matches the target and satisfies all constraints, whereas HOG substantially overshoots the triangle count.Source: §5.1 · p. 8

5.2 Ablation and Scalability Study

  • Projection raises terminal reward and cuts constraint violations 15-fold; reward declines with size or tighter constraints, yet feasible square-like graphs reach 150 nodes.Source: §5.2 · p. 9

6 Limitations & Future Work

Scalability is limited by the growing grammar design space at longer decision horizons, and the chosen grammar restricts which planar embeddings the method can generate.

6 Limitations & Future Work

  • Scalability remains limited as longer decision horizons expand the combinatorial grammar design space; experiments generate graphs up to 150 nodes.Source: §6 · p. 9, Figure 4 · p. 10
  • Future work proposes hierarchical reinforcement learning to shorten effective decision horizons and grammars with improved formal coverage of planar embeddings.Source: §6 · pp. 9–10
  • The chosen grammar limits generation to graphs expressible by its rule set, so the method does not claim completeness over all planar embedded graphs.Source: §6 · p. 10

7 Conclusions

The paper presents grammar-based reinforcement learning for feasible, goal-directed planar graph generation and reports strong rewards across four benchmarks. Its grammar jointly constructs topology and geometry, with rule application and parameterization designed to preserve planarity and geometric closure.

7 Conclusions

  • Across four benchmarks, the method generates graphs with exact prescribed node counts, satisfies all constraints, and achieves the best overall multi-objective reward.It maintains strong rewards while satisfying the full constraint set across heterogeneous benchmarks; the framework is designed to accommodate user-specified objectives and constraints through reward and constraint definitions.Source: §7 · p. 10

A Grammar Rules

  • The grammar defines seven rewriting rules that replace a local neighborhood at a boundary node, adding nodes and edges with rule-specific continuous geometric parameters.The transition removes boundary edges before each rule application and reconstructs them afterward, producing a planar, geometrically closed graph.Source: A Grammar Rules · p. 15

A.1 Rule semantics and notation in Figure 5 and Table 2

  • Rules rewrite a matched local neighborhood; applying them only at leaf nodes ensures the directed graph remains acyclic.The rule set includes merge operations, and the parameter space accounts for existing incident-edge angles when allocating new sector angles.Source: §A.1 · p. 15

A.2 Connecting Procedure cf. Figure 6

  • The deterministic connecting procedure finds mergeable nodes while preserving topological planarity, then restores boundary edges so the graph remains planar and geometrically closed.Traversals from boundary nodes identify merge targets or neighboring boundary nodes; the reconstructed boundary edges form a non-self-intersecting polygonal chain around the graph.Source: §A.2 · p. 16

A.3 Rule Parametrization

  • Rule parameters encode sector angles and edge lengths, which are converted from normalized values into planar node coordinates.The angle allocation respects the remaining angular budget and a positive minimum angle; edge lengths are bounded by the constraint set’s global minimum and maximum.Source: §A.3 · pp. 16–17

A.4 Implementation

The implementation pairs a geometry-aware graph feature extractor with actor–critic policies for selecting boundary matches, grammar rules, and continuous parameters. Graph and node representations encode geometry and graph size to support decisions across changing graph sizes.

A.4 Implementation

  • The grammar uses JAX, with vectorized pairwise edge-intersection checks evaluated in parallel; its sequential control flow and sparse data structures run on a multicore CPU.The implementation is designed around the sequential execution pattern of the grammar rather than GPU-parallel grammar control flow.Source: §A.4 · p. 17

B.1.1 Node-level Embeddings

  • The feature extractor encodes each node’s boundary status, degree, sector angles, and planar coordinates, then processes node features and coordinates through three E(2)-equivariant graph neural network layers.Coordinate updates are equivariant to planar rigid motions, while node and graph features are invariant to translations and rotations.Source: §B.1 · p. 17, §B.1.1 · p. 18

B.1.2 Graph-level Embeddings

  • Graph-level representations combine attentional aggregation and mean pooling, while graph-size-aware jumping knowledge weights pooled features from multiple layers using a log-scaled size signal.The extractor concatenates graph-level information with each node embedding, enabling globally informed node-level decisions while preserving the Markov property.Source: §B.1.1 · p. 18, §B.1.2 · p. 18, §B.1.3 · p. 18

B.2.1 Matching

  • The matching policy scores nodes and masks non-boundary nodes, so it samples only admissible boundary matches.The policy network produces one logit per node from its node representation.Source: §B.2.1 · p. 19

B.2.2 Rule Selection

  • Conditioned on the selected match, the rule-selection policy outputs a categorical distribution over the seven grammar rules.A separate network predicts rule-dependent continuous parameters from the matched-node representation and a learned rule embedding; unused parameter dimensions are masked.Source: §B.2.2 · p. 19, §B.2.3 · p. 19

B.3 Critic Network

  • The critic predicts state value from a graph-level embedding augmented with a learned embedding of graph size.Its feature extractor is architecturally identical to, but independently trained from, the policies’ feature extractor.Source: §B.3 · p. 19

B.4 Implementation, Network Sizes, and Training

The implementation combines an actor–critic system with a learned action projection that maps nominal continuous actions into bounded, state-dependent parameters. CMA-ES supplies feasible correction targets during projection training when proposed actions violate geometric constraints.

B.4 Implementation, Network Sizes, and Training

  • The actor–critic implementation uses PyTorch and PyTorch Geometric, while the environment runs in JAX; the architecture has 66,972 trainable parameters.Training uses PPO with Adam and a cosine-annealed learning-rate schedule, with reported training times from 10 minutes to 2 hours depending on task complexity.Source: §B.4 · p. 19

C.1.1 Squashed Affine Map

  • The action projection conditions on the matched node’s embedding and selected grammar rule, then applies a learned affine transformation and tanh squashing to the nominal continuous action.Its scale is positive and its shift is learned; tanh bounds projected parameters to (−1, 1).Source: §C.1 · p. 20, §C.1.1 · p. 20

C.1.2 Jacobian determinant

  • During PPO, the projection’s element-wise Jacobian determinant supplies the change-of-variables correction to the action log probability.The Jacobian is diagonal, and unused rule-dependent dimensions are masked.Source: §C.1.2 · p. 21

C.1.3 Policy Space Preservation

  • The projection is a C1 diffeomorphism from the nominal parameter space to the bounded action space, preserving the policy space up to reparameterization.The push-forward induced by the map is bijective between the corresponding probability-measure spaces.Source: §C.1.3 · p. 21

C.2 Supervised Training Procedure

  • The projection is trained synchronously with PPO from recent rollout data, using nominal parameters and environment-projected targets in a weighted mean-squared-error loss.The replay buffer retains the last ten rollouts, and samples where the environment changed a parameter receive weight 1 versus 0.5 otherwise.Source: §C.2 · p. 21

C.2.1 Environment-Side Supervision via CMA-ES

  • When a projected action is topologically admissible but geometrically infeasible, CMA-ES searches for a nearby feasible parameter set and provides corrected targets for projection training.If no feasible correction is found, the method falls back to rejection sampling and advances the time step without changing the graph state.Source: §C.2.1 · pp. 21–22

C.3 CMA-ES & Action Projection Results

CMA-ES overhead is reported as negligible relative to other rollout computations after half of training, while learned action projection reduces the need for this fallback. Constraint violations and rejection sampling are generally limited, though rejection sampling remains more common for larger graphs under tighter constraints.

C.3 CMA-ES & Action Projection Results

  • After 50% of training, CMA-ES overhead is negligible relative to remaining rollout computations, and invocations rapidly decline as learned projection approximates the safe set.Even on large graphs under tight constraints, CMA-ES finds parameters satisfying geometric constraints at a high rate.Source: §C.3 · p. 22, Figure 7 · p. 23
  • Topological violations are substantially less frequent than geometric violations, and rejection sampling converges quickly to zero for smaller graphs but remains low and more frequent for larger graphs under tighter constraints.Rejection sampling follows topological or geometric violations after action projection.Source: §C.3 · p. 22, Figure 7 · p. 23

D Graph Metrics

  • The benchmark graph metrics are categorized as topological, geometry-based, or spectral.They are respectively adjacency-based, drawing-dependent, and Laplacian-based.Source: D Graph Metrics · p. 23

D.1 Topological and Spectral Metrics

This block defines graph and drawing metrics and describes classical, planar, and deep generative baselines used for evaluation.

D.1 Topological and Spectral Metrics

  • Triangle count indicates local closure and community structure, while the global clustering coefficient captures how often a node’s neighbors are connected.The cited text notes that triangle statistics can be harder for generators to match than degree distributions.Source: §D.1 · p. 24
  • Spectral gap measures algebraic connectivity, with higher values indicating stronger connectivity, robustness, and faster mixing; degree inequality quantifies hub dominance and load balancing.The spectral gap is the second eigenvalue of the normalized Laplacian.Source: §D.1 · pp. 23–24

D.2 Geometric Metrics

  • Geometric metrics evaluate planar drawings, including angular resolution, edge-length uniformity, circularity, and hull squareness.Angular resolution compares minimum incident angles with an ideal angle; circularity is estimated from baseline graphs’ alpha-shape hulls when they lack boundary nodes.Source: §D.2 · pp. 24–25

E Graph Generators

  • The evaluation includes synthetic random-graph generators and House of Graphs, applying benchmark-favorable settings and force-directed layouts to methods without native embeddings.The HOG dataset contains connected planar graphs but does not provide embeddings.Source: E Graph Generators · p. 25

E.1 Classical Random Graph Models

  • Erdős–Rényi graphs produced no planar graphs in Benchmarks 2 and 3 and never achieved the best performance across evaluations.The passage attributes this to the model being constraint-free and not goal-directed.Source: §E.1 · p. 25
  • Classical baselines include ERGMs, which can produce disconnected or dense non-planar graphs, and planar samplers such as Plantri and Boltzmann sampling.Plantri evaluation is limited by I/O and scaling beyond 15–20 nodes; Boltzmann sampling is evaluated on 50 graphs per benchmark due to cost.Source: §E.1 · p. 26, §E.2 · p. 26

E.2 Planar Graph Generators

  • Planar-generator baselines also include Delaunay triangulations and regular lattice grids, constructed to reflect circular or square targets and spatial regularity.Lattice graphs have no triangles, and their final node count can differ slightly from the target.Source: §E.2 · p. 26

E.3 Deep Generative Graph Models

  • Deep baselines include property-guided DiGress, node-count-guided GDSS with PRODIGY, and MuDiff, which directly generates graphs with geometric embeddings.On HOG, 33% of unconditionally generated DiGress samples satisfy planarity, compared with 75% validity reported for the simpler fixed-size SPECTRE regime.Source: §E.3 · pp. 26–27

F Ranking-Based Graph Selection for Baseline Evaluations

Baseline selection filters for planarity, evaluates benchmark metrics and reward, and applies generator-specific ranking rules to select a graph.

F Ranking-Based Graph Selection for Baseline Evaluations

  • All candidates are first filtered for planarity, then retained graphs are scored using benchmark metrics and final reward.The planarity filter may retain graphs with edge intersections.Source: F Ranking-Based Graph Selection for… · p. 28
  • Classical generators retain graphs satisfying the most constraints, breaking ties by highest reward; they rarely satisfy every constraint.Source: F Ranking-Based Graph Selection for… · p. 28
  • Deep generators produce about 1,000 candidates; selection prioritizes target-size proximity, then chooses the highest-scoring candidate among the closest matches.The largest connected component is retained, and constraint statistics are recorded but not used for ranking.Source: F Ranking-Based Graph Selection for… · p. 28

G Extended Results on Benchmarks

The extended results report multi-objective rewards, individual metrics, and constraint satisfaction across four benchmarks, with qualitative comparisons in accompanying figures.

G Extended Results on Benchmarks

  • The benchmark tables report overall reward, individual metrics, constraint satisfaction, method embedding status, and standard deviations for the proposed method.They also include per-metric relative deviations across the four benchmarks.Source: G Extended Results on Benchmarks · pp. 28–29

G.1 Benchmark 1: Power Grid in Circular Hull

  • MuDiff attains the highest spectral gap in the power-grid benchmark but violates planarity constraints and target graph size.Source: Table 8 · p. 30, Figure 8 · p. 30

G.2 Benchmark 2: Urban Road Grid in Circular Hull

  • The proposed method has the highest combined reward for the urban-road-grid benchmark, balancing metrics closest to their targets on average.Some baselines marginally improve individual metrics, but most do not satisfy the full constraint set.Source: Table 9 · p. 31, Figure 9 · p. 31

G.3 Benchmark 3: Strongly Connected Mesh in Square Hull

  • MuDiff achieves the highest spectral gap for the highly connected square-hull mesh but strongly violates planarity constraints.This benchmark relaxes the constraints used in the other benchmarks.Source: Table 10 · p. 32, Figure 10 · p. 32

G.4 Benchmark 4: Graph with 40 triangles in circular hull

Related papers

Loading 2610.06244v1…