王治政 Label informed Attributed Network Embedding
新闻来源:IR实验室       发布时间:2018/4/15 0:00:36

Baseline

DeepWalkDeepWalk方法主要是将随机游走过程和语言模型进行了融合。算法想通过随机游走进行初始节点的采样,然后根据SkipGram算法对采样所得的节点进行其邻居节点概率的计算,使其邻居节点出现的概率最大化,从而学习得到网络空间到向量空间的映射函数。具体算法如图1所示。


图片1

图1 DeepWalk算法描述


  LINELINE算法主要是从网络中节点连接的角度进行考虑。算法认为除了有直接连边的节点具有高相似性之外,有较多共同邻居节点的节点也有很高的相似性。因此论文介绍了两种思想并将其进行融合,在大规模网络的表示学习中表现出较好的性能。具体如图2 所示。

微信截图_20180412131352

2 LINE网络实例图

Node2vecNode2vec算法的本质是探索网络中具有相似结构的节点信息以及其邻居节点的信息,即考虑局部信息和全局信息。通过设置参数α将深度优先遍历和广度优先遍历的两种遍历方式进行融合,从而规避单一遍历方式的不全面性。具体的算法示意图如图3所示:


图片3

图3 node2vec算法示意图

Problem Statement

现实世界的网络往往不能单纯的抽象为节点与连边的关系,因为网络的固有属性以及网络节点中的标签属性等因素往往会影响网络的表示。因此,本文主要的研究问题即为将网络节点的标签属性融合到属性网络的表示学习中去。由此提出了LANE的网络嵌入框架。

首先对本文的出现的表示字进行解释,具体如图4所示:

图4 论文中主要符号标识及定义

LANE框架的目表就是将节点标签Y融合到{G,A}的属性网络中,形成网络的向量表示H通过矩阵H表征原始的网络空间。下面给出论文中的LANE框架图。如图5所示。

图片4

图5 LANE框架图

从图5中可以看出,LANE框架图主要由属性网络嵌入和标签信息嵌入两部分构成。最终以一个n*d维的矩阵H表示整个带标签的属性网络的向量表示。从矩阵H的每一行向量中可以明确的得到相似性节点,如节点n1和节点n3

(1)属性网络嵌入表示主要是将节点和节点的属性相结合进行网络表示。在此过程中需要先构造网络的相似矩阵,也就需要对网络先进性初始向量表示,在这里论文引进了谱聚类[1]Spectral Technique的方法来对网络进行一个初步的嵌入。

(2)标签信息的嵌入表示主要是将网络空间中的标签信息进行表示学习,将其映射成为向量,然后与已学习到的属性网络嵌入的矩阵进行融合,最终形成网络的向量空间H

Method

本文主要提出的方法流程如图6所示。

图片5

图6 LANE算法流程伪代码

从图6中可以看出,该算法的核心部分在于将三个独立学习所得的矩阵空间进行融合,通过公式更新来优化初始矩阵,达到最终的网络向量空间的映射。

首先介绍一下矩阵S(G)S(A)。两者分别是图G(仅考虑节点)的相似性矩阵和属性A(仅考虑节点属性)的相似性矩阵,他们都是通过在特定的原始矩阵中计算两个节点的余弦相似度所得,将每两个节点的相似度作为矩阵S(G)S(A)特定位置上的元素。即sij S(G)S(A)中第i行第j列上的元素。

属性网络嵌入描述:度量两个节点之间的相似性可以有两种方式,除了上述的余弦相似度还可以使用两节点的距离表示,即向量差的2范数。通过这两种方式的分歧程度可以较为全面的来表征两个节点的相似度。即公式化表示为:。以图G(仅考虑节点)为例说明,将上式扩展到整个网络可以得到总分歧程度的公式表示如下:

1.png

通过使公式最小化,即总的分歧程度越小,表明两个节点的相似程度越大。但是此公式在运算是并不能很好的进行求解,因此需要对其进行改变。通过分析公式可以看出,公式的核心是对2范数进行计算,此2范数的表示使用了相似矩阵S(G)的每一行的总和作为加和数据将初始向量uiuj进行归一化处理。因此为了解决这个问题,论文选用了拉普拉斯矩阵L(G)来完成这项工作。同时考虑2范数的计算核心是取矩阵的共轭转置与矩阵乘积的最大特征作为解,因此论文选用矩阵的迹来解决这个问题。其具体的公式表示如下:

1.png

这里,将最小化问题转变成最大化问题的实质是在将2范数推导所得的矩阵的迹为,可见于上式存在一个逆的过程,因此在这里将一个最小化的问题转变成了一个最大化的问题。

节点属性A的嵌入过程与此类似,同样得到其向量空间U(A),这里不再赘述。

为了将U(A)融合到U(G)中去,论文借鉴与主成分分析的方法,将其做了一个融合。具体的公式表示为

标签信息嵌入描述:标签信息的特别之处在于其类别小,与网络节点的数量不再一个量级上。因此在处理标签信息时就无法完全依照属性网络的嵌入方法。论文就此给出了一套处理标签信息的数学计算公式。

首先,通过计算YYT来得到标签信息的初始向量空间,同样的在此空间基础上计算两个标签之间的相似度,进而形成标签的相似度矩阵S(YY),但是由于标签的类别极为有限,这就导致其相似矩阵S(YY)的排序存在问题,如果使用公式来作为拉普拉斯矩阵的话很有可能使其不可分解。因此论文提出使用已学习到的U(G)矩阵来做一个过渡,即标签信息的拉普拉斯矩阵公式为:

1.png

通过此公式,可以得到标签信息的向量表示,并可以将标签信息的矩阵融合到图嵌入矩阵之中。

矩阵融合:分别所得的矩阵空间不能完整的表征整个网络的信息,因此文章选择将其融合到一个共同的矩阵空间H中去。具体的融合公式如下所示:

1.png

从公式中可以看出,同样借鉴于主成分分析的思想将上述所得的三个向量空间进行融合,并最大化三者的加和来完成矩阵的融合工作。但是这其中却隐含一个问题,单纯的对三者进行加和将导致某一项对网络的贡献过大,从而使得其余的几项作用很小甚至是不起作用,因此作者引进了参数α1和参数α2来进行权重的调整,尽量的规避上述的问题。即得到右边公式。

函数优化:上面右式中可以看出,在将所得的JGJA JYJcorr 进行融合后,在最大化的条件下求解所得的是基于整个网络的解空间,这对计算机的计算性能和时间要求有着很高的要求,可能会得不到预期的解。因此为了解决这个问题,论文提出了将求全局最优解转变成求解局部最优解,即通过一个拉格朗日求极值的方式对上述公式进行改进,具体改进的公式如下所示:

1.png

先对其求二阶偏导并令其等于0,随后借用拉格朗日极值式对其进行极值的求解,选择结果中的前d个特征向量作为最终的向量空间解。至此,算法结束,得到网络的表示矩阵H

Experiments 

首先对论文的数据集进行简单介绍:

1.png

7 实验数据集

其次,基于此两类数据集,论文对方法中的参数α和维数d做了讨论。在预测节点标签任务中,通过设置不同的α值和维数d,计算其F1值作为评价指标,可以看出在参数α1和参数α2分别位于1~10和大于10这两个条件下其F1值是最大的。而在维数比较时,当d大于20时,LANE算法的性能比baseline算法要明显高很多。


 

微信截图_20180413103714

微信截图_20180413104146


8 参数α实验分析                                                                  9 参数d 实验分析

最后,论文对LANE框架与不同的实验方法进行对比分析,最终得出其框架的高性能表现。以下是作者选用的对比方法或处理手段。

实验结果如下所示:

图片13

结论:通过选择不同比例的训练数据,可以看出LANE框架对标签的预测都要优于其他方法,从而证明了LANE框架的稳定性和优良性。