# Grammar-Based Graph Compression

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2017.

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

- [CircuitFormer: A Circuit Language Model for Analog Topology Design from Natural Language Prompt](https://mlsanity.com/paper/2605.05773/) (2026)
- [Directed Graph Grammars for Sequence-based Learning](https://mlsanity.com/paper/2505.22949/) (2025)

## Abstract (arXiv)

We present a new graph compressor that works by recursively detecting repeated substructures and representing them through grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. Specific queries such as reachability between two nodes or regular path queries can be evaluated in linear time (or quadratic times, respectively), over the grammar, thus allowing speed-ups proportional to the compression ratio.