Source-linked AI summary
Graphite: Iterative Generative Modeling of Graphs
Aditya Grover, Aaron Zweig, Stefano Ermon
TL;DR
Large graphs create statistical and computational challenges for unsupervised representation learning, while existing graph generators may lack scalable latent-variable inference. Graphite uses a graph-neural-network variational autoencoder with iterative graph refinement for decoding, and it outperforms competing approaches across density estimation, link prediction, and node classification.
Problem
Deep latent-variable generative models have been effective for high-dimensional data but are challenging to apply to large graph-structured data and to decode hidden representations into graphs.
Method
Graphite parameterizes a graph variational autoencoder with graph neural networks and iteratively refines decoded graphs through inner-product operations and message passing.
Results
Graphite representations outperform competing approaches for density estimation, link prediction, and semi-supervised node classification on synthetic and benchmark datasets.
Takeaways & Limitations
Graphite provides a scalable framework for representation learning on large graphs using locally propagating graph-neural-network encoders and decoders.
Takeaways & Limitations
Current generative graph models, including Graphite, are not permutation-invariant and rely on fixed or heuristic node orderings.
Abstract
from arXiv · showhide
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.
1. Introduction
Graphite addresses the challenge of applying deep latent-variable generative models to large graph-structured data. It combines graph neural networks with variational autoencoding and iterative decoding, and outperforms competing approaches across several graph representation-learning tasks.
- Deep generative modeling has achieved strong results for images and speech but remains challenging for large-scale graph-structured data.
- Graph neural networks encode graphs into node representations, whereas decoding hidden representations back into graphs remains an open challenge.
- Graphite is a variational autoencoder for graphs that uses graph neural networks for inference and generation.
- Its decoder starts from an inferred latent-feature reconstruction and iteratively refines the graph through message passing.
- Graphite representations outperform competing methods for density estimation, link prediction, and semi-supervised node classification on synthetic and benchmark datasets.
2. Preliminaries
The preliminaries characterize graphs, Weisfeiler-Lehman message passing, and graph neural networks as iterative procedures for propagating local information. GNN layers generalize this process through learned transformations and activations, with graph convolutional networks providing a permutation-equivariant instance.
- A graph is represented by a symmetric adjacency matrix A and an optional node-feature matrix X.For a graph with n nodes, A is n×n and its entries encode edge weights.
- Weisfeiler-Lehman algorithm: The Weisfeiler-Lehman algorithm iteratively relabels nodes using hashed sums of neighboring-node messages to test graph isomorphism.It declares graphs isomorphic when their node-label sets match after the specified iterations.
- Weisfeiler-Lehman algorithm: The k-dimensional Weisfeiler-Lehman algorithm passes length-k messages and can produce false positives despite guaranteeing no false negatives.
- Graph neural networks: Graph neural networks unfold iterative message passing into layers that transform previous activations using graph-dependent operators, learned weights, and activations.
- Graph neural networks: GNNs initialize activations with node features or the identity matrix when explicit features are absent.
- Graph neural networks: Graph convolutional networks use a permutation-equivariant propagation rule, while Graphite remains agnostic to the specific message-passing rule.
3. Generative Modeling via Graphite
Graphite formulates graph representation learning as latent-variable generative modeling with GNN-based inference and iterative decoding. Its decoder refines an intermediate graph while using algebraic and Monte Carlo strategies to reduce computational cost.
- Latent-variable model: Graphite models graph structure with latent node vectors, observed adjacency entries, and optional node features treated as conditioning evidence.The model uses a fixed prior p(Z|X), a variational posterior qφ(Z|A, X), and a decoder pθ(A|Z, X).
- Encoding: The encoder uses mean-field Gaussian variational marginals whose parameters are produced by a graph neural network.The marginals are isotropic Gaussians with diagonal covariance, making them reparameterizable and easy to sample.
- Decoding: The decoder alternates between constructing an intermediate graph from latent features and applying a GNN to iteratively refine node representations.The intermediate graph is formed from a latent-feature inner product plus a constant, while the GNN receives concatenated latent features and node features.
- Decoding: The final edge distribution uses an inner product of refined node representations and can factorize across edges for efficient sampling.Unweighted edges can use Bernoulli distributions, with probabilities given by sigmoid(Z*Z*T).
- Scalable learning and inference: Right-multiplication reduces intermediate decoding propagation to O(nk d_(l−1) + n d_(l−1)d_l), avoiding quadratic n^2 complexity without statistical-accuracy loss.The final dense inner product remains, so Graphite uses adaptive Monte Carlo evaluation to trade computational budget against statistical accuracy.
4. Experimental Evaluation
Graphite is evaluated across whole-graph, edge, and node tasks using synthetic and benchmark datasets. It consistently improves over relevant competing approaches, with learned decoders, Graphite-VAE, and Graphitehybrid showing strong results.
- Experimental setup: The evaluation covers density estimation, link prediction, and semi-supervised node classification across synthetic and citation-network datasets.The experiments include Cora, Citeseer, and Pubmed for citation-network evaluation.
- Reconstruction & density estimation: Graphite-AE and Graphite-VAE significantly outperform AE and VGAE on reconstruction and negative log-likelihood tasks.These results indicate the usefulness of learned decoders in Graphite.
- Link prediction: Graphite-VAE achieves the best overall link-prediction performance on both AUC and AP, while Graphite-AE generally outperforms GAE.Results are averaged over 50 random train/validation/test splits on citation-network datasets.
- Qualitative evaluation: Graphite embeddings cluster Cora papers according to their labels despite training without access to node label information.The embeddings are visualized using a two-dimensional t-SNE projection of latent feature vectors.
- Semi-supervised node classification: Graphitehybrid outperforms competing semi-supervised models on all evaluated datasets, including the closest GCN baseline.The hybrid model augments the GCN objective with the Graphite objective, sharing encoder parameters.
5. Theoretical Analysis
The section connects GNN message passing with mean-field variational inference through kernel embeddings and establishes a computational equivalence under a locality property. It then explains when this connection supports using GNNs for variational posteriors in Graphite.
- The analysis derives a theoretical connection between GNN message passing and approximate inference in undirected graphical models.
- Kernel embeddings: Kernel embeddings represent variational marginals in a feature space, allowing iterative mean-field updates to be expressed through neighboring marginal embeddings.
- Locality assumption: Property 1 requires each latent variable to be conditionally independent of non-neighbors given observed graph data and neighboring latent variables.
- Theorem 2: Theorem 2 states that, for models satisfying Property 1, suitable GNN parameters make propagation computationally equivalent to a first-order approximation of the mean-field update.
- Implication for Graphite: The connection motivates GNN parameterization of Graphite variational posteriors, although the posterior in Graphite's generative model generally differs from the graphical model used in the theorem.
6. Discussion & Related Work
This section situates Graphite among probabilistic graph models, graph representation-learning methods, GNNs, and recent deep generative approaches. It emphasizes Graphite's focus on scalable representation learning for observed relational structure.
- Representation learning on graphs: Graph representation learning includes matrix factorization, random-walk methods, and graph neural networks.
- Graph neural networks: GNNs learn node representations through message passing and have been applied to several downstream graph-learning tasks.
- Latent variable models for graphs: Earlier latent-variable graph models were limited by single-graph settings, expensive Markov-chain inference, or task-specific designs.
- Graphite's position: Graphite differs by modeling observed relational structure and introducing a multi-step graph-refinement decoder for large-graph representation learning.
- Deep generative models: Adversarial and autoregressive graph generators do not directly provide latent-variable encoders, while molecular-graph VAEs use decoding procedures that limit scaling to large graphs.
7. Conclusion & Future Work
The conclusion presents Graphite as a scalable VAE-based graph generative model with GNN encoders and iterative decoders. It identifies permutation invariance and richer graph structures as future directions.
- Conclusion: Graphite is a scalable deep generative model for graphs based on variational autoencoding.
- Conclusion: Its encoders and decoders use GNNs to propagate information locally on graphs.
- Conclusion: The decoder alternates inner-product operations with message passing on an intermediate graph across multiple layers.
- Future work: Current graph generative models are not permutation-invariant and rely on fixed or heuristic node orderings.
- Future work: Future work includes richer graph structures, domain knowledge in decoders, and propagation rules inspired by additional message-passing inference schemes.
A. Proof of Theorem 2
The proof specializes the kernel-embedding update and GNN propagation rule to show their equivalence under differentiability and simple dimensional assumptions. Vectorized matrix-calculus notation extends the derivation to multidimensional embeddings.
- The proof begins by considering a single variational marginal embedding and unidimensional embeddings across iterations.
- Neighboring kernel embeddings are collected into a vector, with non-neighbor entries set to zero, rewriting the mean-field update accordingly.
- Assuming differentiability, the kernel-embedding operator is approximated using a first-order Taylor expansion around the origin.
- A single-activation-per-node GNN with scalar layer weights and vector biases is written componentwise to match the approximation.
- Substituting the corresponding terms equates the first-order approximation with the GNN message-passing rule, and vectorized matrix calculus extends the result to arbitrary embedding dimensions.
B.1. Link prediction
The link-prediction experiments evaluate Graphite variants against established baselines, using iterative decoding, skip connections, and edge subsampling. The reported results indicate that Graphite maintains link-prediction accuracy when training scales through Monte Carlo edge subsampling.
- Architecture: Graphite-AE and Graphite-VAE use graph neural network encoders and iterative decoders with two refinement rounds before a final inner product.The encoder has 32-32 units, while the decoder has 16-32-16 units.
- Embedding refinement: Graphite combines the initial embedding Z with the final induced embedding Z∗ through a tunable skip-connection weight λ.The paper considers convex combination and incremental-update aggregation functions.
- Embedding refinement: GAE and VGAE are special cases of Graphite obtained by using only a single inner-product decoder, corresponding to λ = 0.Final embeddings use convex combination on Cora and Pubmed, and incremental update on Citeseer.
- Scalability: Graphite can scale to large graphs through Monte Carlo subsampling of |E| random entries during objective evaluation without significant AUC loss.The corresponding AUC scores are reported in Table 6; higher AUC is better.
- Scalability: Figure 4 reports AUC for VGAE and Graphite as the edge-subsampling coefficient c varies during training on the Cora dataset.The figure compares models trained with edge subsampling.
B.3. Density estimation
The density-estimation experiments train and validate models within selected synthetic graph families, using graphs with 10–20 nodes. The setup spans families defined by independent edges, local structure, regularity, geometry, power-law degrees, and preferential attachment.
- Variable graph sizes: The model architecture accommodates different graph sizes by specifying the maximum node count and padding smaller graphs with disconnected dummy nodes.For the described setting, the maximum is 20 nodes, and dummy nodes do not influence gradient updates for variables involving true nodes.
- Experimental setup: Density-estimation models are trained and validated exclusively on graphs sampled from the same selected graph family.The experiments use graph families with node counts ranging from 10 to 20.
- Graph families: The evaluated families include Erdős–Rényi, ego-network, random-regular, random-geometric, random-power-tree, and Barabási–Albert graphs.Their generators cover independent edges, neighborhood structure, fixed degree, geometric proximity, power-law degrees, and preferential attachment.
- Model evaluation: The experiments use convex combinations over three successively induced embeddings and average scores across 50 runs.A two-layer neural network transforms the initially sampled embedding before decoding or iterative refinement.
- Related approaches: Factorization-based graph representation methods operate on adjacency or Laplacian matrices and can be computationally expensive for large graphs.This provides context for comparing graph representation approaches in the density-estimation setting.