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

Jimmy Dubuisson

cs.SIMay 13, 2026

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

Authors: Jimmy Dubuisson

Organizations: Vantino, Switzerland

Abstract

Reference-based graph compression encodes each vertex's neighbor list as differences from a nearby encoded list. WebGraph's BVGraph fixes a single encoding pipeline and relies on a separately chosen vertex ordering -- typically URL-lexicographic or Layered Label Propagation (LLP). Their interaction is rarely measured. We propose a two-stage Leiden+LLP ordering: global LLP seeds labels, Leiden detects communities, and a final LLP pass reorders each community internally. We study how it interacts with reference-based compression, using BVGraph and three encoders we contribute -- BG, CS, and CG -- each picking, per vertex, the cheapest of up to 28 candidate decompositions. On graphs with poor initial vertex order, reordering with Leiden+LLP improves compression for every encoder measured, saving 0.9 to 4.6 bits per edge (bpe) over the original order on SNAP-style graphs delivered in vertex-ID order. The gain barely depends on the encoder: on four of five weakly ordered datasets, the four encoders agree on the Leiden+LLP-vs-plain-LLP gain within about +/- 0.04 bpe. On URL-ordered web crawls, where the ordering already encodes locality, BG and CS still benefit, while residual-sensitive configurations (BVGraph default, BV-HC, and CG relying on community contiguity) regress. The transfer holds across two encoder generations (Fibonacci-coded and fully context-adaptive range-coded) and three 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 -- 28/28 cells, +0.3 to +35% over Zuckerli -- with the encoder-level gain consistently smaller than the ordering-level gain. All algorithms, the ordering pipeline, and generators are released as the Adjacently Julia library.

Explore similar work

Jul 25, 2026cs.LG

Does Graph Compression Preserve Signal Propagation?

Graph compression reduces the computational cost of graph learning, but its effect on signal propagation remains largely underexplored. Existing work evaluates compression through downstream task performance or structural preservation, neither of which directly captures how propagation dynamics change after compression. We study two fundamental compression paradigms, coarsening and sparsification, and ask whether they preserve the propagation behavior of the original graph. Across five datasets, varying compression rates, and propagation depths, we measure signal behavior through three complementary metrics. Our results reveal a consistent tension between the two compression families. Sparsification retains higher signal diversity and mitigates oversmoothing, but its propagation trajectory progressively diverges from that of the original graph. Coarsening more faithfully preserves propagation behavior, but at the cost of stronger smoothing and rank collapse. These findings demonstrate that two propagation-centric objectives, preserving signal diversity and preserving propagation fidelity, are distinct and empirically at odds under graph compression, highlighting the need for evaluation protocols that jointly consider both dimensions. The code and results are available at: https://github.com/KawshikBanerjee/Compression-Propagation-Duality

Kawshik Banerjee, Khaled Mohammed Saifuddin

Graph Representation Learning Context Compression Propagation Sparsity

Ask PDF

Sep 26, 2025cs.LG

Rotary Position Encodings for Graphs

We study the extent to which rotary position encodings (RoPE), a recent transformer position encoding algorithm broadly adopted in large language models (LLMs) and vision transformers (ViTs), can be applied to graph-structured data. We find that rotating tokens depending on the spectrum of the graph Laplacian efficiently injects structural information into the attention mechanism, boosting performance in synthetic and real-world graph learning tasks. This approach, coined Wave-Induced Rotary Encodings (WIRE), enjoys intriguing theoretical properties: it recovers regular RoPE on grids, and depends asymptotically on the graph effective resistance. Unlike bias-based relative position encodings, WIRE is compatible with linear attention.

Isaac Reid, Arijit Sehanobish, Cederik Höfs +7

Positional Encoding Transformer Architectures Graph Laplacians

Ask PDF

Jun 11, 2026cs.LG

Understanding Truncated Positional Encodings for Graph Neural Networks

Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires

O(n^3)

time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first

k

eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the

k

-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.

James Flora, Mitchell Black, Weng-Keen Wong +1

Graph Neural Networks Positional Encoding Graph Laplacians Expressivity

Ask PDF