# Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Graph Generation with K2-trees](https://mlsanity.com/paper/2305.19125/) (2023)
- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)
- [The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections [Extended Version]](https://mlsanity.com/paper/2107.14525/) (2021)
- [Inference-friendly Graph Compression for Graph Neural Networks](https://mlsanity.com/paper/2504.13034/) (2025)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [Learning to Compress Graphs via Dual Agents for Consistent Topological Robustness Evaluation](https://mlsanity.com/paper/2511.18958/) (2025)
- [CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support](https://mlsanity.com/paper/2607.10969/) (2026)

## Abstract (arXiv)

Various graphs such as web or social networks may contain up to trillions of edges. Compressing such datasets can accelerate graph processing by reducing the amount of I/O accesses and the pressure on the memory subsystem. Yet, selecting a proper compression method is challenging as there exist a plethora of techniques, algorithms, domains, and approaches in compressing graphs. To facilitate this, we present a survey and taxonomy on lossless graph compression that is the first, to the best of our knowledge, to exhaustively analyze this domain. Moreover, our survey does not only categorize existing schemes, but also explains key ideas, discusses formal underpinning in selected works, and describes the space of the existing compression schemes using three dimensions: areas of research (e.g., compressing web graphs), techniques (e.g., gap encoding), and features (e.g., whether or not a given scheme targets dynamic graphs). Our survey can be used as a guide to select the best lossless compression scheme in a given setting.