一种基于LSH技术的链路预测方法

黄寿孟，夏王霞

（三亚学院信息与智能工程学院 海南 三亚 572022）

1 引言

社交网络可以用来描述现实社会中的实际网络，它包括人与人之间的社会关系，物种之间的捕食关系，科学研究中的合作关系等[1]。大量研究已经表明，在真实世界中各种不同社交网络具有许多共同的结构特征，例如小世界性质[2]、无标度性[3]、社团结构等[4-6]。网络中的链路预测是指如何通过已知的网络结构等信息，预测网络中尚未产生连接的两个节点之间产生连接的可能性。网络中的顶点代表用户，边代表用户关系，链路预测问题正是对用户未来关系的分析。

2 相关工作

2.1 局部敏感HASH技术

LSH即Locality Sensitive hash，用来解决在海量数据中进行相似性查找的问题，以图片搜索为例，用户向百度图搜提交待搜索图片，百度图搜将相似的图片返回展示。要实现这样一个应用，需要考虑以下几个步骤。

（1）提取用户提交的图片特征，即将提交图片转换成一个特征向量；

（2）预先将所有收集到的图片进行特征提取；

（3）把步骤（1）中提取的特征与步骤（2）中的特征集合，进行比对，并记录比对的相似值；

（4）对相似值由大到小排序，返回相似度最高的作为检索结果。

步骤（1）（2）是一个图片特征提取的问题，与LSH无关。LSH主要解决步骤（3）（4），在海量特征集中找到相似特征。那么，局部敏感HASH函数必须满足如下条件。

（1）进行相似性搜索时，在概率上可以保证返回值的相似性；

（2）函数族中的各函数，返回值在概率上相互独立，概率独立可以带来统计独立，满足叠加多个函数，提高查准率和通过组合能够避免伪正例、伪反例的好处；

（3）搜索效率：hash比对比线性查询快。

既然是在概率意义下相似性度量，必然会存在着相近样本被hash到不同的hash值情况，同时也必然会存在不相近的样本被hash到相同的hash值情况，前者称为伪反例，后者称为伪正例。伪正例通过与构造解决，即通过多个hash函数，计算同一个特征的多个hash值，只有当多个hash函数均相同时，才认为特征相似。这有效避免了不相似的特征被判定为相似特征的情况。伪反例通过或构造解决，即通过多个hash函数，计算同一个特征的多个hash值，只有多个hash函数有一个hash值相同时，即认为特征相似。这有效避免了相似的特征被判定为不相似特征的情况。

结合与构造与或构造2种方案，可以生成r*b个函数，每r个hash函数代表一组与构造，每b组hash函数族代表一组或构造，当满足一个或构造后特征判定为相似。设一组特征hash的相似概率为s，则通过hash函数与/或构造后的相似概率如下。

1-（1-s^r）^b

在这个概率函数中，s与hash函数的精度相关，属于不可调节参数。当r越大时，相似概率越小，当b越大时，相似概率越大。r与b作为LSH的超参数可以根据实际情况进行相应的调节。

2.2 链路预测指标

衡量链路预测算法精确度的指标有三种：AUC、Precision、Ranking Score。其中，三个指标主要以AUC为主，在AUC基本相同的情况下，可以再以Precision作为标准衡量算法精确度，因此这里只介绍前两个指标。

定义(G,V,E) 为一个无向网络，其中V为节点集合，E为边集合。网络总的节点数为N，边数为M。该网络共有N(N-1)/2个节点对，即全集U。

将已知的连边E分为训练集ET和测试集EP两部分。从数据集中选取一部分边作为测试集EP，并将这部分边从数据集中删去，由数据集中剩余部分的边作为训练集ET。显然有E=ET ∪ EP，且ET ∩ EP=Ø。同时，网络中还有一些节点之间并没有边相连，将这些边称为不存在的边。

2.2.1 AUC（area under the receiver operating characteristic curve）

AUC从整体上衡量算法的准确性。链路预测算法在经过训练后可以得到网络中每一对节点的相似值（即边的相似值）。AUC指标即是基于测试集中边的相似值和不存在的边的相似值的比较（即以不存在的边作为基准）。

若Sim测试＞Sim不存在，则数值的分子加1（此时证明预测效果良好）；

若Sim测试=Sim不存在，则数值的分子加0.5（此时相当于随机选择）；

若Sim测试＜Sim不存在，则数值的分子加0。

Sim表示相似值，数值的分母则是测试集中的边的相似值与不存在的边的相似值比较的次数。

AUC指标即为数值分子与数值分母的比值，AUC大于0.5的程度衡量了算法在多大程度上优于随机选择的算法。

2.2.2 Precision

Precision只考虑前L位的边是否预测准确。链路预测算法经过训练后会得到节点对之间的相似值，去除训练集ET中的边，仅将测试集EP和不存在的边集合中的边的相似值进行排序，排序后取前L个。假设L个中有N个属于测试集，那么Precision值为N/L。

3 预测方法

3.1 定义

LSH技术是从海量高维数据中查询与某个数据最相似的一个数据或数据集，常用于人脸检索。它的基本思想是基于原始数据空间中相邻的数据经过同一个映射变换之后，处于相邻区域的概率仍然较大的理念；人为地选取一些具有上述性质的函数来作为哈希函数，使得相邻的数据映射后处在哈希表的同一个位置，这样就可以轻松地找到与该数据相似的数据集。即通过选取的哈希函数的映射变换，能够将原始的数据集划分为若干较小的子集，且每个子集中的元素个数较小且相邻。偏好向量RD，即xRD，y为社交网络用户向量Rd，即y

对于任意用户有两个特征值:x,y，其中x为用户访问Rd，存在一个哈希函数H(x)满足以下两个条件，则称为敏感哈希函数，记作H(S1,S2,p1,p2）:

(1)如果sim(x,y)≥S1，则P(h(x)=h(y))≥p1

(2)如果sim(x,y)≤S2，则P( h(x)=h(y))≤p2

其中，S1,S2是近邻搜索的兴趣阈值，S1＞S2,p1,p2是概率值且p1＞p2,sim()是相似度函数。

LSH算法重点在于如何将数据映射成二进制编码的概率最大化，即将用户特定向量表示二值化（仅有0和1的表示）。

3.2 预测方案设计

将社交网络的用户数据进行数据清洗，产生构建用户位置签到频率矩阵和用户关系连通子图，接着将前者进行矩阵分解出用户访问偏好向量，将后者细分为网络表示学习得到社交网络用户向量、并构建训练集与测试集。然后，将用户访问偏好向量与社交网络用户向量进行锚链接映射融合，得到融合后的用户向量表示，并引入LSH技术将输入训练集和测试集将其转换为点对关系融合，最后进行模型训练和测试评估性能，这就是基于LSH技术的预测模型LSH-P，见图1。

图1 LSH-P预测方案

3.2 预测算法

预测算法如图2所示。

图2 预测算法

4 实验分析

4.1 实验准备工作

本实验采用Gowalla和Foursquare两种开源数据集[7]其中@NY表示纽约，@TY表示东京，@WHG表示华盛顿，@CCG表示芝加哥，本实验对照基准模型有walk2friends[8]和DeepWalk[9]，评估指标有AUC、精度、查全率和F1值（精度与查全率的平均）[10]。AUC评估指标实验结果见表1，说明在不同的数据集中，LSH-P模型的AUC值都优于walk2friends和DeepWalk。

表1 LSH-P的AUC预测结果

对评估指标精度、查全率、F1值的衡量实验，如表2、表3所示，从两表中可以得到在链路预测任务中，LSH-P预测效果是最佳的，这是因为LSH-P模型加入LHS技术。

表2 Foursquare数据集的预测结果

表3 Gowalla数据集的预测结果

5 结语

为了提升链路预测的效果，本文提出一种LSH技术的数据融合训练，通过用户向量点对关系训练与测试，从而进一步提升链路预测的综合性能。链路预测是网络信息挖掘中最基础最本质的问题，通过对已经观察到的网络结构和其他外部信息的分析，挖掘缺失的连接和预测未来可能出现的连接。链路预测算法在生物网络分析、朋友及关注对象推荐、个性化推荐、网络演化模型评价、标签分类、网络重构等问题上有着广泛的应用。