6 ms·

GraphBLAS – Graph algorithms in the language of linear algebra

289 points by johlo 6y ago

codecoinbot 6y ago
Shameless self promotion, I started a rust wrapper as my first project for GraphBLAS https://github.com/fabianmurariu/rustgraphblas https://github.com/fabianmurariu/rustgraphblas and a JNI wrapper https://github.com/fabianmurariu/graphblas-java-native https://github.com/fabianmurariu/graphblas-java-native They are not 100% complete, the JNI one is not published yet and only works on linux
mark_l_watson 6y ago
Sounds like a good idea with an added benefit that there are BLAS interfaces for many programming languages.
chrisseaton 6y ago
Is there a short example somewhere of what it looks like in practice?
- johlo 6y ago
  There are some examples in in the SuiteSparse implementation, https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/master/GraphBLAS/Demo https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/mast...
- ctchocula 6y ago
  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 https://github.com/gunrock/graphblast#usage
  - bubblethink 6y ago
    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.
    - ctchocula 6y ago
      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 https://dl.acm.org/doi/pdf/10.1145/3225058.3225122
    - DocSparse 6y ago
      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/Algorithm/LAGraph_bc_batch4.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_dnn.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_tricount.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside) https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_pagerank3f.c 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.
- FabHK 6y ago
  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-suitesparsegraphblas/ http://aldenmath.com/performance-of-the-matlab-interface-to-... http://aldenmath.com/a-matlab-interface-for-suitesparsegraphblas/ http://aldenmath.com/a-matlab-interface-for-suitesparsegraph... [1] http://faculty.cse.tamu.edu/davis/suitesparse.html http://faculty.cse.tamu.edu/davis/suitesparse.html
- hobofan 6y ago
  RedisGraph is a graph database that's built on top of GraphBLAS: https://github.com/RedisGraph/RedisGraph https://github.com/RedisGraph/RedisGraph
nimish 6y ago
Is there a treatment of graph algorithms in linear algebra from the basics anywhere?
- bubblethink 6y ago
  There is a book by the same title.
  - JadeNB 6y ago
    Graph algorithms in the language of linear algebra: https://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://epubs.siam.org/doi/book/10.1137/1.9780898719918 .
- FabHK 6y ago
  There's a few papers listed on Davis's GraphBLAS [1] site, this one might serve as an intro: http://faculty.cse.tamu.edu/davis/GraphBLAS_files/toms_graphblas.pdf http://faculty.cse.tamu.edu/davis/GraphBLAS_files/toms_graph... [1] http://faculty.cse.tamu.edu/davis/GraphBLAS.html http://faculty.cse.tamu.edu/davis/GraphBLAS.html
- andersource 6y ago
  Definitely not a comprehensive treatment, but I wrote about some specific use cases from the basics here: https://andersource.dev/2019/08/25/fun-with-matrix-exponentiation.html https://andersource.dev/2019/08/25/fun-with-matrix-exponenti...
- michelpp 6y ago
  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: https://github.com/michelp/pygraphblas/blob/master/pygraphblas/demo/Introduction-to-GraphBLAS-with-Python.ipynb https://github.com/michelp/pygraphblas/blob/master/pygraphbl... I also made a quick introduction video for a paper submission you can see here: https://www.youtube.com/watch?v=JUbXW_f03W0 https://www.youtube.com/watch?v=JUbXW_f03W0
FabHK 6y ago
This interview with Tim Davis has a bit of background information. https://www.acm.org/articles/people-of-acm/2019/tim-davis https://www.acm.org/articles/people-of-acm/2019/tim-davis > 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."
- chrisaycock 6y ago
  >> 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." The author has an example of PageRank in C: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/Source/dpagerank.c https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... I assume his "single call" statement refers to the MATLAB version: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/MATLAB/dpagerank.m https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... for i = 1:20 r = ((c*r) * C) + a * sum (r) ; end The MATLAB interface uses overloaded operators and methods on a GraphBLAS matrix object.
  - DocSparse 6y ago
    I was referring to the PageRank_semiring in https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/5e569f2fcb0597b4ad3c60fca1a4ff8e938fd111/Demo/Source/dpagerank2.c#L348 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.
chrisaycock 6y ago
RedisGraph uses GraphBLAS: https://github.com/RedisGraph/RedisGraph/ https://github.com/RedisGraph/RedisGraph/ Their paper claims that computing with adjacency (sparse) matrices is more performant than alternatives: https://arxiv.org/pdf/1905.01294.pdf https://arxiv.org/pdf/1905.01294.pdf They compile queries written in Cypher (Neo4j's language) to operations in linear algebra. An example query is: MATCH (n:actor{name:"Nicolas Cage"})-[:act]->(m:movie)<-[:act]-(a:actor) RETURN a.name, m.title
- waffle_ss 6y ago
  Note that the Cypher support is incomplete, and missing features like multiple labels. https://oss.redislabs.com/redisgraph/cypher_support/ https://oss.redislabs.com/redisgraph/cypher_support/
szarnyasg 6y ago
I have created a tutorial slideshow on the theory of GraphBLAS with lots of examples and step-by-step illustrations: http://mit.bme.hu/~szarnyas/grb/graphblas-introduction.pdf http://mit.bme.hu/~szarnyas/grb/graphblas-introduction.pdf A shorter version of this tutorial was recorded at FOSDEM earlier this year: https://fosdem.org/2020/schedule/event/graphblas/ https://fosdem.org/2020/schedule/event/graphblas/ More papers/tutorials/libraries are listed at https://github.com/GraphBLAS/GraphBLAS-Pointers https://github.com/GraphBLAS/GraphBLAS-Pointers.
- ngcc_hk 6y ago
  Thanks and great
noobermin 6y ago
The reference is written in C apparently...
wrnr 6y ago
Is their a similar connection from algebra to hyper-graph (semantic graphs)?
- michelpp 6y ago
  Hypergraphs can be represented with Incidence Matrices https://en.wikipedia.org/wiki/Incidence_matrix https://en.wikipedia.org/wiki/Incidence_matrix the same algebra applies and GraphBLAS works well with them!
  - wrnr 6y ago
    Thanks, I get it, instead of using only 0 and 1, use the index to indicate which property, and the index is also a node in the graph.
amelius 6y ago
There is also a Python wrapper: https://github.com/michelp/pygraphblas https://github.com/michelp/pygraphblas
ajflores1604 6y ago
For those like me who prefer watching talks, Tim Davis presented for Redis a year or two ago. https://youtu.be/xnez6tloNSQ https://youtu.be/xnez6tloNSQ
ablmf 6y ago
Can you guys give some real world examples of what graphs algorithms people are actually using in applications?
- kayza 6y ago
  There is a talk by two Facebook engineers [0] where they talk about using graph partitioning to better distribute caching of data. [0]: https://m.youtube.com/watch?v=QHkhyY9atkE https://m.youtube.com/watch?v=QHkhyY9atkE
- deleted 6y ago
  [deleted]
- a_bonobo 6y ago
  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. For example, Canu, one of the more popular current assemblers for PacBio and MinION data, uses a best overlap graph https://genome.cshlp.org/content/27/5/722.long https://genome.cshlp.org/content/27/5/722.long
- fgdh 6y ago
  If you don’t mind the marketing aspect, there are some pretty good overviews in graphconnect (neo4j) conferences. https://m.youtube.com/watch?v=dW6JsFccdkM https://m.youtube.com/watch?v=dW6JsFccdkM

289 points by johlo 6y ago

Shameless self promotion, I started a rust wrapper as my first project for GraphBLAS https://github.com/fabianmurariu/rustgraphblas https://github.com/fabianmurariu/rustgraphblas and a JNI wrapper https://github.com/fabianmurariu/graphblas-java-native https://github.com/fabianmurariu/graphblas-java-native They are not 100% complete, the JNI one is not published yet and only works on linux

mark_l_watson 6y ago

Sounds like a good idea with an added benefit that there are BLAS interfaces for many programming languages.

chrisseaton 6y ago

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

johlo 6y ago
There are some examples in in the SuiteSparse implementation, https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/master/GraphBLAS/Demo https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/mast...
ctchocula 6y ago
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 https://github.com/gunrock/graphblast#usage
- bubblethink 6y ago
  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.
  - ctchocula 6y ago
    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 https://dl.acm.org/doi/pdf/10.1145/3225058.3225122
  - DocSparse 6y ago
    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/Algorithm/LAGraph_bc_batch4.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_dnn.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_tricount.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside) https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_pagerank3f.c 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.
FabHK 6y ago
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-suitesparsegraphblas/ http://aldenmath.com/performance-of-the-matlab-interface-to-... http://aldenmath.com/a-matlab-interface-for-suitesparsegraphblas/ http://aldenmath.com/a-matlab-interface-for-suitesparsegraph... [1] http://faculty.cse.tamu.edu/davis/suitesparse.html http://faculty.cse.tamu.edu/davis/suitesparse.html
hobofan 6y ago
RedisGraph is a graph database that's built on top of GraphBLAS: https://github.com/RedisGraph/RedisGraph https://github.com/RedisGraph/RedisGraph

nimish 6y ago

Is there a treatment of graph algorithms in linear algebra from the basics anywhere?

bubblethink 6y ago
There is a book by the same title.
- JadeNB 6y ago
  Graph algorithms in the language of linear algebra: https://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://epubs.siam.org/doi/book/10.1137/1.9780898719918 .
FabHK 6y ago
There's a few papers listed on Davis's GraphBLAS [1] site, this one might serve as an intro: http://faculty.cse.tamu.edu/davis/GraphBLAS_files/toms_graphblas.pdf http://faculty.cse.tamu.edu/davis/GraphBLAS_files/toms_graph... [1] http://faculty.cse.tamu.edu/davis/GraphBLAS.html http://faculty.cse.tamu.edu/davis/GraphBLAS.html
andersource 6y ago
Definitely not a comprehensive treatment, but I wrote about some specific use cases from the basics here: https://andersource.dev/2019/08/25/fun-with-matrix-exponentiation.html https://andersource.dev/2019/08/25/fun-with-matrix-exponenti...
michelpp 6y ago
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: https://github.com/michelp/pygraphblas/blob/master/pygraphblas/demo/Introduction-to-GraphBLAS-with-Python.ipynb https://github.com/michelp/pygraphblas/blob/master/pygraphbl... I also made a quick introduction video for a paper submission you can see here: https://www.youtube.com/watch?v=JUbXW_f03W0 https://www.youtube.com/watch?v=JUbXW_f03W0

FabHK 6y ago

This interview with Tim Davis has a bit of background information. https://www.acm.org/articles/people-of-acm/2019/tim-davis https://www.acm.org/articles/people-of-acm/2019/tim-davis > 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."

chrisaycock 6y ago
>> 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." The author has an example of PageRank in C: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/Source/dpagerank.c https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... I assume his "single call" statement refers to the MATLAB version: https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Demo/MATLAB/dpagerank.m https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable... for i = 1:20 r = ((c*r) * C) + a * sum (r) ; end The MATLAB interface uses overloaded operators and methods on a GraphBLAS matrix object.
- DocSparse 6y ago
  I was referring to the PageRank_semiring in https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/5e569f2fcb0597b4ad3c60fca1a4ff8e938fd111/Demo/Source/dpagerank2.c#L348 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.

chrisaycock 6y ago

RedisGraph uses GraphBLAS: https://github.com/RedisGraph/RedisGraph/ https://github.com/RedisGraph/RedisGraph/ Their paper claims that computing with adjacency (sparse) matrices is more performant than alternatives: https://arxiv.org/pdf/1905.01294.pdf https://arxiv.org/pdf/1905.01294.pdf They compile queries written in Cypher (Neo4j's language) to operations in linear algebra. An example query is: MATCH (n:actor{name:"Nicolas Cage"})-[:act]->(m:movie)<-[:act]-(a:actor) RETURN a.name, m.title

waffle_ss 6y ago
Note that the Cypher support is incomplete, and missing features like multiple labels. https://oss.redislabs.com/redisgraph/cypher_support/ https://oss.redislabs.com/redisgraph/cypher_support/

szarnyasg 6y ago

I have created a tutorial slideshow on the theory of GraphBLAS with lots of examples and step-by-step illustrations: http://mit.bme.hu/~szarnyas/grb/graphblas-introduction.pdf http://mit.bme.hu/~szarnyas/grb/graphblas-introduction.pdf A shorter version of this tutorial was recorded at FOSDEM earlier this year: https://fosdem.org/2020/schedule/event/graphblas/ https://fosdem.org/2020/schedule/event/graphblas/ More papers/tutorials/libraries are listed at https://github.com/GraphBLAS/GraphBLAS-Pointers https://github.com/GraphBLAS/GraphBLAS-Pointers.

ngcc_hk 6y ago
Thanks and great

noobermin 6y ago

The reference is written in C apparently...

wrnr 6y ago

Is their a similar connection from algebra to hyper-graph (semantic graphs)?

michelpp 6y ago
Hypergraphs can be represented with Incidence Matrices https://en.wikipedia.org/wiki/Incidence_matrix https://en.wikipedia.org/wiki/Incidence_matrix the same algebra applies and GraphBLAS works well with them!
- wrnr 6y ago
  Thanks, I get it, instead of using only 0 and 1, use the index to indicate which property, and the index is also a node in the graph.

amelius 6y ago

There is also a Python wrapper: https://github.com/michelp/pygraphblas https://github.com/michelp/pygraphblas

ajflores1604 6y ago

For those like me who prefer watching talks, Tim Davis presented for Redis a year or two ago. https://youtu.be/xnez6tloNSQ https://youtu.be/xnez6tloNSQ

ablmf 6y ago

Can you guys give some real world examples of what graphs algorithms people are actually using in applications?

kayza 6y ago
There is a talk by two Facebook engineers [0] where they talk about using graph partitioning to better distribute caching of data. [0]: https://m.youtube.com/watch?v=QHkhyY9atkE https://m.youtube.com/watch?v=QHkhyY9atkE
deleted 6y ago
[deleted]
a_bonobo 6y ago
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. For example, Canu, one of the more popular current assemblers for PacBio and MinION data, uses a best overlap graph https://genome.cshlp.org/content/27/5/722.long https://genome.cshlp.org/content/27/5/722.long
fgdh 6y ago
If you don’t mind the marketing aspect, there are some pretty good overviews in graphconnect (neo4j) conferences. https://m.youtube.com/watch?v=dW6JsFccdkM https://m.youtube.com/watch?v=dW6JsFccdkM