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 scale and exhibit prohibitively-slow generation times. We propose a generative architecture that matches or exceeds the state-of-the-art, but can scale to regimes where their training fails, 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 (i.e., exchangeable). This theorem establishes that three ingredients are needed: a graph-level variable, a set of node-specific 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 interpretable representations of graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.