Simultaneous Link Prediction on Unaligned Networks Using Graph Embedding and Optimal Transport

Link prediction is an extensively studied topic and various methods have been proposed to tackle the task in both heuristic and more sophisticated statistical learning approaches. However, most of them focus on the setting of one single graph. Combining information on multiple graphs with similar topological structures can improve the performance and robustness of link prediction; nevertheless, the alignment between nodes of different networks is not always available, or is only partially known. This study considers the link prediction problem on two unaligned networks simultaneously. A new framework is proposed to integrate link prediction using graph embedding and node alignment using optimal transport. The integrated objective is optimized at once via an iterative algorithm. A showcase of the proposed framework using LINE embedding method is discussed with experiments on three real datasets. The results demonstrate that the integrated formulation shows better link prediction performance over single-graph link prediction methods as well as existing methods that do not directly aim at link prediction. The framework is flexible and theoretically able to integrate with different graph embedding methods, which is demonstrated in additional experiments using node2vec.

I. Introduction

Graph is a general and ubiquitous data structure that plays a crucial role in various aspects of the world. Since it was first introduced in the 18th century, graph has been an important subject in many research fields. By representing relationships between entities with nodes and links among them, graph is useful to model complex systems of interactive elements. For example, in a social network, a user account can be seen as a node and the friendship between two users can be seen as a link. In a protein-protein interaction network, each node in the network represents a protein and two proteins are linked if they interact with each other. In many real world scenarios, complex networks are only partially observed, i.e. have missing or hidden links. Social network users who know each other in real life might have not been connected in a social network platform yet. In medical and biological studies, interaction graphs are incomplete because they rely only on expensive lab experiment data. Re-establishing such hidden friendships and possible biological interactions undoubtedly derives tremendous benefits in both academic and industrial settings. In the machine learning context, the task of re-discovering those potential relationships is called link prediction.