@TOC

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

前语

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

知其然知其所以然！

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

简介

原文链接：ieeexplore.ieee.org/abstract/do…

期刊：IEEE Transactions on Systems, Man, and Cybernetics: Systems

代码：github.com/cspjiao/RDA…

年度：2021/06/29

Abstract

近年来，网络嵌入(network embedding, NE)是杂乱网络研讨中的一个热门，致力于各式各样的使命

简直一切的网络模型和办法都是根据网络的部分类似性、高阶类似性或大局类似性，很少有研讨聚集于人物发现或结构类似性，这对传达动力学和网络理论具有重要意义

一起，现有的人物发现NE模型存在两方面的局限性:

不能对每个节点与其相邻节点之间的依靠联系进行建模
不能捕获有助于人物发现的有用节点特征

根据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所示，尽管节点 $f$ 和节点 $d$ 在网络中距离较远，但它们的效果是相同的，因为它们都被红节点包围

这一般与杂乱网络中的人物发现或结构类似的内涵相对应，可用于在线交际网络(如Facebook、Twitter、Yelp)的在线广告活动，在传达、网络理论、网络剖析[16]中具有重要意义

可是，考虑到这个问题的特殊性，一切这些办法都无一例外地失败了

具体来说，人物发现或结构类似性[21]一般标明为在网络中查找一组衔接形式类似的节点

原则上，确实有一些不同类型的传统办法可以处理这个问题[22]，例如，根据图的办法、根据特性的办法和混合办法

在一切这些办法中，人物发现最重要的进程是从杂乱网络中提取节点特征，或许根据网络的邻接矩阵核算类似度

可是，这些传统的根据特征工程[23]或矩阵分化[24]的人物发现作业，无法处理大规划的交际网络

在NE化趋势下，因为该问题与以往的节点嵌入有本质区别，怎么学习人物发现引导的网元依然是一个开放而重要的问题[25]。

近年来，在[20]和[26]-[29]中现已开发出了一些专心于人物发现或结构类似性的学习嵌入方案

可是，关于人物或结构类似性的节点嵌入依然面临如下许多应战

扮演相同人物的节点一般是断开衔接的[30]。如图1所示，相邻节点结构类似的节点，如节点d和节点f，在网络中一般相距较远。
一个节点的人物依靠于它的街坊节点，并且与它的街坊节点有不同的依靠联系。如图1所示，节点 $f$ 和节点 $s$ 具有相同的人物，因为它们都衔接到多个红色节点，而节点f的人物独立于节点e和节点u的人物。可是，目前的作业如DRNE[20]疏忽了每个节点与其街坊节点之间不同的依靠联系。怎么学习专心于每个节点和它的街坊之间最相关的依靠联系的嵌入还没有处理。
从网络中提取隐含的人物特征来辅导根据人物的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将节点之间的类似性映射到向量空间
RIDRs经过-公平区分形成网络，并根据大局特征发掘人物

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

给定一个无向无权网络 $G = (V, E)$

$V$ 为节点集
$E \subseteq V V$ 为边集
节点 $i$ 的街坊为 $N_{(i)} = \{j|(i, j)∈E\}$
$A$ 标明邻接矩阵，其间 $A_{i,j} = 1$ 标明 ${(i, j)∈E\}$ ，不然标明 $A_{i,j} = 0$

一般标明网元学习一个映射 $F: V→R^d$

其间 $d < < ∣ V ∣$ 为嵌入维数
$n = ∣ V ∣$ 为节点数

Definition 1 (Network Embedding)

给定网络G的拓扑信息(如邻接矩阵)，NE旨在学习G中每个节点 $i$ 的接连向量 $z_i$ ，使这些向量可以提醒网络的统计结构特征

Definition 2 (Role Discovery Guided Network Embedding)

人物发现或根据结构类似性的NE一般可以界说为将节点区分为等价类的进程

设 $r (i)$ 是节点 $i$ 的人物，人物发现的NE运用自己学习嵌入向量 $z_j$ ，使

式中， $S (\cdot)$ 是衡量嵌入 $z_i$ 和 $z_j$ 类似度的函数
假如两个节点的人物相同，则它们的嵌入向量应该更类似、

（1）式的意思大概是：假如节点 $i$ 和节点 $j$ 的人物相同，那么其嵌入向量类似度应该挨近1

根据上述界说和问题公式，给定恣意网络 $G$ ，咱们的意图是

根据边的调集学习每个节点的嵌入向量
一起，咱们需求坚持节点 $i$ 和 $j$ 在嵌入空间中相同人物或相同结构的类似性，即 $z_i$ 和 $z_j$ 应该挨近

需求着重的是，咱们的问题不同于经典的NE问题

在经典的NE问题中，节点嵌入简直只在它们挨近时才进行
根据这些嵌入，咱们可以经过恣意的聚类办法发现节点在网络中的人物，例如k-means聚类

B. Overall Framework

咱们的结构RDAA的说明如图2所示

首要，咱们选用递归特征提取算法提取可以提醒人物信息的高维特征
然后，咱们运用主动编码器结构将网络编码到一个潜在空间，并规划一种留意机制来有用地描绘每个节点与其街坊之间的不同依靠联系
终究，经过规划一种奇妙的技能，一起优化自编码器和人物留意机制，取得嵌入。事实上，咱们从两个方面来运用网络拓扑的信息，即
- (1)特征提取
- (2)留意机制

C. Role Feature Extraction

因为具有相同人物的节点一般不相邻，即在网络中距离较远，因而邻接矩阵(一种描绘网络拓扑结构的高维特征)在提取根据人物的特征时十分薄弱

因而，咱们引进了一种提取维数小于 $∣ V ∣$ 的高维结构特征的办法

在很多的特征提取办法中，咱们选用了[23]中描绘的递归特征提取办法(ReFex)

该办法以递归的办法聚合部分特征和邻域特征，获取大局结构信息，然后可以提取足够的人物特征
具体来说，关于每个节点，它首要经过核算其相邻边和节点egonet中的边来生成主特征
然后，经过在egonet上运用一些简单的聚合算子，如求和和均值，递归地对首要特征进行聚合
明显，随着递归次数的增加，可以取得更高阶的结构特性

ReFex算法如下：

D. Encoder–Decoder

尽管RDAA模型在特征提取方面很灵敏，但为了将各种特征嵌入到低维向量空间中，并集成下一节描绘的人物留意机制

咱们在这里引进并扩展了用于人物特征重构的深度自编码器

编码器由多层感知器组成，它将特征编码为低维标明。具体来说，给定feature $x_i$ ，每层的躲藏标明可以标明为

其间

$x_i$ 标明节点 $i$ 的高维特征

运用编码器的一部分，咱们可以生成节点 $i$ 的嵌入 $zi=hi(K)z_i = h^{(K)}_i$ ，然后将编码器的进程倒置如下，得到重构数据 $xi\hat x_i$

其间节点嵌入 $z_i$ 为方便记为 $zi=hi(K)z_i = \hat h^{(K)}_i$

编码器-解码器结构的方针是经过最小化输入特征与重构数据之间的误差来取得低维标明

重构的丢失函数标明为:

最小化重构丢失可以使节点标明平滑地捕获数据流形，并坚持节点在低维空间中的人物特征

可是考虑到假如特征中有很多的零元素，咱们的模型会很简单重构 $x_i$ 中的零元素，这是不可取的

为了处理这一问题，咱们引进系数对重构丢失函数进行批改如下:

$⊙\odot$ 标明 Hadamard product
设 $x_{il}$ 标明 $x_i$ 中的第 $l$ 个元素， $_{il}$ 标明 $_i$ 中的第 $l$ 个元素，则假如 $x_{il} =0， _{il} = 1$ ，不然 $_{il} = > 1$ ，其间是控制非零元素奉献的超参数
事实上，经过为每个节点 $i$ 引进 $_i$ ，咱们可以捕捉到不同节点的不同重要性

E. Role Attention Mechanism

正如在第1节中提到的，咱们经过人物发现或结构类似性来界说NE

根据界说2，经过集成节点的邻域嵌入，以递归的办法束缚节点嵌入

运用聚类的办法

然后，咱们可以根据结构类似性束缚规划一个丢失函数如下:

式中 $G: \{z_j|(j)∈V\}→R^d$ 是一个聚合函数，用于聚合街坊的嵌入

明显，节点嵌入可以经过 $G$ 保存部分人物信息，也可以经过迭代更新节点嵌入取得大局人物类似度信息，这与NE的结构类似度是一起的

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

如图1所示，节点 $f$ 的效果依靠于其周围的红节点，而节点 $e$ 和 $u$ 的效果与节点 $f$ 的效果联系不大

为了描绘每个节点及其街坊之间的不同依靠联系，咱们规划了一种留意力机制

允许处理巨细可变的输入
并专心于输入中最相关的部分

咱们对节点履行自我留意[53]来核算留意相联系数

其间， $a: R^d R^d→R$ 是同享留意力机制

与传统的留意机制不同，咱们只重视相邻节点

因而，咱们只在街坊上核算 $e_{ij}$ ，然后在一切选择的 $j$ 运用softmax函数中对它们进行归一化，如下所示:

式中

查询向量 $q∈R^{2d}$ 为权重向量
⊕标明拼接操作

然后，咱们运用归一化系数界说G，核算街坊节点标明的线性组合如下:

式中为s型激活函数

然后，根据人物留意机制结构类似性束缚的丢失函数可以标明为

F. Joint Training

经过丢失函数的两部分，咱们可以一起优化由自编码器和人物留意机制组成的一起的深度学习结构

为了避免过拟合，进一步进步RDAA的鲁棒性，咱们界说了一个正则化器:

然后，终究的联合丢失函数规划为

其间和分别为 $L_{role}$ 和 $L_{reg}$ 的权值

咱们首要经过算法1生成特征矩阵 $X$ 作为咱们的模型RDAA的输入

然后随机初始化模型的一切参数 $(W(k)，b(k)，W(k)，b(k)，q)(W^{(k)}， b^{(k)}，\hat W^{(k)}，\hat b^{(k)}， q)$

关于每个节点 $v_i$ ，咱们可以经过(3)生成其嵌入 $z_i$ 作为编码器的终究一层，用于重构其特征 $x_i$

为了运用留意机制，咱们经过(10)赋予其街坊 $v_j$ 的权重 $_{ij}$ ，然后得到中心成果来核算 $L_{loss}$ 经过(14)的联合练习

咱们奇妙地整合了主动编码器和人物留意机制。在得到终究的丢失 $L$ 后，咱们可以核算其他参数的梯度，并运用反向传达机制进行更新，使其最小化

咱们重复这个进程很多次，直到丢失收敛

终究，咱们运用练习好的参数来生成节点嵌入

G. Computational Complexity Analysis

优化方针函数的算法见算法2

关于每个节点，核算时刻杂乱度最高的归一化留意系数，为 $O (D d)$ ，

其间 $D$ 为节点的最大度
$D$ 为嵌入维数

然后练习和更新参数取 $O(Dd^2)$

因而，总时刻杂乱度记为 $O(|V|Dd^2)$

因为一般将节点嵌入的维数 $d$ 设为较小的数，且大多数节点的度都较小

因而咱们算法的时刻杂乱度为 $O (∣ V ∣)$ ，关于大规划网络，它与节点数量 $∣ V ∣$ 线性

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

略

C. Visualization

D. Experiments on Role Classification

E. Parameters Sensitivity

F. Efficient versus Effective

G. Case Study: Role Discovery

V. CONCLUSION

本文提出了一种一起的深度学习结构，用于人物发现和结构类似性引导NE

该结构集成了自编码器和人物留意机制

特别是，所提出的人物留意机制有用地描绘了每个节点与其相邻节点之间的依靠联系的改变

咱们还精心规划了一种绑定技能，将这两个部分结合在一起，以一起的办法优化提出的结构。

试验成果证明了RDAA模型的有用性，因为它确实捕获了一些共同的信息

此外，提出的RDAA模型可以很简单地扩展到不同的形式。首要，特征提取可以以任何办法代替，可以标明根据人物的结构特征

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

此外，咱们可以选用类似于简并结构[52]的办法将RDAA扩展到大规划网络

缺陷是该模型是一个相对独立的特征提取模块;可是，怎么为RDAA模型规划一个端到端结构是一个潜在的研讨热门

未来，咱们将研讨怎么改进RDAA，使其可以一起运用于节点和边缘的人物发现，并方案将提出的模型扩展到多层网络和动态网络剖析

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

读后总结

2022/07/11 第一次阅览

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

算法进程

1）运用refex提取每个节点的特征向量 $x_i$

2）运用编码器（ML）对 $x_i$ 进行编码得到 $z_i$

3）运用解码器对 $z_i$ 进行解码，得到重构后的 $xi\hat x_i$

4）核算丢失 $L_{AE}$

5）根据结构类似性质（根据 $z_i$ 与其邻域节点的聚合嵌入进行类似性比较），得到丢失 $L_{role}$

这里感觉运用的仍是结构类似，为啥用role命名，有点迷？？

其间 $G (.)$ 的核算办法为

其间 $q$ 是留意力机制中的查询向量（咱们需求练习的参数）

6）然后为了避免过拟合，构建丢失 $L_{reg}$

7）得到终究丢失函数 $L_{AE} + \gamma L_{role} + \lambda L_{reg}$

8）根据 $L$ 练习AE、留意力机制的参数，直到函数收敛，得到终究的嵌入

疑问：

感觉 $L_{role}$ 的核算仍是运用邻域（结构性质的），没有运用提取得到的refex特征进行聚类（是不是自己看漏了？）

再接再厉，多看论文！

结语

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

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

我正在参加技能社区创作者签约方案招募活动，点击链接报名投稿。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

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

前语

简介