链接预测学习总结
链接预测（Link Prediction）是知识图谱嵌入（Knowledge Graph Embedding）的应用之一，将知识图谱中实体和关系的内容映射到连续向量空间中，对知识图谱中的实体或关系进行预测，即（h,r,?），（?,r,t），（h,?,t）三种知识图谱的补全任务。现有的方法主要是对网络的拓扑结构进行分析，并作出预测。比较流行的方法有基于相似度的、概率统计、SVM或KNN等算法，以及较新的基于注意力的、基于CNN的、基于GCN的链接预测算法。
链接预测可以应用在多个领域。目前应用比较广泛的是：1）在社交网络中向用户推荐熟人和相似的用户，大多数社交网络都使用链接预测技术来推荐熟人。2）在生物领域，链接预测用来发现可以发生相互作用的蛋白质。由于目前有很多蛋白质人们都不熟悉，实验的时间和金钱成本高，所以需要较准确的预测，减少成本。3）用于在已知部分节点类型的网络中预测未标签节点的类型，如用于判断一篇学术论文的类型或从犯罪网络中预测某些犯罪行为。
首先对基本概念进行简单的说明。图或者网络G的有序对G=<V，E>。V是图中的节点，E是边，节点x与节点y的链接表达为。|V|表示节点的数量，|E|表示边的数量。
表示与x相邻的节点，|
|表示与x相邻节点的个数，
表示网络中节点的平均度数。
基于相似性的方法是预测网络中相似的节点。该方法主要是用得分函数对节点打分并排序，故序列中得分最高的就是最终预测的链接。目前主要有以下三种方法:
1.局部法。目前已经发表的局部法至少有十几种，本文中仅列举以下四种。
（1）Common Neighbors(CN)是根据两个节点共同的邻居节点的数量来判断相似性的。公式为：
（2）The Adamic-Adar Index(AA)对x和y的共同邻居节点的度数做了对数惩罚。可以这么理解：如果x与y有一个共同爱好，如果很多人都有这个爱好，那么x与y相似度就不大。如果只有x与y有这个爱好，那么x与y的相似度就大。公式如下：
（3）The Resource Allocation Index(RA)与上述方法很相似，只是去除了对数惩罚，但是在很多网络中效果更好。公式如下：
（4）Resource Allocation Based on Common Neighbor Interactions (RA-CNI)是在上个方法上稍加改进。公式如下：
通过上面四种算法，可以发现对算法改进可以只是对公式的简单修改，但性能上却又不少提升。
2.全局法。
（1）Katz指数算法，是1953年Katz提出的。公式为：，已在这篇文章中详细推导了，此处不再解释。全局法相较于其他两种方法，效果较差。
（2）Random Walks(RW)随机游走算法。公式为:。其中
表示由节点x出发，迭代t次到达其它节点的概率向量。
是对网络的邻接矩阵的每一行进行归一化。参考文献2对随机游走算法进行了详细的解释。
3.准局部方法。
（1）The Local Path Index(LPI)也是基于Katz指标，但是对路径的数量进行了限制。=2时该方法就等价于上述的CN方法，由于时间复杂度，该方法使用时通常令
=3，效果较好。
（2）Local Random Walks(LRW)局部随机游走算法。基于随机游走算法，但是固定了迭代的次数。公式为：
由于网络的形成是一个复杂的过程，受到很多因素的影响，因此不可能设计一个方法比其他的方法在任意的网络上效果都好。下图在YST,CEL等数据集上对这些方法进行了实验，可以发现局部法和准局部法效果较好。
总结。
参考文献：