继续创作，加快成长！这是我参与「日新方案 6 月更文应战」的第31天，点击查看活动详情

前语

Hello！

非常感谢您阅读海轰的文章，倘若文中有过错的地方，欢迎您指出～

毛遂自荐 ଘ(੭ᵕ)੭

昵称：海轰

标签：程序猿｜C++选手｜学生

简介：因C言语结识编程，随后转入核算机专业，获得过国家奖学金，有幸在比赛中拿过一些国奖、省奖…已保研。

学习经历：厚实根底 + 多做笔记 + 多敲代码 + 多考虑 + 学好英语！

唯有尽力

知其然 知其所以然！

本文只记载感兴趣的部分

3.1 Notations and Definitions

$G=(V,E)$

$N(v)=\{u|(v,u)\in E\}$

X=R∣V∣k\boldsymbol X= \mathbb{R}^{|V| \times k}X=R∣V∣k：极点的嵌入空间向量表明

dv=∣N(v)∣d_v=|N(v)|dv​=∣N(v)∣：极点$v$的度

I(x)={1x≥00elseI(x)=\begin{cases} 1\quad x \geq 0\\ 0 \quad else \end{cases}I(x)={1x≥00else​

---

Definition 3.1 (Structural Equivalence)

• $s(u)=s(v)$ : 节点$u$和$v$是结构等价
• $N(u)=N(v)\Rightarrow s(u)=s(v)$
• 也便是节点的邻域相同，则为结构等价

Definition 3.2 (Regular Equivalence)

• $r(u)=r(v)$：节点$u$和$v$是正则等价
• $\{r(i)|i\in N(u)\}=\{r(j)|j\in N(u)\}$（没懂）

3.2 Recursive Embedding

依据界说3.2，咱们以递归的办法学习节点嵌入，方针节点的嵌入能够用其街坊节点嵌入的聚合来近似

根据此概念，咱们规划了如下损失函数:

其间Agg是聚合函数

---

在一个递归进程中，学习到的嵌入节点能够保存其街坊的局部结构

经过迭代更新学习到的表明，学习到的节点嵌入能够在全局意义上融合其结构信息，这与规矩等价的界说是共同的

---

因为实在网络的底层结构往往是高度非线性的[22]，咱们规划了一个深度模型，归一化长短时回忆层(ln-LSTM)[2]作为聚合函数

众所周知，LSTM对序列建模是有用的。然而，节点的街坊在网络中没有自然排序

这儿咱们运用节点的度作为将街坊排序成有序序列的标准

• 主要是因为度是街坊排序的最有用的衡量
• 而度在许多图论衡量中往往起着重要的效果，特别是那些与结构人物相关的衡量，如PageRank[27]和Katz[25]

---

设

• 有序邻域的嵌入为{X1，X2，…，Xt，…，XT}\{X_1，X_2，…，X_t，…，X_T\}{X1​，X2​，…，Xt​，…，XT​}
• 在每个时间步长$t$时，隐态hth_tht​是$t$时刻的输入嵌入XtX_tXt​与其之前的隐态ht−1h_{t−1}ht−1​的函数，即ht=LSTMCell(ht−1,Xt)h_t = LSTMCell(h_{t−1},X_t)ht​=LSTMCell(ht−1​,Xt​)

当LSTM Cell对嵌入序列进行从1到T的递归处理时，隐含表明hth_tht​的信息会越来越丰富

hTh_ThT​能够看作是街坊的聚集表明。

为了学习长序列中的长距离相关性，LSTM运用了门控机制

• 忘记门决议咱们要从回忆中丢弃什么信息
• 输入门和旧回忆一起决议咱们要在回忆中存储什么新信息
• 输出门依据回忆决议咱们要输出什么

具体来说，LSTM跃迁方程LSTMCell为:

此外，为了防止以长序列为输入的梯度[14]爆炸或消失的问题，咱们还引入了层归一化

层归一化的LSTM使其不变地从头缩放一切的求和输入。它产生了更安稳的动力学

特别是，它在方程6后运用额定的归一化使细胞状态CtC_tCt​居中并从头缩放，如下所示:

3.3 Regularization

（1）式是按照界说3.2的递归嵌入进程，没有任何其他约束。

它具有很强的表达能力，只要满足给定的递归进程，就能够推导出多个解。

该模型退化为一切嵌入值为0的平凡解是有危险的

---

为了防止呈现平凡解，咱们将节点的度作为弱引导信息，并设置一个约束条件

• 即学习的节点嵌入必须能够近似节点的度。

据此，咱们规划了以下正则化器:

其间

• dvd_vdv​是节点$v$的度
• $MLP$是单层多层感知器，具有整流线性单元(ReLU)[11]激活，其界说为$ReLU(X)=max(0，x)$

总而言之，咱们经过组合公式1的重构损失和公式9的正则化来最小化方针函数：

其间

• 是正则化的权重

注意

• 这儿不运用度信息作为网络嵌入的监督信息。
• 相反，它最终起到辅助效果，使解决方案远离微不足道的解决方案。
• 因而，这儿的是一个适当小的值。

---

Neighborhood Sampling

在现实网络中，节点的度往往服从重尾散布[9]，即少数节点的度很高，而大多数节点的度很小

在Ln-LSTM算法中，为了提高算法的功率，在输入LN-LSTM之前，咱们对节点的邻域进行了大次数的下采样。

具体地说，咱们设置了街坊数S的上界，如果街坊数超过上界S，咱们将它们下采样为S个不同的节点。

在幂律网络中，度大的节点比度小的普通节点携带更多独特的结构信息。

为此，咱们规划了一种有偏采样策略:

• 经过设置节点$v$的采样概率$P(v)$与其度数dvd_vdv​成正比
• P(v)∝dvP(v)∝d_vP(v)∝dv​来坚持节点的大阶数

3.4 Optimization

为了优化前述模型，方针是最小化作为神经网络参数集和嵌入X的函数的总损失L（等式10）

Adam[16]被用来优化这些参数（运用Adam算法进行求解）

• 运用时间反向传播(BackPropagation Through Time, BPTT)算法[37]估量导数
• 在练习开始时，Adam的学习速率初始设定为0.0025

论文：Adam: A Method for Stochastic Optimization

3.5 Theoretical Analysis

咱们进一步从理论上证明$DRNE$的成果嵌入能够很好地反映几个典型的和常见的中心性衡量，这些中心性衡量与规矩等价密切相关

在不损失一般性的情况下，咱们忽略方程9中用于防止平凡解的正则项。

---

定理3.3. 度中心性、特征向量中心性[5]、PageRank中心性[27]分别是咱们模型的三个最优解。

运用引理3.4进行证明

引理3.4 关于任何可核算函数，都存在一个有限递归神经网络[24]来核算它。

证明进程略（看不懂）

---

定理3.5. 如果节点$v$的中心性$C(v)$满足C(v)=∑u∈N(u)F(u)C(u)C(v) =\sum_{u\in N(u)}F(u)C(u)C(v)=∑u∈N(u)​F(u)C(u) and $F(u)=f(\{F(u)，u\in N(v)\})$，其间$F$是任意可核算函数，那么$C(v)$便是咱们模型的最优解之一

证明进程略（看不懂）

---

经过(F(v)，f({xi}))(F(v)， f(\{x_i\}))(F(v)，f({xi​}))在表1中对中心性的界说，咱们能够很容易地得到度中心性、特征向量中心性、PageRank中心性满足定理3.5的条件，然后完成了定理3.3的证明。

依据定理3.3，关于任何图，咱们提出的办法都存在这样一个参数设置，即学习到的嵌入能够是三个中心性之一

这证明了咱们的办法在捕获与规矩等价相关的网络结构信息的不同方面的表达能力。

3.6 Analysis and Discussions

在本节中，咱们将介绍样本外扩展和复杂性分析。

3.6.1 Out-of-sample Extension

关于一个新抵达的节点$v$，如果已知它与现有节点的衔接，咱们能够直接将其街坊的嵌入输入到聚合函数中，用式1得到作为该节点嵌入的聚合表明。

该进程的复杂度为O(dvk)O(d_vk)O(dv​k)

• $k$为嵌入的长度，
• dvd_vdv​为节点$v$的度。

3.6.2 Complexity Analysis

在练习进程中，关于每次迭代的单个节点$v$，核算梯度和更新参数的时间复杂度为O(dvk2)O(d_v k^2)O(dv​k2)

dvd_vdv​为节点$v$的度，$k$为嵌入的长度

因为采样进程的原因，dvd_vdv​度不会超过限定的数值S。因而全体练习复杂度为O(∣V∣Sk2I)O(|V|Sk^2I)O(∣V∣Sk2I)

$I$为迭代次数

其它参数的设置

• 嵌入的长度$k$一般设置为一个较小的数字，如32,64,128。
• S设为300。迭代次数$I$一般很小，但与节点数$|V|$无关

因而，练习进程的复杂度与节点数$|V|$成线性关系。

4 EXPERIMENTS

4.1 Baselines and Parameter Settings

基线办法

• DeepWalk
• LINE
• node2vec
• struc2vec
• Centralities：采用近中心性[26]、中心中心性[4]、特征向量中心性[6]和K-core[17]这四种常用的中心性来衡量节点的重要性。此外，咱们将之前的四个中心性衔接到一个向量中作为另一个基线(Combined)

参数设置

关于咱们的模型，咱们设置

• 嵌入长度$k$为16
• 正则化器的权值为1
• 有限邻域数$S$为300

咱们将在4.5节中阐明咱们的模型对这些参数不是很灵敏

4.2 Network Visualization

杠铃网络可视化

空手道网络可视化

4.3 Regular Equivalence Prediction

在本节中，咱们评价学习到的嵌入是否在两个实在世界的数据集上坚持规矩等价

数据集

• Jazz[10]
• BlogCatalog [38]

在这儿咱们设置了两个使命，包括规矩等价性猜测和中心性评分猜测

---

关于第一个使命，咱们运用常用的根据规矩等价的相似性衡量办法VS[18]作为根底真值。

两个节点的两两相似度由其嵌入的内积来衡量。

咱们依据节点对的相似性对其进行排序，并将成果排序与VS. Kendall排序进行比较

运用[1]秩相关系数来衡量这两个秩的相关性。其界说如下:

成果如图5所示:

---

关于第二个使命，咱们将4.1节中提到的四个中心性作为基准来核算

然后随机隐藏20%的节点，运用剩余的节点练习线性回归模型，根据节点嵌入猜测中心性得分

练习后，咱们运用回归模型来猜测被屏蔽节点的中心性

采用均方误差(Mean Square Error, MSE)评价其功能。MSE界说如下:

其间$Y$为观测值，Y\hat YY为猜测值。

因为不同中心性的标准存在明显差异，咱们将MSE值除以相应的一切节点中心性的平均值来从头缩放。

成果如表2、表3所示。

4.4 Structural Role Classification

根据结构人物的分类使命中，节点的标签与其结构信息的相关比与其相邻节点的标签的相关更大。

在本节中，咱们评价学习嵌入在猜测给定网络中节点的结构人物的能力。

数据集：欧洲航空交通网络和美国航空交通网络[29]

节点表明机场，边表明直航的存在。 降落加起飞的总人数或经过机场的总人数能够用来衡量他们的活动，反映他们在航班网络中的结构人物。 经过将每个机场的活动散布均匀地划分为四个或许的标签之一。

在得到机场的嵌入后，咱们练习一个逻辑回归来猜测根据嵌入的标签

咱们随机抽取10% ~ 90%的节点作为练习样本，运用剩余的节点来测验功能。

平均精度用于评价功能。

成果如图6所示，其间实线表明网络嵌入办法，虚线表明中心性办法。

4.5 Parameter Sensitivity

咱们评价了嵌入维数$k$、正则化器权重和邻域巨细上界$S$的影响

4.6 Scalability

为了证明可扩展性，咱们测验每个epoch的练习时间

成果如图8所示

5 CONCLUSION

在本文中，咱们提出了一个新的深度模型来学习网络中具有规矩等价性的节点表明。

假定节点的规矩等价信息已被其相邻节点的表明编码，咱们提出一层归一化LSTM模型递归学习节点嵌入。

关于给定的节点，远距离节点的结构重要性信息能够递归地传播到相邻节点，然后嵌入到其嵌入中。

因而，学习到的节点嵌入能够在全局意义上反映节点的结构信息，这与规矩的等价性和中心性衡量是共同的。

实证成果表明，咱们的办法能够明显和继续地优于最先进的算法。

读后总结

全体思路大约了解了

但是因为对LSTM的不了解

细节上的东西仍是没有了解到

若以后需要仔细探究，再仔细研讨研讨！

结语

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

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