One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding

Daniel Severo, James Townsend, Ashish J Khisti, Alireza Makhzani
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:30633-30645, 2023.

Abstract

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ólya’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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-severo23a, title = {One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding}, author = {Severo, Daniel and Townsend, James and Khisti, Ashish J and Makhzani, Alireza}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {30633--30645}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/severo23a/severo23a.pdf}, url = {https://proceedings.mlr.press/v202/severo23a.html}, abstract = {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ólya’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.} }
Endnote
%0 Conference Paper %T One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding %A Daniel Severo %A James Townsend %A Ashish J Khisti %A Alireza Makhzani %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-severo23a %I PMLR %P 30633--30645 %U https://proceedings.mlr.press/v202/severo23a.html %V 202 %X 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ólya’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.
APA
Severo, D., Townsend, J., Khisti, A.J. & Makhzani, A.. (2023). One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:30633-30645 Available from https://proceedings.mlr.press/v202/severo23a.html.

Related Material