Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs
This addresses the challenge of efficient graph compression for large-scale network data, though it appears incremental as it builds on bits-back coding and Pólya's Urn models.
The paper tackles the problem of compressing large labeled graphs by introducing Random Edge Coding, a one-shot method that achieves competitive compression performance on real-world network datasets and scales to graphs with millions of nodes and edges.
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.