Pairwise comparison of sequence data is intensively used for automated functional protein annotation, while graphical models emerge as promising candidates for an integration of various heterogeneous features. We designed a model, termed hRMN that integrates different genomic features and implemented a variant of belief propagation for functional annotation transfer. hRMN allows the assignment of multiple functional categories while avoiding common problems in annotation transfer from heterogeneous datasets, such as an independency of the investigated datasets. We benchmarked this system with large-scale annotation transfer (based on the MIPS FunCat ontology) to proteins of the prokaryotes Bacillus subtilis, Helicobacter pylori, Listeria monocytogenes, and Listeria innocua. hRMN consistently outperformed two competitors in annotation of four bacterial genomes. The developed code is available for download at http://mips.gsf.de/proj/bfab/hRMN.html.