One-Shot Compression of Large Edge-Exchangeable Graphs using Bits-Back Coding
Authors: Daniel Severo, James Townsend, Ashish J Khisti, Alireza Makhzani
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we showcase the optimality of REC on large graphs representing real-world networks. We entropy code with REC using P olya s Urn (PU) model and compare the performance to state-of-the-art compression algorithms tailored to network compression. We report the average number of bits required to represent an edge in the graph (i.e., bits-per-edge) as is common in the literature. |
| Researcher Affiliation | Academia | 1Department of Electrical and Computer Engineering, University of Toronto 2Vector Institute for Artificial Inteligence 3Amsterdam Machine Learning Lab (AMLab), University of Amsterdam. |
| Pseudocode | Yes | Algorithm 1 Naive Random Edge Encoder and Algorithm 2 Random Edge Encoder |
| Open Source Code | Yes | Code implementing Random Edge Coding, P olya s Urn model, and experiments are available at https:// github.com/dsevero/Random-Edge-Coding. |
| Open Datasets | Yes | We used datasets containing simple network graphs with small-world statistics (see Section 4.1) such as You Tube, Four Square, Gowalla, and Digg (Rossi & Ahmed, 2015)... Skitter and DBLP networks (Leskovec & Krevl, 2014) |
| Dataset Splits | No | The paper describes compressing the entire graph in a one-shot manner and does not specify traditional train/validation/test dataset splits. |
| Hardware Specification | No | The paper does not explicitly describe the hardware used for running experiments, such as specific GPU or CPU models. |
| Software Dependencies | No | We use the ANS implementation available in Craystack (Townsend et al., 2020; 2021). However, specific version numbers for Craystack or other software dependencies are not provided. |
| Experiment Setup | No | The paper describes the general process of Random Edge Coding and Polya's Urn model, which is parameter-free, but does not provide specific experimental setup details like hyperparameters or training configurations for a learning model. |