Graph Isomorphism Strikes Back
quantamagazine.org
quantamagazine.org
Scott Aaronson is just such a fantastic writer. So impressive.
Excellent sales pitch. I'm going to listen to some of his lectures next snow day.
He would walk down the hall to his office, saying his hellos to everyone with a deep, sincere enthusiasm for life. It brightened the entire floor.
Throughout my life, I've found that the best lecturers aren't necessarily the smartest or the most credentialed, they're the most apparently passionate and enthusiastic — so much so that their enthusiasm has a tendency to "rub off" on their audiences. Enthusiasm leads to engagement, which leads to attentiveness and self-motivation for learning. Even a mediocre teacher can be a great lecturer, and I've had a few in my lifetime (though unfortunately I can count their number on one hand).
Subexponential but not quasipolynomial
Personal interest: I wrote Ferret, my PhD student wrote Hungry.
VF2 is basically the most stupid search imaginable -- if the problem is easy it stumbles into the solution very quickly, but if any work is required it degrades into a horrible exponential search.
On the other hand, Nauty is very difficult to confuse -- as it reasons about the whole graph (whereas VF2 just does local reasoning), your graph has to have global properties which make it hard, which are rare (and basically never occur in real-world graphs, unless they come from some mathematical problem).
Much of the progress in recent years has come from first finding instances where existing algorithms (in particular, partitioning from Brendan McKay's Nauty) take exponential time, and understanding why.
Sure, there's a lot you can do with it in the math and theoretical cs world, probably in chemistry (derivation of chemical reactions?) and maybe bioinformatics as well.
But despite the power of the approach - general comparison of structures and/or combinatoric enumeration of all "instances" of pattern in data graph - are there any success stories of companies with products which are killing it because of using graph morphisms under the hood? (or maybe even directly exposing pattern/data graph relations to the user)
Take your problem in Constraint Programming / Mixed Integer Programming / SAT / SMT, generate a parse tree, turn that parse tree into a graph, and find symmetries of that graph.
If done in the right way, symmetries of the graph are symmetries of the original problem, and knowledge of these symmetries can be used to avoid redundant symmetric search. This is done all the time in combinatorial search systems.
One problem for many other real-world problems is it is much more common to want "almost symmetries" (for various definitions of almost symmetry). It turns out this is a much harder problem, and algorithms for "pure" graph isomorphism can't be easily modified, to solve the 'almost symmetry' problem.
for some definitions of 'almost', especially the vague human ones, there are very surprising results (well, not for people with CS education, but for the other ones). e.g. 2-SAT vs 3-SAT, hamiltonian path (visit all nodes on a graph) vs eulerian path (visit all edges), shortest path vs longest path, etc. like i said, the 'almost' is debatable, but for the untrained eye the problems are very similar.
Face/shape recognition comes to mind, where inexact graph matching would be useful, but are there any others?
I'm not trolling, just interested in graph matching in general as amateur. I have this feeling that there should be many more applications of these techniques, but amusingly, in practice there's always a more specialized, non matching algorithm used. (probably because of matching's algorithm complexity which doesn't scale for larger problems...)
Compiler optimization, generating hardware layouts of circuits, and helping neural nets scale. Brute force isomorphism (where you check permutations but don't care if the object under study is a graph) is a bit lower than the n! naive method Babai uses as a subroutine in the paper, https://oeis.org/A186202
Plus, in perhaps a bit deeper philosophical sense, we are ourselves biased towards expressing problems that have relatively simple complexities as their solution. While there are some simple problem that have complicated optimal solutions, certainly, I'd say that in general the vast bulk of problems for which the optimal solution has Ackermann's complexity are problems that we can't really express or manipulate, either. We focus a lot on our ability to create and express solutions because problems in the real world tend to force themselves upon us since long since before computer science was even a thing, but our ability to express problems is limited too!
Eg. Many proofs that say "this problem is NP-Hard" just prove that "you would have to solve xyz NP-Hard problem to solve this"
Oh, but inverse Ackerman is very slow, and exp(a^(-1)(n)) is very slow as well. Same with the iterated logarithm.
The later pops up in recursive algorithms that partition in parts of size log n. I don't think that's a very weird thing to do.
And we also see some very weird exponents -- the best asymptotic bound we have on a matrix multiplication algorithm is n^2.3728639.