The first place to look at is [E.M. Luks algorithm for polynomial GI for graphs of bounded degree][1]. The algorithm is group-theoretic, and utilizes the fact that subgroups of products of $S_k$ for bounded $k$ always have subgroups of bounded index, which allows to divide-and-conquer over cosets efficiently.

A [recent breakthrough of Babai][2] solves GI in $\mathrm{exp}(O((\log n)^c))$ time. One of the main ideas (which is not particuraly novel to this paper) is that either the automorphism kernel that stabilizes a subgraph has subgroups of small index (which allows to apply the previous result), or contain an automorphism group of a large [Johnson scheme][3]. The paper then proceeds to treat the second case with an efficient symmetry-breaking procedure.

It would probably be an overly simplified and very imprecise statement, but this implies that the hardest case for GI are graphs obtained from a [Johnson graph][4] in a non-trivial way.


  [1]: http://ieeexplore.ieee.org/abstract/document/4567803/?reload=true
  [2]: http://dl.acm.org/citation.cfm?id=2897542
  [3]: https://en.wikipedia.org/wiki/Johnson_scheme
  [4]: https://en.wikipedia.org/wiki/Johnson_graph