I found some new tools for protein interaction alignment today. My PI forwarded me this paper:

Clark, C. & Kalita, J. A Comparison of Algorithms for the Pairwise Alignment of Biological Networks. Bioinformatics btu307- (2014). doi:10.1093/bioinformatics/btu307

Clark and Kalita seem to really like NATALIE, a tool which ignores parts of the network which don't appear to align well (Lagrangian relaxation!). It's part of the LiSA software collection and looks like it was last updated in 2012. I'll have to see how easy it is to implement - some of these kinds of tools may work really well but are just painful to get working, especially if their documentation is sparse.