> I picked Gaussian elimination. "That will be quick," I thought. Not! I got started on matrices in 1985 and I'm not done with Gaussian elimination yet.
> GraphBLAS is a community effort, including industry, academics, and government labs, that is working to design a library that can implement graph algorithms based on sparse linear algebra over semirings. There are lots of great graph libraries out there that don't exploit the linear algebraic abstraction, but most of what they do can be viewed as matrix operations on adjacency matrices. GraphBLAS makes the connection to linear algebra explicit.
> GraphBLAS gives the graph algorithm developer the power and abstraction of linear algebra, with all its advantages (associative and distributive laws, AB=(B'A')', and so on). One level of breadth-first search, for example, is a single sparse matrix-times-sparse vector multiply, with no loss of asymptotic efficiency. Google's entire PageRank computation can be done with a handful of iterations around a single call to GraphBLAS, using what I call the "PageRank semiring."
>> Google's entire PageRank computation can be done with a handful of iterations around a single call to GraphBLAS, using what I call the "PageRank semiring."
I was referring to the PageRank_semiring in https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/5e569f... . I wasn't counting the test for the termination condition -- in the statement in my interview, I assumed the # of iterations could just be given. I would guess that's the case for the Google PageRank computation, since the graph doesn't change so much each month when they compute it, they probably know how many iterations they need.
pygraphblas author here, here is a good notebook introduction to the very basics of GraphBLAS with Python. The concepts carry naturally to the C API as well:
I'm a graph theorist, and I spend a lot of time on various optimization problems (matchings, packings, coverings, Steiner trees, etc) doing VLSI. AFAICT, it seems like GraphBLAS is geared for information processing about data stored in a graph representation, and doesn't approach the problems I need. Am I wrong?
Right now, the graphs I'm interested in are reasonably small (tens of thousands of edges), and my oldschool approaches are good enough, but if my employer's products continue their grow trajectory, we'll need to leverage GPUs and TPUs if at all possible. Should I be learning about GraphBLAS?
GraphBLAS is meant to solve graph problems (i.e., generally the sort of ones you are interested in, but more emphasis on parallel ones). Perhaps graph analytics may be closer to what it does right now rather than graph theory. At the very basic level, it exploits the matrix graph duality and casts graph problems as matrix problems. For eg., BFS and SSSP are sparse matrix vector multiplications over a suitably defined semiring. The benefit of this is that you can use high performance matrix libraries. The downside is that not everything can be done this way. At least not easily. You may find the book by Kepner and Gilbert useful. Also look at cugraph and gunrock for GPU based graph frameworks.
It's so early in this work that you might be the first person asking those specific questions. I'm no expert but I take it by VLSI you mean doing circuit routing and simulation and optimizing that topology. My gut tells me those would be good fits for the GraphBLAS.
If the base types don't suit your needs, you can always make your own. Tim Davis has talked about how he's made new types that are small nxn matrices as elements of a larger matrix. You can have complex, quaternion, or complex bags of stuff as matrix elements as long as you define the operators you need to work on those types.
Here's an example of using User Defined Types for a shortest path algorithm that also stores backlinks along the shortest path so the shortest path tree is materialized. in Python:
Shortest paths is definitely a big timesink... I'll definitely give that a shot. Thanks for the link :)
As for what I'm doing, I work at D-Wave and a lot of my work is on what can be thought of as "compilers" for our quantum computers. There's tons of similarity between my problem area and compilers for FPGAs, for example, so I call it VLSI because that's the right ballpark.
A lot of bioinformatics (my field) uses graph algorithms. DNA sequencing machines don't give you entire genomes, they give you pieces. Re-assembling the genome from those pieces is a prime graph algorithm target.
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:
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:
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.
A shorter version of this tutorial was recorded at FOSDEM earlier this year: https://fosdem.org/2020/schedule/event/graphblas/
More papers/tutorials/libraries are listed at https://github.com/GraphBLAS/GraphBLAS-Pointers.