5 ms·
Show HN: Graph Processing with Python and GraphBLAS
- enriquto 7y agoVery interesting, didn't know about graphblas! Does anybody here know about the advantages with respect to scipy.sparse ? Does scipy.sparse use graphblas internally?
- michelpp 7y agopygraphblas author here. scipy.sparse and graphblas are superficially similar in that they provide a sparse matrix type, but scipy.sparse is oriented more toward mathematical matrix computation and provides a wonderful and huge bag of tools to work with, for example, solving and doing LU decomposition, see scipy.sparse.linalg. graphblas provides a different bag of tools oriented toward solving graph problems, primarily around semirings and custom graph element operation. I don't think scipy.sparse, for example, provides a means for plugging in different semiring operations for computing shortest paths or max flow. On the other hand, graphblas does not provide decomposition or solving algorithms like scipy.sparse does. It is my goal to make it so that scipy.sparse matrices, dense numpy matrices, and networkX graphs can be interchangeable used with pygraphblas in the most reasonably efficient way. This way we get all the tools in both bags. Would love to chat with more scipy developers to see where there can be unification. UPDATE: it looks like there is some support for graph solving with scipy.sparse.csgraph, would be interesting to see how these compare to GraphBLAS based approaches!
- espeed 7y agoTim Davis also wrote the underlying code for much of scipy.sparse (his code is underneath almost all sparse matrix libs [1]). See... [1] Tim Davis Research http://faculty.cse.tamu.edu/davis/research.html http://faculty.cse.tamu.edu/davis/research.html
- enriquto 7y agoOh, what a man! He's also the author of the legendary CHOLMOD algorithm, probably one of the most used numerical algorithms ever, just after the FFT.
- refset 7y agoGraphBLAS is also the engine behind RedisGraph. Sparse adjacency matrices are interesting from a graph database perspective in particular because they are typically faster and more compact than the mainstream index-free adjacency systems (e.g. Neo4j).
- kuanbutts 7y agoInteresting - would be interested in a comparison between GraphBLAS (which I had not heard of until just now) and, for example, graph-tool's (https://graph-tool.skewed.de/ https://graph-tool.skewed.de/) underlying algorithms (Boost Graph Library).
- enriquto 7y agoIt seems that they serve very different purposes. Graphblas is mostly focused on the processing of real-valued functions defined on the vertices and edges of large-scale sparse graphs, and is optimized for this use case (think graphs with thousands of millions of vertices). The boost graph library is not tailored to numeric functions and it will probably be less efficient for this use case.
- kuanbutts 7y agoThanks! That's a helpful description.
- espeed 7y agoThere's a ton of previous threads over the last year with detailed descriptions and discussions... Search GraphBLAS https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&prefix&page=0&dateRange=all&type=all https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...
- laurencerowe 7y agoThis looks really interesting, potentially makes GraphBLAS much more accessible for exploratory work. A few questions for the author: Does this work in blocking or non-blocking mode? Naively I imagine there might be more opportunity for the GraphBLAS implementation to optimize execution in non-blocking mode. Is there a way to efficiently store and load matrices to and from files? Ideally in a such a way that the data is just mmap'ed or copied directly into memory on load? Does this only work with SuiteSparse or could it potentially work with a GPU implementation like https://github.com/gunrock/graphblast https://github.com/gunrock/graphblast too?
- michelpp 7y ago> Does this work in blocking or non-blocking mode? Naively I imagine there might be more opportunity for the GraphBLAS implementation to optimize execution in non-blocking mode. Non blocking mode. > Is there a way to efficiently store and load matrices to and from files? Ideally in a such a way that the data is just mmap'ed or copied directly into memory on load? The Matrix.from_mm and Matrix.to_mm methods will read and write files in the standard Matrix Market format. They are wrappers around the underlying LAGraph functions. > Does this only work with SuiteSparse or could it potentially work with a GPU implementation like https://github.com/gunrock/graphblast https://github.com/gunrock/graphblast too? It uses a lot of the GxB "extensions" that are to my knowledge only present in SuiteSparse. Investigating other implementations has been on my radar but not a high priority, certainly very open to getting PRs for helping with interchangeability!
- espeed 7y agoThe GraphBLAS GPU code is in the works [1]. For storage see the new RedisGraph 1.0 implementation released last year and 'michelp has a Python Postgres implementation in development. [1] Sparse versus dense in GraphBLAS: sometimes dense is better http://aldenmath.com/sparse-verses-dense-in-graphblas-sometimes-dense-is-better/ http://aldenmath.com/sparse-verses-dense-in-graphblas-someti... [2] RedisGraph: A Graph Database Module for Redis http://graphblas.org/?title=Graph_BLAS_Forum#Graph_analysis_systems_that_integrate_GraphBLAS http://graphblas.org/?title=Graph_BLAS_Forum#Graph_analysis_... [3] Graph Processing with Postgres and GraphBLAS https://news.ycombinator.com/item?id=19379800 https://news.ycombinator.com/item?id=19379800
- espeed 7y agoHi Michel - You've been busy with this and the Postgres lib. Good work. The Gremlin User Group has been working on a new universal graph DSL and compiler that can compile down to any of the graph backends. GraphBLAS has been part of the discussion since the start. An early draft of mm-ADT was just released last week... mm-ADT: A Multi-Model Abstract Data Type http://rredux.com/mm-adt/ http://rredux.com/mm-adt/
- michelpp 7y agoThanks espeed! I'll give this a read.
- dlphn___xyz 7y agovery cool