We predict disease-genes relations on the human interactome network using a methodology that jointly learns functional and connectivity patterns surrounding proteins. To exploit at best latent information in the network, we propose an extended version of random walks, named Random Watcher-Walker (RW²), which is shown to perform better than other state-of-the-art algorithms. We also show that performance of RW² and other compared state-of-the-art algorithms is extremely sensitive to the interactome used, and to the adopted disease categorizations, since this influences the ability to capture regularities in presence of sparsity and incompleteness.