改进图压缩的顶点排序策略,显著提升压缩率。
Community-Aware Vertex Ordering for Reference-Based Graph Compression: A Cross-Encoder Empirical Study

- 分两阶段优化顶点顺序:先用社区检测定位结构,再局部重排。
- 在弱有序图上,压缩率提升0.9至4.6比特/边,优于传统排序。
- 新方法对多种编码器均有效,适合图数据压缩研究者使用。
基于参考的图压缩将每个顶点的邻居列表编码为与邻近已编码列表的差异。WebGraph的BVGraph采用固定编码流程,依赖独立选择的顶点排序(如URL字典序或分层标签传播,LLP)。两者交互很少被评估。本文提出两阶段Leiden+LLP排序:全局LLP播种标签,Leiden识别社区,最终再进行一次局部LLP重排。我们研究其与参考压缩的交互,使用BVGraph及三个新贡献的编码器——BG、CS和CG——每个编码器按顶点选择最多28种候选分解中的最低开销方案。在初始顶点顺序较差的图上,使用Leiden+LLP重排使所有编码器压缩率提升0.9至4.6比特/边(bpe),相比原始顶点ID顺序在SNAP类图中表现优异。该增益几乎不依赖编码器:在五个弱有序数据集中,四个编码器对Leiden+LLP vs. 原始LLP的增益一致性在±0.04 bpe内。在已有局部性编码的URL有序网页爬取数据中,BG和CS仍受益,但对残差敏感配置(如BVGraph默认、BV-HC,以及依赖社区连续性的CG)反而退化。该效果跨越两代编码器(斐波那契编码与全上下文自适应范围编码)和三种排序种子。当所有结构比特熵编码时,我们提出的三个编码器之一在全部七个数据集的所有整体与随机访问比较中均超越现有最强基线(Zuckerli,以及更强的BV-HC / BVGraph默认)——共28个对比项中全部胜出,相较Zuckerli提升0.3%至35%;编码器层面增益始终小于排序层面。所有算法、排序流水线及生成器已开源,发布于Adjacently Julia库。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。