Entropy Coding of Unordered Data Structures
Authors: Julius Kunze
Daniel Severo
Giulio Zani
Jan-Willem van de Meent
James Townsend
Venue: ICLR 2024 poster (2024)
Keywords: graph compression
entropy coding
neural compression
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 (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We present shuffle coding, a general method for optimal compression of unordered objects, achieving state-of-the-art compression rates on a range of graph datasets including molecular data.

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

Published as a conference paper at ICLR 2024
ENTROPY CODING OF UNORDERED DATA STRUCTURES
Julius Kunze University College London juliuskunze@maiil.com
Daniel Severo
University of Toronto and Vector Institute d. severo@mail wtw.onto.caaaaaa
Giulio Zani
Jan- Malllellem van de Meent University of Amsterdam w. vandemeent@uva.nn
James Townsend
University of Amsterdam g. s.zani@uva.nl
University of Amsterdam h. townsend@uva.n!
ABSTRACT
We present shuffle coding, a general method for optimal compression of sequences of unordered objects using bits-back coding. Data structures that be com- pressed using shuffle coding include multisets, graphs, hypergraphs, and others. We release implementation that can easily be adapted to different data types and statistical models, and demonstrate that our implementation achieves state-of- the-art compression rates on a range of graph datasets including molecular data.
INTRODUCTION
The information stored and communicated by computer hardware, in the form of strings of bits and bytes, is inherently ordered. A string has first and last element, and may be indexed by numbers N, a totally ordered set. For data like text, audio, or video, this ordering carries meaning. However, there are also numerous data structures in which the 'elements' have no meaningful order. Common examples include graphs, sets and multisets, and 'map-like' datatypes such as JSON. Recent applications of machine learning molecular data benefit from large datasets of molecules, which are graphs with vertex and edge labels representing atom and bond types (some examples shown in Table | below). All of these data are necessarily stored in ordered manner computer, but the order then represents redundant information. This work concerns optimal lossless compression of unordered data, and seek eliminate this redundancy.
Examples of molecules and their order information. The 'discount' column shows the saving achieved by shuffle coding by removing order information (see eq. 14). For each molecule m, n is the number of atoms and [Aut(m)] is the size of the automorphism group. All values are in bits, and log denotes the binary logarithm.
Table 1:
Permutation log n!
Symmetry [m
Discount
Molecular structure
log n! - log Aut Aut(m)
Nitric oxide
1.00
0.00
1.00
Water
2.58
1.00
1.58
II
Hydrogen peroxide
0-0
4.58
1.00
3.58
Ethylene
9.49
3.00
6.49
I1Q B-O
Boric acid
12.30
2.58
9.71

---

Published as a conference paper at ICLR 2024
Recent work by Severo et al. (2023a) showed how to construct optimal lossless codec for (un- ordered) multisets from a codec for (ordered) vectors, by storing information in an ordering. Their method depends the simple structure of multisets' 'automorphism groups, and does not extend to other unordered objects such as unlabeled graphs. this paper we overcome this issue and de- velop shuffle coding, method for constructing codecs for general 'unordered objects' from codecs for 'ordered objects'. Our definitions of ordered and unordered objects are based on the concept of "combinatorial species' (Bergeron al., 1997| Joyal. 1981) originally developed assist with the enumeration of combinatorial structures. They include multisets, as well as all of the other unordered data structures mentioned above, and many more.
Although the method is applicable to any unordered object, we focus our experiments on unordered (usually referred to as 'unlabeled") graphs, as these are a widely used data type, and the improve- ments in compression rate from removing order information are large (as summarized in Table (2) We show that shuffle coding can achieve significant improvements relative to existing methods, when compressing unordered graphs under the Erdōs-Rényi G(n,p) model of Erdōs and Rényi (1960) as well as the recently proposed Pólya's urn-based model of Severo et al. (2023b). Shuffle coding extends to graphs with vertex and edge attributes, such as the molecular and social network datasets of TUDatasets (Morris et al., 2020). which are compressed in Section We release source code with straightforward interfaces enable future applications of shuffle coding with more phisticated models and to classes of unordered objects other than graphs.
2
BACKGROUND
The definitions for ordered and unordered objects are given in Section 2.1 Entropy coding is re- viewed in Section 2.2 Examples are given throughout the section for clarification.
2.1 PERMUTABLE CLASSES
For n E N. we let [n] == {0, 1, I,..., - 1}, with [0] = 0. The symmetric group of permutations on [n], i.e. bijections from [n] to [n]] will be denoted by S... Permutations compose the left, like functions, i.e., for 8, E S,, the product st denotes the permutation formed by performing t then 8.
Permutations are represented as follows
0 \. > =
(2,0, E S3.
2
The glyph on the left-hand side represents the permutation that maps 0 to to 0 and 2 to This permutation can also be represented concretely by the vector 12)
Concepts from group theory, including subgroups, cosets, actions, orbits, and stabilizers used throughout. We provide a brief introduction in Appendix A
We will be compressing objects which can be 're-ordered' by applying permutations. This for- malized in the following definition:
Definition 2.1 (Permutable classj. For n E N, a permutable class of order n a set F, equipped with a left group action of the permutation group Sn, on F, which we denote with the binary operator. We refer to elements of F as ordered objects.
Example 2.1 (Length n strings). For a fixed set X, let F, = X", that is, length n strings of elements of X, and let S,, act on a string in Fr by rearranging its elements.
Taking X to be the set of ASCII characters, we can define a permutable class of ASCII strings, with action by rearrangement, for example
"Team" "eaTm".
Source code, data and results are available http://ghhhhb.commo.uuuuuuue/eee "This definition is very close to that of a 'combinatorial species', the main difference being that we fix specific See discussion Yorgey (2014) pp. 66-67).
2

---

Published as a conference paper at ICLR 2024
Example 2.2 (Simple graphs 9n). Let Gn be the set of simple graphs with vertex set [n]. Specifically, an element g E In is a set of 'edges', , which are unordered pairs of elements of [n]. We define the action of Sn graph by moving the endpoints of each edge in the direction of the arrows, for example
0
0 = 3 X
33
Our main contribution this paper a general method for compressing unordered objects. These may be defined formally in terms of the equivalence classes, known orbits, which comprise objects that are identical up to re-ordering (see Appendix [ for background):
Definition 2.2 (Isomorphism, unordered objects). For two objects and g in a permutable class F, we say that f is isomorphic to 9. and write = 9. if there exists S, such that = f (i.e. and are the same orbit under the action of S,). Note that the relation = is an equivalence relation. For f E F we use f to denote the equivalence class containing J, and F to denote the quotient set of equivalence classes, We refer to elements f E F as unordered objects.
For the case of strings in example 2.1 an object's isomorphism class is characterized by the multiset of elements contained in the string. For the simple graphs in example 2.2] the generalized isomor- phism in definition reduces to the usual notion of graph isomorphism. We can define a shorthand notation for unordered graphs, with points at the nodes instead of numbers:
(4)
Using this notation, unordered simple graphs on three vertices, for example, can written:
F .
(5)
Finally, we define the subgroup of S,, which contains the symmetries of given object f: Definition 2.3 (Automorphism group). For an element f of permutable class F, we let Aut(f)
denote the autemorphiss group of f. defined by
Aui(S) (a S. 8- 8-
(6)
This is the stabilizer subgroup of under the action of Sn,
The elements of the automorphism group of the simple graph from example are:
(0)))=
20
0
Aut
3 3-2
e3 20
23
2
2.1.1 CANONICAL ORDERINGS
To define a codec for unordered objects, we will introduce the notion of 'canonical' representative of each equivalence class in F. This allows us, for example, to check whether two ordered objects are isomorphic, by mapping both to the canonical representative and comparing.
Definition 2.4 (Canonical ordering). A canonical ordering an operator F such that
1. For f E F, we have f.
2. For f.gEF, = ÿ if and only if g.
For strings, any sorting function satisfies properties I and and is therefore a valid canonical order- ing. For graphs, the canonical orderings (McKay and Piperno, 2014). The libraries provide a function, which we call canon_perm, which, given graph g, returns permutation such that s.g. = g. In addition to canon_perm, nauty and
computed using the nauty and Traces libraries

---

Published as a conference paper at ICLR 2024
Traces can compute the automorphism group of a given graph, via a function which refer as aut
Our method critically depends the availability of such function for given permutation class. While permutable objects other than graphs cannot be directly canonized by nauty and Traces, is often possible embed objects into graphs in such way that the structure is preserved and the onization remains valid (see Anders and Schweitzer (2021). We use an embedding edge-colored graphs into vertex-colored graphs in order canonize and compress graphs with edge attributes (which are not directly supported by nauty/traces). We leave more systematic approaches to canon- izing objects from permutable classes as an interesting direction for future work
2.2 CODECS
We fix set M of prefix-free binary messages. and length function 1: M [0, oo), which mea- sures the number of physical bits required to represent values in M. Our method requires stack-like (LIFO) codecs, such as those based on the range variant of asymmetric numeral systems (rANS), to save bits corresponding to the redundant order using bits-back (Townsend et al., 2019).
Definition 2.5 ((Stack-like) codec). A stack-like codec (or simply codec) for set X is an invertible function
encode M X + M.
(8)
We call codec optimal for probability distribution over X with mass function if for any m E M and x E X,
(())codemm,;:) = [(m) log P(x)
We refer to log P(x) 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.
The encode function requires pre-existing message its first input. Therefore, at the beginning of encoding we set m equal to some fixed, short initial message mo. with length less than 64 bits. As in other entropy coding methods, which invariably have some small constant overhead, this 'initial bit cost' is amortized as we compress more data.
We will assume access to three primitive codecs provided by rANS. These are
Uniform(n), optimal for uniform distribution on (0, n,...,nn1};
Bernoulli (p), optimal for a Bernoulli distribution with probability
Categorical (ps), optimal for a categorical distribution with probability vector ps.
These primitive codecs can be composed to implement codecs for strings and simple graphs. In appendix [B. we show such string codec optimal for distribution where each character is drawn i.i.d. from categorical with known probabilities, and a codec for simple graphs optimal for the Erdös-Rény' G(n,p) p) model, where each edge's existence is decided by an independent draw from Bernoulli with known probability parameter. We will use these codecs for ordered objects component of shuffle coding.
There is an iupllmmentation-ddeeedder limit on the parameter of Uniform and on the number of categories for Categorica ments, this limit is 288 This is not large enough to, for example, cover S, for large and therefore permutations must be encoded and decoded sequentially, see Appendix [ For details on the imple- mentation of the primitive rANS codecs listed above, see Duda (2009) and Townsend (2021).
In the 64-bit rANS implementation which we wrote for our experi-
IIn fact, a list of generators for the group is computed, rather than the entire group, which may be very large. 'Schweitzer and Wichking (2019) descrihe generic methods for canonization starting from constructive definition permutable objects using 'hereditarily finite sets' (i.c. not using the species definition).
"This condition, with suitable definition of x,, is equivalent to rate-optimality in the usual Shannon sense, Townsend (0220)
4

---

Published as a conference paper at ICLR 2024
20
12
051
0-1
22
22
2
0-1
2
0
0
1
2
2
2
0-1
0
12
R
(
2
2
2
Figure 1: Visualization of lemma 3.2, For fixed graph g. the six elements 8 E S3 can be partitioned
according to the value of s g. The three sets the partition are the left cosets Aut
CODECS FOR UNORDERED OBJECTS
Our main contribution in this paper is generic codec for unordered objects, i.c. codec respecting a given probability distribution on F. We first derive an expression for the optimal rate that this describe the codec itself.
codec should achieve, then in Section 3.1
To help simplify the presentation, we will use the following generalization of exchangeability from sequences of random variables to arbitrary permutable classes:
Definition 3.1 (Exchangeabilitty. For a probability distribution P defined on a permutable class F, we say that P is exchangeable isomorphic objects have equal probability under i.e. if
= g P()) P(g).
(10)
We can assume, without loss of modeling power, that unordered objects are generated by first gen- erating an ordered object from exchangeable distribution and then 'forgetting" the order by projecting f onto its isomorphism class f:
Lemma 3.1 (Symmetrization). For any distribution Q on a class of unordered objects F, there exists unique exchangeable distribution P on ordered objects F for which
Q Σ P(g)-
(11)
gEf
Proof. For existence, set P(f) Q(f)lfl for f e F. and note that f f. uniqueness, note that definition 3.1 implies that the restriction of P to any particular class must be uniform, which completely determines P.
For
We will model real-world permutable objects using an exchangeable model, which will play the role of eq. [T). To further simplify our rate expression we will also need the following application of the orbit-stabilizer theorem (see Appendix A for more detail), which is visualized in Figure !
Lemma 3.2. Given permutable class Foror each object I E F, there is fixed bijection between the left cosets of Aut(F) ) in Sn and the isomorphism class f. This is induced by the function oj S,, + F defined by 0y(s) = 3 This implies that
1Sp1
n!!
I/|
(12)
Aul(D]
Proof. Follows directly from the orbit-stabilizer theorem (theorem A.1 and the definitions of Aut, and J.
For any f E F, this allows to express the right hand side of eq.
n!
P(g) = (j(((f) = [Aut(F) P(f)
(13)
EEj
5

---

Published as a conference paper at ICLR 2024
where the first equality follows from exchangeability of P. and the second from eq. (12 Finally, from eqs. (IT) and (I3). we can immediately write down the following optimal rate expression, which codec unordered objects should achieve:
n!
log
log P())
log [At
(14)
Q(f)
Ordored rate
Discount
Note that only the log (J) term depends on the choice of model. The log(n!//Aut(A)) term can be computed directly from the data, and is the 'discount" that we get for compressing an unordered object vs. compressing an ordered one. The discount is larger for objects which have a smaller automorphism group, i.c. objects which lack symmetry. graphs have trivial automorphism group for large enough see e.g. Bollobás (2001, Chapter 9), and thus in practice the discount is usually equal to or close to log n!.
can be shown that almost all simple
3.1
ACHIEVING THE TARGET RATE FOR UNORDERED OBJECTS
How can we achieve the optimal rate in eq. ( appendix we give examples codecs for ordered strings and simple graphs which achieve the 'ordered rate To operationalize the negative 'discount' term, we can use the 'bits- back with ANS' method introduced by Townsend et al. (2019), the key idea being decode ordering as part of an encode function (see line in the code below).
The value the negative term in the rate provides a hint at how exactly to decode an ordering: the discount equal to the logarithm the number of cosets of Aut in Sn, so uniform codec for those cosets will consume exactly that many bits. Lemma 3.2 tells that there is a direct correspondence between the cosets of Aut(F) and the set f. so if uniformly decode choice of coset, we can reversibly map that to an ordering of f.
The following is an implementation of shuffle coding, showing, the right, the effect of the steps on message length.
def encode (m, f):
Effect on message length:
f_canon actiinnnnaae accioo_epply(cmooneeem(()) f)
m, s Cosee cfcfff__anonuuuraaa aut)) decode (m) = action_apply(e f_canon)
- log [
s
encode (m, g)
+ log P(F)
return
def decode
m, P. deceode (m)
s_ anw_canoo_perrmeeee
f_canon action_unapply(s_, f)
12
foi (f_cccff___caccoccm aut). encode s_)
return m, f_canon
The encode function accepts pair (m, f), and reversibly decodes a random choice g from the isomorphism class of f. This is done using uniform codec for left cosets, UniformL Coset,, which we discuss in detail in Appendix C The canonization on line 2 is necessary so that the decoder can recover the chosen coset and encode it line 12. While the codec technically maps between M x F and M, we avoid representing equivalence classes explicitly as sets, and instead use single element of the class encoded, and the decoder then returns the canonization of Similarly, Uni PniforLLCoee encode accepts any element of the coset, and UniformL www.omooooee.eooooooooooooo returns canonical coset element.
representative. Thus the encoder accepts any f in the isomorphism class being
3.2 INITIAL BITS
The increase in message length from shuffle coding is equal the optimal rate in the decode step on line of the encode function assumes that there is already some information in the message which be decoded. At the very beginning of encoding, these 'initial bits' can be
eq. (14). However,

---

Published as a conference paper at ICLR 2024
generated at random, but they are unavoidably encoded into the message, meaning that for the first object, the discount is not realized. This constant initialization overhead means that the rate, when compressing only or a few objects, is not optimal, but tends to the optimal rate if more objects are compressed, as the overhead is amortized.
4 RELATED WORK
To date, there has been a significant amount of work on compression of what refer to 'ordered' graphs, see Besta and Hoefler (2019) for a comprehensive survey. Compression of 'unordered" graphs, and unordered objects in general, has been less well studied, despite the significant potential benefits of removing order information (see Table 2). The work of Varshney and Goyal (2006) is the earliest we are aware of to discuss the theoretical bounds for compression of sets and multisets, which are unordered strings.
Choi and Szpankowski (2012) discuss the optimal rate for unordered graphs (a special case of our eq. [4). and present a compression method called 'structural ZIP" (SZIP), which asymptotically achieves the rate
log PER(2) n logo + O(n).
(15)
where PER is the Erdös-Rényi G(n. p) model. Compared sense that it only applies to simple graphs (without vertex or edge attributes), and is not an entropy coding method, thus the model PER cannot be changed easily. On the other hand, SZIP can achieve good rates on single graphs, whereas, because of the initial bits issue (see Section 3.2), our method only achieves the optimal rate on sequences of objects. We discuss this issue further and provide quantitative comparison in Section
method, SZIP is less flexible in the
Steinruecken (2014 2015 2016) provides range of specialized methods for compression of various ordered and unordered permutable objects, including multisets, permutations, combinations and compositions. Steinruecken's 's approach is similar to ours in that explicit probabilistic modeling used, although different methods are devised for each kind of object rather than attempting unifying treatment as we have done.
Our method can be viewed a generalization of the framework for multiset compression pre- sented in Severo et al. (2023a). which also used 'bits-back with ANS' (BB-ANS; Townsend, [202T] Townsend al., (2119). Severo et al. (2023a) use interleaving reduce the initial bits overhead and achieve an optimal rate when compressing a single multiset (which can also be applied to a sequence of multisets), whereas the method presented in this paper is optimal only for sequences of unordered objects (including sequences of multisets). However, as mentioned in Section 1 their method only works for multisets and not for more general unordered objects.
There are a number of recent works on deep generative modeling of graphs (see Zhu et al. (2022) for survey), which could be applied to entropy coding improve compression rates. Particu- larly relevant Chen et al. (202T). who optimize an evidence lower-bound (ELBO), equivalent to an upper-bound on the rate in eq. (14), when P not exchangeable. Finally, the 'Partition and Code" (PnC; Bouritsas et al., (021 method uses neural networks to compress unordered graphs. We compare PnC empirically in Table 3 PnC is also specialized to graphs, although it does employ probabilistic modeling to some extent.
EXPERIMENTS
To demonstrate the method experimentally, we first applied it to the TUDatasets graphs (Morris et al., 2222),, with very simple Erdös-Rényi G(n, p) model for P. Table 2 shows a summary, highlighting the significance of the discount achieved by shuffle coding. We compressed a dataset at time (note that for each high-level graph type there are multiple datasets in TUDatasets).
To handle graphs with discrete vertex and edge attributes, we treated all attributes as independent and identically distributed (i..d.) within each dataset. For each dataset, the codec computes and encodes a separate empirical probability vector for vertices and edges, as well as an empirical parameter, and the size of each graph. We use run-length encoding for these meta-data, described
7

---

Published as a conference paper at ICLR 2024
in detail in Appendix B Some datasets in TUDatasets contain graphs with continuous attributes. We did not encode these attributes, since for these values lossy compression would usually be more appropriate, and the focus of this work is on lossless.
Table 2: For the TUDatasets, this table shows the significance of the discount term in eq. (14. With Rrdös-Rényi (ER) model, with edge probability adapted to each dataset, the percentage improvement (Discount) is the difference between treating the graph as ordered (Ordered ER) and using Shuffle coding to forget the order (Shuffle coding ER). Rates are measured in bits per edge.
Graph type
Ordered ER
Shuffle coding ER
Discount
Small molecules
2.11
1.14
46%
Bioinformatics
9.20
6.50
29%
Computer vision
6.63
4.49
32%
Social n
3.98
2.97
26%
Synthetic
5.66
2.99
47%
We also compared directly to Bouritsas et al. 2021) who used a more sophisticated neural method compress graphs (upper part of Table 3) They reported results for six of the datasets from the TUDatasets with vertex and edge attributes removed, and for two of the six they reported results which included vertex and edge attributes. Because PnC requires training, it was evaluated on a random test subset of each dataset, whereas shuffle coding was evaluated on entire datasets.
We found that for some types of graphs, such as the bioinformatics and social network graphs, performance was significantly improved by using Pólya urn (PU) preferential attachment model for ordered graphs introduced by Severo et al. (2023b). In this model, a sequence of edges is sampled, where the probability of edge being connected to a specific node is approximately proportional to the number of edges already connected to that node. Such a 'rich-get-richer' dynamic is plausibly present in the formation of many real-world graphs, explaining the urn model's good performance. treats edges as a set, and we were able to use an inner shuffle codec for sets to encode the edges, demonstrating the straightforward compositionality of shuffle coding. See Appendix D for details. The average initial bit cost per TU dataset in Table 3 is 0.01 bits per edge for both ER and PU, demonstrating good amortization.
As mentioned in Section 4, SZIP achieves a good rate for single graphs, whereas shuffle coding is only optimal for sequences of graphs. In the lower part of Table we compare the 'net rate', which is the increase in message length from shuffle coding the graphs, assuming some existing data is already encoded into the message. The fact that shuffle coding 'just works' with any statistical model for ordered graphs is major advantage of the method, as demonstrated by the fact that we were easily able to improve on the Erdös Prdōs-Rééyi results by swapping in a recently proposed model.
We report speeds in Appendix F Our implementation has not yet been optimized. One thing that will not be easy to speed up is canonical ordering, since for this we use the nauty and Traces libraries, which have already been heavily optimized. Fortunately, those calls are currently only 10 percent of the overall time, and we believe there is significant scope for optimization of the rest.
LIMITATIONS AND FUTURE WORK
Time complexity. Shuffle coding relies computing an object's canonical ordering and automor- phism group, for which no polynomial-tee time algorithm is known for graphs. In consequence, while nauty and Traces solve this problem efficiently for various graph classes, it is impractical in the worst case. This limitation can be overcome by approximating an object's canonical ordering, in- stead of calculating it exactly. This introduces trade-off between speed and compression rate in the method, and lowers runtime complexity to polynomial time. We leave a detailed description of that more sophisticated method to future work.
Initial bits. A limitation of the version of shuffle coding presented in this paper is that it only achieves an optimal rate for sequences; the rate 'discount' cannot be realized in the one-shot case,
6Three of the 24 social network datasets, REDDIT-BINARY, REDDIT-MULTT-SK REDDIT-MULTTI12K, were excluded because compression running time was ton long.
8

---

Published as a conference paper at ICLR 2024
Table Comparison between shuffle coding, with Erdös-Rényí (ER) and Pólya (PU) mod- els. and the best results obtained by PnC (Bouritsas et al.. (02T) and SZIP (Choi and Szpankowski, 2012) for each dataset. We also show the discount realized by shuffle coding. Each SZIP compar- ison is on single graph, and thus for shuffle coding report the optimal (ner) compression rate, that is the additional cost of compressing that graph assuming there is already some compressed data to append to. All measurements are in bits per edge.
Shuffle coding
Dataset
Discount
ER
PU
PnC
Small molecules
MUTAG
2.77
1.88
2.66
2.45:10.02
MUTAG (with attributes)
2.70
4.20
4.97
4.45
PTC_ME
2.90
2.00
2.53
2.97
PTC_ MR (with attributes)
2.87
4.88
5.40
6.49:10.5
ZINC_ful
3.11
1.82
2.63
1.99
Bioinformatics Social networks
PROTEINS
2.48
3.68
3.50
3.51++023
0.97
2.06
1,50
0.54
IMDB-MULTI
0.88
1.52
1.14
0.38
Shuffle coding (net)
Dataset
Discount
ER
PU
SZIP
SZIP
Airports (USAir97)
1.12
5.09
2.90
3.81
Protein interaction (YeastS)
3.55
6.84
5.70
7.05
Collaboration (geom)
3.45
8.30
4.41
5.28
Collaboration (Erdos)
7.80
7.00
4.37
5.08
Genetic interaction (homo)
3.97
8.22
6.77
8,49
Internet (as)
7.34
8.37
4.47
5.75
as explained in Section 3.2 However, it is possible to overcome this by interleaving encoding and decoding steps, as done in the 'bit-swap' method of Kingma al. (2019). Information can be eagerly encoded during the progressive decoding of the coset, reducing the initial bits needed by shuffle coding from (log n!) to (log n1). This generalization of the multiset coding method described by Severo et al. (2023a). We again defer detailed description to future work.
Models. Unlike PnC, we do not rely on compute-intenss intensive learning or hyperparameter tuning. Shuf- fle coding achieves late-offthee-tt compression rates when using simple models with minimal pa- rameters. There is currently active research on deep generative models for graphs, see Zhu et al. (202) for survey. We expect improved rates for shuffle coding when combined with such neural models.
CONCLUSION
significant proportion of the data which needs to be communicated and stored is fundamentally un- ordered. We have presented shuffle coding, the first general method which achieves optimal rate when compressing sequences of unordered objects. We have also implemented experiments which demonstrate the practical effectiveness of shuffle coding for compressing many kinds of graphs, in- cluding molecules and social network data. We look forward to future work applying the method to other forms of unordered data, and applying more sophisticated probabilistic generative models to gain improvements in compression rate.
ACKNOWLEDGMENTS
James Townsend acknowledges funding under the project Veni.212.111 financed by the Dutch Research Council (NWO). We thank Ashish Khisti for discussions and encouragement, and Heiko Zimmermann for feedback the paper.

---

Published as a conference paper at ICLR 2024
REFERENCES
Anders, Markus and Schweitzer, Pascal (2021). Parallel Computation of Combinatorial Symmetries. arXiv: 2108. 04590 24590 [cs]
Bergeron, François, Labelle, Gilbert, and Leroux, Pierre (1997). Combinatorial Species and Tree- like Structures. Trans. by Margaret Readdy. Encyclopedia of Mathematics and Its Applications. Cambridge.
Besta, Maciej and Hoefler, Torsten (2019). Survey and Taxonomy of Lossless Graph Compression and Space-tificient Graph Representations. arXiv: 1806. 01799 [cs, math]]
Bollobás, Béla (2001). Random Graphs. 2nd ed. Cambridge Studies in Advanced Mathematics. Cambridge.
Bouritsas, Giorgos, Loukas, Andreas, Karalias, Nikolaos, and Bronstein, Michael (2021). Partition and Code: Learning How to Compress Graphs. In Advances in Neural Information Processing Systems. Vol. 34, pp. 18603-18619.
Chen, Xiaohui, Han, Xu, Hu, Jiajing, Ruiz, Francisco, and Liu, Liping (2021). Order Matters: Prob- abilistic Modeling Node Sequence for Graph Generation. In Proceedings of the 38th Interna- tional Conference on Machine Learning, pp. 1630-1639
Choi, Yongwook and Szpankowski, Wojeiech (2012). Compression of Graphical Structures: Funda- mental Limits, Algorithms, and Experiments. In IEEE Transactions Information Theory 58.2,
pp. 620-638.
Duda, Jarek (2009). Asymmetric Numeral Systems. arXiv: 0902. 0271 [cs, math
Erdös, Paul and Rényi, Alfréd (1960). On the Evolution of Random Graphs. In Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5.1, pp. 17-60.
Holt, Derek F. (2005). Handbook Computational Group Theory. In collab. with Bettina Eick and Eamonn A. O' O'Brien. Discrete Mathematics and Its Applications. Boca Raton, Florida.
Joyal, André (1981). Une théorie combinatoire des séries formelles. In Advances in Mathematics
42.1, pp. 1-82.
Kingma, Friso, Abbeel, Pieter, and Ho, Jonathan (2019). Bit-Swap: Recursive Bits-Back Coding
for Lossless Compression with Hierarchical Latent Variables. Proceedings of the 36th Interna- lional Conference on Machine Learning, pp. 3408-3417.
Knuth, Donald E. (1981). The Art of Computer Programming. 2nd ed. Vol. 2. Reading, Mass. McKay, Brendan D. and Piperno, Adolfo (2014). Practical Graph Isomorphism, II. In Journal of Symbolic Computation 60, pp. 94-
Morris, Christopher, Kriege, Nils M., Bause, Franka, Kersting, Kristian, Mutzel, Petra, and Neu- mann, 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:
Schweitzer, Pascal and Wiebking, Daniel (2019). A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects. In Proceedings of the 5/ Annual ACM SIGACT Symposium Theory of Computing. STOC 2019. New York, NY, USA, pp. 1247-1258.
Scress, Ákos (2003). Permutation Group Algorithms. Cambridge Tracts in Mathematics 152. Cam- bridge.
Severo, Daniel, Townsend, James, Khisti, Ashish, Makhzani, Alireza, and Ullrich, Karen (2023a). Compressing Multisets with Large Alphabets. In IEEE Journal on Selected Areas in Information Theory.
Severo, Daniel, Townsend, James, Khisti, Ashish J., and Makhzani, Alireza (2023b). Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs. In Proceedings of the 40th Inter- national Conference on Machine Learning.
Sims, Charles (1970). Computational Methods in the Study of Permutation Groups. In Computa- tional Problems in Abstract Algebra. pp. 169-183.
Steinruecken, Christian (2014). Lossless Data Compression. University of Cambridge.
Steinruecken, Christian (2015). Compressing Sets and Multisets of Sequences. In IEEE Transactions
on Information Theory 61.3, pp. 1485-1490.
10

---

Published as a conference paper at ICLR 2024
Steinruecken, Christian (2016). Compressing Combinatorial Objects. In 2016 Data Compression Conference (DCC), pp. 389-396.
Townsend, James (2020). A Tutorial on the Range Variant of Asymmetric Numeral Systems. arXiv: 2001 09186 [cs, math, stat]
Townsend, James (2021). Lossless Compression with Latent Variable Models. arXiv: 2104. 10544
Townsend, James, Bird, Thomas, and Barber, David (2019). Practical Lossless Compression with Latent Variables Using Bits Back Coding. In International Conference Learning Representa- tions (ICLR).
Varshney, L.R. and Goyal, V.K. (2006). Toward Source Coding Theory for Sets. In Data Compres- sion Conference (DCC'06), pp. 13-22.
Yorgey, Brent (2014). Combinatorial Species and Labelled Structures. University of Pennsylvania. 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:24

---

Published as a conference paper at ICLR 2024
A GROUP ACTIONS, ORBITS AND STABILIZERS
This appendix gives the definitions of group actions, orbits and stabilizers as well as a statement and proof of the orbit-stabilizer theorem, which make use of in section 3 We use the shorthand H S G to mean that is subgroup of G, and for E G, we use the usual notation, g = {gh h E H) and Hg = {hg h H) for left and right cosets, respectively.
Definition A.1 (Group action). For a set X and a group G. group action, or simply action, is a binary operator
GG G x X + X which respects the structure of G in the following sense:
(16)
1. The identity element e E G neutral, that e G x = N.
2. The operator . respects composition. That is, for g, h E G.
9 G (h a = (gh) G 2.
(17)
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 a group G on a set X induces an equivalence relation ~g on X, defined by
G y if and only if there exists 9 E such that y= 9
(18)
We refer to the equivalence classes induced by ng as orbits, and use Orba(z:) to denote the orbit containing an element x E X. We use X/G to denote the set of orbits, so for each x E X, (xb X/G.
Definition A.3 (Stabilizer subgroup). For an action of a group G on a set X, for each x E X, the stabilizer
(taba = {g E G G
(19)
forms subgroup of G.
We make use of the orbit-stabilizer theorem in Section 3 Here we give a statement and brief proof of this well-known theorem.
Theorem A.1 (Orbit-stabilizer theorem). For an action of a finite group on a set X, for each X, the function 0g G X defined by
0g(g) = 9-2
(20)
induces bijection from the left cosets of Stabb to Orba(x)). This implies that the orbit (rba(x) finite and
|G]
[Orba(z)]
(21)
[Stabo
Proof. We show that Oy induces a well defined function on the left-cosets of Stabo(r), which we call f Specifically, we define
( (tab g x,
(22)
and show that By is injective and surjective.
To see that o, is well defined and injective, note that h E y Stabo(z)
> - h E Staba(a)
(23)
1 I
(24)
g x h.
(25)
using the definition Stabe. For surjectivity, we have
y E Orba(x)
= 3g G.s. y x
(26)
y 0g Stabbc(()
(27)
using the definition of Orbe-
12

---

Published as a conference paper at ICLR 2024
In Appendix C.2 it will be helpful to have explicit bijection between G and the Cartesian product (rba( x (t) This requires a way of selecting a canonical element from each left coset of Stabo in G. This is similar the canonical ordering of definition 2.4
Definition A.4 (Transversal), For group G with subgroup H I G, transversal the left cosets of H in G is a mapping t G + G such that
1. For all g E G. we have t(g) glt.
2. For all J.g E G. if f E gft, then ((J) = i(g).
Given such transversal, Lemma A.1. Let G be group acting on set X. for E X. we have a transversal t, of the left cosets of (taba(z) in G, then we can form an explicit bijection between G and Orba x (ta
setup the bijection mentioned above:
Proof. For y E G. let
(2(g) 9-
(28)
(1((g) = (z(g)) -
(29)
then Or (r). By condition in definition A.4 there exists h E Staba(x) such that t(g) gh, and in particular sg(g) h E Stabe a So there a well-defined function (x) = (o)
with ox G Orba(r) x Stabo
Then oz( (g(g). f-x g-2 x. and therefore f E (t) Condition 2 in definition A.4 implies that (z(() = L2 (g),, and since (g) (f) we have ff()) tz (g) g. so f g.
To see that du is injective, suppose that (f) d.(g)
The orbit-stabilize theorem implies that |G| = Orba (t))b)tab((()) and therefore if Φz is injec- tive it must also be bijective.
B CODECS FOR ORDERED OBJECTS
Codecs for strings and graphs can be composed from the primitive codecs introduced in section 2.2
def String(ps, length)
def ErdosRenyi (n, p):
def encode string):
def encode (m, g): assert len == for i in (rangee)) for j in reversed(range()))
assert len(string) == length
for in reversed(string): Categorical (ps) encode
return
e g[i][j]
m = Bernoulli(p) encode (m, e)
def (m):
return
string []]
for in range(length);
def de)ode g = []
m, c Categorical (ps) decode (m)
string (ppend(())
for i in range(n):
return m, str str(string)
inner = []
return Concode,, decode)
for j in range
m, inner. (ppend))))) appeedd(inner)
(ernoulli(p).decode
return (m, g)
return Codec(encode, decode)
Left: Codee for fixed-length strings implemented by applying Categorical codec to each char- acter. Right: Codec for graphs respecting an Erdós-Rényí distribution G(n,p), implemented by applying the Bernoulli codec each edge.
C A UNIFORM CODEC FOR COSETS OF PERMUTATION GROUP
Shuffle coding, as described in Section 3 requires that we can encode and decode left cosets S, of the automorphism group of permutable object. In this appendix we describe codec for cosets
13

---

Published as a conference paper at ICLR 2024
of arbitrary permutation group characterized by list of generators. We first describe the codec,
which we call Uni fnimfr Coset, on a high level and then in Appendices C.1 and C.2 we describe the two main components in more detail.
The optimal rate for a uniform coset codec is equal to the log of the number of cosets, that
Sn
log
log n! log H
(30)
This rate expression hints an encoding method: to encode coset, first decode choice of element of the coset (equivalent to decoding choice of element of H and then multiplying it by canonical element of the coset), and then encode that chosen element using a uniform codec on S,, Note that if the number of cosets is small we could simply encode the index of the coset directly, but in practice this is rarely feasible.
The following concrete implementation of left coset codec:
def CoiformLCooee(grvt def encode (m, s):
Effects on 1(m)):
s_canon coset_ coset_canonn(rD,, s)
m, Uni UniformPermmrppgrrp decode (m)
- llog|/|
5
s_canon
m = (n) encode u)
+ log(nn)
return m
def decode(m):
m, = Uni fnrmS(n) decode (m)
s_canon coset_canon canonnsnnonnsnrpp u)
= inv(s_canon) *
13
m Uniformperrmrpperp)) encode t)
return m, s_canon return Codec decode)
15
The codecs Uni formS and Uni UniformPermrrp are described in Appendix and Appendix C.2 re- spectively. UniformS(n (n) uniform codee over the symmetric group Sn and Uni UniformPernnt PrrmGr uniform codec over elements of a given permutation group, i.e., subgroup of S..
We use stabilizer chain, discussed in more detail in Appendix ally convenient representation of permutation group. A stabilizer chain allows computation of transversal which can be used canonize coset elements (line and line 11 the code above). Routines for constructing and working with stabilizer chains are standard in computa- tional group theory, and are implemented GAP system (https: / www. gap system. wwsttm..rg/).. scription of the algorithms. The method we use for coset_canon is implemented in the function SinimallEleeenntsttttttbhcc.
which is a computation-
SymPy (https: / /wwww wwwp:://www.ymmy.comm wympy.orgg// as well as the Holt (2005 Chapter 4) for theory and de-
in the GAP system.
C.1 UNIFORM CODEC FOR PERMUTATIONS IN THE SYMMETRIC GROUP
We use method for encoding and decoding permutations based on the Fisher- shuffle (Knuth,
1981 pp. 139-140). The following a Python implementation:
def UniformS(n):
def ss i, i):
3
si_old s[i]
s[i] = s[i]
5
s[j] si_old
7
def encode (m, s):
p = (range
9
p_inv list (range(n)))))
to_encode []
14

---

Published as a conference paper at ICLR 2024
for j in (range,, 1)):
12 i p_inv[x[j 1]] swap(p_inv, p[j 11, x[j - 1])
14
spap(p, i, j 1)
appendd)))
for j, i in zip(range(2, n 1), reversed(to_enccde)) m = Uniform(i) (ncodee(m)
return m
def decode
= (1))
23
for j in (rangeeeeaanneee n 1)):
i Uniform(j) (m)
ssap(s, i,
return
return Codec(encode decode)
The decoder closely resembles the usual Fisher- Yates sampling method, and the encoder has been carefully implemented to exactly invert this process. Both encoder and decoder have time complex- ity in (n).
C.2 UNIFORM CODEC FOR PERMUTATIONS IN AN ARBITRARY PERMUTATION GROUP
For coding permutations from arbitrary permutation group, which is a standard tool in computational group theory (see Holt (2005) and Seress (2003)):
the following construction,
Definition C.1 (Base, stabilizer chain). Let И I Sn, be permutation group, and B
(bo....bb--) bx-1) list of elements of [n]. Let Hu = H, and H₃ = Stab (bk-1) for 1...... ... K. If Hx is the trivial group containing only the identity, then we say that B buse for H, and the sequence of groups Ho.... H is a stabilizer chuin of H relative to B.
Bases and stabilizer chains are guaranteed to exist for all permutation groups, and can be efficiently computed using the Schreier-Sime algorithm (Sims, 1970). The algorithm also produces transver- sal for the left cosets of each Hg+1 in Hg for each O,..., K 1, in a form known as a Schreier tree (Holt, 2005).
.,, K 1, then by applying the orbit-stabilizer theorem recursively, we have H 1 [Oxl. which gives decomposition of the optimal rate that uniform codec on should achieve:
we define Os == Orbs, (b&), for le O,....
K
logl H
Σ
log Ox]-
(31)
Furthermore, by applying lemma A.I recursively, using the transversals produced by Schreier-Sims, we can construct an explicit bijection between and the Cartesian product [T Oş. We use this bijection, along with sequence of uniform codecs Op.... OK-1 for coding automorphisms at the optimal rate in eq. (3I. For further details refer to the implementation.
D PÓLYA URN MODEL DETAILS
We implemented Pólya urn models mostly as described in Severo al. (2023b), with few modi- fications. Differently the original implementation, apply shuffle coding to the list of edges, resulting in codec for the set edges.
We also disallow edge redraws and self-loops, leading to an improved rate, as shown in appendix G This change breaks length depends the initial message. Shuffle coding is compatible with such models. In this more general setting, the ordered log-liielioood term in the optimal rate (eq. [4] is replaced with a variational 'evidence lower bound" (ELBO). The discount term is unaffected. The derivations in the
leading to a 'stochastic' codec, meaning that the code
15

---

Published as a conference paper at ICLR 2024
main text are based the special case of exchangeable models, where log- likelihoods exact, for simplicity. They can be generalized with little effort and new insight.
E PARAMETER CODING DETAILS
All bit rates reported for our experiments include model parameters. Once per dataset, we code the following lists of natural numbers coding both the list length and the bit count [log m of the maximum element m with a 46-bit and 5-bit uniform codec respectively, as well as each element of the list with codec respecting log-uniform distribution in [0, [log m]]:
A list resulting from sorting the graphs' numbers of vertices, and applying run-length cod- ing, encoding run lengths and differences between consecutive numbers of vertices.
For datasets with vertex attributes: a list of all vertex attribute counts within a dataset.
For datasets with edge attributes: a list of edge attribute counts within a dataset.
For Erdös-Rényi models: list consisting of the following two numbers: the total number of edges in all graphs, and the number of vertex pairs that do not share an edge.
Coding these empirical count parameters allows coding the data according to maximum likelihood categorical distributions. Pólya urn models, we additionally code the edge count for each graph using uniform codec over [0, =n(n 1)] exploiting the fact that the vertex count is already coded as described above. For each dataset, we use single bit to code whether or not self-loops are present and adapt the codec accordingly.
F COMPRESSION SPEED
We show compression and decompression speeds of our experiments in Table 4 These speeds include time needed for gathering dataset statistics and parameter coding. The results show that for implementation, only small fraction of runtime is spent on finding automorphism groups and canonical orderings with nauty.
G MODEL ABLATIONS
We present results of additional ablation experiments on the PnC datasets in Table 5 We do an ablation that (unif. ER). There is a clear advantage to coding maximun-likelihood categorical parameters (ER), justifying it as the approach used throughout this paper. We also show the rates obtained by the original method proposed in Severo et al. (20235) (PU redr.), demonstrating a clear rate advantage of our approach disallowing edge redraws and self-loops (PU) in the model.
uniform distribution for vertex and edge attributes with Erdös-Rényi model
16

---

Published as a conference paper at ICLR 2024
Table Compression and decompression speeds in kilobytes per second (kB/s) of shuffle coding with the Sidōs-Rééy'' (ER) and Pólya um (PU) models, for all previously reported TU and SZIP datasets. We show SZIP compression speeds calculated from the runtimes reported in Choi and Szpankowski (2012) for comparison. All results are based on the ordered ER rate as the reference uncompressed size. All shuffle coding speeds are for single thread on a MacBook Pro 2018 with 2.7GHz Intel Core 17 CPU. We also report the share of time spent nauty calls that determine the canonical ordering and generators of the automorphism group of all graphs.
ER
PU
SZIP
Dataset
nauty
encode
decode
encode
decode
encode
TU by type Small molecules
15%
54
56
Bioinformatics
2%
Computer vision
3%
25
28
Social networks
<1%
0.440
0.467
Synthetic
7%
98
110
Small molecules
MUTAG
7%
115
122
MUTAG (with attributes)
16%
135
141
67
62
PTC_MR
8%
107
103
PTC_MR (with attributes)
18%
117
125
67
62
ZINC full
7%
105
105
50
Bioinformatics
PROTEINS
3%
88
30
30
Social networks
IMDE-BINARY
4%
17
18
8
8
IMDB-MULTI
3%
11
12
5
SZIP
Airports (USAir97)
1%
82
78
5
5
164
Protein interaction (YeastS)
8%
2.442
2.391
1.238
0.859
Collaboration (geom)
<1%
0.004
0.005
0.005
0.005
64
Collaboration (Erdos)
15%
0.025
0.025
0.024
0.024
Genetic interaction (homo)
7%
0.180
0.154
0.117
0.141
32
Internet (as)
13%
0.002
0.003
0.002
0.002
Table 5: Model ablations compared to PnC. All results are in bits per edge.
Shuffle coding
Dataset
unif. ER
ER
PU
PU redr.
PnC
Small molecules
MUTAG
1.88
2.66
2.81
2.45+0002
MUTAG (with attributes)
6.37
4.20
4.97
5.13
4,45
PTC_MR
2.00
2.53
2.74
2.97+t0.14
PTC_MR (with attributes)
8.04
4.88
5.40
5.61
6,49-10.54
ZINC_ful
1.82
2.63
2.75
1.99
Bioinformatics
PROTEINS
3.68
3.50
3.62
3.51-L0.23
Social networks
IMDB-BINARY
2.06
1.50
2.36
0.54
IMDB-MULTT
1.52
1.14
2.17
0.38
17


Reviews:
[{"review_id": "adPDOmu6u9", "reviewer": "Reviewer_gbs3", "summary": "This paper focuses on the problem of compressing unordered objects. It presents a general approach called “shuffle coding” to compress different data structures with bits-back coding. After introducing the background in Section2, including data structures and the problem definition of compressing unordered objects, the authors derive Lemma3.2 and then provide the pseudo algorithm for the proposed method. The key idea is to decode an ordering as part of an encode function. The experimental results demonstrate that the proposed shuffle coding could compress different data structures with better lossless compression performance, compared with ordered ER.", "questions": "As I am not entirely familiar with this field, the authors are welcome to direct my attention and address my concerns with more details provided. And I’ll gladly consider increasing my initial rating.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It seems to be meaningful to reduce compression cost by removing the order information in data structure. The proposed shuffle coding can get a discount in lossless compression of such data structures, as illustrated by Equation 14.", "weaknesses": "My major concern is about the significance of the problem studied in this paper: considering the complexity, will the proposed method have wide/potential applications in practice? For my side, it seems slightly intuitive to remove the order information so that we can reduce the coding cost when we compressing graph data. Is bits-back coding necessary in this scheme? These my concern may partially be attributed to my lack of expertise in the field of compressing graphs. In addition,  Appendix C describes the modifications compared with Daniel et al., 2023b, which is also an important baseline in this paper. But for a reader that is not very familiar with the area, appendix C may be hard to understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "N0pJVgYGhr", "reviewer": "Reviewer_aWcE", "summary": "In this work, the authors introduce _shuffle coding_, a method for compressing sequences of unordered objects based on bits-back coding. They provide an exposition of the group-theoretic fundamentals relevant for shuffle coding (Section 2 and Appendix A), define the desiderata required for an optimal-rate codec for unordered sequences (Section 3) and present shuffle coding, an algorithm that fulfils these desiderata (Section 3.1). They apply shuffle coding to unordered data structures (specifically graphs), showing strong performance compared to PnC and SZIP (Section 5).", "questions": "Below are some questions for the authors and suggestions that I think could improve the paper.\n\n## Questions\n\n__Clarification on the discount factors for Table 3:__\nThe ER and PU models are specific probabilistic models for graphs and, as the authors explain, they can be swapped in with any other exchangeable model of graphs.\nTherefore, while it is important to report the overall communication cost in the experiments, an equally important (in my view) quantity to report is the rate discount afforded by shuffle coding.\nWhat are the discounts corresponding to the results in table 3?\nPerhaps the authors can report these as an extra column, since the discount is a function of the graph alone and not the modelling distribution $P.$\n\n\n__Extending the framework with approximate isomorphism solutions:__\nThe authors claim that while no known polynomial-time solution for solving the exact graph isomorphism problem is known\n\n> this limitation can be overcome by approximating an object’s canonical ordering, instead of calculating it exactly. This introduces a trade-off between speed and compression rate in the method, and lowers runtime complexity to polynomial time.\n\nCan the authors comment on the tradeoff between the speed and compression rate of this modified method, here and / or the main text?\n\n\n## Suggestions\n\n__Definition 2.5:__\nI think that definition 2.5 is not totally accurate and / or could be improved.\nPresumably, what the authors mean by \"inverse functions\" is that $\\texttt{decode}$ is the inverse function of $\\texttt{encode}.$\nIn that case the $\\texttt{decode}$ function isn't really needed and / or can be defined as $\\texttt{decode} = \\texttt{encode}^{-1}.$\nAlso, the statement \"with respect to $P$\" does not seem to make sense on its own.\nI think clearer statement is to say that \n\n> an optimal codec for $P$ is an invertible function $\\texttt{encode} : M \\times X \\to M$, which is optimal with respect to $P,$ in the sense that for any [...].\n\nMore importantly however, in shuffle coding, the $\\texttt{encode}$ function is _not invertible_, because for $f \\in \\mathcal{F},$ applying $\\texttt{decode}(\\texttt{encode}(M, f))$ returns the message $M$ together with the canonical representation $\\bar{f}$ rather than $f$ itself (see for example the function signature and return statements in the code listing in Section 3.1).\nWhile this is a technicality that does not seem affect the validity of the algorithm, I think the authors should modify their definition and / or exposition to account for this.\n\n__Framing of definition 2.5:__\nI think definition 2.5 and the paragraph under it could be framed better.\nIn particular, the authors define optimal codecs and explain that \"definition 2.5 captures the abstract properties of codecs based on the range variant of asymmetric numeral systems.\"\nI think a clearer approach would be to say up-front that their plan is to set up a method that gets those bits which correspond to permutations of the graph in question back.\nThis in turn necessitates using a last-in-first-out codec, such as (r)ANS, and that definition 2.5 specifies \"Optimal last-in-first-out codecs\", rather than \"Optimal codecs\".\n\n__Initial bit overhead statement:__\nThe authors argue that the constant bit overhead incurred by bits-back \"exists for all entropy coding methods.\"\nWhile all entropy coding methods have a constant overhead that is amortised as more and more data are compressed, typical methods such as Arithmetic Coding (AC), have constant overheads of the order of a couple of bits.\nThis is far smaller than the claimed overhead of \"at most 64 bits\" of bits-back for shuffle coding.\nI think the authors' phrasing somewhat misrepresents the overhead of other entropy coding methods.\nA more accurate statement would be welcome here, such as: \"As in other entropy coding methods, which invariably have similar (though typically smaller) constant overheads, the constant 'initial bit cost' of bits-back is amortised as more data are compressed.\"\n\n__All units in bits?__\nAre all reported rates, including for example Table 1, in bits?\nIf so, it would be good to add a statement up front, early in the paper, that specifies this.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a few key strengths which, in my view, are as follows:\n\n__Elegant unified framework:__\nThis paper provides an unified theoretical framework for compressing unordered objects, such as multisets and graphs.\nThis approach is based on the elegant idea that the order of the parts of an object does not matter, one can reduce the cost of communicating the object by getting a certain number of bits, i.e. the bits corresponding to a particular ordering of the parts, back.\nThis generality is appealing because one does not have to devise specialised method for each different type of unstructured object.\nHowever, it should be noted that this framework assumes access to a \"canonicalisation\" function, which determines a canonical representation  as well as the automorphism group of the object (e.g. graph) in question (also see weaknesses section below).\n\n__Strong compression performance:__\nThe authors demonstrate that shuffle coding achieves strong compression rates in practice.\nIn particular, shuffle coding outperforms SZIP and PnC on a range of graph datasets.\nThis is an encouraging result because, while the proposed method is asymptotically optimal, it also involves a non-trivial overhead (which is amortised as more data are compressed).\nTherefore it is good that despite this cost, shuffle coding seems to perform well in practice.\n\n__Well written paper:__\nThe paper is generally clearly written and well motivated.\nThe authors have made an effort to discuss the limitations of their work, specifically about the time complexity and initial rate overheads induced by their method.\nI appreciated the illustrations and pseudocode listings in the main text, which helped understand their method.", "weaknesses": "The paper's main weaknesses, in my view, revolve around the practical applicability of shuffle coding:\n\n__Large runtime complexity:__\nAs the authors note, applying shuffle coding to a graph requires solving a graph isomorphism problem, for which no polynomial-time algorithm is known.\nThis can be a significant hurdle when coding larger graphs.\nThe authors brought up this issue in the paper, and suggested that approximately solving the isomorphism problem is a promising way to scale the method.\nHowever, in its current form, the method does not scale to larger graphs.\nFurther, it is unclear what the tradeoff between the communication rate and computational complexity of the method would be, if one were to use an approximate scheme instead.\n\n__Initial bit overhead:__\nDue to the requirement of initial bits, shuffle coding introduces a communication overhead to the transmitted message.\nThis can be significant in the one-shot or few-shot case, making the method from compressing small sequences of messages.\nI think the authors should specify the amount of extra bits used in the experiments (see Table 3) in the main text.\n\n__Contribution as a general solution seems somewhat exaggerated:__ \nWhile the shuffle coding approach is general from a theoretical point of view, it requires access to a \"canonicalisation\" function.\nThe authors focus on graphs, for which existing libraries offering this functionality exist.\nFor other permutable classes, the authors argue that one can \"embed objects into graphs in such a way that the structure is preserved and the canonization remains valid.\"\nHowever, it is unclear whether, for example, this embedding might affect the compression rate, or how difficult it is to construct such an embedding.\nIn light of this latter point, the statement that the authors' \"implementation can easily be adapted to different data types\" in the abstract may be regarded as exaggerated (if for example coming up with an algorithm that constructs such graph embeddings is challenging, or if the computational / memory complexity of such an algorithm is large).\nA more measured statement in the appendix and / or positioning of the main text might be beneficial in this regard.\n\n__Summary:__\nIn conclusion, while I find the paper to be well-motivated and elegant, I think the practical applicability of shuffle coding may be limited due to runtime issues, as well as issues pertaining to the embedding of other kinds of permuted classes on graphs, and the initial bit overhead.\nTherefore I have recommended a moderately positive score for the paper, but I am willing to adjust my score if the authors address my points of concern raised above, and the questions and recommendations made below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gDgZgb4zvI", "reviewer": "Reviewer_NBHy", "summary": "## Summary\n* This paper propose shuffle coding, a BB-ANS approach towards lossless compression of unordered sets. The scenario described by the paper seems to related to the Birkhoff Polytope in variational inference of permutation [Linderman 2017, Reparameterizing the Birkhoff Polytope for Variational Permutation Inference], where each permutation's likelihood is the same. The authors demonstrate the effectiveness of their approach on various datasets.", "questions": "## Questions\n* For practically large structure, what is the computational cost for finding and sampling from the isomorphism class $\\hat{f}$? For practical codec, the metrics such as latency and throughput should also be discussed.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "## Strength\n* The unordered set / graph compression problem is of good practical value. The proposed approach is a neat extension of bits-back coding. It is simple, novel and works well.", "weaknesses": "## Weakness\n* As the authors have discussed, the current initial bits required is quite large. This hinders the practical application of the proposed approach to one-shot object coding. Though it is still possible to apply this approach to a dataset to amortize the initial bits. An alternative to the bit-swap approach mentioned by authors is correlation communication [Harsha 2010, The Communication Complexity of Correlation] [Li 2018, Strong Functional Representation Lemma and Applications to Coding Theorems] [Theis 2021, Algorithms for the Communication of Samples], which has extra overhead of approximately $\\log \\log N!$, but does not require any initial bits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "BTx1TMeRyU", "reviewer": "Reviewer_72sp", "summary": "This paper proposes a general method called shuffle coding for compressing sequences of unordered objects using bits-back coding.    \nThe proposed shuffle coding is applicable to multisets, graphs, hypergraphs etc.    \nSOTA compression rate is achieved on several graph datasets including molecular data.", "questions": "Definition 2.5 is described in a very concise way. It is not clear why the definition is specifically connected with rANS. I think is also applies to arithmetic coding.    \n\nIt is not clear how eq9 is related to the real bitrate. In this definition, the data is compressed in an instance-wise manner and l(m) is the initial bit cost which can be amortized later if we compress more instances. However, log(1/p(x)), which is defined as the rate of the codec, is an averaged value averaging over the input symbol number. I do not understand why l(m) can be added with log(1\\p(x)).  \n\nDefinition 2.3 (Automorphism group) is actually the difinition of stabilizer. If I remember correctly, the concept of Automorphism in group theory is connected with operation by conjugation. Did I miss anything?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem of compressing unordered data optimally by considering the storing order as redundancy is novel to me.    \nThe paper is a solid contribution with solid theoretical foundations. The mathematical structures from group theory are closely connected with the target unordered data.      \nThe idea of decoding the ordering as part of an encode function in the spirits of bits-back coding is very interesting.    \nThe background and proposed methods are clearly explained and relatively easy to follow.    \nExperiments are conducted on server different datasets, and achieve sota compression rate.   \nLimitations of the proposed method is properly discussed.", "weaknesses": "One major concern is the practical value of compressing those unordered data. Compared with images or videos, it seems to me the data volume of those unordered date is very limited. However, I still appreciate the technical contribution of this paper. \n\nCurrently the numbers in Table 4 is relatively not easy to understand. It would be better to report speed as GB/s or MB/s and compare this with previous methods, so that readers can better feel the efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)