# Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs

arXiv: https://arxiv.org/abs/2305.09705 · HTML: https://mlsanity.com/paper/2305.09705/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 16 May 2023.

## Builds on (most cited first, 26 of 26)

- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Variational Diffusion Models](https://mlsanity.com/paper/2107.00630/) (2021)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [Integer Discrete Flows and Lossless Compression](https://mlsanity.com/paper/1905.07376/) (2019)
- [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022)
- [Deep Models of Interactions Across Sets](https://mlsanity.com/paper/1803.02879/) (2018)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation](https://mlsanity.com/paper/2001.08184/) (2020)
- [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019)
- [IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression](https://mlsanity.com/paper/2006.12459/) (2020)
- [DeepZip: Lossless Data Compression using Recurrent Neural Networks](https://mlsanity.com/paper/1811.08162/) (2018)
- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding](https://mlsanity.com/paper/2102.11086/) (2021)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [Edge-based sequential graph generation with recurrent neural networks](https://mlsanity.com/paper/2002.00102/) (2020)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Lossless compression with state space models using bits back coding](https://mlsanity.com/paper/2103.10150/) (2021)
- [Exchangeable Variable Models](https://mlsanity.com/paper/1405.0501/) (2014)
- [Lossless Compression with Latent Variable Models](https://mlsanity.com/paper/2104.10544/) (2021)
- [Compressing Multisets with Large Alphabets using Bits-Back Coding](https://mlsanity.com/paper/2107.09202/) (2021)
- [Edge-exchangeable graphs and sparsity (NIPS 2016)](https://mlsanity.com/paper/1612.05519/) (2016)
- [Zuckerli: A New Compressed Representation for Graphs](https://mlsanity.com/paper/2009.01353/) (2020)
- [Benchmarking Generative Latent Variable Models for Speech](https://mlsanity.com/paper/2202.12707/) (2022)
- [Node-level community detection within edge exchangeable models for interaction processes](https://mlsanity.com/paper/2208.08539/) (2022)

## Built on by (most cited first, 2 of 2)

- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)

## Abstract (arXiv)

We present a one-shot method for compressing large labeled graphs called Random Edge Coding. When paired with a parameter-free model based on P'olya's Urn, the worst-case computational and memory complexities scale quasi-linearly and linearly with the number of observed edges, making it efficient on sparse graphs, and requires only integer arithmetic. Key to our method is bits-back coding, which is used to sample edges and vertices without replacement from the edge-list in a way that preserves the structure of the graph. Optimality is proven under a class of random graph models that are invariant to permutations of the edges and of vertices within an edge. Experiments indicate Random Edge Coding can achieve competitive compression performance on real-world network datasets and scales to graphs with millions of nodes and edges.