Linear Time Graph Generation via Edge Centric Representations

41 concepts31 papers1 proposal

Imagine trying to generate a synthetic social network with a million users. The traditional approach treats the graph as an $N \times N$ adjacency matrix. To decide who is friends with whom, a generative model must evaluate every single pair of nodes. For a million users, that requires making one trillion ($10^{12}$) individual decisions.

This quadratic bottleneck ($O(N^2)$) makes deep generative models for graphs completely impractical for large-scale real-world networks. Real-world networks are almost always highly sparse; the number of actual edges ($M$) is a tiny fraction of the total possible connections.

To break this bottleneck, a powerful paradigm shift has emerged: linear-time graph generation. Instead of iterating over all possible node pairs, these approaches reframe graph generation to scale linearly with the number of edges ($O(M)$) or nodes ($O(N)$). By treating graphs as sequences of edges, recursively traversing matrix quadrants, or generating localized walks, these models bypass the empty space of the adjacency matrix entirely.

From Adjacency Matrices to Edge Sequences

The most direct way to avoid an $O(N^2)$ matrix is to change the representation of the graph itself. If a graph is sparse, we can represent it purely as a list of its edges, transforming a 2D spatial generation problem into a 1D sequence generation problem.

Jang et al. demonstrated this shift in A Simple and Scalable Representation for Graph Generation by introducing the Gap Encoded Edge List (GEEL). Instead of predicting absolute node connections, GEEL models a graph as a sequence of edge-defining tuples using relative "gaps" between node indices. By generating these gaps autoregressively via a simple LSTM, the computational complexity scales linearly with the number of edges rather than quadratically with nodes.

Taking this a step further, recent architectures treat graph generation as a language modeling problem by flattening graphs into token sequences. Chen et al. developed AutoGraph in Flatten Graphs as Sequences: Transformers are Scalable Graph Generators, which flattens graphs into Segmented Eulerian Neighborhood Trails (SENTs). This representation allows standard decoder-only transformers to generate large, sparse graphs with linear scalability relative to the edge count.

To make this sequence-based generation even more efficient, Gao et al. in A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer and Dong et al. in A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer proposed GraphsGPT. Instead of predicting nodes and edges in separate steps, GraphsGPT predicts an edge and its associated endpoint nodes simultaneously as a single unit ("Graph Words"), completely bypassing the traditional link prediction bottleneck.

Traditional Matrix Approach (Quadratic):
[ Node 1 x Node 1 ] -> [ Node 1 x Node 2 ] -> [ Node 1 x Node 3 ] ... (N^2 steps)

Edge-Centric Sequence Approach (Linear):
[ Edge 1: (u1, v1) ] -> [ Edge 2: (u2, v2) ] -> [ Edge 3: (u3, v3) ] ... (M steps)

Recursive Quadrant and Tree-Based Traversal

Another way to achieve near-linear scaling is to use a divide-and-conquer strategy on the adjacency matrix. Think of a sparse matrix like a high-resolution digital image that is mostly black. Instead of scanning every single pixel, you can use a quadtree: if an entire quadrant of the image is empty, you skip it entirely and only recurse into the quadrants that contain pixels.

The authors of Learning multifractal structure in large networks utilized this intuition by designing a hierarchical sampling mechanism. It generates edges by traversing a recursion tree to assign edges to specific node pairs, achieving a complexity of $O(|E| \log |V|)$. Similarly, Dai et al. introduced BiGG in Scalable Deep Generative Modeling for Sparse Graphs. BiGG uses a tree-based recursive structure to exploit graph sparsity, reducing the autoregressive generation time complexity to $O((n+m) \log n)$, which allows it to generate graphs with up to 100,000 nodes on standard hardware.

For stochastic and structural models, quadrant-based recursion provides massive parallelization advantages. Jung et al. developed BalanSiNG in BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks, which generates massive signed networks by recursively sampling quadrants of an adjacency matrix based on probability tensors. This method enables parallelized edge generation that scales logarithmically with the number of vertices and linearly with the number of edges, making the simulation of networks with tens of billions of edges computationally feasible.

Exploiting Sparsity via Bandwidth and Diffusion Constraints

If we cannot flatten or recurse through the graph, we can drastically reduce the search space by placing geometric or state constraints on where edges are allowed to appear.

Real-world graphs often exhibit low "graph bandwidth," meaning that if the nodes are ordered properly, edges will only appear close to the main diagonal of the adjacency matrix. Diamant et al. leveraged this property in Improving Graph Generation by Restricting Graph Bandwidth. By restricting generative models to only predict edges within a narrow diagonal band, they turned a quadratic task into a linear one relative to the number of nodes, achieving up to 14x faster generation without sacrificing graph quality.

Bandwidth-Restricted Adjacency Matrix:
[ X X 0 0 0 ]  <- Edges are only generated
[ X X X 0 0 ]     within a narrow band
[ 0 X X X 0 ]     around the diagonal.
[ 0 0 X X X ]     All 0s are ignored.
[ 0 0 0 X X ]

This optimization principle also applies to diffusion models. Traditional graph diffusion models add noise to the entire adjacency matrix, which forces the model to continuously evaluate a quadratic space. To fix this, Chen et al. introduced EDGE in Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling. Instead of diffusing toward a random noise matrix, EDGE diffuses toward an empty graph by progressively removing edges. By focusing only on active nodes and leveraging the inherent sparsity of the network, the framework reduces the generation complexity to roughly $O(M)$.

Block-by-Block and Walk-Based Assembly

A final strategy for achieving linear time complexity is to change the granularity of the generation steps. Instead of adding a single edge or node at a time, models can generate graphs in larger structural chunks or via continuous paths.

Liao et al. proposed Graph Recurrent Attention Networks (GRAN) in Efficient Graph Generation with Graph Recurrent Attention Networks, which generate graphs by adding blocks of multiple nodes and their associated edges simultaneously. This block-by-block approach reduces the total number of generation steps from quadratic to near-linear relative to the number of nodes, enabling the generation of large-scale graphs with thousands of nodes.

Alternatively, we can generate graphs by synthesizing random walks or node sequences rather than assembling a static structure. Yang et al. in Deep Generation of Heterogeneous Networks and He et al. in Temporal Heterogeneous Graph Generation with Privacy, Utility, and Efficiency utilized walk-based generation within generative adversarial networks (GANs). By training the generator to produce node sequences (walks) rather than full adjacency matrices, these models achieve linear computational complexity relative to the number of nodes. This strategy bypasses the memory constraints that typically cause dense graph models to fail, making it possible to synthesize industrial-scale networks containing millions of entities.

Conclusion

The transition from node-pair iteration to edge-centric, recursive, and constrained sampling has successfully broken the quadratic bottleneck of graph generation. By aligning the underlying data representations and generation mechanics with the sparse reality of real-world networks, these modern frameworks achieve linear-time scaling—unlocking the ability to generate high-quality, synthetic networks at massive scale.

Key Foundational Work

Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs (2012) — contributed 2 concept elements to this direction.
Scalable modeling of real graphs using Kronecker multiplication (2007) — contributed 1 concept elements to this direction.
A Sequential Algorithm for Generating Random Graphs (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_time_graph_generation_bca488cd,
  title = {linear-time graph generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-graph-generation/rdr_bca488cd86b748ceade2fe224c117d41},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_time_graph_generation_bca488cd_v1,
  title = {linear-time graph generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-graph-generation/rdr_bca488cd86b748ceade2fe224c117d41/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake