SuperCSR: A Space-Time-Efficient CSR Representation for Large-scale Graph Applications on Supercomputers

It is widely accepted that graph representations such as the Compressed Sparse Row (CSR) format, directly affect the space and time complexities of graph processing. However, the standard CSR and its current variations are prone to high memory footprint and complicated calculations, which necessitates the development of more efficient graph processing techniques to save memory and reduce calculations. This paper presents SuperCSR, a more space-time-efficient CSR representation for fast graph processing. SuperCSR’s key idea is to leverage the law of sorted graphs, which would directly access adjacent vertex sets from an active vertex ID without complex indexing calculations and with a lower memory footprint.

We validate SuperCSR through theoretical analysis and experimental evaluation. Theoretically, it is proved that SuperCSR would reduce the space of the auxiliary array to O(1), compared to the best previously claimed O(Nnz), where Nnz is the number of vertices with degrees > 0. Moreover, SuperCSR requires the fewest calculations among all CSR-like methods. Practically, extensive evaluations validate that SuperCSR achieves up to 98.61% in space savings and SuperCSR-based graph traversal exhibits the highest performance in graph processing among CSR-like formats. Finally, SuperCSR has been deployed on a 79,024-node supercomputer to rank Graph500. Based on SuperCSR, the next-generation Tianhe supercomputer surpasses the top 1 with 58% higher performance and 50% lower memory space.