5 ms·

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 Str

by dpflan 5y ago

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-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/index.htm https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: Special Matrices discussing the Laplacian and Distance matrices as noted in the posted paper. [TOC: https://math.mit.edu/~gs/learningfromdata/dsla_toc.pdf https://math.mit.edu/~gs/learningfromdata/dsla_toc.pdf]

dls2016 5y ago
> Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Agreed... if you're going to write down the Laplacian at least demonstrate the null space <-> connected component relationship. Edit: looks like maybe an undergraduate paper?
- dpflan 5y ago
  Oh, ah, nice find, yeah, if you go down the URL: https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017/projects2017.html https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017... Projects from a LA class at UofU.
actually_a_dog 5y ago
You are most definitely not wrong. I would have expected some mention of the spectrum of a graph beyond simply defining what the eigenvalues are. Incidentally, one interesting thing about the graph spectrum is that it's actually not a very interesting invariant. Among other things, almost all trees are cospectral, as proven in the following paper by Allen Schwenk in 1973: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral https://www.researchgate.net/publication/245264768_Almost_al...
- enriquto 5y ago
  > Among other things, almost all trees are cospectral This does not really mean that the spectrum is not interesting, does it? Only that all trees have nearly the same spectrum. Sure, there's not much variability inside the class of trees, but almost no graphs are trees. After all, the matrix associated to a tree is basically a permutation of the identity.
  - actually_a_dog 5y ago
    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 all zeroes on the diagonal. That means the adjacency matrix contains (literally) n^2/2 - n bits of information, while the number of connected graphs of order n as n -> infinity grows exponentially [0]. That implies that for the purpose of telling two graphs of the same order apart, the spectrum is of fairly limited utility, which is what I was thinking of when I wrote that it was not an interesting invariant. --- [0]: https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf
    - Py-o7 5y ago
      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.
      - orange3xchicken 5y ago
        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).
hwers 5y ago
The laplacian of a matrix also has cool applications in computer graphics, if anyone is curious (about further connections). Think of the mesh of an object as a graph and compute the lapacian. (You get natural unsupervised segmentations of the mesh for instance if you look at it as a spectral clustering problem.) Look up resources by Keenan Crane. If you've played with 'smooth normals' in blender I believe it uses techniques like that as well.
OccamsRazr 5y ago
> 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 tell, thus, who the desired audience is or what the aim of it is. So whether one should expect one thing or another from this random pdf... I mean, without knowing more, what is there to reasonably expect? For instance (and I can imagine this because I've taught an undergraduate course on graph theory, among other undergrad math courses), if these are notes from a course, then the instructor may have some good, context specific reasons for focusing on some topics while not going into details on others. But, as I said above, it's really impossible to know because this has just been plunked on HN with no context, as if that is somehow valuable.
- dpflan 5y ago
  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/projects2017.html 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.
faizshah 5y ago
Related: There’s a really good book called “Graph Algorithms in the Language of Linear Algebra” if you’re interested in GRAPHBLAS related topics.

by dpflan 5y ago

dls2016 5y ago

> Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Agreed... if you're going to write down the Laplacian at least demonstrate the null space <-> connected component relationship. Edit: looks like maybe an undergraduate paper?

dpflan 5y ago
Oh, ah, nice find, yeah, if you go down the URL: https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017/projects2017.html https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017... Projects from a LA class at UofU.

actually_a_dog 5y ago

You are most definitely not wrong. I would have expected some mention of the spectrum of a graph beyond simply defining what the eigenvalues are. Incidentally, one interesting thing about the graph spectrum is that it's actually not a very interesting invariant. Among other things, almost all trees are cospectral, as proven in the following paper by Allen Schwenk in 1973: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral https://www.researchgate.net/publication/245264768_Almost_al...

enriquto 5y ago
> Among other things, almost all trees are cospectral This does not really mean that the spectrum is not interesting, does it? Only that all trees have nearly the same spectrum. Sure, there's not much variability inside the class of trees, but almost no graphs are trees. After all, the matrix associated to a tree is basically a permutation of the identity.
- actually_a_dog 5y ago
  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 all zeroes on the diagonal. That means the adjacency matrix contains (literally) n^2/2 - n bits of information, while the number of connected graphs of order n as n -> infinity grows exponentially [0]. That implies that for the purpose of telling two graphs of the same order apart, the spectrum is of fairly limited utility, which is what I was thinking of when I wrote that it was not an interesting invariant. --- [0]: https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf
  - Py-o7 5y ago
    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.
    - orange3xchicken 5y ago
      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).

hwers 5y ago

The laplacian of a matrix also has cool applications in computer graphics, if anyone is curious (about further connections). Think of the mesh of an object as a graph and compute the lapacian. (You get natural unsupervised segmentations of the mesh for instance if you look at it as a spectral clustering problem.) Look up resources by Keenan Crane. If you've played with 'smooth normals' in blender I believe it uses techniques like that as well.

OccamsRazr 5y ago

> 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 tell, thus, who the desired audience is or what the aim of it is. So whether one should expect one thing or another from this random pdf... I mean, without knowing more, what is there to reasonably expect? For instance (and I can imagine this because I've taught an undergraduate course on graph theory, among other undergrad math courses), if these are notes from a course, then the instructor may have some good, context specific reasons for focusing on some topics while not going into details on others. But, as I said above, it's really impossible to know because this has just been plunked on HN with no context, as if that is somehow valuable.

dpflan 5y ago
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/projects2017.html 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.

faizshah 5y ago

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