【论文阅读｜深读】RDAA：Role Discovery-Guided Network Embedding Based on Autoencoder and Attention Mechanism

目录

• ​​前言​​
• ​​简介​​
• ​​Abstract​​
• ​​I. INTRODUCTION​​
• ​​II. RELATED WORK​​

• ​​A. Role Discovery​​
• ​​B. NE for Structural Similarity​​
• ​​C. Autoencoder for Complex Networks​​

• ​​III. METHODOLOGY​​

• ​​A. Notations and Definitions​​
• ​​B. Overall Framework​​
• ​​C. Role Feature Extraction​​
• ​​D. Encoder–Decoder​​
• ​​E. Role Attention Mechanism​​
• ​​F. Joint Training​​
• ​​G. Computational Complexity Analysis​​

• ​​IV. PERFORMANCE EVALUATION​​

• ​​A. Datasets and Metrics​​
• ​​B. Experimental Settings​​
• ​​C. Visualization​​
• ​​D. Experiments on Role Classification​​
• ​​E. Parameters Sensitivity​​
• ​​F. Efficient versus Effective​​
• ​​G. Case Study: Role Discovery​​

• ​​V. CONCLUSION​​
• ​​读后总结​​

• ​​2022/07/11 第一次阅读​​

• ​​结语​​

前言

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

知其然 知其所以然！

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

简介

期刊：IEEE Transactions on Systems, Man, and Cybernetics: Systems （CCF-B类）

代码：https://github.com/cspjiao/RDAA

年度：2021/06/29

Abstract

近年来，网络嵌入(network embedding, NE)是复杂网络研究中的一个热点，致力于各种各样的任务

几乎所有的网络模型和方法都是基于网络的局部相似性、高阶相似性或全局相似性，很少有研究聚焦于角色发现或结构相似性，这对传播动力学和网络理论具有重要意义

同时，现有的角色发现NE模型存在两方面的局限性:

1. 不能对每个节点与其相邻节点之间的依赖关系进行建模
2. 不能捕获有助于角色发现的有效节点特征

依据role发现的NE方法的一些缺陷

这使得这些方法在应用于角色发现任务时失效

---

为了解决NE角色发现或结构相似性问题，我们提出了一种统一的深度学习框架RDAA

• 该框架可以有效地表示节点的特征
• 用深度自编码器对角色发现引导的NE有益
• 同时使用Attention机制对局部链接进行建模

此外，我们精心设计了一种绑定技术，将两者结合起来，统一优化框架

我们进行了不同的实验，包括可视化、角色分类、角色发现，以及与流行的NE方法在邻近性和结构相似性方面的运行时间

RDAA在所有数据集上都有更好的性能，并实现了良好的权衡

I. INTRODUCTION

社交媒体的爆发式增长推动了社交网络分析的快速发展

由于现实世界中大规模网络的稀疏性，如何有效地表示节点信息对于许多网络任务[1]来说是极其重要的

网络嵌入(Network embedding, NE)是近年来最流行的用于表示和分析大规模网络的工具，其目的是将网络节点嵌入到低维空间中，同时保留网络拓扑[2]的重要特征

然后，学习到的保留结构信息的节点表示可以应用于网络分析的下游任务，如节点分类[3]、团体检测[4]、推荐系统[5]、链路预测[6]

---

针对NE提出了多种方法和模型，一般可分为基于随机漫步、矩阵分解、统计网络模型和机器学习的方法

受word2vec[7]的启发

• DeepWalk[8]首先致力于学习基于经典图上随机漫步的节点嵌入，并通过分层Softmax进行优化，然后针对不同类型的随机漫步[6]开发了其他一些方法

奇异值分解(SVD)和非负矩阵分解因其对低秩特征的最优性而在NE中得到了广泛的应用

此外，基于神经网络特别是深度学习的NE方法也不断被提出[1]，[9]。例如

• SDNE[10]可以基于自编码器联合利用一阶和二阶近度进行节点嵌入
• DVNE[11]可以通过集成基于变分自编码器(VAEs)的节点嵌入的不确定性来维持网络结构
• GraphSAGE[12]可以利用节点特征信息对之前未见过的数据高效地生成节点嵌入
• [13]提出了分析用于嵌入的图神经网络的理论框架。提出了更高效的鲁棒优化[14]和社区增强[15]方法
• 更详细的评论可以在[16]-[18]中看到

本质上，这些作品大多试图保留网络结构[19]或组合的局部(第一和第二相似性)、高阶(motif和群落相似性)或全局邻近性

---

然而，在各种现实世界的网络中，有一些情况下

两个节点即使没有共享一个连接，甚至相隔很远，但却扮演着相同的角色或占据着相同的位置[20]，这也被称为结构相似性问题

我们的目标是学习可以分配节点角色的嵌入

如图1所示，虽然节点和节点在网络中距离较远，但它们的作用是相同的，因为它们都被红节点包围

这通常与复杂网络中的角色发现或结构相似的内涵相对应，可用于在线社交网络(如Facebook、Twitter、Yelp)的在线广告活动，在传播、网络理论、网络分析[16]中具有重要意义

---

然而，考虑到这个问题的特殊性，所有这些方法都无一例外地失败了

具体来说，角色发现或结构相似性[21]通常表示为在网络中搜索一组连接模式相似的节点

原则上，确实有一些不同类型的传统方法可以解决这个问题[22]，例如，基于图的方法、基于特性的方法和混合方法

在所有这些方法中，角色发现最重要的步骤是从复杂网络中提取节点特征，或者根据网络的邻接矩阵计算相似度

然而，这些传统的基于特征工程[23]或矩阵分解[24]的角色发现工作，无法处理大规模的社交网络

在NE化趋势下，由于该问题与以往的节点嵌入有本质区别，如何学习角色发现引导的网元仍然是一个开放而重要的问题[25]。

---

近年来，在[20]和[26]-[29]中已经开发出了一些专注于角色发现或结构相似性的学习嵌入方案

然而，对于角色或结构相似性的节点嵌入仍然面临如下许多挑战

1. 扮演相同角色的节点通常是断开连接的[30]。如图1所示，相邻节点结构相似的节点，如节点d和节点f，在网络中通常相距较远。
2. 一个节点的角色依赖于它的邻居节点，并且与它的邻居节点有不同的依赖关系。 如图1所示，节点和节点具有相同的角色，因为它们都连接到多个红色节点，而节点f的角色独立于节点e和节点u的角色。然而，目前的工作如DRNE[20]忽略了每个节点与其邻居节点之间不同的依赖关系。如何学习专注于每个节点和它的邻居之间最相关的依赖关系的嵌入还没有解决。
3. 从网络中提取隐含的角色特征来指导基于角色的NE是一项有趣但困难的工作。虽然node2vec[6]可以通过结构相似性[31]在一定程度上提取角色特征，但利用宽度优先搜索获得局部特征来发现角色是不够的。有必要研究一种角色发现引导的网元方法来解决这些挑战。

一方面，对于挑战1和挑战2，我们设计了角色注意机制，不仅通过递归学习步骤驱动递归相似性​​21​​，而且自然聚合其嵌入的邻居节点(挑战2)

另一方面，对于挑战3，我们采用有效的特征提取方法提取节点的高维特征表示，可以揭示节点在给定网络中的角色

尽管这两个部分对角色发现至关重要，但要保持每个节点及其邻居和特性之间的不同依赖关系是不现实的，而且效率低下

然后，最重要的问题是如何通过统一的模型学习嵌入角色注意和角色特征矩阵的节点，使嵌入的节点更有效地揭示角色特征

---

为了解决上述挑战，我们设计了一个统一的深度学习框架RDAA，用于角色发现引导的NE

首先，我们采用递归特征提取方法获取节点的高维角色特征，可以探索被观测结构信息无法实现的潜在角色特征

然后，我们利用自动编码器框架将其编码到一个矢量空间，然后派生出一个角色注意机制，以有效地描述每个节点与其邻居节点之间的不同依赖关系

最后，我们设计了一种精细的绑定技术，将两部分结合在一起。通过将基于隐藏特征表示的自编码器和角色注意整合到注意机制中，设计一个联合损失函数进行训练，使上述两部分相互增强

此外，还进行了大量的定量和定性实验，以验证所提出的方法的有效性

---

主要贡献可归纳如下。

• 我们设计了一个统一的深度学习框架RDAA，用于角色发现引导的NE，它集成了自编码器和角色注意机制。
• 提出的深度学习框架可以提取角色的特征，有效地刻画每个节点与其相邻节点信息之间的不同依赖关系，并在原理上巧妙地融合了上述两部分
• 在基于角色的任务上的实验结果，包括结构化角色分类、角色可视化，以及在几个真实网络上的角色发现案例研究，表明RDAA模型与其他先进的方法相比可以取得显著的改进。

II. RELATED WORK

本文介绍了角色发现、角色发现或结构相似性指导的NE和自编码器框架方面的一些重要研究成果

A. Role Discovery

在网络科学中，角色发现(role discovery)研究[32]-[36]已有数十年的历史，其目的是区别节点[21]的功能或行为

认为相似角色的节点具有相似的连接模式(或更高阶结构)[37]

• Lorrain和White[32]首先根据结构等价性定义了节点的角色。该标准规定连接到相同邻居的节点扮演相同的角色。它的严格程度使得网络中相距较远的节点失效
• 为了放宽这一标准，White和Reitz提出了规则等价[34]，即相同角色的节点有角色等价的邻居
• Nowicki和Snijders[36]提出了随机等价，说明节点的角色是由邻居角色的分布决定的。无论以后使用什么方法来挖掘节点角色，它们都遵循或尝试接近这些标准。例如，RoleSim[35]，一个满足公理角色相似属性的角色相似度量，通过迭代计算过程满足常规等价标准。

还有一些其他的方法可以通过使用基于图或基于特征的结构相似性来挖掘角色

• refex[23]是一种递归的特征聚合方法，可以获得丰富的结构信息
• RolX[24]和GLRD[38]通过分解基于refx的特征矩阵来获取结构相似性
• RC-Joint[39]旨在同时检测社区和角色。在检测角色时，它利用最小散列签名有效地逼近角色相似性
• REACT[40]和struc2gauss[41]利用RoleSim将节点之间的相似性映射到向量空间
• RIDεRs通过ε-公平划分形成网络，并基于全局特征挖掘角色

B. NE for Structural Similarity

最近，受网络理论的启发，人们提出了几种保持网络结构相似性的方法，并用于角色发现。

• SNS[26]首先提出了利用结构信息进行网元处理以提高其质量，并通过结构相似性信息从本质上提高了嵌入的稳定性
• Struc2vec[30]将基于近邻度的相似度转换为完全图的边缘权值，并利用语言模型进行嵌入
• Role2vec[42]将语言模型的输入替换为基于motif-count的指示器
• DRNE[20]通过递归的方式聚合其邻域的嵌入来学习每个节点的表示
• HONE[27]是一种用于节点嵌入的高阶网络表示学习方法，它利用多重加权motif邻接矩阵来捕获结构角色的概念
• NRDR[28]基于两个目标学习基于角色的嵌入:一个是级联建模目标，目的是使观察到的级联的可能性最大化;另一个是矩阵分解目标，目的是重建结构的近邻
• GraphWave[43]利用热-小波扩散模式来表示节点，并将它们视为分布
• SEGK[44]通过在节点中心子图上应用图核方法计算节点之间的结构相似性，并通过矩阵分解生成嵌入
• SPaE[29]是一种基于graphlet度向量概念的混合网元方法，它同时结合了结构邻近性和相似性

C. Autoencoder for Complex Networks

由于能够对网络的高阶非线性特性进行建模，为NE开发了自编码器[10]，[45]框架及其扩展。

• SDNE[10]首先被设计用于将网络的一阶二阶邻近性纳入编码器-解码器框架，并分别将网络结构捕获为半监督和无监督形式。三联增强自编码器[46]基于度量学习捕获拓扑结构并保留判别信息
• AAANE[47]由一个基于注意的自编码器(约束潜在嵌入的后后分布)和一个对抗性正则化(约束先验分布的一致性)组成，因此，它可以促进不同尺度的鲁棒嵌入的协作
• 受VAEs的启发，Zhu等[11]提出了Wasserstein空间中的NE的DVNE，它学习了每个节点的高斯分布，并保持了网络的传递性。
• Chen等[48]提出了基于拉普拉斯特征映射的变分图嵌入和聚类，这是一种基于VAE的生成模型
• 在NE[49]中引入对抗性学习原理
• 在[50]和[51]中分别提出对抗性正则化图自编码器和自编码器
• 在[52]中提出了一个通用框架，通过优化节点重建损失和在整个图中传播嵌入，将自动编码器和VAE扩展到具有数百万个节点和边的图。

然而，上述几乎所有的方法都主要是为了捕捉网络中的邻近性，而不能对结构相似性和角色发现进行建模。

III. METHODOLOGY

在本节中，我们将介绍角色发现中NE的一些表示法和定义

然后给出所提出框架的详细构建过程，包括特征提取模块、编码器-解码器过程和角色注意机制

最后，我们展示了如何优化损失函数及其计算复杂度。

A. Notations and Definitions

给定一个无向无权网络

• 为节点集
• 为边集
• 节点的邻居为
• 表示邻接矩阵，其中表示，否则表示

通常表示网元学习一个映射

• 其中为嵌入维数
• 为节点数

---

Definition 1 (Network Embedding)

给定网络G的拓扑信息(如邻接矩阵)，NE旨在学习G中每个节点的连续向量，使这些向量能够揭示网络的统计结构特征

---

Definition 2 (Role Discovery Guided Network Embedding)

角色发现或基于结构相似性的NE通常可以定义为将节点划分为等价类的过程

设是节点的角色，角色发现的NE应用自己学习嵌入向量，使

• 式中，是衡量嵌入和相似度的函数
• 如果两个节点的角色相同，则它们的嵌入向量应该更相似、

（1）式的意思大概是：如果节点和节点的角色一样，那么其嵌入向量相似度应该接近1

---

根据上述定义和问题公式，给定任意网络，我们的目的是

• 基于边的集合学习每个节点的嵌入向量
• 同时，我们需要保持节点和在嵌入空间中相同角色或相同结构的相似性，即和应该接近

需要强调的是，我们的问题不同于经典的NE问题

• 在经典的NE问题中，节点嵌入几乎只在它们接近时才进行
• 基于这些嵌入，我们可以通过任意的聚类方法发现节点在网络中的角色，例如k-means聚类

B. Overall Framework

我们的框架RDAA的说明如图2所示

• 首先，我们采用递归特征提取算法提取能够揭示角色信息的高维特征
• 然后，我们利用自动编码器框架将网络编码到一个潜在空间，并设计一种注意机制来有效地描述每个节点与其邻居之间的不同依赖关系
• 最后，通过设计一种巧妙的技术，共同优化自编码器和角色注意机制，获得嵌入。事实上，我们从两个方面来利用网络拓扑的信息，即

• (1)特征提取
• (2)注意机制

C. Role Feature Extraction

由于具有相同角色的节点通常不相邻，即在网络中距离较远，因此邻接矩阵(一种描述网络拓扑结构的高维特征)在提取基于角色的特征时非常薄弱

因此，我们引入了一种提取维数小于的高维结构特征的方法

在众多的特征提取方法中，我们采用了[23]中描述的递归特征提取方法(ReFex)

• 该方法以递归的方式聚合局部特征和邻域特征，获取全局结构信息，从而可以提取足够的角色特征
• 具体来说，对于每个节点，它首先通过计算其相邻边和节点egonet中的边来生成主特征
• 然后，通过在egonet上应用一些简单的聚合算子，如求和和均值，递归地对主要特征进行聚合
• 显然，随着递归次数的增加，可以获得更高阶的结构特性

ReFex算法如下：

D. Encoder–Decoder

虽然RDAA模型在特征提取方面很灵活，但为了将各种特征嵌入到低维向量空间中，并集成下一节描述的角色注意机制

我们在这里引入并扩展了用于角色特征重构的深度自编码器

---

编码器由多层感知器组成，它将特征编码为低维表示。具体来说，给定feature ，每层的隐藏表示可以表示为

其中

• 表示节点的高维特征

利用编码器的一部分，我们可以生成节点的嵌入，然后将编码器的过程颠倒如下，得到重构数据

其中节点嵌入为方便记为

编码器-解码器结构的目标是通过最小化输入特征与重构数据之间的误差来获得低维表示

重构的损失函数表示为:

最小化重构损失可以使节点表示平滑地捕获数据流形，并保持节点在低维空间中的角色特征

但是考虑到如果特征中有大量的零元素，我们的模型会很容易重构中的零元素，这是不可取的

为了解决这一问题，我们引入系数对重构损失函数进行修正如下:

• 表示 Hadamard product
• 设表示中的第个元素，表示中的第个元素，则如果，否则，其中是控制非零元素贡献的超参数
• 事实上，通过为每个节点引入，我们可以捕捉到不同节点的不同重要性

E. Role Attention Mechanism

正如在第1节中提到的，我们通过角色发现或结构相似性来定义NE

根据定义2，通过集成节点的邻域嵌入，以递归的方式约束节点嵌入

使用聚类的方式

然后，我们可以根据结构相似性约束设计一个损失函数如下:

• 式中是一个聚合函数，用于聚合邻居的嵌入

显然，节点嵌入可以通过保留局部角色信息，也可以通过迭代更新节点嵌入获得全局角色相似度信息，这与NE的结构相似度是一致的

---

众所周知，节点的作用与其邻域的部分密切相关

如图1所示，节点的作用依赖于其周围的红节点，而节点和的作用与节点的作用关系不大

为了描述每个节点及其邻居之间的不同依赖关系，我们设计了一种注意力机制

• 允许处理大小可变的输入
• 并专注于输入中最相关的部分

我们对节点执行自我注意[53]来计算注意相关系数

其中，是共享注意力机制

与传统的注意机制不同，我们只关注相邻节点

因此，我们只在邻居上计算，然后在所有选择的利用softmax函数中对它们进行归一化，如下所示:

式中

• 查询向量为权重向量
• ⊕表示拼接操作

然后，我们利用归一化系数定义G，计算邻居节点表示的线性组合如下:

• 式中σ为s型激活函数

然后，基于角色注意机制结构相似性约束的损失函数可以表示为

F. Joint Training

通过损失函数的两部分，我们可以共同优化由自编码器和角色注意机制组成的统一的深度学习框架

为了防止过拟合，进一步提高RDAA的鲁棒性，我们定义了一个正则化器:

然后，最终的联合损失函数设计为

• 其中和分别为和的权值

---

我们首先通过算法1生成特征矩阵作为我们的模型RDAA的输入

然后随机初始化模型的所有参数

对于每个节点，我们可以通过(3)生成其嵌入作为编码器的最后一层，用于重构其特征

为了利用注意机制，我们通过(10)赋予其邻居的权重，然后得到中间结果来计算通过(14)的联合训练

我们巧妙地整合了自动编码器和角色注意机制。在得到最终的损失后，我们可以计算其他参数的梯度，并利用反向传播机制进行更新，使其最小化

我们重复这个过程很多次，直到损失收敛

最后，我们应用训练好的参数来生成节点嵌入

G. Computational Complexity Analysis

优化目标函数的算法见算法2

对于每个节点，计算时间复杂度最高的归一化注意系数，为，

• 其中为节点的最大度
• 为嵌入维数

然后训练和更新参数取

因此，总时间复杂度记为

由于通常将节点嵌入的维数设为较小的数，且大多数节点的度都较小

因此我们算法的时间复杂度为，对于大规模网络，它与节点数量线性

IV. PERFORMANCE EVALUATION

A. Datasets and Metrics

Datasets

• Barbell Graph
• American, European, and Brazilian Air-Traffic Network
• Actor Co-Occurrence Network
• Ca-Netscience Network

Metrics

• F1-micro
• F1-macro

B. Experimental Settings

为了实证评估 RDAA 模型的有效性，我们将其与广泛使用的嵌入算法进行了比较，包括五种基于邻近度的方法和八种基于角色的嵌入方法。这里介绍它们的机制。

在接下来的角色分类和发现实验中，除了 GraphWave 和 RIDεRs 之外，所有基线方法的嵌入维度都设置为 128。 GraphWave 将默认维度设置为 100，而 RIDεR 的维度不固定。为了使 node2vec 的随机游走更加 BFSbiased，它的两个超参数 p 和 q 分别设置为 1 和 2。其他参数与原始论文中提到的默认值保持一致。从embedding机制来看，node2vec、struc2vec、struc2gauss是基于随机游走的，LINE、GraphWave、SEGK、RIDεRs、RolX是来自低秩矩阵分解，SDNE、DRNE、GraLSP、GraphSTONE、RESD是受到深度学习的启发。 RDAA 框架包括一个多层深度神经网络，其在不同数据集上的设置如表 II 所示。

对于提出的 RDAA 模型，我们设置超参数 β = 3，损失函数的权重 = 15，损失函数的权重

C. Visualization

为了说明 RDAA 模型与角色发现的一些基线相比的有益性能，我们在杠铃图上进行了几个可视化实验，如图 3 所示，从中我们可以得出如下重要的观察结果。

RDAA 模型的性能比 LINE、node2vec、SDNE、GraLSP 和 GraphSTONE 好得多，因为角色发现引导的 NE 可以使具有相同角色的节点在嵌入空间中更接近。 LINE 不能很好地探索网络的相似性，因为它只考虑成对的邻近性。尽管node2vec考虑了结构相似性，但无论模型参数p和q的不同组合，它仍然无法捕获全局结构相似性信息。 SDNE 旨在对网络的非线性进行建模，似乎将具有相同角色的节点投影到附近的点，但它将路径 P 上的几乎所有节点分配在一起，这显然是错误的。 GraLSP 和 GraphSTONE 可以有效地捕获网络中的近似值，但未能在该领域嵌入面向角色的网络。

尽管 DRNE、RolX、struc2gauss 和 RESD 试图学习属于同一角色的节点的结构特征，但它们都未能捕捉到两个团的节点的特征。 DRNE关注节点度的影响而忽略了高阶属性，节点显然分为两部分：a）路径上的节点和b）两个派系。 RolX 基于特征提取和非负矩阵分解，忽略了网络的非线性结构。 struc2guass 通过 RoleSim 计算角色相似度，很难区分路径中节点的微妙角色差异。 RESD侧重于重构特征，而忽略节点之间的依赖关系

相对而言，SEGK、RIDεRs和RDAA模型对路径P中节点的区分能力更强。它们都发现了相同角色的节点，尤其是两个团，如图3所示。这是因为这些方法可以有效地对节点的相似特征进行建模，并学习角色发现引导的嵌入。但是，其他两种方法或多或少会丢失一些节点信息，因为它们过度拟合了网络。

需要强调的是，struc2vec 和 GraphWave 最接近我们的方法，但是它们的青色节点向量不如我们的方法。此外，这两种方法的复杂度都较高。

D. Experiments on Role Classification

为了定量评估基于角色的嵌入，我们对结构角色分类进行了实验，这是最重要和最直观的任务。我们在预测节点角色的基础上评估 RDAA 模型在美国、欧洲和巴西空中交通网络和 Actor 共现网络上的能力和性能。对于每个基线和 RDAA 模型，我们随机抽取 10%–90% 的学习嵌入作为训练集，用于训练一个简单的逻辑回归分类器，并将另一部分作为测试集，用于评估性能。我们采用与其他方法相同的策略进行十倍交叉验证并报告平均值。

最后，我们使用 F1-micro 和 F1-macro 评估性能。详细的实验结果如图 4 所示，从中我们有以下观察结果。

一般来说，我们提出的 RDAA 优于四个网络上的几乎所有基线，表明 RDAA 在结构角色分类方面表现出色，并且可以很好地预测角色。只有 RIDεR 比巴西的空中交通网络略占优势。 RESD 在这些网络上的这项任务上取得了有竞争力的结果。 node2vec 和 LINE 模型的性能较差，因为它们专注于接近度而忽略了节点的结构相似性。 SDNE 在巴西空中交通和 Actor 共现网络上表现不佳。基于角色的嵌入的所有其他方法都是次优的，并且在角色分类上是稳定的。具体来说，所有方法在美国空中交通网络上的 F1 分数都高于欧洲空中交通网络。同时，RDAA 模型在美国空中交通网络上实现了更大的性能改进。由于美国空中交通网络的复杂结构，我们的角色注意机制能够更准确地揭示节点与其邻居之间的不同依赖关系。

此外，我们使用统计测试来查看 RDAA 模型的重要性和稳定性，并将其与美国、欧洲和巴西空中交通网络以及 Actor 共现网络上的其他 10 个基线进行比较。在这里，我们将训练集的比例设置为 0.7，随机运行 20 次。 F1-micro 和 F1-macro 的性能如表 III 所示，其中列出了每种方法在不同数据集上的结果的均值和标准差。很容易知道，所有方法的标准差都比较小，没有明显的差异。

此外，我们还将结果与 RDAA 的几个变体（一些消融实验）进行了比较。这里，RDAE 表示没有 Lrole 的模型，我们删除了注意力的部分。另一方面，我们评估了 RDMAA 中 LAE 的另一种类型的损失函数，我们将其替换为 LAE = ∑n i=1 |(xi - xi) βi|。根据两种消融模型和表三的结果，我们知道RDAA具有明显的优势，表明它的每一部分都是有效的。此外，我们还在表 IV 中报告了所有这些方法的运行时间，我们的方法具有折衷水平。

E. Parameters Sensitivity

在这一部分中，我们研究参数是否以及如何影响性能。具体来说，我们评估节点表示的维度 d 以及超参数 β 和 γ 的有效性。我们将结构角色分类任务分别应用于美国、欧洲和巴西的空中交通网络。

从图 5（a）中，我们观察到在维度 d 增加的同时，性能最初得到了显着改善。然后，当维度大于 16 时，效果趋于稳定，这证明了 RDAA 模型的鲁棒性和有效性。

图 5(b) 表明，随着控制 Lrole 贡献的超参数 γ 的增加，性能首先增加，然后逐渐变平。性能的提高证明了 RDAA 模型中角色注意机制的有效性。当 γ = 15 时，我们的方法在所有网络上的 F1-micro 和 F1-macro 指标都具有最佳性能。

图 5© 显示了超参数 β 的影响，该参数用于惩罚比零元素更难的非零元素对重构误差的影响。总体而言，当 β = 3 时，我们的方法几乎可以达到最佳性能。

F. Efficient versus Effective

如图 6 所示，我们提供了欧洲和美国空中交通网络上不同方法的嵌入时间和分类结果的比较。可以看出，这些方法的有效性和效率之间存在折衷。一方面，我们的 RDAA 模型在所有方法中具有最好的分类结果，这证明了 RDAA 在角色发现方面的优越性。另一方面，RDAA 的嵌入时间略长于 SEGK 和 struc2gauss，这意味着 RDAA 的效率不如 SEGK 和 struc2gauss；但是，它在可接受的范围内。与 RDAA 相比，RESD 具有具有竞争力的性能并且效率略高。

总体而言，RDAA 模型在 F1-micro 分数方面取得了最佳性能，仅牺牲了一小部分嵌入时间。

G. Case Study: Role Discovery

对 ca-netscience 网络进行了案例研究，以展示 RDAA 模型在角色发现方面的有效性。我们首先在这个网络上训练模型并为每个节点生成一个表示。然后，我们为它们分配角色，作为通过 K-Means 模型进行聚类的任务。通过这样做，可以通过分析嵌入是否反映结构相似性来评估这些方法的性能。

直观地，我们可以从图 7 中观察到 node2vec、LINE 和 SDNE 无法通过聚类进行角色挖掘。 SDNE 显然是一种基于社区的嵌入方法，因为网络被划分为多个节点密集连接的子图。由于 LINE 只能以浅层的方式保留一阶和二阶近似，因此相同颜色的节点通常作为邻居出现或具有相同的邻居。 GraLSP 和 GraphSTONE 都为图神经网络中的局部传播机制学习了面向邻近的结果。

由于我们偏向 BFS 的参数设置，node2vec 捕获结构信息的能力有限：几乎所有颜色都出现在每个局部部分；但是，没有观察到明显的模式。 DRNE、struc2vec 和 RIDεRs 的结果显示出与节点度数的强相关性，这主要取决于它们基于度数的过程。虽然 DRNE 也以与 struc2gauss 类似的方式对某些节点进行着色，因为它们都旨在捕获常规等效性。 RolX、struc2vec、SEGK和RIDεRs由于结构信息计算浅而硬，以非常困难的方式聚类节点，这使得可视化结果看起来有点混乱。 RESD 将具有相同度数的节点划分为一个簇，用于其直接正则化项。相反，GraphWave 和我们的 RDAA 的性能优于其他嵌入方法，尤其是在黑色矩形突出显示的子图上。然而，我们的 RDAA 在区分星形子图和类团子图方面的表现也比 GraphWave 好得多。所有这些结果表明，RDAA模型可以更有效地挖掘节点的角色。

V. CONCLUSION

本文提出了一种统一的深度学习框架，用于角色发现和结构相似性引导NE

该框架集成了自编码器和角色注意机制

• 特别是，所提出的角色注意机制有效地描述了每个节点与其相邻节点之间的依赖关系的变化

---

我们还精心设计了一种绑定技术，将这两个部分结合在一起，以统一的方式优化提出的框架。

实验结果证明了RDAA模型的有效性，因为它确实捕获了一些独特的信息

此外，提出的RDAA模型可以很容易地扩展到不同的形式。首先，特征提取可以以任何方式替代，可以表明基于角色的结构特征

然后，自动编码器过程可以通过VAE、图卷积网络或其他方法进行交换

此外，我们可以采用类似于简并框架[52]的方式将RDAA扩展到大规模网络

---

缺点是该模型是一个相对独立的特征提取模块;然而，如何为RDAA模型设计一个端到端框架是一个潜在的研究热点

未来，我们将研究如何改进RDAA，使其能够同时应用于节点和边缘的角色发现，并计划将提出的模型扩展到多层网络和动态网络分析

定量评价也是该问题的一个研究方向

读后总结

2022/07/11 第一次阅读

总体思路文章写的还是比较清晰的

算法步骤

1）使用refex提取每个节点的特征向量

2）使用编码器（ML）对进行编码得到

3）使用解码器对进行解码，得到重构后的

4）计算损失

5）依据结构相似性质（依据与其邻域节点的聚合嵌入进行相似性比较），得到损失

这里感觉利用的还是结构相似，为啥用role命名，有点迷？？

其中的计算方法为

• 其中是注意力机制中的查询向量（我们需要训练的参数）

6）然后为了防止过拟合，构建损失

7）得到最后损失函数

8）依据训练AE、注意力机制的参数，直到函数收敛，得到最终的嵌入

疑问：

1. 感觉的计算还是利用邻域（结构性质的），没有利用提取得到的refex特征进行聚类（是不是自己看漏了？）

再接再厉， 多看论文！

结语

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

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