Source-linked AI summary
NetGAN: Generating Graphs via Random Walks
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, Stephan Günnemann
TL;DR
Graph generative models must capture real-world network properties that explicit models may not anticipate. NetGAN learns a distribution of biased random walks with a stochastic neural-network GAN, generating graphs that preserve important topology and generalize to competitive link prediction without explicit task training. The paper concludes that implicit graph generators are well-suited to capturing the complex nature of real-world networks, while noting scalability and evaluation limitations.
Problem
NetGAN addresses the challenge of defining graph models that capture essential, potentially unknown properties of real-world networks rather than only prescribed ones.
Method
NetGAN learns graph topology by training a stochastic neural-network GAN to generate discrete biased random walks sampled from the input graph.
Results
NetGAN generates graphs that capture important topological properties and achieves competitive link prediction performance, including state-of-the-art results on some datasets despite not being trained for link prediction.
Takeaways & Limitations
The results provide evidence that implicit generative models can capture complex real-world network structure without manually specifying each topological property.
Takeaways & Limitations
Large graphs require many generated random walks for representative transition counts, and better measures for evaluating implicit graph generators remain an open direction.
Abstract
from arXiv · showhide
We propose NetGAN - the first implicit generative model for graphs able to mimic real-world networks. We pose the problem of graph generation as learning the distribution of biased random walks over the input graph. The proposed model is based on a stochastic neural network that generates discrete output samples and is trained using the Wasserstein GAN objective. NetGAN is able to produce graphs that exhibit well-known network patterns without explicitly specifying them in the model definition. At the same time, our model exhibits strong generalization properties, as highlighted by its competitive link prediction performance, despite not being trained specifically for this task. Being the first approach to combine both of these desirable properties, NetGAN opens exciting avenues for further research.
1. Introduction
NetGAN addresses the challenge of modeling real-world graph structure without prescribing which properties matter by learning to generate plausible biased random walks. It reproduces important network patterns, supports smoothly varying graph characteristics through latent interpolation, and generalizes to competitive link prediction despite not being trained for that task.
- Motivation: Real-world networks exhibit surprising properties that established explicit graph models may fail to capture comprehensively.This motivates models that can learn essential graph properties without requiring them to be specified in advance.
- Approach: NetGAN learns graph topology through the distribution of biased random walks, using a stochastic neural-network generator and a discriminator trained on real walks.The generator produces plausible discrete random walks, while the discriminator distinguishes them from walks sampled from the original graph.
- Results: NetGAN consistently reproduces known real-world network patterns, including degree distributions, without explicitly specifying those patterns in its model definition.Figure 1 illustrates similar structure and closely matching degree distributions between a CITESEER subgraph and a generated counterpart.
- Results: NetGAN achieves competitive, sometimes state-of-the-art, link prediction results on real-world datasets despite not being trained explicitly for link prediction.The result is presented as evidence of generalization beyond simply replicating the input graph.
- Results: Latent-space interpolation produces graphs with smoothly changing characteristics while preserving important topological properties without manually encoding them.This demonstrates that the model can vary generated graph characteristics continuously.
2. Related Work
Prior graph-generation work largely used prescribed models that target selected properties, while early GAN-based graph approaches faced discrete-generation or scalability challenges. NetGAN is positioned against these limitations by generating graph data through a different implicit approach.
- GANs for graphs: Earlier GAN approaches for graph data either learn topological features of subgraphs or directly generate adjacency matrices.Direct adjacency-matrix generation includes zero entries and therefore incurs quadratic computation and memory in the number of nodes.
- GANs for graphs: Adjacency-matrix GAN generation was reported to require over 60 hours for a graph with only 154 nodes.This illustrates the practical scalability problem associated with generating entire adjacency matrices.
- Prescribed graph models: Prescribed graph generators typically target a predefined subset of properties such as degree distribution, community structure, or clustering coefficient.The related-work literature includes configuration models, stochastic blockmodels, and other explicit probabilistic approaches.
- Discrete GAN generation: GAN methods for discrete data commonly address sampling challenges through reinforcement learning, modified GAN objectives, or generation of discrete patient-record features.These approaches had not considered graph-structured data according to the related-work discussion.
3. Model
NetGAN learns graph topology through a generator of biased random walks and a discriminator trained to distinguish generated walks from real ones. Its sequential stochastic generator, differentiable discrete sampling, WGAN training, and controlled graph assembly support scalable graph generation and generalization.
- Model overview: NetGAN models graph topology by learning a distribution over biased random walks sampled from the input graph.Random walks of length T from an input graph with N nodes provide the training set.
- Model overview: The generator and discriminator are trained end-to-end so generated random walks resemble plausible walks from the input graph.The generator produces synthetic walks, while the discriminator distinguishes them from training walks sampled from the input graph.
- Generator: At each step, an LSTM generator outputs next-node logits and a memory state, samples a one-hot node through softmax, and feeds both into the next step.A latent code initializes the generator memory through a parametric function; the LSTM uses cell and hidden states as its memory.
- Generator: Low-dimensional LSTM outputs are projected to N-node logits, reducing overhead for large graphs, while node inputs are down-projected to the LSTM dimension H.The implementation uses H ≪ N and up- and down-projection matrices to handle high-dimensional node spaces efficiently.
- Generator: The Straight-Through Gumbel estimator enables backpropagation through categorical node sampling by using a differentiable relaxation during the backward pass.The forward pass uses a one-hot sample, while gradients flow through the differentiable relaxed sample; temperature τ controls the relaxation.
- Training: NetGAN uses WGAN training with gradient penalty, Adam optimization, and L2 regularization, while early stopping controls memorization and graph overlap.Validation-based stopping targets link-prediction generalization; user-specified edge overlap provides task-dependent control over generated graphs.
- Assembling the Adjacency Matrix: Generated walks form a transition-count score matrix that is symmetrized and sampled into a binary adjacency matrix while ensuring every node has at least one edge.Edges are sampled according to transition-count probabilities until the desired edge count is reached; the procedure is not guaranteed to produce a fully connected graph.
4. Experiments
NetGAN is evaluated for graph realism, generalization through link prediction, sensitivity to design choices, and latent-space control of generated graph properties. It preserves diverse network statistics without explicitly modeling them, generalizes competitively, and produces smoothly varying graph characteristics through latent interpolation.
- 4. Experiments: NetGAN is evaluated on graph statistics, link prediction, latent-space interpolation, and sensitivity to random-walk and model settings.Experiments use citation networks and Political Blogs, treating graphs as undirected largest connected components.
- 4.1. Graph Generation: NetGAN captures diverse graph properties well, while prescribed models excel mainly on statistics they explicitly model.NetGAN achieves the best average rank across the measured statistics; VGAE does not produce realistic graphs.
- 4.1. Graph Generation: Rewiring non-overlapping edges causes strong deviations from the input statistics, indicating that NetGAN captures network structure rather than merely memorizing edges.The experiment fixes overlapping edges and rewires the rest with the configuration model.
- 4.2. Link Prediction: NetGAN achieves competitive link prediction across datasets and state-of-the-art results on CITESEER and POLBLOGS despite not being trained for link prediction.There is no overall dominant method, with different methods performing best on different datasets.
- 4.2. Link Prediction: More sampled random walks improve NetGAN link prediction, especially on larger networks, at additional computational cost.The sampling procedure can be trivially parallelized, including when using 100M walks.
- 4.2. Link Prediction: Longer random walks outperform edge-only walks, but the gain from T = 20 over T = 16 is marginal; experiments therefore use T = 16.Most hyperparameters are noncritical within a reasonable range, with H ≥30 given as an example.
- 4.3. Latent Variable Interpolation: Latent-space interpolation produces graphs whose properties change smoothly across regions of the learned two-dimensional space.Heatmaps and community-distribution trajectories show distinct but smoothly transitioning graph characteristics.
5. Discussion and Future Work
The discussion identifies limitations in scalability, evaluation, experimental scope, and graph modalities, while showing that latent-space regions produce graphs with distinct characteristics.
- Explicit models recover specified properties but perform worse on other graph characteristics, motivating implicit graph generators such as NetGAN.
- Scalability: NetGAN requires many generated random walks to obtain representative transition counts for large graphs, although sampling is parallelizable.
- Evaluation: Visual inspection cannot reliably judge graph realism, so new measures for implicit graph generators remain an important research direction.
- Latent-space behavior: Figure 4 shows that latent-space regions correspond to graphs with different degree distributions and random-walk properties.
- Experimental scope: The current work focuses on a single large graph, leaving collections of smaller i.i.d. graphs and topology-dependent performance for future study.
- Other types of graphs: Adapting NetGAN to attributed, k-partite, heterogeneous, dynamic, or inductive networks remains future work.
6. Conclusion
NetGAN is an implicit graph generator that captures important network topology and supports smoothly varying graph characteristics through latent-space interpolation. Its competitive link prediction performance provides evidence of strong generalization and suitability for modeling complex real-world networks.
- NetGAN captures community structure and degree distribution without manually specifying them.
- NetGAN shows competitive link prediction performance across multiple datasets, despite not being trained explicitly for link prediction.
- Latent-space interpolation generates graphs with continuously varying characteristics.
- The results provide evidence that implicit graph generative models can capture the complex nature of real-world networks.
A. Graph statistics
The paper uses graph statistics to measure generated graph properties, including maximum degree.
- Table 4 lists the graph statistics used to measure graph properties in this work.
- Maximum degree is one of the graph statistics used in the evaluation.
B. Baselines
The baselines include configuration models, exponential random graph models, degree-corrected stochastic blockmodels, and variational graph autoencoders.
- The configuration model preserves a selected share of input edges while randomly shuffling the remaining edges to match specified overlap.
- The exponential random graph model uses edge count, density, degree correlation, deg1.5, and gwesp settings.
- The degree-corrected stochastic blockmodel is implemented with graph-tool using recommended hyperparameter settings.
- The variational graph autoencoder constructs graphs from predicted edge probabilities and uses validation-based early stopping.
C. Properties of generated graphs
The section compares graph statistics for the CITESEER and CORA-ML graphs with graphs generated by GraphGAN and DC-SBM, averaging results over five trials.
- Table 5 compares graph statistics between the CITESEER/CORA-ML graphs and graphs generated by GraphGAN and DC-SBM.The comparison is averaged after 5 trials.
D. Graph statistics during the training process
The section examines how graph statistics evolve during training and how random-walk and generated-graph properties vary across latent-space bins and subregions.
- Graph statistics during training: Figures 7 and 8 show the evolution of graph statistics during training on CORA-ML and CITESEER.
- Latent-space bins: Figures 9 and 10 examine random-walk and sampled-graph properties across 20 × 20 latent-space bins for CORA-ML and CITESEER.
- Community distributions: Figure 11 examines community distributions of graphs generated by NetGAN across subregions of the latent space z on CITESEER.
G. Recovering ground-truth edge probabilities
The section evaluates whether NetGAN can recover ground-truth edge probabilities from a graph generated by a prescribed model, using a DC-SBM graph and inferred edge scores.
- Experimental setup: The experiment generates a 300-node, 3-community graph from DC-SBM and fits NetGAN on that graph.
- Evaluation: The evaluation compares ground-truth edge probabilities with edge scores inferred by NetGAN.
- Implementation: The reported implementation uses single hidden layers with 40 generator units and 30 discriminator units, plus 64- and 32-dimensional down-projections.
- Implementation: Training uses Adam with learning rate 1e−3, L2 regularization strength 1e−6, five discriminator updates per generator update, and gradient penalty 10.
- Implementation: Additional implementation details are provided in the reference implementation.