  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\times$ and $6555\times$
for essential GraphBLAS kernels SpMV and SpGEMM, respectively, making
GraphBLAS-based BFS accelerate up to $433\times$, SSSP, PR, and CC up to
$35\times$, and TC up to $52\times$.
