In recent years, considerable efforts have been devoted to identifying and characterizing protein-protein interaction (PPI). Besides investigations on the molecular events involved in PPI, functional annotation of an unclassified protein according to its interacting partners is also an important topic [28] . Since it is too bold to infer protein functions according to the "majority rule" that utilizes only the PPI network structure [29, 30] , many studies integrate other data sources into the functional characterization of PPI, among which the gene expression data is the favorite [9, 31, 32] . All these works assumed that interacting protein pairs were characterized with higher expression correlation than random ones. However, previous investigations indicated that the relationship between expression correlation and PPI was weak on a genomic scale [33] [34] [35] although a recent work strengthened the association by integrating cross-species conservation information [10] .