Viet-Anh on Software Logo

What is: BiGG?

SourceScalable Deep Generative Modeling for Sparse Graphs
Year2000
Data SourceCC BY-SA - https://paperswithcode.com

BiGG is an autoregressive model for generative modeling for sparse graphs. It utilizes sparsity to avoid generating the full adjacency matrix, and reduces the graph generation time complexity to O(((n+m)logn)O(((n + m)\log n). Furthermore, during training this autoregressive model can be parallelized with O(logn)O(\log n) synchronization stages, which makes it much more efficient than other autoregressive models that require Ω(n)\Omega(n). The approach is based on three key elements: (1) an O(logn)O(\log n) process for generating each edge using a binary tree data structure, inspired by R-MAT; (2) a tree-structured autoregressive model for generating the set of edges associated with each node; and (3) an autoregressive model defined over the sequence of nodes.