Like with facing most assassins, whom of which they like to roam and gank top and bot. You just push down their turret when they leave and punish them for doing so, whilst forcing them to stay glued to their lane.

Tell your team mates that the enemy mid is an assassin and will try to gank you, so play extra cautious.

I don't know if Kat is over the top, but every game i see her in, her team wins and she usually gets fed. as long as the Kat has team mates who have cc, the arguement "just cc her" is invalid. since the katarina will combo her damage off of partner's cc. In which case you can't cc Kat when you are cc'd currently.