What is GraphBLAS?

By davis

GraphBLAS is a way of writing graph algorithms using the "language" of linear algebra.  It has an entire community behind it, at graphblas.org.

An adjacency matrix of a graph is a sparse matrix, and matrix operations using different semirings can express steps of a graph algorithm.  For example, a single step of a breadth-first search can be written as a masked matrix-vector multiply.

The semiring redefines what is meant by multiplying two matrices: the scalar multiply and the add of conventional linear algebra are  replaced with the multiplicative operator and additive monoid of a semiring.  For breadth-first-search, the semiring is OR_AND (the add becomes the logical OR, and the multiply becomes the logical AND).  The mask is a bulk-if statement, that only adds new nodes to the next level of the BFS.


A single statement in GraphBLAS can do a lot inside. This gives me, the library implementor, a great deal of scope to optimize the operation.  It gives the graph algorithm developer a powerful and expressive way to write graph algorithms, kind of like a MATLAB for graphs.

All the gnarly details of the graph are hidden inside the GraphBLAS matrix.  I'll take care of those details; you write the high-level algorithms.  You don't have to write code that walks across nodes and edges, one at a time.  Then I can do the gnarly stuff asymptotically fast (and fast in practice).  I'm currently working on a parallel implementation, both on the CPU (with OpenMP) and on the GPU (in CUDA), which speeds things up even more. More on that in a future blog.

The community has been designing GraphBLAS for years (see for example the 2011 book edited by Kepner and Gilbert), and finalized a specification of the library about 2 years ago.  They asked me to write the reference implementation, which you can read about in my prior blog post.

You can read more about GraphBLAS in my interview by the ACM.