Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Matrices and Graph

thepalindrome.org

Post reply on HN
Print view View original

11–20 of 47 posts

Re: Matrices and Graph

#11

Post by EsportToys »

aziis98 wrote: post #10
EsportToys wrote: post #9

Fun fact: this is only valid for domains that have a notion of "selfness", i.e. that there is such thing as an "identity matrix" for the quantities. Consider the following square matrix: TSLA APPL GOOG MSFT Alice | 100 5 0 1 Bob | 0 30 100 5 Carol | 2 2 2 2 Dan | 0 0 0 1000 An input vector of stock prices gives an output vector of net worths. However, that is about the only way you can use this matrix. You cannot tra…

Yeah, this is also the case if the table is not square as the values can't represent edges any more. So its more something like the rows and columns should index the same "thing". By the way by changing the graph representation we can give meaning even to non square matrices as described in this article https://www.math3ma.com/blog/matrices-probability-graphs

I think the most common application is describing mesh connectivity in Finite Element Methods, where each entry in the matrix represents the influence each node has on each other. Basically any N^2 table can be constructed to describe the general dependency of components in any simulation or systems in genera.

Re: Matrices and Graph

#12

Post by EsportToys »

dustingetz wrote: post #5

what book to read to develop these concepts and intuitions with engineering level of math (not proofs)?

I highly recommend anything in Finite Element Methods, it gives you an immediate grounding to a concrete application. I personally really benefitted a lot in the following YouTube lecture series:

https://www.math.colostate.edu/~bangerth/videos.html

Re: Matrices and Graph

#13

Post by aziis98 »

EsportToys wrote: post #11
aziis98 wrote: post #10

Earlier quoted context omitted.

Yeah, this is also the case if the table is not square as the values can't represent edges any more. So its more something like the rows and columns should index the same "thing". By the way by changing the graph representation we can give meaning even to non square matrices as described in this article https://www.math3ma.com/blog/matrices-probability-graphs

I think the most common application is describing mesh connectivity in Finite Element Methods, where each entry in the matrix represents the influence each node has on each other. Basically any N^2 table can be constructed to describe the general dependency of components in any simulation or systems in genera.

Another notable example is the PageRank algorithm [0] where you consider the graph where nodes are web pages and edges are links between them and you can build an adjacency matrix of this graph and with this algorithm sort the pages based "popularity" (which pages have more links pointing to them intuitively)

Let's say that in most cases you have a graph and you consider the corresponding matrix. Doing the inverse is not as useful in practice except in some cases as explained in the article.

[0]: https://en.wikipedia.org/wiki/PageRank

Re: Matrices and Graph

#14

Post by mark_l_watson »

Beautifully done. I subscribe to the author’s Substack, lots of other really nice stuff there.

A little off topic, but this is just one more example of beautifully done content on Substack. I have seriously considered setting my freedom.to settings to only allow accessing HN, FB, Twitter, Mastodon, etc., 1 or 2 mornings a week, and that time would mostly be for ensuring that I was always subscribed to a few good Substack channels.

With the explosion of ‘tech stuff I should read’, I think I need a more extreme culling of what I spend my time on.

Re: Matrices and Graph

#15

Post by Scene_Cast2 »

Another interesting mapping is that a vector is (or can be thought of as) a discrete function (f(x) = ....) over an interval, a dot product of two vectors is a discrete integral product, and a matrix is a discrete scalar field.

I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?

Re: Matrices and Graph

#16

Post by shakow »

Scene_Cast2 wrote: post #15

Another interesting mapping is that a vector is (or can be thought of as) a discrete function (f(x) = ....) over an interval, a dot product of two vectors is a discrete integral product, and a matrix is a discrete scalar field. I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?

A bivariate function?

Re: Matrices and Graph

#17

Post by lukburchard »

dustingetz wrote: post #5

what book to read to develop these concepts and intuitions with engineering level of math (not proofs)?

There is a book I would like to recommend, as it was not mentioned. The book "Graph algorithms in the language of linear algebra"[1] gives an overview and intuition of different graph algorithms expressed in linear algebra using semirings. The concept of expressing graphs as adjacency matrices (or incidence matrices) is quite old and was already noted by Koenig[4][5]. I remember the duality was used in some proofs and algorithms while doing my CS degree, e.g., see the Floyd–Warshall algorithm. One advantage of using linear algebra, apart from the beauty of it, is that naturally, vectorization and parallelization strategies become easier to implement. In practice, sparse linear algebra is used to reduce space and computational complexity. This is done by storing the matrices in compressed formats, such as COO/CSR/ELLPack.

In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]).

References:

[1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011.

[2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509.

[3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51.

[4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai Lapok, 38:116–119, 1931.

[5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.

Re: Matrices and Graph

#18

Post by enriquto »

Scene_Cast2 wrote: post #15

Another interesting mapping is that a vector is (or can be thought of as) a discrete function (f(x) = ....) over an interval, a dot product of two vectors is a discrete integral product, and a matrix is a discrete scalar field. I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?

> I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?

Exactly!

The correspondence between manifolds and graphs is very beautiful. What many folks call today "graph signal processing" has traditionally been called "discrete differential geometry". Scalar fields are functions defined on vertices, vector fields are functions defined on edges, the incidence matrix is the gradient operator, its transpose is the divergence, the Laplacian is the divergence of the gradient, integrals and fluxes are scalar products by indicator functions, the boundary operator is minus the gradient, Green's formula is just matrix transposition, etc.

You can even go further in the analogy and define p-forms as functions defined on the p-cliques of the graph, and from that rebuild a whole discrete Hodge theory. The correspondence is almost perfect, except for the fact that you cannot write easily the product rule for derivatives (because you cannot multiply pointwise scalar fields with vector fields).

Re: Matrices and Graph

#20

Post by derbOac »

EsportToys wrote: post #9

Fun fact: this is only valid for domains that have a notion of "selfness", i.e. that there is such thing as an "identity matrix" for the quantities. Consider the following square matrix: TSLA APPL GOOG MSFT Alice | 100 5 0 1 Bob | 0 30 100 5 Carol | 2 2 2 2 Dan | 0 0 0 1000 An input vector of stock prices gives an output vector of net worths. However, that is about the only way you can use this matrix. You cannot tra…

You make a good point about types of matrices that a graph representation makes sense with but it seems a bit much to say that PCA is pseudoscience?

If you had a lot of people and a lot of stocks, a low-rank representation of the matrix (probably not PCA per se with that particular matrix, but something closely related) could convey a lot of information about, e.g., submarkets and how they're valuated together. Or not, depending on how those prices covary over time.

Post reply on HN