FIG-LP: Feature-Inverse-Graph based Link Prediction in Graph Stream

Link prediction is one of the essential issues in network science, which aims to find the unknown link or estimate the future link in networks. Existing methods are mainly based on the assumption that the network data is completely available and has stable distribution before analysis. In practice, however, complex networks evolve lifelong with massive data. The data in those networks is associated with previous ones, and the distribution will be non-stationary. Compared with conventional link prediction methods, online link prediction in the largescale dynamic network has three main challenges: i) How to analyze massive data with acceptable expenditure; ii) How to predict future links with less topological information; iii) How to make link prediction stably in a dynamic evolutionary network. In this paper, we propose a streaming link prediction model based on lifelong learning and graph neural networks (GNNs), which converts the link prediction problems to graph classification. Our main idea is to design a new topology, the Feature-Inverse-Graph, which turns node pairs into independent graphs and takes the features of the node pair as new vertices. Additionally, we apply a two-phase sampling sketch to deal with the massive data so that the complexity of the model within lifelong evolving networks could be acceptable. Then, the link prediction tasks in the regular graph is converted into a series of individually Feature-Inverse-Graph classifications. In this case, the computational cost of our model will not increase dramatically with the increase of network data, which is further verified by analyzing the computational complexity. The experimental results demonstrate the efficiency and effectiveness of our model by continuously predicting future links of classical datasets. In our experiments, several topological link prediction measures are chosen as features of node pair. For future work, the FIG-LP model can be used as the basic research of intelligent systems such as the Internet of Things and smart cities, and provide necessary support for the analysis of intelligent systems.