Skip to yearly menu bar Skip to main content


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

Daniel Severo · James Townsend · Ashish Khisti · Alireza Makhzani

Exhibit Hall 1 #713


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.

Chat is not available.