Graph isomorphism is actually not known to be NP-complete. Many complexity theorists believe it isn't, since if it is, then the polynomial hierarchy collapses.