Link Prediction Based On Hierarchical Link Patterns Learning

In the real world,there are plenty of physical objects which affect and relate to each other.We can use graphs to model them,specifically,entities can be represented by nodes and relationships can be represented by edges.Link prediction,as one of the graph analysis techniques,aims to mine the relationship between entities that are missing or will be generated in the next moment.It has important research significance and application value in network evolution mechanism,entity association prediction,and data denoising.A large number of link prediction methods have been proposed in the past,among which: Methods based on artificially defined structural similarity have the advantages of simplicity and strong interpretability,but single and solid features cannot be applied to rich and diverse network topology types;Although the probabilistic method of estimation has better adaptability to the data,while the cumbersome statistical process also brings too much computational consumption.Compared with the previous two methods,the learning-based method achieves better generalization performance and computational efficiency by automatically extracting topological features and data sampling.Furthermore,due to the sparsity of the graph,modeling the hierarchical structure features in the network also bring a general performance boost for link prediction.Inspired by this,we propose a link prediction method Hie Link based on hierarchical link pattern learning.In this method,we construct hierarchical links of different orders by extracting reachable paths of different lengths between nodes,so as to solve the difficulty of predicting links in the network due to sparseness in low-order link patterns.Specifically,we obtain shortest pathes between nodes through the breadth-first search algorithm,and generate links in different orders according to the length,thereby characterizing the hierarchical link pattern in the network.And further sample the node sequence through truncated random walk,and learn the context embedding of the node according to the word embedding method in the language model,to generate the vector representation of the node in different order's link patterns.The final representation of a node is obtained by concatenating the vector representations of nodes in different order's link patterns.For link prediction,we train a multi-layer neural network to perform training for link classification.Compared with the artificially defined edge embedding operator,the supervision information of the training process can be directly transmitted to the edge representation layer,realizing the automatic extraction of implicit structure features for node pairs,and completing the training process between the edge representation layer and the link prediction task layer.The experimental results show that the proposed method outperforms the comparison algorithms on eight classic networks and three sparse networks,and has better performance for sparse links.Due to the complexity of real data,link prediction algorithms that can only deal with a single type of link have been unable to deal with the diverse link types in network data.Therefore,on the basis of Hie Link,we further extend it to multi-layer networks,and propose Hie Link-M for multi-layer network link prediction based on hierarchical link pattern learning.By combining the high-order link construction method in Hie Link and the existing heterogeneous network embedding methods,we can easily learn the hierarchical vector representation of nodes in a multi-layer network to overcoming the prediction difficulties caused by sparse links.Experimental results on five classical multi-layer networks and three sparse multi-layer networks show that Hie Link-M outperforms classical single-layer network link prediction methods and methods based on artificially defined inter-layer correlations or heterogeneous network embeddings.