Storing a network graph efficiently means not paying for things that carry no information, such as the arbitrary order in which nodes are numbered. A recent family of lossless coders, called shuffle coding, avoids that cost with a trick named bits-back coding: the encoder "spends" the arbitrary ordering by reading it out of bits it already holds, so those bits are effectively returned. To scale to billion-edge graphs, these coders estimate graph symmetry with color refinement, a cheap procedure that repeatedly relabels each node by the multiset of its neighbors' labels until the labels stop changing. In current systems, though, the probability model that predicts the graph is a fixed textbook model, such as Erdős–Rényi or a preferential-attachment urn. That model accounts for about half the runtime and is badly matched to graphs like Internet router topologies.
This note proposes a single change. The predictive model should be a learned message-passing network that reads only the color-refinement labels. It should also run directly on the collapsed "quotient" graph, in which each group of same-colored nodes becomes one node with integer counts. Inference researchers call this collapse lifting, and they have shown it gives exact results for belief propagation and graph convolutions. The coder already computes these colors to claim its symmetry discount. The claim is that the same partition can do two jobs. It makes a learned model valid for bits-back coding, because the model's output cannot change under permutations the coder treats as free. It also makes that model cheap, because the model only needs one evaluation per color class, not one per node.
Core Claim
In autoregressive shuffle coding (Practical Shuffle Coding), each step does two things. It decodes from the stack which color class the next pinned element comes from, and it then picks the element within that class uniformly. That uniform choice is exactly where bits come back. The probability model therefore only has to output a distribution over the current color classes, never over individual nodes.
Any message-passing model whose input features are the refinement colors gives identical outputs to all nodes of a class. It can therefore be computed exactly on the quotient graph, as shown for graph convolutions by Lossless Compression of Structured Convolutional Models via Lifting and for label propagation by Compressed Label Propagation. The per-step model cost falls from scaling with the number of nodes $n$ to scaling with the number of classes $k$.
The bitrate of the coder is the model's negative log-likelihood minus the symmetry discount. Swapping in a learned model should therefore lower the rate on graphs where urn models fail, while costing far less than running an ordinary graph neural network. The proposal stands or falls on two quantities. The first is the ratio $k/n$ along the decoding trajectory, because partitions refine as more nodes are pinned. The second is whether the learned model's likelihood gain survives after the bits needed to transmit its parameters are counted.
Relation to Prior Work
The method is built from two prior lines. The coding machinery comes from shuffle coding. Entropy Coding of Unordered Data Structures introduced shuffle coding and proved the discount $\log_2 n!
- \log_2|\mathrm{Aut}(G)|$, where $\mathrm{Aut}(G)$ is the group of node relabelings that leave the graph unchanged. That paper computed this group exactly with the canonical-labeling tool nauty, which limits it to small graphs. Practical Shuffle Coding replaced exact symmetry with color refinement, added the pin-and-pop autoregressive scheme, and recomputed refinement only once per chunk of elements. It left the model as a simple ordered graph model, and it reports that model evaluation dominates runtime. We keep its coder unchanged and replace only the model.
The computation trick comes from lifting. Lifted First-Order Belief Propagation and Counting Belief Propagation introduced exact message passing on supernodes. Exploiting symmetries for scaling loopy belief propagation and relational training scaled color refinement with radix sort. The lifting work on convolutional models extended exactness to graph convolutions and reported large training speedups, with roughly 2x for the more expressive Graph Isomorphism Network. None of these works produces a bitstream. We reuse their exactness argument inside an entropy coder.
Two papers constrain the design rather than motivate it. One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding introduced Random Edge Coding, which pairs bits-back coding with a parameter-free urn model and reaches essentially zero gap to that model's likelihood. It loses to ad-hoc compressors on Skitter, which tells us the remaining headroom is in the model, not the coder. The symmetry-breaking result from the loopy belief propagation work warns that informative features split color classes into singletons. That is why our model may take only the refinement colors and pinned status as inputs, and no extra node attributes.
Research Program
We will build a family of color-equivariant predictors. Each predictor runs a few rounds of message passing on the weighted quotient graph of the partially pinned graph. In that graph, an edge between class $i$ and class $j$ carries the count of neighbors each class-$i$ node has in class $j$. Each predictor outputs logits over the classes for "which class is pinned next," along with the edge-attachment probabilities needed to encode that node's connections to the already pinned nodes. Because shuffle coding requires that encoder and decoder see identical partitions at every chunk boundary, the predictor is a deterministic function of quantities both sides hold.
The first technical piece is incremental maintenance of the quotient across chunks. Pinning a chunk only splits existing classes. We will therefore update the lifted computation only for split classes and their neighbors, avoiding a full rebuild. This is where lifting's "unfold first" memory cost has to be avoided.
The second piece is accounting for the model's own size. Predictors will be small, with thousands to tens of thousands of parameters. We will test two settings. In the first, a model is trained once per graph family and shared, so its weights are not counted. In the second, a model is fit to the single graph, and its quantized weights are charged to the bitstream. Only the second setting is a fair comparison with parameter-free Random Edge Coding.
The third piece is an analysis of $k/n$ as a function of the decoding position and the chunk size. This connects to the open chunk-size question in Practical Shuffle Coding. If the classes stay coarse for most of the decoding trajectory, the case for lifting is strong. If they collapse to singletons early, lifting buys little, and we will report that.
Baselines
The naive reference point is ordered coding: the same learned predictor and coder applied to the graph in its given node order, with no bits-back step. This measures the full ordering cost the method is meant to remove.
The strongest existing method on large social graphs is Random Edge Coding. On YouTube it reports 15.19 bits per edge, against 15.38 for pooled compression, 17.03 for SlashBurn and 17.98 for Backlinks (One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding). On YouTube, beating it means falling below 15.19 bits per edge with the model parameters counted. We will rerun it on the same machine and the same graphs, because no Lacuna resource link exists for either codebase and our runs may not reproduce the reported numbers exactly.
The second strong baseline is Practical Shuffle Coding with its original simple models and its default chunking. It defines the rate and speed we must improve on. The file gives no bits-per-edge figure for it, only that it removed 0.8 GB from a 3.4 GB billion-edge Erdős–Rényi graph and ran at megabytes per second. For the molecular sets, Entropy Coding of Unordered Data Structures reports a 46% reduction relative to ordered Erdős–Rényi coding, but the file gives no absolute rates. We will therefore measure both shuffle-coding baselines ourselves.
For Skitter, no reported result was found on Lacuna for the ad-hoc compressors that beat Random Edge Coding, so we will run SlashBurn and Backlinks ourselves.
The key ablation runs the identical learned predictor unlifted, as a standard per-node graph neural network on a GPU. It must produce bit-identical streams, which serves as an exactness check, and it isolates the speed contribution of lifting. A second ablation feeds the predictor features that break the coloring, such as node degree raised to the second hop beyond the refinement depth, or random node identifiers. This shows that the coder's bitrate accounting fails, or that the partition shatters, when the model is not tied to the coloring.
All learned variants get the same tuning budget, a fixed number of fitting steps per graph, and all runs use one commodity CPU plus one GPU.
Why not just…?
Why not just use a better hand-built model, such as a degree-corrected urn fitted to the graph? This is the most serious threat. A cheap parametric model might capture most of the likelihood gap at negligible cost. We will include a fitted degree-corrected model inside the same shuffle coder. If it matches the learned predictor's rate on Skitter and YouTube, we will conclude that the learned model is unnecessary, and the contribution narrows to the speed analysis.
Why not just run an ordinary graph neural network on a GPU and skip lifting? For moderate graphs this might well be fast enough. The unlifted ablation settles the question directly in wall-clock terms, across graph sizes from the TU molecular sets up to YouTube's 9.4M edges. Lifting is justified only if the speedup grows with $n$ and the classes stay coarse. The 2x speedup that the lifting work on convolutional models reports for Graph Isomorphism Networks suggests the gain may be modest for expressive models. We expect it to be larger here because early decoding steps have very coarse partitions, but we treat that as unproven.
Why not just reorder the adjacency matrix heuristically and delta-code it, as SlashBurn or Backlinks do? On YouTube these methods trail Random Edge Coding by about 2–3 bits per edge, according to the reported figures. On Skitter they win. That is exactly the regime where a learned model should help, so our main test is on Skitter against these heuristics.
Why not just cache model outputs by node color? Caching by color is lifting under another name if the model is color-equivariant. If the model is not color-equivariant, the cache is incorrect. The design questions that remain are the incremental quotient updates and the parameter accounting, and those are what we study.
Proposed Experiments
We will evaluate on YouTube, DBLP, Gowalla, Digg, FourSquare and Skitter from the large-network collections, and on MUTAG, ZINC, PROTEINS and IMDB for small graphs. The metrics are bits per edge including parameter bits, encode and decode throughput, the fraction of runtime spent in the model, and $k/n$ traced over decoding.
Two outcomes decide the proposal. The first is whether the lifted learned coder beats the best ad-hoc compressor on Skitter while staying within the speed of Practical Shuffle Coding. The second is whether it goes below 15.19 bits per edge on YouTube with parameters charged.
A secondary check tests whether making the chunk size depend on the measured rate of class splitting improves the rate–speed tradeoff over a fixed chunk size. If the learned predictor wins on likelihood but $k/n$ approaches one early in decoding, we will report a negative result for lifting: the rate gain is real, but it comes from the model and not from the symmetry quotient.
References
- Practical Shuffle Coding
- Lossless Compression of Structured Convolutional Models via Lifting
- Computer Science on the Move: Inferring Migration Regularities from the Web via Compressed Label Propagation
- Entropy Coding of Unordered Data Structures
- Lifted First-Order Belief Propagation
- Counting Belief Propagation
- Exploiting symmetries for scaling loopy belief propagation and relational training
- One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding