Research map / Graph learning / Graph self-supervised learning
Generative Modelling of Structurally Constrained Graphs
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 ConStruct, a discrete graph diffusion framework that hard-constrains generated graphs to edge-deletion-invariant structural properties (planarity, acyclicity, lobster) via an edge-absorbing noise model and a projector operator.
Problem
Graph diffusion models cannot guarantee domain-specific structural properties (e.g., planarity, acyclicity) in generated graphs, which limits deployment where invalid graphs are useless.
Approach
Use an edge-absorbing forward process (edges only get deleted toward no-edge), so forward and reverse processes stay within the set of graphs satisfying an edge-deletion-invariant property; a projector inserts candidate edges in random order and rejects those violating the property, with incremental property checks and a blocking hash table for efficiency.
Key results
- On planar synthetic graphs, ConStruct reaches 100% V.U.N. and 100% planarity with average ratio 1.1, versus 3.6 for DiGress+.
- On digital pathology high-TLS graphs, ConStruct improves V.U.N. to 99.8% from 7.8% for DiGress+ (up to 71.1 percentage points gain in validity claimed in abstract).
- On tree synthetic data ConStruct is outperformed by DiGress+ (ratio 1.9 vs 1.3), attributed to the lower expressivity of the edge-absorbing noise model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add planarity constraints to graph diffusion | DiGress · Planar Dataset | V.U.N.: 76.4 -> 100.0 | Helped |
| Add acyclicity constraints to graph diffusion | DiGress · Tree Dataset | V.U.N.: 91.6 -> 83.0 | Hurt |
| Add acyclicity constraints to graph diffusion | DiGress · Tree Dataset | Ratio: 1.3 -> 1.9 | Hurt |
| Add lobster-component constraints to graph diffusion | DiGress · Lobster Dataset | V.U.N.: 69.4 -> 83.2 | Helped |
| Add planarity constraints to graph diffusion | DiGress · Low TLS Dataset | V.U.N.: 18.6 -> 98.4 | Helped |
| Add planarity constraints to graph diffusion | DiGress · High TLS Dataset | V.U.N.: 7.8 -> 99.8 | Helped |
| Add planarity constraints to graph diffusion | DiGress · High TLS Dataset | TLS Valid: 6.6 -> 88.0 | Helped |
Surprising findings
- On the tree dataset, the constrained model underperforms the unconstrained DiGress+, attributed to the edge-absorbing noise model's lower expressivity.
- The projector does not always output the GED-optimal graph for properties beyond acyclicity (counterexamples for planarity, max degree, lobster).
Limitations
- Only handles edge-deletion invariant properties; edge-insertion invariant properties need an inverted framework (future work)
- Connectedness cannot be enforced since not edge-deletion invariant, so validity below 100% on synthetic sets
- Does not handle joint node-edge constraints such as valency in molecules
Experimental setup
Datasets: planar tree lobster METABRIC-derived digital pathology cell graphs (low TLS, high TLS)
Benchmarks: planar tree lobster low TLS high TLS
Metrics: MMD^2 degree/clustering/orbit/spectral/wavelet average ratio Valid Unique Novel V.U.N. property satisfaction connectedness planarity TLS valid
Baselines: GraphRNN GRAN SPECTRE DiGress EDGE BwR BiGG GraphGen HSpectre GDSS GEEL HGGT
Builds on: DiGress PRODIGY EDGE GraphARM HSpectre
Closest papers by meaning
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.90)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.90)
- Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models (NeurIPS 2025 · similarity 0.89)
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.89)
- Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation (ICML 2025 · similarity 0.89)
- Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.