  Topological network alignment aims to align two networks node-wise in order
to maximize the observed common connection (edge) topology between them. The
topological alignment of two Protein-Protein Interaction (PPI) networks should
thus expose protein pairs with similar interaction partners allowing, for
example, the prediction of common Gene Ontology (GO) terms. Unfortunately, no
network alignment algorithm based on topology alone has been able to achieve
this aim, though those that include sequence similarity have seen some success.
We argue that this failure of topology alone is due to the sparsity and
incompleteness of the PPI network data of almost all species, which provides
the network topology with a small signal-to-noise ratio that is effectively
swamped when sequence information is added to the mix. Here we show that the
weak signal can be detected using multiple stochastic samples of "good"
topological network alignments, which allows us to observe regions of the two
networks that are robustly aligned across multiple samples. The resulting
Network Alignment Frequency (NAF) strongly correlates with GO-based Resnik
semantic similarity and enables the first successful cross-species predictions
of GO terms based on topology-only network alignments. Our best predictions
have an AUPR of about 0.4, which is competitive with state-of-the-art
algorithms, even when there is no observable sequence similarity and no known
homology relationship. While our results provide only a "proof of concept" on
existing network data, we hypothesize that predicting GO terms from
topology-only network alignments will become increasingly practical as the
volume and quality of PPI network data increase.
