PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Deep Generative Modeling for Sparse Graphs

Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, Dale Schuurmans

arXiv:2006.15502v1cs.LGstat.ML

TL;DR

Deep graph generative models have been difficult to scale because generating full adjacency matrices has quadratic complexity. BiGG uses graph sparsity in an autoregressive model, and the paper reports comparable or better graph quality while scaling to much larger graphs.

  • Problem

    Deep graph generative models that generate full adjacency matrices require Ω(n^2) time and space, and prior methods have not scaled beyond small graphs.

    Source: §1 · p. 1

  • Method

    BiGG exploits sparsity in an autoregressive graph model, generating sparse graphs in O((n+m) log n) time and parallelizing training with O(log n) synchronization steps.

    Source: §1 · pp. 1–2

  • Results

    BiGG achieves comparable or better quality on benchmarks and large random graphs while scaling to orders of magnitude larger graphs than current deep models.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The paper concludes that time- and memory-efficient parallel training can yield comparable or better quality on benchmark and large random graphs.

    Source: §5 · p. 9

    BiGG models graph topology only and assumes graphs are unattributed.

    Source: §2 · p. 2

Abstract

from arXiv · show

Learning graph generative models is a challenging task for deep learning and has wide applicability to a range of domains like chemistry, biology and social science. However current deep neural methods suffer from limited scalability: for a graph with $n$ nodes and $m$ edges, existing deep neural methods require $\Omega(n^2)$ complexity by building up the adjacency matrix. On the other hand, many real world graphs are actually sparse in the sense that $m\ll n^2$. Based on this, we develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix, and importantly reduces the graph generation time complexity to $O((n + m)\log n)$. Furthermore, during training this autoregressive model can be parallelized with $O(\log n)$ synchronization stages, which makes it much more efficient than other autoregressive models that require $\Omega(n)$. Experiments on several benchmarks show that the proposed approach not only scales to orders of magnitude larger graphs than previously possible with deep autoregressive graph generative models, but also yields better graph generation quality.

1. Introduction

Deep graph generative models offer expressive distributions but have struggled to scale beyond small graphs because generating full adjacency matrices is quadratic. BiGG exploits graph sparsity to improve generation scalability while retaining comparable or better sample quality on benchmarks.

1. Introduction

  • Graph distributions support applications including knowledge graph completion, drug design, architecture search, and program synthesis.Classical graph models capture selected properties but are often too inexpressive for challenging applications; some are hand-engineered for particular graph families.Source: §1 · pp. 1–2
  • Existing deep graph generative models require Ω(n^2) time and space to generate full adjacency matrices, limiting their scalability to large graphs.Prior deep methods modeled small graphs, such as molecules with hundreds of nodes, but did not scale to graphs over 10,000 nodes.Source: §1 · p. 1
  • BiGG exploits sparsity without explicit conditional-independence assumptions, generating sparse graphs in O((n+m) log n) time.Its design combines O(log n) edge generation, a tree-structured autoregressive model for each node's edges, and autoregression over nodes.Source: §1 · p. 1
  • BiGG achieves comparable or superior sample quality while scaling orders of magnitude beyond previous deep graph generative models.The reported benchmarks include synthetic graphs and real-world protein, 3D mesh, and SAT graphs.Source: §1 · p. 2
  • BiGG's training can be synchronized in O(log n) steps, with memory costs of O(√m log n) for training and O(log n) for inference.The model is reported to model graphs with 100k nodes on one GPU.Source: §1 · p. 2

2. Model

BiGG models sparse graphs by generating edges rather than every adjacency-matrix entry, using recursive binary-tree generation and autoregressive conditioning. Its full model has O((n + m) log n) generation time for sparse graphs, with O(n^2) time in the complete-graph case.

2. Model

  • The model focuses on graph topology and uses a single canonical node ordering, estimating graph size from its empirical distribution.Source: §2 · p. 2

2.1. Recursive edge generation

  • BiGG generates each row's edges by recursively halving the node-index interval, specifying a neighbor in at most ceil(log2 n) decisions.This adapts R-MAT's recursive decomposition to a one-dimensional row of the adjacency matrix.Source: §2.1 · pp. 2–3
  • Generating a node's edge-binary tree directly visits each tree node once, taking O(|T_u|) time rather than regenerating every leaf's path.The tree size is at most |N_u| log n.Source: §2.1 · p. 3
  • For hub nodes, the edge-binary tree becomes dense, and direct tree generation approaches O(n) time instead of the Ω(n log n) cost of generating each leaf from the root.Source: §2.1 · p. 3

2.2. Autoregressive conditioning for generating Tu

  • When generating a tree node, BiGG conditions on a top-down context and, for right-child decisions, the generated left subtree's bottom-up context.The top-down context summarizes prior traversal decisions; the bottom-up context summarizes the left subtree.Source: §2.2 · p. 3

2.3. Full autoregressive model

  • A row-binary forest, inspired by Fenwick trees, summarizes preceding row embeddings for autoregressive generation and supports updates in O(log n) time.Its levels organize earlier edge-binary-tree embeddings into a prefix summary.Source: §2.3 · pp. 4–5
  • O((n + m) log n) generation time for sparse graphs; the complete-graph case takes O(n^2).The full model's cost is O(n log n + sum_u |T_u|); for complete graphs, each tree has 2n − 1 nodes.Source: §2.3 · p. 5

3. Optimization

BiGG's training procedure exploits known edge-binary trees to parallelize embedding computations. It needs O(log n) synchronization steps across tree depths, unlike a sequential autoregressive LSTM's Ω(L) synchronization for a sequence of length L.

3. Optimization

  • BiGG's training optimization targets single-graph likelihood computation, with extension to multiple graphs described as straightforward.Source: §3 · p. 5

3.1. Training with O(log n) synchronizations

  • A sequential LSTM requires Ω(L) synchronized computation for a sequence of length L, motivating greater concurrency during BiGG training.Source: §3.1 · p. 5
  • O(log n) synchronization steps suffice to compute bottom-up embeddings, since nodes at the same tree depth can be processed concurrently.Source: §3.1 · p. 5

2. Computing gi

Training is organized into four stages, each requiring O(log n) synchronization. The section also describes distributed training, memory-reduction methods, and position encodings for BiGG.

2. Computing gi

  • All four training stages require O(log n) synchronization, allowing more efficient training of large graphs than a simple sequential autoregressive model.The stages include independently batched LSTMs for row states and top-down tree processing for likelihood computation.Source: §2 · p. 5

3.2. Model parallelism

  • Dividing the adjacency matrix into consecutive row chunks enables concurrent computation, while cross-GPU g-messages create dependencies bounded by the row-binary forest's O(log n) depth.The g-messages travel in the opposite direction during the backward pass.Source: §3.2 · p. 6

3.3. Reducing memory consumption

  • Chunked-row training keeps only inter-chunk g-messages and recomputes tree embeddings; its memory cost is O(√m log n), with one extra Stage 1 feedforward.The section says this additional feedforward does not hurt training speed much.Source: §3.3 · p. 6
  • For intervals of length at most L, ternary vectors encode interval length and adjacency, allowing subtree neural computation to be skipped; L=256 saved 50% of training memory without information loss.The representation uses vectors in {-1, 0, 1}^L.Source: §3.3 · p. 6

3.4. Position encoding:

  • Adding sinusoidal position encodings for interval span and row position supplies future context that can improve generation quality.The interval encoding uses PE(vr − vl), and the row encoding can use PE(n − u).Source: §3.4 · p. 6

4. Experiment

The experiments compare BiGG’s graph quality with prior models and test its runtime, memory use, and quality as graphs grow. Across these settings, results show strong benchmark performance and scalability, with some training-time limits on a single GPU.

4.1.1. GENERAL GRAPHS

  • General-graph evaluation uses held-out graph-distribution MMDs for degree, clustering, orbit count, and normalized-Laplacian spectra, plus a Lobster validity error rate.The benchmark includes Grid, Protein, Point cloud, and Lobster datasets, with baselines copied from Liao et al. (2019).Source: §4.1.1 · p. 7
  • BiGG outperforms all compared methods on four general-graph datasets; on the largest, GraphVAE and GraphRNN run out of memory while BiGG’s orbit metric is two magnitudes better than GRAN.Table 1 reports degree, clustering, orbit, and spectral MMD metrics, for which smaller values are better.Source: §4.1.1 · p. 7, Table 1 · p. 8

4.1.2. SAT GRAPHS

  • BiGG mostly recovers training-instance statistics for SAT graphs, while G2SAT outperforms it on 4/6 test-set metrics and BiGG is more prone to overfit the small training set.The experiment uses 24 training and 8 test SAT instances; the test-set comparison is reported in Appendix B.3.Source: §4.1.2 · p. 7, Table 2 · p. 8

4.2.1. RUNTIME AND MEMORY COST

  • Single-graph inference time aligns with O((n + m) log n) on grid graphs where m = Θ(n).The scalability experiment tests graph sizes from 100 to 100k nodes.Source: §4.2.1 · p. 8
  • Training time is O(log n) under an infinite-FLOPS assumption, but grows linearly for larger graphs on a single GPU because of FLOPS and RAM limits.The reported O(log n) behavior is consistent with measurements below 5,000 nodes.Source: §4.2.1 · p. 8
  • Peak training memory grows as O(√m log n), a sublinear trend that scales beyond sparse graphs with 100k nodes.The experiment selects the optimal number of chunks as suggested in Section 3.3.Source: §4.2.1 · p. 8

4.2.2. QUALITY W.R.T GRAPH SIZE

  • On grid graphs up to 100k nodes, BiGG preserves high quality, while GRAN fails to train beyond 50k nodes because of RAM or file-I/O limitations.Quality is evaluated with orbit MMD because spectra are infeasible to calculate for the largest graphs.Source: §4.2.2 · p. 9, Table 3 · p. 9

4.3. Ablation study

The ablations examine how node ordering and edge density relate to BiGG’s performance. BFS and DFS are consistently effective, and BiGG remains close to the ground truth across tested random-graph densities.

4.3.1. BIGG WITH DIFFERENT NODE ORDERING

  • BFS and DFS give consistently good performance, while BiGG can accept other node orders, leaving ordering selection open for future research.The authors attribute BFS/DFS performance to reduced tree-width and suggest them as defaults.Source: §4.3.1 · p. 9, Table 4 · p. 9

4.3.2. PERFORMANCE ON RANDOM GRAPHS WITH DECREASING SPARSITY

  • Across tested edge densities, BiGG performs consistently better than GRAN and remains close to the ground-truth Erdos-Renyi model.The comparison uses spectral MMD on Erdos-Renyi graphs averaging 500 nodes.Source: §4.3.2 · p. 9, Table 5 · p. 9

5. Conclusion

BiGG is presented as a scalable autoregressive model for general graphs, with sparse-graph complexity and efficient parallel training. The authors report comparable or better quality on benchmark and large random graphs, and identify attributed graphs as future work.

5. Conclusion

  • For sparse graphs, BiGG has O((n + m) log n) complexity, improves on prior Ω(n²) algorithms, and uses efficient parallel training while matching or surpassing quality on benchmarks and large random graphs.The stated future direction is scaling further while modeling attributed graphs.Source: §5 · p. 9

A. Detailed discussion of related work

The related-work discussion contrasts classical models with deep graph generative approaches. It describes autoregressive methods as expressive but costly on large graphs, and positions BiGG as an advance in scalability and quality.

Traditional generative models

  • Classical graph models target properties such as degree distribution, diameter, and eigenvalues, while many are hand-engineered for particular graph families.The discussion also describes models of local structural features and models combining global dense patches with local structure.Source: A. Detailed discussion of related work · p. 12

Deep graph generative models

  • Deep neural graph models are typically more expressive than classical random-graph models, but at higher computational cost.VAE- and GAN-based methods are described as generating large parts or all of the adjacency matrix independently, limiting their ability to model complex structures.Source: A. Detailed discussion of related work · p. 12
  • Autoregressive methods gain expressivity by generating graphs sequentially but are costly for large graphs; GraphRNN and GRAN reported generation up to 5,000 nodes, while BiGG advances both quality and scalability.Domain-specific graph models also use domain knowledge for molecule graphs and SAT instances, including (Kusner et al., 2017; Dai et al., 2018; Jin et al., 2018; Liu et al., 2018) and.Source: A. Detailed discussion of related work · p. 12

B. More experiment details

BiGG enables parallel cell operations through manual batching and retains shared cell parameters. The authors keep parameter sharing because per-layer parameters did not significantly affect performance and would enlarge the model.

B. More experiment details

  • Manual batching enables parallel tree or LSTM cell operations by gathering and dispatching their inputs.The authors use one CUDA GEMM instead of multiple cell-operation GEMV calls.Source: B. More experiment details · p. 12
  • A custom C++ operation computes the indices used to gather and dispatch cell inputs.Source: B. More experiment details · p. 12
  • BiGG shares cell parameters because per-layer parameters did not significantly change performance and would make the model O(log n) times larger.The authors also note that per-layer parameters could make learning harder and limit generation beyond training graph sizes.Source: B. More experiment details · p. 12

B.1. BiGG setup

The appendix reports BiGG’s training settings and the SAT-formula sets used for its experiments. It also specifies the single-GPU setup and the block size for sparse-graph training.

B.1. BiGG setup

  • BiGG uses embedding size d = 256, position encoding, and a learning rate decaying from 1e−3 to 1e−5 when training loss plateaus.Source: §B.1 · p. 12
  • Experiments use a single V100 GPU, with sparse-graph block size set to 6,000 to fit training while minimizing synchronization overhead.The number of blocks is chosen as small as possible while allowing training to fit on that GPU.Source: §B.1 · p. 12
  • Table 7 reports test and generated graph statistics using 8 SAT formulas.Source: Table 7 · p. 13
  • BiGG is trained on 24 SAT formulas, and Table 6 reports training and generated graph statistics for 10 SAT formulas.Source: §B.1 · p. 13, Table 6 · p. 13

B.2. Baselines setup

The baseline protocols combine previously reported results with additional runs where literature numbers are unavailable. The appendix gives method-specific settings for those additional baseline comparisons.

B.2. Baselines setup

  • The authors use baseline numbers from original papers when applicable and run methods when their results are unreported.Source: §B.2 · p. 13
  • For grid graphs, Erdős–Rényi graphs are generated using edge density estimated from training graphs and compared with held-out test graphs.Source: §B.2 · p. 13
  • GraphRNN-S is trained for 3,000 epochs to obtain the Lobster random-graph result.The run uses the official code.Source: §B.2 · p. 13
  • GRAN is trained with the grid-graph configuration for up to 8,000 epochs or 3 days, whichever limit is reached first.Source: §B.2 · p. 13
  • G2SAT is run for 1,000 epochs, and its test-graph comparison uses the 8 test graphs as template graphs.Source: §B.2 · p. 13

B.3. More experimental results on SAT graphs

On a 10-instance SAT subset, BiGG-0.1 nearly recovers training statistics, while G2SAT outperforms BiGG on most reported test metrics. The passage attributes G2SAT’s advantage to its bipartite-graph specialization and notes that BiGG may need more data.

B.3. More experimental results on SAT graphs

  • 4 of 6 metrics favor G2SAT over BiGG on the SAT test comparison.The passage attributes this advantage to G2SAT’s specialized bipartite-graph inductive bias, particularly in low-data and extrapolation settings.Source: §B.3 · p. 13
  • 90% greedy decoding lets BiGG-0.1 almost perfectly recover training statistics on the 10-instance SAT subset.The subset has 82 to 1,122 variables and 327 to 4,555 clauses, yielding graphs with at most 6,799 nodes.Source: §B.3 · p. 13
  • BiGG’s general-purpose model is expected to require more training data than specialized G2SAT because of its higher model-space capacity.Source: §B.3 · p. 13

Related papers

Loading 2006.15502v1…