intro.tex

\section{Introduction}
\label{sec:introduction}

Graphs represent networks of relationships. They play a key role in 
a wide range of applications.   Consequently, numerous graph libraries exist 
such as igraph~\cite{igraph}, NetworkX~\cite{DBLP:reference/snam/X18xv}, and SNAP~\cite{DBLP:journals/tist/LeskovecS16}.
%, and JGraphT~\cite{DBLP:journals/toms/MichailKNS20}.
These libraries let programmers work with graphs without the need to master the art of crafting graph algorithms.

There are multiple ways to build libraries of graph algorithms.  One approach
views graphs as sparse matrices and graph algorithms as
linear algebra. This perspective led to the 
GraphBLAS~\cite{DBLP:conf/hpec/MattsonBBBDFFGGHKLLPPRSWY13,DBLP:conf/hpec/MattsonYMBM17}; 
a community effort~\cite{GraphBLASforum} to define low-level building blocks for graph algorithms as linear algebra.
The GraphBLAS are for graph algorithm \emph{developers}.  They are too 
low-level for graph algorithm \emph{users}.  To focus on users and the 
algorithms they require, we launched the
LAGraph project~\cite{DBLP:conf/ipps/MattsonDKBMMY19}.  

LAGraph is a library 
of high quality, production-worthy algorithms constructed on top of
the GraphBLAS.  In this paper, we describe the first release of LAGraph~\cite{LAGraphRepo}.
While LAGraph will eventually work with any implementation of the GraphBLAS, it is currently tied to
the \ssgrb library~\cite{SuiteSparseGraphBLAS} (SS:GrB).

In this release of LAGraph, we restricted ourselves to versions of the algorithms found in the GAP benchmark.
This restricted scope allowed us to focus on the key design decisions needed to establish a solid
foundation for the future.  Those design decisions, the rationale behind them, and a performance baseline 
using the GAP benchmark suite~\cite{DBLP:journals/corr/BeamerAP15} are key contributions of this paper.   

The LAGraph project is more than a library project.   It is also
a repository of algorithms based on the GraphBLAS to help advance the state of the art in 
Graph algorithms expressed as Linear algebra. To support this goal, we created a concise notation for expressing
graph algorithms in terms of the GraphBLAS.   As an example of this notation in action, we use it to describe 
the algorithms used in the GAP benchmark suite.  This notation is a key contribution of this paper.  

%
%Save for Future work: improve data ingestion performance, e.g. using SIMD techniques~\cite{DBLP:journals/vldb/LangdaleL19}

%Previous \grb design papers:
%theory~\cite{DBLP:conf/hpec/MattsonBBBDFFGGHKLLPPRSWY13},
%C API~\cite{DBLP:conf/hpec/MattsonYMBM17},
%C++ API~\cite{DBLP:conf/ipps/BrockBMMM20},
%distributed API~\cite{DBLP:conf/ipps/BrockBMMMPSS20},
%LAGraph~\cite{DBLP:conf/ipps/MattsonDKBMMY19}


%\todo{add two paragraphs with a high-level overview of LAGraph}

%\footnote{A non peer-reviewed comparison of 6 popular graph algorithms libraries is available at
%\url{https://www.timlrx.com/blog/benchmark-of-popular-graph-network-packages-v2}.}