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

Graph Theory and Linear Algebra [pdf]

math.utah.edu

Post reply on HN
Print view View original

31–40 of 40 posts

Re: Graph Theory and Linear Algebra [pdf]

#31

Post by orange3xchicken »

Py-o7 wrote: post #16
actually_a_dog wrote: post #10

Earlier quoted context omitted.

You're right, of course. I should have said that the spectrum isn't all that useful for telling two graphs of the same order apart. Certain eigenvalues are frequently useful by themselves ( e.g. the largest, second largest, and smallest eigenvalues often contain some information). But, speaking of information, consider this: the adjacency matrix of a simple, loopless graph of order n is a symmetric n x n matrix with…

I don't understand why you are linking to something about labelled graphs when people are (presumably) trying to distinguish between graphs up to isomorphism i.e. after modd'ing out the labeling.

The term "labeled graph" just means a graph with each node labeled differently (but arbitrarily). It just allows for reasoning & enumerating the vertex set. It's a typical assumption to make in the context of graph isomorphism.

It doesn't relate to machine learning (which is what I assume you mean).

Re: Graph Theory and Linear Algebra [pdf]

#32

Post by dellamonica »

activatedgeek wrote: post #12

A question for the more informed: "What are recent developments in linear algebra?" Perhaps, we can broaden the scope and include numerical/randomized linear algebra. I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).

Linear Programming methods (barrier/simplex) have been able to run faster and solve larger instances in great part due to algorithmic advances (the other contribution being faster hardware, more memory etc). Considering that LP is a fundamental tool for mixed/integer programming, these improvements are incredibly valuable.

Gurobi had a white paper mentioning how much their solvers' performance was improved by which techniques (I'll link it here if I can find it).

Re: Graph Theory and Linear Algebra [pdf]

#34

Post by bmc7505 »

activatedgeek wrote: post #12

A question for the more informed: "What are recent developments in linear algebra?" Perhaps, we can broaden the scope and include numerical/randomized linear algebra. I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).

> "What are recent developments in linear algebra?"

Have you heard of geometric algebra? It takes a while to wrap your head around, but unifies a lot of mathematics in a very elegant way. For instance, you can view Euclidean geometry as a special case, and concepts like quaternions and rotations can be explained in a very natural way. There are a few good resources below if you're interested.

[0]: http://geometry.mrao.cam.ac.uk/2020/06/euclidean-geometry-an...

[1]: https://www.youtube.com/watch?v=ipqKvNHnABs

[2]: https://alexkritchevsky.com/2020/10/15/ea-operations.html

[3]: https://www.youtube.com/playlist?list=PLpzmRsG7u_gqaTo_vEseQ...

[4]: https://crypto.stanford.edu/~blynn/haskell/ga.html

[5]: https://bivector.net/

Re: Graph Theory and Linear Algebra [pdf]

#35

Post by gilleain »

orange3xchicken wrote: post #31
Py-o7 wrote: post #16

Earlier quoted context omitted.

I don't understand why you are linking to something about labelled graphs when people are (presumably) trying to distinguish between graphs up to isomorphism i.e. after modd'ing out the labeling.

The term "labeled graph" just means a graph with each node labeled differently (but arbitrarily). It just allows for reasoning & enumerating the vertex set. It's a typical assumption to make in the context of graph isomorphism. It doesn't relate to machine learning (which is what I assume you mean).

Isomorphism of a pair of graphs usually refers to isomorphism of their unlabelled equivalents.

Yes the concrete expression of the isomorphism would be as a mapping between the labels.

Given that the paper linked to is by Brendan McKay et al, it seems reasonable to mention that nAUTy works by finding (efficiently) all permutations of the labellings that result in an automorphism of the graph.

Re: Graph Theory and Linear Algebra [pdf]

#36

Post by faizshah »

dpflan wrote: post #2

Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…

Related: There’s a really good book called “Graph Algorithms in the Language of Linear Algebra” if you’re interested in GRAPHBLAS related topics.

Re: Graph Theory and Linear Algebra [pdf]

#37

Post by dpflan »

OccamsRazr wrote: post #30
dpflan wrote: post #2

Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…

> Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? I mean, this is a link to a pdf titled "chapter 3" buried deep in the directories of someone's academic homepage. There's no context about who the author is (is it a student project from a course? Part of a dissertation? notes for a draft of a book?), except that I think I can extract their name from the URL. It's pretty hard to…

I think the desired audience is the student, professor, and students' peers in University of Utah's MATH 2270 Linear Algebra class. If you walk up the URL, the context presents itself more.

https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017...

And true, these projects have limitations/constraints, and I am happy that the author took LA and learned more about LA and Graph Theory. I didn't know what to expect, but assumed Graphs + LA ==> Let's talk about spectral graph theory -- well, because I hoped for it.

Re: Graph Theory and Linear Algebra [pdf]

#38

Post by achr2 »

galaxyLogic wrote: post #21

What I'm interested to learn more about is Hypergraphs. They basically seem like a more real-world thing than basic graphs. Yes social networks are graphs but think about electrical circuits. They are hyper-graphs. See the picture of an electrical circuit in: https://en.wikipedia.org/wiki/Hypergraph How does Linear Algebra deal with Hypergraphs?

Interesting. I write a lot of code that deals with graphs in engineering data (pipelines, circuits, etc.). And typically I use the somewhat reverse logic to this, which is having 'hyper' vertices, i.e. a vertex can be a grouping of vertices.

Re: Graph Theory and Linear Algebra [pdf]

#39

Post by headsupftw »

Syzygies wrote: post #23
azxd123 wrote: post #19

Can someone please explain to me why there are 17 paths of length 4 between v1 (1) and itself.

If you're checking that 17 isn't a typo, do a screen grab and doodle on the graph. For each vertex, write down how many ways you can get there in two steps from v1. There are the same number of ways to get back, so you sum the square of these numbers. That's the dot product (3,1,1,1,1,2) with itself, 9+1+1+1+1+4 = 17. The (1,1) entry of the matrix multiplication of A^2 with itself is exactly this calculation. Matrix…

"how many ways you can get there in two steps from v1" If it's not obvious, v1=3, v2=1, v3=1, v4=1, v5=1, v7=2.

Re: Graph Theory and Linear Algebra [pdf]

#40

Post by headsupftw »

ogogmad wrote: post #26

This document has mistakes. The consequences of Theorem 2.2 are wrong as stated. Substitute k = n, and count the number of eigenvalues they say exist. Caught another mistake: Section 3.2: First, an observation: the column sums of Q(G) are all zero is wrong. Contradicts their definition of Q(G).

"Caught another mistake: Section 3.2: First, an observation: the column sums of Q(G) are all zero is wrong. Contradicts their definition of Q(G)." True, but it's pretty obvious he was referring to a directed graph G where matrix Q(G) is defined as Qij = 1 if vertex vi has an outgoing edge ej; -1 if vertex vi has an incoming edge ej; 0 otherwise.
Post reply on HN