Link Prediction through Deep Learning

Abstract

Inferring missing links or predicting future ones based on the currently observed network is known as link prediction, which has tremendous real-world applications in biomedicine1-3, e-commerce4, social media5 and criminal intelligence6. Numerous methods have been proposed to solve the link prediction problem7-9. Yet, many of these existing methods are designed for undirected networks only. Moreover, most methods are based on domain-specific heuristics10, and hence their performances differ greatly for networks from different domains. Here we developed a new link prediction method based on deep generative models11 in machine learning. This method does not rely on any domain-specific heuristic and works for general undirected or directed complex networks. Our key idea is to represent the adjacency matrix of a network as an image and then learn hierarchical feature representations of the image by training a deep generative model. Those features correspond to structural patterns in the network at different scales, from small subgraphs to mesoscopic communities12. Conceptually, taking into account structural patterns at different scales all together should outperform any domain-specific heuristics that typically focus on structural patterns at a particular scale. Indeed, when applied to various real-world networks from different domains13-17, our method shows overall superior performance against existing methods. Moreover, it can be easily parallelized by splitting a large network into several small subnetworks and then perform link prediction for each subnetwork in parallel. Our results imply that deep learning techniques can be effectively applied to complex networks and solve the classical link prediction problem with robust and superior performance. SummaryWe propose a new link prediction method based on deep generative models.