Exchangeable graph model speeds up accurate graph generation
xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs
Machine Learning
Summary
Graphs help describe connections in things like social networks or molecules. The authors found that some current graph-generating methods are slow or hard to train. They created a new model called xVGAE that uses a mathematical idea about how graph data can be broken down into group and node parts. This model can quickly generate new graphs that behave like the examples it learned from, matching important features well.
What this means in practice
- •For drug discovery teams: Generate realistic molecular graphs much faster to support rapid virtual screening.
- •For social network analysts: Create synthetic social network graphs quickly that preserve key connectivity features for testing and simulation.
Authors
Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth
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.