# Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU

arXiv: https://arxiv.org/abs/2201.08560 · HTML: https://mlsanity.com/paper/2201.08560/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2022.

## Built on by (most cited first, 2 of 2)

- [BitGNN: Unleashing the Performance Potential of Binary Graph Neural Networks on GPUs](https://mlsanity.com/paper/2305.02522/) (2023)
- [Tango: rethinking quantization for graph neural network training on GPUs](https://mlsanity.com/paper/2308.00890/) (2023)

## Abstract (arXiv)

In a general graph data structure like an adjacency matrix, when edges are homogeneous, the connectivity of two nodes can be sufficiently represented using a single bit. This insight has, however, not yet been adequately exploited by the existing matrix-centric graph processing frameworks. This work fills the void by systematically exploring the bit-level representation of graphs and the corresponding optimizations to the graph operations. It proposes a two-level representation named Bit-Block Compressed Sparse Row (B2SR) and presents a series of optimizations to the graph operations on B2SR by leveraging the intrinsics of modern GPUs. Evaluations on NVIDIA Pascal and Volta GPUs show that the optimizations bring up to 40× and 6555× for essential GraphBLAS kernels SpMV and SpGEMM, respectively, making GraphBLAS-based BFS accelerate up to 433×, SSSP, PR, and CC up to 35×, and TC up to 52×.