Well, Frankfurt is not easy sometimes. Be quickly in reserving your room. Into the bargain, its fair week during NODE. That means that towards the weekend prices will get high.
In general: the more out of the city, the better for the price. You can e.g. check hotels in the direction of the town Offenbach. There is a regularly train connection to Offenbach.
Moving around in Frankfurt:
If you are looking for a cheap hostel room to share with others you should check the following hostels.
Maybe use the vvvv.org forum to connect yourselfs in advance.
Private couches and accommodations: