Entropy Coding of Unordered Data Structures

We thank reviewer 72sp for their review.

Currently 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.

We fully agree with the reviewer, and updated Table 4 to show speeds in the more standard unit of kB/s. While we did not find information on speeds for PnC, we added a column for SZIP compression speeds for comparison (no decompression speeds were reported).

---

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.

Our method requires stack-like (LIFO) codecs, such as those based on the range variant of asymmetric numeral systems (rANS), to recover bits corresponding to the redundant order using bits-back. Queue-like (FIFO) codes such as arithmetic coding cannot be directly used to implement bits-back coding, see Townsend et al. (2019) for more detail. This was previously not explicitly stated. We revised section 2.2, including definition 2.5, to clarify this.

---

It 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)).

If $m$ is the initial message, the left-hand side $l(\text{encode}(m, x))$ of eq. 9 is the real bit rate for a specific input $x$, measuring how many bits are needed to store $x$ without encoding any other information. $\log(1/\text{p}(x))$ is the ideal (amortized) bit rate for that specific input $x$, bounding the real bit rate from below. This is not an average over all possible inputs $x$. Note that in general, $m$ can contain previously compressed objects, and $l(m)$ is therefore not necessarily just the initial bit cost.

---

Definition 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?

That is all absolutely correct. The automorphism group of $f$ is the stabilizer subgroup of $f$ under the action of $\mathcal{S}_n$, as mentioned right after definition 2.3. The concepts of automorphism and conjugation are indeed closely related in group theory. For example, the function $f_h(g) = h^{-1}gh$ that conjugates any element $g$ of a group $G$ by a fixed element $h$ of $G$ is an automorphism of $G$ (called an inner automorphism).

We thank reviewer NBHy for taking the time to review our paper.

The scenario described by the paper seems to related to the Birkhoff Polytope in variational inference of permutation

Indeed, as the reviewer pointed out, our method is related to [Linderman 2017], where they reparameterize the Birkhoff Polytope to perform variational inference over permutation matrices. The vertices of the n-dimensional Birkhoff Polytope represent permutations over n elements. Our decoding algorithm can be seen as performing inference of the permutation applied to the input via canonicalization. Relaxing this inference to the inner hull of the Birkhoff Polytope, as done in [Linderman 2017], could be a way to perform lossy compression of combinatorial objects.

---

An alternative to the bit-swap approach mentioned by authors is correlation communication

While correlation communication methods could theoretically be an alternative to the future work of interleaving, these methods have computational complexity which scale exponentially with the entropy of the source, making them impractical. However, the reviewer is correct that these methods could in theory be used to avoid the initial bits problem, if we disregard computational complexity.

These methods relate to bits-back coding in the following way. Consider the source $X$ and another random variable $Y$ from which we can recover $X$ deterministically, i.e., $X = f(Y)$ for some function $f$. Note this implies that $H(X|Y) = 0$. As a concrete example from BB-ANS, $Y = (Z, X)$ where $Z$ is the latent variable of the VAE. Then, bits-back coding implements rate $R = H(Y) - H(Y|X) = I(X; Y) = H(X) - H(X|Y) = H(X),$ where $-H(Y|X)$ is the savings from the bits-back step.

Correlation communication methods can be used to communicate a sample Y | X, achieving a rate of $R + log(R+1) + 5$ via the Poisson Functional Representation Lemma (in this case, the discrete version which falls back onto the exponential races) [Li & El Gammal 2017], and X can then be recovered from that sample. Unfortunately, as mentioned, the computational complexity would be much larger than our method.

Bits-back can be viewed as an extremely efficient algorithm for “deterministic” correlation communication (i.e., when $X = f(Y)$ for some $f$).

---

For practically large structure, what is the computational cost for finding and sampling from the isomorphism class $\tilde{f}$?

We provided relative timings for nauty, the library we used to find the canonical labeling and automorphism group (these are the computational bottlenecks for sampling from the isomorphism class), in Appendix E. As mentioned in the paper, no polynomial-time algorithm for the graph isomorphism is known, but nauty and Traces solve this problem efficiently for various graph classes. Thorough benchmarks of nauty and traces on different graph types and sizes can be found at https://pallini.di.uniroma1.it/.

---

For practical codec, the metrics such as latency and throughput should also be discussed.

We have updated Appendix E to now report compression throughput. We believe that latency is more appropriate for streaming applications, such as video decoding. We would envision our codec being used in a non-streaming setting, where a whole file would be downloaded and then decompressed.

We thank reviewer aWcE for their thoughtful, thorough and constructive review.

Weaknesses

Large runtime complexity: We address this in our overall response.

Initial bit overhead: 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. We added this result to section 5.

Clarification of the discount factors for Table 3: We added a column to report the discounts for all datasets in Table 3. As in Table 2, the discounts are very significant for compression performance.

Questions

Extending the framework with approximate isomorphism solutions: The tradeoff between rate and performance of the approximate version of shuffle coding is promising: Preliminary experiments show that on SZIP graphs, we can achieve speedups of multiple orders of magnitude for a few-percent increase in compression rate compared to optimal-rate shuffle coding, i. e. a 1000x speedup for a 4% rate increase on the “geom” dataset. We implemented a version of shuffle coding that has pseudo-linear runtime and completes on graphs with more than 10 million edges. The approximate method saves the “easy-to-find” redundant bits, leaving the “hard” bits out that cause most of the computational complexity when calculating the canonical ordering in nauty and traces. On all datasets we tested, there seems to be a favorable distribution between these, i. e. many easy bits vs. few hard bits. Characterizing and predicting this tradeoff would be an interesting avenue for future work.

Contribution as a general solution seems somewhat exaggerated: We updated section 2.1.1 to clarify that our method critically depends on the availability of function to retrieve a canonical ordering (as well as a set of generators of the automorphism group) for elements of the permutable class. As mentioned in Anders and Schweitzer (2021), embedding into vertex-colored graphs, and then running nauty/traces, is the standard technique for computing the automorphism group (and canonization) of other objects. It would be great though to prove that this is always possible, and to have a general embedding method. We actually used an embedding of edge-colored graphs into vertex-colored graphs in order to canonize and compress graphs with edge attributes (which are not directly supported by nauty/traces) for our experiments. We have updated the paper to mention that we did this.

Suggestions

We agree with all of the reviewer’s suggestions and have implemented them in our updated paper version. This includes a simplified and better-framed definition 2.5, an updated statement regarding the initial bit overhead of rANS, and a missing clarification regarding units (all results are indeed in bits, this information was missing for Table 5).

Invertibility of encode function. The encode function for shuffle coding is invertible because it takes an unordered object of type $X=\tilde{F}$ (not $F$), so the codec signature is $M×\tilde{F}→M$. We updated section 3.1 to mention this explicitly. We merely use an ordered object with arbitrary order to represent the unordered object in our implementation, as described in section 3.1. Their order has no meaning in the sense that equality of unordered objects is implemented by comparing canonized versions of their ordered representations. In practice, we use a wrapper data type called Unordered to define equality in this way (i. e. Unordered(‘abc’) == Unordered(‘bca’)), so that the universal invertibility property c.decode(c.encode(m, x)) == (m, x) of codecs is upheld. This is omitted in the listing of section 3.1 for simplicity.

We thank reviewer gbs3 for the time to review our paper.

We addressed the concern regarding runtime complexity in our overall response.

It is intractable to directly compress unordered objects without bits-back at the optimal rate. The role of bits-back coding is to enable us to convert the problem of compressing unordered objects into a problem of compressing ordered objects, where we can apply common sequential methods such as the ones shown in Listing 1 in the paper.

Appendix C describes details of an ordered graph model that we plug into shuffle coding for our experiments. It is not a baseline for shuffle coding, since we are concerned with unordered graph compression. It is not core to our method either since shuffle coding can be combined with any ordered graph codec. We merely aimed to demonstrate that a few-parameter ordered model/codec can lead to competitive results in combination with shuffle coding, and Severo et al. 2023b is a good fit for that purpose. The minor modifications lead to rate improvements as shown in Appendix F, but are not core to our method.