graphrnn
**GraphRNN** is an **autoregressive deep generative model that constructs graphs sequentially — adding one node at a time and deciding which edges connect each new node to previously placed nodes** — modeling the joint probability of the graph as a product of conditional edge probabilities, enabling generation of diverse graph structures beyond molecules including social networks, protein structures, and circuit graphs.
**What Is GraphRNN?**
- **Definition**: GraphRNN (You et al., 2018) decomposes graph generation into a sequence of node additions and edge decisions using two coupled RNNs: (1) a **Graph-Level RNN** that maintains a hidden state encoding the graph generated so far and produces an initial state for each new node; (2) an **Edge-Level RNN** that, for each new node $v_t$, sequentially decides whether to create an edge to each previous node $v_1, ..., v_{t-1}$: $P(G) = prod_{t=1}^{N} P(v_t | v_1, ..., v_{t-1}) = prod_{t=1}^{N} prod_{i=1}^{t-1} P(e_{t,i} | e_{t,1}, ..., e_{t,i-1}, v_1, ..., v_{t-1})$.
- **BFS Ordering**: The node ordering significantly affects generation quality. GraphRNN uses Breadth-First Search (BFS) ordering, which ensures that each new node only needs to consider edges to a small "active frontier" of recently added nodes rather than all previous nodes. This reduces the edge decision sequence from $O(N)$ per node to $O(M)$ (where $M$ is the BFS queue width), dramatically improving scalability.
- **Training**: During training, the model is given random BFS orderings of real graphs and trained via teacher forcing — at each step, the true binary edge decisions are provided as input while the model learns to predict the next edge. At generation time, the model samples edges autoregressively from its own predictions, building the graph from scratch.
**Why GraphRNN Matters**
- **Domain-General Graph Generation**: Unlike molecular generators (JT-VAE, MolGAN) that exploit chemistry-specific constraints, GraphRNN is a general-purpose graph generator — it can learn to generate any type of graph: social networks, protein contact maps, circuit netlists, mesh graphs. This generality makes it the foundational autoregressive model for graph generation research.
- **Captures Long-Range Structure**: The graph-level RNN maintains a global state that captures the overall graph structure built so far, enabling the model to generate graphs with coherent global properties (correct degree distributions, clustering coefficients, community structure) rather than just local connectivity patterns.
- **Scalability via BFS**: The BFS ordering trick is GraphRNN's key practical contribution — reducing the edge decision space per node from $O(N)$ to $O(M)$, where $M$ is typically much smaller than $N$. For sparse graphs with bounded treewidth, this makes generation scale linearly rather than quadratically with graph size.
- **Foundation for Successors**: GraphRNN established the autoregressive paradigm for graph generation that influenced numerous successors — GRAN (attention-based edge prediction), GraphAF (flow-based generation), GraphDF (discrete flow), and molecule-specific extensions. Understanding GraphRNN is essential for understanding the lineage of autoregressive graph generators.
**GraphRNN Architecture**
| Component | Function | Key Design Choice |
|-----------|----------|------------------|
| **Graph-Level RNN** | Encodes graph state, seeds each new node | GRU with 128-dim hidden state |
| **Edge-Level RNN** | Predicts edges from new node to previous nodes | Binary decisions, sequential |
| **BFS Ordering** | Limits edge decisions to active frontier | Reduces $O(N)$ to $O(M)$ per node |
| **Training** | Teacher forcing on random BFS orderings | Multiple orderings per graph |
| **Sampling** | Autoregressive sampling, edge by edge | Bernoulli per edge decision |
**GraphRNN** is **sequential graph drawing** — constructing graphs one node and one edge at a time through an autoregressive process that maintains memory of the evolving structure, providing the general-purpose foundation for deep generative modeling of arbitrary graph topologies.