PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models

Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, Jure Leskovec

arXiv:1802.08773v3cs.LGcs.AIcs.SI

TL;DR

Graph generation must learn complex, variable graph distributions from observed examples rather than relying on structural assumptions. GraphRNN uses hierarchical autoregressive recurrent networks and BFS ordering to generate graphs, outperforming prior models while scaling to graphs 50 times larger than previous deep approaches.

  • Problem

    Graph generation lacks methods that directly learn generative models from observed graphs despite variable, large output spaces and complex dependencies.

  • Method

    GraphRNN hierarchically autoregressively generates nodes and edges with recurrent networks, using BFS ordering to accommodate variable-sized graphs and improve scalability.

  • Results

    GraphRNN achieves superior quantitative performance to prior deep graph generative models while scaling to graphs 50× larger than those approaches.

  • Takeaways & Limitations

    GraphRNN provides a scalable framework for learning graph generators that match target-set structural characteristics across synthetic and real-world benchmarks.

  • Takeaways & Limitations

    BFS ordering can still require n! orderings in the worst case, such as for star graphs.

Abstract

from arXiv · show

Modeling and generating graphs is fundamental for studying networks in biology, engineering, and social sciences. However, modeling complex distributions over graphs and then efficiently sampling from these distributions is challenging due to the non-unique, high-dimensional nature of graphs and the complex, non-local dependencies that exist between edges in a given graph. Here we propose GraphRNN, a deep autoregressive model that addresses the above challenges and approximates any distribution of graphs with minimal assumptions about their structure. GraphRNN learns to generate graphs by training on a representative set of graphs and decomposes the graph generation process into a sequence of node and edge formations, conditioned on the graph structure generated so far. In order to quantitatively evaluate the performance of GraphRNN, we introduce a benchmark suite of datasets, baselines and novel evaluation metrics based on Maximum Mean Discrepancy, which measure distances between sets of graphs. Our experiments show that GraphRNN significantly outperforms all baselines, learning to generate diverse graphs that match the structural characteristics of a target set, while also scaling to graphs 50 times larger than previous deep models.

1. Introduction and Related Work

GraphRNN addresses the challenge of learning graph generative models directly from observed data despite large, non-unique output spaces and complex edge dependencies. It introduces an autoregressive graph-generation framework with benchmark tasks and MMD-based evaluation, achieving strong performance across synthetic and real-world datasets.

  • Motivation: Learning graph generative models directly from observed graphs remains a key open challenge beyond hand-engineered structural assumptions.Data-driven generation can improve fidelity and support applications such as discovering graph structures and completing evolving graphs.
  • Challenges: Graph generation must handle variable output sizes, non-unique node orderings, and complex dependencies between edges.An n-node graph requires n2 output values, may have up to n! equivalent adjacency matrices, and often contains dependencies such as shared-neighbor effects.
  • GraphRNN: GraphRNN learns graph distributions autoregressively by sequentially adding nodes and edges while maintaining graph-level state.The hierarchical model captures the joint probability of all nodes and edges in a graph.
  • Evaluation: The paper introduces benchmark tasks, baselines, and MMD-based comparisons of degree, clustering-coefficient, and motif statistics for quantitative evaluation.The setup addresses limitations of prior evaluation based mainly on visual inspection or first-order moment statistics.
  • Results: GraphRNN significantly improves over traditional and recent deep graph-generative baselines on synthetic and real-world graphs of varying sizes.It generates high-quality graphs across all benchmark datasets, whereas traditional models perform well only on datasets with special structures.

2. Proposed Approach

GraphRNN represents graphs under node orderings as sequences and learns their distribution autoregressively, decomposing generation into node and edge formation. BFS orderings reduce the number of sequences and edge predictions, yielding overall time complexity O(Mn).

  • Sequence Representation: GraphRNN maps graphs to adjacency-vector sequences, learns p(Sπ) instead of directly modeling p(G), and generates graphs by sampling Sπ and mapping it back to G.For undirected graphs, Sπ determines a unique graph; sampling the auxiliary node ordering makes the sequence distribution autoregressively modelable.
  • Autoregressive Modeling: The sequence distribution is factorized into conditional distributions over its elements, enabling autoregressive modeling of variable-length graph sequences.An end-of-sequence token EOS represents sequences with variable lengths.
  • Hierarchical Architecture: GraphRNN uses a hierarchical RNN in which a graph-level GRU generates nodes and maintains graph state, while an edge-level GRU generates each node’s edges.Both variants implement the transition function as a GRU and are trained with stochastic gradient descent using maximum likelihood over Sπ.
  • BFS Ordering: BFS orderings avoid training on every node permutation without loss of generality because multiple permutations can map to the same BFS ordering.The BFS function selects a starting node and orders queued neighbors according to the input permutation.
  • BFS Ordering: BFS reduces both the number of sequences considered and the edge predictions required by the edge-level RNN; overall GraphRNN time complexity is O(Mn).The model’s empirical upper bound for M is estimated in practice.

3. GraphRNN Model Capacity

GraphRNN’s representational capacity is illustrated under idealized memory and universal-approximation assumptions through community-structured and regular geometric graph examples. The model can represent probabilistic community structure and generate regular ladder graphs from degree-based conditions.

  • Model capacity: GraphRNN’s capacity analysis assumes its graph-level RNN exactly encodes Sπ_i,<j and relies on neural-network universal approximation.These assumptions let the RNN retain prior generation decisions and analyze representational capacity in an ideal case.
  • Graphs with community structure: The community result follows because p(Sπ_<i) depends on ps, pd, and prior community assignments, which the RNNs can encode and update through edge-generation outcomes.The base case samples with probability 0.5ps + 0.5pd at the first edge-level RNN step.
  • Graphs with community structure: GraphRNN can represent community-structured graphs: if it generates Sπ_i,<j according to pcom(G), it can also output p(Sπ_<i) according to pcom(G).The observation applies when an appropriate GraphRNN parameter setting exists for the distribution over Sπ implied by pcom(G).
  • Graphs with regular structure: GraphRNN can generate ladder graphs by activating edge-level functions according to node degrees and applying three degree-dependent connection cases.When Pj_i,j = 0, it connects to a degree 1 node or any degree 2 node; when Pj_i,j = 1, it connects to the degree 2 node two hops away; when Pj_i,j = 2, it makes no further connections.

4. Experiments

GraphRNN is evaluated on synthetic and real graph datasets using MMD-based metrics over graph statistics, with results showing strong structural matching, generalization, and performance gains over traditional and deep baselines. Experiments also examine robustness across interpolations between Barabási-Albert and Erdős-Rényi graphs.

  • Datasets: Experiments span synthetic and real datasets with graph sizes ranging from |V| = 10 to |V| = 2025.The datasets include community, grid, Barabási-Albert, protein, and ego-network graphs.
  • Evaluation metrics: The evaluation uses MMD over degree, clustering-coefficient, and orbit-count distributions, with Wasserstein distances providing efficient graph-statistic comparisons.The orbit counts capture higher-level motifs, while the kernel is designed to incorporate high-order moments.
  • Qualitative and statistical evaluation: GraphRNN captures diverse graph structures and closely matches the test-set distributions of degree, clustering-coefficient, and orbit-count statistics.Visualizations show learning of regular grids, including unseen grid widths and heights, alongside natural ego-network structures.
  • Quantitative results: GraphRNN variants achieve the best performance on all datasets, with 80% decrease of MMD on average compared with traditional baselines and 90% decrease of MMD compared with deep learning baselines.The comparisons use full and small dataset versions and select test performance at the step with the lowest training error.
  • Generalization ability: 22% smaller average NLL gap indicates that GraphRNN generalizes well between training and test graphs.The study compares training and test negative log-likelihoods, with baseline likelihoods defined according to their respective papers.
  • Robustness: Robustness is assessed by perturbing [0%, 20%, ..., 100%] of the edges in 100-node Barabási-Albert graphs to interpolate between Erdős-Rényi and Barabási-Albert graphs.MMD scores are measured for degree and clustering-coefficient distributions across the six graph sets.

5. Further Related Work

This section situates GraphRNN among domain-specific molecule and parse-tree generators and deep autoregressive models, emphasizing its fully general graph-generation setting.

  • Molecule and parse-tree generation: Molecule-generation methods often rely on expert-crafted SMILES representations, while SD-VAE uses grammar-based generation for structured data such as molecules and parse trees.GraphRNN instead considers fully general graph generation.
  • Deep autoregressive models: Deep autoregressive models factor joint distributions into products of conditionals and have succeeded in image and audio generation.GraphRNN extends this modeling paradigm to graph generation.
  • Deep autoregressive models: DeepGMG and related prior work can also be viewed as deep autoregressive models of graphs.The passage places these methods within the same broader modeling framework as GraphRNN.

6. Conclusion and Future Work

The paper proposes GraphRNN and a comprehensive graph-generation evaluation suite, showing significantly better performance than previous state-of-the-art models while remaining scalable and robust to noise. It identifies scaling to larger graphs and efficient conditional graph generation as important open challenges.

  • Contributions: GraphRNN is an autoregressive generative model for graph-structured data, introduced alongside a comprehensive evaluation suite for graph generation.The suite supports evaluation of the graph-generation problem.
  • Contributions: GraphRNN achieves significantly better performance than previous state-of-the-art models while remaining scalable and robust to noise.These properties were demonstrated using the proposed evaluation suite.
  • Future Work: Future work includes scaling graph-generation models to even larger graphs and developing models capable of efficient conditional graph generation.The conclusion describes these as significant remaining challenges.

A. Appendix · A.1. Implementation Details of GraphRNN

GraphRNN uses separate larger and smaller configurations, hierarchical GRU-based generation, and teacher forcing during training. Its implementation also relies on BFS-based sequence preprocessing, empirically selected dimensions, and fixed Adam optimization settings.

  • A.1. Implementation Details of GraphRNN: GraphRNN uses larger and smaller parameter configurations for large datasets and datasets with at most 20 nodes, respectively.The smaller model is reserved for comparisons with two recent preliminary deep graph-generative models.
  • A.1. Implementation Details of GraphRNN: The graph-level RNN has 4 GRU layers with 128-dimensional hidden states in the larger model and 64-dimensional states in the smaller model.The edge-level RNN uses 4 GRU layers with 16-dimensional hidden states in both models.
  • A.1. Implementation Details of GraphRNN: Teacher forcing supplies ground-truth inputs to both RNNs during training, whereas inference uses the model’s own predictions at each time step.The highest graph-level hidden state initializes the lowest edge-level layer through a linear dimensionality-matching layer.
  • A.1. Implementation Details of GraphRNN: GraphRNN-S generates graph sequences with a two-layer MLP using ReLU and sigmoid activations, with 64- and 32-dimensional hidden states for larger and smaller models.Performance is reported as relatively stable with respect to these hyperparameters.
  • A.1. Implementation Details of GraphRNN: Training sequences are created by randomly sampling a training graph, randomly permuting node order, and applying deterministic BFS to obtain BFS node ordering.The robustness section instead uses the ordering that generates B-A graphs.
  • A.1. Implementation Details of GraphRNN: The maximum sequence dimension M is chosen near the empirical 99.9 percentile after 100000 preprocessing runs and removal of consecutive zeros.The procedure reflects that regular graphs tend to require smaller M, while random or community graphs tend to require larger M.
  • A.1. Implementation Details of GraphRNN: Adam minibatch training uses 32 graph sequences for 96000 batches, with learning rate 0.001 decayed by 0.3 at steps 12800 and 32000.These optimization settings are used in all experiments.

A.2. Running Time of GraphRNN

GraphRNN training on the protein dataset converges in about 64,000 iterations and takes roughly 12–24 hours on one Titan X GPU. This runtime includes CPU-based preprocessing, batching, and BFS without multithreading, while GraphRNN-S is about twice as fast.

  • 64,000 iterations are required for training to converge on the protein dataset of about 1,000 graphs with roughly 500 nodes each.
  • 12–24 hours is the reported training runtime using only one Titan X GPU.The runtime includes preprocessing, batching, and BFS.
  • CPU-based preprocessing, batching, and BFS are currently implemented without multithreading.
  • GraphRNN-S is about twice faster than the full GraphRNN model.

A.3. More Details on GraphRNN’s Expressiveness

GraphRNN’s expressiveness on regular structures arises from BFS ordering and edge-level recurrent dependencies. These mechanisms reduce the encoding dimension and distinguish valid from invalid connections during generation.

  • Regular Structures: GraphRNN can use node degree, which is propagated through BFS ordering, as a feature that could be approximated by a neural network.The example concerns generation on graphs with regular structures such as grid and ladder networks.
  • BFS Ordering: BFS node ordering reduces the maximum encoding dimension M from N −1 to a constant smaller than N, illustrated with M = 3 for N = 10.Without BFS ordering, M must equal N −1 to encode all necessary connection information.
  • Edge Dependencies: The edge-level RNN uses previously generated edges to distinguish the single connection that preserves a valid grid structure from multiple incorrect alternatives.In the ladder example, only one candidate connection forms the required 4-cycle with the new edge.

A.4. Code Overview

The repository organizes GraphRNN’s training, modeling, data sampling, and evaluation components across dedicated modules. It also includes implementations of several baseline graph-generation models, including a SNAP-based Kronecker graph model.

  • Repository modules: main.py manages dataset loading, training, inference, and hyper-parameter settings through the Args class.model.py provides the RNN, MLP, and loss-function modules used to build GraphRNN.
  • Repository modules: data.py implements minibatch sampling by drawing random BFS orderings for batches of randomly selected graphs.
  • Baseline implementations: The baselines include Erdős-Rényi, Barabási-Albert, MMSB, GraphVAE, and DeepGMG models, plus a C++ Kronecker graph implementation from SNAP.

A.5. Proofs … A.7. Extension to Graphs with Four Communities

The appendix proves structural and kernel propositions, extends GraphRNN to graphs with node and edge features, and evaluates its ability to learn four-community synthetic graphs. The extensions support feature-rich and directed graphs, while the four-community experiment compares generated graphs with training data and baseline outputs.

  • A.5.1. PROOF OF PROPOSITION 1: BFS ordering implies that, after a missing edge from v_i to v_j, earlier nodes cannot reconnect to any later v_j′.The proof uses the ordering of children in BFS and propagates the absence of edges across later indices.
  • A.5.2. PROOF OF PROPOSITION 2: The proof of Proposition 2 establishes that the Wasserstein distance based kernel k_W(p,q) is positive definite.It combines positive-definite-kernel closure properties with the stated prior result.
  • A.5.2. PROOF OF PROPOSITION 2: By the Moore-Aronszajn theorem, the symmetric positive-definite kernel induces a unique RKHS, yielding Equation (9) when k = k_W.The kernel’s positive definiteness is also noted as obtainable by expressing its function using Taylor expansion.
  • A.6. Extension to Graphs with Node and Edge Features: GraphRNN extends to graphs whose nodes and edges carry feature vectors, represented under ordering π by node matrix X_π and edge matrix F_π.The feature dimensions are m for nodes and k for edges.
  • A.6. Extension to Graphs with Node and Edge Features: The extended state representation includes corresponding node and edge features, and the f_out module can use an MLP to generate node features.The cited passage also describes extending the definition of S_π with feature vectors.
  • A.6. Extension to Graphs with Node and Edge Features: Directed graphs are a special case of the feature extension because they can be viewed as undirected graphs with two edge types.This places directionality within the same node-and-edge-feature framework.
  • A.7. Extension to Graphs with Four Communities: 500 four-community graphs with 48 ≤ |V| ≤ 68 are generated from Erdős-Rényi communities with p = 0.7 plus 0.01|V|^2 uniformly distributed inter-community edges.Each community has n ∈ [|V|/4 − 2, |V|/4 + 2] nodes, and Figure 7 visualizes training graphs, GraphRNN outputs, and Kronecker, MMSB, and B-A baselines.
Loading 1802.08773v3…