Leiden+LLP graph compression method outperforms Zuckerli on all 28 datasets

Reference-based graph compression encodes each vertex's neighbor list as differences from a nearby encoded list, but the interaction between vertex ordering and the encoding pipeline is rarely measured. Jimmy Dubuisson's new study proposes a two-stage community-aware ordering: first, LLP (Layered Label Propagation) seeds labels globally; then Leiden detects communities; finally, a second LLP pass reorders each community internally. This Leiden+LLP ordering is tested with BVGraph and three custom encoders (BG, CS, CG) that each pick the cheapest of up to 28 candidate decompositions per vertex.

On graphs with poor initial ordering (SNAP-style), reordering with Leiden+LLP saves 0.9 to 4.6 bits per edge across all encoders. On web crawls with URL-based ordering, BG and CS still benefit, while residual-sensitive configurations regress. The approach beats the strongest published baselines (Zuckerli, BV-HC/default) on all seven datasets in every whole-graph and random-access comparison — 28/28 cells, with improvements of +0.3% to +35% over Zuckerli. Critically, the ordering-level gain consistently surpasses the encoder-level gain. All algorithms, the ordering pipeline, and generators are released as the Adjacently Julia library for reproducibility.