Hacker News Reader

Comment by chrisseaton | Hacker News Reader

Is there a short example somewhere of what it looks like in practice?

Tim Davis, the developer of SuiteSparse [1], a library for calculating with sparse matrices, also developed a reference implementation of GraphBLAS. On his blog are a few short examples of how it looks when you call it from MATLAB:

http://aldenmath.com/performance-of-the-matlab-interface-to-...

http://aldenmath.com/a-matlab-interface-for-suitesparsegraph...

[1] http://faculty.cse.tamu.edu/davis/suitesparse.html

There's an example here showing you don't need to write a shortest path algorithm in terms of nodes and edges: https://github.com/gunrock/graphblast#usage

graphblas is nice in theory, but actual high performance code tends to be quite messy and not always easily encapsulated by graphblas. For example, if you want to store predecessors in SSSP, the semiring becomes quite involved, and not easily transferable to GPUs etc. And there are other other optimizations (direction optimizing BFS, delta stepping SSSP etc.) that are not really a part of the algorithmic specification which also break the encapsulation.

Give us time; we're still in the beginning stages of writing algorithms that use it. If you dig through LAGraph, you'll find lots of messy prototypes, as we experiment on various methods. Those are drafts, not polished results. Our most recent methods are polished, extremely simple, yet very fast:

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo...

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside)

https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo...

We're working on the GPU version, and all the built-in semirings very work nicely on the GPU. For user-defined semirings, we will need the user operators defined as strings containing C code. Then they can all be done on the GPU too.

People have shown that direction optimizing BFS fits very neatly inside graphblas actually [1]. Perhaps in a few years people will have figured out how to make delta stepping and storing predecessors fit too even if it's not clear at the moment.

For delta stepping, it seems all you would need is a priority queue that works in batches as opposed to individual elements. Then to make it performant and match delta stepping code written from scratch, you might need something that can fuse multiple graphblas operations together so that you don't have too many extra memory ops from the priority queue operations.

[1] https://dl.acm.org/doi/pdf/10.1145/3225058.3225122

There are some examples in in the SuiteSparse implementation, https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/mast...

RedisGraph is a graph database that's built on top of GraphBLAS: https://github.com/RedisGraph/RedisGraph

Reply on news.ycombinator.com