Generalized Graph Variational Autoencoders: Bounded Divergences Control Posterior Collapse

Kleyton da Costa; Bernardo Modenesi; Ivan F. M. Menezes; Helio Lopes

cs.LGAug 25, 2026

Generalized Graph Variational Autoencoders: Bounded Divergences Control Posterior Collapse

Authors: Kleyton da Costa, Bernardo Modenesi, Ivan F. M. Menezes, Helio Lopes

Organizations: UCL & Holistic AI London, UK · University of Utah Salt Lake City, US · PUC-Rio Rio de Janeiro, Brazil

Abstract

The variational graph autoencoder (VGAE) regularizes its posterior toward the prior with the Kullback-Leibler divergence, a choice inherited from the variational autoencoder rather than argued for. We introduce the generalized graph variational autoencoder (GGVA), which replaces that term with any member of the Rényi-Tsallis family of order $q$ while leaving every other part of the model untouched. Both members admit closed forms for diagonal Gaussians and both recover the KL exactly as $q \to 1$ , so the VGAE is the $q=1$ arm of our own model rather than a separate baseline, and any measured difference is attributable to a single scalar. Our analysis identifies boundedness, not the order, as the operative property: for $q<1$ the Tsallis divergence is bounded above by $1/(1-q)$ , independently of the latent width, whereas the KL and the Rényi divergence of the same order are unbounded. On ten graphs spanning three synthetic families, a social network, three citation networks, a connectome, a power grid and a road network, $q$ moves the retained posterior information by up to $49\times$ relative to the VGAE, while the Rényi arm at the same order stays within $1.02$ - $1.30\times$ of it on all six larger real graphs (isolating the bound as the cause). The retained information is usable: probing the frozen embedding for node class, a label absent from the objective, gives GGVA up to $+0.14$ macro-F1 over the VGAE on CiteSeer, with the Rényi control again tracking the VGAE. We also report what the design was built to expose: none of this reaches held-out link-prediction accuracy on any of the six larger real graphs, and boundedness delays posterior collapse rather than preventing it.

Figures & tables

Figure 1: The shape of the response differs, not just its scale. Held-out AUC (top) and retained posterior information in KL nats (bottom) against the penalty weight

c

, for four objectives. The VGAE, Tsallis

q{=}0.8

and Rényi

q{=}0.5

decay steadily; Tsallis

q{=}0.5

holds a rich posterior across two decades and then falls off a cliff. A pure magnitude effect would shift a curve sideways, not change its shape. Bands are 95%

t

-intervals over five seeds. Four of the ten graphs are shown; the rest are in Appendix C .

Figure 2: No arm separates in aggregate link-prediction accuracy. Critical-difference diagram for six arms over ten graphs. All mean ranks lie in one Nemenyi clique (

\mathrm{CD}=2.384

\alpha=0.05

		Posterior KL (nats/node)			Mean AUC
Objective	Bound	SBM	Cora	PubMed	(6 larger real)
VGAE (KL, $q{=}1$ )	$\infty$	1.63	10.13	17.59	0.7764
Tsallis $q{=}0.5$	2.00	55.50	112.99	48.46	0.7789
Tsallis $q{=}0.8$	5.00	3.34	109.83	47.74	0.7788
Tsallis $q{=}0.95$	20.0	1.92	15.16	27.80	0.7746
Tsallis $q{=}1.5$	$\infty$	0.60	2.65	4.51	0.7552

Table 1: Retained posterior information is ordered by

q

; the Rényi control is not. Posterior KL in nats per node at

c=100

, mean over five seeds, measured with the KL for every arm regardless of its training objective. “Bound” is Proposition 1 . The last column is held-out AUC averaged over the six larger real graphs. Tsallis

q{=}0.5

retains

2.8

–

49\times

the VGAE’s information across all ten graphs, while Rényi at the same order stays within

1.02

–

1.30\times

of it on the six larger real graphs; accuracy is flat throughout. All ten graphs in Appendix C .

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: The response in

q

, with the mechanism measured. Held-out AUC (top), retained posterior information (middle), and the trained penalty as a fraction of its

1/(1-q)

ceiling (bottom). The dashed line is the VGAE, which is the

q{=}1

point of the same curves. The shaded region is where the Tsallis penalty is bounded; the saturation row exists only there, because an unbounded penalty has no ceiling to be a fraction of. Below

q\approx 0.7

the penalty is pinned at its ceiling and the orders become indistinguishable.

Figure 4: Frozen-embedding probes. Linear-probe macro-F1 (top), clustering NMI (middle) and effective rank (bottom) against the penalty weight

c

. Node class is never seen by any model. On the citation networks the VGAE’s probe degrades as

c

grows while Tsallis

q{=}0.5

holds; the Rényi control at the same order tracks the VGAE. The Erdős–Rényi panel carries random labels. Every arm sits at chance through

c\leq 10^{3}

; at

c=10^{4}

all arms degenerate and macro-F1 falls below chance.

Model	BA	C. elegans	CiteSeer	Cora	ER control
Rényi $q=0.5$	$\mathbf{0.689\pm 0.045}$	$0.829\pm 0.045$	$0.864\pm 0.018$	$0.860\pm 0.009$	$0.520\pm 0.050$
Tsallis $q=0.5$	$0.654\pm 0.079$	$0.837\pm 0.020$	$\mathbf{0.870\pm 0.018}$	$\mathbf{0.864\pm 0.005}$	$0.513\pm 0.026$
Tsallis $q=0.8$	$0.687\pm 0.045$	$0.825\pm 0.030$	$0.870\pm 0.019$	$0.864\pm 0.006$	$0.518\pm 0.060$
Tsallis $q=0.95$	$0.686\pm 0.045$	$0.818\pm 0.050$	$0.866\pm 0.018$	$0.855\pm 0.019$	$0.525\pm 0.059$
Tsallis $q=1.5$	$0.618\pm 0.050$	$\mathbf{0.839\pm 0.033}$	$0.824\pm 0.017$	$0.800\pm 0.033$	$\mathbf{0.527\pm 0.056}$
VGAE (KL, $q=1$ )	$0.680\pm 0.042$	$0.835\pm 0.033$	$0.864\pm 0.017$	$0.859\pm 0.007$	$0.522\pm 0.063$

Appendix

Table 2: Held-out AUC for every graph and arm at

c=100

. Members of the Rényi–Tsallis family act as the latent penalty at

\mathrm{kl\ scale}=100/N

. Entries are mean

\pm

standard deviation over five seeds. The VGAE is the

q=1

arm; only the divergence differs. BA is Barabási–Albert and ER is the Erdős–Rényi negative control.

Figure 5: Held-out AUC over the complete ten-graph weight sweep. This is the full-suite counterpart of the top row of Figure 1 .

Figure 6: Retained posterior KL over the complete ten-graph weight sweep. This is the full-suite counterpart of the bottom row of Figure 1 .

Figure 7: Frozen-embedding label probes over all ten graphs. Macro-F1 (top) and clustering NMI (bottom) extend Figure 4 to the full suite. Labels are unavailable on graphs where a probe is undefined.

Figure 8: Effective rank over the complete ten-graph sweep. This continuous diagnostic complements the thresholded active-unit count.

Variational Autoencoders

Variational autoencoders are probabilistic encoder–decoder models for learning latent representations, generating data, and estimating uncertainty.

See all 204 papers

Oct 22, 2026

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

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.

Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth

University of California, Irvine · Swarthmore College

Graph Generation Variational Autoencoders

Ask PDF

Jul 6, 2026

$\mathbfλ$ -VAE: Variance Equalization for Posterior Collapse

Variational Autoencoders (VAEs) frequently suffer from posterior collapse, a failure mode in which the approximate posterior converges to the prior, rendering the latent code uninformative. Despite extensive research, a unified account of why collapse occurs has remained an open question. We identify and formalize two logically independent but coupled causes. Gradient imbalance occurs when the decoder's reconstruction signal vanishes faster than the

\mathbb{KL}

regularization pressure as the posterior widens. Information gap occurs when the stochastic sampling step discards a substantial fraction of the encoder's computed representation, attenuating decoder sensitivity and making collapse inexpensive. Both causes share the same collapse trajectory, and we show that the information gap is algebraically equivalent to mismatch between the aggregate posterior and the prior, unifying two pathologies. Subsequently, we introduce

λ

-VAE, which resolves both causes through a single modification to the reparameterization step: the sampling noise is scaled by per-dimension exponent, while the

\mathbb{KL}

penalty retains the original posterior variance. This asymmetry shifts the stable training attractor away from the degenerate collapsed state, driving all latent dimensions toward the same equilibrium -- a mechanism we term variance equalization. A closed-form optimal exponent per dimension follows from a net information gain objective, with a single hyperparameter controlling the reconstruction-generation tradeoff. We validate on standard benchmarks (Binary MNIST, Binary Omniglot, CIFAR-10, CelebA-64), showing consistent reductions in collapsed dimensions, information capacity gains of up to

2.8\times

nats, and reconstruction quality improvements of up to

+0.33

BPD.

Girum Demisse

Microsoft African Development Center Nairobi Kenya

Variational Autoencoders Posterior Collapse

Ask PDF

May 15, 2026

GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance

We introduce GraViti, a transformer-based graph-level variational autoencoder that encodes entire graphs into single, fixed-dimensional latent vectors rather than per-node embeddings, yielding a graph-level latent space that supports smooth interpolation, property-guided search, and other downstream tasks beyond the reach of node-level approaches. GraViti achieves state-of-the-art reconstruction accuracy on large molecular graph datasets while offering competitive single-step generative performance. Our central finding concerns where permutation invariance is needed in such a model, and where it is not. The encoder remains permutation-invariant throughout, ensuring the model generalizes to graphs regardless of input order. The reconstruction loss, however, does not need to be: when training data is provided in a consistent node order, comparing predictions to targets directly in that order, without a graph-matching step, is sufficient. Relaxing invariance in the loss alone lets GraViti avoid the cubic-cost matching step required by prior graph-level autoencoders, reducing complexity to quadratic while improving reconstruction fidelity. We show the resulting latent space is chemically meaningful, supporting controlled molecular editing and property optimization, recovering established chemical trends, and enabling direct regression of graph-level properties from latent embeddings.

Roman Bresson, Konstantinos Divriotis, Johannes F. Lutzeyer +2

Mohamed bin Zayed University of Artificial Intelligence · LIX, CNRS, École Polytechnique, IP Paris

Molecular Generation Molecular Representation Learning Molecular Graph Generation Variational Autoencoders Invariant Representation Learning Graph Transformer+1

Ask PDF

Abstract

Variational Autoencoders

Explore similar work

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

λ\mathbfλλ-VAE: Variance Equalization for Posterior Collapse

GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance

$\mathbfλ$ -VAE: Variance Equalization for Posterior Collapse