Research map / Graph learning / Graph self-supervised learning
Graph Generation with $K^2$-trees
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 HGGT, which generates graphs by autoregressively producing a pruned, flattened, and tokenized K^2-tree representation with a Transformer using a tree positional encoding.
Problem
Graph generation from a target distribution is hard because adjacency-matrix generation is costly and common representations do not capture hierarchical structure in a compact, domain-agnostic way.
Approach
Uses the K^2-tree (a lossless compression representation) as the generation target: prunes symmetric redundant nodes, flattens via BFS, groups sibling nodes into tokens, and generates tokens with a Transformer that uses a tree positional encoding encoding each node's path from the root.
Key results
- On generic graphs HGGT achieves the best MMD on all four datasets (e.g., Grid degree/clustering/orbit 0.000/0.000/0.000 and Community-small degree 0.001).
- On ZINC250k HGGT reports NSPDK 0.001 and FCD 1.93, well below the best baselines (GDSS 0.019 / 14.66).
- On QM9 HGGT achieves validity 99.22 and NSPDK 0.000, but low novelty (24.01) and lower uniqueness (95.65) than some baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Group (sibling-node token grouping) (ablation) | HGGT · Community-small | Degree MMD: 0.072 -> 0.009 | Helped |
| add Group (sibling-node token grouping) (ablation) | HGGT · Planar | Degree MMD: 0.346 -> 0.003 | Helped |
| add Group (sibling-node token grouping) (ablation) | HGGT · Enzymes | Degree MMD: 0.050 -> 0.005 | Helped |
| add TPE (ablation) | HGGT with Group · Community-small | Degree MMD: 0.009 -> 0.002 | Helped |
| add TPE (ablation) | HGGT with Group · Enzymes | Degree MMD: 0.005 -> 0.002 | Helped |
| add TPE (ablation) | HGGT with Group · Community-small | Orbit MMD: 0.001 -> 0.001 | No clear effect |
| add Prune (ablation) | HGGT with Group and TPE · Community-small | Clustering MMD: 0.028 -> 0.006 | Helped |
| add Prune (ablation) | HGGT with Group and TPE · Planar | Degree MMD: 0.003 -> 0.000 | No clear effect |
| add Prune (ablation) | HGGT with Group and TPE · Enzymes | Degree MMD: 0.002 -> 0.005 | No clear effect |
| use HGGT instead of the strongest baseline | Generic graph generation models · Community-small | Degree MMD: 0.011 -> 0.001 | Helped |
| use HGGT instead of the strongest baseline | Generic graph generation models · Grid | Clustering MMD: 0.000 -> 0.000 | No clear effect |
| use HGGT instead of the strongest baseline | Molecular graph generation models · QM9 | Validity: 99.90 -> 99.22 | Hurt |
Surprising findings
- On QM9, HGGT's novelty (24.01) is much lower than most baselines, indicating it largely reproduces training molecules.
Limitations
- On QM9 novelty is low (24.01) and uniqueness is below some baselines.
- Some baselines (e.g., DiGress) were reproduced with fewer epochs due to compute cost, which may affect comparisons.
- Assumes the number of nodes is a power of K^2 (handled by default assumption), and pruning only applies to undirected graphs.
Experimental setup
Datasets: Community-small Planar Enzymes Grid QM9 ZINC250k
Benchmarks: Community-small Planar Enzymes Grid QM9 ZINC250k
Metrics: MMD degree MMD clustering coefficient MMD orbit count validity NSPDK FCD uniqueness novelty
Baselines: GraphVAE GraphRNN GNF GRAN EDP-GNN GraphGen GraphAF GraphDF SPECTRE GDSS DiGress GDSM
Builds on: K^2-tree lossless graph compression Cuthill-McKee ordering Transformer GDSS
Closest papers by meaning
- Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.89)
- SNACK: A Sequential Notation Framework for Probabilistic Graph Generation (NeurIPS 2026 · similarity 0.87)
- A Simple and Scalable Representation for Graph Generation (ICLR 2024 · similarity 0.86)
- DMol: A Highly Efficient and Chemical Motif-Preserving Molecule Generation Platform (NeurIPS 2025 · similarity 0.86)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.86)
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.85)
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.