Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs
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.
Code (1)
Similar Papers 제목 키워드 기반
Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters
While deep neural networks are a highly successful model class, their large memory footprint puts considerable strain on energy consumption, communication bandwidth, and storage requirements. Consequently, model size red…
Neural Network CompressionQuantizationImproving Lossless Compression Rates via Monte Carlo Bits-Back Coding
Latent variable models have been successfully applied in lossless compression with the bits-back coding algorithm. However, bits-back suffers from an increase in the bitrate equal to the KL divergence between the approxi…
Data CompressionEncoding Explanatory Knowledge for Zero-shot Science Question Answering
This paper describes N-XKT (Neural encoding based on eXplanatory Knowledge Transfer), a novel method for the automatic transfer of explanatory knowledge through neural encoding mechanisms. We demonstrate that N-XKT is ab…
Question AnsweringScience Question AnsweringTransfer LearningZero-shot GeneralizationBit-aware Randomized Response for Local Differential Privacy in Federated Learning
In this paper, we develop BitRand, a bit-aware randomized response algorithm, to preserve local differential privacy (LDP) in federated learning (FL). We encode embedded features extracted from clients' local data into b…
Federated Learningimage-classificationImage ClassificationEnd-to-End Image Compression with Segmentation Guided Dual Coding for Wind Turbines
Transferring large volumes of high-resolution images during wind turbine inspections introduces a bottleneck in assessing and detecting severe defects. Efficient coding must preserve high fidelity in blade regions while …
Image Compression