Skip to content

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

Notifications You must be signed in to change notification settings

GraphBLAS/GraphBLAS-Pointers

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 

Repository files navigation

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

Selected readings and presentations

GraphBLAS design papers

Tutorials

Specifications

Algorithms

Generic

Traversals, max-flow, and shortest paths

Connected components

Triangle counting, k-truss, clustering coefficient, etc.

Context-free path querying (CFPQ)

Community detection

Other

Presentations

Overviews on GraphBLAS and linear algebra-based graph processing

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").
  • Path Problems in Networks (Morgan & Claypool Publishers, 2010) by John S. Baras and George Theodorakopoulos.
    • This book is about the algebraic path problem – a semiring-based generalization of shortest path problem. The mathematical foundations of semiring-based graph analysis are described. Basic ideas to create new semirings to solve new problems are described.
    • The section 3.1 "Alternative viewpoints: paths and matrices" (p17-19) provides a matrix-based framework for the algebraic path problem which is highly relevant to GraphBLAS.
    • The table on pages 58-59 contains 29 different semirings and respective applied problems.

Implementations

Core implementations

Other implementations

Wrappers

See also the ongoing design of the GraphBLAS C++ API and its rgri reference implementation.

Related libraries

FalkorDB

RedisGraph

Graphulo

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

Events

year IPDPS workshop HPEC
2023 GrAPL 2023 HPEC 2023
2022 GrAPL 2022 HPEC 2022
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

Typesetting

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

Related work

Source code

The source of this page is available at https://github.com/GraphBLAS/GraphBLAS-Pointers.

About

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

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published