【论文阅读｜深读】RolNE: Improving the Quality of Network Embedding with Structural Role Proximity

前言

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

知其然 知其所以然！

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

简介

原文链接：https://link.springer.com/chapter/10.1007/978-3-030-62005-9_2

会议：International Conference on Web Information Systems Engineering （ICIS）

年度：2020

Abstract

节点的结构角色是网络结构的基本信息，为理解网络结构提供了更好的视角

大多数网络嵌入学习算法都试图保留节点的邻域信息

然而，这些方法很难识别节点的结构角色贴近度

我们提出了一种新的方法RolNE

• 该方法通过对节点的度向量进行聚类来学习节点的结构角色贴近度
• 并使用聚合函数来学习包含邻域信息和结构角色贴近度的节点嵌入

在多个数据集上的实验表明，我们的算法在下游任务上的性能优于其他最先进的基线。

1 Introduction

网络描述了日常生活中复杂的信息。例如

• 邮件通信构成了人与人之间的社会网络[1]
• 城市之间的交通构成了交通网络

如何高效地执行大规模网络上的分析任务，如节点分类和聚类[2]，一直是该领域的研究基础和重点

目前的主流方法是利用网络表示学习来学习网络中节点的特征

网络嵌入算法将网络信息转化为低维稠密实数向量，作为下游机器学习算法的输入

---

目前，网络嵌入学习算法的工作主要集中在保持网络的微观结构，如节点之间的一阶邻近性、二阶邻近性和高阶邻近性

• DeepWalk[7]在网络嵌入学习任务中引入了word2vec[13]
• 更多的工作[8，9，14，15，28]从不同的范围扩展了邻域的定义，并捕捉邻域信息来改进DeepWalk
• GraphSAGE[16]是近年来提出的一种重要的网络嵌入学习算法。该算法主要学习从节点的局部邻域中提取特征信息，然后学习节点的嵌入

然而，网络中的结构信息不仅有微观结构[3]，还包含介观结构，如结构角色接近

---

结构角色贴近度描述了网络中具有相似角色的节点之间的相似性，例如链的边缘、星的中心以及两个社区之间的桥梁[3]

特别是在电子邮件网络和传输网络中，节点结构角色对于刻画节点具有重要意义
例如，在由电子邮件连接组成的社交网络中，两个部门的秘书在网络中相距较远，确实具有相似的结构角色

与捕捉节点邻域信息的一阶邻近度、二阶邻近度和高阶邻近度不同，结构角色邻近度试图捕捉具有相同结构角色的节点之间的相似性

如图1所示，节点a和b相距很远，但它们具有相似的结构角色

直观上，我们认为角色相似的节点应该具有相似的嵌入

• 但如果两个节点在网络中相距较远而没有共同的邻居，基于邻域信息的嵌入学习不能捕捉到节点的结构角色相似性
• 如果网络中节点的分类更依赖于结构角色接近度，则捕获结构角色接近度的嵌入将执行得更好

---

现有的保持结构角色相似度的网络嵌入学习算法通常需要人工标注拓扑特征[17]，进行复杂的特征工程

然后计算节点间的相似度得分来获得节点间的结构相似度[10]

当这些算法定义与本地网络邻域中不同拓扑对应的节点的结构角色时

例如链上的节点、离散空间中的星形中心，它们需要预先定义这样的离散角色，这需要领域专家和对网络结构的人工检查

我们设计了一种新的算法RolNE，该算法

• 使用一种简单的启发式方法来发现节点的结构角色
• 然后通过一个聚合函数来联合学习节点的结构角色邻近性和节点的邻域信息，以提高节点嵌入的质量

---

我们总结了我们研究的两个主要贡献：

• 首先，我们使用启发式方法来寻找具有相似结构角色的节点，这些节点不需要手动标注网络中的拓扑特征或计算两个节点之间的相似度。
• 其次，我们的方法有效地利用邻居信息和结构角色贴近度来学习节点嵌入。与以往只捕捉节点邻域特征或只保持节点结构等价的方法相比，提高了网络嵌入的质量。学习到的节点嵌入既包含节点结构角色的相似度，又包含节点连接的顺序信息。

2 Related Work

早期的工作主要是通过矩阵分解来获得节点嵌入

• LLE(局部线性嵌入)[4]假设节点及其邻域的嵌入位于流形的局部线性区域内
• LE(拉普拉斯特征映射)[5]通过求解对应于网络的拉普拉斯矩阵的特征值来获得每个节点的嵌入
• GraRep[6]对特定的关系矩阵进行奇异值分解，进行特征降维，得到节点嵌入

---

DeepWalk[7]的提出使基于随机游走的节点嵌入学习算法得到了迅速发展。该算法使用随机游走来捕捉顶点之间的结构关系

• DeepWalk算法首先使用随机游走生成序列，然后使用跳过语法模型学习节点嵌入。
• Node2vec[8]算法提出了一种基于DeepWalk的有偏随机游走算法来生成序列，更有效地探索了邻域结构
• Harp[9]将网络中的相关节点合并成超级节点，然后使用DeepWalk和Node2vec生成节点嵌入
• Line[11]是一种边建模算法，它用节点间的直接连接来描述一级相似关系，用非直连的两个节点的公共邻居来描述节点之间的二级相似关系

---

随着深度学习应用范围的不断扩大，近年来出现了许多利用深度学习的网络嵌入学习方法

• DNGR[18]使用随机冲浪模型直接捕获网络结构信息，并将深度学习方法应用于PPMI矩阵。为了增强模型的稳健性
• DNGR使用堆叠式去噪自动编码器来学习多层嵌入
• SDNE[12]提出了一种具有多层非线性函数的半监督深度模型来捕捉高度非线性的网络结构
• GraphSAGE[16]使用图神经网络来聚集节点邻域信息以生成节点嵌入
• GCN[19]改进了邻域聚集的思想，对每个邻域的信息进行了归一化处理。这种归一化不是简单的平均值，而是引入了每个邻居之间的差异，并降低了高度邻居的权重
• [26]使用匿名遍历和图锚点LDA在图形上构建主题模型，以降低复杂性并有效地生成结构化主题。

---

上述方法主要是为了保存节点的邻域信息，但节点的结构角色也是网络中必不可少的信息

• RolX[17]是一种使用网络结构来识别节点角色的方法，该方法需要枚举节点的局部结构特征，如度数、三角形计数和PageRank[21]分数
• SNS[20]使用ORVA[22]来帮助计算每个节点的Graphlet度向量，然后计算向量之间的欧几里得距离
• Struct2vec将具有相似结构角色的节点编码成多层图，并通过随机游走来捕获结构信息
• GraphWave[23]使用热小波扩散模型来学习节点的结构信息
• GraphCSC[27]使用链接信息和中心度信息来学习网络顶点的低维矢量表示。GraphCSC学习到的嵌入可以保留节点不同的中心信息

上述方法基本上只学习节点的部分结构信息，如邻域信息或结构角色信息

节点的嵌入信息不全面

3 RolNE

该算法的核心思想是从节点的局部邻域和具有相似角色的节点集合中聚集特征信息

该方法应具有两个特点：

• a)节点嵌入距离应与节点结构角色的邻近程度密切相关，即具有相似结构角色的节点应具有相似的嵌入，而具有不同结构角色的节点应远离
• b)节点的嵌入距离应与节点的邻域信息具有较强的相关性，即直连节点或具有公共邻居的节点的嵌入距离应相对较近。

---

我们提出了RolNE，它主要有两个步骤：

1. 通过对节点的度向量进行聚类，找出结构角色相似的节点
2. 利用聚集函数学习包含邻域信息和结构角色信息的节点嵌入

训练过程包括多次迭代

• 在每一次迭代中，节点将聚集来自本地邻域中的节点和具有相同结构角色的节点的信息
• 随着迭代次数的增加，节点将从更深入、更广泛的范围收集更多信息

如图1所示，节点a和b的度数相同，相邻节点的度数之和也大致相同，两个节点具有相似的结构角色

直观地说，我们可以使用这些二维向量（度向量）来确定节点是否具有相似的结构角色

就是依据节点的度向量判断结构角色相似性

---

RolNE的算法图：

---

为了发现相似的结构角色节点，对于图中的每个节点$u$，我们计算该节点的度向量$x(u)$

该度向量包含两个维度

• 第一个维度是节点的度
• 第二个维度是节点的邻域的度之和

在生成所有节点的度向量后，使用Kmeans[24]算法对节点进行聚类，得到具有相似结构角色的节点的簇$R$

简单的说就是：使用度向量作为节点结构角色的分类标准，在使用Kmeans进行聚类，得到R

---

聚合

• $K$表示聚合操作的迭代次数
• $k$表示当前步骤
• $h_u^k$表示在步骤$k$嵌入节点$u$

对于每个节点$u\in V$，我们计算其直连邻居$h_{N(u)}^k$的嵌入和的平均值

然后计算其节点在同一结构角色簇$h_{R(u)}^k$中的嵌入和的平均值

---

我们将这两个嵌入与节点的当前嵌入$h_u^{k-1}$连接起来，并将连接的向量输入到一个完全连通的层

全连通层采用非线性激活函数，输出为$h_u^k$，作为下一步迭代输入

在完成所有迭代后

• 输出的$h_u^k$将被用作每个节点的最终嵌入
• $W^k$是$k$层的权重矩阵

---

我们采用与GraphSAGE相同的损失函数，将基于图的损失函数应用于$Z_u$，所有参数都通过随机梯度下降进行训练

整个训练过程是无人监督的，损失函数如下所示

• $Q$是负样本的个数
• $v$是可以通过固定长度的随机行走到达$u$附近的节点，并且与$u$属于同一簇的节点

4 Experimental Estimate

4.1 Barbell Graph

我们可以看到，RolNE已经正确地学习到具有相似结构角色的节点具有相似的嵌入，并将所有具有相同颜色的节点向量投影到彼此更接近的空间上

在给定的杠铃图上，蓝色和黑色节点比绿色、粉色和紫色节点离红色节点更远

该模型将具有相似结构的节点学习在一起，相同颜色节点之间的距离较近，投影的节点顺序也与原始图形一致

最接近红色的节点依次为橙色、绿色、粉色、紫色、黑色和蓝色

RolNE有效地捕捉了原始图的结构信息和邻域信息

4.2 Mirror Karate Club

4.3 Air Traffic Network

4.4 Enron Email Network

5 Conclusion

我们提出了一种新的方法RolNE

• 它既能捕捉节点的邻域特征
• 又能捕捉节点的结构角色

通过与DeepWalk、Node2vec、GraphSAGE、struc2vec等最新技术的比较，证明了该算法在多个数据集上的有效性

不同的算法捕获了不同的结构特征，而RolNE捕获了更全面的结构信息，生成了丰富的节点嵌入

读后总结

这篇文章总体思路不复杂

主要步骤就是

1. 利用度向量作为标准，使用k-means算法进行聚类，得到簇R
2. 然后再使用聚合函数：多次迭代，利用损失函数（借鉴GraphSAGE）和多层神经网络，使得嵌入表示中相同结构角色及直接相连的节点嵌入更近

大概就是：先聚类，再以一个损失函数为优化目标，利用神经网络训练参数，使得嵌入表示中相同结构角色及直接相连的节点嵌入更近

细节方面，主要是最后损失函数那里，不太了解，但整体思路有点了解了

结语

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

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