gsvgit/GraphBLAS-Pointers

Resources on the GraphBLAS standard for graph algorithms in the language of linear algebra

GraphBLAS Pointers

Notation:

• ⭐ if you're new to GraphBLAS, check out these pointers first
• 🔨 theory-focused
• 🔧 implementation-focused
• 🛠️ mix of theory and implementation
• 📖 detailed specification

Community sites

• 🐦 GraphBLAS Twitter page
• GraphBLAS.org
• HPC Graph Analysis

Selected readings and presentations

• ⭐ GraphBLAS Wikipedia page
• ⭐ 🎥 Graph Analytics: A Foundational Building Block for the Data Analytics World, Tim Mattson, Henry Gabb (2020)
• ⭐ Introduction to GraphBLAS: A linear algebraic approach for concise, portable, and high-performance graph algorithms by Gábor Szárnyas

GraphBLAS design papers

• 🔨 Standards for graph algorithm primitives (HPEC 2013) by Tim Mattson et al.
• 🔨 Graphs, Matrices, and the GraphBLAS: Seven Good Reasons (ICCS 2015) by Jeremy Kepner et al.
• 🔨 ⭐ Mathematical Foundations of the GraphBLAS (HPEC 2016) by Jeremy Kepner et al.
  • Extended version: GraphBLAS Mathematics - Provisional Release 1.0 (2017)
• 🛠️ Design of the GraphBLAS API for C (GABB @ IPDPS 2017) by Aydın Buluç et al.
• 🛠️ GraphBLAS C API: Ideas for future versions of the specification (HPEC 2017) by Tim Mattson et al.
• 🔧 Implementing the GraphBLAS C API (GABB @ IPDPS 2018) by José E. Moreira, Manoj Kumar, William P. Horn
• 🔨 Mathematics of Digital Hyperspace (GrAPL @ IPDPS 2020) by Jeremy Kepner et al., introducing the definition of semilinks

Tutorials

• 🔨 ⭐ Introduction to GraphBLAS: A linear algebraic approach for concise, portable, and high-performance graph algorithms by Gábor Szárnyas: a tutorial with 180+ slides
  • 🎥 Talk at FOSDEM 2020's HPC room (abridged version)
  • Case studies, algorithms, and other slide decks
• 🛠️ ⭐ Hands-on tutorial for GraphBLAS (HPEC 2018-) by Scott McMillan and Tim Mattson
  • latest version presented at SIAM CSE 2021
• 🔧 ⭐ Introduction to GraphBLAS with Python (2019) by Michel Pelletier
• 🔨 The Algebraic Path Problem: Semirings by Fred Hamprecht at the HCI of Heidelberg University (2020)

Specifications

• 🛠️ 📖 The GraphBLAS C API Specification by Aydın Buluç, Tim Mattson, Scott McMillan, José Moreira, Carl Yang
  • Summary paper: Design of the GraphBLAS API for C (GABB @ IPDPS 2017)
• 🛠️ 📖 SuiteSparse:GraphBLAS User Guide by Tim Davis

Algorithms

• 🔧 ⭐ LAGraph – A library of algorithms for GraphBLAS, similar to LAPACK for BLAS
  • Repository on GitHub
  • LAGraph Working Group: Public document and planning repository for the LAGraph Working Group
  • LAGraph: A Community Effort to Collect Graph Algorithms Built on Top of the GraphBLAS (GrAPL @ IPDPS 2019) by Tim Mattson et al.
  • LAGraph: Linear Algebra, Network Analysis Libraries, and the Study of Graph Algorithms (GrAPL @ IPDPS 2021) by Gábor Szárnyas et al.

Generic

• 🛠️ Large-scale graph representation learning and computational biology through sparse matrices by Aydın Buluç (NJIT Data Science Seminar Series, 2021)
• 🔧 Parallel GraphBLAS with OpenMP (SIAM Workshop on Combinatorial Scientific Computing, CSC 2020) by Mohsen Aznaveh et al.
• 🔨 GraphBLAS: Handling performance concerns in large graph analytics (Computing Frontiers 2018) by Manoj Kumar, José Moreira, Pratap Pattnaik
• Many algorithms are described as an example in the specification and in papers about frameworks:
  • The specification has BFS (levels/parents), betwenness centrality, maximal independent set (Luby's algorithm) and triangle count
  • The GraphBLAS CF paper has deep neural network (feed-forward pass), betweenness centrality and PageRank.
  • The SuiteSparse TOMS paper has BFS and maximal independent set (Luby's algorithm).
  • The GraphBLAS Template Library has many textbook algorithms including maxflow and minimum spanning tree (Prim's).
  • LAGraph has many algorithms including community detection using label propagation and an SCC algorithm.
  • BFS algorithm computing the DAG of the traversal

Traversals and shortest paths

• 🛠️ [BFS] Optimal algebraic Breadth-First Search for sparse graphs (preprint, 2019) by Paul Burkhardt
• 🛠️ [BFS] Implementing Push-Pull Efficiently in GraphBLAS (ICPP 2018) by Carl Yang, Aydın Buluç, John D. Owens
  • This paper forms the basis of Chapter 5 in Carl Yang's PhD thesis, High-Performance Linear Algebra-based Graph Framework on the GPU (2019). The figures in the conference paper have some coloring issues that have been amended in the thesis.
  • Presentation
• 🛠️ [BFS] A GraphBLAS solution to the SIGMOD 2014 Programming Contest using multi-source BFS (HPEC 2020) by Márton Elekes et al.
  • Presentation
• 🔨 [DFS] Linear Algebraic Depth-First Search (ARRAY workshop @ PLDI 2019) by Daniele G. Spampinato et al.
  • 🎥 Video
• 🛠️ [SSSP] Delta-Stepping SSSP: From Vertices and Edges to GraphBLAS Implementations (GrAPL @ IPDPS 2019) by Upasana Sridhar et al.
  • In its Preliminaries section, this paper contains the translation of a few vertex-centric and edge-centric design patterns to linear algebra.

Connected components

• 🛠️ [CC] Parallel algorithms for finding connected components using linear algebra (Journal of Parallel and Distributed Computing 2020) by Yongzhe Zhang, Ariful Azad, Aydın Buluç
• 🛠️ [CC] FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence (PP 2020) by Yongzhe Zhang, Ariful Azad, Zhenjiang Hu
• 🛠️ [CC] LACC: A Linear-Algebraic Algorithm for Finding Connected Components in Distributed Memory (IPDPS 2019) by Ariful Azad and Aydın Buluç

Triangle counting, k-truss, clustering coefficient

• 🔧 Graph algorithms via SuiteSparse:GraphBLAS: Triangle counting and K-truss (HPEC 2018) by Tim Davis
• 🛠️ Tze Meng Low et al.'s work on triangle counting:
  • First look: Linear algebra-based triangle counting without matrix multiplication (HPEC 2017) by Tze Meng Low et al.
  • A Family of Provably Correct Algorithms for Exact Triangle Counting (Correctness @ SC 2017) by Matthew Lee and Tze Meng Low
    • Presentation
  • Linear Algebraic Formulation of Edge-centric K-truss Algorithms with Adjacency Matrices (HPEC 2018) by Tze Meng Low et al.
• 🔨 Parallel Triangle Counting and Enumeration Using Matrix Algebra (GABB @ IPDPS 2015) by Ariful Azad, Aydın Buluç, John R. Gilbert
  • This paper introduced masked matrix multiplication which became an important primitive in GraphBLAS.
• 🔨 A task-based linear algebra building blocks approach for scalable graph analytics (HPEC 2015) by Michael M. Wolf, Jonathan W. Berry, Dylan T. Stark
  • Related presentation: Task Parallel Approach to the Linear Algebra-Based Implementation of miniTri (SIAM Annual Meeting 2016) by Michael M. Wolf
  • Related presentation: Fast Linear Algebra-Based Triangle Counting with KokkosKernels (IEEE HPEC/DARPA/Amazon Graph Challenge at HPEC 2017) by Michael Wolf et al.

Context-free path querying (CFPQ)

• 🛠️ Context-Free Path Querying with Single-Path Semantics by Matrix Multiplication (GRADES-NDA 2020) by Arseniy Terekhov et al.
• 🛠️ Context-Free Path Querying by Kronecker Product (ADBIS 2020) by Egor Orachev et al.
• 🔨 Path Querying with Conjunctive Grammars by Matrix Multiplication (Programming and Computer Software 2019) by Rustam Azimov and Semyon Grigorev
• 🔧 CFPQ algorithm implementations using pygraphblas

Community detection

• 🛠️ Linear Algebraic Louvain Method in Python (GrAPL 2020) by Tze Meng Low et al.
  • 🎥 Video
  • pygraphblas implementation

Other

• 🛠️ A GraphBLAS Approach for Subgraph Counting (preprint) by Langshi Chen et al.
• 🛠️ Write Quick, Run Fast: Sparse Deep Neural Network in 20 Minutes of Development Time via SuiteSparse:GraphBLAS (HPEC 2019) by Tim Davis, Mohsen Aznaveh, Scott P. Kolodziej
• 🛠️ Graph Coloring on the GPU (GrAPL 2019) by Muhammad Osama et al.

Presentations

Overviews on GraphBLAS and linear algebra-based graph processing

• 🔨 ⭐ Gábor Szárnyas: GraphBLAS: A linear algebraic approach for high-performance graph algorithms (introduction to GraphBLAS, 100+ slides), 🎥 Talk at FOSDEM 2020's HPC room (abridged version)
• 🔨 ⭐ Jeremy Kepner: Mathematical Foundations of the GraphBLAS and Big Data (SIAM Minisymposium 2020 on Linear Algebraic Tools for Graph Computation) :movie_camera: Video
• John R. Gilbert's talks:
  • 🛠️ ⭐ GraphBLAS: Graph Algorithms in the Language of Linear Algebra (2019)
  • 🔨 Graph Algorithms in the Language of Linear Algebra: How did we get here, where do we go next? (GABB @ IPDPS 2018)
  • 🛠️ Building Blocks for Graph Algorithms in the Language of Linear Algebra (CIMI Workshop on Innovative Clustering Methods 2015)
  • 🛠️ Graph Algorithms in the Language of Linear Algebra (originally at Intel Non-Numeric Computing Workshop 2014)
• Scott McMillan's talks:
  • 🛠️ ⭐ Graph Algorithms on Future Architectures (CMU SEI Research Review 2015), :scroll: Poster, :movie_camera: Video
  • 🛠️ GraphBLAS: A Programming Specification for Graph Analysis (SEI Research Review 2016), :scroll:Poster
  • 🛠️ Design and Implementation of the GraphBLAS Template Library (GBTL) (SIAM Annual Meeting 2016)
  • 🛠️ Automated Code Generation for High-Performance, Future-Compatible Graph Libraries (SEI Research Review 2017), :scroll: Poster, :movie_camera: Video
  • 🛠️ GraphBLAS Updates, SC BoF: HPC Graph Toolkits and GraphBLAS Forum, 2019
• Aydın Buluç's talks:
  • 🛠️ Sparse Matrices Beyond Solvers: Graphs, Biology, and Machine Learning (MIT CSAIL Fast Code Seminar, June 22 2020), 🎥 Video
  • 🛠️ GraphBLAST: A high-performance C++ GPU library implementing GraphBLAS (ECP Annual Meeting 2020)
  • 🛠️ ⭐ GraphBLAS: Concepts, algorithms, and applications (Scheduling Workshop 2019)
  • 🛠️ Graph algorithms, computational motifs, and GraphBLAS (ECP Annual Meeting 2018)
  • 🔧 Concepts in the GraphBLAS C API (2017)
  • 🔨 Parallel Algorithms across the GraphBLAS Stack (ACS HPC and Data Analytics Workshop 2017) co-authored by Ariful Azad
  • 🔨 Faster parallel GraphBLAS kernels (EECS, UC Berkeley, 2016)
  • The Graph BLAS effort and its implications for Exascale (SIAM Workshop on Exascale Applied Mathematics Challenges and Opportunities, 2014)
• 🛠️ Task Parallel Approach to the Linear Algebra-Based Implementation of miniTri Michael Wolf (SIAM Annual Meeting, 2016) by Michael Wolf
• 🛠️ Efficient sparse matrix computations and their generalization to graph computing applications (Linked Data Benchmark Council, Technical User Community meeting, 2017) by Albert-Jan Yzelman
• Tim Davis' talks:
  • 🛠️ SuiteSparse:GraphBLAS: Graph algorithms via sparse matrix operations on semirings (Sparse Days @ CERFACS 2017)
  • 🛠️ SuiteSparse:GraphBLAS, a Parallel Implementation of the GraphBLAS Specification (SIAM Minisymposium 2020 on Linear Algebraic Tools for Graph Computation) 🎥 Video
• 🛠️ Multiplex graph analysis with GraphBLAS (Graph Developer room @ FOSDEM 2019) by Gábor Szárnyas

Minisymposium at SIAM CSE'21: GraphBLAS: Tools, Algorithms, and Applications

• 🛠️ Sparse Matrices for Scaling Data-Intensive Problems on Distributed-Memory Systems by Aydın Buluç
• 🔧 SuiteSparse:GraphBLAS, a Parallel Implementation of the GraphBLAS API by Tim Davis
• 🔧 Lagraph: Graph Algorithms as Linear Algebra by Scott McMillan
• 🛠️ Vertex Centric and/or Graphblas – Why Choose One? by Roger Pearce
• 🔧 Introduction to Pygraphblas by Michel Pelletier
• 🛠️ Bandwidth-Optimized Algorithms for Sparse Matrix-Matrix Multiplication by Ariful Azad
• 🔧 High-Performance Sparse Linear Algebra on NVIDIA GPUs with cuSPARSE by Federico Busato
• 🛠️ F-Dbscan: Fusing Dbscan with Accelerated Tree Traversal on GPUs by Andrey Prokopenko
• 🛠️ Implementing Graphblas Primitives on Distributed-Memory Systems by Ben Brock
• 🛠️ Dense Semiring Linear Algebra on Modern CUDA Hardware by Vijay Thakkar

Books

• Graph Algorithms in the Language of Linear Algebra (SIAM, 2011) by Jeremy Kepner and John R. Gilbert
  • This is the best reference on the topic of linear algebra-based graph processing. However, note that GraphBLAS effort was not yet started when this book was written. Therefore, there are some differences between the notation of GraphBLAS documents and the one used in this book.
• Mathematics of Big Data: Spreadsheets, Databases, Matrices, and Graphs (MIT Press, 2018) by Jeremy Kepner and Hayden Jananthan
  • An updated version of paper Mathematical Foundations of the GraphBLAS is reprinted in this book (Chapter 6, p81-113)
  • This book is currently the latest detailed reference on semiring-based computations, including graph algorithms. It also covers many other topics such as associative arrays. The book is not intended to be a GraphBLAS reference, but it can be used for providing a background in linear algebra (see e.g. Chapter 8, "Visualizing the Algebra of Associative Arrays").

Implementations

Core implementations

• SuiteSparse:GraphBLAS
  • GitHub repository
  • 🛠️ Algorithm 1000: SuiteSparse:GraphBLAS: Graph algorithms in the language of sparse linear algebra (preprint) (ACM Transactions on Mathematical Software, 2019) by Tim Davis
  • The SuiteSparse:GraphBLAS library is released both as an individual package and (less frequently) as part of SuiteSparse.
  • This library can be installed on Debian-based distributions with the libsuitesparse-dev package. For example, Ubuntu 20.04's default repository contains SuiteSparse:GraphBLAS 3.2.0.
• GraphBLAS Template Library (GBTL): C++ implementation (version 3.0 has been release in June 2020)
• GraphBLAST
  • GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU, preprint by Carl Yang, Aydın Buluç, John D. Owens
  • High-Performance Linear Algebra-based Graph Framework on the GPU (PhD dissertation, 2019) by Carl Yang

Other implementations

• IBM GraphBLAS: C++ implementation in approx. 6000 lines of code.
• GraphBLAS C99: "C99 prototype implementation of enough of GraphBLAS standard to run first two examples in Appendix A of the standard." Consists of <800 lines of code. Only supports vxm.
• GraphMat: linear algebra-based graph analytics framework prototype by Intel
  • GraphMat: High performance graph analytics made productive (VLDB 2015) by Narayanan Sundaram
  • GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms (IPDPS 2016) by Michael J. Anderson et al.
• EJML (Efficient Java Matrix Library): partial Java implementation
  • 🔧 A GraphBLAS implementation in pure Java (GRADES-NDA 2021) by Florentin Dörre et al.

Wrappers

• Python wrappers:
  • ⭐ pygraphblas: a Python wrapper for SuiteSparse:GraphBLAS aiming to provide a Pythonic AP
    • GraphBLAS Programmability: Python and MATLAB Interfaces by Tim Mattson, Michel Pelletier, Tim Davis (preprint)
  • ⭐ grblas: a Python wrapper for SuiteSparse:GraphBLAS with a new high-level syntax that provides a 1:1 mapping between the C API and Python
    • This library and all dependencies can be installed with conda for OS X and Linux
  • PyGB: a Python wrapper for GBTL
• SuiteSparseGraphBLAS.jl: a Julia wrapper for SuiteSparse:GraphBLAS
  • a fork aiming to provide a more Julian interface
• rustgraphblas: a Rust wrapper
• graphblas-java-native: a Java wrapper
  • artifact at the Maven Central
• MATLAB wrapper: built-in for SuiteSparse:GraphBLAS
• Docker containers on Docker Hub

See also the ongoing design of the GraphBLAS C++ API.

Related libraries

• RedisGraph
  • More pointers below
• Graphulo (built for Apache Accumulo)
  • More pointers below
• D4M
  • Repository
  • D4M.jl: Julia implementation
  • D4M.py: Python implementation
• pggraphblas: Postgres extension for using GraphBLAS
• Combinatorial BLAS (CombBLAS): "An extensible distributed-memory library offering a small but powerful set of linear algebraic operations specifically targeting graph analytics." Influences the development of GraphBLAS.
  • Aydın Buluç, John R. Gilbert: The Combinatorial BLAS: design, implementation, and applications, Int. J. High Perform. Comput. Appl. 2011 (paper entry at the publisher's site). This paper is referred to as a "strawman proposal" on GraphBLAS.org
  • Documentation
  • Presentation
• Viral B. Shah, Alan Edelman, Stefan Karpinski, Jeff Bezanson, Jeremy Kepner: Novel algebras for advanced analytics in Julia, HPEC 2013
  • Repository
• A Hybrid GraphBLAS in C++11: specification, design, implementation, and performance (a work-in-progress distributed C++11 GraphBLAS implementation)
  • A C++ GraphBLAS: specification, implementation, parallelisation, and evaluation (preprint 2020) by Albert-Jan Yzelman et al.
  • Poster by Albert-Jan Yzelman and W. J. Suijlen

RedisGraph

• Deep Dive into RedisGraph (RedisConf 2019) by Roi Lipman
  • Presentation
• Lower Latency Graph Queries in Cypher with Redis Graph (RedisConf 2018) by Roi Lipman and Tim Davis
  • GraphBLAS section
  • Presentation
• Evaluating Cypher queries and procedures as algebraic operations within RedisGraph (12th LDBC TUC, 2019) by Roi Lipman

Graphulo

• Graphulo: Graph Analytics in Apache Accumulo (Accumulo Summit 2016) by Vijay Gadepally, Timothy Weale, Dylan Hutchison, Jeremy Kepner
• Interacting with Accumulo and Graphulo using Julia/Python D4M (Accumulo Summit 2018) by Lauren Milechin, Hayden Jananthan, Vijay Gadepally, Jeremy Kepner
• Accumulo and the Convergence of Machine Learning, Big Data, and Supercomputing (Accumulo Summit 2017) by Jeremy Kepner
• Server-side Sparse Matrix Multiply in the Accumulo Database (HPEC 2015) by Dylan Hutchison, Jeremy Kepner, Vijay Gadepally, Adam Fuchs
• Using D4M for rapid prototyping of analytics for Apache Accumulo (Accumulo Summit 2015) by Vijay Gadepally, Lauren Edwards, Jeremy Kepner
• Graph Analytics expressed in GraphBLAS (2014) by Jeremy Kepner, Vijay Gadepally, Ben Miller

You can also find many papers, posters, and presentations in the Accumulo repository.

Events

year	IPDPS workshop	HPEC
2021	GrAPL 2021	HPEC 2021
2020	GrAPL 2020	HPEC 2020
2019	GrAPL 2019	HPEC 2019
2018	GABB 2018	HPEC 2018
2017	GABB 2017	HPEC 2017
2016	GABB 2016	HPEC 2016
2015	GABB 2015	HPEC 2015
2014	GABB 2014	HPEC 2014
2013	−	HPEC 2013

News, interviews, popular science

• GraphBLAS: Building Blocks For High Performance Graph Analytics – Berkeley Lab Researchers Contribute to GraphBLAS and Will Leverage it for Exascale Applications
• ACM's interview with Tim Davis
• First Person: Tim Davis, American Scientist
• The Applications of Matrices | What I wish my teachers told me way earlier (Networks segment) by Zach Star (2019)

Typesetting

The nicematrix LaTeX package can be used to typeset block matrices.

• Example TeX code

Related work

• graphblas-verif: Formal verification of the GraphBLAS C API implementation by Tim Davis using Frama-C/WP.
• LA3: A scalable link-and locality-aware linear algebra-based graph analytics system (VLDB 2018) by Yousuf Ahmad et al.
• Efficient Distributed Graph Analytics using Triply Compressed Sparse Format (CLUSTER 2019) by Mohammad Hasanzadeh Mofrad et al.
• MAGiQ – a GraphBLAS-based RDF query engine:
  • A Demonstration of MAGiQ: Matrix Algebra Approach for Solving RDF Graph Queries (demo at VLDB 2018) by Fuad Jamour, Ibrahim Abdelaziz, Panos Kalnis
  • Matrix Algebra Framework for Portable, Scalable and Efficient Query Engines for RDF Graphs (EuroSys 2019) by Fuad Jamour, Ibrahim Abdelaziz, Yuanzhao Chen, Panos Kalnis
  • Algorithms and Frameworks for Graph Analytics at Scale (PhD thesis, 2019) by Fuad Jamour
• Parallel and Scalable Sparse Basic Linear Algebra Subprograms (PhD thesis, 2015) by Weifeng Liu
• Density-Aware Linear Algebra in a Column-Oriented In-Memory Database System (PhD thesis, 2016) by David Kernert
• Connection of relational joins (join-project, projected join) and sparse matrix multiplication:
  • A relational approach to the compilation of sparse matrix programs (Euro-Par 1997) by Vladimir Kotlyar et al.
  • Faster join-projects and sparse matrix multiplications (ICDT 2009) by Rasmus Resen Amossen and Rasmus Pagh
  • Fast Join Project Query Evaluation using Matrix Multiplication (SIGMOD 2020) by Shaleen Deep et al.
  • SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra (VLDB 2020) by Yisu Remy Wang et al.
• Semiring Provenance over Graph Databases (USENIX Workshop on the Theory and Practice of Provenance 2018) by Yann Ramusat et al.
• Provenance-Based Algorithms for Rich Queries over Graph Databases (EDBT 2021) by Yann Ramusat et al.
• Querying Sparse Matrices for Information Retrieval (PhD thesis, 2012) by Roberto Cornacchia