We present a one-shot method for compressing large labeled graphs called
Random Edge Coding. When paired with a parameter-free model based on P\'olya's
Urn, the worst-case computational and memory complexities scale quasi-linearly
and linearly with the number of observed edges, making it efficient on sparse
graphs, and requires only integer arithmetic. Key to our method is bits-back
coding, which is used to sample edges and vertices without replacement from the
edge-list in a way that preserves the structure of the graph. Optimality is
proven under a class of random graph models that are invariant to permutations
of the edges and of vertices within an edge. Experiments indicate Random Edge
Coding can achieve competitive compression performance on real-world network
datasets and scales to graphs with millions of nodes and edges.

通过基于 Pólya 的 urn 模型的无参数模型，利用随机边编码 (Random Edge Coding) 方法进行图压缩，依靠位后编码 (bits-back coding) 从边列表中无需替换抽样边和节点。实验证明，Random Edge Coding 可在现实世界的网络数据集上达到竞争性压缩性能，并可扩展到具有数百万节点和边的图。

随机边缘编码：大型带标签图的一次性比特回传编码

Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs

We consider the problem of lossy image compression with deep latent variable
models. State-of-the-art methods build on hierarchical variational autoencoders
(VAEs) and learn inference networks to predict a compressible latent
representation of each data point. Drawing on the variational inference
perspective on compression, we identify three approximation gaps which limit
performance in the conventional approach: an amortization gap, a discretization
gap, and a marginalization gap. We propose remedies for each of these three
limitations based on ideas related to iterative inference, stochastic annealing
for discrete optimization, and bits-back coding, resulting in the first
application of bits-back coding to lossy compression. In our experiments, which
include extensive baseline comparisons and ablation studies, we achieve new
state-of-the-art performance on lossy image compression using an established
VAE architecture, by changing only the inference method.

本文研究了利用深度潜变量模型进行有损图像压缩的问题，并提出了迭代推理、离散优化的随机退火以及 bits-back 编码等方法，取得了新的最优表现。