Babai's graph isomorphism result, for programmers

For about a month the theory blogs have been buzzing about a talk László Babai gave at the University of Chicago on November 10th, in which he said he could solve graph isomorphism in quasipolynomial time. On Friday the paper went up on arXiv, Graph Isomorphism in Quasipolynomial Time, all 84 pages of it. I’ve read the introduction and skimmed a good chunk of the rest, and understood maybe a fifth of the group theory, which is about what my math degree prepared me for.*

It’s also a good excuse to explain something I’ve never been able to explain well to other programmers, which is why complexity theorists get so worked up about the difference between running times that all look “slow” to the rest of us. So this post wanders a bit.

Same graph, different drawing

Two graphs are isomorphic if they’re the same graph with the vertices renamed. More precisely, there’s a one-to-one mapping from the vertices of one to the vertices of the other such that two vertices are connected in the first exactly when their images are connected in the second. The question is: given two graphs, is there such a mapping?

The drawing tells you nothing. These two are the same graph:

You can check a proposed mapping quickly, just go edge by edge, so the problem is in NP. The obvious algorithm tries all n! mappings, which for 20 vertices is about 2.4 × 10¹⁸, and for 100 vertices is a number with 158 digits. You can do much better than that with simple tricks: count each vertex’s neighbors, and a vertex of degree 3 can only map to a vertex of degree 3. Then refine, a vertex of degree 3 whose neighbors have degrees 2, 2 and 5 can only map to another one like that, and keep going until nothing changes. This “color refinement” idea is basically what practical tools like Brendan McKay’s nauty do (plus a lot of cleverness on top), and for nearly every graph you’ll meet in real life it finishes fast.

The trouble is “nearly every”. There are families of very regular graphs, where every vertex looks exactly like every other vertex from the inside, and refinement gets nowhere. Strongly regular graphs are the classic example (they have their own, somewhat better bounds, but they’re still hard). For general graphs, the best proven bound for decades has been exp(O(√(n log n))), from 1983 (Babai’s paper credits it to Luks). That’s better than n! by an enormous margin, and still far from polynomial.

Why theorists care so much

Graph isomorphism is one of very few natural problems that are in NP but aren’t known to be either in P or NP-complete. Factoring integers is another one. Most problems people care about fall cleanly into “we have a polynomial algorithm” or “it’s NP-complete, so probably not”, and these two just sit in between.

And there’s good evidence GI isn’t NP-complete. A result from the 80s says that if it were, the polynomial hierarchy (a tower of complexity classes above NP) would collapse to its second level, which almost nobody believes. So GI has been the poster child for “probably easier than NP-complete, but nobody can show it’s in P” for more than thirty years. Babai’s result is a big step toward the “easy” side. It also makes NP-completeness even less likely: if GI were NP-complete and quasipolynomial, every problem in NP would have a quasipolynomial algorithm, which would contradict what most people believe about problems like SAT.

What quasipolynomial means

This is the part I wanted to get to. Here are the families of running time that matter:

• polynomial: n^c for some constant c, like n³
• quasipolynomial: exp((log n)^c), which you can also write as n^((log n)^(c−1)). The simplest one is n^(log n).
• Luks’s bound, 2^√(n log n), which is “subexponential”
• exponential: 2^n
• brute force: n!

Quasipolynomial is a polynomial whose exponent creeps up very slowly with n. n^(log₂ n) at n = 1,000 is n^10. At a million it’s n^20. It’s not polynomial, but it’s a lot closer to polynomial than to anything exponential. A lot of theorists think of it as “nearly polynomial”.

It’s much easier to see with numbers, so here’s what each of those costs. I’ve taken log₂ of the number of steps, set every hidden constant to 1 and used base-2 logs throughout, which is not how anyone would really count, but it shows the shapes:

n	n³	n^(log₂ n)	2^√(n log₂ n)	2^n	n!
10	2^10	2^11	2^5.8	2^10	2^21.8
100	2^19.9	2^44.1	2^25.8	2^100	2^525
1,000	2^29.9	2^99.3	2^99.8	2^1000	2^8,529
1,000,000	2^59.8	2^397	2^4,465	2^1,000,000	2^18,488,885

The row I find interesting is n = 1,000. With these simplified formulas, the simplest quasipolynomial bound and Luks’s bound are basically the same, about 2^100 each. Below about a thousand vertices the old bound is actually smaller. That crossover is real: setting (log₂ n)² = √(n log₂ n) and squaring gives (log₂ n)³ = n, which holds at about n ≈ 980. After that, the gap opens up very fast, and by a million vertices it’s 2^397 against 2^4,465.

Also note that 2^397 is still not something you’re going to run. Neither of these bounds says anything about whether a computer can do it this afternoon. They’re about how the cost grows, and Babai’s grows like something only slightly worse than a polynomial. Here’s the million-vertex row on a log scale, which is the only way to fit it on a page:

One honest caveat about my table: the c in exp((log n)^c) matters a lot. With c = 2 you get n^(log n), as above. With c = 3 you get n^((log n)²), which at a million vertices is about 2^7,900, worse than Luks’s bound at that size, though it still wins eventually. From what I’ve read so far, the paper doesn’t try to make the exponent small, and it doesn’t need to. The result is that some constant works. Optimizing it is the kind of thing that happens in follow-up papers.

How it works, as far as I can tell

I want to be careful here, because I’ve read the overview, not the proofs, and the proofs are where all the difficulty is.

The approach builds on Eugene Luks’s work from the early 80s, which turned isomorphism into a problem about groups. Instead of searching through all possible mappings, you work with the group of permutations that might be allowed and break it down recursively into smaller pieces, a divide-and-conquer over the structure of the group. Luks used this to get a polynomial algorithm for graphs where every vertex has bounded degree, and his framework is a problem called string isomorphism: given two strings and a group of permutations, is there a permutation in the group that turns one string into the other?

The recursion works well until the group is huge and very symmetric, essentially the full symmetric group acting on some set, and then it has nothing to divide. Babai’s contribution, in his words in the abstract, is to attack these “barrier configurations” with what he calls group-theoretic “local certificates” combined with combinatorial partitioning, and to show that a particular family of graphs, Johnson graphs, are the only things that can block the partitioning. If you hit one, it’s so structured that you can deal with it directly. If you don’t, you can split the problem into much smaller ones. Either way you make progress, and the bookkeeping on how much progress gives you the quasipolynomial bound. I’ve also seen it said that, like a lot of modern group theory algorithms, it relies on consequences of the classification of finite simple groups somewhere along the way.

That’s the cartoon version. I don’t understand it well enough to tell you why the local certificates work, and I’d distrust any blog post that claims to after four days.

It hasn’t been checked yet

Which brings me to the thing I want to be clear about. This is a fresh claim. Babai is one of the most respected people in the field, he’s worked on this problem for decades, the people who sat through his talks seem convinced, and he’s being careful about what he claims. But the paper has been public since Friday, it’s 84 pages of dense math, and nobody has finished refereeing it. Proofs of this size need months of careful reading before the field treats them as settled, and occasionally the reading turns up problems. I’d put my own confidence fairly high, for whatever my opinion is worth on group theory, but “announced and very promising” is the honest status, and I’ll be reading the reactions from people who can actually check it.

Does it matter for programmers

Directly, no. If you need graph isomorphism today, for chemistry (is this molecule already in the database?), for finding duplicate circuits, for deduplicating anything that’s structured as a graph, you use nauty, Traces or bliss, which are fast on almost everything you’ll ever feed them. Babai’s algorithm is about the worst case, and nobody’s suggesting you implement it. I suspect implementing it would be a heroic project in itself.

Indirectly, I think it matters the way most theory matters. Knowing where the real boundaries are changes what you try. For thirty years the honest answer to “is graph isomorphism hard?” was “we really don’t know”. Now it’s “almost certainly not very hard, if this holds up”, which is a much more interesting answer, and you get to explain the difference between n^(log n) and 2^√n to your team at lunch.

* Most of the abstract algebra from my undergrad math is gone, apart from the moment Lagrange’s theorem finally clicked. That got me through the first ten pages of this paper. The other seventy-four are going to take a lot longer.