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?