Graph Compression for Adjacency-Matrix Multiplication
Alexandre P. Francisco, Travis Gagie, Dominik Köppl, Susana Ladra,
and Gonzalo Navarro
Computing the product of the (binary) adjacency matrix of a large
graph with a real-valued vector is an important operation that
lies at the heart of various graph analysis tasks, such as computing
PageRank. In this paper we show that some well-known web-graph
and social graph compression formats are computation-friendly,
in the sense that they allow boosting the computation. We focus
on the compressed representations of (a) Boldi and Vigna and (b)
Hernandez and Navarro, and show that the product computation can
be conducted in time proportional to the compressed graph size.
Our experimental results show speedups of at least 2 on graphs
that were compressed at least 5 times with respect to the original.