【论文阅读｜深度】Role-based network embedding via structural features reconstruction with degree-regularized

前言

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

知其然 知其所以然！

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

ABSTRACT

基于角色的网络嵌入旨在将网络映射为低维节点表示，同时保持结构相似性。

邻接矩阵既包含了网络的局部信息，也包含了网络的全局信息，但不能直接表示节点的作用。

因此，从邻接矩阵中提取高阶结构特征对于基于角色的网络嵌入(结构等效)至关重要。

---

一般来说，在真实网络中，采用相同的方法提取的特征对噪声很敏感，但不能真正代表节点的作用。

因此，我们提出了一个深度学习框架RESD

1. 首先，我们提出提取网络中每个节点的高阶结构特征

2. 然后，我们利用变分自编码(VAE)对特征的非线性关系建模，减少噪声，提高嵌入的鲁棒性

3. 此外，在嵌入空间中，我们应用度正则化约束来指导表示学习，以保留节点的关键结构信息(如度)，这些信息可能由于VAE框架的原则而丢失

4. 最后，我们构造一个统一的目标函数，通过保留结构特征和节点度来学习节点嵌入的角色发现

1. Introduction

基于社区的网络嵌入（保留节点邻近性）

• DeepWalk [14] and node2vec [8] ，通过随机游走
• GCN[15]和GraphSAGE[16]，通过网络传播特征

然而，角色是复杂网络中的另一个重要点，它与社区的概念有根本的不同。

---

角色的定义被定义为等价节点的类[17]，用来表示节点之间的结构相似性。

换句话说，角色是满足以下条件的节点分区:节点在结构上与同一分区内的节点比与分区外的节点更相似

直观地说，角色代表了邻居中节点的连接模式。

---

如图1（上图）所示，两个红色节点共享相同的角色，因为它们可以被归类为两个子图的桥梁，而黄色节点具有相同的角色，因为它们都是中心，即使它们彼此相距很远或不相连

因此，基于角色的网络嵌入被设计成将网络投影到嵌入空间中，在该空间中，相同角色的节点更紧密地连接在一起。

综上所述，虽然这两个问题（基于社区或角色）都致力于网络中节点的聚类，但它们有本质的区别和各自的优先顺序[18]。

基于社区的网络嵌入方法通常不能解决基于角色的任务，因为它们不能捕获和建模节点的结构特征

---

最近，已经提出了一些方法来获取结构相似性和获得基于角色的网络嵌入。

其中最具代表性的一种方法是基于随机游走。

角色发现的第一个挑战是：同一角色中的节点可能不能直接连接或彼此远离。为了解决这个问题，一些方法对普通的随机游动进行了改进。

例如，role2vec[12]采用基于特征的随机游动代替基于id的随机游动来生成序列作为SkipGram[19]的输入。
然而，它仍然无法处理远距离节点的结构身份提取，不能应用于大规模网络。

一些方法尝试利用邻接矩阵而不是随机游走来缓解相同角色的节点之间的非连通性问题。

然而，网络的邻接矩阵可以包含一阶和高阶关系，不能直接表示结构上的相似性。

因此邻接矩阵不适用于简单地用于生成基于角色的嵌入。

然后，一些方法转向基于邻接矩阵的结构特征提取来进行角色发现。例如，refex[20]是递归聚合邻域特征和基于egonet的特征的有效方法。它具有良好的性能，并获得了一个相对紧凑的表示。

但随着迭代次数的增加，每个节点都会遇到较高阶的邻域，这可能会造成过拟合，导致特征不能真实地反映结构信息。

RolX[21]和GLRD[22]利用REFEX特征并分解特征矩阵以获得紧凑的节点表示。

然而，基于矩阵分解的方法存在计算复杂度高的问题。更重要的是，它们使用的特征依赖于邻域信息，这使得它们对网络中的噪声非常敏感，并且它们产生的嵌入丢失了节点的一些统计特征，如节点度。

受深度学习的启发，DRNE[23]利用按节点度规则化的层归一化LSTM来递归聚合邻居的表示以获取规则等价性。该机制可以有效地捕捉远距离节点之间的结构相似性，但仍然忽略了噪声。

最重要的是，为了学习基于角色的节点嵌入，我们必须在保持节点统计特征的同时解决非连通性和噪声的挑战。

---

为此，我们提出了一种基于度正则约束的结构特征重构的深度学习框架，称为基于角色的网络嵌入。

该框架由特征提取、嵌入生成和拓扑特征保持三部分组成。

• 首先提取每个节点的高阶结构特征。在本文中，我们选择REFEX作为样本特征提取方法，以提高其效率和效果。

• 然后，利用特征矩阵上的变分自动编码器(VAE)来降低噪声，获得更紧凑的表示，并能捕捉到输入与节点嵌入之间的非线性关系，具有很好的鲁棒性，避免了过拟合。

  • 然而，VAE的编码过程可能会导致节点的一些关键结构特征的丢失。

  • 因此，在VAE的基础上加入正则化来保持节点的度数，起到辅助指导优化方向的作用。

---

我们的主要贡献:

• 提出了一种通过结构特征重构生成基于角色的网络嵌入的新框架。此过程可以获得更紧凑的结点表示，并提高要素的性能
• 我们利用特征上的变分自动编码器来捕捉输入和节点嵌入之间的非线性关系，同时保持结构的相似性。它还可以降低原始网络中的噪声，增加表示的稳健性。
• 编码过程失去了结构特征(例如度)，我们确认节点度对于角色的分配是重要的。因此，我们在VAE上添加了度正则化约束，以保持结构一致性并提高性能。
• 我们通过我们的模型RESD在真实网络上进行了几个广泛的实验，并将结果与其他最先进的方法进行了比较。实验结果证明了该模型的优越性，并证明了该模型能够很好地适应网络规模和维度的变化。

2. Related work

传统的研究一般通过图形表示来定义角色。其中最流行的方法是块模型，它构建了一个框架，节点代表角色，边代表角色之间的交互

• Concor[25]是第一个以递归方式计算邻接矩阵相关性的人。

• 随机区块模型(SBM)[26]是一种经典的方法，它将随机等价性引入到角色标识中，因此，如果链接到所有其他节点的概率相同，则节点处于相同的角色

• 然后对SBM进行了改进，使其能够更好地发现角色。例如，混合成员随机块模型(MMSB)[27]利用了块模型的思想，并假设一个节点可以属于多个角色。

---

其他传统的方法利用特征工程的机制，将焦点从图形表示转移到节点表示。

他们尝试了不同的度量来评估节点的一些特定的结构一致性，如度中心性、特征向量中心性[28]、PageRank中心性[29]和结构空洞值[30]，这些度量在一些特殊任务中可能会显示出良好的效果。

REFEX[20]是一种获取结构特征的有效方法。它递归地聚合邻域特征和基于eGonet的特征，以获得全局结构信息。但它们仍然很难被应用于发现节点角色和复杂的任务，因为保存的结构信息太有限

---

最近，为了捕捉全面的角色信息并将其用于复杂的机器学习任务，研究人员试图利用网络嵌入的优势。根据嵌入机制的不同，这些基于角色的网络嵌入方法大多可以分为三类：

• 基于语言模型的方法
• 矩阵分解方法
• 深度学习方法

1）基于随机行走的语言模型Skip-Gram[19]

经典的基于随机游走的网络嵌入方法，如DeepWalk[14]和node2vec[8]，都是绑定到社区的，因为它们基于id的随机游走，但它们不适用于角色发现。

一些方法试图改进随机游走，以使其适用于角色检测。

• 这类角色发现最有效的模型是struc2vec[31]。该算法使用动态时间规整(DTW)距离计算所有节点对之间的多个基于特征的相似度，然后构造一个完整图的层次结构，其边权重由基于特征的相似度转换并用于计算随机游动的概率。
• 最近，role2vec[12]在基于Motif的特征上应用了随机漫游，
• node2bit[32]对用户缝合任务应用了相同的想法，还利用了临时漫游CTDNE[33]。
• RiWalk[34]设计了一种新的随机游走方法来逼近子图上的图核。

2）矩阵分解机制

现有的方法大多构造特征矩阵或相似度矩阵，然后通过矩阵分解计算紧凑的节点表示

• RolX[21]是第一个利用这种机制来生成基于角色的节点嵌入的。它利用REFEX[20]提取的结构特征，利用矩阵分解得到低维节点表示。实践证明，该模型在角色发现方面具有很大的潜力。
• GLRD[22]利用了这些特征
• Regal[35]中的xNetMF也构造了一个特征矩阵并对其进行分解
• Hone[36]则通过分解一组基于Motif的矩阵来生成高阶网络嵌入。它们可以有效地提取节点之间的结构相似度。
• 一些方法利用经典方法来计算成对相似性。Reaction[37]应用RoleSim[38]矩阵来获取每对节点之间的相似度，从而获得节点表示
• SEGK[39]对图核计算的相似度矩阵进行了分解。
• GraphWave[40]还通过应用图扩散核并将其视为图上的概率分布来生成嵌入。
• 另一项工作[41]设计了四种基于非负矩阵分解(NMF)的多层网络嵌入算法，同时保持了结构特性。但这种基于矩阵分解的方法由于计算和空间复杂度较高，不适用于除RolX以外的大规模网络。

3）基于神经网络的深度学习框架，以捕捉网络拓扑结构与节点表示之间的高度非线性关系[43]。

• DRNE[23]应用层归一化的LSTM[44]来学习正则等价。该算法对每个节点的邻域进行采样并按节点度进行排序，然后将邻域的表示作为多层感知器正则化的LSTM的输入，重构节点度
• Demo-Net[45]构造了一个度特定的GCN，它根据节点度使用不同的参数，但它是针对半监督条件的
• DMER[46]利用邻接上的GCN编码器和REFEX[20]功能上的自动编码器
• GAS[47]还利用简单结构上的GCN来生成节点嵌入

然而，这些深度学习方法仍然对噪声敏感。

3. Method

3.1. Notions

$G=\{V,E\}$

$N(u)=\{u\in V|(u,v)\in E\}$ : 节点$u$的邻域

$d(u)$：节点$u$的度

the one-hop egonet of node $v_i$: $G_i=\{V(g_i),E(g_i)\}$

• $V(g_i)=\{v_i\}\cup \{v_j\in V|(v_i,v_j)\in E\}$，与顶点$v_i$相连的节点集合
• $E(g_i)=\{(u,v)\in E|u,v\in V(g_i)\}$：节点$v_i$与它的邻域集合之间的顶点的边集合（也就是$V(g_i)$构成原图的子图）

$\mathbf{X}={\mathbb{R}}^{n\times m}$：表示提取后的特征空间，m为特征的维度

低维向量空间（目标）${\mathbb{R}}^k$，其中$k<<|V|$

3.2. Model

RESD框架图

RESD包括三个部分

1. 角色特征的提取过程
2. 用于将特征组合成节点表示的变分自动编码器
3. 用于增强学习嵌入的表示能力的基于节点度的正则化。

3.2.1. Feature extraction

如果两个节点$u$和$v$具有相似的结构同一性，则它们倾向于共享相同的角色。

尽管图的邻接矩阵包含了所有的拓扑信息，但由于邻接矩阵通常是稀疏的，而节点之间可能相距很远，甚至是不连通的，很难比较两个节点的结构一致性。

因此，结构相似性不能直接从邻接矩阵中学习，需要从邻接关系中提取紧凑的高阶结构特征。

---

早期的工作表明，许多高阶特征提取方法在角色发现中是有效的，如基于Motif计数的特征[12]、多跳邻居度数[31]和REFEX[20]。所有这些方法都可以作为框架RESD中的特征提取部分

在这里，我们采用了refex[20]

因为它的高效性和有效性，它通过以递归的方式聚合简单的局部和egonet特征来生成高阶结构特征

该方法为每个节点提取一个局部特征和五个基于egonet的特征。

对于节点$v_i$，局部特征是节点度$d(v_i)$，基于$G_i$的egonet特征定义如下：

3.2.2. Variational auto-encoder

由于现实网络中存在大量的噪声，所提取的高阶结构特征往往对噪声非常敏感，不能满足角色发现的需要。

因此，我们利用变分自动编码器(VAE)[24]将结构特征编码为结点表示

VAE参考资料：
https://zhuanlan.zhihu.com/p/418352070
https://zhuanlan.zhihu.com/p/260627899#:~:text=%E5%8F%AF%E5%8F%98%E8%87%AA%E5%8A%A8%E7%BC%96%E7%A0%81%E5%99%A8%E8%83%BD,%E7%90%86%E6%83%B3%E8%BE%93%E5%87%BA%E7%9A%84%E9%97%B4%E9%9A%99%E3%80%82

VAE可以降低噪声，捕捉输入特征之间的非线性关系。与普通自动编码器(AE)相比，VAE有效地避免了过拟合问题，提高了输出嵌入的稳健性

我们使用多层感知器模型而不是图形神经网络(GNN)作为编码器

因为GNN总是平滑嵌入的事实会否定提取的特征。

---

在我们提出的RESD模型的VAE部分，给定提取的节点$v_j$的特征向量$X_j$，编码器定义如下：

• $W^l$和$b^l$是第l层的权重和偏置bias
• L：编码器中的隐藏层数
• tanh(·)是双曲正切激活函数
• $h_j^0=X_j$：编码器的输入

我们假设节点$v_j$的表示$Z_j$服从高斯分布${\mathbb{P}}_j(Z_j)$，其中$Z_j$的所有元素是独立的，并且${\mathbb{P}}_j(Z_j)=N_j({\mu }_j,diag({\sigma }_j^2))$

可以通过下面式子学习分布${\mathbb{P}}_j(Z_j)$中的参数${\mu }_j$和${\sigma }_j$

• 其中$W^{\mu }、b^{\mu }、W^{\sigma }$和$b^{\sigma }$分别是编码器最后一层的权重和偏置，之前的参数是共享的

我们对$\sigma$取对数，以保证标准方差始终为正。

然后，我们可以通过重新参数化技巧[24]获得节点表示Zj，这允许我们计算${\mu }_j$和${\sigma }_j$的梯度

其中，$\odot$是元素级乘积，$\epsilon$服从标准高斯分布

---

对于RESD的解码器部分，我们同样使用多层感知器模型:

• ${\hat{W}}^l$和${\hat{b}}^l$为解码器中第$l$隐含层的权重和偏差
• ${\hat{h}}_j^0=Z_j$为解码器的输入
• $\hat{X}$为重构的特征矩阵，其中${\hat{X}}_j={\hat{h}}_j^L$

最后，我们将VAE损失定义为:

3.2.3. Regularization

虽然上述VAE模型具有生成表达表示的能力，但在估计输入特征的分布时，它可能会丢失一些关键的结构信息

因此，在嵌入信息中添加约束来保存关键的结构信息是至关重要的。

---

从传统的基于图的角色发现方法的结构等价、规则等价等准则可以推断，扮演相同角色的节点具有相似的度。

因此，度是一个节点最重要的结构特征，并通过许多方法如Demo-Net[45]和DRNE[23]进行了实验验证

类似于DRNE[23]，RESD定义基于等级的正则化器如下:

• 其中MLP(·)是一个修正线性单元激活ReLU(·)的多层感知器模型。

我们通过联合最小化特征重构和度正则化约束的损失来训练我们的深度学习框架RESD，如下所示:

• 其中β为基于度的正则化器的权重

---

RESD算法伪代码如下：

个人理解：

• 首先依据图的邻接矩阵 使用refex提取特征矩阵
• 然后依次遍历图中的节点
• 遍历到每一个节点时：
  • 先使用等式（3）获得由于编码器得到的向量 $Z_j$
  • 再使用等式（5）计算由于VAE得到的损失
  • 再使用等式（7）计算加上正则约束后的总损失
  • 利用这个总的损失 反向传播 更新参数
• 应用训练好的参数，得到节点表示矩阵Z（就是最后我们需要的向量空间）

$Z$就是由编码器得到的$Z_j$组成的，也就是编码器得到的结果就是我们需要的在低维空间的嵌入！

3.3. Computational complexity analysis

给定网络G，设

• n表示节点数，
• e表示边数，
• r表示ReFeX的特征聚合数，
• m表示提取的特征矩阵X的维数
• k表示节点嵌入Z的维数

ReFeX的整个过程取$O(rm(e+nm))$

因为每次特征聚合的计算量都大于上一次聚合。

每个节点用VAE表示，计算复杂度为$O(m^{2}k)$，正则化耗时$O(k^2)$。

因此$k<m$在整个网络上的嵌入生成计算为$O(n{m}^{2}k)$。

由于r总是很小，且$r<k<m\ll n$，所以RESD的整个计算$O(rem+n{m}^{2}k)$。

因此，我们的RESD框架对于花费$O(nm2k)$时间的大规模网络具有很大的潜力。

4. Experiments

4.1. Baselines

• node2vec [8]
• role2vec [12]
• struc2vec [31]
• RolX [21]
• DRNE [23]
• struc2gauss [48]

4.2. Datasets

数据集（无向无权图）

4.3. Experiment settings

在特征提取部分，我们使用ReFeX，设置

• 特征聚合次数为3次
• 箱数设置为5次

对于VAE的编码器和解码器，我们将

• 隐藏层的数量都设置为2

对于基于程度的正则化器，我们使用了一个带有ReLU激活函数的2层MLP模型

我们采用学习率为0.001的Adam SGD优化器[52]，设置权重为0.001的L2正则化以避免过拟合。

对于大多数50个epoch，批大小设置为32。

在我们后来的实验中，如果没有特别说明，嵌入的维度设置为128，β设置为0.6。

4.4. Role classification

我们随机输入不同比例的数据来训练一个嵌入的线性逻辑回归分类器，而剩下的用于测试。

我们运行所有基线方法和RESD 20次，并计算它们在每个网络上的平均F1得分。

为了验证度保持约束的有效性，我们还运行了一个不含基于度的正则化器的RESD变体，称为RES

结果如下图：

4.5. Bot detection

在本节中，我们的目标是探索我们的模型是否可以检测到一些网络中的罕见角色。

我们选择了两个机器人只占总用户一小部分的维基百科谈话网络。

在这些网络中检测机器人是非常复杂的。

1. 首先生成每个用户的表示
2. 对于每个机器人，我们计算它与其他用户之间的欧氏距离
3. 最后，我们选择与每个机器人最接近的K个用户，计算机器人的平均精度

大概意思是这样的：
首先对每一个user（包括bot机器人）
然后利用低维表示的bot 找到最接近它的k个user
看这k个user中 bot的比例是多少
若这个比例非常高 则说明对罕见角色嵌入的程度很高（模型越好）

结果如下表

• 在机器人检测任务上K个选定用户的精确度
• OT表示该方法不能在48小时内得到结果。

4.6. Parameter sensitivity and computational complexity

正则化的权重β和嵌入维数的参数敏感性

基线方法和RESD的运行时间

• 其中全值表示48小时内无法得到结果
• 所有这些方法的输出嵌入维数都设置为128

4.7. Visualization

采用的数据集： Brazil

利用t-SNE将嵌入的维数降至2以实现可视化

• 每个节点表示为一个点
• 颜色表示其角色

理想情况下，相同颜色的点之间应该很近，而不同颜色的点之间应该很远。

可视化结果：

5. Conclusion

不足：

• 模型中的结构特征过于简单
• 编码器忽略了网络结构
• 该模型只能应用在无权无向图上

在未来的工作中，我们计划利用图神经网络(GNN)来编码特征，同时提取节点之间的复杂关系。

我们也希望设计一个新颖的深度学习框架，产生比手工作品更富有表现力的结构特征。

据我们所知，大多数基于角色的网络嵌入方法只关注静态网络，而忽略了节点或边缘上的附加属性。为了更好地理解角色的影响，我们将进一步探索动态网络，引入属性来学习更有效的表示，这可能是未来有吸引力的工作。

读后总结

随着阅读论文的增加 读论文速度也快了起来

也没有之前那么生疏

对文章中提到的一些东西也还是有一点点懂的

---

这篇文章主要思路是：

• 通过邻接矩阵 使用Refex提取特征
• 再通过VAE 减少噪声对其的影响 提高模型的鲁棒性
• 又因为使用VAE会损失一些结构信息
• 再引入正则约束：度
• 二者结合 便于更好地提取节点的高阶特征

结语

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

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