Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Monotonic graph algorithms, such as shortest path, BFS, and reachability, are fundamental to graph analytics and are widely used across domains. Recent systems employ pruning techniques to accelerate the processing of these algorithms. However, state-of-the-art monotonic graph engines are restricted to in-memory execution and cannot scale to graphs that exceed main memory capacity. In contrast, existing out-of-core graph engines are designed for general-purpose workloads and lack effective pruning mechanisms tailored to monotonic graph algorithms. To bridge this gap, we present Gem, an out-of-core graph engine designed for monotonic graph algorithms. Gem introduces a PageRank-based graph sketch that captures key topological features inmemory with minimal preprocessing overhead. Building on this sketch, we propose a novel graph abstraction that enables the direct derivation of tight bounds for monotonic graph algorithms, supporting effective pruning at both the vertex and partition levels. Comprehensive evaluations on six real-world datasets, including the 42.5-billion-edge ClueWeb graph, show that Gem significantly outperforms existing systems. It achieves up to 135.40x speedup over GridGraph and 12.58x over Wonderland in out-of-core settings, and also delivers substantial improvements in other modes: up to 10.41x over RisGraph in memory and 20.64x over CGgraph out-of-GPU memory.

Author Affiliations

@article{huan2026gem,
  title = {Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine},
  author = {Huan, Chengying and Yang, Zhengyi and Yang, Haoshen and Ma, Shaonan and Gu, Rong and Xi, Fang and Liu, Yongchao and Chen, Guihai and Tian, Chen},
  volume = {3},
  issn = {2836-6573},
  url = {http://dx.doi.org/10.1145/3769795},
  doi = {10.1145/3769795},
  number = {6},
  journal = {Proceedings of the ACM on Management of Data},
  publisher = {Association for Computing Machinery (ACM)},
  year = {2025},
  month = Dec,
  pages = {1-30}
}