Knowledge Graph Representation Learning Based on Automatic Network Search for Link Prediction

Link prediction,also known as Knowledge Graph Completion(KGC),is the common task in Knowledge Graphs(KGs)to predict missing connections between entities.Most existing methods focus on designing shallow,scalable models,which have less expressive than deep,multi-layer models.Furthermore,most operations like addition,matrix multiplications or factorization are handcrafted based on a few known relation patterns in several wellknown datasets,such as FB15k,WN18,etc.However,due to the diversity and complex nature of real-world data distribution,it is inherently difficult to preset all latent patterns.To address this issue,we proposeKGE-ANS,a novel knowledge graph embedding framework for general link prediction tasks using automatic network search.KGEANS can learn a deep,multi-layer effective architecture to adapt to different datasets through neural architecture search.In addition,the general search spacewe designed is tailored forKGtasks.We performextensive experiments on benchmark datasets and the dataset constructed in this paper.The results show that our KGE-ANS outperforms several state-of-the-art methods,especially on these datasets with complex relation patterns.

Semantic-aware graph convolution network on multi-hop paths for link prediction

Knowledge graph(KG) link prediction aims to address the problem of missing multiple valid triples in KGs. Existing approaches either struggle to efficiently model the message passing process of multi-hop paths or lack transparency of model prediction principles. In this paper,a new graph convolutional network path semantic-aware graph convolution network(PSGCN) is proposed to achieve modeling the semantic information of multi-hop paths. PSGCN first uses a random walk strategy to obtain all-hop paths in KGs,then captures the semantics of the paths by Word2Sec and long shortterm memory(LSTM) models,and finally converts them into a potential representation for the graph convolution network(GCN) messaging process. PSGCN combines path-based inference methods and graph neural networks to achieve better interpretability and scalability. In addition,to ensure the robustness of the model,the value of the path thresholdKis experimented on the FB15K-237 and WN18RR datasets,and the final results prove the effectiveness of the model.

Link prediction based on a semi-local similarity index

Missing link prediction provides significant instruction for both analysis of network structure and mining of unknown links in incomplete networks. Recently, many algorithms have been proposed based on various node-similarity measures. Among these measures, the common neighbour index, the resource allocation index, and the local path index, stemming from different source, have been proved to have relatively high accuracy and low computational effort. In this paper, we propose a similarity index by combining the resource allocation index and the local path index. Simulation results on six unweighted networks show that the accuracy of the proposed index is higher than that of the local path one. Based on the same idea of the present index, we develop its corresponding weighted version and test it on several weighted networks. It is found that, except for the USAir network, the weighted variant also performs better than both the weighted resource allocation index and the weighted local path index. Due to the improved accuracy and the still low computational complexity, the indices may be useful for link prediction.

Entropy-based link prediction in weighted networks

Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks.In a previous work [Xu et al. Physica A, 456 294（2016）], we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight,and propose a weighted prediction index based on the contributions of paths, namely weighted path entropy（WPE）, to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three other typical weighted indices.

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes＇ attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes＇ similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recov- ers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.

Combat network link prediction based on embedding learning

Link prediction of combat networks is of significant military value for precisely identifying the vital infrastructure of the enemy target and optimizing the operational plan of our side.Due to the profound uncertainty in the battleground circumstances, the acquired topological information of the opponent combat network always presents sparse characteristics. To solve this problem, a novel approach named network embedding based combat network link prediction(NECLP) is put forward to predict missing links of sparse combat networks. First,node embedding techniques are presented to preserve as much information of the combat network as possible using a low-dimensional space. Then, we put forward a solution algorithm to predict links between combat networks based on node embedding similarity. Last, massive experiments are carried out on a real-world combat network case to verify the validity and practicality of the proposed NECLP. This paper compares six baseline methods, and experimental results show that the NECLP has outstanding performance and substantially outperforms the baseline methods.

Cold-Start Link Prediction via Weighted Symmetric Nonnegative Matrix Factorization with Graph Regularization

Link prediction has attracted wide attention among interdisciplinaryresearchers as an important issue in complex network. It aims to predict the missing links in current networks and new links that will appear in future networks.Despite the presence of missing links in the target network of link prediction studies, the network it processes remains macroscopically as a large connectedgraph. However, the complexity of the real world makes the complex networksabstracted from real systems often contain many isolated nodes. This phenomenon leads to existing link prediction methods not to efficiently implement the prediction of missing edges on isolated nodes. Therefore, the cold-start linkprediction is favored as one of the most valuable subproblems of traditional linkprediction. However, due to the loss of many links in the observation network, thetopological information available for completing the link prediction task is extremely scarce. This presents a severe challenge for the study of cold-start link prediction. Therefore, how to mine and fuse more available non-topologicalinformation from observed network becomes the key point to solve the problemof cold-start link prediction. In this paper, we propose a framework for solving thecold-start link prediction problem, a joint-weighted symmetric nonnegative matrixfactorization model fusing graph regularization information, based on low-rankapproximation algorithms in the field of machine learning. First, the nonlinear features in high-dimensional space of node attributes are captured by the designedgraph regularization term. Second, using a weighted matrix, we associate the attribute similarity and first order structure information of nodes and constrain eachother. Finally, a unified framework for implementing cold-start link prediction isconstructed by using a symmetric nonnegative matrix factorization model to integrate the multiple information extracted together. Extensive experimental validationon five real networks with attributes shows that the proposed model has very goodpredictive performance when predicting missing edges of isolated nodes.

Research on Link Prediction Algorithms Based on Multichannel Structure Modelling

Today’s link prediction methods are based on the network structure using a single-channel approach for prediction,and there is a lack of link prediction algorithms constructed from a multichannel approach,which makes the features monotonous and noncomplementary.To address this problem,this paper proposes a link prediction algorithm based on multichannel structure modelling(MCLP).First,the network is sampled three times to construct its three subgraph structures.Second,the node representation vectors of the network are learned separately for each subgraph on a single channel.Then,the three node representation vectors are combined,and the similarity matrix is calculated for the combined vectors.Finally,the performance of the MCLP algorithm is evaluated by calculating the AUC using the similarity matrix and conducting multiple experiments on three citation network datasets.The experimental results show that the proposed link prediction algorithm has an AUC of 98.92%,which is better than the performance of the 24 link prediction comparison algorithms used in this paper.The experimental results sufficiently prove that the MCLP algorithm can effectively extract the relationships between network nodes,and confirm its effectiveness and feasibility.

Link Prediction Based on the Relational Path Inference of Triangular Structures

Link prediction is used to complete the knowledge graph.Convolu-tional neural network models are commonly used for link prediction tasks,but they only consider the direct relations between entity pairs,ignoring the semantic information contained in the relation paths.In addition,the embedding dimension of the relation is generally larger than that of the entity in the ConvR model,which blocks the progress of downstream tasks.If we reduce the embedding dimension of the relation,the performance will be greatly degraded.This paper proposes a convolutional model PITri-R-ConvR based on triangular structure relational infer-ence.The model uses relational path inference to capture semantic information,while using a triangular structure to ensure the reliability and computational effi-ciency of relational inference.In addition,the decoder R-ConvR improves the initial embedding of the ConvR model,which solves the problems of the ConvR model and significantly improves the prediction performance.Finally,this paper conducts sufficient experiments in multiple datasets to verify the superiority of the model and the rationality of each module.

Type-Augmented Link Prediction Based on Bayesian Formula

Knowledge graphs(KGs)play a pivotal role in various real-world applications,but they are frequently plagued by incomplete information,which manifests in the form of missing entities.Link prediction,which aims to infer missing entities given existing facts,has been mostly addressed by maximizing the likelihood of observed triplets at the instance level.However,they ignore the semantic information most KGs contain and the prior knowledge implied by the semantic information.To address this limitation,we propose a Type-Augmented Link Prediction(TALP)approach,which builds a hierarchical feature model,computes type feature weights,trains them to be specific to different relations,encodes weights into prior probabilities and convolutional encodes instance-level information into likelihood probabilities;finally,combining them via Bayes rule to compute the posterior probabilities of entity prediction.Our proposed TALP approach achieves significantly better performance than existing methods on link prediction benchmark datasets.

LGHAE: Local and Global Hyper-relation Aggregation Embedding for Link Prediction

The Knowledge Graph(KGs)have profoundly impacted many researchfields.However,there is a problem of low data integrity in KGs.The binary-relational knowledge graph is more common in KGs but is limited by less information.It often has less content to use when predicting missing entities(relations).The hyper-relational knowledge graph is another form of KGs,which introduces much additional information(qualifiers)based on the main triple.The hyper-relational knowledge graph can effectively improve the accuracy of pre-dicting missing entities(relations).The existing hyper-relational link prediction methods only consider the overall perspective when dealing with qualifiers and calculate the score function by combining the qualifiers with the main triple.How-ever,these methods overlook the inherent characteristics of entities and relations.This paper proposes a novel Local and Global Hyper-relation Aggregation Embed-ding for Link Prediction(LGHAE).LGHAE can capture the semantic features of hyper-relational data from local and global perspectives.To fully utilize local and global features,Hyper-InteractE,as a new decoder,is designed to predict missing entities to fully utilize local and global features.We validated the feasibility of LGHAE by comparing it with state-of-the-art models on public datasets.

Improving Link Prediction Accuracy of Network Embedding Algorithms via Rich Node Attribute Information

Complex networks are widely used to represent an abundance of real-world relations ranging from social networks to brain networks. Inferring missing links or predicting future ones based on the currently observed network is known as the link prediction task. Recent network embedding based link prediction algorithms have demonstrated ground-breaking performance on link prediction accuracy. Those algorithms usually apply node attributes as the initial feature input to accelerate the convergence speed during the training process. However, they do not take full advantage of node feature information. In this paper, besides applying feature attributes as the initial input, we make better utilization of node attribute information by building attributable networks and plugging attributable networks into some typical link prediction algorithms and name this algorithm Attributive Graph Enhanced Embedding (AGEE). AGEE is able to automatically learn the weighting trades-off between the structure and the attributive networks. Numerical experiments show that AGEE can improve the link prediction accuracy by around 3% compared with SEAL, Variational Graph AutoEncoder (VGAE), and node2vec.

Multitask Graph Neural Network for Knowledge Graph Link Prediction

Predicting entities in knowledge graphs is a crucial research area,and convolutional neural networks(CNNs)have exhibited significant performance due to their ability to generate expressive feature embeddings.However,sev-eral existing methods in thisfield tend to disrupt entities and relational embed-dings,disregarding the original translation characteristics in triples,leading to incomplete feature extraction.To address this issue and preserve the translation characteristics of triples,the present study introduces a novel representation tech-nique,termed MultiGNN.The suggested approach uses a graph convolutional neural network for encoding and implements a parameter sharing technique.It employs a convolutional neural network and a translation model as decoders.The model’s parameter space is expanded to effectively integrate translation charac-teristics into the convolutional neural network,which allows it to capture these characteristics and enhance the model’s performance.The proposed method in this paper has demonstrated significant enhancements in several metrics on the public benchmark dataset when compared to the baseline method.

Link Prediction in Brain Networks Based on a Hierarchical Random Graph Model

Link prediction attempts to estimate the likelihood of the existence of links between nodes based on available brain network information, such as node attributes and observed links. In response to the problem of the poor efficiency of general link prediction methods applied to brain networks, this paper proposes a hierarchical random graph model based on maximum likelihood estimation. This algorithm uses brain network data to create a hierarchical random graph model. Then, it samples the space of all possible dendrograms using a Markov-chain Monte Carlo algorithm. Finally, it calculates the average connection probability. It also employs an evaluation index. Comparing link prediction in a brain network with link prediction in three different networks （Treponemapallidum metabolic network, terrorist networks, and grassland species food webs） using the hierarchical random graph model, experimental results show that the algorithm applied to the brain network has the highest prediction accuracy in terms of AUC scores. With the increase of network scale, AUC scores of the brain network reach 0.8 before gradually leveling off. In addition, the results show AUC scores of various algorithms computed in networks of eight different scales in 28 normal people. They show that the HRG algorithm is far better than random prediction and the ACT global index, and slightly inferior to local indexes CN and LP. Although the HRG algorithm does not produce the best results, its forecast effect is obvious, and shows good time complexity.

SSDBA:the stretch shrink distance based algorithm for link prediction in social networks

In the field of social network analysis,Link Predic-tion is one of the hottest topics which has been attracted attentions in academia and industry.So far,literatures for solving link prediction can be roughly divided into two categories:similarity-based and learning-based methods.The learning-based methods have higher accuracy,but their time complexities are too high for complex networks.However,the similarity-based methods have the advantage of low time consumption,so improving their accuracy becomes a key issue.In this paper,we employ community structures of social networks to improve the prediction accuracy and propose the stretch shrink distance based algorithm(SSDBA),In SSDBA,we first detect communities of a social network and identify active nodes based on community average threshold(CAT)and node average threshold(NAT)in each community.Second,we propose the stretch shrink distance(SSD)model to iteratively calculate the changes of distances between active nodes and their local neighbors.Finally,we make predictions when these links'distances tend to converge.Furthermore,extensive parameters learning have been carried out in experiments.We compare our SSDBA with other popular approaches.Experimental results validate the effectiveness and efficiency of proposed algorithm.

Learning Universal Network Representation via Link Prediction by Graph Convolutional Neural Network

Network representation learning algorithms,which aim at automatically encoding graphs into low-dimensional vector representations with a variety of node similarity definitions,have a wide range of downstream applications.Most existing methods either have low accuracies in downstream tasks or a very limited application field,such as article classification in citation networks.In this paper,we propose a novel network representation method,named Link Prediction based Network Representation(LPNR),which generalizes the latest graph neural network and optimizes a carefully designed objective function that preserves linkage structures.LPNR can not only learn meaningful node representations that achieve competitive accuracy in node centrality measurement and community detection but also achieve high accuracy in the link prediction task.Experiments prove the effectiveness of LPNR on three real-world networks.With the mini-batch and fixed sampling strategy,LPNR can learn the embedding of large graphs in a few hours.

Link Prediction based on Tensor Decomposition for the Knowledge Graph of COVID-19 Antiviral Drug

Due to the large-scale spread of COVID-19,which has a significant impact on human health and social economy,developing effective antiviral drugs for COVID-19 is vital to saving human lives.Various biomedical associations,e.g.,drug-virus and viral protein-host protein interactions,can be used for building biomedical knowledge graphs.Based on these sources,large-scale knowledge reasoning algorithms can be used to predict new links between antiviral drugs and viruses.To utilize the various heterogeneous biomedical associations,we proposed a fusion strategy to integrate the results of two tensor decomposition-based models(i.e.,CP-N3 and Compl Ex-N3).Sufficient experiments indicated that our method obtained high performance(MRR=0.2328).Compared with CP-N3,the mean reciprocal rank(MRR)is increased by 3.3%and compared with Compl Ex-N3,the MRR is increased by 3.5%.Meanwhile,we explored the relationship between the performance and relationship types,which indicated that there is a negative correlation(PCC=0.446,P-value=2.26 e-194)between the performance of triples predicted by our method and edge betweenness.

Combining Topological Properties and Strong Ties for Link Prediction

Link prediction is an important task that estimates the probability of there being a link between two disconnected nodes. The similarity-based algorithm is a very popular method that employs the node similarities to find links. Most of these types of algorithms focus only on the contribution of common neighborhoods between two nodes. In sociological theory relationships within three degrees are the strong ties that can trigger social behaviors.Thus, strong ties can provide more connection opportunities for unconnected nodes in the networks. As critical topological properties in networks, nodes degrees and node clustering coefficients are well-suited for describing the tightness of connections between nodes. In this paper, we characterize node similarity by utilizing the strong ties of the ego network（i.e., paths within three degrees） and its close connections（node degrees and node clustering coefficients）. We propose a link prediction algorithm that combines topological properties with strong ties, which we called the TPSR algorithm. This algorithm includes TPSR2, TPSR3, and the TPSR4 indices. We evaluate the performance of the proposed algorithm using the metrics of precision and the Area Under the Curve（AUC）. Our experimental results show the TPSR algorithm to perform remarkably better than others.

Integrating Local Closure Coefficient into Weighted Networks for Link Prediction

Triadic closure is a simple and fundamental kind of link formulation mechanism in network.Local closure coefficient(LCC),a new network property,is to measure the triadic closure with respect to the fraction of length-2 paths for link prediction.In this paper,a weighted format of LCC(WLCC)is introduced to measure the weighted strength of local triadic structure,and a statistic similari-ty-based link prediction metric is proposed to incorporate the definition of WLCC.To prove the metrics effectiveness and scalability,the WLCC formula-tion was further investigated under weighted local Naive Bayes(WLNB)link prediction framework.Finally,extensive experimental studies was conducted with weighted baseline metrics on various public network datasets.The results demonstrate the merits of the proposed metrics in comparison with the weighted baselines.

Discrete Choice Analysis of Temporal Factors on Social Network Growth

Social networks like Facebook, X (Twitter), and LinkedIn provide an interaction and communication environment for users to generate and share content, allowing for the observation of social behaviours in the digital world. These networks can be viewed as a collection of nodes and edges, where users and their interactions are represented as nodes and the connections between them as edges. Understanding the factors that contribute to the formation of these edges is important for studying network structure and processes. This knowledge can be applied to various areas such as identifying communities, recommending friends, and targeting online advertisements. Several factors, including node popularity and friends-of-friends relationships, influence edge formation and network growth. This research focuses on the temporal activity of nodes and its impact on edge formation. Specifically, the study examines how the minimum age of friends-of-friends edges and the average age of all edges connected to potential target nodes influence the formation of network edges. Discrete choice analysis is used to analyse the combined effect of these temporal factors and other well-known attributes like node degree (i.e., the number of connections a node has) and network distance between nodes. The findings reveal that temporal properties have a similar impact as network proximity in predicting the creation of links. By incorporating temporal features into the models, the accuracy of link prediction can be further improved.