携手创造，一起生长！这是我参加「日新方案 8 月更文应战」的第22天，点击检查活动详情

【论文阅读】AROPE：Arbitrary-Order Proximity Preserved Network Embedding

前言

Hello！十分感谢您阅览海轰的文章，倘若文中有错误的当地，欢迎您指出～自我介绍 ଘ(੭ᵕ)੭ 昵称：海轰标签：程序猿｜C++选手｜学生简介：因C语言结识编程，随后转入核算机专业，获得过国家奖学金，有幸在比赛中拿过一些国奖、省奖…已保研。学习经验：厚实根底 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！唯有努力

知其然知其所以然！

本文仅记载自己感兴趣的内容

简介

原文链接：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，…， w_q$ 是权重值

请注意，咱们将 $q$ 阶的挨近程度称为从 $1$ 阶到 $q$ 阶的一切阶的加权组合，而不是单独的 $q$ 阶

假如和收敛，咱们允许 $q = + \infty$ 按照前面的作业，咱们将假设 $\forall 1 \leq i \leq q$ 的 $w_i≥0$ 。当提及不同的高阶附近时，咱们运用下标来区分，例如 $F_i()$

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

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

邻接矩阵 $A$ 能够用其他改换方式替换，如拉普拉斯矩阵[1]，只要替换矩阵是稀少对称的

为了简略起见，咱们在本文的其余部分首要讨论邻接矩阵，但相似的主意能够直接推行

咱们还重用了 $F (\cdot)$ 的标明法，当函数效果于一个数字时，Eq.(1)中的矩阵乘积被数字的乘积代替

为了在低维向量空间中坚持高阶挨近，广泛采用的办法是矩阵分化，它最小化了以下方针函数:

其间

$U∗，V∗∈RNdU^∗，V^∗ \in R^{N d}$ 是内容/上下文嵌入向量
$d$ 是空间的维数
在不失一般性的状况下，咱们运用 $U^*$ 作为内容嵌入向量

根据Ercart-Young定理，经过切断SVD[10]（ truncated SVD）能够得到Eq.(2)的大局最优解

其间 $[U ，， V]$ 为 $S$ 的d顶维SVD成果（ top-d SVD ）
其间 $U, V∈R^{N d}$ ，每一列对应一个左/右奇特向量
$R^{dd}$ 为奇特值降序对角矩阵

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

可是，直接核算 $S$ 和履行 $S V D$ 既耗时又耗时

此外，因为不同的网络和方针运用一般需求不同订单的挨近，怎么在不同订单之间转化也是一个应战

鄙人一节中，咱们将展现一个可弹性的处理方案，以保留根据上述公式的恣意阶附近性，该处理方案支撑跨阶搬运

4 AROPE: THE PROPOSED METHOD

4.1 Problem Transformation

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

标明 $S$ 的顶d特征分化为 $[， X]$ ，其间

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

然后，经过以下定理将奇特值分化与特征分化联系起来

奇特值分化与特征分化得到的成果之间是有相关联系的

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

运用该定理，咱们能够很容易地由式(4)的特征分化得到SVD的成果，由式(5)得到SVD的成果

接下来，咱们只需求专心于求解S的特征分化

运用特征分化得到的成果直接得到SVD的成果

4.2 Eigen-Decomposition Reweighting

为了高效地求解S的特征分化，咱们的要害发现是运用Eq.(1)中界说的恣意阶近邻的方式，不同近邻的特征分化成果是高度相关的

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

定理标明，在不对S进行特征分化的状况下，用 $F ()$ 替换，就能够由 $A$ 的特征分化成果得到 $S$ 的特征分化成果

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

事实上，该定理提醒了不同阶近邻之间的内涵联系。假如咱们将每个特征向量视为网络中节点的“坐标”，将每个特征值视为坐标的“权值”，那么，坚持不同阶的附近性就相当于对维度进行从头加权

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

为了处理这个问题，咱们能够证明恣意 $S$ 的顶d特征分化确保是A的顶l特征分化的重权，其间 $l = L (A, d)$ 是网络和d的函数

具体来说，标明 $_1， ‘ _2，…， ‘_ d$ 为 $S = F (A)$ 的顶退化值，其绝对值由高到低排列

从定理4.2，咱们有

即

p_i

是

_i

在高阶改换

F (\cdot)

之前的阶数

因而，咱们只需求顶部 $p_i, 1≤i≤d$ $A$ 的特征分化就能够得到 $_1，…， ‘_d$ 为 $S$

咱们能够证明以下定理:

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

由上述定理可知，要得到恣意

F (\cdot)

的顶维特征分化，需求核算

A

的顶维特征分化，然后对维数进行加权和排序，再运用加权后的顶维得到嵌入向量。

关于 $d$ 和 $l$ 之间的联系，关于随机网络的最简略状况，即Erdos Renyi模型，因为Wigner半圆规律[11]，关于足够大的网络，咱们有l≈2d的期望联系。关于幂律散布的随机网络，在温和的[7]条件下也能够推导出相同的联系

关于真实网络，这种联系与网络的结构有关，但咱们验证了咱们所试验的一切网络都满意 $l \leq 2 d$

一个重要的观察是，因为 $A$ 的顶 $l$ 特征分化是由恣意阶近邻同享的，咱们能够经过预核算特征分化，以较低的边沿本钱在不同阶的近邻之间移动

4.3 The Framework and Complexity Analysis

咱们在算法1中展现了咱们的算法结构

本文提出的AROPE办法运用特征分化重加权定理，能够得到恣意阶近邻的大局最优解。此外，咱们的办法还能够处理不同阶近度恣意加权的一般状况

咱们的办法的一个简化版本是将持平的权重或指数衰减的权重分配给不同的次序

人们还或许关心咱们办法的数值稳定性，特别是当特征值十分相似时

在实践中，咱们发现咱们的办法是相当稳定的，潜在的原因是建立的数值办法在处理特征分化问题上的成功

由算法可知，经过迭代迫临[16]，行1的时刻复杂度为 $O (T (Nl^2 + Ml))$ ，其间

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

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

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

这有两个长处

首要，复杂度与网络规划(别离为 $M$ 和 $N$ )呈线性联系，因而咱们的办法具有扩展性，能够运用于大规划网络
其次，因为 $l \geq 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]可知，

_1≥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 * ， V *$

办法是运用SVD求得 $∑,U,V\sum, U, V$

再下面的经过运算，得到 $U^*, V^*$ （ $U^*$ 作为最终的嵌入）

可是运用SVD直接核算U、V核算量十分大，销量低，故转为求S的特征分化 $S = [， X]$

再运用求得的特征分化直接求得嵌入（文中有定理及其证明）

凶猛，很多知识点都是课本上提到过的，可是一组合起来，没有想到能够这样运用，凶猛凶猛

结语

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

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

【论文阅读】AROPE：Arbitrary-Order Proximity Preserved Network Embedding

前言

简介