Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs

Author name not available (Why is that?)

Publication date: 16 May 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'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.

Has companion code repository: https://github.com/dsevero/random-edge-coding

This page was built for publication: Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436859)