Practical Shuffle Coding
Authors: Julius Kunze
Daniel Severo
Jan-Willem van de Meent
James Townsend
Venue: NeurIPS 2024 poster (2024)
Keywords: graph compression
entropy coding
bits-back coding
lossless compression
generative models
information theory
probabilistic models
graph neural networks
multiset compression
asymmetric numeral systems
compression
entropy
shuffle coding
Primary area: probabilistic_methods
TL;DR: We present a general method for practical lossless compression of unordered data structures that achieves state-of-the-art rates and speeds on large graphs.

Abstract: We present a general method for lossless compression of unordered data structures, including multisets and graphs. It is a variant of shuffle coding that is many orders of magnitude faster than the original and enables 'one-shot' compression of single unordered objects. Our method achieves state-of-the-art compression rates on various large-scale network graphs at speeds of megabytes per second, efficiently handling even a multi-gigabyte plain graph with one billion edges. We release an implementation that can be easily adapted to different data types and statistical models.

Practical Shuffle Coding
Julius Kunze University College London jul iuskunze@gmail com
Daniel Severo
University of Toronto Vector Institute d. www.ree..aaaonnn..eeeeeeeeee
Jan- Willem van de Meent University of Amsterdam j. vandemeent@uva. nl
James Townsend University of Amsterdam
.h.n. townsendeuva.n
Abstract
We present general method for lossless compression of unordered data structures, including multisets and graphs. It a variant of shuffle coding that is many orders of magnitude faster than the original and enables 'one-shot' compression of single unordered objects. Our method achieves state-of-the-ar compression rates on various large-scale network graphs at speeds of megabytes per second, efficiently handling even multi-gigabyte plain graph with one billion edges. We release an implementation that be easily adapted to different data types and statistical models.
Introduction
Big data is often contained in unordered objects, such sets, multisets, graphs, hypergraphs. Unlike ordered data types like text, audio, and video, the order of elements these structures is irrleevnt and represents redundant information. Recent work by Kunze al. (2024) shows that eliminating this redundancy can lead to significant storage and transmission savings. It proposed shuffle coding, an entropy coding method based on bits-back (Townsend et al., 2019) with asymmetric numeral systems (ANS; Duda, 2009) that approaches optimal compression rates for sequences of unordered objects. However, their specific method, which we will refer as complete joint shuflle coding, has two major limitations that make it impractical for large unordered data structures: It incurs a prohibitive initial bit cost in one-shot scenarios where only single unordered object needs to be compressed, and it requires the exact computation of automorphism groups which is often slow or completely intractable, for example for large graphs.
To overcome these limitations, we propose two new variants, autoregressive and incomplete shuffle coding. Autoregressive shuffle coding builds recent work by Severo et al. (2023a), which constructed an optimal one-shot codec for multisets from a codec of vectors by storing information in an ordering. This method depends the simple structure of multisets' automorphism groups, and does not extend to other unordered objects such as unlabeled graphs. Autoregressive shuffle coding generalizes this method arbitrary unordered objects. Incomplete shuffle coding approximates an object's 's symmetries, enabling compression despite intractable automorphism groups. These two variants can be combined into method allowing one-shot compression of large unordered data structures at practical speeds.
Our experiments show that our perforarformanc implementation matches the optimal compression rates from Severo et al. (2023a) for multisets, but is orders of magnitude faster. Similarly, it many orders of magnitude faster than joint shuffle coding for medium-sized graphs of various types with minimal rate increase. We also compress much larger unordered graphs, including social network graphs and random graphs with up billion edges, which are infeasible for complete shuffle
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

coding. We show that the rate discount from removing order information is large, as previously shown for joint shuffle coding on many smaller graph datasets, and that we achieve state-of-the-eee graph compression rates at practical speeds when using models with minimal parameters. We release source code' which can extended easily to new models and classes of unordered objects other than multisets and graphs.
The structure of the paper is follows: Section 2 reviews the necessary background, including permutable classes, unordered objects and codecs. Sections 3 and 4 detail our incomplete and autoregressive shuffle coding variants. We discuss related work in Section 5, our experimental results in Section 6, and conclude in Section 7 with future research directions. Proofs are in Appendix B.
2
Background
Table 1: Examples for key concepts from Section 2 for the permutable class F of ASCII strings of length K...B denotes multiset, and we use cycle notation for permutations.
Concept
Example
Permutation
(0. 2), Sz
Permutable class
F = faaaaa, aa.ab....
Ordered object
sense E
(0,2) sense nesse
If SENSE Sense sense ... (~ is equality up to casc),
Quotient class
sense,, = {SENSE, Sense, sense.... E F. (0,2) sense, = nesse.
Unordered object Automorphisms
sense ((s, e, n, s, e} (sense, esnse, ensse, enses, snese, ... E F Aut(sense) = {0)), (0, 3), (1, 4), (),
This paper is concerned with compression of unordered objects. Kunze et (2024) define these in terms of equivalence classes which comprise ordered objects that are identical up to re- re-ordering. We introduce ordered and unordered objects in Section 2.1, as well as how equivalence classes of ordered objects can form ordered objects themselves, central idea of this paper. We review codecs in Section 2.2 and the optimal compression rate for unordered objects in Section 2.3. We provide a summary of concepts through examples in Table 1.
2.1 Permutable classes
Concepts from group theory, including subgroups, actions, stabilizers, and orbits are used throughout. We provide a brief introduction in Appendix A.
For E N. we let [x] {0, I,..., 1}. with [0] 0. For this paper, it is convenient to
identify
permutations purely by their cycle notation, such that we can apply a permutation of order to any objects of order i. This can be achieved by defining the symmetric group S, on the subset of bijections/ f + IN with f(i) = for all E N \ [n], leading to
S. = Stabs,, (1) < S1+1-
From here on, we use the shorthand H < G to mean that H/ is a subgroup of G. Staba(i) denotes the stabilizer with respect E [n]] of group < S,, acting on the indices [n].
We will consider objects which can be 're-ordered' by applying permutations. This is captured in the following definition from Kunze et al. (2024):
Definition 2.1 (Permutable class). For n E N, a permutable class F of order n is a pair of a set F and left group action of the permutation group S., on F, which we denote with the binary operator. We also use F to refer to the underlying set F. We refer to the elements of as ordered objects.
Strings are ordered objects, and so are labeled graphs because their vertices can be re-ordered. Equivalence classes of ordered objects can themselves form a permutable class. For example, case- insensitive ASCII strings naturally are ordered objects, and can be defined as the equivalence classes
Source code, data and results available https: // thub. com/ http://.o./.cconnneeeeee huw.uuuuukneeessuflle-oooiiii

---

of such strings under an equivalence relation ~ that indicates equality up to character case, as illustrated in Table As shown in Appendix B.1, this happens whenever the equivalence relation preserved under permutations, in the following sense:
Definition 2.2 (Congruence, quotient class). We say equivalence relation
a permutable
class F = .) of order n is a congruence if 8 ~ 8 g holds if f ~ for all f.g E F and E S, Then, the quotient set F/~ equipped with the operator
S, x (F/~) + F/~ with f- = {s f E f-} forms permutable class of order n, which we refer to as the quotient class of F by ~,, denoted as F/~. For f E use fa denote the equivalence class under containing f.
We define unordered objects as equivalence classes comprising ordered objects that are identical up to re-ordering, an important special case of Definition 2.2:
Definition 2.3 (Isomorphism, unordered objects). For two objects f and g in a permutable class F, we say that f is isomorphic to g. and write f ~ g, if there exists Sn such that g isomorphism relation = is congruence, inducing a quotient class unordered objects that we will denote as F = F/c,, and the unordered object containing some f E F as f == fm.
The
Unordered strings then correspond to multisets (for example see = e, = (see, ese, ees}) and unordered graphs to unlabeled graphs. The of permutations that, when applied to ordered object, do not change it, forms a group indicating its 'symmetries':
Definition 2.4 ( (Automorphism group). For an element f of a permutable class F, we let Aut(f) denote the automorphism group of f. defined by Aft == {s E S, = f].
For the example of unordered objects, every element's automorphism group comprises all permuta- tions, Aut(f) = Sn.
2.2 Codecs
Shuffle coding requires stack-like (LIFO) codecs, such as those based on the range variant of asymmetric numeral systems (rANS: Duda, 2009), to save bits corresponding to the redundant order using bits-back (Townsend et al., 2019). To define these, we fix a set M prefix-free binary messages, and length function I: M + oo). which measures the number of physical bits required to represent values in M. We rely on the following definition from Kunze et al. (2024):
Definition 2.5 (Codec). A slack-like codec (or simply codec) for set X is an invertible function encode M x X + M. We call codec optimal for a probability distribution over X with mass M and E X. the message length 1 satisfies" I(encode .r) se
function P if for any 1(m) + log P(a). We refer to log P(z) as the optimal rate and to the inverse of encode as decode. Since decode has to be implemented in practice, we treat it as an explicit part of a codec below.
1
The encode function requires a pre-existing message as its first input. Therefore, at the beginning of encoding we m equal to some fixed, short initial message mi, with length less than 64 bits. As in other entropy coding methods, which invariably have some small constant overhead, this 'initial bit cost' amortized as we compress more data.
2.3 Optimal rate for unordered objects
Our codec will be based probability distribution with mass function P over ordered objects from a permutable class F. Then, for any equivalence relation ~ on F, a joint distribution P(f g) with equivalence classes f- E F/rr is induced by sampling an ordered object y E F from P. and returning its corresponding equivalence class, resulting in
P(f~)
Σ P(g). ge
"This condition, with suitable definition of ~2 is equivalent to rate-optimality in the usual Shannon sense, Townsend (2020).
3

---

We will implicitly assume this induced distribution over quotient classes, even in nested cases. Kunze al. (2024) specify the optimal rate any codec for unordered objects f.
n!
log
log P(J)
log (f)
P(f)
Ordered rate
Discount
assuming, without loss of modeling power, that P(f) is exchangeable, meaning invariant under permutations of f.
3
Incomplete shuffle coding
Table 2: Example for color refinement as defined in Appendix C on plain graphs with 0 and 1 convolutions, and the resulting incompletely ordered graphs according to Definition 3.1. Colors only visualize correspondence to the resulting hashes, they are not materialized in the graph. The actual hashes, characters in the example, depend the specific hash function used. Co bases each vertexes' hash on its degree only, while C1 also takes the multiset of neighboring hashes from Co into account. The automorphism group of the incompletely ordered graph is the same that for the string of vertex hashes, and color partitions correspond to their orbits.
Coloring
Incompletely ordered graph
Co
3-4
4
aaacd
3-4,
1
3-4
~Co
Ci
3-4
= babed
3
Complete joint shuffle coding, as presented in Kunze al. (2024), relies on function retrieve (a list of generators of) the automorphism group Aut(f), as well as the canonization for any given ordered object f. No polynomial-tine time algorithm is known compute this function for graphs. Accordingly, their results show that the method is impractically slow even for moderately sized graphs.
In this section, we will introduce method that gives shuffle coding reliably fast runtime for graphs. To achieve this, we will in return accept slightly suboptimal compression rates. Instead of recovering the exact order and therefore realizing the complete bit discount, we can ignore some hard-to-compute information about the order to improve runtime. Specifically, we can treat isomorphic objects that are hard to distinguish as elements of the same 'incompletely ordered' object, formalized as follows:
Definition 3.1 (Incompletely ordered objects). We refer to the elements a quotient class F/r as incompletely ordered objects if f~ C f for all F.
We show in Appendix B.3 that their unordered objects F/r correspond to the original unordered objects F through the bijection f.f. leading to
1 log P(f) log P(f_) log
AAut(f~) [Aut()]
(4)
Equation (4) reveals the rate increase compared to the optimal rate if we suboptimally code fa by representing it by an arbitrary f E faw and using a codec optimal for P(f)-
We can apply joint shuffle coding to incompletely ordered objects, approach refer to as incomplete joint shuffle coding, We are then not recovering the 'hard-to-compute" bits to distinguish
LLibaaries commonly used in practice such as nauty and Traces (McKay and Piperno, 2014) have exponen- tial case runtime. An algorithm with quasi polinooooooaa runtime complexity is known (Babai, 2016, 2019; Helfgott et al., 2017), but is complicated that it has never been implemented.

---

elements within f~r leading to a rate increase given by Equation (4) over the optimal rate. This requires two functions determining the automorphism group Aut(fa.) and canonization f~ for any given such f~. In the next section, we introduce a choice for ~ that makes these functions and therefore incomplete joint shuffle coding practical for graphs.
Any function C' on F with the relation defined by C(f) C(g) being a congruence has an associated class of incompletely ordered objects F/~c through f ~C exactly if = g and ((f) = C(g). The color refinement algorithm, also known as the 1-dimensional version of the algorithm of Leman and Weisfeiler (1 (1968), is practical choice for such a function for graphs. It returns a string of n vertex 'colors' that were iteratively refined by hashing local features through graph convolution, starting from the vertex degrees, as visualized in Table 2, and formalized in Appendix C. As discussed there, any >> convolutions suffice to find the exact automorphism group (ut = Aut(g) for almost all simple graphs for large enough (Babai et al., 1980), and thus in practice the compression rate of incomplete shuffle coding with color refinement is usually optimal or near-optimal.
When used for incomplete joint shuffle coding, color refinement yields string of vertex 'colors' that assigns a graph to a specific incomplete ordered graph I-c.- Since these vertex colors form a string, we can apply complete joint shuffle coding which is fast for multisets, to approximately canonize graphs and code string cosets. As shown in Appendix B.3, for fixed number of convolutions k the resulting, much improved overall runtime complexity is
O(m + n nlogn).
(5)
where m denotes the number of edges in the graph.
4 Autoregressive shuffle coding
(a.bb.cc.
pin
pop 1
fa,c. cJb
fa,c.cH..
Ca,cBc
[aacc]..
fcBa....
H.
(a)
(b)
Figure 1: Iterations for autoregressive shuffle coding during encoding of (a) a multiset and (b) an unlabeled undirected graph. Dotted placeholders indicate deleted information. Decoding an orbit allows to 'pin' an element in the last position. The pinned element is subsequently 'popped" from the object and encoded, and the process is repeated recursively on the remaining unordered prefix.
Joint shuffle coding, both complete and incomplete, incurs prohibitive initial bit cost in one-shot scenarios where only a single unordered object needs to be compressed. This is because it constructs an encoder by decoding all order information from the message (the bits-back step) before the ordered object is encoded with a given 'ordered' codec optimal for P(f). Therefore, other information has to be encoded into the message m before unordered object. At the very beginning of encoding, these 'initial bits' can be generated at random, but they are unavoidably encoded into the message. While for sequences of such objects, this constant initialization overhead is amortized and the rate tends to the optimal rate with more objects being compressed, it means that joint shuffle coding realizes no discount when coding single unordered object, rendering it useless in the one-shot case.
Specifically, joint shuffle coding realizes the discount from Equation (3) the net rate completely (or incompletely if using the variant from Section 3), but none of it in the (one-shot) rate. We now
5

---

aim to realize most of the discount in the rate by progressively decoding the permutation while autoregressively encoding the object. Severo al. (2023a) implement this idea for the special case of multisets, as visualized in Figure (a)). However, it exploits the simple structure of a string's s automorphism group and does not extend to other unordered objects such as graphs. In this section, Table 3: Examples of key concepts from Section 4 for the permutable class F. of ASCII strings of length 5 and the prefixing chain given by Example 4.1. {(..} denotes a multiset, and E indicates an arbitrary ASCII character. We visualize the same concepts for graphs in Table 4 in Appendix D.
we will generalize this codec to arbitrary unordered objects, including graphs, as shown in Figure ((b).
Concept
Example
Unordered derivative
sense' s e, n, sIe (ensse, esnse, .snee) F
Unordered i-th derivative
sense [s, esse = {sense, esnse) E ((3)
Prefix
(e sen (senaa, senab, ..... senba, senbb,... F(3)
Slice
sense2 = s e represeened by in context of ((ss eB 1.
Pop
pop(sen..L.) [ (ns.e)n....))
Push
push H. H.,, {(s. e|n (...)) seni...i
Orbit of index i
Orb (seenee) (1) [1,4]
Orbits
Orbs ArbsAnt (snnee) = {{0,3) 3), (1.4), (2)}
Orbit function
(rbits(sense)) (2,0,1,200) implies orbits(eenss) = (0, 2,
4.1 Prefixes of ordered objects
A general notion of 'pinning' objects such graphs, as visualized in Figure 1, can be formalized by disallowing any permutations involving the last position, exploiting Equation (1):
Definition 4.1 (Derivative). For a permutable class F = (F,,) of order n > 0. the pair of and ' S:Sn1 F F with s. == s- forms permutable class of order n 1, which refer as the derivative of F, denoted as F². We say that the unordered object this class containing f is the unordered derivative of f. denoted as f'. By applying the derivative i E [r] times, we obtain permutable class of order - i, which we refer to as the i-th derivative of F, denoted as F((), We define the unordered i-th derivative of f in the same way, denoted as f())
The derivative J has the same elements as F, but its unordered objects I' are different: seen' ((s, e, e n) (seen, esen, eesn] * seen. While the derivative F' pins the last position, the i-th derivative (+) pins the last i positions.
Length i string prefixes are ordered objects of order which we formalize as follows:
Example 4.1 (String prefixes). For E [n + 1] and set of elements X, let ~| be the equivalence relation on strings X with f ~"1 exactly if the first elements of and are equal for f.g E X We denote the equivalence class of f E X under ~M as f(J) and refer of length i. While ~| is not a congruence on X", is on the (n - i)-th derivative (X=)(n-(), and (Xx))(=1)) /~{ therefore forms quotient class.
(string) prefix of
While string naturally has 'prefixes' and 'elements' it is not obvious what the equivalent notions should be for graphs, and more generally, ordered objects. The conditions our method requires are captured in the following generalized definition of prefixes, for which Example 4.1 is special case. Importantly, the notion of a 'slice" will be used in place of 'string element', as visualized in Table 3: Definition 4.2 (Prefixes of ordered objects). For a permutable class F of order n and all i E [n + 1), let ryja] be congruence on F(--i), We then refer to the tuple of quotient classes Fig == F( |~ as a prefixing chain on F if the equivalence class of f E F under ~Ij referred as prefix of f of
length i and denoted as flg. and f. U Uk+411 referred to the slice of f at index fulfiil
fin] {f).
(6)

---

meaning that an object of order is uniquely determined by its prefix of length n, and
[[+11] F14 n,r
(7)
meaning that a prefix of length + is uniquely determined by the prefix of length and the slice at index i. The latter condition ensures the existence of invertible function pop Fi++1|
{(faj: f F}} with pop(f(+11) = (f(a). ft). We will denote its inverse as push.
For strings, the slice Si uniquely determines the element at index In practice, we can represent a string slice fi simply as the string element at index i since we only ever use it in context of prefix fi-- This definition of prefixes general enough to apply graphs, as visualized in Table 4:
Example 4.2 (Graph prefixes), For E {0,.... n). let M be the relation on simple graphs 9n with [[]] 9 exactly if f and g are equal up to the edges between the last
vertices for f.g E Gn. The quotient classes G -/--0/~~p J~H then form prefixing chain. Graph prefixes fıx can then be represented as graphs without any edges between the last n - vertices. Because graph slice fi for i E [r|] is only ever used in context of prefix f[j] we represent it as the subset of edges from { + 1), (i, 2)..... (i, }}} in practice.
Given a prefixing chain and an exchangeable probability distribution P over F, the optimal rate for an unordered prefix f(j is
log
log P(g(-1))
log P 1 9K-11)
log (r)
(8)
P(f()
Slice rate
Orbit discount
where 9[]] (j,i ( 1) flg for any j E [i]. For proof see Appendix B.2.
4.2
Achieving the target rate
The recursive structure in Equation (8) hints at how to construct a recursive codec for unordered
prefixes optimal for P(fEe) ). To obtain g[u) we require a function swap(f(a, j. k) == (j. k) fig that
swaps two positions of prefix flg.- To realize the slice rate term from Equation (8). we require
an (autoregressive) codec for slices fa parameterized by Di that is optimal for P(ʃs 914)). denoted as Slice. For simplicity, we assume that there is only a single unique 'empty" prefix of length 0, denoted as fo below, as is the case for Examples 4. I and 4.2. We will realize the orbit discount by recovering the bits for the orbit of j in Aut(f(t). For that, we need a way to identify the orbits of any f E F in way that is invariant under permutations, formalized through the following definition:
Definition 4.3 (Orbit function). For a permutable class F of order n, let < be total order on the orbits
Orbs Aur(f) = {Orb (i) i E [n]] of all indices i E [n]. This induces a unique function I O - [[]] with I()) S [(o') exactly if S o' for all o, of E O. We then refer to the function orbits(s)) (((Orbsau(r)(i)) jE[n]
for all E F orbits(s D.. orbits(/), for all E S,, f e F and j E [n]]
orbit function of F if
An orbit function for string prefixes ranks its elements according to some order over the alphabet, as visualized in Table 3. For graph prefixes fig. we can implement an orbit function by distinctly coloring the last n vertices of the graph f. deleting the edges between them, and passing nauty and Traces library (McKay and Piperno, 2014), which provides an orbit function for graphs.
the
We require orbit function orbits; on prefixes Fij of all lengths i E [n). This defines corre- sponding probability distribution over orbit indices [|Orbs ll with mass function P. s.t. for all i [n] and j e [i]. P. (orbits,
(Orb (i)l// We construct codec Orbit optimal for P. by using categorical codec with masses proportional the counts of each orbit index orbits((J1s).
We list the autoregressive codec UnorderedPrefix parameterized by the prefix length i:
7

---

def emcode f):
Effect on message length:
2
if i=0: return
os = orbits(f)
m, Orbit decode
log [Orb (
5
fond(o, o5)
swap(f, j, 1-1)
7
g1, s pg)(g)
Slice(g1) encode s)
+ log P(o: g(-1))
UnorderedPrefixx(ii) (mcode g!)
+ log r(g(--))
return
11
def d if i=0: return m, fo
13
m, gl = UnorderedPrefiix(i11 .de..de (m)
15
m, s Slice(g1) (m)
pgsh s)
os orbits(g)
os[i-1]
Orbit(os) encode o)
return m, g
Similarly to joint shuffle coding, we represent an unordered prefix Fig by an arbitrary (ordered) prefix
fi f(j) denoted as in the listing. In the encoder, we decode an orbit index o from the message according to P.. and let an arbitrary index within the corresponding orbit. We express this with function find(o, os) which returns the first index of a given element in a given tuple. Equation (6) ensures that we can represent ordered objects F as their prefixes Jim] = { of length n. This allows us to recursively code unordered objects with UnorderedPrefix(n optimal for P(f), method which will refer to autoregressive shuffle coding.
4.3 Achieving practical speeds
naive implementation of autoregressive shuffle coding as shown the listing above is impractically slow on larger objects: for every prefix length E [n). the prefix orbits and the corresponding orbit codec (as well the slice codec), need to be recomputed. In the case of graphs, finding the exact orbits for even one such graph prefix is slow, just like finding the automorphism group of a graph for complete joint shuffle coding. This subsection presents three techniques critical to achieving practical speeds with autoregressive shufile coding.
Adaptive entropy coding, Instead of independently computing new Slice and Orbit codec for each iteration using orbits, as shown in the code listing for simplicity, we allow reuse between iterations by updating their state during push. pop and swap. This allows to implement 'adaptive entropy coding', used by Severo et al. (2023a) in the context of Orbit for multisets X", which achieves fast updates of mutable categorical codec based on order statistic tree that is weighted in the sense that allows each element to be present some k E N times, We will reuse the same approach to efficiently implement autoregressive Slice codecs, where for multisets we use custom weighted AVL tree (Adelson- Andelson-Velskii, 1962).
Incomplete autoregressive shufile coding, Instead of computing the orbit function on prefixes fij] we can apply to some incompletely ordered version (f(a) instead, as defined in Definition 3.1. Similarly Equation (4), this reduces the realized discount from Equation (8), increasing the rate by
log [Orbant(((n))(())
bits in each recursive step. We refer to this variant incomplete autoregressive shuffle coding. We can apply color refinement to graph prefixes by distinctly coloring the last n vertices the graph f. deleting the edges between them, and then applying it to graphs as usual (discarding the last i vertex hashes). Applying incomplete autoregressive shuffle coding with color refinement by using the graph prefixing chain from Example 4.2 greatly improves runtime complexity compared to the

---

complete version. However, it still results in runtime of at least (2(ne) that is impractical for larger graphs. since color refinement has to be run for every prefix fij) E [n] times. Thus, it would be helpful to reduce the number of required color refinement runs to reduce runtime further, motivating the next technique.
Chunking. Instead of encoding order information after every slice, we can decode slices in a small fixed number с of chunks, with sequence C' of sizes adding up to n. For graphs, we can apply color refinement to the graph prefix after decoding the next chunk, and iteratively code the new order information according to the resulting vector of vertex colors. We then repeat this process until the complete graph is decoded. In Appendix E we formalize this generalized approach as (incomplete) autoregressive shuffle coding with 'chunked' prefixing chain, where prefixes code more slices than usual to complete the respective chunk. For graphs, we then require only a color refinement runs (instead of n for the 'full' prefixing chain), resulting in practical runtime of
Occ- m + n logn)
(10)
Coarser chunks generally lead to better runtimes but also higher initial bits overhead. The extreme case of using only a single chunk of size leads to a method sharing many properties with joint shuffle coding. Chunking allows using a Fenwick tree (Ryabko, 1989) for adaptive entropy coding since all possible values for vertex hashes in a chunk are known in advance, leading to better memory layout and faster runtimes. For a detailed discussion, see Appendix E.
5 Related work
Complete joint shuffle coding. Unlike joint shuffle coding introduced in Kunze al. (2024), autoregressive shuffle coding allows one-shot compression of unordered objects. This is achieved by interleaving encoding and decoding steps while coding a single object, an approach first proposed in the context of 'Bit-Swap' (Kingma et al., 2019). Our method requires an autoregressive model for slices instead of a joint model. Unlike complete shuffle coding, incomplete shuffle coding does not require the automorphism group of an object and therefore does not depend on libraries such as nauty and Traces (McKay and Piperno, 2014).
Graphs. Choi and Szpankowski (2012) present a compression method called 'structural ZIP" (SZIP), which asymptotically achieves the rate
log PER(g)
n log n + Onn).
(11)
where PEn is the Erdōs- G(n,p) model. Compared to our method, SZIP is less flexible in the sense that it only applies to simple graphs (without vertex or edge attributes), and it is not an entropy coding method, thus the model PER cannot be changed easily. The 'Partition and Code' (PnC; Bouritsas et al., 2021) method uses neural networks to compress unordered graphs. Unlike PnC, we achieve state-of-the-arr compression rates when using simple models with minimal parameters, which amortize better when compressed along with a single graph.
Multisets. Our method generalizes Severo et al. (2023a) from multisets to arbitrary unordered objects, including graphs.
Experiments
To demonstrate our methods experimentally, we applied them to multisets and graphs. We report multiset compression results in Appendix G where compare implementation of full autore- gressive shuffle coding to Severo et al. (2023a) on multisets of varying lengths, showing that while (one-shot) rates are matched, our implementation is well over two orders of magnitude faster and scaling to large multisets. Further multiset experiments show that joint shuffle coding is even faster while achieving the same net rates.
For graphs we applied incomplete joint and autoregressive shuffle coding with color refinement according to Definition C.I to various graph datasets. We use the simple Rédōs-Rénní (ER) G(n,p) model for P, which straightforward to convert into an autoregressive model P(f f(j)) Kunze et al. (2024) observe that the Pólya urn (PU) preferential attachment model proposed by Severo

---

et al. (2023b) drastically improves the compression rate on SZIP graphs from Choi and Szpankowski (2012). Motivated by this, we also use a variational approximation to obtain a tractable autoregressive model that we refer to autoregressive Pólya um (AP), described in Appendix F. We favored AP for larger graphs over PU because AP scaled better terms of runtime, with similar rates.
Joint. We report results for incomplete joint shuffle coding on graphs in Appendix H. We first apply SZIP graphs with varying and report how this affects compression rate in Figure to find a practical number of convolutions k. The results show that k = 3 is sufficient to get close to the optimal rate, which we therefore use for all other graph experiments in this paper. In Tables and 9, we compare complete and incomplete joint shuffle coding on the TU (Morris et al., 2020) and SZIP datasets.* 4 We observe that incomplete shuffle coding leads to dramatic speedups of up to a factor of one million on some of these graphs, with minimal increase in compression rate across all datasets. We also evaluate incomplete joint shuffle coding using the AP codec on the large graphs used by Severo et al. (2023b) in Table 10, which we refer to as the 'REC' graph dataset, where complete joint shuffle coding is too slow to finish on any graphs. the same table, we report compression speeds when run on single thread and 8 threads, both on the SZIP and REC graphs, confirming an advantage with multiple threads.
Autoregressive. For incomplete autoregressive graph shuffle coding, we apply chunking to the prefixing chain from Example 4.2. We first evaluate the effect of chunk size in Appendix on SZIP graphs, and find that e = 16 uniformly sized chunks lead to a good balance between runtime and rate, which we will use in all following experiments.
We apply incomplete autoregressive shuffle coding to the SZIP graphs based on ER and AP, and compare it to the SZIP method in Table 11. The results show that the advantage of preferential attachment model over Kéndi- carries over from the joint PU codec to the autoregressive approximation AP, demonstrating the value of shuffle coding being an entropy coder where the model can be changed easily. This results in significantly better rates compared to SZIP, at practical compression speeds that appear be largely independent of graph size, whereas speeds for the SZIP codec seem to drop with graph size (SZIP graph sizes are shown in Table 10).
We evaluate autoregressive shuffle coding on REC graphs in Table 12, and compare it to the ordered rate without shuffle coding, demonstrating its practicality and rate advantage on large graphs. These results also confirm that the discount unrealized due initial bits, visible as the difference between net rate and rate, is relatively small, highlighting the effectiveness of autoregressive shuffle coding for one-shot compression.
Finally, we evaluate autoregressive shuffle coding with the AP model on very large plain random graphs drawn from G(n, m) Erdds-RRény models and report rates and speeds in Table 13. The largest graph has one billion edges and an uncompressed size 3.4 gigabytes, with our compression method saving 0.8 gigabytes. The speed results confirm the hear-linear runtime predicted by Equation (10) across many orders of magnitude.
7 Conclusion
We proposed general entropy coding method for unordered objects, achieving ofate-of-the-art compression rates at practical speeds for multisets and graphs up to gigabyte-scale. it a combination of two new shuffle coding variants, as summarized in Table 5.
We believe that there is significant room for optimization. On REC graphs, we observed that roughly half of the runtime is spent on the ordered autoregressive model which has not yet been optimized. Chunking invites parallelization, for example with vectorized ANS (Giesen, 2014). Non- uniform chunk sizes C' are likely also beneficial for graphs, already demonstrated for multisets in Appendix G. Unlike competing methods like SZIP and PnC, shuffle coding is an entropy method that can be easily adapted to specific domain models, and benefits from advances in generative graph modeling, such as recent work on neural (autoregressive) graph models (Kong et al., 2023; Zhu et al., 2022). We leave these promising research directions for future work.
*The TU dataset features vertex and edge attributes. Here, maximum- maximum-iikelihood parameters for categorical attribute distributions are inferred for and coded along with each dataset, as described in Kunze et al. (2024).
10

---

References
Adelson-Velsee Georgii M (1962), An algorithm for the organization of information. In Soviet Math.
3, pp. 1259-1263. Babai, László (2016). Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eight annual ACM symposium Theory of Computing, pp. 697.
Babai, László (2019). Canonical form for graphs in quasipolynomial time: preliminary report. In
Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing. STOC 2019. Phoenix, A7. USA: Association for Computing Machinery, pp. 1237-1246. ISBN: 9781450367059.
DOI: 10. 1145/ 0//5/33122 331 331 6356. URL: https: http://ooiooro.oo org/10. 1144/331322 3316356.
Babai, László, Erdos, Paul, and Selkow, Stanley M (1980). Random graph isomorphism. In SlaM Journal on computing 9.3, pp. 628-635.
Babai, László and Kučera, Ludëk (1979). Canonical labelling of graphs in linear average time. In
20th Annual Symposium on Foundations of Computer Science (SFCS 1979). IEEE, pp. 39-46.
Bouritsas, Giorgos, Loukas, Andreas, Karalias, Nikolaos, and Bronstein, Michael (2021). Partition and Code: Learning How Compress Graphs. In Advances in Neural Information Processing Systems. Vol. 34, pp. 18603-18619.
Choi, Yongwook and Szpankowski, Wojciech (2012). Compression of Graphical Structures: Funda- mental Limits, Algorithms, and Experiments. In IEEE Transactions on Information Theory 58.2,
pp. 620-638.
Duda, Jarek (2009). Asymmetric Numeral Systems. arXiv: 0902. 0271 [cs, math].
Giesen, Fabian (2014). Interleaved entropy coders. In arXiv preprint arXiv:1402.3332.
Helfgott, Harald Andrés, Bajpai, Jitendra, and Dona, Daniele (2017). Graph isomorphisms in quasi- polynomial time. In arXiv preprint arXiv: 170.04557
Huang, Ningyuan Teresa and Villar, Soledad (2021). A Short Tutorial on The Weisfeiler-Lehman
Test And Its Variants. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).
Kingma, Friso, Abbeel, Pieter, and Ho, Jonathan (2019). Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables. In Proceedings of the 36th International Conference on Machine Learning, pp. 3408-348444 -417.
Kong, Lingkai, Cui, Jiaming, Sun, Haotian, Zhuang, Yuchen, Prakash, B Aditya, and Zhang, Chao (2023). Autoregressive diffusion model for graph generation. In International conference on machine learning. PMLR, pp. 17391-17408.
Kunze. Julius, Severo, Daniel, Zani, Giulio, van de Meent, Jan- Willeeleem, and Townsend, James (2024). Entropy Coding of Unordered Data Structures. In International Conference on Learning Representations (ICLR).
Leman, Andrey Aleksandrovich and Weisfeiler, Boris (1968). A reduction of a graph to canonical form and an algebra arising during this reduction. Nauchno--Techniiceskkayy Informatsiya 2.9,
pp. 12-16.
McKay, Brendan D. and Piperno, Adolfo (2014). Practical Graph Isomorphism, II. Journal of
Symbolic Computation 60, pp. 94-112.
Morris, Christopher, Kriege, Nils M., Bause, Franka, Kersting, Kristian, Mutzel, Petra, and Neumann, Marion (2020). TUDataset: A Collection of Benchmark Datasets for Learning with Graphs. In ICML 2020 Workshop on Graph Representation Learning and beyond (GRL+ 2020). arXiv: 2007 08663.
Ryabko, Boris Yakovlevich (1989). fast on-line code. In Doklady Akademii Nauk. Vol. 306. 3. Russian Academy of Sciences, pp. 548-552.
Severo, Daniel, Townsend, James, Khisti, Ashish, Makhzani, Alireza, and Ullrich, Karen (2023a). Compressing Multisets with Large Alphabets. In IEEE Journal Selected Areas in Information Theory.
Severo, Daniel, Townsend, James, Khisti, Ashish J., and Makhzani, Alireza (2023b). Random Edge Coding: She-Shot Back Coding of Large Labeled Graphs. In Proceedings of the 40th International Conference Machine Learning.

---

Townsend, James (2020). A Tutorial on the Range Variant of Asymmetric Numeral Systems. arXiv: 2001.09186 [cs, math, stat].
Townsend, James, Bird, Thomas, and Barber, David (2019). Practical Lossless Compression with Latent Variables Using Bits Back Coding. In International Conference on Learning Representations (ICLR).
Zhu, Yanqiao, Du, Yuanqi, Wang. Yinkai, Xu, Yichen, Zhang, Jieyu, Liu, Qiang, and Wu, Shu (2022). A Survey on Deep Graph Generation: Methods and Applications. In Proceedings of the First Learning on Graphs Conference, 47:1-47:21.
12

---

A Group actions, orbits and stabilizers
This appendix gives the definitions of group actions, orbits and stabilizers well statement and proof of the orbit-stabilizer theorem, which we make use of in Section 4. We use the shorthand H < G mean that I is subgroup of G, and for g E G. we use the usual notation, gll [gh h E H1 and fg = { h E } for left and right cosets, respectively. For any two subgroups G, H S S, we denote the group of their intersection as G E H.
Definition A.1 (Group action). For a set X and group G, group action, or simply action, is binary operator
"G G X -
(12)
which respects the structure of G in the following sense:
1. The identity element e E G is neutral, that is e G G
2. The operator "G respects composition. That is, for g. h E G,
9 G (h x) = (gh) z.
(13)
We will often drop the subscript G and use infix alone where the action is clear from the context. Definition A.2 (Orbit). An action of group G on a set X induces an equivalence relation ~g on X, defined by
I G~ y if and only if there exists g GEG such that y = 9 x.
(14)
We refer to the equivalence classes induced by <G as orbits, and use (rba(a)) to denote the orbit containing an element x E X. We use X/G to denote the set of orbits, so for each x X, (r) X/G.
Definition A.3 (Stabilizer subgroup). For an action of group G on a set X, for each a E X, the stabilizer
(taba = {g E G 1-
(15)
forms subgroup of G.
Here, we give a statement and brief proof of the well-known orbit-stabilizer theorem.
Theorem A.4 (Orbit-stabilizer theorem). For action of fonite group G on set X, for each x E X, the function 0g: + X defined by
(g(g) == x
(16)
induces bijection from the left cosets of Stabo(x)) to Orba(x). This implies that the orbit Orba(z) finite and
GG
[Orba(z)]
(17)
[St)
Proof. We show that 0f induces a well defined function on the left-cosets of Staba(r), which we call 0 Specifically, we define
( Stabo(x)) = xx,
(18)
and show that fy is injective and surjective.
To see that oy is well defined and injective, note that h E g Stabo(z)
th -
Stabo(I)
(19)
g h = x
(20)
g. ===l: h.
(21)
using the definition of Stabe. For surjectivity, have
y E Orba(x)
= 3y E G.l. y = g. , (g Stabe(x))
(22)
(23)
using the definition of Orbg.
13

---

B Proofs
B.1
Background (Section 2)
Proof for Definition 2.2. We first prove f~ E F~ for all S, and f~ Fu.. Let E Sn and f.g E F. Now s f~ s 9- exactly if ~ because is exchangeable, and the inverse permutation s E S, of exists. Since F~ is a partition of FF, this implies {s fife f-] E F. and therefore s fw E Fr. It is left to show that the operator : Sn x F~ + F~ is a left group action. This follows from Sn F associated with the permutable class F being left group action.
B.2 Autoregressive shuffle coding (Section 4)
Definition B.1 (Exchangeable function). We say a function on a permutable class F exchangeable if a(f) a(g) for all f.g E F with f =.
Lemma B.2. If + P(J) on F is exchangeable then the functions fT - P(f()) on Fig for i E [n + 1] are exchangeable.
+ 1] and 8 E S,, Equation (2) implies P(s f(a) EyEta P(s f) EyEtu P(f) P(ff)) and therefore f - P(f(a) on Flj is exchangeable.
Proof. If ʃ + P()) is exchangeable, then for any i In+
Lemma B.3. If P(f) on F is exchangeable, then for i [n], Fia, the function fla P(g. f(a) on Fig is exchangeable, and P(g. fie) = P(g. f(a) fia) for flg E flc.
Proof. Assume P(f) is exchangeable. We will use induction over starting at down to 0, for the statement that f(i] + P((9)) jem]// ((a) is exchangeable for any given Jj. and implies the lemma. P((gs) [(a) = P(O (ra)) is exchangeable, covering the base case. Assume for i [n] that f[+1] P((g)) je([)(++))) ((t+) is exchangeable. For all E [n] and f E F,, we have P(f) = P(f P()))((s)) (EMM/NM))) [[tta]) Therefore, the function mapping from f F is also exchangeable due to Lemma B.2 and the inductive assumption. This further implies that the function mapping from f(g Fij P((g)))e(m)) (1x) induction.
to P(f: f(a) P(f()) (( se(e]N(411) (f(++)))
[fpi)) f(a) is exchangeable, completing the
Lemma B.4. For prefixing chain given by Fij StabAme(fera) (1) = Aut(f(a) for all i E [n 1,,E
{s S s s iisiin f ([+1] f), which is {8 Si I s- ([+1] f} due Equation (1) and = {s S s ~y f A U(s Dien -f(u+1) through Equation (7). Since (s (0 isomorphic to I in Flt41j this is in uurn {s E S f mM f} Aut(fra)
Proof. We have Stab
Proof of Equation (8). The optimal rate is given by Equation (3):
1
log
log P(faa)
log
(24)
P(fa)
Aut
Orderedd rate
Discoutt
The optimal rate for 9[--1] is given by Equation (24):
1
1
(i 1)!
log
log
log Aut(g
(25)
P(g
P(g
Ordered
Discount
14

---

It is informative to rewrite Equation (24) in terms of Equation (25):
1
log 1
+ log P(g
log
P((())
P( P(5N))
(26)
|Aut(g]--)]
log AAut(Jia)]
Definition 4.2 and Lemma B.3 imply P(f(a) P((s f).) = P(gn) ((91-199/1-1 P(
Additionally, have Aut(fia) = Aut (s fr1) Aut(g))) since permuting f results in conjugated automorphism group which is isomorphic to Aut(f(q). Lemma B.4 together with the orbit- stabilizer theorem A.4 implies [gat( = (Orb - 1)1 [Aut(g; Finally, we have
[Orb (gt) (i 1)1 (OrbAw((fa) (i)). We can now rewrite Equation (26) into Equation (8). L
Lemma B.5. UnorderedPrefix forms valid codec, with encode and decode being inverses of each other.
Proof. This mostly straightforward, but notably, the swap operation of the encoder is reversed. Here, we exploited that output of the function /4-1j + orbits; (obiss:(push(ip (push(Ai-_1), ())-)))-1 on Fit+1] does not change when permuting the input, and therefore the decoder recovers the correct orbit index (g)):- orbits; (fa)) for any decoded hj=11 E 9[--1]-
B.3 Incomplete shuffle coding (Section 3)
Proof for Equation (4). The condition in Definition 3.1 is equivalent to f = g for all f.g F with g. We show f U by proving that for g~ F/",, we have g~ E fn exactly if g~ S g~ E f~ means 3s Sn 9~ = 8 f~, which is equivalent to E Sn : n ~-8 8 8.
f. On the other
hand, 9- S. holds exactly if g- C [I J~ E S,). meaning that 31 E Sn : L ʃ. It is left to show that 3s E Sn with = t. To show the implication assume 3s Sn 1g-ggs s-f. Definition 3.1 now implies Es E S₁, 9 < s f. and therefore Es, E Sn = u f. u. implies 3 E S, = f. completing the proof.
8 exactly if 31 E Sn :g =L-f. The implication <= proved
This leads to P(J) P(f~) for any given distribution P(J) over F, and Equation (4) follows from applying Equation (3) on both sides.
Proof for Equation (5). To achieve this runtime, implicitly assumed that ordered graph model fast enough. We can hash multiset represented as a string in linear time by accumulating hashes using bitwise 'xor' operation, which is associative and commutative, making the overall hash permutation- inauutation-iivaiiant. This results in an overall runtime of O(Σ [n:(g)) = O(m). The
remaining computation has the runtime O(n log n) of joint shuffle coding on multisets, leading to the given overall runtime complexity.
L
15

---

C Color refinement details
We here state the formal definition of color refinement, described in Section 3, that we use for the paper:
Definition C.1. For an (ordered) simple graph E In. let na(g) denote the set of indices of the neighbors of the vertex at index i. Let the coloring of a graph 9n with N iterations be the tuple C& with Co(g) = (Ina()))iess) and
C (g) (L j E n.(g))))
(27)
for a 'hashing' function h M + N multisets M U of up to natural numbers N. We then obtain congruence corresponding to (f) = (g) and Gn/~o, forms class of incompletely ordered objects for l: E N.
Color refinement is often run to convergence of vertex partitions (Huang and Villar, 2021). This happens after at most [n] iterations and is therefore equivalent to Cn. can be naturally extended to graphs with vertex and edge attributes, by hashing each vertex attribute together with the multiset of neighboring edge attributes in the initial Co. and then convolving multisets of pairs neighboring edges attributes and hashes in subsequent iterations. The corresponding Weisfeiler Leman graph iso- morphism test is based on the fact that C&(f) & (x(g) implies b g and successfully distinguishes almost all pairs of non-isomorphic graphs (Babai and Kučera, 1979).
Similarly, color refinement with k 0 convolutions finds the exact automorphism group Aut(g=o.) = Aut(g) for almost all simple graphs for large enough n.
Proof. Babai al. (1980) show that with probability of at least r there is set U of vertices whose degrees are distinct U, and no other vertices have the same set of neighbors within U. Since color refinement starts with the vertex degrees, single convolution will assign pairwise distinct hashes for almost all graphs.
We assumed here that no hash collisions occur (h(a) h(b) with a * b). for simplicity. practice, we use an off-the-shelf 64-bit hash function h, where hash collisions are extremely improbable. Even such collision occurs, it results only marginal increase.
16

---

D Conceptual visualizations
We visualize key concept for autoregressive shuffle coding for the example of graphs in Table and summarize the variants of shuffle coding proposed in Table 5.
Table 4:
Examples of key concepts from Section 4 for the permutable class F of simple graphs with vertices and the prefixing chain given by Example 4.2. Dotted edges indicate deleted information.
Concept
Example
Unordered derivative
E
3
0
Unordered
i-th derivative
2
E
F(3)
3
3
3
0
Prefix
2
2
E
F121
3
3
3
33
2
Slice
2
2
represented by
in context of
3
Pop
pop
2
Push
push
2
3
Orbit of
Orb
(1) (1,3)
index i
Aut
Orbits
Orbs
(10). (1,3)
Orbit function
orbits
2
(2, 0, 1, 1) implics orbits
2
(0, 0, 1,
3
3
17

---

Table 5: Comparison between variants of shuffle coding.
Not One-Shot & Allows Any Model
One-Shot & Requires Autoregressive Model
Shuffle Coding Variant
Optimal Rate & Requires Automorphism Group
Complete Joint (Kunze et al., 2024)
Complete Autoregressive
Near-Optimal Rate
Incomplete Joint
Incomplete Autoregressive
Allows Approx. Automorphism Group
E
Chunking
no chunking ('full")
single chunk ('joint')
C
[1,1,
[2, 2, 1]
[5]
fij
ab
abacb
[[2]
ab
ab
abacb
f19]
aba
abac
abacb
f14
abac
abac
abacb
f15t
abacb
abacb abacb
Table 6: Prefixes for the string f = abacb according to chunked prefixing chains of Example 4. for various chunk size sequences C. When used with autoregressive shuffle coding, the prefix f(a) resembles the information decoded after iterations during decoding.
Autoregressive shuffle coding with chunking, described in Section 4.3 refers autoregressive shuffle coding using the following 'chunked' prefixing chain:
Definition E.1 (Chunked prefixing chain). Let (Fin)seja be a prefixing chain on with Fig) == f(~-0//,, and let C = (cy) be a sequence of e chunk sizes with Eje(d Cj = In this context, we refer Pj == Exe(++1) Ct the prefix size for chunk , [c], and C(i) = min E [c]la E [py]} as chunk for index E [n]. Another prefixing chain is now formed on F by (F(n-1) /rpoc) )sefm) which we refer to as the chunked prefixing chain of (Fi) )ae()) with chunk sizes C.
Then, the slice the first position of a chunk codes complete chunk from the original prefixing chain, and all its remaining slices have no additional information about the object. To apply incomplete autoregressive shuffle coding according to some incompletely ordered prefixes (fra)~ E Fia/r, formally, we will require a prefixing chain to be defined for each Fig/~. Then, we code orbits of chunked prefixes of length according Aut((USpea (()))) This means that approximate the orbit based on the full chunked prefix, and then use prefix of that approximation of length i.
E.1 Runtime
For graphs, we will use color refinement to map to incompletely ordered prefixes (f14)=e, and use the string prefixes according to Example 4.1 of the resulting hashes within given chunk. This choice requires color refinement runs (instead of one as in Equation (5)), and additionally has the runtime complexity of (full) autoregressive shuffle coding on strings O(n log n), resulting in the overall runtime Occ- m + n log n) stated in Equation (10), which achieves the goal of a practical runtime for a fixed number of chunks c. A Although not affecting runtime complexity, we can also switch adaptive entropy coding to a Fenwick tree to achieve better memory layout and therefore runtime, as described in Section 4.3, since all possible vertex colors within a chunk are known immediately after color refinement.
18

---

E.2 Choosing chunk sizes
Larger chunks soften the restriction for our ordered model to be autoregressive but increase the (one-shot) compression rate due to more required initial bits, For chunking graphs as discussed above, larger chunks additionally can expect a speedup due to fewer rehashings with color refinement, and slightly worse net rate, since chunk borders soften the restriction of the automorphism group to be factored.
The degenerate case of c = n chunks is equivalent to not using chunking at all, a setting we refer as 'full' autoregressive shuflle coding, shown in the second column of Table 6. The last column shows the other extreme with only c = chunk, where autoregressive shuffle coding degenerates into method behaving very much like joint shuffle coding, in the sense that can employ a joint model, and the method is not suitable for one-shot coding since the complete discount would stay unrealized the rate due initial bits. We therefore refer this setting as 'joint' autoregressive shuffle coding. Joint shuffle coding still has reason to exist: It typically allows more batched and parallel coding of order information and accordingly, it can significantly faster, as we show in our experiments.
The unrealized discount in the rate due to initial bits influenced by the distribution the object's information among slices, visualized in Figure 2. With the usual prefixing chain from Example 4.1 for ii.d. multisets, information is distributed equally across slices, as pictured in Figure 2(a), and all but Oloo r.) of the On log discount should be realized in the rate. For simple graphs sampled from an Erdös-Rényí model and the prefixing chain from Example 4.2, each slice fi contains information about n 1 edges, so the expected slice rate drops linearly with i down last slice, as visualized in Figure 2(b). In effect, the last slices (that are encoded onto the stack first) have the least amount of information, canceling out fewer initial bits. For graphs, we can thus expect less of the discount realized in the rate.
for the
log P(fa)
E log P(f))
1 i
0
n
(a)
(b)
Figure 2: Expected slice information Elog P(fs) by slice index i for (a) i.i.d. strings using the prefixing chain from Example 4.1 and (b) simple Erdös-Rényi graphs using Example 4.2.
Assuming that all slices have the same rate, which is met in expectation for i..dd strings shown in Figure 2(a), that each coded orbit has the same rate (which only slightly inaccurate), and given that want to exactly chunks, the chunk sizes that minimize the rate have the following property: For each pair of neighboring chunks with sizes e; and G+11, the ratio of the two latter by the form size should be approximately equal to the relative discount, meaning the discount log Aut(f) of the object f per ordered net rate log P(J).
a! log Aut() log P(f)
C++1
~
(28)
leading geometric series of chunk sizes with the given base, with the first chunk being the largest. For simple Erdös-Rény graphs, as shown in Figure 2(b), the slice rate is not uniform, making it more difficult model the condition required for the minimal rate. For our experiments graphs, will simply choose (approximately) equally sized chunks, and leave optimizing relative chunk sizes for future work.
DDuiing encoding, this condition causes the ANS stack to be exactly emptied by the initial bits of the next chunk. It can be shown that this is optimal under the given assumptions.
19

---

Autoregressive Pólya urn model details
Kunze et al. (2024) use the Pólya urn (PU) preferential attachment model proposed by Severo et al. (2023b) to drastically improve compression rate on SZIP graphs with joint shuffle coding, Motivated by this, we use variational approximation to obtain tractable autoregressive model that we refer to as autoregressive Pólya um (AP). The task of predicting the next graph slice fs given the prefix f(j) can be broken down into two parts: Given the prefix fli), predict the number of edges kg E [n i] within the next slice ft. and then from that, predict the edge positions within the slice. For the Pólya ur (PU) model P(f). assuming the slice representation from Example 4.2, the distribution for the first part, (kk; ((g)) not tractable, and in order to obtain a tractable variational autoregressive model, we instead approximate it based on a Zipf distribution. Specifically, we use the Zipf distribution Q(k;) (k++))2 except for smaller graphs up 100000 edges (which includes all SZIP graphs), for which
Q(ka)) ke for k; and Qk;; second part, Pff k2). is tractable. The generative process for P(filft k2) is as following: Given the graph of the prefix fia and the number of edges K; in the next slice fú. iteratively insert K; edges, with probabilities proportional the neighbor count of the adjacent vertices 1i+1,i+2,... n-13 without allowing repetition (i.e. zeroing out the probabilities where edges were already inserted), Our overall autoregressive model is then given by Q(fi f(a) = Ex.= P(f f1z) (k) f(a)-
Q(k; = 3. The distribution of the
In general, is not important for autoregressive exactly match even approximate recognizable joint models. Instead, they can be designed or learned on their own. In our case, however, a joint model inspired reasonable autoregressive model through approximating the original with the derivation above.
20

---

G
Multiset compression results
All shuffle coding speeds in this paper were measured on MacBook Pro 2018 with a 2.7GHz Intel Core i7 CPU.
We compare our implementation of full autoregressive shuffle coding Severo et al. (2023a) multisets of varying lengths, sampled from an i.i.d, categorical distribution with probabilities sampled according Dirichlet distribution, described in Severo al. (2023a). We show compression rates in Table 7, and speeds in Figure 3. The results confirm that our implementation matches the rate of Severo al. (2023a), but is well We observe that the rate is within 64 bits of the optimal rate across all multiset sizes, likely mostly caused by the fixed overhead of ANS. This is consistent with our prediction from Appendix E.2 that the unrealized discount should be very small at (log nt).
orders of magnitude faster, and scales large multisets.
We also evaluate joint shuffle coding using the same data and i..dd model, well as 'joint' autoregres- sive shuffle coding (with a single chunk). While both result the same net rate as full autoregressive shuffle coding. joint shuffle coding leads to the fastest runtime over wide range of multiset sizes.
In Table 7, we also report the rates of autoregressive shuffle coding with 10 chunks using a geometric series of chunk sizes with varying choices for the base, compared to equally-sized chunks (base 1). The results confirm the prediction of Appendix E.2 that on multisets, a geometric series of (unequal) chunk sizes can lead to better rates over equally sized chunks. For experiments, our chunked autoregressive ordered model simply codes multiple slices per chunk using the underlying fully autoregressive model. On multisets, this results in autoregressive shufile coding with larger chunks having no benefits over the fully autoregressive variant, Improved speeds can expected for specialized chunked autoregressive models that parallelized, similar to joint shuffle coding. We leave this for future work.
joint
joint AR
R.
full AR
full AR (Severo et al.)
10.
Compression speed MBis
1.
0.01
10
100
1,000
10,000
100,000
1,000,000 000
10 08.000 000
Multiset size
Figure 3: Compression speeds (dotted lines) and decompression speeds (solid lines) of multisets of varying size using joint and autoregressive shuffle coding with chunk ('joint AR') and n chunks ('full AR'), compared to the full autoregressive implementation from Severo (2023a). All results are based on the (ordered) string rate as the reference uncompressed size averaged across 10 runs (100 runs for sizes <IM for our implementations).
21

---

Table 7: Compression rates in bits for one-shot compression of multisets with full autoregressive shuffle coding, compared to the implementation from Severo et al. (2023a), as well as the optimal (net) rate. We also show the effect rates when using 10 chunks with geometric series of sizes, with varying bases. The last but one column uses the relative discount from Equation (28) of each graph the base (shown in parentheses).
Full
10 Chunks (Geometric with given Base)
Size
Net
Ours
Severo
(unif.)
(log Aut(yy) ) log P(f)
93%
1k
1769
1833
1856
2707
2487
(18%)
2443
10k
8683
8744
8768
17598
15219
(49%)
14988
100k
68852
68912
68960
157690
131782
(82%)
131782
1M
663046
663104
1550754
1295534
(91%)
1295534
10M
6597373
6597432
15473751
12935710
(93%)
12935710
H
Joint graph shuffle coding results
We report experimental results for incomplete joint shuffle coding graphs in Figure 4 and Tables
to 10.
USAir97
YeastS
geom
Relative nat-unrealized discount
Erdos
5.%
homo
as
1.%
0.5%
0.1%
0.05%
Convolutions
Figure 4: Rate increase from Equation (4) relative to the (optimal) discount from Equation (3) for incomplete shuffle coding graphs, depending on the number of color refinement convolutions k for each SZIP graph. The results are independent of the employed ordered model.
22

---

Table 8: Incomplete joint shuffle coding with color refinement using 3 convolutions on the TUDatasets (Morris et al., 2020), compared to complete joint shuffle coding from Kunze et al. (2024), both using the Kédōs-Rénní (ER) model. Since complete joint shuffle coding is too slow for three of the 24 social network datasets, REDDIT-BINARY, REDDIT-MULTIS evaluated separately the category 'Reddit'. Compression rates are measured bits per edge, and encoding and decoding speeds are for single thread, in kB/s.
SEDDIT-MULT1-12K they were
Speed
Thread)
Rate
Complete
Incompl.
Graph type
Compl.
Incompl.
Increase
Enc.
Dec.
Enc.
Dec.
Small molecules
1.14
1.19
4.0%
54
56
167
179
Bioinformatics
6.50
6.51
0.1%
51
66
426
421
Computer vision
4.49
4.56
1.5%
25
28
163
162
Social networks
2.97
2.97
0.3%
0.44
0.47
215
284
Synthetic Reddit
2.99
2.99
0.1%
98
110
317
323
5.38
129
123
Table 9: Incomplete joint shuffle coding with color refinement using 3 convolutions on the SZIP dataset, compared to complete joint shuffle coding from Kunze al. (2024), both using the autore- gressive Pólya urn (AP) model. We report the net compression rate, that is the additional cost of compressing that graph assuming there is already some compressed data append to. measured in bits per edge, as well as compression and decompression speeds on 8 threads in kB/s. All results are means across multiple runs, 3 for complete, and 100 for incomplete shuffle coding.
Speed (8 Threads)
Net rate
Complete
Incompl.
SZIP graph
Compl.
Incompl.
Incr.
Enc.
Dec.
Enc.
Dec.
Airports (USAir97)
3.12
3.13
0.2%
98
111
1025
1151
Protein (YeastS)
5.89
5.91
0.2%
2.834
2.852
1636
1697
Collaboration (geom)
4.57
4.84
7.1%
0,004
0.004
2289
2372
Collaboration (Erdos)
4.45
4.45
0.2%
0.024
0.023
1951
1979
Genetic (homo)
6.95
6.98
0.5%
0.249
0.261
2238
2358
Internet (as)
4.52
4.53
0.2%
0.002
0.003
2459
2537
I Autoregressive graph shuffle coding results
To evaluate the effect of chunk size, we run autoregressive shuffle coding with varying numbers of equally sized chunks on the SZIP dataset. We report discount unrealized by the net rate, which independent of the ordered model as well as results on the AP model in Figure 5. The results confirm that finer chunks lead to better one-shot rates, with most of the discount realized in the rate for roughly 16 chunks or more, with practical runtimes. We therefore use default of 16 equally-sized chunks in further experiments.
The results also confirm that finer chunks lead to slightly better net rates, effect predicted in Appendix E.2 caused by the corresponding softening of the restriction of a factored approximate automorphism group retrieved through color refinement. Remarkably, we observe that the net rate of autoregressive shuffle coding with 512 chunks is only 2 bits above the optimal rate given by Equation (3) for the SZ.I graph dataset in total, leaving only 0.00002% of the discount unrealized in the net rate, practically matching the optimal net rate from Equation (3), and outperforming incomplete joint shuffle coding. For a more practical 16 chunks, 0.05% of the discount is unrealized in the net rate.
Further results, discussed in Section 6, are shown in Tables 11 13.
'I has been evaluated based results from the deterministic ER codec avoid stochasticity.
23

---

Table 10: Incomplete joint shuffle coding with the autoregressive Pólya ur model (AP), compared to just ordered AP, SZIP and REC graphs. We report mean rates and compression speeds based on 10 compression runs (100 for SZIP graphs) with varying initial message seeds. All net rates are in bits per edge, with empirical standard deviations below 0.02 bits per edge except where shown. Single-threaded and multi-threadee compression speeds with 8 logical cores are reported, all in MB/s.
Speed
Net rate
Thread
8 Threads
Graph
Vertices
Edges
Ord.
Incompl.
Enc.
Dec.
Enc.
Dec.
SZIP
USAir97
0.3k
2.1k
4.17
3.13
1.2
1.3
1.0
1.2
YeastS
2.3k
6.6k
9.17
5.91
1.6
1.6
1.6
1.7
geom
6.2k
21.5k
7.51
4.84
2.0
2.1
2.3
2.4
Erdos
6.9k
11.9k
9.88
4.45
1.8
1.8
2.0
2.0
homo
8.6k
26.1k
10.65
6.98
1.1
1.2
2.2
2.4
25.9k
52.4k
10.24
4.53
2.1
2.2
2.5
2.5
REC
YouTube
3.2M
9.3M
15.34
8.97
1.7
1.5
2.3
1.9
FourSquare
0.6M
3.2M
9.95
6.61
1.5
2.0
Digg
0.8M
5.9M
10.69
8.56
1.8
1.7
2.4
2.2
Gowalla
0.2M
1.0M
13.09
9.82
2.1
2.1
2.7
2.6
Skitter
1.6M
11.1M
14.44
11.59
2.1
1.9
2.9
2.5
DBLP
0.2M
1.0M
16.21
11.24
2.3
2.3
2.8
2.7
Table 11: Compression rates and speeds between incomplete autoregressive shuffle coding with 16 (or 200) chunks and 3 color refinement convolutions using an Erdös-Rény: (ER) and our autoregressive Pólya (AP) model, compared the best results obtained by SZIP (Choi and Szpankowski, 2012) for each graph (on different hardware). We report means and standard deviations based on 100 compression runs with varying initial message seeds. All rates are in bits per edge, and all speeds for 8 threads, in kB/s.
Incomplete Autoregressive Shufile Coding
Rate
ER
AP
AP, 200
SZIP
Airports (USAir97)
5.27+.02
3.32+.033
3.27=t.03
3.81
Protein (YeastS)
7.41
6.46
6.27+t.04
7.05
Collaboration (geom)
8.73+-09
5.24
5.10
5.28
Collaboration (Erdos)
8.05++088
5.55+.008
5.24++-08
5.08
Genetic (homo)
8.81+.03
7.55+.02
7.32+t03
8.49
Internet (as)
9.42+.11
5.75+.08
5.46+t008
5.75
Speed (8 Thread)
Enc.
Dec.
Enc.
Dec.
Enc.
Dec.
Enc.
Airports (USAir97)
301
390
282
433
29
53
(164)
Protein (YeastS)
145
147
576
795
56
89
(77)
Collaboration (geom)
93
86
916
1253
113
201
(64)
Collaboration (Erdos)
46
42
724
983
81
123
(18)
Genetic (homo)
63
58
854
1140
119
215
(32)
Internet (as)
17
15
1025
1408
152
277
(7)

---

5.%
Relative nef-unrealized discount
1.%
0.5%
0.1%
0.05%
5
10
50
100
500
1000
100%
Reletive unrealized discount
60%
40%
10%
10
100
1000
5000
Speed kBis
10
10
100
1000
Chunks
USAir97
YeastS
geom
Erdos
homo
as
Figure 5: Results for incomplete autoregressive shuffle coding for various numbers of chunks on SZIP graphs, based on the AP model and color refinement with 3 convolutions, averaged across 100 repeated runs per data point. The top and middle plots respectively show the increase of the net rate and rate over the optimal rate, relative the discount given by Equation (3). The bottom plots shows compression speeds (dotted lines) and decompression speeds (solid lines), based on the (ordered) Erdós-Rad Rényi rate the reference uncompressed size.
25

---

Table 12: Compression rates and speeds of incomplete autoregressive shuffle coding with 16 chunks and 3 color refinement convolutions based on the AP model, for the REC graph dataset. All rates are reported in bits edge. We show the ordered rate for AP for comparison. Single-threaded and multi-threaded compression speeds are reported in MB/s.
Speed
Ord.
Thread
Threads
Graph
Vertices
Edges
Rate
Rate
Net rate
Enc.
Dec.
Enc.
Dec.
YouTube
3.2M
9.3M
15.34
10.05
8.93
0.5
0.7
0.9
1.3
FourSquare
0.6M
3.2M
9.95
7.12
6.61
0.6
1.0
1.0
1.6
Digg
0.8M
5.9M
10.69
8.81
8.56
0.7
1.3
1.2
2.0
Gowalla
0,2M
1.0M
13.09
10.26
9.81
0.9
1.5
1.4
2.2
Skitter
1.6M
11,1M
14.44
11.92
11.58
0.8
1.2
1.3
2.1
DBLP
0.2M
1.0M
16.21
11.98
11.23
1.5
2.3
Table 13: Compression rates and speeds of incomplete autoregressive shuffle coding with 16 chunks and color refinement convolutions based the AP model, on random graphs sampled from G(n, m) Erdös-Rényi models with large numbers of edges m to one billion, and n = 3/10 m vertices. sampled from, both in
We show the uncompressed size, meaning the ordered rate for the model megabytes total and bits per edge. Rates and net rates are reported in bits per edge, and multi multi-threaded compression speeds in MB/s.
Ord. Rate
Rate
Speed (8 Threads)
Vertices
Edges
ER/MB
ER
AP
Net AP
Enc.
Dec.
30k
100k
0.2
13.6
10.7
10.1
1.2
1.4
300k
1M
2.1
16.9
13.3
12.5
1.4
1.7
3M
10M
25
20.2
15.7
14.9
1.2
1.3
30M
100M
294
23.5
18.2
17.2
0.8
0.9
300M
IB
3358
26.9
20.6
19.5
0.4
0.6
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims are backed by an open-source implementation, with results reported in Section 6.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section 7.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification:
Theory developed in Sections 2 to 4 is backed by proofs in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide an open-source implementation including instructions to replicate all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [Yes]
Justification: Code, data and instructions to replicate experiments are openly available at https://gi thub. www/co////ua/e jun
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc cc/ Sublic//giies/Codeeeiee www.wubsissoooliiioooooooooooooe for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https: /nnps..cc//// hwwpol/c/ggieee//ooooo
conlbiissionn ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper thoroughly describes experimental details in Section 6. Additionally, all code and data open-sourced.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Stochastic experiments are repeated an appropriate amount of times, and number of runs, means and averages are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative enrr rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The type of hardware used in all experiments is described in Appendix G. Runtimes can inferred from reported compression speeds and sizes of the respective data. Further hints are given in the provided source code.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: //nurrip/// http::/eerrrss..ppppllieeeeeeeee hcc///bblcc/ffhccssseeeeees
didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: The authors have concluded that there are no potential harms caused by this work. All data is insensitive and was already publicly available previously.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The presented compression method is foundational without direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Data used in this paper is insensitive.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Original owners of data and code properly credited in repository and their licenses mentioned and respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paper thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
All published code and data is properly documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "CLP3wZyfJK", "reviewer": "Reviewer_AUZQ", "summary": "Coding of unordered structures is considered. This paper addresses the two main limitations of the entropy coding method proposed by Kunze et al. (2024): high cost of automorphism group calculation and poor compression of single unordered objects. To solve the first problem, it is suggested to approximate the object symmetries. The second problem is solved via a recursive coding, which requires an autoregressive probability model. Experiments are performed to demonstrate the merits of the proposed improvements in comparison to the original (``plain'') entropy coding method.", "questions": "- Have you considered generalizing your method to any objects with symmetries inducing the groups of automorphisms?\n- Is it possible to extend your method to non-discrete symmetries? For example, one can consider translation and rotation invariance of images and 3D objects. Such symmetries can \"disappear\" after the floating point discretization due to the machine precision, but it might be possible to define \"approximate\" automorphisms.\n- Have you considered other random graph models, e.g., admitting the clustered structure?\n- Is it possible to conduct more experiments with variable \"accuracy\" of automorphisms calculation (from very poor to almost exact)? It seems interesting to vary the rate increase given in eq. 7 and measure the change in encoding/decoding speed.\n - Repetition in Table 4: ``All measurements are in bits per edge. All measurements are in bits per edge.''\n - Is it possible to add a table, similar to Table 2, but for graph prefixes and other related concepts?", "limitations": "The authors briefly mention some of the limitations in the conclusion. However, I believe that the limitations related to the requirement of an autoregressive probability model should also be mentioned and discussed thoroughly.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written, with all the required preliminary information included. The definitions, theorems, and proofs are mathematically rigorous. However, a great effort has also been made to facilitate the understanding of the article via various examples and clarifications, which is also commendable.\n- The proposed solutions to the issues raised are elegant and might admit a generalization to arbitrary groups of automorphisms.", "weaknesses": "- Recursive variant of the method requires an autoregressive probability model to encode the slices. Such probabilities can be untractable or hard to compute in case of complex models. This might limit the compression capabilities of the method in the case of complex structures. For example, the considered ER and PU random graph models might yield significantly suboptimal results for complex networks, but more advanced models might also be inapplicable due to intractable conditional probabilities.\n- The tradeoff between the approximation of the automorphisms group and encoding/decoding speed and compression rate is under-researched. Only two methods for approximate graph automorphisms calculation are considered.\n- It seems that the method can be abstracted from the ordered/unordered objects and permutations, and can be described in terms of equivalence relations solely. This approach should unify the \"plain\" and \"approximate\" methods and slightly simplify the article. I believe that the current state of the work already requires only the slightest changes to finalize this transition.\n- In the speed comparison table, the encoding speed values for SZIP are not measured on the same hardware as the rest of the experiments, but adopted from the original article.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer AUZQ for their thoughtful, thorough review.\n\n## Weaknesses\n> It seems that the method can be abstracted from the ordered/unordered objects and permutations, and can be described in terms of equivalence relations solely. This approach should unify the \"plain\" and \"approximate\" methods and slightly simplify the article. I believe that the current state of the work already requires only the slightest changes to finalize this transition.\n\nThe described generalization is possible and would allow compressing elements of arbitrary quotient sets. This class of methods can be summarized as bits-back coding (Townsend et al., 2019) restricted to models with deterministic conditional distributions $P(f_\\sim | g)$, which includes all shuffle coding variants.\n\nHowever, the existence of efficient algorithms for (approximate) orbit functions makes permutable classes something of a sweet spot in the trade-off between generality and practicality, hence the choice of framing for this paper.\n\n> In the speed comparison table, the encoding speed values for SZIP are not measured on the same hardware as the rest of the experiments, but adopted from the original article.\n\nWe agree with the reviewer that having results on the same hardware would be valuable. Unfortunately, we have not found a public implementation for SZIP method, making such comparison difficult.\n\n## Questions\n> Have you considered generalizing your method to any objects with symmetries inducing the groups of automorphisms?\n\nYes. This generalization is straightforward, with the resulting rate being\n\n$\\log \\frac{1}{P(\\bar{f})} = \\log \\frac{1}{P(f)} - \\log \\frac{|G|}{|\\text{Aut}(f)|}$, \n\nwhere $G$ is the considered group, i. e. what’s $S_n$ in the paper. Hereby, the ratio inside the discount term computes the size of each coset of $\\text{Aut}(f)$.\n\nAll compelling applications that we found have objects that can be arbitrarily permuted. To keep this already quite technical paper more accessible, we chose to present the paper based on the most important case of a full symmetric group $G=S_n$.\n\n> Is it possible to extend your method to non-discrete symmetries?\n\nContinuous objects have infinite information content, i. e. no probability mass function can be defined over them. Therefore, they require discretization before any lossless compression method can be applied. Our method can be applied to such discretized objects, as usual. The discrete case is therefore sufficient for our practical purposes.\n\nIn some cases, however, we can still generalize our rate for unordered objects to a ‘rate density’. For example, given a probability density function $p(f)$ over continuous objects f, and under the condition that the size of the cosets $c(f)$ of $\\text{Aut}(f)$ is finite, we obtain a probability density function $p(\\bar{f})$ over ‘unordered’ objects, via $p(\\bar{f}) = p(f) \\cdot c(f)$, and the corresponding ‘rate density’ $\\log \\frac{1}{p(\\bar{f})} = \\log \\frac{1}{p(f)} - \\log c(f)$.\n\n> Have you considered other random graph models, e.g., admitting the clustered structure?\n\nYes. Generative modeling of graphs is an active area of research, see Zhu et al. (2022) and Maneth et al. (2015) for surveys. It is somewhat orthogonal to our work since any advance in graph modeling will allow better rates with shuffle coding. The models used in our paper have few parameters, with which we outperform competing methods. Finding and applying models that exploit more structure is a promising research direction to improve rates quickly. As explained in more detail in response to reviewer Htst, our simple Pólya models already exploit a ‘rich get richer’ generative process present in many natural contexts (such as social networks), where vertices with many neighbors have a proportionally higher probability to accumulate even more edges.\n\n> Is it possible to conduct more experiments with variable \"accuracy\" of automorphisms calculation (from very poor to almost exact)? It seems interesting to vary the rate increase given in eq. 7 and measure the change in encoding/decoding speed.\n\nYes. As stated in the overall response, we ran an additional experiment with more variants of incomplete shuffle coding, reporting compression rates and speeds. For this, we chose three datasets with relatively small graphs because more WL iterations quickly become too slow on large graphs as local graph convolution features typically degenerate into global ones exponentially.\n\nThe experiment shows that increasing WL iterations quickly approaches the optimal rate. In all 3 experiments, the exact optimal rate is achieved within 2 to 5 iterations. This corresponds to the fact that the Weisfeiler-Leman graph isomorphism test is effective on practical graphs.\n\n> Repetition in Table 4: \"All measurements are in bits per edge. All measurements are in bits per edge.\"\n\nThanks, this will be fixed!\n\n> Is it possible to add a table, similar to Table 2, but for graph prefixes and other related concepts?\n\nThis is a fantastic idea, and we will include it in the final version of the paper.\n\n## Limitations\n> I believe that the limitations related to the requirement of an autoregressive probability model should also be mentioned and discussed thoroughly.\n\nAgreed, will do! We want to emphasize here that we propose joint shuffle coding to mitigate exactly this restriction. Additionally, recent work on autoregressive models is promising (see Kong et al., 2023), and our results show that such models can lead to competitive rates even with few parameters.\n\n## References\nZhu, Yanqiao et al. (2022): A survey on deep graph generation: Methods and applications. Learning on Graphs Conference. PMLR.\n\nManeth, Sebastian et al. (2015): A survey on methods and systems for graph compression. arXiv preprint.\n\nTownsend, James et al. (2019): Practical lossless compression with latent variables using bits back coding. ICLR.\n\nKong, Lingkai, et al. (2023): Autoregressive diffusion model for graph generation. ICML. PMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eymt51LPDN", "reviewer": "Reviewer_NPhs", "summary": "This paper proposed an entropy coding method of  large unordered data structures. The newly proposed method allows one-shot  compression and achieves competitive speed. The experimental results demonstrate the advantages.", "questions": "What are the applications of one-shot compression?", "limitations": "No. The comparison with other works for common cases (other than one-shot compression) should be discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper proposed a new entropy coding method for large unordered data sets with near-optimal compression. Specially, the new method allows one-shot compression. In addition, the new method has competitive speed, which is verified by the experiments.", "weaknesses": "As a contribution, the proposed method in this paper can work for one-shot compression while the SOTA works can not. Hence, the applications of one-shot compression should be presented and stressed in details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer NPhs for taking the time to review and comment on our paper.\n\n### Questions\n> What are the applications of one-shot compression?\n\nExample applications include storing/transmitting large social, web, network, or compute graphs, JSON files (nested multisets), machine learning datasets, and relational database tables with many rows (multisets). Large objects of these kinds are often sent/stored separately, making one-shot compression an interesting problem. For this reason, the initial bits problem of plain shuffle coding poses a fairly substantial limitation in practice.\n\n### Limitations\n> The comparison with other works for common cases (other than one-shot compression) should be discussed.\n\nAs described and discussed in the overall response, we performed additional experiments on all TU datasets comparing our method to plain shuffle coding outside of the one-shot regime, for graphs with vertex and edge attributes. Specifically, we compress the many graphs per dataset together in sequence. The experiments clearly show that outside of the one-shot regime, incomplete recursive shuffle coding can offer dramatically faster speeds for relatively small increases in compression rate.\n\nWe hope that this addresses your concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5kGMMlqfPp", "reviewer": "Reviewer_Htst", "summary": "This paper proposes recursive shuffle coding, a general method for optimal compression of unordered objects using bits-back coding. And the paper further presents present incomplete shuffle coding, allowing near-optimal compression of large unordered objects with intractable automorphism groups. When combined, these methods achieve state-of-the-art one-shot compression rates on various large network graphs at competitive speeds.", "questions": "1. Could you specifically explain more details of the Autoregression PU model in Appendix C?\n2. Could you clarify the connection between recursive shuffle coding and incomplete shuffle coding?", "limitations": "1. Less evaluation on unordered graphs with vertex and edge attributes.\n2 Answer my questions Q1 and Q2.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Incomplete recursive methods improve the speed of processing large-scale unordered multiple sets.\n2. The paper is a solid contribution with solid theoretical foundations. Introducing group theory to consider this problem is very interesting.", "weaknesses": "1. The two methods seem to address different issues and do not clarify their connection. \n2. The symbols in the paper are too numerous, making it difficult to intuitively understand your intention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer Htst for their review, comments, and questions.\n\n## Weaknesses\n> The two methods seem to address different issues and do not clarify their connection.\n\nYour observation is correct, the two methods address different issues. They appear together in this paper since it is convenient to use recursive shuffle coding to implement incomplete shuffle coding, and their advantages can be combined this way. Specifically, we implement incomplete shuffle coding by modifying the orbits function to return orbits of an incompletely ordered object, approximating the orbits (and automorphism group) of the underlying ordered object.\nIt would be feasible for incomplete shuffle coding to be based on plain shuffle coding instead, requiring a function that returns an approximate canonization and automorphism group for a given object. While this would be an interesting direction of research, readily available graph isomorphism libraries do not provide such functionality. Therefore, we leave implementing this idea for future work and focus on the approach based on recursive shuffle coding.\n\n> Less evaluation on unordered graphs with vertex and edge attributes.\n\nAs stated in the overall response, we ran additional experiments on a vast array of graph datasets featuring vertex and edge attributes, confirming that the favorable properties of our method extend to attributed graphs.\n\n## Questions\n\n> The symbols in the paper are too numerous, making it difficult to intuitively understand your intention.\n\nWhile we agree that this is a technical paper, we spent great effort on visualizations to help motivate and clarify the technical concepts required for formalizing our method. In particular, we strongly encourage the reviewer to revisit the example in Tables 1 and 2, as well as Figure 1.\n\n\n> Could you specifically explain more details of the Autoregression PU model in Appendix C?\n\nYes. We will extend Appendix C and also give a detailed explanation here.\n\nThe joint model we want to approximate is the Pólya urn model from Kunze et al. (2024). Its iterative generative process starts from an empty graph, into which a fixed number of edges are inserted iteratively. The two vertices forming the next inserted edge are sampled with probabilities proportional to the current number of vertex neighbors (+1). This process favors vertices that already have many neighbors in a ‘rich get richer’ dynamic, often called ‘preferential attachment’, with a skewed distribution over vertex neighbor counts.\nHerby, self-loops and redraws are disallowed. This breaks edge-exchangeability, leading to a 'stochastic' codec, meaning that the code length depends on the initial message. Shuffle coding is compatible with such models. In this more general setting, the ordered log-likelihood term in the optimal rate of Eq. 3 is replaced with a variational `evidence lower bound' (ELBO). The discount term is unaffected. The derivations in the main text are based on the special case of exchangeable models, where log-likelihoods are exact, for simplicity. They can be generalized with little effort and new insight.\n\nWe will now describe the approximate Pólya urn (AP) model that is autoregressive over graph slices. A graph slice $f_i$ can be represented as the set of edges connecting the vertex $i$ with any following vertex, i. e. a subset of $\\lbrace (i, i+1), (i, i+2), … (i, n-1) \\rbrace$. Any autoregressive graph model will provide a distribution over slices $f_i$, given the graph prefix $f_{[i]}$ (that comprises all previous slices). We can break down the task into two parts: Given the prefix $f_{[i]}$, predict the number of edges $k_i \\in [n - i]$ within the next slice $f_i$, and then from that, predict the edge positions within the slice.\nFor the Pólya urn model, the distribution for the first part, $P(k_i | f_{[i]})$, is not tractable and we instead approximate it by a truncated log-uniform distribution $Q(k_i | f_{[i]})$ where $\\lfloor \\log k_i | f_{[i]} \\rfloor$ is (approximately) uniformly distributed within the possible range.\n\nThe distribution of the second part, $P(f_i | f_{[i]}, k_i)$, is tractable with the following generative process: Given the graph of the prefix $f_{[i]}$ and the number of edges $k_i$ in the next slice $f_i$, iteratively insert $k_i$ edges, with probabilities proportional to the neighbor count + 1 of the adjacent vertices $\\{ i+1, i+2, … n-1\\}$ without allowing repetition (i. e. zeroing out the probabilities where edges were already inserted).\n\nWe then have the slice distribution $Q(f_i | f_{[i]}) = \\sum_{k_i=0}^{n-i} P(f_i | f_{[i]}, k_i) Q(k_i | f_{[i]})$, and finally the complete AP model $Q(f) = \\prod_{i=0}^{n-1} Q(f_i | f_{[i]})$.\n\nThe approximation of $k_i$ increases the stochasticity of the compression rates, much like disallowing self-loops/redraws. As described in the overall response, we conducted further experiments to characterize this stochasticity. We report empirical means and standard deviations of compression rates for the experiments from Table 4 with the AP model, on the supplemental page in Table S1. It shows that the resulting stochasticity is significant, highlighting that our choice of $Q(f_i | f_{[i]})$ is a crude approximation. Improving it, for example, by using information from the prefix $f_{[i]}$, is left for future work.\n\n> Could you clarify the connection between recursive shuffle coding and incomplete shuffle coding?\n\nThis is answered in the first section of this response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gpGoh2bW60", "reviewer": "Reviewer_tkqf", "summary": "The design of compression mechanisms for compression of unordered objects is considered. The scenario models various applications of interest such as compression of unlabeled graphs and multisets. A novel recursive solution, called recursive shuffle, is introduced. An advantage of this compression mechanism, compared to previous plain shuffle method, is that it can be applied in one-shot compression scenarios. However, it is noted that since the mechanism requires computation of orbits of prefixes, it cannot be completed in polynomial time. To mitigate this, an alternative `sub-optimal' mechanism is introduced which does not jointly compress all of the order information, and handles part of the information separately. The mechanism is called incomplete recursive shuffle. Various simulations on real-world datasets are provided to compare the performance of the proposed mechanism with the state of the art methods.", "questions": "- It appears from Tables 5 and 6 that the performance of SZIP is comparable and even better than the proposed methods on average. Please comment on why and in what respect if any do the proposed methods outperform SZIP?\n- In Table 4, sometimes WL_1 and sometimes WL_2 hashing yields better results. I wonder if there is an intuitive explanation and a way to determine what type of hash should be used beforehand. Also, the proposed methods sometimes outperform SZIP and sometime do not. Please comment if there are specific conditions (such as graph statistics) that would cause one mechanism to outperform in different scenarios.", "limitations": "- The comparison with SZIP performance should be made more explicit and comprehensive in the discussions in Section 6.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The compression problem considered in this work is of interest and is applicable to a wide range of graph compression problems. \n- The method, using a recursive process that interleaves encoding and decoding steps to allow for one-shot compression, and which avoids jointly compressing all order information to reduce run-time is novel and interesting. \n- The paper is well-written, and the proof arguments and explanations are complete and clear.\n- The manuscript includes comprehensive numerical simulations and comparisons with the state of the art methods both in terms of compression rate and speed of compression.", "weaknesses": "- As mentioned in the manuscript, the recursive shuffle mechanism requires computation of the orbits of the prefixes, which cannot be solved in polynomial time. The alternative of separately compressing part of the order information is suboptimal in terms of compression rates.\n-  In several of the scenarios for graph compression, the experimental results do not seem to show significant gains compared to SZIP and Plane shuffle methods. For instance, in Table 5, for one-shot compression, SZIP outperforms the proposed methods in two of the datasets and performs comparably in the other four. Furthermore, while the compression speed is significantly faster than plain shuffle, it is still below that of SZIP in several cases as shown in Table 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer tkqf for taking the time to review our paper.\n\nIt will be helpful to respond to part of your second question first:\n\n> In Table 4, sometimes WL$_1$ and sometimes WL$_2$ hashing yields better results. I wonder if there is an intuitive explanation and a way to determine what type of hash should be used beforehand. Also, the proposed methods sometimes outperform SZIP and sometime do not.\n\nWe thank the reviewer for pointing this out. Using more Weisfeiler Leman hashing iterations with incomplete recursive shuffle coding will always result in equal or better rates in expectation over all possible initial messages, assuming that hash collisions are rare enough, a condition practically achieved with standard 64-bit hashing methods. Our paper was misleading in this sense, and will be amended, in two ways:\n\n- As detailed in our response to reviewer Htst and briefly mentioned in Appendix C, the AP model uses a variational approximation. In the paper we failed to clarify that this can lead to the rate depending on the initial message, making it appear stochastic. We will update the paper accordingly.\n- In Table 4 we only reported each compression rate result for the AP model based on a single run. This was misleading in the sense that WL$_2$ appeared worse than WL$_1$ for some graphs. As stated in the overall response, we have now repeated each of these experiments three times with different initial message seeds, and the new results, shown in Table S1 of the supplemental page, are compatible with the prediction that WL$_2$ has a rate at least as good as WL$_1$. We now also report empirical standard deviations to characterize the stochasticity of the AP model.\n\nWe will now respond to the remaining questions together:\n> Also, the proposed methods sometimes outperform SZIP and sometime do not. Please comment if there are specific conditions (such as graph statistics) that would cause one mechanism to outperform in different scenarios.\n\n> It appears from Tables 5 and 6 that the performance of SZIP is comparable and even better than the proposed methods on average. Please comment on why and in what respect if any do the proposed methods outperform SZIP?\n\nAs described in the overall response, our new results in Table S1 show that incomplete shuffle coding now comfortably outperforms SZIP both with AP/WL$_1$ and AP/WL$_2$ in terms of one-shot compression rate.\n\nOur proposed methods are entropy coding methods, with optimal rates for a model that can be easily inspected, improved, and swapped out.\nShuffle coding methods can therefore be easily adapted to specific domain models, and automatically benefit from advances in generative graph modeling. The model update mentioned above leading to the drastically improved rates from Table S1 demonstrates this capability. \n\nThis is not possible for SZIP, since it is not based on an explicit probabilistic model. If its implicit model fails, there is no known method to improve it. Similarly, it is difficult to reason about the strengths of SZIP. \n\nOne thing that we do know is that for large enough graphs, SZIP cannot perform significantly worse than shuffle coding with an Erdős–Rényi graph model, due to the rate upper bound discussed in Section 5,\n\n$\\log\\frac{1}{P_\\mathrm{ER}(g)} - n\\log n + O(n)$.\n\nIt is hard to know how large graphs have to be for this bound to have practical significance, since the constant factor for $O(n)$ is unknown.\n\nIn contrast, we can easily inspect the explicit model used by shuffle coding. We know, for example, that preferential attachment models, like the Pólya urn models (PU / AP) used in our experiments, are suitable whenever there is a ‘rich get richer’ dynamic in the generating process, meaning the rate at which new neighbors are attached is approximately proportional to the number of neighbors already present, leading to skewed neighbor count distributions (see Severo et al. 2023 for more details). This dynamic is present in many natural contexts such as social networks or web graphs, providing a possible explanation for good performance of Pólya urn models on such graphs.\n\nWe will extend the discussion on SZIP in Section 6 accordingly to be more comprehensive.\n\n### References\n\nSevero, Daniel, et al. (2023): Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs.\" arXiv preprint arXiv:2305.09705.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are delighted that all reviewers agreed on the good soundness of the paper, with multiple pointing out its mathematical rigor, and most reviewers appreciate its presentation.

Based on reviewers’ requests, we are excited to report striking new experimental results on our supplemental page, described here, and discussed further in the individual responses:

- Table S1 updates Table 4 from the paper. We found that for incomplete recursive shuffle coding with the autoregressive Pólya urn (AP) graph model, to compress edge counts $k_i$ in slices, using a simple approximation based on a discretized Pareto distribution (specifically, $Q(k_i) \propto \frac{1}{2} k_i^{-2}$ for $k_i>1$ with $Q(k_i=0)=Q(k_i=1)=\frac{1}{3}$) leads to much-improved rates over the previously used log-uniform distribution. As a result, our method now comfortably outperforms SZIP in terms of one-shot compression rate for both the AP/WL$_1$ and AP/WL$_2$ configurations. This also improves all results in Table 5, which we will update in the final version.
- We now repeat these AP experiments with varying seeds, and report means and empirical standard deviations. As explained further in the responses below, this highlights the stochastic nature specific to the AP model and supports the prediction that more WL iterations in practice lead to better or equal expected rates. Previous results for AP in Table 4 were misleading in these two respects.
- In Table S2, we compare incomplete recursive with plain shuffle coding on all the 136 TU graph datasets (Morris et al., 2020) in six categories, ranging from molecules to social networks, with the majority of these datasets featuring vertex and edge attributes (see [chrsmrrs.github.io/datasets/docs/datasets](https://chrsmrrs.github.io/datasets/docs/datasets/) for details). Our method leads to a dramatic speedup over plain shuffle coding on some of these datasets, with a minimal increase in compression rate across all datasets, showing that these favorable properties extend to graphs with attributes. Maximum-likelihood parameters for a categorical distribution over vertex and edge attributes are inferred for and coded along with each dataset, as done and described in Kunze et al. 2024.
- Figure S1 shows how the compression rate and speed varies with the automorphism group's approximation level, on three such graph datasets. This experiment further confirms that in practice, a low number of WL iterations is sufficient to get very close to the optimal rate.

**Crucially, the new results show that our method now achieves state-of-the-art rates in one-shot graph compression, as well as competitive rates and speeds on graphs with attributes, and explore the method’s rate-speed trade-off. We believe these results significantly strengthen the paper, particularly in the 'contribution' category.** We hope that the reviewers agree, find our responses satisfactory, and that their concerns are being fully addressed.

### References

Morris, Christopher et al. (2020): TUdataset: A collection of benchmark datasets for learning with graphs. Graph Learning and Beyond workshop, ICML. [chrsmrrs.github.io/datasets](https://chrsmrrs.github.io/datasets/)

Kunze, Julius et al. (2024): Entropy Coding of Unordered Data Structures. ICLR.

Meta-review: The paper proposes recursive shuffle coding, a general method for comparison of unordered data structures (multisets, unlabeled graphs, etc.) based on bits-back coding. The paper improves on recent previous works that utilize similar techniques for compressing unordered structures. Recursive shuffle coding, unlike the previous "plain" shuffle coding, can be applied in one-shot compression scenarios (where a single unordered object needs to be compressed). Moreover, the paper proposes incomplete shuffle coding, which mitigates the fact that shuffle coding requires computing the automorphism group (which can be computationally intractable). The methods achieve state-of-the-art compression rates on several datasets.

The reviewers mostly agree that this paper provides meaningful improvements over previous shuffle coding approaches. As compression of unordered data structures has a wide range of applications, this is a meaningful contribution.
Decision: Accept (poster)