Hacker News Reader

Comment by actually_a_dog | Hacker News Reader

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

View on HN

I don't think that follows. Since the adjacency matrix contains O(n^2) _bits_ of information, the number of adjacency matrices of graphs is O(2^(n^2)). This makes sense: graphs with vertex labels {1,...,n} are in bijection with symmetric n x n binary matrices with zero diagonal. It's difficult to quantify how much information is lost when we reduce this matrix to its spectrum, since the eigenvalues are real numbers, but there are O(n) degrees of freedom, and in principle plenty of room to distinguish any two graphs.

Of course, as a sibling comment notes, unlabeled graphs are often more interesting, for which one has to look at equivalence classes of adjacency matrices. The spectrum is nice here because it is automatically invariant to vertex permutations and hence a graph isomorphism invariant. The existence of nonisomorphic cospectral graphs is not immediately obvious, although there are simple examples, and that there are infinite families of cospectral pairs is even less obvious. So at the very least, it's interesting that the spectrum is not a complete invariant, and that it does work well for certain classes of graphs.

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.

Reply on news.ycombinator.com