Research map / Graph learning / Graph self-supervised learning
Entropy Coding of Unordered Data Structures
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 shuffle coding, a bits-back/rANS-based general method for optimally compressing sequences of unordered objects (multisets, graphs, hypergraphs), and evaluates it on TUDatasets and SZIP datasets with Erdős-Rényi and Pólya urn models.
Problem
Lossless compression of unordered data structures (e.g., unlabeled graphs, multisets) where the ordering carries redundant information, so the optimal rate should discount log n! minus log automorphism group size.
Approach
A generic codec that uses bits-back with ANS to decode a uniformly random coset of the automorphism group (via canonical orderings from nauty/Traces) as part of encoding, so the redundant ordering is removed; it works with any statistical model for ordered objects and achieves the optimal rate on sequences of unordered objects.
Key results
- Shuffle coding with an Erdős-Rényi model yields a 26-47% rate improvement over ordered ER coding across TUDataset graph types (e.g., 2.11 to 1.14 bits per edge for small molecules).
- On PnC datasets, shuffle coding with ER achieves 1.88 bits per edge on MUTAG versus 2.45 for PnC, and 1.82 on ZINC_full versus 1.99 for PnC.
- On single SZIP graphs (net rate), the Pólya urn shuffle coding model beats SZIP on all six datasets, e.g., 2.90 vs 3.81 bits per edge on Airports (USAir97).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use shuffle coding with the ER model instead of ordered ER coding | TUDatasets graph types · Small molecules | bits per edge: 2.11 -> 1.14 | Helped |
| use shuffle coding with the ER model instead of ordered ER coding | TUDatasets graph types · Bioinformatics | bits per edge: 9.20 -> 6.50 | Helped |
| use shuffle coding with the ER model instead of ordered ER coding | TUDatasets graph types · Computer vision | bits per edge: 6.63 -> 4.49 | Helped |
| use shuffle coding with the ER model instead of ordered ER coding | TUDatasets graph types · Social networks | bits per edge: 3.98 -> 2.97 | Helped |
| use shuffle coding with the ER model instead of ordered ER coding | TUDatasets graph types · Synthetic | bits per edge: 5.66 -> 2.99 | Helped |
| use maximum-likelihood categorical parameters instead of uniform attribute distributions (ablation) | Shuffle coding ER · MUTAG (with attributes) | bits per edge: 6.37 -> 4.20 | Helped |
| use maximum-likelihood categorical parameters instead of uniform attribute distributions (ablation) | Shuffle coding ER · PTC_MR (with attributes) | bits per edge: 8.04 -> 4.88 | Helped |
| disallow edge redraws and self-loops (ablation) | Shuffle coding Pólya urn · MUTAG | bits per edge: 2.81 -> 2.66 | Helped |
| disallow edge redraws and self-loops (ablation) | Shuffle coding Pólya urn · MUTAG (with attributes) | bits per edge: 5.13 -> 4.97 | Helped |
| disallow edge redraws and self-loops (ablation) | Shuffle coding Pólya urn · PTC_MR | bits per edge: 2.74 -> 2.53 | Helped |
| disallow edge redraws and self-loops (ablation) | Shuffle coding Pólya urn · PTC_MR (with attributes) | bits per edge: 5.61 -> 5.40 | Helped |
| disallow edge redraws and self-loops (ablation) | Shuffle coding Pólya urn · ZINC_full | bits per edge: 2.75 -> 2.63 | Helped |
Surprising findings
- PnC outperforms shuffle coding on social network datasets (IMDB-BINARY 0.54 vs 1.50 bits per edge with PU), where the simple models fit poorly.
- Disallowing edge redraws and self-loops in the Pólya urn model improves rate, breaking exchangeability and requiring an ELBO-based rate.
Limitations
- Canonical ordering and automorphism group computation have no known polynomial-time algorithm for graphs, so the method is impractical in the worst case.
- Optimal rate is only achieved for sequences; one-shot coding incurs initial bits overhead of O(log n!) bits.
- Relies on simple statistical models; performance lags PnC on some datasets such as social networks.
Experimental setup
Datasets: TUDatasets SZIP datasets (Airports USAir97, YeastS, etc.) PnC datasets (MUTAG, PTC_MR, ZINC_full, PROTEINS, IMDB-BINARY, IMDB-MULTI)
Benchmarks: TUDatasets SZIP datasets PnC datasets
Metrics: bits per edge compression speed (kB/s) discount (bits)
Baselines: PnC (Partition and Code) SZIP Ordered Erdős-Rényi coding
Builds on: bits-back with ANS Pólya urn graph model multiset compression with bits-back
Closest papers by meaning
- Practical Shuffle Coding (NeurIPS 2024 · similarity 0.94)
- Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding (NeurIPS 2024 · similarity 0.85)
- Accelerating Relative Entropy Coding with Space Partitioning (NeurIPS 2024 · similarity 0.85)
- Minimum Entropy Coupling with Bottleneck (NeurIPS 2024 · similarity 0.83)
- SlimSAM: 0.1% Data Makes Segment Anything Slim (NeurIPS 2024 · similarity 0.82)
- Debiased Distribution Compression (ICML 2024 · similarity 0.82)
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.