notation.tex

\section{GraphBLAS Theory and Notation}
\label{sec:notation}

\input{table-graphblas-notation}

In this section, we summarize the key concepts in \grb, then present a concise notation for the operations and methods defined in the \grb standard.
Additionally, we demonstrate how the operations can be interpreted as graph processing primitives if graphs are encoded as adjacency matrices 
and nodes are selected using vectors.\footnote{We use these specialized vectors/matrices here for illustration purposes -- the \grb standard allows the definition of arbitrary vectors/matrices.}

\subsection{Overview}

We first give a brief overview of the theoretical aspects of the \grb. For more details, we refer the reader to tutorials~\cite{gabor_szarnyas_2020_4318870} and the specification documents~\cite{GraphBLASv13,GxBUserGuide}.

\paragraph{Data structures}
\grb builds on the duality between graph and matrix data structures.
Namely, a directed graph $G = (V, E)$ can be represented with a boolean \emph{adjacency matrix} $\grbm{A} \in \grbbool^{|V| \times |V|}$ where $\grbm{A}_{i,j} = \grbtrue$ iff $(v_i, v_j) \in E$.
The adjacency matrices used in \grb algorithms are not necessarily square: \eg induced subgraphs, where source nodes are selected from $V_1 \subseteq V$ and target nodes are selected from $V_2 \subseteq V$, can be represented with $\grbm{A} \in \grbbool^{|V_1| \times |V_2|}$.
The transposition of~$\grbm{A} \in D^{n \times m}$ is denoted with $\grbm{A}\grbt \in D^{m \times n}$ where $\grbm{A}\grbt(i, j) = \grbm{A}(j, i)$.
Compared to $\grbm{A}$, matrix~$\grbm{A}\grbt$ contains the edges in the reverse direction.

\emph{Vectors} can be used to encode data for nodes, \eg $\grbv{u} \in \grbbool^{|V|}$ can be used to select a subset of nodes.
For vectors, $\grbm{u}$ denotes a column vector and $\grbm{u}\grbt$ denotes a row vector.
Vectors and matrices can be defined over different types, \eg an unsigned integer ($\grbuint$) matrix can encode the number of paths between two nodes, while a floating point ($\grbdouble$) matrix can encode edge weights.

In practice, adjacency matrices representing graphs are sparse, \ie most of their elements are \emph{zero}, lending themselves to compressed representations such as CSR/CSC.
The \emph{zero elements} take their values during operations based on the identity of the semiring's $\grbplus$ operation (see below).

%We refer to the graph represented by adjacency matrix~$\grbm{A}$ as ``the graph of $\grbm{A}$''.

\paragraph{Semirings}
\grb uses matrix operations %(\autoref{sec:operations})
to express graph processing primitives, \eg a matrix-vector multiplication $\grbm{A} \grbplustimes \grbm{u}$ finds the incoming neighbors of the set of nodes selected by vector~$\grbv{u}$ in the graph of~$\grbm{A}$.

\grb allows users to perform the multiplication operations over an arbitrary \emph{semiring}.
The multiplication operator $\grbtimes$ is used for combining the values of matching input elements, while the addition operator $\grbplus$ defines how the results should be summarized.
For example, the $\grbminplus$ semiring uses $\grbplustext$ as the multiplication operator to compute the path length and $\grbmin$ as the addition operator to determine the length of the shortest path.
The algorithms presented in this paper use a number of non-conventional semirings such as $\grbanysecondi$, $\grbplusfirst$, and $\grbpluspair$. These are summarized in \autoref{tab:semirings} and defined in \autoref{sec:evaluation}.

\input{table-semirings}

\paragraph{Masks and accumulators}
All \grb operations whose output is a vector or a matrix allow the use of masks to limit the scope of the computation and an accumulator $\grbaccum$, a binary operator, that determines how the result of an operation should be applied to their output. %? ~\cite{DBLP:conf/ipps/AzadBG15}
The semantics of masks is that the computation should be performed
on a given set of nodes (for vector masks) or
on a given set of edges (for matrix masks).
The accumulator determines how the results should be applied to the (potentially non-empty) output matrix/vector.
The interplay of masks and the accumulators is discussed in the specifications~\cite{GraphBLASv13,GxBUserGuide}.

\paragraph{Notation}
To present our algorithms, we use the mathematical notation given in \autoref{tab:graphblas-notation}.
Matrices and vectors are typeset in bold, starting with uppercase ($\grbm{A}$) and lowercase ($\grbv{u}$) letters, respectively.
Scalars including indices are lowercase italic ($\grbs{k}$, $\grbs{i}$, $\grbs{j}$) while arrays are lowercase bold italic ($\grba{x}$, $\grba{i}$, $\grba{j}$).

\subsection{Operations}
\label{sec:operations}

\paragraph{Matrix multiplication}
\label{sec:mxm}

The \emph{matrix-matrix multiplication} operation $\grbm{A} \grbplustimes \grbm{B}$ expresses a navigation step that starts
in the edges of $\grbm{A}$ and traverses from their endpoints
using the edges of $\grbm{B}$.
The result matrix~$\grbm{C}$ has elements $\grbm{C}_{i,j}$ representing the summarized paths (\eg number of paths, shortest paths) between start node $i$ in the graph of $\grbm{A}$ and end node $j$ in the graph of $\grbm{B}$.

The \emph{vector-matrix multiplication} operation $\grbv{u}\grbt \grbplustimes \grbm{A}$ performs navigation starting from the nodes selected in vector~$\grbv{u}$ along the edges of matrix~$\grbm{A}$.
The result vector~$\grbm{w}$ contains the set of reached nodes with the values computed on the semiring (combining the source node values with the outgoing edge values using $\grbtimes$ then summarizing these for each target node using $\grbplus$).
The \emph{matrix-vector multiplication} operation $\grbm{A} \grbplustimes \grbv{u}$ performs navigation in the reverse direction on the edges of~$\grbm{A}$.


\paragraph{Element-wise addition}

The \emph{element-wise addition} operations
$\grbm{u} \grbewiseadd{\grbgenericop} \grbm{v}$ and
$\grbm{A} \grbewiseadd{\grbgenericop} \grbm{B}$
apply the operator $\grbgenericop$ on the elements selected by the \emph{union of the structures of its inputs},
\ie nodes/edges which are present in at least one of the input matrices.

\paragraph{Element-wise multiplication}

The \emph{element-wise multiplication} operation
$\grbm{u} \grbewisemult{\grbgenericop} \grbm{v}$ and
$\grbm{A} \grbewisemult{\grbgenericop} \grbm{B}$
apply the operator $\grbgenericop$ on the elements selected by the \emph{intersection of the structures of its inputs},
\ie nodes/edges which are present in both inputs.

\paragraph{Extract}
For adjacency matrix~$\grbm{A}$,
the \emph{extract submatrix} operation $\grbm{A}(\grba{i}, \grba{j})$ returns a matrix containing the elements from $\grbm{A}$ with
row indices in $\grba{i}$ and
column indices in $\grba{j}$.
In graph terms, the submatrix represents an induced subgraph where
the source nodes of the edges are in array $\grba{i}$ and
the target nodes of the edges are in array $\grba{j}$.
The \emph{extract vector} operation $\grbv{A}(\grbs{i}, :)$ selects a column vector containing node $\grbs{i}$'s neighbors along incoming edges.
The \emph{extract subvector} operation $\grbv{u}(\grba{i})$ selects the nodes with indices in array $\grba{i}$.

%with an optional mask $\grbmask{\grbm{M}}$ to limit the computation to certain edges.

\paragraph{Assign}
The \emph{assign} operation has multiple variants.
The first assigns a matrix to a submatrix selected by row indices $\grba{i}$ and column indices $\grba{j}$:
$\grbm{C} \grbmask{\grbm{M}} (\grba{i},\grba{j}) \grbaccumeq{} \grbm{A}$.
This operator is useful to project an induced subgraph back to the original graph.
The second assigns a vector to a subvector selected by indices $\grba{i}$:
$\grbv{w} \grbmask{\grbv{m}} (\grba{i}) \grbaccumeq{} \grbv{u}$.
Finally, both the selected submatrix/subvector can be assigned with a scalar value:
$\grbm{C} \grbmask{\grbm{M}} (\grba{i},\grba{j}) \grbaccumeq{} \grbs{s}$ and
$\grbv{w} \grbmask{\grbv{m}} (\grba{i}) \grbaccumeq{} \grbs{s}$.
In all cases, the scope of the assignment can be further constrained using masks (see \autoref{sec:masks}).

%\paragraph{Subassign} ?

\paragraph{Apply and select}
The \emph{apply} and \emph{select} operations evaluate a unary operator $f$ with an optional input $k$ (the \emph{thunk}) on all elements of the input matrix/vector. When evaluated on a given element, function $\mathit{f}$ can access the indices of the element, allowing the operation to be constrained on regions of the matrix such as its lower triangle.
In the case of \emph{apply}, denoted with $\grbf{f}{\grbm{A}, \grbs{k}}$ and $\grbf{f}{\grbv{u}, \grbs{k}}$, the resulting elements are returned as part of the output.
The \emph{select} operation requires $f$ to be a boolean function and zeros out elements that return $\grbfalse$.
Intuitively,
$\grbm{A}\grbselect{\grbf{f}{\grbm{A}, \grbs{k}}}$ and $\grbv{u}\grbselect{\grbf{f}{\grbv{u}, \grbs{k}}}$ express filtering on the edges of matrix~$\grbm{A}$ and the nodes of vector~$\grbv{u}$, respectively.

\paragraph{Reduce}
For adjacency matrix~$\grbm{A}$,
the \emph{row-wise reduction} $\grbv{w} \grbmask{\grbv{m}} \grbaccumeq{} \grbreduce{\grbplus}{\grbs{j}}{\grbm{A}}{:,\grbs{j}}$ represents a summarization of the values on outgoing edges for each node (represented by row vector~$\grbm{A}(:, \grbs{j})$) to vector~$\grbv{w}. $ %with an optional mask $\grbmask{\grbv{m}}$ to limit the computation to certain nodes.
For matrix~$\grbm{A}$, the \emph{reduction to scalar} $\grbs{s} \grbaccumeq{} \grbreduce{\grbplus}{\grbs{i}, \grbs{j}}{\grbm{A}}{\grbs{i},\grbs{j}}$ represents a summarization of all edge values.
For vector~$\grbv{u}$, the \emph{reduction to scalar} $\grbs{s} \grbaccumeq{} \grbreduce{\grbplus}{\grbs{i}}{\grbm{u}}{\grbs{i}}$ represents a summarization of all node values.

\paragraph{Transposition}
Transposition can be applied as a standalone \grb operation $\grbm{C} \grbmask{\grbm{M}} \grbaccumeq{} \grbm{A}\grbt$ %with an optional mask $\grbmask{\grbm{M}}$
and also to the input/output matrices of operations, for example:
$$\grbm{C}^{[\grbtransposesymbol]} \grbmask{\grbm{M}} \grbaccumeq{} \grbm{A}^{[\grbtransposesymbol]} \grbplustimes \grbm{B}^{[\grbtransposesymbol]}$$

%\paragraph{Kronecker}
%omitted to keep the paper concise

\subsection{Masks}
\label{sec:masks}

% \todo{explain replace/merge as per Scott's email}
% REPLACE: C :=              M .* (C + AB)
% MERGE:   C := (!M .* C) U [M .* (C + AB)]
% \todo{revise Scott, Tim D, and Tim M}

Masks are used  to limit the scope of \grb operations \wrt their outputs.
For operations resulting in a vector, the mask is based on a vector~$\grbm{m}$. For those resulting in a matrix, it is based on a matrix~$\grbm{M}$.
Here, we only discuss matrix masks.  Extension to vectors is straightforward.

By default, the elements of the mask that exist and are non-zero select corresponding elements of the output matrix that should be computed.  
There are three variations on the mask that impact the output of a \grb operation:
\begin{enumerate}
    \item
        Does the computation need to be performed on the elements selected by the mask ($\grbmask{\grbm{M}}$) or the complement of these elements ($\grbmask{\grbneg\grbm{M}}$)?
    \item
        How are existing elements of the output matrix treated that fall outside the ones selected by the  mask?
        By default, masks use \emph{merge} semantics, \ie the computation can only affect elements selected by the mask, elements outside the mask are unaffected.
        If \emph{replace} semantics is set, masks annihilate all elements outside the mask. This is denoted with $\grbmaskreplace{\grbm{M}}$.
    \item
        How the elements are selected?
        By default, masks are \emph{valued}, \ie values in the mask are checked and elements with explicit zero values (\eg 0 for $\grbarithmeticplustimestext$) are not considered to be part of the mask.
        To only consider the pattern of the mask, \ie the elements of the mask that exist, a \emph{structural mask} should be used, denoted with $\grbmask{\grbstr{\grbm{M}}}$. %and $\grbmask{\grbneg\grbstr{\grbm{M}}}$ for negated masks.
\end{enumerate}

Operations can use \emph{replace semantics} and \emph{structural masks} at the same time, denoted with
$\grbmaskreplace{\grbstr{\grbm{M}}}$

\subsection{Methods}

\grb provides methods for initializing and duplicating vectors and matrices
(\eg $\grbnewvector{\grbv{w}}{\grbfloat}{32}{n}$ and $\grbm{C} \grbassign \grbm{A}$),
setting the values of individual elements ($\grbv{w}(2) = \grbtrue$),
extracting the tuples in the form of index/value arrays from matrices/vectors and building them from tuples ($\grbv{w} \grbassign \left\{ \grba{i}, \grba{x} \right\}$ and $\left\{ \grba{i}, \grba{x} \right\} \grbassign \grbv{u}$).
Additionally, methods are provided for creating new operators, monoids, and semirings, clearing a matrix/vector, etc.