[HN Gopher] GraphBLAS - Graph algorithms in the language of line...
___________________________________________________________________
GraphBLAS - Graph algorithms in the language of linear algebra
Author : johlo
Score : 87 points
Date : 2020-05-23 19:57 UTC (3 hours ago)
(HTM) web link (graphblas.org)
(TXT) w3m dump (graphblas.org)
| chrisseaton wrote:
| Is there a short example somewhere of what it looks like in
| practice?
| FabHK wrote:
| 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
| johlo wrote:
| There are some examples in in the SuiteSparse implementation,
| https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/mast...
| hobofan wrote:
| RedisGraph is a graph database that's built on top of
| GraphBLAS: https://github.com/RedisGraph/RedisGraph
| ctchocula wrote:
| 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
| bubblethink wrote:
| 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.
| DocSparse wrote:
| 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/Alg
| o...
|
| https://github.com/GraphBLAS/LAGraph/blob/master/Source/Alg
| o...
|
| https://github.com/GraphBLAS/LAGraph/blob/master/Source/Alg
| o... (that one has 6 algorithms inside)
|
| https://github.com/GraphBLAS/LAGraph/blob/master/Source/Alg
| o...
|
| 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.
| ctchocula wrote:
| 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
| szarnyasg wrote:
| 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
|
| 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.
| nimish wrote:
| Is there a treatment of graph algorithms in linear algebra from
| the basics anywhere?
| andersource wrote:
| 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-exponenti...
| michelpp wrote:
| 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/pygraphbl...
|
| I also made a quick introduction video for a paper submission
| you can see here:
|
| https://www.youtube.com/watch?v=JUbXW_f03W0
| boothby wrote:
| 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?
| bubblethink wrote:
| 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.
| boothby wrote:
| Time to hit the books, I guess. Thanks!
| bubblethink wrote:
| There is a book by the same title.
| FabHK wrote:
| 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_graph...
|
| [1] http://faculty.cse.tamu.edu/davis/GraphBLAS.html
| FabHK wrote:
| This interview with Tim Davis has a bit of background
| information.
|
| 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 wrote:
| >> _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...
|
| I assume his "single call" statement refers to the MATLAB
| version:
|
| 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 wrote:
| I was referring to the PageRank_semiring in https://github.co
| m/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.
| michelpp wrote:
| Here are two different PageRank approaches with pygraphblas:
|
| https://github.com/michelp/pygraphblas/blob/master/pygraphbl...
| chrisaycock wrote:
| RedisGraph uses GraphBLAS:
|
| 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
|
| 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
| mark_l_watson wrote:
| Sounds like a good idea with an added benefit that there are BLAS
| interfaces for many programming languages.
___________________________________________________________________
(page generated 2020-05-23 23:00 UTC)