4 ms·

GraphBLAS

104 points by hui-zheng 4y ago

jim22k 4y ago
If you want to play around with SuiteSparse:GraphBLAS using Python, try python-graphblas (https://python-graphblas.readthedocs.io/ https://python-graphblas.readthedocs.io/). And this is a shameless plug. I'm one of the authors of the Python wrapper.
- DrewRWx 4y ago
  Whoa! That takes me back. During undergrad I did some work on the KDT Python wrapper for CombinatorialBLAS.
deleted 4y ago
[deleted]
collegeburner 4y ago
Feels good to see my school on here, Gig 'Em! (We need the consolation after that app state shitshow)
westurner 4y ago
> When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs Sparse matrix: https://en.wikipedia.org/wiki/Sparse_matrix https://en.wikipedia.org/wiki/Sparse_matrix : > The concept of sparsity is useful in combinatorics and application areas such as network theory and numerical analysis, which typically have a low density of significant data or connections. Large sparse matrices often appear in scientific or engineering applications when solving partial differential equations. CuGraph has a NetworkX-like API, though only so many of the networkx algorithms are yet reimplemented with some possible CUDA-optimizations. From https://github.com/rapidsai/cugraph https://github.com/rapidsai/cugraph : > cuGraph operates, at the Python layer, on GPU DataFrames, thereby allowing for seamless passing of data between ETL tasks in cuDF and machine learning tasks in cuML. Data scientists familiar with Python will quickly pick up how cuGraph integrates with the Pandas-like API of cuDF. Likewise, users familiar with NetworkX will quickly recognize the NetworkX-like API provided in cuGraph, with the goal to allow existing code to be ported with minimal effort into RAPIDS. > While the high-level cugraph python API provides an easy-to-use and familiar interface for data scientists that's consistent with other RAPIDS libraries in their workflow, some use cases require access to lower-level graph theory concepts. For these users, we provide an additional Python API called pylibcugraph, intended for applications that require a tighter integration with cuGraph at the Python layer with fewer dependencies. Users familiar with C/C++/CUDA and graph structures can access libcugraph and libcugraph_c for low level integration outside of python. /? sparse https://github.com/rapidsai/cugraph/search?q=sparse https://github.com/rapidsai/cugraph/search?q=sparse Pandas and scipy and IIRC NumPy have sparse methods; sparse.SparseArray, .sparse.; https://pandas.pydata.org/docs/user_guide/sparse.html#sparsearray https://pandas.pydata.org/docs/user_guide/sparse.html#sparse... From https://pandas.pydata.org/docs/user_guide/sparse.html#interaction-with-scipy-sparse https://pandas.pydata.org/docs/user_guide/sparse.html#intera... : > Series.sparse.to_coo() is implemented for transforming a Series with sparse values indexed by a MultiIndex to a scipy.sparse.coo_matrix. NetworkX graph algorithms reference docs https://networkx.org/documentation/stable/reference/algorithms/index.html https://networkx.org/documentation/stable/reference/algorith... NetworkX Compatibility > Differences in Algorithms https://docs.rapids.ai/api/cugraph/stable/basics/nx_transition.html#differences-in-algorithms https://docs.rapids.ai/api/cugraph/stable/basics/nx_transiti... List of algorithms > Combinatorial algorithms > Graph algorithms: https://en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms https://en.wikipedia.org/wiki/List_of_algorithms#Graph_algor...
- 7thaccount 4y ago
  To give an example of real world sparse matrices, power grids can have thousands and thousands of nodes, but most of those nodes only connect to a few other nodes at most that are local neighbors. Systems are highly sparse as a result
  - westurner 4y ago
    Integer factor graphs are sparse. https://en.wikipedia.org/wiki/Factor_graph#Message_passing_on_factor_graphs https://en.wikipedia.org/wiki/Factor_graph#Message_passing_o... Compared to the Powerset graph that includes all possible operators and parameter values and parentheses in infix but not Reverse Polish Notation, a correlation graph is sparse: most conditional probabilities should be expected to tend toward the Central Limit Theorem, so if you subtract (or substitute) a constant noise scalar, a factor graph should be extra-sparse. https://en.wikipedia.org/wiki/Central_limit_theorem_for_directional_statistics https://en.wikipedia.org/wiki/Central_limit_theorem_for_dire... What do you call a factor graph with probability distribution functions (PDFs) instead of float64s? Are Path graphs and Path graphs with cycles extra sparse? An adjacency matrix for all possible paths through a graph is also mostly zeroes. https://en.wikipedia.org/wiki/Path_graph https://en.wikipedia.org/wiki/Path_graph Methods of feature reduction use and affect the sparsity of a sparse matrix (that does not have elements for confounding variables). For example, from "Exploratory factor analysis (EFA) versus principal components analysis (PCA)" https://en.wikipedia.org/wiki/Factor_analysis https://en.wikipedia.org/wiki/Factor_analysis : > For either objective, it can be shown that the principal components are eigenvectors of the data's covariance matrix. Thus, the principal components are often computed by eigendecomposition of the data covariance matrix or singular value decomposition of the data matrix. PCA is the simplest of the true eigenvector-based multivariate analyses and is closely related to factor analysis. Factor analysis typically incorporates more domain specific assumptions about the underlying structure and solves eigenvectors of a slightly different matrix.
code_sam 4y ago
Another shameless plug, if you'd like to play around with SuiteSparse GraphBLAS using Rust, then you could try https://crates.io/crates/graphblas_sparse_linear_algebra https://crates.io/crates/graphblas_sparse_linear_algebra
deleted 4y ago
[deleted]
tiger_eye 4y ago
GraphBLAS is underrated and underused IMHO. If you use e.g. scipy.sparse, NetworkX, or similar, you should check out GraphBLAS. It is really fast even compared to scipy.sparse, and more capable in many ways. They've actually started implementing the NetworkX API https://github.com/python-graphblas/graphblas-algorithms https://github.com/python-graphblas/graphblas-algorithms with python-graphblas https://github.com/python-graphblas/python-graphblas https://github.com/python-graphblas/python-graphblas
tiger_eye 4y ago
To learn the latest about GraphBLAS, join the free online GraphBLAS session at HPEC next Tuesday: https://graphblas.org/hpec_bof.html https://graphblas.org/hpec_bof.html https://ieee-hpec.org/ https://ieee-hpec.org/ Also, these are probably better intro pages to GraphBLAS: https://graphblas.org/ https://graphblas.org/ https://graphblas.org/GraphBLAS-Pointers/ https://graphblas.org/GraphBLAS-Pointers/

104 points by hui-zheng 4y ago

If you want to play around with SuiteSparse:GraphBLAS using Python, try python-graphblas (https://python-graphblas.readthedocs.io/ https://python-graphblas.readthedocs.io/). And this is a shameless plug. I'm one of the authors of the Python wrapper.

DrewRWx 4y ago
Whoa! That takes me back. During undergrad I did some work on the KDT Python wrapper for CombinatorialBLAS.

deleted 4y ago

[deleted]

collegeburner 4y ago

Feels good to see my school on here, Gig 'Em! (We need the consolation after that app state shitshow)

westurner 4y ago

> When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs Sparse matrix: https://en.wikipedia.org/wiki/Sparse_matrix https://en.wikipedia.org/wiki/Sparse_matrix : > The concept of sparsity is useful in combinatorics and application areas such as network theory and numerical analysis, which typically have a low density of significant data or connections. Large sparse matrices often appear in scientific or engineering applications when solving partial differential equations. CuGraph has a NetworkX-like API, though only so many of the networkx algorithms are yet reimplemented with some possible CUDA-optimizations. From https://github.com/rapidsai/cugraph https://github.com/rapidsai/cugraph : > cuGraph operates, at the Python layer, on GPU DataFrames, thereby allowing for seamless passing of data between ETL tasks in cuDF and machine learning tasks in cuML. Data scientists familiar with Python will quickly pick up how cuGraph integrates with the Pandas-like API of cuDF. Likewise, users familiar with NetworkX will quickly recognize the NetworkX-like API provided in cuGraph, with the goal to allow existing code to be ported with minimal effort into RAPIDS. > While the high-level cugraph python API provides an easy-to-use and familiar interface for data scientists that's consistent with other RAPIDS libraries in their workflow, some use cases require access to lower-level graph theory concepts. For these users, we provide an additional Python API called pylibcugraph, intended for applications that require a tighter integration with cuGraph at the Python layer with fewer dependencies. Users familiar with C/C++/CUDA and graph structures can access libcugraph and libcugraph_c for low level integration outside of python. /? sparse https://github.com/rapidsai/cugraph/search?q=sparse https://github.com/rapidsai/cugraph/search?q=sparse Pandas and scipy and IIRC NumPy have sparse methods; sparse.SparseArray, .sparse.; https://pandas.pydata.org/docs/user_guide/sparse.html#sparsearray https://pandas.pydata.org/docs/user_guide/sparse.html#sparse... From https://pandas.pydata.org/docs/user_guide/sparse.html#interaction-with-scipy-sparse https://pandas.pydata.org/docs/user_guide/sparse.html#intera... : > Series.sparse.to_coo() is implemented for transforming a Series with sparse values indexed by a MultiIndex to a scipy.sparse.coo_matrix. NetworkX graph algorithms reference docs https://networkx.org/documentation/stable/reference/algorithms/index.html https://networkx.org/documentation/stable/reference/algorith... NetworkX Compatibility > Differences in Algorithms https://docs.rapids.ai/api/cugraph/stable/basics/nx_transition.html#differences-in-algorithms https://docs.rapids.ai/api/cugraph/stable/basics/nx_transiti... List of algorithms > Combinatorial algorithms > Graph algorithms: https://en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms https://en.wikipedia.org/wiki/List_of_algorithms#Graph_algor...

7thaccount 4y ago
To give an example of real world sparse matrices, power grids can have thousands and thousands of nodes, but most of those nodes only connect to a few other nodes at most that are local neighbors. Systems are highly sparse as a result
- westurner 4y ago
  Integer factor graphs are sparse. https://en.wikipedia.org/wiki/Factor_graph#Message_passing_on_factor_graphs https://en.wikipedia.org/wiki/Factor_graph#Message_passing_o... Compared to the Powerset graph that includes all possible operators and parameter values and parentheses in infix but not Reverse Polish Notation, a correlation graph is sparse: most conditional probabilities should be expected to tend toward the Central Limit Theorem, so if you subtract (or substitute) a constant noise scalar, a factor graph should be extra-sparse. https://en.wikipedia.org/wiki/Central_limit_theorem_for_directional_statistics https://en.wikipedia.org/wiki/Central_limit_theorem_for_dire... What do you call a factor graph with probability distribution functions (PDFs) instead of float64s? Are Path graphs and Path graphs with cycles extra sparse? An adjacency matrix for all possible paths through a graph is also mostly zeroes. https://en.wikipedia.org/wiki/Path_graph https://en.wikipedia.org/wiki/Path_graph Methods of feature reduction use and affect the sparsity of a sparse matrix (that does not have elements for confounding variables). For example, from "Exploratory factor analysis (EFA) versus principal components analysis (PCA)" https://en.wikipedia.org/wiki/Factor_analysis https://en.wikipedia.org/wiki/Factor_analysis : > For either objective, it can be shown that the principal components are eigenvectors of the data's covariance matrix. Thus, the principal components are often computed by eigendecomposition of the data covariance matrix or singular value decomposition of the data matrix. PCA is the simplest of the true eigenvector-based multivariate analyses and is closely related to factor analysis. Factor analysis typically incorporates more domain specific assumptions about the underlying structure and solves eigenvectors of a slightly different matrix.

code_sam 4y ago

Another shameless plug, if you'd like to play around with SuiteSparse GraphBLAS using Rust, then you could try https://crates.io/crates/graphblas_sparse_linear_algebra https://crates.io/crates/graphblas_sparse_linear_algebra

deleted 4y ago

[deleted]

tiger_eye 4y ago

GraphBLAS is underrated and underused IMHO. If you use e.g. scipy.sparse, NetworkX, or similar, you should check out GraphBLAS. It is really fast even compared to scipy.sparse, and more capable in many ways. They've actually started implementing the NetworkX API https://github.com/python-graphblas/graphblas-algorithms https://github.com/python-graphblas/graphblas-algorithms with python-graphblas https://github.com/python-graphblas/python-graphblas https://github.com/python-graphblas/python-graphblas

tiger_eye 4y ago

To learn the latest about GraphBLAS, join the free online GraphBLAS session at HPEC next Tuesday: https://graphblas.org/hpec_bof.html https://graphblas.org/hpec_bof.html https://ieee-hpec.org/ https://ieee-hpec.org/ Also, these are probably better intro pages to GraphBLAS: https://graphblas.org/ https://graphblas.org/ https://graphblas.org/GraphBLAS-Pointers/ https://graphblas.org/GraphBLAS-Pointers/