Due to the constraints of limited effort and sampling error, observed species interac- tion networks are an imperfect representation of the ‘true’ underlying community. Link prediction methods allow us to construct a potentially more complete representation of a given empirical network by guiding targeted sampling of predicted links, as well as offer insight into potential interactions that may occur as species’ ranges shift. Various data types can predict interactions; understanding how different kinds of information compare in their ability to predict links between different types of nodes is important. To this end, we compare random-forest regression models informed by combinations of phylogenetic structure, species traits, and latent network structure-hidden features inferred from the observed network topology – in their ability to predict interactions in a diverse network of fruiting plants and frugivorous birds in Brazil’s Atlantic forest. We found that for our dataset, latent structure derived through a single-value decom- position approach was the most important determinant of model predictive perfor- mance. While incorporating trait or phylogenetic information alongside latent features had little effect on discriminatory power, they did meaningfully increase overall model accuracy. Our results highlight the potential importance of latent structural features for predicting mutualistic interactions, and encourage a clear conceptual link between prediction performance metrics and the overall goal of predicting cryptic links.