xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs
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.
Related
- Theoretical Study on the Evidential Learning-based Variational Autoencoder
- An Elastic Shape Variational Autoencoder for Skeleton Pose Trajectories
- A novel Weighted Exponential-Lindley distribution with Bayesian estimation under progressive Type-II censoring and a Bayesian-Calibrated Variational Autoencoder for survival prediction.
- A Hierarchical Bayesian Cox Model with Variational Inference for High-Dimensional Survival Analysis
- Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs
BibTeX
@misc{micheletti2026xvgae,
title = {{xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs}},
author = {Daniele Micheletti and Federica Zoe Ricci and Erik B. Sudderth},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30815},
eprint = {2610.30815},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30815},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs
AU - Daniele Micheletti
AU - Federica Zoe Ricci
AU - Erik B. Sudderth
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.30815
UR - https://arxiv.org/abs/2610.30815
AB - 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.
ER -