In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable misery” for people who want to solve GI quickly. At the same time, it is a “curse and a blessing,” as once you’ve found a Johnson graph embedded in your problem you can recurse to much smaller instances. This routine to find one of these three things is called the “split-or-Johnson” routine.'
(1) Are Isospectral Johnson graphs the hardest case to find Isomorphism?
(2) In general what makes a graph class hard to tame (Isomorphism difficult for this class)?
(3) Supposing we know that two graphs are isomorphic. Suppose our goal is to find say isomorphism between any of $\alpha\log N$ vertices of the $N$ vertices for some $\alpha >0$. How difficult is to accomplish this? If you pick a random choice of $\alpha\log N$ on an average how many spurious matches could we land up with as candidate isomorphisms on the other graph based on these fixed $\alpha\log N$ vertices?
Best Answer
Johnson graphs do not cause difficulty to existing programs. Actually they are rather easy; nauty can handle them up to tens of millions of vertices, and so can other programs such as Traces and Bliss.
The difficulty that Babai refers to is more theoretical. The Johnson graph $J(v,t)$, which has $n=\binom vt$ vertices, has the property that $\Theta(n^{1/t})$ vertices need to be fixed in order for partition refinement to produce a partition with all cells at most $cn$ in size ($c<1$), nor does the group have a nice recursive structure like a wreath product. Babai says that a major part of his breakthrough was to realise that only the Johnson graphs (and closely related graphs) have these undesirable properties. With that knowledge, special processing takes care of them. Previously it could have been that some other families of graphs exist with similar properties.
I think this description is reasonably close. I recently listened to Babai speaking on his algorithm for 5 hours but some parts remain unclear to me.
Btw, the automorphism group of $J(v,t)$ for $t\lt v/2$ is $S_v$ acting on $t$-sets. Programs find them easy because of this rich group.
About the "supplementary problem", fixing $O(\log n)$ vertices helps very little. It is necessary to match $\Theta(n^{1/t})$ vertices in each graph before elementary methods will provide much further information about isomorphisms. It's hard to define "elementary methods", but they include all the obvious things like classifying vertices according to their adjacencies with the fixed vertices and more generally fixed-dimensional Weissfeiler-Lehman refinement.
Babai's statement that you quote is easy to misunderstand. It isn't the Johnson graphs themselves that were a scourge to theorists. It's more that the Johnson graphs showed that certain difficult structural properties (mentioned above) are possible and nobody knew a general method for handling these properties. Once Babai showed that only the Johnson graphs caused that structure, the difficultly vanished.