6 ms·

Viewing Matrices and Probability as Graphs

245 points by _Microft 8y ago

bhl 8y ago
I do recall looking up the definition of 'bijection', and seeing that it slightly resembles a graph. As a generalization: so an n-dimensional tensor can be viewed as a weighted n-partite graph?
- Twisol 8y ago
  An n-partite graph has the problem that edges can still only connect two vertices at a time. I think you would also need to include hyper-edges (faces, solids, etc). The joint probabilities would be represented by these hyper-edges, and the bounding ("lower") edges represent progressively more marginal probabilities. Higher category theory studies these kinds of objects, so it wouldn't particularly surprise me. I wonder if simplicial complexes would work here? https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex
- yorwba 8y ago
  No, because the space of tensors of order n with k-dimensional arguments is k^n-dimensional, while a complete n-partite graph with partitions of size k has only nk(n-1)k/2 edges, which doesn't give you enough coefficients to uniquely identify a tensor if n > 2. You'd need a n-uniform n-partite hypergraph, where coefficients are assigned to n-tuples instead of pairs. So for a tensor of order 3, that would mean weighted triangles, which are somewhat hard to draw and everything gets less intuitive.
Twisol 8y ago
> [...] what do matrices corresponding to equivalence relations look like? Actually, the graphic under "Block matrices correspond to disconnected graphs" illustrates this for us already! (Just mentally replace all the non-zero entries with 1; the graphs structurally remain the same.) I initially thought it would be "a disconnected set of cliques", but we've already established that we're modeling rectangular matrices as bipartite graphs between the input and output spaces. Square matrices in particular can be considered to operate over the same vector space, so we could have more arbitrary graphs -- such as cliques.
michelpp 8y ago
There is an API formalizing this style of matrix/graph computation called GraphBLAS, coming soon to a language and database near you. Here is an easy to read but math focused introduction to the topic by Dr Jeremy Kepner Head and Founder of the MIT Lincoln Laboratory Supercomputing Center: http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release.pdf http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release....
- espeed 8y ago
  What do you mean "coming soon" -- GraphBLAS 2.3.0 was just released [1] -- it's been here! ;) [1] http://faculty.cse.tamu.edu/davis/GraphBLAS.html http://faculty.cse.tamu.edu/davis/GraphBLAS.html [2] http://graphblas.org http://graphblas.org For more context, depth, and previous discussions, see... https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&prefix&page=0&dateRange=all&type=all https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...
  - michelpp 8y ago
    It's true. I look forward to seeing more language bindings, like Python, Javascript, etc. I expect it will be soon. For my own GraphBLAS education I have been working on a PostgreSQL extension: https://github.com/michelp/pggraphblas https://github.com/michelp/pggraphblas
TuringNYC 8y ago
I like how the material was presented. Anyone know what program was used to create the illustrations -- these are fantastic for explanations!
- abnry 8y ago
  I believe they are hand drawn. Check out more posts on the blog, they are similarly wonderfully presented!
edflsafoiewq 8y ago
Re viewing matrices as graphs Under the usual matrices-as-linear-maps interpretation, a nxm matrix is a linear map from the free vector space on m elements to the free vector space on n elements, M : Vect(Y) -> Vect(X), where X and Y are as in the article. For a regular map of finite sets Y -> X, we can draw a picture showing how each element of Y goes to an element of X by drawing a bunch of dots for Y and a bunch of dots for X with an arrow from each dot in Y to its image in X. This is a directed bipartite graph where each dot in Y is the source of exactly one edge. How is a linear map, Vect(Y) -> Vect(X), different? Each element of Y goes not to a single element of X, but to a linear combination of elements of X. If y goes to a x1 + b x2, we can think of this as two arrows out of y, each one now being weighted, one arrow to x1 with weight a and one to x2 with weight b (considering edges with weight 0 to be non-existent if you like). This is the graph shown in the article. This interpretation shows why matrix multiplication is path composition. It's exactly analogous to how for the map of finite sets, you find the image of z by first following its arrow to y in Y, then following its arrow to x in X. Here you first follow z to all its images in Y, then you follow those to all their images in X. Relation composition is only a special case. And of course the connection between XxY->R and Vect(Y)->Vect(X) is the usual correspondence between a rank (1,1) tensor and a linear map. Re probabilities: this corresponds to imagining a random process that transforms elements of Y into elements of X where y turns into x with probability p(x,y). The probability that you end up with x (the marginal probability) is the probability that any dot in Y transformed into x, ie. sum over all the arrows that wind up at x.
ironSkillet 8y ago
If you like this idea, also check out https://graphicallinearalgebra.net https://graphicallinearalgebra.net. It also describes fundamental linear algebra operations in terms of graphs, but with a slightly different flavor, and much more detail.
- blondin 8y ago
  thank you so much for sharing! this looks very interesting.
Cogito 8y ago
The semi-ring described at the end on Z_2 = {0,1} with the 'interesting' addition function where 1+1=1 might be more familiar here as Boolean logic, where: 0 -> False 1 -> True x -> AND + -> OR (a AND b)=True iff a=True and b=True; (axb)=1 iff a=1 and b=1 (a OR b)=False iff a=False and b=False; (a+b)=0 iff a=0 and b=0
CMCDragonkai 8y ago
There's also graphical linear algebra which takes matrices into a more category theory interpetation that is also visual: https://graphicallinearalgebra.net https://graphicallinearalgebra.net
leetrout 8y ago
Is there a typo in the header "Matrices with no nonzero entires correspond to complete bipartite graphs"?? Shouldn't it be "Matricies with all nonzero entries" or "Matricies with no zero entries"?
ajuc 8y ago
This seems related to the way graphs are often implement in code - https://en.wikipedia.org/wiki/Adjacency_matrix https://en.wikipedia.org/wiki/Adjacency_matrix Just in that case you can start with any graph, not necessarily bipartite, so you don't divide vertices into 2 sets X and Y, just use the same set of all vertices V twice, so the matrix is always square: V * V -> R I wonder if the properties from this article still hold on adjacency matrices. Would be very useful.
- edflsafoiewq 8y ago
  Yes, it's really the same graph. There really no difference between drawing two copies of V with arrows going from one to the other, and drawing one copy of V with arrows just staying in that copy. Either way, if you trace the arrows from a given vertex you will end up at the same spots. So for example the interpretation of matrix multiplication as path composition given here explains why the nth power of the adjacency matrix gives the number of length-n walks. (I think the precise relation is that if A the adjacency matrix for G, then if you draw the graph from this article for the matrix A, the adjacency matrix of that graph will be the block matrix 0 A A 0 That's assuming the edges in the article are regarded as undirected; if they are directed, just replace one of the As with 0.)
  - ajuc 8y ago
    Thanks. It's crazy to me that I've had graph theory on university, and many graph algorithms, and I don't remember ever hearing that multiplicating adjacency matrices have this properties. Maybe I just forgot about it. It would make some algorithms much easier :)
  - edflsafoiewq 8y ago
    Heh. No one noticed but that should have been 0 A^T A 0 In the matrix-as-arrows-from-dots-in-Y-to-dots-in-X picture, the transpose means "turn all the arrows around". This also explains the connection between the transpose and the categorical dual.
outlace 8y ago
There's a probability theory and associated software package that uses stochastic matrices for inference/conditioning/etc: https://efprob.cs.ru.nl/ https://efprob.cs.ru.nl/
lmeyerov 8y ago
A fun before and after for me was when trying to explore correlations over samples with a lot of features. In particular, on survey results on why teams adopt different programming languages: V1: Correlations as an interactive heatmap -- http://lmeyerov.github.io/projects/socioplt/viz/rank.html http://lmeyerov.github.io/projects/socioplt/viz/rank.html V2: Correlations as an interactive graph -- https://labs.graphistry.com/graph/graph.html?dataset=PyGraphistry%2FPC7D53HHS5 https://labs.graphistry.com/graph/graph.html?dataset=PyGraph... Nowadays when we're dealing with wide event data (security, fraud, operations, etc. investigations), even more fun!
mike_ivanov 8y ago
And vice versa. Take a graph, write it down as a matrix, apply a discrete Laplacian operator. Then - just as an example - find the number of distinct non-negative eigenvalues. This is exactly the number of connected components in the graph. Pure magic.
elbear 8y ago
I've been thinking about this lately. Specifically, I see a connection between systems theory and graph theory. My intuition tells me that all relationships between systems can be expressed as graphs. Can anyone confirm this? I'm not very familiar with either field, so I may be asking a basic question.
- ironSkillet 8y ago
  You would have to be more precise in describing what you mean by "all relationships between systems". A simple graph (meaning vertices and edges with no additional information) can encode the notions of a system and the existence of relationships between two systems, but without more structure you can't day much more. But this is already useful. If you have a big system you're trying to understand, a good first step is to draw a graph of the major components with edges indicating a dependency.
  - elbear 8y ago
    Systems interact through inputs and outputs, right? I mean, one system's output can be another system's input and even the second system's output can be the first one's input. I guess my question was if there's something that can't be described or modelled with graphs. As I said, my intuition is fuzzy, because I don't know much graph theory.
justAlittleCom 8y ago
It's funny because I could write a "viewing probability graphs as matrices" For me, probabilities are graphs, and matricess is just a way to represent those.
activatedgeek 8y ago
Given this seamless transition between linear algebra and graph theory, could someone summarize how exactly one or the other formulation helps to solve problems better? I wouldn't want to read up a huge list of things, just trying to get a sense of what's being achieved by this kind of (re)formulation.
- sjg007 8y ago
  See Bayesian networks, Markov chains...
cpburns2009 8y ago
I'm not following. Why are M12 and M31 ignored in the first example, and why are only edges given values while vertices coordinates are ignored?

245 points by _Microft 8y ago

bhl 8y ago

I do recall looking up the definition of 'bijection', and seeing that it slightly resembles a graph. As a generalization: so an n-dimensional tensor can be viewed as a weighted n-partite graph?

Twisol 8y ago
An n-partite graph has the problem that edges can still only connect two vertices at a time. I think you would also need to include hyper-edges (faces, solids, etc). The joint probabilities would be represented by these hyper-edges, and the bounding ("lower") edges represent progressively more marginal probabilities. Higher category theory studies these kinds of objects, so it wouldn't particularly surprise me. I wonder if simplicial complexes would work here? https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex
yorwba 8y ago
No, because the space of tensors of order n with k-dimensional arguments is k^n-dimensional, while a complete n-partite graph with partitions of size k has only nk(n-1)k/2 edges, which doesn't give you enough coefficients to uniquely identify a tensor if n > 2. You'd need a n-uniform n-partite hypergraph, where coefficients are assigned to n-tuples instead of pairs. So for a tensor of order 3, that would mean weighted triangles, which are somewhat hard to draw and everything gets less intuitive.

Twisol 8y ago

> [...] what do matrices corresponding to equivalence relations look like? Actually, the graphic under "Block matrices correspond to disconnected graphs" illustrates this for us already! (Just mentally replace all the non-zero entries with 1; the graphs structurally remain the same.) I initially thought it would be "a disconnected set of cliques", but we've already established that we're modeling rectangular matrices as bipartite graphs between the input and output spaces. Square matrices in particular can be considered to operate over the same vector space, so we could have more arbitrary graphs -- such as cliques.

michelpp 8y ago

There is an API formalizing this style of matrix/graph computation called GraphBLAS, coming soon to a language and database near you. Here is an easy to read but math focused introduction to the topic by Dr Jeremy Kepner Head and Founder of the MIT Lincoln Laboratory Supercomputing Center: http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release.pdf http://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release....

espeed 8y ago
What do you mean "coming soon" -- GraphBLAS 2.3.0 was just released [1] -- it's been here! ;) [1] http://faculty.cse.tamu.edu/davis/GraphBLAS.html http://faculty.cse.tamu.edu/davis/GraphBLAS.html [2] http://graphblas.org http://graphblas.org For more context, depth, and previous discussions, see... https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&prefix&page=0&dateRange=all&type=all https://hn.algolia.com/?query=GraphBLAS&sort=byPopularity&pr...
- michelpp 8y ago
  It's true. I look forward to seeing more language bindings, like Python, Javascript, etc. I expect it will be soon. For my own GraphBLAS education I have been working on a PostgreSQL extension: https://github.com/michelp/pggraphblas https://github.com/michelp/pggraphblas

TuringNYC 8y ago

I like how the material was presented. Anyone know what program was used to create the illustrations -- these are fantastic for explanations!

abnry 8y ago
I believe they are hand drawn. Check out more posts on the blog, they are similarly wonderfully presented!

edflsafoiewq 8y ago

Re viewing matrices as graphs Under the usual matrices-as-linear-maps interpretation, a nxm matrix is a linear map from the free vector space on m elements to the free vector space on n elements, M : Vect(Y) -> Vect(X), where X and Y are as in the article. For a regular map of finite sets Y -> X, we can draw a picture showing how each element of Y goes to an element of X by drawing a bunch of dots for Y and a bunch of dots for X with an arrow from each dot in Y to its image in X. This is a directed bipartite graph where each dot in Y is the source of exactly one edge. How is a linear map, Vect(Y) -> Vect(X), different? Each element of Y goes not to a single element of X, but to a linear combination of elements of X. If y goes to a x1 + b x2, we can think of this as two arrows out of y, each one now being weighted, one arrow to x1 with weight a and one to x2 with weight b (considering edges with weight 0 to be non-existent if you like). This is the graph shown in the article. This interpretation shows why matrix multiplication is path composition. It's exactly analogous to how for the map of finite sets, you find the image of z by first following its arrow to y in Y, then following its arrow to x in X. Here you first follow z to all its images in Y, then you follow those to all their images in X. Relation composition is only a special case. And of course the connection between XxY->R and Vect(Y)->Vect(X) is the usual correspondence between a rank (1,1) tensor and a linear map. Re probabilities: this corresponds to imagining a random process that transforms elements of Y into elements of X where y turns into x with probability p(x,y). The probability that you end up with x (the marginal probability) is the probability that any dot in Y transformed into x, ie. sum over all the arrows that wind up at x.

ironSkillet 8y ago

If you like this idea, also check out https://graphicallinearalgebra.net https://graphicallinearalgebra.net. It also describes fundamental linear algebra operations in terms of graphs, but with a slightly different flavor, and much more detail.

blondin 8y ago
thank you so much for sharing! this looks very interesting.

Cogito 8y ago

The semi-ring described at the end on Z_2 = {0,1} with the 'interesting' addition function where 1+1=1 might be more familiar here as Boolean logic, where: 0 -> False 1 -> True x -> AND + -> OR (a AND b)=True iff a=True and b=True; (axb)=1 iff a=1 and b=1 (a OR b)=False iff a=False and b=False; (a+b)=0 iff a=0 and b=0

CMCDragonkai 8y ago

There's also graphical linear algebra which takes matrices into a more category theory interpetation that is also visual: https://graphicallinearalgebra.net https://graphicallinearalgebra.net

leetrout 8y ago

Is there a typo in the header "Matrices with no nonzero entires correspond to complete bipartite graphs"?? Shouldn't it be "Matricies with all nonzero entries" or "Matricies with no zero entries"?

ajuc 8y ago

This seems related to the way graphs are often implement in code - https://en.wikipedia.org/wiki/Adjacency_matrix https://en.wikipedia.org/wiki/Adjacency_matrix Just in that case you can start with any graph, not necessarily bipartite, so you don't divide vertices into 2 sets X and Y, just use the same set of all vertices V twice, so the matrix is always square: V * V -> R I wonder if the properties from this article still hold on adjacency matrices. Would be very useful.

edflsafoiewq 8y ago
Yes, it's really the same graph. There really no difference between drawing two copies of V with arrows going from one to the other, and drawing one copy of V with arrows just staying in that copy. Either way, if you trace the arrows from a given vertex you will end up at the same spots. So for example the interpretation of matrix multiplication as path composition given here explains why the nth power of the adjacency matrix gives the number of length-n walks. (I think the precise relation is that if A the adjacency matrix for G, then if you draw the graph from this article for the matrix A, the adjacency matrix of that graph will be the block matrix 0 A A 0 That's assuming the edges in the article are regarded as undirected; if they are directed, just replace one of the As with 0.)
- ajuc 8y ago
  Thanks. It's crazy to me that I've had graph theory on university, and many graph algorithms, and I don't remember ever hearing that multiplicating adjacency matrices have this properties. Maybe I just forgot about it. It would make some algorithms much easier :)
- edflsafoiewq 8y ago
  Heh. No one noticed but that should have been 0 A^T A 0 In the matrix-as-arrows-from-dots-in-Y-to-dots-in-X picture, the transpose means "turn all the arrows around". This also explains the connection between the transpose and the categorical dual.

outlace 8y ago

There's a probability theory and associated software package that uses stochastic matrices for inference/conditioning/etc: https://efprob.cs.ru.nl/ https://efprob.cs.ru.nl/

lmeyerov 8y ago

A fun before and after for me was when trying to explore correlations over samples with a lot of features. In particular, on survey results on why teams adopt different programming languages: V1: Correlations as an interactive heatmap -- http://lmeyerov.github.io/projects/socioplt/viz/rank.html http://lmeyerov.github.io/projects/socioplt/viz/rank.html V2: Correlations as an interactive graph -- https://labs.graphistry.com/graph/graph.html?dataset=PyGraphistry%2FPC7D53HHS5 https://labs.graphistry.com/graph/graph.html?dataset=PyGraph... Nowadays when we're dealing with wide event data (security, fraud, operations, etc. investigations), even more fun!

mike_ivanov 8y ago

And vice versa. Take a graph, write it down as a matrix, apply a discrete Laplacian operator. Then - just as an example - find the number of distinct non-negative eigenvalues. This is exactly the number of connected components in the graph. Pure magic.

elbear 8y ago

I've been thinking about this lately. Specifically, I see a connection between systems theory and graph theory. My intuition tells me that all relationships between systems can be expressed as graphs. Can anyone confirm this? I'm not very familiar with either field, so I may be asking a basic question.

ironSkillet 8y ago
You would have to be more precise in describing what you mean by "all relationships between systems". A simple graph (meaning vertices and edges with no additional information) can encode the notions of a system and the existence of relationships between two systems, but without more structure you can't day much more. But this is already useful. If you have a big system you're trying to understand, a good first step is to draw a graph of the major components with edges indicating a dependency.
- elbear 8y ago
  Systems interact through inputs and outputs, right? I mean, one system's output can be another system's input and even the second system's output can be the first one's input. I guess my question was if there's something that can't be described or modelled with graphs. As I said, my intuition is fuzzy, because I don't know much graph theory.

justAlittleCom 8y ago

It's funny because I could write a "viewing probability graphs as matrices" For me, probabilities are graphs, and matricess is just a way to represent those.

activatedgeek 8y ago

Given this seamless transition between linear algebra and graph theory, could someone summarize how exactly one or the other formulation helps to solve problems better? I wouldn't want to read up a huge list of things, just trying to get a sense of what's being achieved by this kind of (re)formulation.

sjg007 8y ago
See Bayesian networks, Markov chains...

cpburns2009 8y ago

I'm not following. Why are M12 and M31 ignored in the first example, and why are only edges given values while vertices coordinates are ignored?