【CN109636658A】一种基于图卷积的社交网络对齐方法【专利】

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号(43)申请公布日(21)申请号201910044138.4(22)申请日2019.01.17(71)申请人电子科技大学地址611731四川省成都市高新区（西区）西源大道2006号(72)发明人钟婷　李小妍　温子敬　周帆　(51)Int.Cl.G06Q50/00(2012.01)G06N3/04(2006.01)(54)发明名称一种基于图卷积的社交网络对齐方法(57)摘要本发明公开了一种基于图卷积的社交网络对齐方法，首先利用图卷积神经网络对社交网络中的用户关系进行网络嵌入，然后利用高斯核函数将嵌入空间升维，得到高维空间中节点的相似度矩阵，利用锚节点来表示非锚节点，得到两个社交网络最终的网络嵌入，再利用已知的锚节点信息来学习一个网络映射函数，最后利用该函数将两个社交网络中的节点进行对齐。本发明不需要提取大量的用户隐私信息，利用图形就能够很好地表示社交网络用户之间的社交关系。通过引入高斯核函数将嵌入空间升维，可以分离原始低维嵌入空间中不可分离的节点。利用已知锚节点来学习网络映射函数，可以大大地提高社交网络对齐的准确率，从而实现了一种优于现有方法的社交网络对齐方法。权利要求书3页说明书6页附图1页CN109636658A2019.04.16CN109636658A1.一种基于图卷积的社交网络对齐方法，其特征在于包括以下步骤：S1，利用图卷积神经网络来对社交网络中的用户关系进行网络嵌入，得到能代表用户社交关系的网络嵌入，即为每一个用户节点生成包含用户社交关系信息的一个嵌入向量；S2，利用高斯核函数将嵌入空间映射到更高的维度，从而分离原始低维嵌入空间中不可分离的节点，计算升维后节点嵌入向量间的距离，并对嵌入向量的距离进行归一化处理得到高维空间中节点的相似度矩阵；S3，利用高维空间中节点的相似度矩阵，得到两个社交网络用已知锚节点表示非锚节点的网络嵌入，再利用已知的锚节点信息来学习一个网络映射函数；S4，得到网络映射函数之后，利用该函数将两个社交网络中的节点进行对齐。2.根据权利要求1所述基于图卷积的社交网络对齐方法，其特征在于所述步骤S1包括以下分步骤：S11，利用图卷积神经网络将社交网络Gs进行网络嵌入；定义社交网络图为Gs＝(Vs，Es)，Vs＝{ui|i∈[1，2，...，N]}是图Gs所有顶点的集合，每个顶点代表一个用户，N为图中的顶点数，也就是用户的数量，小写字母u代表用户；Es＝{eij|i，j∈[1，2，...，N]}是图Gs边的集合，图Gs中的每条边eij∈Es表示用户ui和用户uj存在社交关系；做如下定义：定义图的邻接矩阵为一个表示节点之间关系的矩阵，记为其中表示N×N维的向量空间，矩阵元素定义为：若eij∈Es，则Wij＝1，若则Wij＝0；为对角矩阵，称为图Gs的对角度矩阵，对角线元素为Dii＝∑jWij；定义矩阵由此定义一个对角矩阵其对角线元素为令定义两层神经网络如下：其中σ(·)是ReLU激活函数(ReLU(*)＝max(0，*))，是第一层学习的参数矩阵，是第二层学习的参数矩阵，其中F0是第一层输出的维数，F1是第二层输出的维数；令定义交叉熵损失函数如下：其中通过不断的训练将L的值降到最小，我们就得到了社交网络Gs的一个基于GCN的图表示模型Us；Us的第i行ui是社交网络Gs中第i个用户的网络嵌入表示，其维度为F1；S12，利用图卷积神经网络将社交网络Gt＝(Vt，Et)进行网络嵌入；该过程与步骤S11相同，最后得到社交网络Gt的网络嵌入Ut；Ut的第i行vi是社交网络Gt中第i个用户的网络嵌入表示，其维度为F1。3.根据权利要求1所述基于图卷积的社交网络对齐方法，其特征在于所述步骤S2包括以下分步骤：S21，计算网络嵌入Us映射到高维空间之后节点之间的相似度矩阵Ss；定义由步骤S1得权　利　要　求　书1/3页2CN109636658A2到的社交网络嵌入u构成的空间为通过一个函数φ将u投影到更高维特征空间中，即性质优良的升维函数φ往往比较复杂不易求取；求解相似度矩阵并不需要知道函数φ的具体形式，而只需能计算φ(ui)和φ(uj)的点积，并由此计算出φ(ui)和φ(uj)的距离并进行归一化处理即可得到相似度矩阵；用非线性函数κ来表示向量φ(ui)和φ(uj)之间的点积：κ(ui，uj)＝〈φ(ui)，φ(uj)；采用机器学习中常用的高斯核函数进行升维，即定义其中σ＞0为高斯核的带宽，它是一个超参数，我们实验中将其设置为3；由此就可以直接通过该核函数计算φ(ui)和φ(uj)之间的距离：D(φ(ui)，φ(uj))＝||φ(ui)-φ(uj)||2＝κ(ui，ui)+κ(uj，uj)-2κ(ui，uj)   (3)然后，构造一个相似矩阵其中元素sij∈Ss为公式(3)定义的φ(ui)和φ(uj)之间的距离的归一化表示，即sij(φ(ui)，φ(uj))＝1/exp{D(φ(ui)，φ(uj))}    (4)上述sij的值被标准化到(0，1]区间内；sij的值越大，表示用户ui和uj的网络嵌入表示越接近；S22，计算网络嵌入Ut映射到高维空间之后节点之间的相似度矩阵St；该过程与步骤S21相同，最后得到相似度矩阵St。4.根据权利要求1所述基于图卷积的社交网络对齐方法，其特征在于所述步骤S3包括以下分步骤：S31，通过步骤S11得到的网络嵌入Us和步骤S21得到的相似度矩阵Ss，得到社交网络Gs利用锚节点表示非锚节点的网络嵌入U′s；定义：ui和vj分别是Gs和Gt中的用户，若已知在真实世界中它们指向同一个自然人，那么称ui和vj为锚节点；利用训练集中已知的锚节点构建一个中间矩阵其第i行记为ci，若ui为锚节点，则令ci＝ui，否则ci＝0；然后将矩阵Cs与步骤S21得到的相似矩阵Ss相结合来得到用锚节点表示非锚节点的节点网络嵌入表示：U′s＝Ss·Cs    (5)其中的第i行是一个向量通过这种方式，能使原本网络嵌入中的不可分离的节点变得可分离；S32，通过步骤S12得到的网络嵌入Ut和步骤S22得到的相似度矩阵St，得到社交网络Gt用锚节点表示非锚节点的网络嵌入U′t；该过程与步骤S31相同，最后得到网络嵌入U′t；其中的第i行是一个向量v′i；S33，得到两个图Gs和Gt用锚节点表示非锚节点的网络嵌入之后，利用已知的锚节点来学习一个网络映射函数Φ；该函数是用全连接神经网络实现的参数化函数，具体表达形式为Φ(u′i，K，b)＝Ku′i+b，其中K和b是需要学习的参数；定义(ui，vj)(ui∈Vs，vj∈Vt)为一对锚节点，u′i是ui用锚节点表示非锚节点的嵌入向量，v′j是vj用锚节点表示非锚节点的嵌入向量，u′i通过函数Φ映射得到的网络嵌入为u″i，为了度量u″i和v′j之间的相似性，可以计权　利　要　求　书2/3页3CN109636658A3算它们之间的余弦值由余弦函数的性质，若u″i和v′j的余弦值越大，则u″i和v′j越相似；因此可以定义以下损失函数来训练函数Φ：l(u′i，v′j)＝argmin{1-cos〈Φ(u′i，K，b)，v′j}   (6)通过最小化上面的损失函数，我们就得到了一个网络映射函数Φ。5.根据权利要求2所述基于图卷积的社交网络对齐方法，其特征在于利用图卷积神经网络对社交网络中的节点进行网络嵌入，为每一个用户节点生成包含用户社交关系信息的一个嵌入向量；训练的损失函数为：6.根据权利要求3所述基于图卷积的社交网络对齐方法，其特征在于利用高斯核函数将嵌入空间映射到更高的维度，从而分离原始低维嵌入空间中不可分离的节点。7.根据权利要求4所述基于图卷积的社交网络对齐方法，其特征在于利用已知锚节点学习得到网络映射函数，该函数可以用来进行社交网络对齐；训练网络映射函数的损失函数为：l(u′i，v′j)＝argmin{1-cos〈Φ(u′i，K，b)，v′j}。8.根据权利要求1所述生成对抗网络的轨迹数据分类方法，其特征在于所述步骤S4的具体实现方式为：设ui为Gs中的某一节点，u′i是ui用锚节点表示非锚节点的嵌入向量，u′i通过函数Φ映射之后的网络嵌入u″i，计算u″i和Gt中所有节点网络嵌入的余弦值，在所有余弦值当中找到最大的前k个，也即在Gt中中找到与节点ui最匹配的k个节点；如果在该k个节点中有该节点的对应节点，则认为该匹配是成功的；按照此方法可以对两个社交网络Gs和Gt中的节点进行对齐。权　利　要　求　书3/3页4CN109636658A4一种基于图卷积的社交网络对齐方法技术领域[0001]本发明属于机器学习中的神经网络领域，是一种基于深度学习的方法，主要利用图卷积神经网络(Graph Convolutional Neural Networks，GCN)对社交网络中的用户进行网络嵌入(Network Embedding，NE)从而将网络中的用户节点用嵌入向量表示，并在此基础上利用高斯核函数对嵌入空间进行维度提升从而分离在低维空间难于区分的用户节点，最后利用锚节点信息进行神经网络训练得到两个社交网络中用户节点的映射函数，达到将两个社交网络中的用户对齐的目的。背景技术[0002]社交网络对齐的主要目的是在两个社交网络之间找到对应用户，即在不同社交网络中对应真实世界中的同一个自然人的用户。由于社交网络对齐在用户行为预测、身份验证和隐私保护等各种应用程序设置方面的重要影响，最近引起了越来越多的关注。[0003]随着社交网络服务(Social Network Service，SNS)的普及，网络数据无处不在。社交网络可以通过社交网络图(Social Network Graph，SNG)来表示。该图是未加权的无向图，图的每个顶点都代表一个用户，两点之间的边代表两个用户之间的关系。在现实中，因为社交网络服务商会对用户隐私进行保护，往往不能知道两个社交网络所有的对应用户，但是可能通过其它途径获知两个社交网络一部分的对应用户。这种两个不同的社交网络中已知的对应节点被称为锚节点。本发明根据社交网络图以及锚节点信息来进行两个社交网络的对齐。[0004]传统的网络嵌入方法可以分为两种，一种方法通常从账户配置文件或活动(如用户名、性别、写作风格等)中提取出一组特征来代表用户；另一种方法是通过利用网络结构信息来进行网络嵌入。随着图形表示技术的发展，本发明利用图卷积方法来进行网络嵌入，利用锚节点来训练两个社交网络间节点的映射函数，仅仅依据社交网络图的结构信息及少量的锚节点信息，就能够实现优于现有方法的社交网络对齐。发明内容[0005]本发明的目的是依据社交网络图的结构信息及少量的锚节点信息而不需要利用用户的其它特征信息来解决社交网络对齐问题，即在两个不同的社交网络中找到对应用户。[0006]本发明的思路为，利用图卷积神经网络来对社交网络中的用户关系进行网络嵌入，得到能代表用户社交关系的网络嵌入，在此基础上引入高斯核函数来优化网络嵌入从而帮助识别原始嵌入空间中不可分离的节点，最后利用锚节点来训练两个社交网络间节点的映射函数进一步提高社交对齐的准确率。[0007]基于上述发明思路，本发明提出一种基于图卷积的社交网络对齐方法，其具体包括以下步骤：[0008]S1，利用图卷积神经网络来对社交网络中的用户关系进行网络嵌入，得到能代表说　明　书1/6页5CN109636658A5用户社交关系的网络嵌入，即为每一个用户节点生成包含用户社交关系信息的一个嵌入向量；[0009]S2，利用高斯核函数将嵌入空间映射到更高的维度，从而分离原始低维嵌入空间中不可分离的节点，计算升维后节点嵌入向量间的距离，并对嵌入向量的距离进行归一化处理得到高维空间中节点的相似度矩阵；[0010]S3，利用高维空间中节点的相似度矩阵，得到两个社交网络用已知锚节点表示非锚节点的网络嵌入，再利用已知的锚节点信息来学习一个网络映射函数；[0011]S4，得到网络映射函数之后，利用该函数将两个社交网络中的节点进行对齐。[0012]基于图卷积的社交网络对齐方法，所述