《Label informed Attributed Network Embedding》论文解析

本篇论文于2017年发表在第十届ACM子会WSDM（CCF列表B类会议）上的。这是我最近在实验室组会上主讲的一篇论文，因为最近正在研究表示学习算法，当我看到这篇文章的时候感觉问题很新颖，因此对本篇论文进行了研读，所以把我的一些理解记录一下。我将从论文中涉及到的baseline开始介绍，然后在过渡到论文提出的方法，最后对论文的实验和结果进行适当的讨论和介绍。

Baseline：

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

图1 DeepWalk算法描述

LINE【2】：LINE算法主要是从网络中节点连接的角度考虑。算法认为除了有直接连边的节点具有高相似性之外，有较多共同邻居节点的节点也有很高的相似性。像图2中节点6和节点7则是因为有直接连边而保持其相似性，节点5和节点6因为共享较多的邻居节点而保持其相似性。因此论文介绍了这两种思想并将其进行融合，在大规模网络的表示学习中表现出较好的性能。具体算法可参见文献【2】。

图2 LINE网络实例图

Node2vec【3】：Node2vec算法的本质是探索网络中具有相似结构的节点信息（如图3中的节点u和节点S6）以及节点的直接邻居节点的信息（如图3中节点u的邻居节点），即综合节点的考虑局部信息和全局信息。算法主要通过设置参数α将深度优先遍历和广度优先遍历的两种遍历方式进行融合，从而规避单一遍历方式的不全面性，在利用词向量模型将遍历所得的节点进行向量化表示。具体的算法可参见文献【3】：

图3 node2vec算法示意图

Problem Statement：

现实世界的网络往往不能单纯的抽象为节点与连边的关系，因为网络节点的固有属性以及网络节点所属的标签属性等因素往往会对网络的表示产生影响。因此，本文主要的研究问题即为将网络节点的标签属性融合到属性网络（由网络的节点信息和节点属性信息构成的网络）的表示学习中去。由此提出了LANE的网络嵌入框架。首先对本文的出现的主要标识字符进行解释，具体如图4所示：

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

LANE框架的目标就是将节点标签Y融合到{G,A}的属性网络中，形成网络的向量表示H。然后通过矩阵H表征原始的网络空间。

下面给出论文中的LANE框架图。如图5所示。

图5 LANE框架图

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

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

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

Method：

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

图6 LANE算法流程伪代码

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Experiments：

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

图 7 实验数据集

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