Redundancy and Structure of computational problems

It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.

What are the major results known about such formal notions for computational problems? A recent survey of such notions would be very nice.

It was posted on TCS stackexchange without any answer.

-
The widely-held belief that (say) $GI \ne NP$ comes as much from the few results we do have (e.g. that $GI$ is in the low hierarchy of $NP$) which would either have surprising consequences or would contradict other widely-held beliefs, as it does from the rather vaguer idea that there is "not enough structure" (or "too much structure"?) in $GI$.