Dirichlet Graph Variational Autoencoder

Jia Li, Jianwei Yu, Honglei Zhang, Kangfei Zhao, Yu Rong, Hong Cheng, Junzhou Huang

Introduction

Graph Neural Networks (GNNs) and Variational Autoencoders (VAEs) have become standard tools for modeling and generating graphs. However, standard Graph Variational Autoencoders (GVAEs) suffer from a "black box" problem. Typically, these models map nodes to a Gaussian distribution in their latent space. While mathematically convenient, these latent factors lack a clear physical or structural meaning, leaving researchers in the dark about what the model is actually learning regarding the graph's topology.

Furthermore, the standard encoder used in these models—the Graph Convolutional Network (GCN)—has been criticized for being an imperfect "low-pass filter." In graph signal processing, an effective low-pass filter should retain smooth, structural information (low-frequency) while discarding noise (high-frequency). GCNs often fail to suppress high-frequency noise effectively, leading to suboptimal reconstruction and clustering.

To address these issues, researchers have introduced the Dirichlet Graph Variational Autoencoder (DGVAE). By replacing standard Gaussian latent variables with Dirichlet distributions and introducing a superior low-pass GNN layer called Heatts, this framework provides a more interpretable and higher-performing approach to graph generation and clustering.

Methodology: Dirichlet Factors and Heatts

The DGVAE framework introduces two major architectural innovations to solve the interpretability and filtering problems of standard GVAEs.

1. Dirichlet Latent Factors Instead of mapping nodes to a Gaussian distribution, DGVAE maps them to a Dirichlet distribution. This approach is analogous to "topic modeling" in natural language processing: each node is assigned a probability of belonging to various clusters. To make this process differentiable for training via the reparameterization trick, the authors utilize a Laplace approximation to represent the Dirichlet distribution as a logistic normal distribution.

2. Heatts (Heat Taylor Series) Encoder To improve upon the GCN, the authors propose a new GNN variant to serve as the encoder. Motivated by the heat kernel ($e^{-sL}$)—a classic tool in physics and spectral geometry—Heatts uses a 3rd-order Taylor series expansion to approximate the heat kernel.

Spectral filter properties comparing the ideal heat kernel to 1st, 2nd, and 3rd order Taylor expansions across different depths.

As shown in the spectral filter analysis, the 1st-order approximation (used by standard GCNs) can become negative at high frequencies, which is highly undesirable. The 3rd-order Heatts approximation remains positive and decays more sharply. This allows for fast computation without expensive eigendecomposition while providing a much better low-pass filter that effectively "smooths" the graph data, leading to cleaner cluster assignments.

3. Theoretical Linkage to Graph Cuts The paper also provides a formal proof showing that maximizing the reconstruction term in a DGVAE is mathematically equivalent to minimizing a spectral relaxed balanced graph cut. This insight successfully anchors the deep learning model in classical graph theory.

Key Insights: Built-In Interpretability

Because the latent space is Dirichlet, the "factors" learned by the model are literally explicit cluster memberships.

Graph visualizations demonstrating how DGVAE captures explicit cluster memberships in its latent space.

When a generated graph is colored by its latent factors, the communities the model has identified become immediately visible. This built-in interpretability is a significant advantage over Gaussian VAEs, where the latent dimensions have no inherent structural meaning.

To ensure the model actually learns these meaningful clusters, the authors had to overcome "posterior collapse"—a common VAE failure mode where the model ignores the latent space. Because Dirichlet priors are particularly sensitive to this, the authors implemented an aggressive optimization strategy (an inner loop for reconstruction) to force the model to utilize the latent cluster assignments.

Empirical Results

The DGVAE model was evaluated on two primary tasks, demonstrating significant improvements over existing baselines:

  • Graph Generation: Evaluated across six synthetic graph families (Erdos-Renyi, Ego, Regular, Geometric, Power Law, and Barabasi-Albert), DGVAE significantly outperformed standard VGAE and Graphite-VAE. For example, on the Erdos-Renyi dataset, DGVAE achieved a Negative Log-Likelihood (NLL) of 0.286, a massive improvement over VGAE’s 1.010.
  • Graph Clustering: Tested on standard citation benchmarks (Pubmed, Citeseer, and Wiki), the model set new state-of-the-art marks for unsupervised clustering. On the Citeseer dataset, the deterministic version (DGAE) achieved 51.3% accuracy, jumping well past the standard VGAE's 43.4%.

Ablation studies further confirmed that replacing the Heatts encoder with a standard GCN consistently lowered performance, validating the 3rd-order Taylor-series approach.

Limitations and Future Directions

While powerful, Dirichlet VAEs are notably harder to train than Gaussian ones. They require specific training dynamics, such as separating the KL-divergence and reconstruction terms, to avoid local optima. Additionally, the scaling factor $s$ in the heat kernel and the order of the Taylor expansion introduce new hyperparameters that require tuning for different graph topologies.

Looking forward, the "balanced cut" interpretation introduced by DGVAE could be extended to other types of deep generative models. This paves the way for new, highly interpretable methods for generating complex structures like molecular graphs or social networks with specific, controllable community structures.

Summary updated

Abstract

Graph Neural Networks (GNN) and Variational Autoencoders (VAEs) have been widely used in modeling and generating graphs with latent factors. However there is no clear explanation of what these latent factors are and why they perform well. In this work, we present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Our study connects VAEs based graph generation and balanced graph cut, and provides a new way to understand and improve the internal mechanism of VAEs based graph generation. Specifically, we first interpret the reconstruction term of DGVAE as balanced graph cut in a principled way. Furthermore, motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships. Heatts utilizes the Taylor series for fast computation of Heat kernels and has better low pass characteristics than Graph Convolutional Networks (GCN). Through experiments on graph generation and graph clustering, we demonstrate the effectiveness of our proposed framework.
BibTeX
@inproceedings{li2020dirichlet,
  author = {Jia Li and Jianwei Yu and Jiajin Li and Honglei Zhang and Kangfei Zhao and Yu Rong and Hong Cheng and Junzhou Huang},
  title = {{Dirichlet Graph Variational Autoencoder}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=IAmQCnaAVT},
}
Figure