MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach

Abstract

Network embedding approaches are gaining momentum to analyse a large variety of networks. Indeed, these approaches have demonstrated their effectiveness in tasks such as community detection, node classification, and link prediction. However, very few network embedding methods have been specifically designed to handle multiplex networks, i.e. networks composed of different layers sharing the same set of nodes but having different types of edges. Moreover, to our knowledge, existing approaches cannot embed multiple nodes from multiplex-heterogeneous networks, i.e. networks composed of several multiplex networks containing both different types of nodes and edges. In this study, we propose MultiVERSE, an extension of the VERSE framework using Random Walks with Restart on Multiplex (RWR-M) and Multiplex-Heterogeneous (RWR-MH) networks. MultiVERSE is a fast and scalable method to learn node embeddings from multiplex and multiplex-heterogeneous networks. We evaluate MultiVERSE on several biological and social networks and demonstrate its performance. MultiVERSE indeed outperforms most of the other methods in the tasks of link prediction and network reconstruction for multiplex network embedding, and is also efficient in link prediction for multiplex-heterogeneous network embedding. Finally, we apply MultiVERSE to study rare disease-gene associations using link prediction and clustering. MultiVERSE is freely available on github at https://github.com/Lpiol/MultiVERSE .

Figure 1

Illustrations of the different types of networks. (A) A multiplex network. The different layers share the same set of nodes but different types of edges. (B) A heterogeneous network. The two networks are composed of different types of nodes and edges, connected by bipartite interactions (black dashed lines). (C) A multiplex-heterogeneous network composed of two multiplex networks. The multiplex networks are connected by bipartite interactions (dashed lines). For the sake of simplicity, the figure does not represent all the possible bipartite interactions (each layer of a given multiplex is in reality linked with every layer of the other multiplex).

Figure 2

Overview of the MultiVERSE pipeline. Starting from a multiplex-heterogeneous network, we represent its structure through an adjacency matrix (size $|V|\times |V|$); we then compute a similarity matrix using Random Walk with Restart algorithm, and apply an optimized version of the VERSE algorithm to compute the embeddings. The resulting matrix of embeddings will be used for the applications.

Figure 3

General approach for link prediction on multiplex networks: (top) for the link prediction heuristics, we apply them to each layer and average them across all layers; (center) for monoplex-based methods, we embed each layer with the given method, then average it; (bottom) for multiplex-based methods, we apply the specific embedding method to the network. The embedding operators are then applied to monoplex- and multiplex-based method embeddings. The three types of methods are finally evaluated for link prediction using a binary classifier and a ROC-AUC is computed.

Figure 4

General approach for network reconstruction on multiplex networks: (top) for monoplex-based methods, embed each layer with the given method, then average it; (bottom) for multiplex-based methods, apply the specific embedding method to the network. Embedding operators are then applied to monoplex- and multiplex-based method embeddings. The three types of methods are finally evalutated for network embedding using a binary classifier and a precision@K score is computed.

Figure 5

Cluster containing the HGPS disease node. Disease-Disease edges from the disease multiplex network are represented in green (shared symptoms) and blue (CTD projection). Gene-Gene edges from the molecular multiplex network are represented in pink (Reactome pathways), red (protein-protein interactions) and orange (molecular complexes). Gene-Disease bipartite interactions are represented with black dashed lines.

Figure 6

Cluster containing the Xeroderma pigmentosum VII disease node. Gene-Gene edges from the molecular multiplex network are represented in pink (Reactome pathways), red (protein-protein interactions) and orange (molecular complexes). Gene-Disease bipartite interactions are represented with black dashed lines.