Hierarchical Discrete Flow Matching for Graph Generation

Yoann Boget; Pablo Strasser; Alexandros Kalousis

cs.LGMar 31, 2026

Hierarchical Discrete Flow Matching for Graph Generation

Authors: Yoann Boget, Pablo Strasser, Alexandros Kalousis

Organizations: Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland

Abstract

Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of function evaluations required during generation. In this work, we introduce a novel hierarchical generative framework that reduces the number of node pairs that must be evaluated and adopts discrete flow matching to significantly decrease the number of denoising iterations. We empirically demonstrate that our approach more effectively captures graph distributions while substantially reducing generation time.

Figures & tables

Panel of Figure 1 — Figure 1: Top : Deterministic Graph Expansion. Each parent node spawns a fixed number of child nodes. Children of the same parent form cliques, while children of connected parents form bicliques. Bottom : Graph Refinement. A generative model prunes excess edges and optionally generates node and edge attributes.

Method	Zinc250k	SBM20k	Reddit12k
Data	0.09 $\pm$ 0.00	0.08 $\pm$ 0.00	0.01 $\pm$ 0.00
DiffPool	0.34 $\pm$ 0.00	0.87 $\pm$ 0.03	0.82 $\pm$ 0.03
DMoN	0.57 $\pm$ 0.01	0.63 $\pm$ 0.02	0.04 $\pm$ 0.00
MinCut	0.37 $\pm$ 0.02	0.26 $\pm$ 0.01	0.12 $\pm$ 0.01
$D$ -Min (Ours)	0.25 $\pm$ 0.00	0.22 $\pm$ 0.00	0.02 $\pm$ 0.00

Table 1: Average density of the spanning supergraphs for four coarsening methods.

Model	NFE	FCD $\downarrow$	NSPDK $\downarrow$	Valid % $\uparrow$	Time (s) $\downarrow$
Train.	–	$0.062$	$0.121$	$98.90$	–
DiGress	1000	–	–	$95.4\phantom{0}$	–
DiscDif	128	$4.27$	$41.93\phantom{0}$	$22.29$	–
SID	128	$0.37$	$1.15$	97.97	–
DFM	128	$0.25$	0.44	$97.17$	$842.5$
HDFM	128	0.23	$0.53$	$95.78$	$333.5$

Table 2: Generation results on the QM9H dataset datasets. NSPDK results

\times 10^{3}

. Generation time in seconds.

Model	NFE	FCD $\downarrow$	NSPDK $\downarrow$	Valid % $\uparrow$	Time (s) $\downarrow$
Train.	–	$1.13$	$0.10$	$100.00\phantom{0}$	–
DiGress	1000	$3.48$	$2.1\phantom{0}$	$94.99$	$5517$
SparseDiff	2000	15.82	55.1	76.05	9826
Grum	1000	2.26	1.5	98.65	–
GraBFN		2.12	1.3	99.22	–
SID	128	2.06	2.01	99.50	–

Table 3: Generation results on the Zinc250k datasets. NSPDK results

\times 10^{3}

. Generation time in seconds.

Model	NFE	Valid $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Spec. $\uparrow$	Time (s) $\downarrow$
Train	–	90.7	0.08	1.97	0.17	–
EDGE	128	–	154.16	766.79	10.58	00 350
DiGress	1000	–	4.85	5.92	28.30	0 3906
SparseDiff	4000	–	1.10	5.25	19.11	11089
SID	128	0.00	$30.95\phantom{0}$	$38.79\phantom{0}$	$13.32$	$2840$
DFM	128	51.63	4.81	4.92	0 1.00	0 2834

Table 4: Generation results on the SBM20k datasets. MMDs results

\times 10^{3}

. Generation time in seconds.

Model	NFE	Degree $\downarrow$	Cluster. $\downarrow$	Spect. $\downarrow$
Train. set	–	$0.7\pm 0.4$	$14.6\pm 1.6$	$2.2\pm 0.7$
HiGen	–	$47.\phantom{0\pm 0.00}$	$3\phantom{\pm 0.000}$	–
EDGE	128	$58.\phantom{0\pm 0.00}$	$180\phantom{\pm 0.0000.}$	–
DiGress	1000	$8.9\pm 1.6$	$54\phantom{.0}\pm 4\phantom{.0}$	$19\phantom{.0}\pm 3.2\phantom{0}$
SparseDiff	10000	$3.7\pm 0.4$	32 .0 $\pm$ 1	$5.6\pm 0.8$
HDFM	128	1.4 $\pm$ 0.1	57.7 $\pm$ 1.3	3.3 $\pm$ 0.4

Table 5: Generation results on the Ego datasets. MMDs results

\times 10^{3}

. Generation time in seconds.

Model	NFE	degree $\downarrow$	clust. $\downarrow$	spect. $\downarrow$	Time $\downarrow$
Train.	–	0.17	5.17	1.51
EDGE	128	154.16	766.79	37.63	172
SparseDiff	10000	0 93.73	68.46	124.96	7234
HDFM	128	00 $0.32$	$3.35$	$3.34$	$107$
HDFM	32	00 $0.40$	$2.31$	$3.62$	$47$

Table 6: Generation results on the Reddit12k datasets. MMDs results

\times 10^{3}

. Generation time in seconds

Dataset	Test set	Conditional Gen.	Ratio Cond. / Test
SBM20k	4.57 $\pm$ 1.55	0.49 $\pm$ 0.06	0.114 $\pm$ 0.024
Reddit	3.57 $\pm$ 1.10	0.57 $\pm$ 0.31	0.161 $\pm$ 0.069

Table 7: Average spectral distances to reference graphs

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	level	$n_{\max}$	Reduc.	$D_{\text{data}}$	$D_{\mathcal{H}}$	Time (s)
Zinc250k	0	38	4	0.094	0.247	991
SBM20k	0	194	3	0.083	0.213	661
SBM20k	1	67	3	0.181	0.410	478
SBM20k	2	23	-	-	-	-
Reddit12k	0	1499	3	0.005	0.017	5891
Reddit12k	1	500	3	0.014	0.059	1516

Appendix

Table 8: Densities, training time, and maximum number of nodes for all datasets and all levels.

Dataset	Test set	Cond. gen.	Ratio
SBM20k	4.57 $\pm$ 1.55	0.49 $\pm$ 0.06	0.114 $\pm$ 0.024
Reddit	3.57 $\pm$ 1.10	0.57 $\pm$ 0.31	0.161 $\pm$ 0.069

Appendix

Table 9: Spectral distances

Model	NFE	Valid % $\uparrow$	FCD $\downarrow$	NSPDK $\downarrow$	Time (s) $\downarrow$
DFM	128	$97.17\pm 0.12$	$0.251\pm 0.005$	$0.438\pm 0.025$	$842.5\pm 12.8$
HDFM	128	$95.78\pm 0.03$	$0.231\pm 0.026$	$0.533\pm 0.027$	$333.5\pm 7.6$
HDFM	32	$94.22\pm 0.31$	$0.236\pm 0.007$	$0.469\pm 0.019$	$174.1\pm 2.3$

Appendix

Table 10: Generation results on the QM9H dataset. NSPDK results rescaled by

10^{3}

Model	NFE	FCD $\downarrow$	NSPDK $\downarrow$	Valid % $\uparrow$	Time (s) $\downarrow$
DFM	128	$1.48\pm 0.01$	$0.554\pm 0.014$	$99.41\pm 0.10$	$1998.8\pm 2.5\hphantom{00}$
HDFM	128	$1.23\pm 0.02$	$0.433\pm 0.025$	$99.30\pm 0.07$	$394.3\pm 8.6$
HDFM	64	$1.26\pm 0.01$	$0.500\pm 0.009$	$99.17\pm 0.09$	$238.7\pm 2.4$
HDFM	32	$1.34\pm 0.01$	$0.637\pm 0.021$	$98.82\pm 0.04$	$167.6\pm 2.2$
HDFM	128	$1.25\pm 0.02$	$0.376\pm 0.023$	$99.28\pm 0.03$	$\hphantom{0}237.0\pm 12.1$

Appendix

Table 11: Generation results on the Zinc250k datasets. NSPDK results

\times 10^{3}

. Generation time in seconds.

Model	NFE	Valid $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Spec. $\uparrow$	Time (s) $\downarrow$	Uniq+novel (s) $\uparrow$
	EDGE		154.16 $\pm$ 3.79	766.79 $\pm$ 19.24	10.58 $\pm$ 0.12	350 $\pm$ 8
	DiGress		4.85 $\pm$ 6.15	5.92 $\pm$ 1.97	28.30 $\pm$ 14.4	3906 $\pm$ 53
	SparseDiff		1.10 $\pm$ 0.34	5.25 $\pm$ 0.50	19.11 $\pm$ 4.52	11089 $\pm$ 640
DFM	128	$51.63\pm 1.71$	$4.813\pm 0.140$	$4.921\pm 0.144$	$1.001\pm 0.032$	$2834.4\pm 1.2\hphantom{0}$	$100.00\pm 0.00$
HDFM	128	$70.40\pm 0.96$	$0.147\pm 0.039$	$2.055\pm 0.022$	$0.301\pm 0.016$	$\hphantom{0}489.8\pm 17.3$	$100.00\pm 0.00$
HDFM	32	$68.80\pm 0.54$	$0.241\pm 0.028$	$2.057\pm 0.025$	$0.302\pm 0.018$	$160.7\pm 3.5$	$100.00\pm 0.00$

Appendix

Table 12: Generation results on the SBD20k dataset (MMD results rescaled by

10^{3}

	Model	degree $\downarrow$	clust. $\downarrow$	spect. $\downarrow$	Time $\downarrow$
EDGE	1000	154.16 $\pm$ 3.79	766.79 $\pm$ 19.24	37.63 $\pm$ 1.63	172 $\pm$ 1
SparseDiff	10000	00 93.73 $\pm$ 10.80	0 68.46 $\pm$ 39.01	124.96 $\pm$ 14.24	7234 $\pm$ 859
HDFM	128	$0.32\pm 0.07$	$3.35\pm 0.86$	$3.34\pm 0.18$	$107\pm 6$
HDFM	32	$0.40\pm 0.08$	$2.31\pm 0.37$	$3.62\pm 0.26$	$47\pm 4$

Appendix

Table 13: Generation results on Reddit12k datasets. MMDs results rescaled by

10^{3}

. Generation time in seconds.

Panel of Figure 2 — Figure 2: SBM20k: Comparison of generated graphs with graphs from the dataset.

Panel of Figure 3 — Figure 3: ego: Comparison of generated graphs with graphs from the dataset.

Panel of Figure 4 — Figure 4: reddit: Comparison of generated graphs with graphs from the dataset.

Graph Generation

Graph generation builds models and algorithms that create graphs with desired structures, properties, or distributions.

See all 66 papers

Efficient Graph Generation via Direct Prediction and Flow Matching
Oct 4, 2026Susie LuFlow Matching Graph Generation
MIT
Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation
Mar 30, 2026Yoann Boget, Alexandros KalousisGenerative Modeling Diffusion Models
Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland
DiPhon: Diffusion on Graphons for Scalable Graph Generation
Jul 8, 2026Sergio Rozada, Yiming Qin, Manuel Madeira +2Graphon Theory Graph Generation
King Juan Carlos University · EPFL, Lausanne, Switzerland · University of Pennsylvania

Oct 4, 2026J/K move · Enter open · S save

Efficient Graph Generation via Direct Prediction and Flow Matching

Susie Lu

MIT

Flow Matching Graph Generation Molecular Graph Generation Flow-Based Generative Modeling Graph Transformer

Open paper AskPDF arXiv

Generative modeling of graph-structured data is crucial for tasks ranging from drug discovery to social network simulation. Among these models, denoising diffusion models have achieved great success in graph generation by learning to progressively reverse a process that adds noise to the original graph. However, the standard noise-prediction approach of diffusion models is suboptimal for graph data. The goal for a graph generative model is to learn the clean graphs' topological properties, such as connectivity and degree distribution. Because a diffusion model that predicts noise does not explicitly learn these topological properties, it is challenging for the model to output graphs with the desired structural statistics. To address this challenge, we introduce Direct Graph Flow Matching (DiGFM), a novel graph transformer model guided by two goals: predict clean graphs and improve sampling efficiency. Distinct from the prevailing diffusion approach, DiGFM employs a continuous flow-matching paradigm and integrates direct graph prediction. Specifically, DiGFM maps the prior noise distribution to the clean graph distribution via a multi-step process: the model repeatedly predicts the underlying clean graph, and a transformation is employed to convert the model output to the velocity vector that points in the direction toward the clean graph distribution. This design enables DiGFM to generate high-quality samples using only 2.5% to 15.6% of the steps required by diffusion-based models, which leads to a 5.3x to 257x speedup in wall-clock inference time. Experiments demonstrate that DiGFM outperforms or matches prior state-of-the-art models across general graph benchmarks and molecular datasets, generating graphs with strong adherence to ground-truth structural statistics at significantly faster inference speeds.

Abstract

Graph Generation

Explore similar work

Efficient Graph Generation via Direct Prediction and Flow Matching

Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation

DiPhon: Diffusion on Graphons for Scalable Graph Generation