Deep generative models have revolutionized how we synthesize images, text, and audio. However, applying these models to graphs—such as social networks, protein structures, or financial transaction webs—reveals a fundamental computational barrier: the quadratic scaling bottleneck.
When generating an image, a neural network operates on a fixed grid of pixels. But when generating a graph of $N$ nodes, the model must determine the connectivity between every possible pair of entities. Naively, this requires predicting an $N \times N$ adjacency matrix, leading to a computational and memory complexity of $O(N^2)$. For a graph of 100 nodes, a model evaluates 10,000 potential relationships; for 10,000 nodes, that number explodes to 100 million.
Because real-world networks are inherently sparse—where the number of actual edges $M$ is much smaller than $N^2$—dense matrix-based models waste massive amounts of computation predicting the absence of connections. To scale graph generation to large networks, researchers have developed architectures that bypass the dense adjacency matrix entirely.
The Adjacency Matrix Trap
As highlighted by Yanqiao Zhu et al. in A Survey on Deep Graph Generation: Methods and Applications, traditional "one-shot" graph generators attempt to output the entire adjacency matrix simultaneously. This approach hits a hard ceiling at a few hundred nodes. The $O(N^2)$ overhead is not just a matter of execution time; it creates an unsustainable memory footprint during training.
This bottleneck extends across various generative paradigms. For instance, Yuanxin Zhuang et al. note in Data-Free Adversarial Knowledge Distillation for Graph Neural Networks that adversarial frameworks suffer from the same matrix-synthesis overhead. Even in diffusion models, which iteratively denoise data, tracking every potential edge at every diffusion step becomes prohibitively expensive. As Dmitrii Gavrilev et al. observe in Anomaly Detection in Networks via Score-Based Generative Models, this scaling behavior restricts generative modeling to small local neighborhoods or ego-graphs rather than global structures.
To break through this wall, modern approaches fundamentally rethink how a graph is represented and constructed by the model.
Sparse and Edge-Centric Diffusion
Standard diffusion models operate by adding continuous or discrete noise to a data structure and training a network to reverse the process. If the data structure is a dense adjacency matrix, the model must denoise all $N^2$ entries.
To solve this, Xiaohui Chen et al. introduced EDGE in Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling. Instead of diffusing toward a completely random, dense noise matrix, EDGE diffuses toward an empty graph. By explicitly modeling node degrees and focusing only on "active nodes" where edges actually exist, the authors reduced the computational complexity from $O(N^2)$ to roughly $O(M)$, where $M$ is the number of edges.
Standard Diffusion: [Full Dense Matrix] ---> Denoise All N^2 Pairs ---> [Final Graph]
EDGE Diffusion: [Empty Graph] ---> Add Active Edges O(M) ---> [Final Graph]
Taking a similar approach, Yiming QIN et al. developed SparseDiff in Sparse Training of Discrete Diffusion Models for Graph Generation. SparseDiff avoids the quadratic bottleneck by training exclusively on sparse edge lists and a small, sampled subset of "query edges." This shift grants the model linear space complexity, allowing discrete diffusion to scale to graphs with thousands of nodes while remaining highly competitive on smaller molecular datasets.
Autoregressive Trees and Sequence Flattening
Another way to avoid the quadratic explosion of the adjacency matrix is to generate the graph sequentially, one piece at a time. Early autoregressive models like GraphRNN, proposed by Jiaxuan You et al. in GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models, used a Breadth-First Search (BFS) node ordering to limit the number of potential edge look-aheads, preventing a full combinatorial explosion. However, the underlying representation still tracked local matrix slices.
To achieve true scalability, Hanjun Dai et al. developed BiGG (Scalable Deep Generative Modeling for Sparse Graphs). Instead of viewing the adjacency matrix as a flat grid, BiGG represents it hierarchically as a tree structure (similar to a quadtree). Because real graphs are sparse, large blocks of the adjacency matrix contain only zeros. BiGG's tree-based recursive structure allows it to prune these empty regions instantly, reducing generation time complexity from $O(N^2)$ to $O((N+M) \log N)$. This framework was later extended to large-scale weighted networks by Richard Williams in Scalable Generative Modeling of Weighted Graphs.
Hierarchical Matrix Representation (BiGG):
[ Root: Contains Edges? Yes ]
/ \
[ Left Half: Empty ] [ Right Half: Has Edges ]
| / \
(Pruned) [ Block A ] [ Block B ]
Alternatively, graphs can be flattened into sequences so they can be processed by highly optimized language modeling architectures. Dexiong Chen et al. introduced AutoGraph in Flatten Graphs as Sequences: Transformers are Scalable Graph Generators, which uses Segmented Eulerian Neighborhood Trails (SENTs) to map a graph's topology into a sequence of tokens. This allows standard decoder-only Transformers to generate graphs with linear scalability.
To optimize the token vocabulary of sequence-based generators, Yunhui Jang et al. proposed the Gap Encoded Edge List (GEEL) in A Simple and Scalable Representation for Graph Generation. Instead of recording absolute node indices, GEEL records the relative numerical "gaps" between connected nodes. Combined with an LSTM and positional encodings, this compact representation bypasses the matrix entirely, running up to 100x faster than traditional diffusion models on graphs with up to 10,000 nodes.
Coarsening and Subgraph Decomposition
A final strategy for mitigating the quadratic bottleneck is to change the resolution at which the generative model operates. Rather than generating a massive graph all at once, models can operate on compressed representations or localized subgraphs.
In LGDC: Latent Graph Diffusion via Spectrum-Preserving Coarsening, Nagham Osman et al. introduced a hybrid approach. LGDC compresses a large graph into a smaller, coarsened version that preserves its spectral properties. The diffusion model runs its computationally intensive denoising steps on this smaller latent graph, which is subsequently expanded back to full resolution. This multi-scale approach captures both global structural properties and fine-grained local details without forcing the diffusion mechanism to process the full node set directly.
Similarly, Puja Trivedi et al. developed SGDM (Editing Partially Observable Networks via Graph Diffusion Models), which restricts the diffusion process to sampled subgraphs. By using global coordinates to maintain structural alignment across subgraphs, the model can perform network editing and generation tasks locally, completely avoiding the $O(N^2)$ cost of global matrix updates.