携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第22天，dl.acm.org/doi/10.1145…

会议：KDD ’18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （CCF-A）

年度：2018/08/19

ABSTRACT

网络嵌入近年来受到越来越多的研究关注

现有的方法表明，高阶邻近度在捕捉网络的底层结构方面起着关键作用

然而，保持高阶邻近性的两个基本问题仍然没有解决

• 首先，尽管不同的网络和目标应用通常需要不同阶次的邻近度，但所有现有的方法都只能保持固定阶次的邻近度
• 其次，在给定一定阶次邻近性的情况下，现有方法不能同时保证精度和效率

为了应对这些挑战，我们提出了一种基于奇异值分解框架的网络嵌入方法AROPE(AROPE)。从理论上证明了特征分解重权定理，揭示了不同阶次的邻近度之间的内在联系

利用这一定理，我们提出了一种可伸缩的特征分解解来导出嵌入向量，并将它们在任意阶的邻域之间移动

理论分析表明，该方法在不同阶次间移动嵌入向量具有较低的边际代价，在给定阶次的情况下，我们的方法可以得到全局最优解，并且该方法的总时间复杂度与网络规模呈线性关系

在几个大规模网络上的大量实验结果表明，我们提出的方法在包括网络重建、链路预测和节点分类在内的各种任务中都显著且一致地优于基线

1 INTRODUCTION

网络嵌入是一种在保持网络固有性质和结构的前提下，用低维向量表示节点的方法，近年来受到越来越多的研究关注。这样，基于特征的机器学习算法可以很容易地应用于网络分析。前人的工作已经证明，除了成对边之外，节点之间的高阶邻近度对于捕捉网络的底层结构非常重要[3，8，13，21，23]，因此可以为学习嵌入向量提供有价值的信息。因此，人们提出了一系列在网络嵌入中保持高阶邻近度的方法

尽管取得了成功，但仍有两个根本问题没有解决

首先，现有的所有方法都只能保持定阶的邻近性。然而，具有特定顺序邻近度的嵌入不一定在所有网络和目标应用程序上执行得最好[3，24]

例如，在分类任务中，不同粒度的类通常需要不同阶的邻近度，即粗粒度的类需要高阶的邻近度，而细粒度的类需要低阶的邻近度[24]

我们还对阶数的影响进行了实证验证，如图5所示。要合并不同阶数的邻近度，现有方法必须多次重复运行，并分别为每个节点计算多次嵌入

例如，DeepWalk[23]通过超参数(即预定义的窗口大小)设置顺序，并且每次对于不同的超参数必须从头开始重新运行算法

考虑到更一般的情况，不同阶的邻近度需要用不同的权重来保存，例如像[14]中那样组合原子邻近度以形成更精细的邻近度度量，现有的方法由于不变地结合高阶邻近度而面临更多的困难。

其次，即使给定一定的阶次邻近性，现有方法如何同时保证精度和效率仍然是一个悬而未决的问题。例如，一系列的工作[13，23]采用随机游动来探索高阶逼近，并使用随机梯度下降(SGD)进行优化。由于目标函数不是凸的，而且为了保证效率，通常将优化的迭代次数设置得很小，这些方法不能保证全局最优解[4]。另一方面，基于矩阵分解[3，35]或深度学习[34]的网络嵌入方法存在效率问题。如何在保持任意阶邻近性的情况下同时保证精度和效率就更具挑战性了。

提出了一种基于奇异值分解框架的网络嵌入方法AROPE1(AROPE1)

我们从理论上证明了特征分解重权定理，它揭示了不同阶邻近度之间的内在联系是对维度进行重加权和重新排序

在这个定理的基础上，我们提出了一种可伸缩的解决方案来导出嵌入向量。同时，我们可以在任意阶的邻近度之间移动嵌入向量，即即使在不同阶的邻近度被任意加权的一般设置下，也可以从一些基本嵌入向量中有效地获得任意邻近度的嵌入向量

理论分析表明：

• i)在不同的阶数和权值之间移动嵌入向量时，我们的方法具有较低的边际代价
• ii)给定一定的阶数，我们的方法可以得到全局最优解
• iii)我们的方法的总时间复杂度是关于网络规模的线性的

在几个具有数百万个节点和边的大规模网络上进行了广泛的实验

实验结果表明，在网络重构、链路预测和节点分类等网络嵌入应用中，我们提出的方法在性能上都明显优于现有的网络嵌入方法

综上所述，本论文的主要贡献如下：

• 提出了一种新的网络嵌入方法AROPE，该方法以较低的边际代价支持任意阶次的移位
• 我们证明了特征分解重加权定理，以揭示奇异值分解框架中不同阶邻近度之间的内在联系。理论分析表明，该方法能够在线性时间复杂度下得到全局最优解
• 大量的实验结果表明，该方法在两个大型网络上的网络重构和链路预测的精度都提高了100%以上

2 RELATED WORK

网络嵌入最近已经成为一种用低维向量来表示节点的范例，旨在弥合网络分析和机器学习技术之间的差距。接下来，我们简要回顾了一些有代表性的网络嵌入方法，读者可以参考文献[8]进行全面的综述

早期的网络嵌入方法，也称为图嵌入，被作为降维问题来研究[36]。然而，这些方法侧重于两两相似。如何保持高阶邻近关系是最近一个非常吸引人的研究问题

• DeepWalk[23]首先提出使用截断随机游走来探索高阶邻接关系，并利用Skipgram模型[20]来推导嵌入向量。Line[30]采用了类似的想法，但将步行长度设置为具有明确目标函数的长度。
• Node2vec[13]是进一步提出的，它具有潜在的偏向随机游动，以获得更大的灵活性
• 如文[4，25]所示，这些基于随机游动的方法等价于分解高阶邻近矩阵。通过使用有效的优化方法，如随机梯度下降(SGD)[30]，这些方法比一些矩阵分解方法更具伸缩性，但不能保证全局最优解

另一方面，还采用了显式矩阵分解方法来保持高阶逼近性

• GraRep[3]将奇异值分解直接应用于高阶邻接矩阵，取得了良好的性能
• 在[35]中应用了非负矩阵分解，以保持网络的高阶邻近性和社区结构。然而，这两种方法都存在可扩展性问题，无法应用于大规模网络。为了解决效率问题
• [4]引入了一个保持高阶邻近度的统一框架，并提出了一种稀疏化技术来加速SVD方法
• 在[38]中，在矩阵分解中引入了另一种逼近技术。尽管这些方法有了显著的改进，但仍然不能保证得到全局最优解
• 这种困境的一个例外是HOPE[21]，它使用广义奇异值分解来保持具有线性时间复杂度的有向网络中的高阶邻近性。然而，它需要一种特殊形式的高阶近似。实际上，希望的目标函数是我们方法的一个特例，它将阶数设为无穷大，权重设为指数衰减(见定义3.1)。除此之外，希望不能保持其他order的接近，也不能在不同订单之间移动

研究了保持高阶邻近度的深度学习方法

• SDNE[34]首先考虑了网络嵌入中的高度非线性，并使用深度自动编码器同时保留了一阶和二阶邻近度。然而，SDNE只能保持前两阶的邻近性。此外，它还存在效率问题

探讨了如何将边信息融入到网络嵌入中。例如

• 文献[5，9]将元路径引入到嵌入异类信息网络中以处理节点类型
• 在[17，37]和[22，32，39]中分别将节点属性和节点标签合并到网络嵌入中

动态网络嵌入[19，41，42]进一步考虑了网络的演化特性

• DHNE[33]扩展了SDNE以保持超网络中的不可分解性

在本文中，我们关注的是最基本的情况，即只有静态网络结构可用

综上所述，如何在很大程度上保证高阶邻近关系的效率和准确性仍然是文献中未解决的问题

此外，现有的方法只能保持固定顺序的邻近度，不能跨顺序移动

3 PROBLEM FORMULATION

3.1 Notation

假设我们有一个网络$G$，有$N$个节点和$M$条边

我们用$A$表示邻接矩阵。$A(i，:)$和$A(:，i)$分别表示其第$i$行和第$i$列

$A(i,j)$是节点$i$和$j$之间边的权值

在本文中，我们主要考虑无向网络，所以$A$是对称的，$A(i,j)=A(j,i)$

$A(i,j)$对于无权网络是0或1，对于有权网络是任意非负数。$A^T$表示$A$的转置

在本文中，我们使用粗体大写字符表示矩阵，使用粗体小写字符表示向量。函数用花絮标记，例如F(·)。

3.2 Arbitrary-Order Proximity Preserved Network Embedding

Definition 3.1 (High-Order Proximity)

给定无向网络的邻接矩阵$A$，将高阶接近度定义为$A$的多项式函数$F(\cdot )$

其中

• $q$为顺序
• $w_1，\dots ，w_q$是权重值

请注意，我们将$q$阶的接近程度称为从$1$阶到$q$阶的所有阶的加权组合，而不是单独的$q$阶

如果和收敛，我们允许$q=+\infty$
按照前面的工作，我们将假设$\forall 1\le i\le q$的$w_i\ge 0$。当提及不同的高阶邻近时，我们使用下标来区分，例如$F_i(\cdot )$

先前的研究表明，许多最先进的网络嵌入方法显式或隐式地保留了这种高阶邻近性[4,25,38]

值得一提的是，一些工作表明额外的非线性包装函数是重要的[4]，而其他工作表明额外的函数具有有限的效果[38]
我们在本文中不考虑包装函数，留给以后的工作

邻接矩阵$A$可以用其他变换形式替换，如拉普拉斯矩阵[1]，只要替换矩阵是稀疏对称的

为了简单起见，我们在本文的其余部分主要讨论邻接矩阵，但类似的想法可以直接推广

我们还重用了$F(\cdot )$的表示法，当函数作用于一个数字时，Eq.(1)中的矩阵乘积被数字的乘积代替

为了在低维向量空间中保持高阶接近，广泛采用的方法是矩阵分解，它最小化了以下目标函数:

其中

• $U^{\ast }，V^{\ast }\in R^{N\times d}$是内容/上下文嵌入向量
• $d$是空间的维数
• 在不失一般性的情况下，我们使用$U^{\ast }$作为内容嵌入向量

根据Ercart-Young定理，通过截断SVD[10]（ truncated SVD）可以得到Eq.(2)的全局最优解

• 其中$[U，\Sigma ，V]$为$S$的d顶维SVD结果（ top-d SVD ）
• 其中$U,V\in R^{N\times d}$，每一列对应一个左/右奇异向量
• $\Sigma \in R^{d\times d}$为奇异值降序对角矩阵

将$\Sigma$乘入$U,V$即可得到嵌入:

但是，直接计算$S$和执行$SVD$既耗时又耗时

此外，由于不同的网络和目标应用通常需要不同订单的临近，如何在不同订单之间转换也是一个挑战

在下一节中，我们将展示一个可伸缩的解决方案，以保留基于上述公式的任意阶邻近性，该解决方案支持跨阶转移

4 AROPE: THE PROPOSED METHOD

4.1 Problem Transformation

求解方程(2)(3)中的SVD问题，我们首先将其转化为特征分解问题

表示$S$的顶d特征分解为$[\Lambda ，X]$，其中

• $\Lambda \in R^{d\times d}$是特征值按绝对值降序排列的对角矩阵
• $X\in R^{N\times d}$，每一列对应一个特征向量
• $[\Lambda (i,i)，X(:，i)]，1\le i\le d$也被称为特征对

然后，通过以下定理将奇异值分解与特征分解联系起来

奇异值分解与特征分解得到的结果之间是有关联关系的

证明可以在线性代数教科书中找到，如[29]

利用该定理，我们可以很容易地由式(4)的特征分解得到SVD的结果，由式(5)得到SVD的结果

接下来，我们只需要专注于求解S的特征分解

利用特征分解得到的结果间接得到SVD的结果

4.2 Eigen-Decomposition Reweighting

为了高效地求解S的特征分解，我们的关键发现是利用Eq.(1)中定义的任意阶近邻的形式，不同近邻的特征分解结果是高度相关的

具体来说，我们有如下定理

定理表明，在不对S进行特征分解的情况下，用$F(\lambda )$替换$\lambda$，就可以由$A$的特征分解结果得到$S$的特征分解结果

要计算$S$的特征分解，只需要计算$A$的特征分解
再对A特征分解得到的$\lambda$使用函数$F()$即可
$F(\lambda )$即为$S$的特征分解（$S=F(A)$）

事实上，该定理揭示了不同阶近邻之间的内在关系。如果我们将每个特征向量视为网络中节点的“坐标”，将每个特征值视为坐标的“权值”，那么，保持不同阶的邻近性就相当于对维度进行重新加权

另一个问题是，在进行特征分解加权之后，特征值的阶数可能会发生变化，即$S$的顶d特征分解不一定是A的顶变分解的加权

为了解决这个问题，我们可以证明任意$S$的顶d特征分解保证是A的顶l特征分解的重权，其中$l=L(A,d)$是网络和d的函数

具体来说，表示${\lambda }_1^{\prime }，{\lambda }_2^{\prime }，\dots ，{\lambda }_d^{\prime }$为$S=F(A)$的顶退化值，其绝对值由高到低排列

从定理4.2，我们有

即$p_i$是${\lambda }_i^{\prime }$在高阶变换$F(\cdot )$之前的阶数

因此，我们只需要顶部$p_i,1\le i\le d$ $A$的特征分解就可以得到${\lambda }_1^{\prime }，\dots ，{\lambda }_d^{\prime }$为$S$

我们可以证明以下定理:

我们还证明定理4.3在以下推论中是紧密的

由上述定理可知，要得到任意$F(\cdot )$的顶维特征分解，需要计算$A$的顶维特征分解，然后对维数进行加权和排序，再利用加权后的顶维得到嵌入向量。

对于$d$和$l$之间的关系，对于随机网络的最简单情况，即Erdos Renyi模型，由于Wigner半圆定律[11]，对于足够大的网络，我们有l≈2d的期望关系。对于幂律分布的随机网络，在温和的[7]条件下也可以推导出相同的关系

对于真实网络，这种关系与网络的结构有关，但我们验证了我们所实验的所有网络都满足$l\le 2d$

一个重要的观察是，由于$A$的顶$l$特征分解是由任意阶近邻共享的，我们可以通过预计算特征分解，以较低的边际成本在不同阶的近邻之间移动

4.3 The Framework and Complexity Analysis

我们在算法1中展示了我们的算法框架

本文提出的AROPE方法利用特征分解重加权定理，可以得到任意阶近邻的全局最优解。此外，我们的方法还可以处理不同阶近度任意加权的一般情况

我们的方法的一个简化版本是将相等的权重或指数衰减的权重分配给不同的顺序

人们还可能关心我们方法的数值稳定性，特别是当特征值非常相似时

在实践中，我们发现我们的方法是相当稳定的，潜在的原因是建立的数值方法在解决特征分解问题上的成功

由算法可知，通过迭代逼近[16]，行1的时间复杂度为$O(T(N{l}^2+Ml))$，其中

• $N$为节点数
• $M$为边数
• $T$为迭代次数

从第3行到第6行，每个循环的时间复杂度为$O(l+Nd)$

所以总复杂度是$O(T(N{l}^2+Ml)+r(l+Nd))$

这有两个优点

• 首先，复杂度与网络规模(分别为$M$和$N$)呈线性关系，因此我们的方法具有扩展性，可以应用于大规模网络
• 其次，由于$l\ge d$，通常为$T>>r$，因此第一项占主导地位，并且计算多个任意阶邻近需要较低的额外时间，即我们的方法支持跨阶移动，且边际成本较低

4.4 Special Cases of the Proposed Method

接下来，我们展示了我们的方法合并了许多常用的高阶近似作为特殊情况

4.4.1 Common Neighbors and Propagation

在网络分析中，有一种简单而被广泛研究的邻近测度是共同邻居[18]，即反映节点的邻居的邻居的结构

如果我们将顺序设为$q=2$，权值设为$w_1=0,w_2=1$，即:

为了推广公共邻域，提出了一些基于传播的邻域，并考虑了网络的高阶结构

我们的方法在[14]中加入了常用的基于传播的接近度，通过设置$S$为:

其中$w_2、w_3$为传播权值

4.4.2 Katz Proximity

另一种常用的接近测度是Katz接近[15]，它是权重指数衰减的不同阶接近的集合

我们的方法可以保持Katz接近度定义为

其中β是一个常数，控制权重衰减的速度

为了保证接近收敛，β必须小于A[29]的谱半径的倒数

4.4.3 Eigenvector Centrality

我们方法的另一种特殊情况是将维度设为d = 1，即我们只分析第一个维度的作用

我们发现，第一个维度实际上与特征向量中心性[2]高度相关，这是一种广泛应用于测量网络中节点重要性的方法

我们在下面的定理中说明这种情况

利用定理4.2和等式(3)(4),我们有:

由[26]可知，${\lambda }_1\ge d_{ave}>0$，其中$d_{ave}$为网络的平均度

然后，根据定理4.3，我们有$p_1=1$，这就得到了结果

该定理表明，我们的嵌入向量的第一个维度包含所有的特征向量中心性信息，无论使用什么高阶接近

换句话说，我们可以使用我们的嵌入向量来衡量节点的重要性

有趣的是，这与节点的结构身份有关，这是网络嵌入[27]中最近出现的一个主题

虽然我们在设计我们的方法时没有表明这样的目的，但特征向量中心性是我们方法的一个特例

5 EXPERIMENTS

5.1 Experimental Setting

5.2 Preserving the High-Order Proximity

5.3 Network Reconstruction

5.4 Link Prediction

5.5 Node Structural Role Classification

……

6 CONCLUSION

本文研究了网络嵌入中保持任意阶邻近性的问题。通过证明和利用特征分解重加权定理，我们提取了不同阶近度之间的内在关系，并提出了一种可扩展的AROPE方法来导出嵌入向量

理论分析表明

• 我们的方法支持以较低的边际成本跨任意阶的移动
• 给定某个阶，我们的方法可以得到全局最优解
• 我们的方法的总体时间复杂度与网络大小成线性关系

大量的实验结果证明了该方法在网络嵌入中的几种应用中的有效性

未来的一个方向是将该框架推广到有向网络中，并结合节点内容和节点标签等侧信息

读后总结

主体思路还是利用矩阵分解的思想

创新之处在于可以模拟不同阶数的矩阵分解，用于提取不同阶数的特征

A为邻接矩阵，S为其高阶表示，如下（通过函数$F()$）

我们的目标就是分解S，得到$U\ast ，V\ast$

方法是利用SVD求得$\sum ,U,V$

再下面的经过运算，得到$U^{\ast },V^{\ast }$（$U^{\ast }$作为最后的嵌入）

但是使用SVD直接计算U、V计算量非常大，销量低，故转为求S的特征分解$S=[\Lambda ，X]$

再利用求得的特征分解间接求得嵌入（文中有定理及其证明）

厉害，很多知识点都是课本上提到过的，但是一组合起来，没有想到可以这样应用，厉害厉害👍

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正