PaperlayerView exact revision on arXiv

Source-linked AI summary

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth

arXiv:2610.30815v1stat.MLcs.LG

TL;DR

Graph generators face a trade-off between permutation invariance, expressive modeling, and computational efficiency, with dense graphs posing particular generation bottlenecks. xVGAE builds on the Aldous–Hoover representation, learning graph- and node-level latents with a graphon-like decoder. It achieves competitive sample quality across several benchmarks while generating graphs faster than autoregressive and diffusion competitors.

  • Problem

    Graph generation must handle node-permutation invariance and expressive dependencies, while dense graphs can make existing generation methods slow.

    Source: §1 · pp. 1–2

  • Method

    xVGAE uses the Aldous–Hoover representation to learn graph-level and conditionally exchangeable node-level latents, with a decoder that maps them to edge probabilities.

    Source: §1 · p. 2

  • Results

    xVGAE achieves competitive or superior sample quality on MMSBM, LFR, and CiteSeer-Ego, places second on degree and WL for Protein/D&D, and samples faster than every autoregressive and diffusion competitor across datasets.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The learned graph- and node-level latents correlate with properties of community, ego, and protein networks.

    Source: §1 · p. 2

    On Protein/D&D, xVGAE trails GRAN and ILE on clustering, spectrum, and C2ST∆; fixed-dimensional global and local vectors may limit fidelity for irregular, chain-like protein geometries.

    Source: §5.2 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Graph generation must balance permutation invariance and expressive, efficient modeling, yet existing approaches can be slow on dense graphs or sacrifice interpretability. xVGAE uses the Aldous–Hoover representation to organize graph- and node-level latents, enabling one-shot generation with competitive quality and much faster sampling.

1 Introduction

  • Graph generation must respect node-permutation invariance while balancing computational efficiency with the expressivity needed to model dependencies among node pairs.Classical latent-variable models address invariance and tractability, but impose restrictive assumptions on graph structure and edge probabilities.Source: §1 · p. 1
  • Dense moderate-sized graphs expose generation bottlenecks: sequential construction or iterative per-edge updates can be slow, while existing latents offer little semantic decomposition.Scalability-oriented methods may rely on sparsity assumptions that fail in denser settings.Source: §1 · p. 2
  • xVGAE adopts the Aldous–Hoover representation, using graph- and node-level latents without requiring per-edge latent variables.The design targets tractability on dense graphs with hundreds of nodes.Source: §1 · p. 2
  • xVGAE enables one-shot graph generation at speeds orders of magnitude faster than competitors, with quality comparable to them.Its learned latent representations correlate with properties of community, ego, and protein networks.Source: §1 · p. 2

2 Background: Representations of Exchangeable Graphs

Permutation symmetry means that relabeling nodes does not change the graph, and joint exchangeability is its probabilistic analogue. The Aldous–Hoover representation expresses exchangeable graphs through a graph-level latent, exchangeable node-level latents, and a graphon; xVGAE uses this hierarchy as an architectural design principle.

2 Background: Representations of Exchangeable Graphs

  • Relabeling nodes changes an adjacency matrix but not the underlying graph, so probabilistic graph models should respect this symmetry.Permutation-equivariant neural networks and diffusion enforce symmetry architecturally; autoregressive methods use canonical orderings or permutation augmentation.Source: §2 · p. 3
  • The Aldous–Hoover representation characterizes jointly exchangeable graph arrays using a global latent, node-level latents, and a symmetric graphon.The graphon maps the global and node-level variables to edge probabilities; xVGAE replaces uniform latents with learnable Euclidean variables while maintaining exchangeability.Source: §2 · p. 3
  • Classical models such as SBMs, MMSBMs, RDPGs, and LSMs correspond to particular parametric restrictions on the graphon.The global variable represents structure shared across a graph, while node variables encode each node within that structure.Source: §2 · p. 3
  • Although the Aldous–Hoover theorem does not prescribe how to parameterize or learn a graphon from finite data, it motivates a hierarchical latent-space design.With a sufficiently flexible decoder, the global latent indexes a graphon and node latents index positions within it, without explicit per-edge latents.Source: §2 · pp. 3–4

3 A Hierarchical VAE for Exchangeable Graphs

xVGAE uses an Aldous–Hoover-inspired hierarchical VAE to model exchangeable graphs with graph-level and node-level latents, then generates graphs in one decoder pass.

3.1 Generative model

  • The hierarchy uses a global latent z0 and conditionally i.i.d. node latents zi, with edge probabilities given by a symmetric function of the global and paired node latents.The node prior is a z0-conditioned Gaussian mixture, allowing multimodal node distributions such as community structure; z0 mediates dependence across nodes.Source: §3.1 · p. 4
  • The decoder maps node latents to embeddings with a z0-conditioned MLP and symmetric bilinear interaction, preserving a pointwise graphon and exchangeable edge probabilities.An optional set-attention decoder adds flexibility while preserving exchangeability, at the cost of projectivity.Source: §3.1 · pp. 4–5

3.2 Inference model

  • The encoder approximates the posterior with global and local factors whose permutation-invariant and permutation-equivariant symmetries match the generative hierarchy.SABs produce Gaussian parameters from graph features; the global encoder uses Laplacian eigenvalues and invariant attention pooling, while the local encoder is conditioned on z0.Source: §3.2 · p. 5

3.3 Training

  • Training first optimizes a two-level variational lower bound, then fits a latent diffusion prior to encoded global embeddings.The first stage uses a standard normal prior for z0; reconstruction and local KL terms decompose over upper-triangular edges and nodes, respectively, and β is annealed toward 1.Source: §3.3 · p. 5

3.4 Generation of New Graphs

  • A new graph is generated by sampling z0 and conditionally i.i.d. node latents, computing edge probabilities in one decoder pass, and sampling edges independently.The node count can be set freely or sampled from the training set’s empirical node-count distribution.Source: §3.4 · p. 6

3.5 Visualization of the Learned Graph and Node Embeddings

  • The learned global and local latents are inspectable: z0 associates with graph statistics, while zi captures node characteristics such as group membership and Ego hop distance.Figure 2 reports associations with community count, mixing rate, average degree, and node count across four datasets.Source: §3.5 · p. 6, Figure 2 · p. 6

4 Related Work

The related work contrasts xVGAE’s generative use of the Aldous–Hoover representation with graphon estimation and earlier VAE-based graph-generation approaches.

Implicit Graphons

  • Unlike graphon-estimation methods, xVGAE uses the Aldous–Hoover representation as an architectural guide for hierarchical VAE generation without aligning nodes to a canonical uniform space.The cited graphon-estimation approach learns no explicit generative model and uses Gromov–Wasserstein alignment, which the passage describes as slow.Source: §4 · p. 6

VAEs for graph generation

  • Where LGD requires per-node and per-edge latents without a structured prior, xVGAE uses a global z0 and conditionally i.i.d. node latents.The passage says LGD’s unconditional generation results are limited to small graphs and that its latent requirements are costly on the paper’s benchmarks.Source: §4 · p. 6
  • Figure 3 pairs colored test graphs with PCA projections of encoded local latents associated with node characteristics across four datasets.Node colors represent community membership, Ego distance, or Protein Fiedler-vector values, depending on the dataset.Source: Figure 3 · p. 7
  • Figure 4 compares xVGAE with the two top-ranked baselines per dataset using degree, clustering, spectral, and WL MMD2 ratios and generation time.Ratios and seconds per graph use log scales; lower is better, and whiskers show ranges over three draws.Source: Figure 4 · p. 7

5 Experiments

The experiments compare three xVGAE variants with twelve baselines across four synthetic and real-world graph datasets under a uniform compute budget. Results show dataset-dependent quality, very fast xVGAE generation, and graph- and node-level latent variables correlated with graph properties.

5.1 Setup

  • The study compares three xVGAE variants with twelve graph-generative baselines on four datasets under a shared budget of one 48 GB GPU, 12 h training, and 10 h sampling.Reported metrics include degree, clustering coefficient, normalized Laplacian spectrum, 4-node orbit counts, WL subtree-kernel MMD2, and generation time; metrics are scored on the largest connected component across three draws.Source: §5 · p. 7, §5.1 · pp. 8–9

5.2 Results

  • On MMSBM, xVGAE achieves the best clustering (SAB, 1.01), spectral (MLP, 0.44), and C2ST∆ (MLP, 0.032) scores, and generates graphs in <0.02 s/G.It places a close second on WL (MLP, 1.28 vs. 1.27 for EDGE), sampling roughly 8× faster than EDGE and over 200× faster than GRAN.Source: Table 1 · p. 8, §5.2 · p. 9
  • On CiteSeer-Ego, xVGAE-SAB achieves the best C2ST∆ (0.102 vs. 0.148 for EDGE and 0.217 for DiGress) and generates graphs in <0.01 s/G.It places second on clustering (5.20), spectrum (4.97), and WL (3.85; the non-diffusion ablation reaches 3.57), and outperforms DiGress on degree (5.91–8.30 vs. 10.9).Source: Table 2 · p. 9, §5.2 · pp. 9–10
  • On LFR, xVGAE-SAB achieves the best clustering (2.50) and spectral (1.17) MMD2 ratios, while xVGAE samples at <0.01 s/G.It trails EDGE and DiGress on degree, WL, and C2ST∆; generation is roughly 5× faster than EDGE and over 3,000× faster than DiGress.Source: §5.2 · p. 9
  • On Protein/D&D, xVGAE-SAB places second on degree (17.9) and WL (7.46) behind GRAN, but trails GRAN and ILE on clustering, spectrum, and C2ST∆.xVGAE samples in <0.01 s/G versus 0.82 s/G for GRAN and 14.5 s/G for ILE; the authors suggest fixed-dimensional global and local vectors limit fidelity for irregular, chain-like protein geometries.Source: §5.2 · p. 10
  • The global latent z0 correlates with graph properties, while local latents zi reflect node-level structure across the four datasets.Reported associations include community count, mixing, average degree, and node count for z0, and community membership, ego-node hop distance, and the Fiedler vector for zi.Source: §5.2 · p. 10

6 Conclusion

xVGAE uses an Aldous–Hoover-guided, two-level latent structure to generate exchangeable graphs, with competitive quality and faster sampling across several benchmarks. Its scope and theory leave open questions about broader graph types and neural-decoder expressivity.

6 Conclusion

  • The Aldous–Hoover-guided model uses graph-level z0, conditionally i.i.d. node latents zi, and a graphon-like map to generate edges.The latent variables empirically capture global graph structure and node-level variation, respectively.Source: §6 · p. 10
  • Theoretical derivations are still needed to establish when a neural decoder can approximate arbitrary measurable symmetric kernels on finite graphs.Source: §6 · p. 10
  • xVGAE matches or exceeds strong baselines on MMSBM, LFR, and CiteSeer-Ego, places second on Protein/D&D degree and WL, and samples faster than autoregressive and diffusion competitors on every dataset.The reported speed advantage ranges from about 2× over EDGE to three orders of magnitude.Source: §6 · p. 10
  • The current evaluation focuses on binary adjacency matrices, while the framework is described as extendable to weighted edges, edge attributes, and node features or labels.Extensions to bipartite, directed, and other asymmetric structures are also proposed through separately or partially exchangeable arrays.Source: §6 · p. 10
  • Synthetic graph deployment requires attention to training-data structural biases and distributional limitations, with responsible and transparent use.Source: §6 · p. 10

A Datasets

The evaluation uses four structurally distinct graph-generation benchmarks, spanning real citation and protein graphs and synthetic community networks. Their origins, construction, and benchmark roles establish the scope of the dataset suite.

A Datasets

  • The benchmark suite covers real-world citation topology, synthetic community and power-law graphs, and biological protein-contact networks.Table 3 summarizes benchmark statistics, including split counts and per-graph averages for node count, density, and mean degree.Source: A Datasets · p. 15, Table 3 · p. 15

A.1 CiteSeer-Ego

  • CiteSeer-Ego graphs are undirected, self-loop-free three-hop citation ego-networks with a hub-and-spoke structure, following preprocessing used in prior generation benchmarks.The dataset has been used by GraphRNN, SPECTRE, DiGress, GRAN, and other graph-generation papers.Source: §A.1 · p. 15

A.2 MMSBM

  • MMSBM graphs vary community count K and membership concentration α per graph, testing whether models reproduce graph-specific modular structure rather than only a dataset-average pattern.The benchmark is the suite’s densest corpus, and ILE runs out of GPU memory on it.Source: §A.2 · pp. 15–16

A.3 LFR

  • LFR graphs combine power-law degree and community-size distributions with a graph-specific mixing parameter µ, and are included to test generation on large, heavy-tailed community graphs.The benchmark is rarely used to evaluate generative models; its graphs reach 500 nodes.Source: §A.3 · p. 16

A.4 Protein (D&D)

  • Protein/D&D graphs represent amino-acid contact networks and provide a heterogeneous real-world setting, with graph sizes from 100 to 500 nodes and substantial local-density variation.Node labels are not used; the evaluated models receive graph structure only.Source: §A.4 · p. 16

A.5 Comparison: dataset structural regimes

The benchmark suite spans distinct graph structures, and the evaluation compares generated graphs with held-out test graphs using kernel-based and classifier-based two-sample metrics. The metrics target different structural summaries, with known saturation caveats for orbit MMD.

A.5 Comparison: dataset structural regimes

  • The evaluation also spans four structurally distinct regimes, from real-world citation and protein networks to synthetic community benchmarks.Source: §A.5 · p. 17
  • The four regimes are sparse hub-and-spoke citation graphs, dense mixed-membership communities, large power-law community graphs, and heterogeneous protein networks.The suite is designed to test, respectively, topology and size variability, per-graph community variation, tail fidelity, and joint size-topology calibration.Source: §A.5 · p. 17

B Metrics: Explanation and Discussion

  • Generated graphs are evaluated against the test set with five kernel-based MMD2 tests and one classifier two-sample test, all computed on each graph’s largest connected component.Source: B Metrics: Explanation and Discussion · p. 17

B.1 MMD2 framework

  • MMD2 is reported as a ratio to the train–test value for the same statistic; a ratio of 1 means generated graphs are as close to test graphs as held-out real graphs are.The training set is subsampled to test-set size, and the denominator is averaged over five subsamples.Source: §B.1 · p. 17

B.2 Histogram metrics: degree, clustering, spectral

  • Degree, clustering, and spectral MMD compare normalized histograms of node degrees, local clustering coefficients, and normalized Laplacian eigenvalues, respectively.These summaries capture marginal degree distributions, local triangle density, and global mixing or modular structure.Source: §B.2 · p. 17

B.3 Orbit MMD

  • Orbit MMD counts node participation in 15 graphlet orbits with up to four nodes, averages counts across nodes, and applies a Gaussian-TV kernel.The orbit kernel saturates on MMSBM and LFR, and those corpora are marked accordingly.Source: §B.3 · pp. 17–18

B.4 Weisfeiler–Leman MMD (wl)

  • WL MMD uses a hashed bag of Weisfeiler–Leman labels after four refinement rounds and computes MMD2 with a linear kernel in that feature space.The paper describes WL as a stable ranker that captures local motifs at multiple scales and is robust to graph scale and size differences.Source: §B.4 · p. 18

B.5 Classifier Two-Sample Test (C2ST)

C2ST measures how well a classifier separates real from generated graphs, while reporting conventions standardize metric direction, graph preprocessing, and flags for saturated or collapsed results.

B.5 Classifier Two-Sample Test (C2ST)

  • C2ST∆ is the absolute deviation of held-out classifier accuracy from chance: 0 means indistinguishable distributions, while 0.5 means perfect separability.A logistic-regression classifier uses untrained three-layer GIN embeddings and five-fold cross-validation.Source: §B.5 · p. 18

B.6 Reporting conventions

  • All metrics use largest connected components; lower is better, MMD2 values are ratios to train–test values, † marks saturated orbit columns, and ∗ marks collapsed samples.Collapsed rows are degenerate under the paper’s stated component-size or edge-count criteria.Source: §B.6 · pp. 18–19
  • Table 4 covers LFR graphs with 200–500 nodes and approximately 3.7% density, while Table 5 covers Protein/D&D graphs with heterogeneous density.Source: Table 4 · p. 19, Table 5 · p. 19

C.1 Compute limits, protocol and baseline notes

The appendix specifies shared compute limits, evaluation and checkpoint-selection protocols, and sampling timings, while documenting baseline training and implementation caveats.

C.1 Compute limits, protocol and baseline notes

  • ILE alone fails at batch size 1 from CUDA out-of-memory errors on dense MMSBM and LFR graphs under the stated limits.The reported failures arise in sparse PPGN message aggregation over edge triples.Source: §C.1 · p. 20
  • Every model receives one GPU, 12 hours of training, and 10 hours of sampling; some baselines remain undertrained within this shared budget.The authors report undertraining for specified LGD, SPECTRE, SparseDiff, and EDGE runs; GRAN completes its stated epochs on every dataset.Source: §C.1 · p. 20
  • Baselines use public code and upstream hyperparameters where possible, with shared splits, scoring, validation-based selection, and test scoring only for the selected checkpoint.Selection averages draws, ties candidates within 10% by C2ST accuracy closest to 0.5, and reports medians of three sampling draws with ranges.Source: §C.1 · p. 20
  • The DiGress-lean memory fix leaves the model, loss, noise schedule, and sampler unchanged, with seeded CPU checks yielding identical losses and weights.A float64 option is used for cycle-count features on MMSBM and LFR after float32 values exceeded the exact-integer range and stopped training.Source: §C.1 · p. 21

C.2 Sampling protocol

  • Sampling speed is timed on one RTX 6000 Ada across batch sizes, with reported seconds per graph taken from the fastest tested setting.Timing covers the full generation pipeline, including denoising or Langevin steps, decoding, and edge sampling, but excludes model loading.Source: §C.2 · p. 21

C.3 Orbit metric on LFR and MMSBM

The standard orbit kernel saturates on MMSBM and LFR, making its reported ratio uninformative for distinguishing model fit there.

C.3 Orbit metric on LFR and MMSBM

  • With Gaussian width 30 on TV distance between node-averaged ORCA count vectors, the standard orbit kernel is numerically 0 for distinct MMSBM test graphs (median distance about 2 × 10^5).Source: §C.3 · p. 21
  • On MMSBM and LFR, orbit-kernel saturation makes the ratio close to 1 even for models whose generated graphs are far from the data.The summed kernel gives the same biased MMD2 value for held-out real graphs, degree-preserving rewires, and Erdős–Rényi graphs with matching edge counts.Source: §C.3 · p. 22

D.1 Configurations per Dataset

The appendix details xVGAE configurations and decoder parameterisations, then illustrates how encoded graph- and node-level latents relate to structural properties and shows generated graph examples.

D.1 Configurations per Dataset

  • xVGAE configurations share a five-layer set-attention encoder and specify dataset-specific decoders, latent dimensions, and training schedules.The configurations use either a five-layer set-attention or pointwise MLP decoder; six diffusion-prior models follow the standard schedule, with a CiteSeer-Ego exception.Source: §D.1 · p. 22, Table 9 · p. 22

D.2 Chunked Bilinear Decoder and W Parameterisations

  • The decoder logit mixes chunk-specific bilinear forms over node embeddings, with graph-level weights and bias; the MLP also uses node and pair terms.The chunks make the heads distinct, and the reported models use low-rank W_mod with r = 4.Source: §D.2 · p. 23

E.1 Per-graph latent variables

  • Global latent variables associate with graph statistics across MMSBM, Ego, LFR, and Protein, including degree and clustering measures.The plotted associations also include graph size and dataset-specific properties such as community count, Ego-node degree, mixing parameter, and algebraic connectivity.Source: Figure 5 · p. 23, Figure 6 · p. 24, Figure 7 · p. 24

E.2 Per-node latent variables

  • Encoded node latents reflect structural labels or position in MMSBM, Ego, LFR, and Protein despite inference using adjacency information.The figures describe patterns involving community membership, membership distribution, Ego-node distance, relative degree, and Fiedler-vector colors.Source: Figure 9 · p. 25, Figure 10 · p. 26, Figure 11 · p. 27

F Illustrated Graphs with spring layout

Related papers

Loading 2610.30815v1…