3 ms·

In the language of Linear Algebra, the type of a graph is a sparse matrix. Adjacency matrices can express simple directed and undirected graphs, and Incidence

In the language of Linear Algebra, the type of a graph is a sparse matrix. Adjacency matrices can express simple directed and undirected graphs, and Incidence matrices can express multi, hyper, and ubergraphs. The real power of using matrices for graphs is that you can use Linear Algebra to process them. Instead of "edge and node" thinking, LA brings the power of matrix multiplication and semirings to graph algorithms. Instead of working about edgelists, hashmaps of visited nodes, thread pools and when to fork or not to fork, by using a standard like the GraphBLAS you can just express an algorithm as a system of matrix operations, and the underlying library can choose how to run it, and on what hardware. For example, the current state of the art GraphBLAS implementation is SuiteSparse:GraphBLAS, has a JIT compiler that runs graph algorithms on a variety of CPUs and CUDA GPUs. The same sparse deep neural network inference code that is a few lines of Python can run on a chromebook all the way up to a large GPU system with no changes, the only difference is the size of the graph and the time it takes to process it. As graphs get into billions and trillions of edges, writing algorithms by hand that target different architectures gets extremely difficult and tedious. Future versions of SuiteSparse have a lot of exciting feature planned, including operation fusion and distributed processing. Retargeting hand written algorithms will be a thing of the past. One of the best parts about the GraphBLAS is that the graph really does have a "type" in the programming language sense, it's a Matrix, and the same operators and operations you expect to work are there. There is great support for both Julia and Python at the moment for beginners and data science oriented folks to dive in quickly. Here's an interesting paper on how to express centrality algorithms like PageRank and Triange Centrality (disclaimer: I am one of the paper authors): https://www.researchgate.net/publication/356707900_The_GraphBLAS_in_Julia_and_Python_the_PageRank_and_Triangle_Centralities https://www.researchgate.net/publication/356707900_The_Graph... I also created an introductory video some time ago explaining the very basic concepts: https://www.youtube.com/watch?v=JUbXW_f03W0 https://www.youtube.com/watch?v=JUbXW_f03W0

refulgentis 3y ago
Does it avoid the downsides of a matrix representation mentioned? The article responds to another, noting that there's inherent tradeoffs. ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes." (n.b. this flattens a lot of the interesting info in both articles into 'ah, matrix!" - open to that being true but it feels unlikely)
- michelpp 3y ago
  > ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes." The GraphBLAS is a sparse matrix library, it does not store the non-present values. Also, a non-present value may or may not be zero. For example in shortest path algorithms, the non present value is positive infinity.
jltsiren 3y ago
Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.) When I think of graphs, I usually think of ones used for representing the alignment of biological sequences. Nodes have two sides, left and right, and both sides have their own neighbors. A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left. Sometimes the graphs are path-centric. There is a fixed set of paths (or walks, if you prefer), and the graph is induced by them. The typical query is path extension: if you have already traversed >A<B>C>D, what are the possible left/right extensions according to the underlying paths matching the context. In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths. Matrices don't feel like a good abstraction for graphs like this. There are a number of representations for graphs like this, mostly differing by whether they are mutable or immutable, faster or more space-efficient, and graph-centric or path-centric. Generic algorithms use either node identifiers, which are consistent across graph representations, or opaque handles, which are representation-specific and often more efficient to use. Sometimes you select the representation according to the algorithm you want to use. Sometimes you select the algorithm according to the graph you already have (because conversions can be expensive). And sometimes you adjust the problem definition to reach something that can be computed efficiently with the available tools.
- michelpp 3y ago
  > Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.) George Box was very specifically talking about statistical models when he coined that aphorism. Matrices are linear algebra and graphs are graph theory, I find it hard to think they are not correct and useful models. > A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left. I'm not an expert in this field but I'm guessing you're talking about De Bruijn graphs, which can be very elegantly modeled with incidence matrices, here's an example of one using the GraphBLAS that downloads data from BioPython, loads it into incidence matrices and graphs it. This is just a simple example, SuiteSparse can handle many billions of edges: https://github.com/Graphegon/Graphony?tab=readme-ov-file#example-weighted-de-bruijn-using-biopython https://github.com/Graphegon/Graphony?tab=readme-ov-file#exa... Traversing bidirectionally is quite easy, the upper triangle of a matrix are the directed outgoing edges, and the lower triangle are the incoming. This style of "push/pull" optimization is common in the GraphBLAS. > In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths. Again if I understand you correctly, in the GraphBLAS this is accomplished by using accumulators and masks. During traversal data can be accumulated, with a stock operator or one you define, into a vector or matrix, and that object can be used to efficiently mask subsequent computations to avoid unnecessary work or determine when you've reached a termination condition. > Matrices don't feel like a good abstraction for graphs like this. Mathematically, graphs and matrices are isomorphic. Regardless of algorithm or storage format like edge lists, tuples or CSR, every graph is a matrix, and vice versa. And if you have a matrix, you have linear algebra to operate on it. Some people don't like Linear Algebra to operate on graphs, so I guess for them it is "not good", but on the other hand, it's Linear Algebra and Graph Theory, whose roots date back to the 2nd century BC, forward through great minds like Descartes and Euler, permeating every kind of math, science, physics and engineering discipline humans have ever created. That's a strong argument for its goodness. Now it is entirely possible, likely even, that the current SuiteSparse implementation doesn't have exactly the tool needed or maybe not the precise best storage format, but these missing pieces do not invalidate the underlying mathematical foundation that it's based on.

refulgentis 3y ago

Does it avoid the downsides of a matrix representation mentioned? The article responds to another, noting that there's inherent tradeoffs. ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes." (n.b. this flattens a lot of the interesting info in both articles into 'ah, matrix!" - open to that being true but it feels unlikely)

michelpp 3y ago
> ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes." The GraphBLAS is a sparse matrix library, it does not store the non-present values. Also, a non-present value may or may not be zero. For example in shortest path algorithms, the non present value is positive infinity.

jltsiren 3y ago

Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.) When I think of graphs, I usually think of ones used for representing the alignment of biological sequences. Nodes have two sides, left and right, and both sides have their own neighbors. A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left. Sometimes the graphs are path-centric. There is a fixed set of paths (or walks, if you prefer), and the graph is induced by them. The typical query is path extension: if you have already traversed >A<B>C>D, what are the possible left/right extensions according to the underlying paths matching the context. In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths. Matrices don't feel like a good abstraction for graphs like this. There are a number of representations for graphs like this, mostly differing by whether they are mutable or immutable, faster or more space-efficient, and graph-centric or path-centric. Generic algorithms use either node identifiers, which are consistent across graph representations, or opaque handles, which are representation-specific and often more efficient to use. Sometimes you select the representation according to the algorithm you want to use. Sometimes you select the algorithm according to the graph you already have (because conversions can be expensive). And sometimes you adjust the problem definition to reach something that can be computed efficiently with the available tools.

michelpp 3y ago
> Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.) George Box was very specifically talking about statistical models when he coined that aphorism. Matrices are linear algebra and graphs are graph theory, I find it hard to think they are not correct and useful models. > A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left. I'm not an expert in this field but I'm guessing you're talking about De Bruijn graphs, which can be very elegantly modeled with incidence matrices, here's an example of one using the GraphBLAS that downloads data from BioPython, loads it into incidence matrices and graphs it. This is just a simple example, SuiteSparse can handle many billions of edges: https://github.com/Graphegon/Graphony?tab=readme-ov-file#example-weighted-de-bruijn-using-biopython https://github.com/Graphegon/Graphony?tab=readme-ov-file#exa... Traversing bidirectionally is quite easy, the upper triangle of a matrix are the directed outgoing edges, and the lower triangle are the incoming. This style of "push/pull" optimization is common in the GraphBLAS. > In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths. Again if I understand you correctly, in the GraphBLAS this is accomplished by using accumulators and masks. During traversal data can be accumulated, with a stock operator or one you define, into a vector or matrix, and that object can be used to efficiently mask subsequent computations to avoid unnecessary work or determine when you've reached a termination condition. > Matrices don't feel like a good abstraction for graphs like this. Mathematically, graphs and matrices are isomorphic. Regardless of algorithm or storage format like edge lists, tuples or CSR, every graph is a matrix, and vice versa. And if you have a matrix, you have linear algebra to operate on it. Some people don't like Linear Algebra to operate on graphs, so I guess for them it is "not good", but on the other hand, it's Linear Algebra and Graph Theory, whose roots date back to the 2nd century BC, forward through great minds like Descartes and Euler, permeating every kind of math, science, physics and engineering discipline humans have ever created. That's a strong argument for its goodness. Now it is entirely possible, likely even, that the current SuiteSparse implementation doesn't have exactly the tool needed or maybe not the precise best storage format, but these missing pieces do not invalidate the underlying mathematical foundation that it's based on.