Label propagation is an effective and efficient technique to utilize local and global features in a network for semi-supervised learning. In the literature, one challenge is how to propagate information in heterogeneous networks comprising several subnetworks, each of which has its own cluster structures that need to be explored independently. In this paper, we introduce an intutitive algorithm MINProp (Mutual Interaction-based Network Propagation) and a simple regularization framework for propagating information between subnetworks in a heterogeneous network. MINProp sequentially performs label propagation on each individual subnetwork with the current label information derived from the other subnetworks and repeats this step until convergence to the global optimal solution to the convex objective function of the regularization framework. The independent label propagation on each subnetwork explores the cluster structure in the subnetwork. The label information from the other subnetworks is used to capture mutual interactions (bicluster structures) between the vertices in each pair of the subnetworks. MINProp algorithm is applied to disease gene discovery from a heterogeneus network of disease phenotypes and genes. In the experiments, MINProp significantly output-performed the original label propagation algorithm on a single network and the state-of-the-art methods for discovering disease genes. The results also suggest that MINProp is more effective in utilizing the modular structures in a heterogenous network. Finally, MINProp discovered new disease-gene associations that are only reported recently.  Network-based data analysis is recently attracting increasing attention in practical applications of data mining and machine learning [9, 17, 19, 13] . It is believed that many real world networks contain useful hidden neighborhood structures among the objects in the network. Several graph-based semi-supervised learning algorithms have been developed to utilize the global network structure to improve performance in different learning tasks on networks such as classification and ranking [16, 24, 2, 23] . In these algorithms, some of the vertices (labeled data) are initialized with labels or activation values and the other vertices (unlabeled data) are initialized with 0, and the learning problem is to assign label/activation value to the unlabeled data for classification or ranking. The common property of the graph-based semi-supervised learning algorithms is the "cluster assumption": nearby data points in a network should be labeled similarly and data points in the same global cluster in the network should also be labeled similarly. These algorithms are typically formulated as label propagation on a network: the label information on the vertices is iteratively propagated between the neighboring vertices and the propagation process will finally converge toward the unique global optimum minimizing a quadratic criterion [3] . One important problem not previously addressed is how to design an algorithm for propagating label information across several subnetworks of different types of vertices and edges. Under this scenario, several subnetworks describing relations between different objects are present in a heterogeneous network (Fig 1A) . Without loss of generality, we define two types of subnetworks in the heterogeneous network: subnetworks containing the same type of objects (homo-subnetwork ) and bipartite subnetworks with edges connecting two types of objects (hetero-subnetwork ). Simply propagating the label on the combined network is not a principled method to explore the cluster structures in the network since each homo-subnetwork may have its own cluster structure and each hetero-subnetwork may also have its own bicluster structures (A bicluster is a set of densely connected vertices in the two joint vertex sets in a bipartite graph.). In principle, these cluster and bicluster structures should be explored independently, rather than be-
In REF , an algorithm called MINProp and a regularization framework is introduced for label propagation over the subnetworks of a heterogeneous network.
A Heterogeneous Label Propagation Algorithm for Disease Gene Discovery
SDM
Computer Science