# GraphBLAS

Status The logo of the GraphBLAS API Released 29 May 2017 1.325 September 2019 Graph algorithms Creative Commons Attribution (CC BY) 4.0 graphblas.org

GraphBLAS () is an API specification that defines standard building blocks for graph algorithms in the language of linear algebra. GraphBLAS is built upon the notion that a sparse matrix can be used to represent graphs as either an adjacency matrix or an incidence matrix. The GraphBLAS specification describes how graph operations (e.g. traversing and transforming graphs) can be efficiently implemented via linear algebraic methods (e.g. matrix multiplication) over different semirings.

The development of GraphBLAS and its various implementations is an ongoing community effort, including representatives from industry, academia, and government research labs.

## Background

Graph algorithms have long taken advantage of the idea that a graph can be represented as a matrix, and graph operations can be performed as linear transformations and other linear algebraic operations on sparse matrices.: xxv–xxvi  For example, matrix-vector multiplication can be used to perform a step in a breadth-first search.: 32–33

The GraphBLAS specification (and the various libraries that implement it) provides data structures and functions to compute these linear algebraic operations. In particular, the GraphBLAS specifies sparse matrix objects which map well to graphs where vertices are likely connected to relatively few neighbors (i.e. the degree of a vertex is significantly smaller than the total number of vertices in the graph). The specification also allows for the use of different semirings to accomplish operations in a variety of mathematical contexts.

Originally motivated by the need for standardization in graph analytics, similar to its namesake BLAS, the GraphBLAS standard has also begun to interest people outside the graph community, including researchers in machine learning, and bioinformatics. GraphBLAS implementations have also been used in high-performance graph database applications such as Redis.

### Specification

The GraphBLAS specification has been in development since 2013, and has reached version 1.3 as of November 2019. While formally a specification for the C programming language, a variety of programming languages have been used to develop implementations in the spirit of GraphBLAS, including C++, Java, and Nvidia CUDA.

### Compliant implementations and language bindings

There are currently two fully-compliant reference implementations of the GraphBLAS specification. Bindings assuming a compliant specification exist for the Python, MATLAB, and Julia programming languages.

## Linear algebraic foundations Computing a single step in a breadth-first search of a graph. Matrix-vector multiplication can be used to compute the outbound neighbors (vertices 1 and 3, shown in blue) of a given source vertex (shown in red). Note that the matrix $A$ is the adjacency matrix of the graph shown to the left, with outbound edges (4,1) and (4,3) shown in green.

The mathematical foundations of GraphBLAS are based in linear algebra and the duality between matrices and graphs.

Each graph operation in GraphBLAS operates on a semiring, which is made up of the following elements:

• A scalar addition operator ($\oplus$ )
• A scalar multiplication operator ($\otimes$ )
• A set (or domain)

Note that the zero element (i.e. the element that represents the absence of an edge in the graph) can also be reinterpreted.:  For example, the following algebras can be implemented in GraphBLAS:

Algebra $\oplus$ $\otimes$ Domain Zero Element
Standard arithmetic $+$ $\times$ $\mathbb {R}$ 0
Max–plus algebra $\max$ $+$ $\{-\infty \cup \mathbb {R} \}$ $-\infty$ Min–plus algebra $\min$ $+$ $\{+\infty \cup \mathbb {R} \}$ $+\infty$ Max–min algebra $\max$ $\min$ $[0,+\infty )$ 0
Min–max algebra $\min$ $\max$ $(-\infty ,0]$ 0
Galois field XOR AND $\{0,1\}$ 0

All the examples above satisfy the following two conditions in their respective domains:

• Additive identity, $a\oplus 0=a$ • Multiplicative annihilation, $a\otimes 0=0$ For instance, a user can specify the min-plus algebra over the domain of double-precision floating point numbers with GrB_Semiring_new(&min_plus_semiring, GrB_MIN_FP64, GrB_PLUS_FP64).

## Functionality

While the GraphBLAS specification generally allows significant flexibility in implementation, some functionality and implementation details are explicitly described:

• GraphBLAS objects, including matrices and vectors, are opaque data structures.: 2.4 GraphBLAS Opaque Objects
• Non-blocking execution mode, which permits lazy or asynchronous evaluation of certain operations.: 2.8.1 Execution modes
• Masked assignment, denoted $A\langle M\rangle =B$ , which assigns elements of matrix $B$ to matrix $A$ only in positions where the mask matrix $M$ is non-zero.: 3.6 Masks

The GraphBLAS specification also prescribes that library implementations be thread-safe.: 2.8.2 Thread Safety

## Example code

The following is a GraphBLAS 1.3-compliant example of a breadth-first search in the C programming language.: 222

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include "GraphBLAS.h"

/*
* Given a boolean n x n adjacency matrix A and a source vertex s, performs a BFS traversal
* of the graph and sets v[i] to the level in which vertex i is visited (v[s] == 1).
* If i is not reachable from s, then v[i] = 0. (Vector v should be empty on input.)
*/
GrB_Info BFS(GrB_Vector *v, GrB_Matrix A, GrB_Index s)
{
GrB_Index n;
GrB_Matrix_nrows(&n,A);                  // n = # of rows of A

GrB_Vector_new(v,GrB_INT32,n);           // Vector<int32_t> v(n)

GrB_Vector q;                            // vertices visited in each level
GrB_Vector_new(&q, GrB_BOOL, n);         // Vector<bool> q(n)
GrB_Vector_setElement(q, (bool)true, s); // q[s] = true, false everywhere else

// BFS traversal and label the vertices.
int32_t d = 0;                           // d = level in BFS traversal
bool succ = false;                       // succ == true when some successor found

do {
GrB_assign(*v, q, GrB_NULL, d, GrB_ALL, n, GrB_NULL);                    // v[q] = d
GrB_vxm(q, *v, GrB_NULL, GrB_LOR_LAND_SEMIRING_BOOL, q, A, GrB_DESC_RC); // q[!v] = q ||.&& A; finds all the
// unvisited successors from current q
GrB_reduce(&succ, GrB_NULL, GrB_LOR_MONOID_BOOL, q, GrB_NULL);           // succ = || (q)

} while (succ);                                                            // if there is no successor in q, we are done.

GrB_free(&q);                                                              // q vector no longer needed

return GrB_SUCCESS;
}