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 of an automorphism subgraph stabilizer efficiently (since for bounded degree graphs it is contained within products of $S_k$ induced by automorphisms of neighbourhoods of each vertex).

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 (primitive) quotient of an automorphism subgraph stabilizer either has subgroups of small index (which allows to apply the previous result), or contains an automorphism group of a large [Johnson scheme][3]. The paper then proceeds to treat the second case with an efficient symmetry-breaking procedure, which is novel and highly non-trivial.

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