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

Yuxiang Yao; Zijun Zhao

cs.LGSep 29, 2026

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

Authors: Yuxiang Yao, Zijun Zhao

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

Abstract

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.

Figures & tables

Figure 1: The three stages of GraphVQ . Stage 1 (training): the graph is serialized in BFS order (random roots/tie-breaking, multi-order augmentation); each node context $c_{i}$ —one-hot features plus an edge mask over the preceding $W$ nodes—is encoded, quantized to the nearest codebook entry (the discrete token), and decoded into features and BCE-calibrated edge probabilities. Stage 2 (training): a GRU prior factorizes the token sequence. Stage 3 (inference): Stage A samples node tokens and decodes features; Stage B builds per-pair features $r_{ij}$ , chunks the upper triangle into $B$ -bit groups, and autoregressively emits each chunk from a GRU whose input pools the chunk’s pair features; padding bits are forced to zero and the symmetrized matrix is the generated graph. Solid arrows: forward flow; dashed: training objectives.

	Datasets (deg / clu / orb / spc MMD, conn)
Method	MUTAG	PROTEINS	SYN-RING-ROLE	SYN-COMM
One-stage	.331/.928/.729/.105/.65 (6.60)	.275/ .755 /.474/.047/.67 (4.30)	.108/.032/.079/.069/.82 (4.00)	.067/.076/.150/.092/.28 (5.10)
Continuous	.297/.871/ .437 / .090 /.13 (3.20)	.281/1.142/.304/ .039 /.38 (4.15)	.287/.400/.159/.064/.74 (6.40)	.791/.502/.665/.074/1.00 (8.90)
Raw	.414/.895/.605/ .081 /.09 (5.60)	.182 /1.031/.209/ .044 /.67 (3.15)	.017 / .011 / .014 /.042/.50 (2.65)	.006 / .022 / .013 /.051/.36 (2.40)
GraphRNN	.313/ .850 / .401 / .090 /.17 (2.95)	.198/1.070/.301/.059/.44 (4.40)	.177/.623/.148/.038/.92 (5.85)	.066/.029/.211/ .010 /.72 (3.50)
GRAN	.344/.904/.592/.117/.92 (6.30)	.446/1.125/.449/.079/.85 (6.75)	.333/.448/.206/ .018 /.99 (5.35)	.340/.146/.499/.028/.96 (5.70)

Table 1: Same-split generation quality: mean over five seeds,

10{,}000

samples per seed; MMD = kernel MMD 2 (median bandwidth, identical for all methods); conn. = connectivity. Mean rank is the pre-registered primary metric over degree/clustering/orbit/spectral MMDs (ten methods, resample floor excluded, average ranks for ties; block rank sums verify to

55

). Bold = best, underline = second-best per MMD column; ties share the mark.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$G=(V,E,X)$ , $N$	graph, node set, feature matrix $X$ , size
$A$ , $\pi$	adjacency matrix; BFS order of nodes
$c_{i}=[x_{i};\,e_{i}]$	node context: features $x_{i}$ + local edge mask $e_{i}$
$W$ , $K$	edge-mask window; codebook size
$E{=}\{e_{1},\dots,e_{K}\}$	codebook, entries $e_{j}\!\in\!\mathbb{R}^{h}$
$t_{1},\dots,t_{n}$	token sequence of a graph, SOS/EOS-wrapped

Appendix

Table A.1: Key notation.

Figure B.1: Condition dependence of the trained Stage-B decoder on held-out MUTAG graphs (unweighted target). Removing the condition raises positive-edge NLL $1.836\!\to\!1.879$ and globally shuffling the pair features raises it to $2.086$ ( $+13.6\%$ ); permuting pair features within a chunk changes nothing—the chunk pool is a masked mean.

Figure B.2: Edge coverage of the BFS serialization window as a function of $W$ , versus random orderings, on the TUD benchmarks (MUTAG/ENZYMES/PROTEINS/NCI1). BFS keeps edges local ( $\geq\!93\%$ coverage at $W{=}8$ and $\geq\!98\%$ at $W{=}16$ ); the uncovered remainder—long-span edges—breaks the cycles and motifs that contain them, motivating Stage B.

Figure B.3: Representable edge fraction of the BFS serialization window versus random orderings on the generation benchmarks (random-root BFS, five orders averaged). BFS keeps $\geq\!88\%$ of edges within $W{=}8$ and $0.98$ – $1.00$ within $W{=}16$ ; the residual long-span edges are what one-stage generation cannot emit.

Figure B.4: The condition’s value is dataset-dependent. An independently trained unconditional decoder matches the conditioned one on MUTAG and SYN-RING-ROLE but loses by $1.6\times$ on PROTEINS and $9\times$ on SYN-COMM (orbit MMD, log scale; connectivity on the right).

Figure B.5: Edge NLL (nats/bit) of held-out graphs under three Stage B conditions: oracle (true-feature tokens), reconstructed (deterministic Stage-A reconstruction), and generated (one prior sample). The oracle-to-generated gap is $\leq\!0.009$ nats/bit on MUTAG/PROTEINS and substantially larger on the synthetic benchmarks, where the token prior’s samples diverge most from true conditions. The gap alone is not a transfer certification—a decoder that ignored its condition would show the same pattern—so condition-dependence controls accompany it (Sec. 4 ).

Figure B.6: Weighted BCE re-targets density rather than calibrating probability. The optimum of the weighted loss is $q^{*}{=}wp/(wp{+}1{-}p)$ (red curve), so $w{=}3$ fits a true edge probability of $0.1$ by $0.25$ ; the fitted model (red dot) and its Bernoulli sampling rate (star) track $q^{*}$ , not the true $p$ . Unweighted BCE stays on the diagonal (blue).

Figure B.7: Degree distributions of training graphs versus generated samples on MUTAG (unweighted Stage-B). Probability mass shifts toward low degrees relative to training (connectivity $0.11$ vs. $1.00$ ), the honest cost of the unweighted edge target reported in Table 1 .

Figure B.8: Qualitative samples on MUTAG: training graphs (top row; node colors denote labels), one-stage generation (middle), and GraphVQ two-stage generation with the unweighted edge target (bottom). Two-stage decoding restores denser motifs than one-stage sampling; residual under-generation remains (cf. connectivity $0.11$ in Table 1 ).

Dataset	#Graphs	Avg. $\|V\|$	Avg. $\|E\|$	Feat. dim	Labels
MUTAG	188	17.9	19.8	7	random
PROTEINS	1113	39.1	72.8	3	random
SYN-RING-ROLE	400	10–30	—	4	role-corr.
SYN-RING	400	10–30	—	4	random
SYN-COMM	400	15–40	—	3	community

Appendix

Table C.1: Dataset statistics. Avg.

|V|

and avg.

|E|

are means over graphs. SYN-RING is the random-label falsification control of SYN-RING-ROLE.

Component	VQ	Continuous	Raw
Tokenizer / autoencoder	3,623	2,599	—
Autoregressive prior	14,882	15,840	13,481
Stage-B decoder	20,744	20,744	20,744
Total	39,249	39,183	34,225

Appendix

Table C.2: Parameter budgets of the three component-attribution variants (MUTAG instance; all three share the same Stage-B decoder).

Ablation	Dataset	Setting	orbit MMD	conn.
Condition	PROTEINS	mean vs. pair	.248 vs. .174	.406 vs. .693
Condition	SYN-RING-ROLE	mean vs. pair	.030 vs. .009	.605 vs. .578
Condition	SYN-RING (control)	mean vs. pair, random labels	.017 vs. .027 (n.s.)	.479 vs. .521
Density reweight	MUTAG	$w_{+}=1/3/5$	.523/.387/.536	.136/.672/.804
Corruption	PROTEINS	$\rho=0/.15/.3$	.211/.174/.175	.647/.693/.718

Appendix

Table C.3: GraphVQ conditioning ablations (means over three seeds; P0 protocol).

Ablation	Setting	Result
Ordering	8-order NLL: fixed/random/multi8 BFS (MUTAG)	1.441 / 1.486 / 1.096
Ordering	connectivity: fixed/multi8 (MUTAG)	0.650 / 0.984
Ordering	DFS/deg-desc/random vs. BFS (MUTAG)	conn. .56/.03/.02 vs. .80
Stage-B head	within-chunk AR vs. indep. Bernoulli (SYN-RING)	orbit .020 vs. .032
Stage-B readout	pooled vs. per-pair (MUTAG/SYN-RING)	orbit .642 vs. .777 / .032 vs. .034
Attr-only ctx	remove edge mask (MUTAG / SYN-RING)	orbit .590 / 1.166; conn $\approx\!0$

Appendix

Table C.4: GraphVQ order and Stage-B ablations (means over three seeds).

Metric	MUTAG	PROTEINS	SYN- RING-ROLE	SYN- COMM
Feature acc. $\uparrow$	0.857	0.987	0.934	0.990
Feature CE $\downarrow$	1.325	0.572	0.801	0.568
Edge AUROC $\uparrow$	0.994	0.950	0.993	0.892
Edge AUPRC $\uparrow$	0.970	0.843	0.989	0.761
Edge Brier $\downarrow$	0.016	0.065	0.029	0.075
Edge ECE $\downarrow$	0.003	0.005	0.004	0.007

Appendix

Table D.1: GraphVQ tokenizer fidelity on held-out splits (seed 0; reconstructed-graph structural MMDs against the true graphs).

Dataset	degree	clustering	orbit	spectral
MUTAG	.423 [.362,.516]	.897 [.884,.916]	.598 [.504,.730]	.074 [.065,.081]
PROTEINS	.163 [.150,.178]	1.031 [1.018,1.046]	.175 [.151,.198]	.044 [.043,.045]
SYN-RING-ROLE	.015 [.011,.020]	.013 [.004,.028]	.012 [.008,.017]	.086 [.081,.091]
SYN-COMM	.005 [.003,.007]	.015 [.012,.017]	.009 [.006,.012]	.057 [.055,.060]

Appendix

Table D.2: GraphVQ mean [bootstrap 95% CI] over five seeds.

Baseline	MUTAG	PROTEINS	SYN- RING-ROLE	SYN-COMM
One-stage	.202 (n.s.)	$<$ .001	$<$ .001	.002
Continuous	.030 †	.235 (n.s.)	.020	$<$ .001
Raw	.908 (n.s.)	.502 (n.s.)	.155 (n.s.)	.245 (n.s.)
GraphRNN	.049 †	.010	$<$ .001	$<$ .001
GRAN	.928 (n.s.)	$<$ .001	$<$ .001	$<$ .001
GraphVAE	.923 (n.s.)	$<$ .001	$<$ .001	$<$ .001

Appendix

Table D.3: Paired

t

-test

p

-values vs. GraphVQ on orbit MMD (five seeds; n.s. marks

p\geq 0.05

;

\dagger

marks baselines significantly better than GraphVQ ).

Metric	MUTAG	PROTEINS	SYN- RING-ROLE	SYN- COMM
Cond. NLL pos. (nats/bit)	1.943	2.335	0.281	1.436
Cond. NLL neg. (nats/bit)	0.125	0.046	0.097	0.127
Cond. Brier pos.	0.707	0.739	0.102	0.518
Cond. Brier neg.	0.015	0.005	0.014	0.029
Cond. ECE pos.	0.822	0.762	0.489	0.720
Cond. ECE neg.	0.116	0.185	0.107	0.109

Appendix

Table D.4: GraphVQ ’s unweighted conditional Stage-B metrics on held-out graphs under true conditions (mean over five seeds), and train- vs. test-reference orbit MMD of free generation (same fixed splits).

Dataset	Tokenizer	Active / $K$	Dead rate	Perplexity	Gini
MUTAG	context	12/32	.625	9.49	.76
	feature-only	4/32	.875	2.30	.94
PROTEINS	context	23/32	.281	14.01	.66
	feature-only	3/32	.906	2.20	.94
SYN-RING-ROLE	context	10/32	.688	6.05	.85
	feature-only	4/32	.875	3.37	.91

Appendix

Table D.5: GraphVQ codebook diagnostics (seed 0). Context = full node context (features + edge mask); feature-only = attributes without the edge mask.

Autoregressive Generation

Autoregressive generation creates structured outputs step by step, conditioning each prediction on what has already been generated.

See all 109 papers

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs
Oct 22, 2026Daniele Micheletti, Federica Zoe Ricci, Erik B. SudderthGraph Generation Variational Autoencoders
University of California, Irvine · Swarthmore College
WL-SeqVAE: Sequence-Based Graph Generation Using Variational Autoencoders and Weisfeiler-Leman Colors
Oct 23, 2026Iakovos Evdaimon, Giannis Nikolentzos, Achilleas Tsimichodimos +2Graph Generation Molecular Graph Generation
´Ecole Polytechnique, IP Paris, France · University of Peloponnese, Greece · National Technical University of Athens, Greece +1
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

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

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth

University of California, Irvine · Swarthmore College

Graph Generation Variational Autoencoders

Open paper AskPDF arXiv

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.

Abstract

Autoregressive Generation

Explore similar work

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

WL-SeqVAE: Sequence-Based Graph Generation Using Variational Autoencoders and Weisfeiler-Leman Colors

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models