Entropy Coding of Unordered Data Structures

We present shuffle coding, a general method for optimal compression of sequences of unordered objects using bits-back coding. Data structures that can be compressed using shuffle coding include multisets, graphs, hypergraphs, and others. We demonstrate that the method achieves state-of-the-art compression rates on a range of graph datasets including molecular data, and release an implementation that can easily be adapted to different data types and statistical models.