Community-Aware Vertex Ordering for Reference-Based Graph Compression: A Cross-Encoder Empirical Study

Jul 16, 2026

Reference-based graph compression stores each vertex’s neighbor list as differences from a nearby, already-encoded list. The dominant BVGraph framework fixes a single encoding pipeline and depends on a separately chosen vertex ordering, typically URL-lexicographic or Layered Label Propagation (llp), whose interaction is rarely quantified. This study proposes a Leiden+llp two-stage ordering and evaluates four encoders (BVGraph plus three proposed) across seven datasets, showing ordering improvements translate into consistent bits-per-edge savings.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages33

Reading Time1 h 23 min

Introduction

Motivation

The Role of Vertex Ordering

arXiv :2605 .2 15 10v2 [ cs . SI] 13 Jul 2026 Community-Aware Vertex Ordering for Reference-Based Graph Compression: ACross-Encoder Empirical Study JIMMY DUBUISSON, Vantino, Switzerland Reference-based graph compression stores each vertex’s neighbor list as a set of differences from a nearby, already-encoded list. The dominant tool, WebGraph’s BVGraph, fixes a single encoding pipeline and relies on a separately chosen vertex ordering—typically URL-lexicographic or Layered Label Propagation (llp) . How the two choices interact is rarely measured. We propose a two-stage Leiden+llp vertex ordering: global llp seeds the labels, Leiden detects communities on top of them, and a final llp pass reorders each community internally. We measure how this ordering interacts with reference-based compression, using BVGraph and three encoders we contribute—BG, CS, and CG—which pick, for every vertex, the cheapest of up to 28 candidate decompositions. On graphs whose initial vertex order is poor, reordering with Leiden+llp improves compression for every encoder we measured. It saves roughly 0.9 to 4.6 bits per edge (bpe) over the original ordering on the SNAP-style graphs delivered in vertex-ID order (Table 4) . The size of that gain barely depends on which encoder runs afterward: on four of five weakly ordered datasets, the four encoders agree on the Leiden+llp-vs-plain-llp gain within roughly ±0 .04 bpe. The exception is EAT. There, our three larger-window encoders still agree within ±0 .008 bpe, but BVGraph at its default reference window (􀁆=7) shows a slightly negative residual gain—a window-size effect, not a refutation of the pattern. On URL-ordered web crawls, where the distributed ordering already encodes locality, BG and CS still benefit from reordering, while the residual-sensitive configurations—BVGraph default, BV-HC, and CG where it relies on the crawl’s community contiguity—regress. The transfer holds across two encoder generations (a Fibonacci-coded backend and a fully context-adaptive range-coded one) and under three independent ordering seeds. With every structural bit entropy-coded, the best of our three encoders beats the strongest published baseline in each regime (Zuckerli, and the stronger of BV-HC / BVGraph default) on all seven datasets, in every whole-graph and random-access comparison we ran—28/28 cells, +0 .3 to +35% over Zuckerli. The encoder-level gain remains consistently smaller than the ordering-level gain on weakly ordered datasets. The encoders share a self-delimiting bitstream with low-overhead random access, which we present as a practical implementation choice rather than a primary contribution. All algorithms, the ordering pipeline, and generators are released as the Adjacently Julia library. Additional Key Words and Phrases: graph compression, vertex ordering, community detection, Leiden, Layered Label Propagation, reference encoding, bits per edge, algorithm engineering, WebGraph 1 Introduction 1.1 Motivation Large directed graphs—web crawls, social networks, citation indices, knowledge graphs—are routinely too large to store as uncompressed adjacency lists. Yet they must stay accessible to in-memory analytics. A graph compressor therefore stores each vertex’s list of out-neighbors in as few bits as possible while keeping the lists cheap to decode. Quality is measured in bits per edge (bpe): the compressed size divided by the number of edges. At this scale small differences matter. On a crawl with two billion edges, saving one bpe saves 250 MB of memory. The workhorse technique of the field is reference encoding. Rather than writing every neighbor list from scratch, the encoder copies most of a list from a nearby, already-encoded vertex and spells out only the differences. This works because web-style graphs, once sensibly numbered, have two structural properties. The first is locality: edges tend to connect vertices placed nearby in the chosen vertex order, so the numbers written are smal

FAQs

What is reference-based graph compression in this work?

It encodes a vertex’s neighbor list by copying most of a nearby, already-encoded vertex’s list and writing only the differences. Efficiency depends on good vertex numbering and reuse opportunities.

Why does vertex ordering matter for compressed size?

Ordering changes the integer labels assigned to vertices, which alters gap sizes and copy opportunities. Since locality and similarity are ordering-driven properties, the same graph can compress very differently under different orderings.

What ordering strategy does the paper propose and what is its impact?

It proposes a two-stage Leiden+llp approach: a global llp seeds labels, Leiden detects communities, then a final llp pass reorders within each community. On weak initial orderings, reordering improves compression across all measured encoders.

Jul 16, 2026

Upload by Emma Wilson