Graphite: Iterative Generative Modeling of Graphs

Aditya Grover, Aaron Zweig, Stefano Ermon

Abstract

Graphs are a fundamental abstraction for modeling relational data. However, graphs are discrete and combinatorial in nature, and learning representations suitable for machine learning tasks poses statistical and computational challenges. In this work, we propose Graphite, an algorithmic framework for unsupervised learning of representations over nodes in large graphs using deep latent variable generative models. Our model parameterizes variational autoencoders (VAE) with graph neural networks, and uses a novel iterative graph refinement strategy inspired by low-rank approximations for decoding. On a wide variety of synthetic and benchmark datasets, Graphite outperforms competing approaches for the tasks of density estimation, link prediction, and node classification. Finally, we derive a theoretical connection between message passing in graph neural networks and mean-field variational inference.

Introduction

Deep generative models, such as Variational Autoencoders (VAEs), have revolutionized domains like image and audio processing. However, applying these techniques to graph-structured data remains difficult because graphs are discrete, lack a fixed grid, and exhibit complex combinatorial properties. Existing methods typically face a trade-off: they are either computationally expensive models that generate small, complex structures (e.g., molecules) or scalable models like the Variational Graph Autoencoder (VGAE) that rely on simplistic "inner product" decoders. These simple decoders often fail to capture the higher-order structural patterns found in real-world networks.

Graphite addresses these limitations by introducing a scalable, iterative decoder that refines graph reconstructions through multiple passes, allowing the model to capture complex relational dependencies while maintaining efficiency for large-scale networks.

Methods

Graphite follows a VAE architecture consisting of a GNN-based encoder and a novel iterative decoder. The encoder maps node features into a latent space, producing mean and standard deviation vectors for each node.

The Generative Model

The model assumes a latent variable $Z_i$ for each node $i$, conditioned on observed features $X_i$. The adjacency matrix $A$ is then generated based on these latent representations.

Plate notation of the Graphite generative model showing the dependencies between features X, latent variables Z, and the adjacency matrix A.

Iterative Decoding

The core innovation of Graphite is its decoder. Instead of a single-step reconstruction, it employs an iterative refinement process:

  1. Initial Draft: An initial adjacency matrix is estimated using the inner product of latent vectors.
  2. Refinement: This draft, along with latent features, is passed through a GNN to update node representations.
  3. Iteration: This process repeats, allowing the model to "smooth" predictions and incorporate global structural information.

To ensure scalability to graphs with thousands of nodes, Graphite utilizes the associativity of matrix multiplication. This allows the model to perform refinement steps without explicitly constructing the dense $N \times N$ adjacency matrix, keeping the computational complexity manageable ($O(N)$ per iteration for sparse graphs).

Theoretical Connection

A significant contribution of this work is the formal proof connecting GNN message passing to mean-field variational inference. The authors demonstrate that a GNN update can be viewed as a first-order Taylor approximation of the updates used in solving complex probabilistic graphical models. This provides a rigorous Bayesian foundation for the use of GNNs in generative modeling.

Results

Graphite was evaluated on synthetic graph families (e.g., Barabasi-Albert, Erdos-Renyi) and citation networks (Cora, Citeseer, Pubmed).

In link prediction tasks, Graphite-VAE consistently outperformed baselines like VGAE and node2vec. For instance, on the Pubmed dataset, it achieved an AUC of 97.4%. Furthermore, when used as a feature extractor for semi-supervised node classification, Graphite improved the performance of standard GCNs, indicating that its unsupervised representations are highly informative.

t-SNE visualizations of node embeddings learned by Graphite-AE and Graphite-VAE, demonstrating clear clustering of node categories.

Density Estimation

On synthetic datasets, Graphite showed significantly lower reconstruction errors compared to standard Graph Autoencoders. This suggests that the iterative decoder is better at capturing the underlying generative rules of different graph topologies.

Conclusion

Graphite provides a powerful framework for unsupervised graph representation learning. By treating decoding as an iterative message-passing process, it overcomes the limitations of simple inner-product decoders while remaining scalable. Future work includes extending this framework to dynamic and heterogeneous graphs, as well as incorporating domain-specific constraints for applications like molecular generation.

Summary updated

Abstract

Graphs are a fundamental abstraction for modeling relational data. However, graphs are discrete and combinatorial in nature, and learning representations suitable for machine learning tasks poses statistical and computational challenges. In this work, we propose Graphite, an algorithmic framework for unsupervised learning of representations over nodes in large graphs using deep latent variable generative models. Our model parameterizes variational autoencoders (VAE) with graph neural networks, and uses a novel iterative graph refinement strategy inspired by low-rank approximations for decoding. On a wide variety of synthetic and benchmark datasets, Graphite outperforms competing approaches for the tasks of density estimation, link prediction, and node classification. Finally, we derive a theoretical connection between message passing in graph neural networks and mean-field variational inference.
BibTeX
@inproceedings{grover2019graphite,
  author = {Aditya Grover and Aaron Zweig and Stefano Ermon},
  title = {{Graphite: Iterative Generative Modeling of Graphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=wjaiC1BkOO},
}
Figure