3 ms·

> Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.) George Box was very specifically talking ab

> 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.

jltsiren 3y ago
The model I was talking about is sometimes called a bidirected sequence graph. It's another member of a more general graph family de Bruijn graphs also belong to. In that model, nodes have separate sets of left edges and right edges, and the edges connect node sides rather than nodes. For example, there can be an edge between the right sides of two nodes. The edges are undirected, but you can't exit a node from the side you entered it. Alternatively, the edges become directed once you fix the orientation of the node visit. Then the successors of a node in one orientation are its predecessors in the other orientation. Some graph representations have an underlying directed graph with separate nodes for the two orientations, but that's an implementation detail people usually don't want to think about. The path-centric model can be thought as predicting the token preceding/following a context. Node D may have right edges to >E, <F, and >G, but if you are in context <B>C>D, only >E and <F are available. And if you extend the context to the left to >A<B>C>D, then your only option may be <F. This is a primitive operation that may be repeated a million times per CPU-second in a graph with hundreds of millions of nodes. You often don't know which extensions you are going to take until you have processed the sequences in the previous ones. Matrices are a useful model when you want to do similar things to most nodes in a graph. But when you are exploring the graph locally in an iterative fashion, it's more convenient to think about nodes and edges.

jltsiren 3y ago

The model I was talking about is sometimes called a bidirected sequence graph. It's another member of a more general graph family de Bruijn graphs also belong to. In that model, nodes have separate sets of left edges and right edges, and the edges connect node sides rather than nodes. For example, there can be an edge between the right sides of two nodes. The edges are undirected, but you can't exit a node from the side you entered it. Alternatively, the edges become directed once you fix the orientation of the node visit. Then the successors of a node in one orientation are its predecessors in the other orientation. Some graph representations have an underlying directed graph with separate nodes for the two orientations, but that's an implementation detail people usually don't want to think about. The path-centric model can be thought as predicting the token preceding/following a context. Node D may have right edges to >E, <F, and >G, but if you are in context <B>C>D, only >E and <F are available. And if you extend the context to the left to >A<B>C>D, then your only option may be <F. This is a primitive operation that may be repeated a million times per CPU-second in a graph with hundreds of millions of nodes. You often don't know which extensions you are going to take until you have processed the sequences in the previous ones. Matrices are a useful model when you want to do similar things to most nodes in a graph. But when you are exploring the graph locally in an iterative fashion, it's more convenient to think about nodes and edges.