Research map / Graph learning / Graph algorithms and clustering
Practical Shuffle Coding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes faster shuffle-coding variants (incomplete and autoregressive) that enable one-shot, near-optimal lossless compression of unordered objects such as multisets and graphs at megabytes-per-second speeds.
Problem
Shuffle coding for unordered data (multisets, graphs) is impractical: joint shuffle coding has a large initial bit cost for one-shot compression and needs exact automorphism groups, which are slow or intractable for large graphs.
Approach
Two variants: incomplete shuffle coding replaces exact automorphism groups with those of color-refinement-based incompletely ordered objects, and autoregressive shuffle coding progressively decodes the permutation while encoding slices, realizing most of the discount in one-shot rate; chunking reduces color refinement runs to make it near-linear in edges.
Key results
- Incomplete joint shuffle coding increases rate by only 0.1–4% on TU datasets while giving speedups up to a factor of one million over complete joint shuffle coding.
- Autoregressive shuffle coding with AP model gives significantly better rates than SZIP on SZIP graphs at practical speeds largely independent of graph size.
- Autoregressive shuffle coding handles a random graph with one billion edges (3.4 GB uncompressed), saving 0.8 GB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace complete joint shuffle coding with incomplete joint shuffle coding using 3 color-refinement convolutions | Joint shuffle coding with the Erdős-Rényi model · TU small molecules | rate (bits per edge): 1.14 -> 1.19 | Hurt |
| Replace complete joint shuffle coding with incomplete joint shuffle coding using 3 color-refinement convolutions | Joint shuffle coding with the Erdős-Rényi model · TU bioinformatics | rate (bits per edge): 6.50 -> 6.51 | Hurt |
| Replace complete joint shuffle coding with incomplete joint shuffle coding using 3 color-refinement convolutions | Joint shuffle coding with the Erdős-Rényi model · TU social networks | rate (bits per edge): 2.97 -> 2.97 | No clear effect |
| Replace complete joint shuffle coding with incomplete joint shuffle coding using 3 color-refinement convolutions | Joint shuffle coding with the autoregressive Pólya urn model · SZIP Collaboration (geom) | net rate (bits per edge): 4.57 -> 4.84 | Hurt |
| Use 10 uniform chunks instead of full autoregressive coding (ablation) | Multiset 1k · Multiset 1k | compression rate (bits): 1833 -> 2707 | Hurt |
| Use 10 geometric chunks with base 18% instead of full autoregressive coding (ablation) | Multiset 1k · Multiset 1k | compression rate (bits): 1833 -> 2443 | Hurt |
| Use 10 geometric chunks with base 18% instead of 10 uniform chunks (ablation) | Multiset 1k · Multiset 1k | compression rate (bits): 2707 -> 2443 | Helped |
| Use 10 uniform chunks instead of full autoregressive coding (ablation) | Multiset 10k · Multiset 10k | compression rate (bits): 8744 -> 17598 | Hurt |
| Use 10 geometric chunks with base 49% instead of 10 uniform chunks (ablation) | Multiset 10k · Multiset 10k | compression rate (bits): 17598 -> 14988 | Helped |
| Use 10 uniform chunks instead of full autoregressive coding (ablation) | Multiset 100k · Multiset 100k | compression rate (bits): 68912 -> 157690 | Hurt |
| Use the autoregressive Pólya urn model instead of the Erdős-Rényi model | Shuffle coding on SZIP graphs · SZIP graphs | compression rate | Helped |
| Use incomplete rather than complete joint shuffle coding | Joint shuffle coding on graphs · TU and SZIP graph datasets | compression rate | Mixed |
Surprising findings
- On incomplete joint coding of SZIP graphs, the geom collaboration graph shows a 7.1% rate increase, larger than other graphs.
Limitations
- Incomplete shuffle coding gives slightly suboptimal rates when color refinement fails to separate automorphisms, e.g. 7.1% increase on one SZIP graph.
- Chunk sizes are chosen approximately equal for graphs; optimal non-uniform chunking left unexplored.
- Autoregressive model for ordered graph is not yet optimized; roughly half of runtime is spent in it.
Experimental setup
Datasets: SZIP graphs TU datasets REC graphs Erdős-Rényi random graphs G(n,m) multisets sampled from Dirichlet-categorical
Benchmarks: SZIP graphs TU datasets REC graphs random ER graphs up to 1B edges multisets of 1k to 10M elements
Metrics: net bits per edge compression speed (kB/s, MB/s) decompression speed
Baselines: SZIP PnC complete joint shuffle coding Severo et al. 2023a
Builds on: Kunze et al. 2024 joint shuffle coding Severo et al. 2023a multiset one-shot codec bits-back asymmetric numeral systems
Closest papers by meaning
- Entropy Coding of Unordered Data Structures (ICLR 2024 · similarity 0.94)
- SlimSAM: 0.1% Data Makes Segment Anything Slim (NeurIPS 2024 · similarity 0.84)
- Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding (NeurIPS 2024 · similarity 0.83)
- LotteryCodec: Searching the Implicit Representation in a Random Network for Low-Complexity Image Compression (ICML 2025 · similarity 0.82)
- Debiased Distribution Compression (ICML 2024 · similarity 0.82)
- Accelerating Relative Entropy Coding with Space Partitioning (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.