What is GraphBLAS? | Hacker News Reader

What is GraphBLAS?

aldenmath.com

54 pointsespeed11 comments

Back in my heady grad school days I was working on the old "Texas" concepts proposal for C++. We published this paper:

    https://parasol.tamu.edu/~jarvi/papers/gpce07.pdf

Which used the 'concept map' feature to lower a flood-fill onto the Boost Graph library (BGL). What went unpublished was that we then lowered the PBGL (parallel BGL) onto a Fortran BLAS implementation. Then we ran image algorithms (usual spectral analysis stuff) on BGL on Fortran BLAS. It was lightning fast. In fact, the results were so good, we didn't publish them because it was too much work to explain how — with all the abstraction layers — it could be so fast. Good times.

Also see Prof Tim Davis recent interview with the ACM: https://www.acm.org/articles/people-of-acm/2019/tim-davis

Sorry if this is nonsense, are these semirings a form of "Kernel (linear algebra)"? They seem superficially similar at least, a normalized matrix which can serve as an operation applied stepwise to a larger dataset.

Here are are a couple good introductions to semirings:

https://www.youtube.com/watch?v=Gd_VT_Nj8Xw

https://www.youtube.com/watch?v=dluPFbuq6zs

Dr. Jeremy Kepner's paper is a good follow up read after those two quick videos:

http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release....

Hi Michel - You're working on a GraphBLAS Postgres implementation [0] -- here's an open question I've been pondering...

[0] Postgres GraphBLAS https://github.com/michelp/pggraphblas

Now that we have SOTA linear algebra models for graphs [1], logic [2] and the lambda calculus [3] that are being optimized for vectorized parallel compute on modern CPU/GPU/TPUs -- do we have the makings for a unified linear algebra model that obsoletes the relational algebra model in relational DBs?

[1] Graph Algorithms in the Language of Linear Algebra (2011) https://epubs.siam.org/doi/book/10.1137/1.9780898719918

Mathematical Foundations of the GraphBLAS (2016) https://arxiv.org/pdf/1606.05790.pdf

[2] A Linear Algebraic Approach to Datalog Evaluation (2017) [pdf] https://arxiv.org/abs/1608.00139

A Linear Algebraic Approach to Logic Programming (2018) https://www.imperial.ac.uk/media/imperial-college/faculty-of...

[3] Lineal: A linear-algebraic Lambda-calculus (2017) https://arxiv.org/pdf/quant-ph/0612199.pdf

The Vectorial λ-Calculus (2017) https://arxiv.org/pdf/1308.1138.pdf

Simple λΠ-interpreter for matrix computation (2017) http://cs242.stanford.edu/assets/projects/2017/nykh.pdf

Algebra and the Lambda Calculus https://people.csail.mit.edu/jaffer/lambda.txt

No, it's not nonsense at all. GraphBLAS does rely on semirings on sparse matrices, so it does use linear matrix algebra. But it doesn't use or compute a kernel explicitly.

A kernel is a vector x so that Ax = 0. There are places where y<m> = Ax = 0 is useful to compute (m is a mask, like a bulk-if statement, where y(i) is modified only if m(i)=1). If x is a set of nodes then A'x is the set union of the neighbors of x (assuming A(i,j) is the edge (i,j), which is typical but not required). Then if x has no neighbors in the set m, then y = 0. I use this in the GraphBLAS implementation of Luby's independent set algorithm (in my Demo/ folder of SuiteSparse/GraphBLAS).

There are lots of connections between linear algebra and graph theory. In this case, the idea of a kernel does find its place in a graph algorithm, but it's a special case. It's not something that appears everywhere in every graph algorithm.

Has anyone tried to compile GraphBLAS via emscripten [1] and have it running on wasm [2]?

[1] https://emscripten.org

[2] https://webassembly.org

sounds like a pretty cool idea!

How do these dense linear algebra oriented implementations differ with stack-oriented algorithms, like in https://github.com/chen0040/lua-graph ?

Nitpick: The article talks about sparse linear algebra (rather than dense) by modeling a graph traversal as a sparse matrix-vector multiplication. The sparse matrix represents the adjacency matrix of the graph, and the vector represents the subset of vertices that are currently "active" (you can think of an active vertex as being in the workqueue for a breadth-first-search).

I haven't tried benchmarking Prof. Davis's GraphBLAS implementation myself against the one you linked to. My intuition would be that the GraphBLAS one is faster for larger graphs, because it uses data structures like CSR (compressed sparse row) [1], which are heavily optimized for processing static graphs (i.e. graphs that are not very amenable to adding vertices or edges). Based on the code examples on the first page, lua-graph seems more focused on small, dynamic graphs where the user can easily add vertices and edges. Short answer: they target different sets of applications. GraphBLAS is faster for processing large, static graphs with |V| and |E| in the millions or billions. lua-graph perhaps more flexible and handles dynamic graphs.

[1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...

GraphBLAS uses sparse matrices internally, and the API assumes a sparse format. The data structure is opaque, however, so if I want, I could use dense matrices if it's faster (and there are times when that's faster; see for example the vector v in the push/pull BFS in LAGraph, at https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... ). However, I don't switch to dense matrices automatically yet.

SuiteSparse:GraphBLAS does have a fast incremental update mechanism, but it's not (yet) as flexible as other approaches. But the beauty of GraphBLAS is that the data structure is entirely opaque to the user, so if a library implementor such as myself wants to plunk in an entire new one, then the user code that relies on GraphBLAS doesn't change. It would be possible, even, to use lua-graph internally (or anything else, license permitting), and then to select the fastest format for the problem at hand. Or, lua-graph (or any graph library) could be augmented to support a GraphBLAS API to its functionality.

Currently, SuiteSparse:GraphBLAS has four matrix formats: CSR, CSC, hypersparse CSR, and hypersparse CSC. The CSR and CSC formats take O(|V|+|E|) space, and the hypersparse formats take O(|E|) space. Hypersparse matrices arise in some problems, and subgraphs are often hypersparse. In the future, I would like to add a CSB format as well. I select between standard and hypersparse formats automatically. The default is CSR and I don't pick CSC automatically. In some cases, it would make sense to hold the matrix in both CSR and CSC formats, simultaneously, thus allowing fast access to both the in- and out-adjacency lists at the same time (at the cost of double the memory). I don't do that yet, however.

Reply on news.ycombinator.com