Research map / Graph learning / Graph self-supervised learning
Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation
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.
Pard generates graphs block-by-block autoregressively, with each block modeled by a shared permutation-equivariant discrete diffusion model using a PPGN-transformer hybrid, achieving state-of-the-art molecular and generic graph generation without extra features.
Problem
Graph generation: autoregressive models are sensitive to node ordering, while diffusion models need thousands of denoising steps and extra structural features to perform well.
Approach
Exploit a unique structural partial order on graph nodes (via k-hop degree structure) to split graph generation into permutation-invariant blocks; model each block's conditional with a shared discrete diffusion model using an equivariant PPGN-Transformer, with a causal block-ID masking scheme enabling parallel training.
Key results
- On ZINC250k, Pard reaches 99.99 uniqueness and FCD 1.98, matching SwinGNN-L on FCD and beating it on uniqueness, with 95.23 validity.
- On MOSES, Pard achieves FCD 1.00 and SNN 0.56, outperforming DiGress (FCD 1.19) without extra features.
- On generic graphs, Pard achieves best MMD on Caveman, Cora and Grid across degree/clustering/orbit metrics, e.g., Cora degree 0.0003 vs DiGress 0.044.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add autoregressive block generation (K_h=1) instead of full diffusion without AR (ablation) | Pard · QM9 | Validity: 93.8 -> 97.1 | Helped |
| add autoregressive block generation (K_h=1) instead of full diffusion without AR (ablation) | Pard · QM9 | Molecule stability: 76.4 -> 86.1 | Helped |
| add autoregressive block generation (K_h=1) instead of full diffusion without AR (ablation) | Pard · QM9 | Uniqueness: 96.9 -> 96.5 | Hurt |
| increase no-AR diffusion steps from 140 to 280 (ablation) | Pard without AR · QM9 | Validity: 93.8 -> 94.3 | Helped |
| increase no-AR diffusion steps from 140 to 490 (ablation) | Pard without AR · QM9 | Validity: 93.8 -> 95.2 | Helped |
| increase no-AR diffusion steps to 490 rather than use AR with K_h=1 and 140 total steps (ablation) | Pard · QM9 | Validity: 97.1 vs 95.2 | Hurt |
| replace PPGNTransformer with a Transformer-only backbone (ablation) | Pard · QM9 | Validity: 97.1 -> 26.3 | Hurt |
| replace PPGNTransformer with a PPGN-only backbone (ablation) | Pard · QM9 | Molecule stability: 86.2 -> 84.67 | Hurt |
| replace PPGN-only backbone with PPGNTransformer (ablation) | Pard · QM9 | Molecule stability: 84.67 -> 86.2 | Helped |
| use Pard rather than DiGress (marg. + feat.) | molecular graph generation · QM9 | Molecule stability: 79.8 -> 86.1 | Helped |
| use Pard rather than GDSS | molecular graph generation · ZINC250k | FCD: 14.66 -> 1.98 | Helped |
| use Pard rather than DiGress | molecular graph generation · MOSES | SNN: 0.52 -> 0.56 | Helped |
Surprising findings
- On MOSES, Pard scores much lower on scaffold similarity (2.2 vs 14.8 for DiGress) and novelty (78.2 vs 95.0), which the paper does not fully explain.
- Parallel causal training reduces expressiveness; the authors find sequential training easier to minimize on symmetry-rich Grid data.
Limitations
- Causal parallel training may reduce expressiveness for symmetry-rich graphs such as Grid.
- Lower scaffold similarity and novelty on MOSES versus DiGress indicate weaker coverage of some chemical properties.
- Reported baselines are largely sourced from prior papers rather than re-run under identical settings.
Experimental setup
Datasets: QM9 ZINC250k MOSES Community-small Caveman Cora Breast Grid
Benchmarks: QM9 ZINC250k MOSES Community-small Caveman Cora Breast Grid
Metrics: validity uniqueness novelty atom stability molecule stability FCD SNN scaffold similarity filters MMD degree
Baselines: DiGress GDSS GraphARM SwinGNN EDP-GNN GraphRNN GRAN ConGress JT-VAE GraphINVENT
Builds on: DiGress PPGN GRIT D3PM GraphARM
Closest papers by meaning
- Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.90)
- 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.89)
- Generating Graphs via Spectral Diffusion (ICLR 2025 · similarity 0.88)
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.88)
- Bias Mitigation in Graph Diffusion Models (ICLR 2025 · similarity 0.88)
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.