xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Daniele Micheletti; Federica Zoe Ricci; Erik B. Sudderth

stat.MLOct 22, 2026

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Authors: Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth

Organizations: University of California, Irvine · Swarthmore College

Abstract

Graphs play a crucial role in many applications, ranging from drug discovery to social network modeling and astronomy. Generative models for graphs have substantially advanced in recent years, but we identify relatively simple scenarios where state-of-the-art models struggle to converge within a standard compute budget, or exhibit prohibitively slow generation times. We propose a generative architecture that achieves quality competitive with state-of-the-art models and is orders of magnitude faster at generation. Our approach is inspired by the Aldous-Hoover theorem, a classic representation theorem that characterizes any probability distribution of graphs that is invariant to permutations of node indices or exchangeable. This theorem establishes that three ingredients suffice: a graph-level latent variable, a set of exchangeable node-specific latent variables, and a so-called graphon function that maps graph- and node-level variables to the probability of an edge between any node pair. Given a training set of graphs, our exchangeable Variational Graph AutoEncoder (xVGAE) learns an approximation to their underlying graphons, as well as graph- and node-level latent variables. We show that our xVGAE encodes latent representations that correlate with graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of the xVGAE architecture (inference and generation). The encoder (left) maps a graph $A$ to a global posterior $q_{\phi}(z_{0}\mid A)$ and node-level posteriors $q_{\phi}(z_{i}\mid z_{0},A)$ for the $n$ nodes. The prior (middle) samples the global latent $z_{0}\sim p_{\theta}(z_{0})$ and, conditionally, the independent node latents $z_{i}\sim p_{\theta}(z_{i}\mid z_{0})$ . The decoder (right) refines the node latents into features $h_{i}$ via an MLP, $z_{0}$ -conditioned FiLM ( Perez et al., 2018 ) , and optional attention. Finally, a bilinear head predicts pairwise edge probabilities $p_{\theta}(A_{ij}\mid h_{i},h_{j},z_{0})$ for all node pairs to generate $\hat{A}$ .

Figure 2: Two-dimensional PCA projections of the latent space for the global variable $z_{0}$ across all MMSBM, LFR, Ego, and Protein graphs in the test set. The latent space embeds structural information of the graphs: the plots show a clear association between the global variable and the graphs’ number of communities, mixing rate $\mu$ , average degree, and number of nodes $n$ .

Figure 3: Top: graphs from the test set of four different datasets (MMSBM, Ego, LFR, Protein) visualized using a spring layout. The nodes are colored by community membership for MMSBM and LFR, by distance from the ego node (represented by a star) for the Ego graph, and by Fiedler vector for Protein graphs. Bottom: Two-dimensional PCA projections of the encoded local variables, which are associated with these node characteristics.

Figure 4: Benchmark overview across four datasets. Panels compare xVGAE (blue) against the strongest (red) and second-strongest (orange) baselines per dataset. Both the xVGAE variant (MLP on MMSBM; SAB on LFR, Ego, and Protein) and the two baselines are selected per dataset by total column wins across degree, clustering, spectral, and WL $\mathrm{MMD}^{2}$ ratios (baseline names shown under each dataset). $\mathrm{MMD}^{2}$ ratios and $\mathrm{s/G}$ use a log scale; dashed lines mark the train–test reference ( $1.0$ ). Lower is better; whiskers show min–max ranges over three draws.

	$\mathrm{MMD}^{2}$ / train–test $\downarrow$				Auxiliary
Model	deg	clu	spec	orb	WL $\downarrow$	C2ST ${}_{\Delta}\downarrow$	s/G $\downarrow$
Train vs. test (raw)	0.00179	0.00990	0.00016	0.01000	0.00714	n/a	n/a
One-shot
VGAE	85.7 [85.1–88.4]	31.2 [29.6–31.6]	1,002 [984–1,032]	1.00 † [1.00–1.00]	25.4 [25.3–26.4]	0.470 [0.460–0.475]	$<$ 0.01
GraphVAE ∗	300	102	4,847	100 †	166	0.500	$<$ 0.01
SPECTRE	9.19 [8.38–9.39]	2.81 [2.76–2.87]	6.00 [5.61–6.63]	1.00 † [1.00–1.00]	2.28 [2.05–2.47]	0.195 [0.180–0.228]	0.03

Table 1: MMSBM (

n\in[120,400]

, density

\sim\!27.5\%

	$\mathrm{MMD}^{2}$ / train–test $\downarrow$				Auxiliary
Model	deg	clu	spec	orb	WL $\downarrow$	C2ST ${}_{\Delta}\downarrow$	s/G $\downarrow$
Train vs. test (raw)	0.00031	0.00993	0.00095	0.01299	0.00437	n/a	n/a
One-shot
VGAE ∗	1,390	16.9	382	4.94	160	0.500	$<$ 0.01
GraphVAE ∗	2,469	107	719	77.1	368	0.500	$<$ 0.01
SPECTRE	42.1 [39.0–43.9]	5.62 [5.37–5.72]	11.1 [10.3–11.9]	2.48 [2.33–2.53]	11.5 [11.4–12.0]	0.260 [0.259–0.276]	$<$ 0.01

Table 2: CiteSeer-Ego (

n\in[50,399]

, density

\sim\!3.6\%

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Split (tr/va/te)	$n$ (min / mean / max)	Density	Mean degree	$\bar{E}$	Type
CiteSeer-Ego	484 / 121 / 152	50 / 145 / 399	0.036	4.1	328	Real, citation
MMSBM	640 / 160 / 200	120 / 249 / 400	0.275	68.4	9144	Synthetic, blockmodel
LFR	640 / 160 / 200	200 / 350 / 500	0.037	12.2	2044	Synthetic, power-law
Protein (D&D)	587 / 147 / 184	100 / 258 / 500	0.023	5.0	632	Real, biological

Appendix

Table 3: Summary statistics for the four benchmarks. Splits are train / val / test graph counts.

n

, density

2|E|/(n(n-1))

and mean degree

2|E|/n

are per-graph averages over all splits;

\bar{E}

is the mean edge count of the scored test graphs (largest connected component).

	$\mathrm{MMD}^{2}$ / train–test $\downarrow$				Auxiliary
Model	deg	clu	spec	orb †	WL $\downarrow$	C2ST ${}_{\Delta}\downarrow$	s/G $\downarrow$
Train vs. test (raw)	0.00075	0.00914	0.00013	0.00986	0.00405	n/a	n/a
One-shot
VGAE ∗	458	40.1	3,439	1.05	138	0.500	$<$ 0.01
GraphVAE ∗	862	110	5,744	102	351	0.500	$<$ 0.01
SPECTRE ∗	247	9.61	3,986	1.28	69.4	0.500	0.03

Appendix

Table 4: LFR (

n\in[200,500]

, density

\sim\!3.7\%

	$\mathrm{MMD}^{2}$ / train–test $\downarrow$				Auxiliary
Model	deg	clu	spec	orb	WL $\downarrow$	C2ST ${}_{\Delta}\downarrow$	s/G $\downarrow$
Train vs. test (raw)	0.00022	0.01058	0.00031	0.00318	0.00174	n/a	n/a
One-shot
VGAE	2,541 [2,456–2,544]	28.7 [28.5–29.0]	1,012 [995–1,032]	238 [238–238]	623 [610–625]	0.500 [0.500–0.500]	0.006
GraphVAE	2,956 [2,955–2,961]	100 [100–101]	536 [536–537]	444 [444–444]	970 [970–971]	0.500 [0.500–0.500]	$<$ 0.01
SPECTRE ∗	1,330	88.5	1,790	238	395	0.500	0.02

Appendix

Table 5: Protein/D&D (

n\in[100,500]

, density heterogeneous).

Baseline	Dataset	Published (source)	Ours, their protocol	Verdict	Likely cause
GRAN	Protein	2.0e-3 / 0.049 / 0.13 (GRAN T1)	2.5e-3 / 0.082 / 0.16	match
GRAN	Ego	7.7e-3 / 0.066 / 0.043 (HiGen T9)	0.017 / 0.11 / 0.061	match ( $\leq 2.2\times$ )	split
GraphRNN	Protein	4.0e-3 / 0.15 / 0.59 (SPECTRE T2)	7.0e-3 / 0.12 / 0.40	match
GraphRNN	Ego (EMD)	0.077 / 1.15 / 0.11 (EDGE T2)	0.18 / 1.08 / 0.052	match
DiGress	Ego	8.9e-3 / 0.054 / 0.030 (SparseDiff T1)	3.9e-3 / 0.041 / 0.027	match
DiGress	Protein	4.1e-3 / 0.049 / 0.13 (ILE T2)	0.050 / 0.080 / 0.58	mismatch, 4–12 $\times$	undertrained

Appendix

Table 6: Baselines against their published numbers: raw

\mathrm{MMD}^{2}

degree / clustering / orbit under the published protocol (EMD kernel where marked, TV otherwise). Sources in parentheses: the table of the paper reporting the number.

Dataset (test $\bar{n}$ / $\bar{E}$ )	Model	LCC $\bar{n}$	$\bar{E}$	Reason
MMSBM (249 / 9,144)	GraphVAE	1	0	empty
	LGD	1	0	empty
LFR (350 / 2,044)	GraphVAE	1	0	empty
	SPECTRE	42	191	fragmented
	VGAE	346	31,679	$15\times$ edges
	EDP-GNN	360	43,119	$21\times$ edges

Appendix

Table 7: Collapsed rows: mean LCC size and mean edge count of the generated graphs against the test graphs (test:

\bar{n}

\bar{E}

Model	MMSBM	LFR	CiteSeer-Ego	Protein
VGAE	64	8	1	1
GraphVAE	128	128	64	128
SPECTRE	8	8	8	8
IGNR	8	8	8	8
GraphRNN	256	256	256	256
GRAN	64	64	64	64

Appendix

Table 8: Batch size of the fastest timing (the s/G reported in the result tables).

Dataset	Row	Encoder	Decoder	$\beta_{0}$	$\beta$ schedule; LR schedule
CiteSeer-Ego	xVGAE-SAB	SAB, 5	SAB, 5	1	$\beta{=}1$ , 2000 ep.; constant
CiteSeer-Ego	xVGAE-MLP	SAB, 5	MLP	0.1	16 / 46 / 1230; cosine
MMSBM	xVGAE-SAB	SAB, 5	SAB, 5	0.1	12 / 35 / 938; cosine
MMSBM	xVGAE-MLP	SAB, 5	MLP	0.1	12 / 35 / 938; cosine
LFR	xVGAE-SAB	SAB, 5	SAB, 5	0.1	12 / 35 / 938; cosine
LFR	xVGAE-MLP	SAB, 5	MLP	0.1	12 / 35 / 938; cosine

Appendix

Table 9: xVGAE autoencoder configurations. All models use a 5-layer SAB encoder and either a 5-layer SAB or pointwise MLP decoder. Schedule triples denote warm-up / anneal / total epochs. ∗ Uses a 32-component Gaussian-mixture node prior, weight decay

10^{-8}

, and

z_{0}\sim\mathcal{N}(0,I)

Figure 5: The latent space of the global variable $z_{0}$ embeds structural information of MMSBM graphs. The plots show a clear association between the global variables and the graphs’ average degree, clustering coefficient, size and number of communities.

Figure 6: The latent space of the global variable $z_{0}$ embeds structural information of Ego graphs. The plots show a clear association between the global variables and the graphs’ average degree, clustering coefficient, size and the degree of the Ego node.

Figure 7: The latent space of the global variable $z_{0}$ embeds structural information of LFR graphs. The plots show a clear association between the global variables and the graphs’ average degree, clustering coefficient, number of communities and mixing parameter.

Figure 8: The latent space of the global variable $z_{0}$ embeds structural information of Protein graphs. The plots show a clear association between the global variables and the graphs’ average degree, clustering coefficient, algebraic connectivity and graph size.

Figure 9: Top: Three graphs from the test set of MMSBM (spring layout). The nodes are colored by their strongest community membership. Bottom: PCA 2D projection of the latent space for the encoded local variables, demonstrating that the latent space of our xVGAE clusters together nodes with similar membership distribution even though it was only exposed to the adjacency matrix.

Figure 10: Top: Three graphs from the test set of Ego (spring layout). The nodes are colored based on the number of hops separating them from the Ego node, represented with a star. Bottom: PCA 2D projection of the latent space for the encoded local variables, demonstrating that the latent space of our xVGAE maps nodes based on their distance from the Ego node, even though it does not know which node is the Ego.

Figure 11: Top: Three graphs from the test set of LFR (spring layout). The nodes are colored by their community membership, showing that the latent space of our xVGAE clusters together nodes with the same community membership and orders them by relative degree, even though it was only exposed to the adjacency matrix. Bottom: PCA 2D projection of the latent space for the encoded local variables, demonstrating that the latent space of our xVGAE clusters together nodes with the same community membership even though it was only exposed to the adjacency matrix.

Figure 12: Top: Three graphs from the test set of Protein (spring layout). The nodes are colored by Fiedler vector. Bottom: PCA 2D projection of the latent space for the encoded local variables, demonstrating that the latent space of our xVGAE contains meaningful information given the clustering colors based on the Fiedler vector.

Figure 13: Examples of generated Ego graphs (spring layout) from our model, main baselines and version of xVGAE without global diffusion.

Figure 14: Examples of generated LFR graphs (spring layout) from our model, main baselines and version of xVGAE without global diffusion.

Figure 15: Examples of generated MMSBM graphs (spring layout) from our model, main baselines and version of xVGAE without global diffusion.

Figure 16: Examples of generated Protein graphs (spring layout) from our model, main baselines and version of xVGAE without global diffusion.

Graph Generation

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

See all 67 papers

GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens
Sep 29, 2026Yuxiang Yao, Zijun ZhaoAutoregressive Generation Graph Foundation Models
Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology Beijing Institute of Technology
Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA
GraphK: Variable-Size Graph Generation with Efficient Edge Construction
Aug 19, 2026Resul Tugay, Eren Oluğ, Elif Ak +1Graph Generation Generative Modeling
Department of Artificial Intelligence and Data Engineering Ataturk University, Turkey · Department of Artificial Intelligence and Data Engineering ITU AI Research and Application Center Istanbul Technical University, Turkey · Faculty of Engineering and Applied Science Memorial University, Canada

Sep 29, 2026J/K move · Enter open · S save

GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens

Yuxiang Yao, Zijun Zhao

Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology Beijing Institute of Technology

Autoregressive Generation Graph Foundation Models

Open paper AskPDF arXiv

Graph foundation models need a discrete token representation, but casting a graph as a generatable token sequence faces a structural obstacle: edges spanning beyond the serialization window cannot be emitted in one pass--so one-pass autoregressive generators systematically under-produce cycles--and a single global condition cannot tell candidate edges apart. GraphVQ removes both obstacles: node contexts--features plus a local edge mask under multi-order breadth-first serialization--are quantized into a shared codebook by a VQ-VAE with BCE-calibrated Bernoulli edge decoding, and a second-stage structure-aware decoder emits the global adjacency conditioned on token-derived pair features, whose necessity over any global-summary condition is formalized in a scoped impossibility result. The tokenizer reconstructs node features at 0.86--0.99 accuracy and decodes local edges at AUROC >= 0.89 (ECE <= 0.007). Under one same-split protocol on four datasets, pair conditioning improves orbit MMD 0.248 -> 0.174 on PROTEINS and 3.4x on a ring stress test, and vanishes on a random-label control--the signature of attribute--topology coupling--so the gain is claimed exactly where attributes carry edge-relevant signal. GraphVQ ranks first among learned generators on PROTEINS, ties for first on SYN-COMM, and improves orbit MMD 2.7--17x over one-stage generation on three datasets, with seed-level bootstrap intervals confirming the rankings are not seed noise; on MUTAG the unweighted edge target under-generates and is reported as such. These results locate the structural control of autoregressive graph generation in the granularity of the condition: pair-level token context turns a quantized vocabulary into a usable capacity axis for distribution-faithful graph generation and future token-level pretraining.

Abstract

Graph Generation

Explore similar work

GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

GraphK: Variable-Size Graph Generation with Efficient Edge Construction