Generating graphs is a fundamentally difficult challenge in machine learning. Unlike text or images, which can be flattened into fixed-dimensional sequences or regular grids, graphs are permutation-invariant, discrete, and vary wildly in size and topology. A naive "one-shot" approach—predicting an entire adjacency matrix simultaneously—suffers from a combinatorial explosion of possibilities and struggles to guarantee structural validity.
As noted in a comprehensive survey by Zhu et al., generating a network incrementally trades off the raw speed of one-shot generation for a massive gain in structural integrity. By breaking graph construction down into a sequence of local, discrete decisions, models can dynamically adapt to the topology they are building, making it possible to enforce complex domain constraints and scale to larger networks.
Decomposing the Adjacency Matrix
The core intuition behind sequential graph generation is autoregression: predicting the next structural element conditioned on all previously generated elements. In practice, this means building the graph node-by-node and edge-by-edge.
A foundational realization of this idea is GraphRNN, proposed by You et al., which decomposes graph generation into a hierarchical sequence of recurrent neural networks (RNNs). First, a node-level RNN decides whether to add a new vertex to the graph. Second, an edge-level RNN generates a sequence of binary values determining which existing nodes the new vertex should connect to.
To prevent the sequence length from exploding combinatorially, You et al. utilized a Breadth-First Search (BFS) node ordering strategy. Because BFS limits the maximum node degree lookback required to define a graph, it drastically reduces the decision space, allowing the model to capture long-range dependencies and scale to significantly larger graphs than previous one-shot methods.
One-Shot Generation:
[ Matrix of NxN probabilities ] ---> High combinatorial complexity, invalid structures
Sequential Generation (Autoregressive):
Step 1: Add Node A
Step 2: Add Node B ---> Connect B to A? (Yes/No)
Step 3: Add Node C ---> Connect C to A? (Yes/No) ---> Connect C to B? (Yes/No)
This autoregressive paradigm has been adapted across various domains. For instance, Wu et al. designed a hierarchical recurrent structure to model the evolution of dynamic graphs, alternating between node-level and edge-level decisions to transform a latent vector into a discrete set of nodes and edges. Similarly, Faez et al. extended this to graph completion tasks by separating the generation of "inter-links" (connecting new nodes to an existing observed subgraph) and "intra-links" (connecting new nodes to each other).
Enforcing Structural Constraints via Masking
The primary reason sequential generation works so well is that it allows models to enforce hard domain constraints at each step of the generation process. In a one-shot model, ensuring that a generated molecule obeys chemical valency rules or that a causal network contains no cycles requires complex, often non-differentiable global loss functions. In a sequential model, invalid actions can simply be masked out.
Consider the generation of Directed Acyclic Graphs (DAGs), which form the underlying scaffolding for neural architectures and causal models. Zhang et al. demonstrated that by maintaining the hidden states of all previously generated nodes, a state-aware sequential decoder can guarantee acyclicity. At each step, the placement of a new edge is strictly conditioned on the existing partial graph's state, preventing any backward-facing connections.
Taking this further, Deleu et al. used Generative Flow Networks (GFlowNets) to sample DAGs sequentially. By explicitly masking out actions that would introduce cycles based on the current topology, the generative process ensures that every single sampled graph is a valid topological structure.
This step-by-step validation is equally potent in chemistry. The Constrained Graph Variational Autoencoder (CGVAE) developed by Liu et al. generates molecules one edge at a time. By applying a masked decoding process that evaluates valency rules against the current partial structure, the model achieves 100% chemical validity. Crucially, the authors found that generating graphs based only on the current partial structure—rather than the entire historical construction path—enhances model robustness and prevents overfitting to specific generation orders.
In natural language processing, Lyu et al. utilized a depth-first search (DFS) masking strategy to maintain the hierarchical, acyclic nature of Abstract Meaning Representation (AMR) semantic graphs during parsing, ensuring that the induced generation order never introduces illegal cycles. Even in random graph theory, Bayati et al. showed that sequentially approximating edge probabilities allows for the polynomial-time construction of graphs that strictly satisfy large girth constraints (avoiding short cycles).
State Tracking and Contextual Encoding
To make accurate sequential predictions, a model must maintain a rich representation of the graph generated so far. How do models encode this evolving context?
One approach is to use Graph Neural Networks (GNNs) dynamically within the generation loop. For example, GraphDF, a discrete flow model proposed by Luo et al., uses a relational graph convolutional network to encode the partial subgraph structure at each step. This structural embedding provides the exact relational context needed to parameterize the next discrete node or edge addition.
In early foundational work, Tarlow et al. introduced Gated Graph Sequence Neural Networks (GGS-NNs), which chain multiple GNN modules together using Gated Recurrent Units (GRUs). Each step in the sequence produces a partial result and modifies the graph's internal hidden states, allowing the network to output a series of interdependent decisions for complex reasoning tasks like pathfinding or program verification.
For discovering causal graphs from data, Ke employed an autoregressive decoder where each edge prediction is conditioned on both a summary of the input data and the set of edges already established, demonstrating that sequential attention over existing structures yields highly accurate causal induction.
Coarse-to-Fine: Hierarchical Skeletons
For highly complex or domain-specific graphs, generating every single node and edge in a flat sequence can still be daunting. To alleviate this, many modern frameworks adopt a coarse-to-fine strategy: first generating a structural "skeleton" or macro-topology, and then filling in the fine-grained details.
In molecular design, Zhu et al. showed that factorizing the generation process—first establishing a structural skeleton and then conditioning node attributes on that skeleton—drastically improves graph validity. This sequential dependency provides a necessary relational context that prevents the structural fragility common in models that try to guess nodes and edges simultaneously.
This skeleton-first approach is also highly effective in automated machine learning (AutoML). Helali et al. modeled machine learning pipeline construction by first predicting a structural skeleton of pre-processors and models, effectively pruning the search space before hyperparameter optimization begins.
Similarly, Hu et al. synthesized complex procedural material graphs using a three-stage hierarchy:
- Predict the high-level node operations.
- Establish the connectivity edges between those operations.
- Assign specific parameter values to the nodes.
This ensures that the logical computational flow is fully established before fine-tuning the specific visual attributes.
Hierarchical Generation Flow:
[ Macro-Topology / Skeleton ] ---> [ Edge Connectivity ] ---> [ Node/Edge Attributes ]
Broader Applications and Search Frameworks
By framing graph generation as a sequential decision process, researchers can leverage powerful search and sequence-modeling algorithms originally designed for games, language, or time-series.
For instance, Roucairol et al. treated graph construction as a game, using Monte Carlo Search (MCS) to incrementally add nodes and edges. This allowed the algorithm to explore the space of possible topologies efficiently, successfully finding counter-examples to long-standing conjectures in spectral graph theory.
In the realm of user interaction, Mittal utilized a recurrent framework to process scene graphs step-by-step, transforming a static graph-to-image pipeline into an incremental generation process where users can add objects sequentially while maintaining visual consistency.
To recover the latent growth rules of scale-free networks, Guzman utilized a sequential LSTM-based decoder within a Variational Autoencoder, demonstrating that static architectures fail to capture the iterative dependencies found in models like preferential attachment.
To address the "exposure bias" common in step-by-step models, Krimmel et al. introduced graph filtration, a generalized framework that models non-monotonic graph sequences, offering greater flexibility in how structural evolution is structured.
Finally, for formal query building in question answering, Chen et al. constructed query graphs incrementally using primitive operations like adding and selecting vertices, reducing the noise of incorrect candidate queries. By framing graph evolution as a sequence generation task, Chen et al. enabled zero-shot link prediction on unseen dynamic graphs, treating historical node pairs as context for future predictions.
Whether applied to event schema induction (Ji et al.) or mechanical linkage synthesis (Farimani et al.), sequential graph generation transforms a daunting global optimization problem into a series of manageable, context-aware local steps.
Key Foundational Work
Gated Graph Sequence Neural Networks (2016) — contributed 4 concept elements to this direction.
Gated Graph Sequence Neural Networks Yujia Li (2016) — contributed 3 concept elements to this direction.
Generating Random Graphs with Large Girth (2008) — contributed 1 concept elements to this direction.