前言

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

知其然 知其所以然！

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

简介

原文链接：link.springer.com/chapter/10.…

会议：International Conference on Database Systems for Advanced Applications（DASFAA CCF B类）

年度：2020/09/22

Abstract

在杂乱网络中，人物一般代表节点的部分衔接形式，它反映了相应实体的功用或行为

人物发现对了解网络的构成与演化具有重要意义

跟着人物发现在网络中的重要性逐步被认识到，各种面向人物的网络表明学习办法被提出

现有的办法简直都依赖于人工的高阶结构特性，而这些特性往往是琐细的

它们的功能不稳定，泛化才能较差，由于其手艺结构特征有时会忽略不同网络的特征

---

此外，图神经网络(gnn)在主动捕获结构特性方面具有很大潜力，但由于面向人物无监督丢失的规划困难，很难对其进行操控

为了战胜这些应战，咱们提出了一个主意，运用低维提取的结构特征作为辅导练习图神经网络

在此根底上，咱们提出了一种新的根据结构信息的图数据自编码器GAS来学习面向人物的节点表明

很多的试验成果表明，该办法具有较好的功能。

1 Introduction

Graph or Network是不规矩数据在很多应用范畴的天然表明结构，包括社交网络[28]、蛋白质组学[31]等

具体来说，网络中的节点和边被用来表明实际国际的实体及其联系

这样，许多范畴的不同问题就能够转化为相应的网络研讨问题

在实际中对杂乱系统进行建模时，网络中包括着许多有用的隐藏信息，值得咱们仔细发掘和剖析

社区检测[11]和人物发现[21,24]就是在介观层面发掘网络信息的两个研讨范畴

---

社区检测和人物发现是两种根据不同标准的图数据聚类问题

如图1所示，在构成内部衔接多于外部衔接的社区时，节点在部分衔接形式中发挥着不同的作用

与之相对应的是，实际国际中的实体总是在群体中执行各种功用和行为，比如不同岗位的雇主和职工组成公司

• 研讨社区能够协助了解实体的共同利益和方针
• 而研讨人物则有助于捕捉联系之间的差异

因而，社区和人物关于了解网络的构成和演化具有重要意义

---

但是，长期以来，社区发现得到了深化的研讨，而人物发现近年来却受到越来越多的重视

本质上，人物发现是捕获节点结构特点的进程

因而，根据节点中心结构核算的经典衡量，例如PageRank[18]和其他节点中心，能够被视为人物衡量

但这些方针只能从特定角度表征人物，一般具有较高的核算杂乱度，束缚了其在大规模网络上杂乱大规模剖析和机器学习使命中的应用

幸运的是，网络嵌入(Network Embedding，又称网络表明学习)运用低维向量保存网络中原始节点信息

在大规模网络表明方面表现出了巨大的才能

与上述方针相比，学习到的嵌入是更通用的表明

这种嵌入办法在失掉杂乱的图结构、将很多信息保存在向量中的一起，能够轻松有效地用于很多的网络剖析和机器学习使命

但是，现有的网络嵌入算法[5,19,25]大多根据节点的附近性，即网络中节点越近，嵌入的类似性越高

换句话说，这些算法是面向社区的

跟着人物重要性的逐步认识，近年来提出了一些面向人物的网络嵌入办法

---

面向人物网络嵌入的意图是对以节点为中心的结构信息进行编码，将节点之间的结构类似性转化为嵌入空间中的几何联系

根据此意图，简直一切面向人物的网络嵌入办法都分为两个进程:

• (S1)获取节点的结构特点
• (S2)将结构性质和类似性映射到嵌入

大多数面向人物的嵌入办法运用高阶结构特征来捕获结构信息。例如，

• role2vec[1]和HONE[23]运用了称为motifs的小诱导子图
• 而RolX[8]、GLRD[3]和DMER[12]运用了递归特征聚合算法ReFeX[9]
• DRNE[27]运用层规范化的lstm来表明排序街坊上的节点
• 一起，随机散步[1,20]、矩阵分化[7,8]和图神经网络[12,27]是常用的映射办法

明显，取得高质量的结构功能是学习面向人物嵌入的要害

但是，大多数面向人物的嵌入办法运用的提取结构特点的办法有许多束缚

• 首先，这些提取办法是手艺的，得到的信息比较琐细。虽然在不同的网络中，决定人物的特征是不同的，但提取的特征并不遍及适用
• 第二，一些无监督学习办法会使生成的嵌入过度拟合输入特征，而忽略图结构。手艺结构特征虽然直观易懂，易于操作，但存在很多信息丢失的问题
• 第三，提取高阶结构特征，如图画，或许是适当耗时的

---

此外，图神经网络(GNNs)由于其在边上的传达机制，具有学习结构特性的天然才能

但是，规划面向人物的无监督丢失是适当困难的。虽然已有一些研讨尝试了输入特征重构、邻域递归调集近似嵌入等不同办法

但由于过于依赖人工提取进程，仍存在上述局限性

面向人物的GNN模型只需求很少的辅导就能够主动提取出高质量的结构信息

---

为了处理上述问题，咱们提出了一种新的根据结构信息的图形自编码器GAS

• 在GAS中，咱们运用图卷积层[14]来获取结构特点
• 咱们将每个图卷积层中的对称归一化邻接矩阵替换为非归一化邻接矩阵，以更有力区域分部分结构
• 咱们运用结构特征作为引导信息，而不是输入信息，这样咱们的办法能够极大地缓解过度依赖手艺特征带来的问题
• 此外，咱们运用的特征是经过调集一次街坊的首要特征，它们的维数很低。由于没有很多不必要的核算，咱们的模型是十分高效的

---

综上所述，本文的奉献如下:

• 咱们初次提出了运用结构特征作为辅导信息练习面向人物的图神经网络的思维。
• 咱们提出了一种新的根据结构信息的面向人物使命的图数据自编码器GAS。咱们运用极低维度的特性来进步GAS的效率和有效性。
• 在多个实在数据集上的各种试验中，咱们的嵌入办法比其他先进的嵌入办法表现得更好，咱们的辅导思维的正确性和办法的有效性得到了验证。

2 Related Work

图是不规矩结构，实际国际的网络往往是大规模的、稀疏的

因而，直接运用图结构数据作为杂乱、海量网络使命的输入十分困难

受词嵌入办法对稀疏散布的词发生低维密集表明的启发，提出了将节点编码到低维嵌入空间的网络嵌入办法

• DeepWalk[19]是第一个将经典言语模型SkipGram[17]引进网络表明学习的。它运用随机遍历生成由节点组成的序列作为Skip-Gram的输入。然后，SkipGram生成节点的表明
• Node2vec[5]在DeepWalk的根底上，经过添加两个超参数使随机散步有误差，以一起捕捉节点的同质性和结构特性。但是，由于类似的节点上下文，网络中挨近的节点的嵌入仍然是类似的
• 为了适用于大规模网络，LINE[25]运用了保存节点直接链接(一阶附近性)和共享街坊(二阶附近性)的方针函数和优化方针的边际采样算法

因而，这些办法都是为获取节点的附近性而规划的，关于面向人物的使命不可行

近年来提出了一些面向人物的网络嵌入办法，ReFeX[9]提取本地和egonet特征，递归地聚合街坊的特征

ReFeX作为一种高效的高阶结构特征提取办法，在许多面向人物的嵌入办法中得到了广泛的应用。例如，

• RolX[8]运用ReFeX提取结构特征，并经过非负矩阵分化生成嵌入
• 随后，GLRD[3]扩展了RolX，在NMF公式中加入了稀疏性和多样性束缚
• 同样，REGAL[7]中的xNetMF首先经过核算每个节点k-hop街坊的节点度来取得结构特征。然后运用奇异值分化将根据结构和特点核算的类似度编码到表明中

有几种根据随机游动的办法

• Role2vec[1]规划了一个根据特征的随机游走学习面向人物的嵌入。它将DeepWalk中的节点序列替换为根据主题的特征值序列，以便在表明中保存结构信息
• 与Role2vec直接运用随机游走的特性不同，Struc2vec[20]经过将根据程度的结构类似性转换为边的权值来构建完全图的层次结构。构建完成后，在多层网络上练习Skip-Gram。

图神经网络由于其在边际上的传达机制，在获取部分连通性形式方面具有很大的潜力

但是，最广为人知的是，只有两种面向人物的嵌入办法运用了图神经网络

• DRNE[27]运用层归一化LSTMs[10]来处理输入的图形数据。本质上，它是一种捕获结构特性的半手艺办法。DRNE还界说了一个递归聚合进程来学习节点的规矩等价性
• DMER[12]是一种结合图卷积网络[14]和根据特征的自编码器的深度互编码模型，它企图减少对人工进程的依赖。应该指出的是，传达机制或许是一把双刃剑。很多的聚合进程或许会使衔接节点的嵌入愈加滑润，这对面向人物的嵌入是十分晦气的。
• 别的，HONE[23]和GraphWave[2]运用不同的扩散办法来学习节点的部分连通性形式。

很明显，简直一切以上面向人物的嵌入办法都能够归结为两个进程:结构特点提取和映射

虽然提取特点的质量决定了学习表明的有效性，但这些办法由于它们的彼此提取办法而面对许多问题。

3 Method

在本节中，咱们将介绍咱们提出的名为GAS的面向人物的网络嵌入结构的符号和细节

如图2所示，咱们的结构大致分为三个部分

• $(a)$提取结构特征作为辅导信息
• $(b)$运用图自编码器将节点编码为面向人物的嵌入，解码器将这些嵌入重构为特征
• $(c)$根据引导特征和重构特征核算丢失，用于练习图形自编码器

3.1 Notations

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

• V={v1，…，vn}V = \{v_1，…， v_n\}V={v1​，…，vn​}为$n$个节点的调集
• $E\subseteq VV$为节点间边的调集。关于每个节点$v\in V$
• 其邻域调集记为$N(v)=\{u|(v,u)\in E\}$
• A∈RnnA∈R^{nn}A∈Rnn是$G$的邻接矩阵。如果viv_ivi​和vjv_jvj​在$G$中链接，Aij=1A_{ij}= 1Aij​=1，不然Aij=0A_{ij} = 0Aij​=0

(v)=(V(v)，E(v))\varepsilon(v) = (V_{\varepsilon(v)}， E_{\varepsilon(v)})(v)=(V(v)​，E(v)​)表明节点$v$的egonet，其间

• V(v)=N(v)∪{v}V_{\varepsilon(v)}= N (v)∪\{v\}V(v)​=N(v)∪{v}
• E(v)={(u,u′)∣(u,u′)∈E∧u,u′∈V(v)}E_{\varepsilon(v)}= \{(u, u’)| (u, u’) \in E \land u, u’ \in V_{\varepsilon(v)}\}E(v)​={(u,u′)∣(u,u′)∈E∧u,u′∈V(v)​}
• T(v)={{v,u,u′}∣(v,u)，(v,u′)，(u,u′)∈E}T (v) = \{\{v, u, u ‘\}|(v, u)， (v, u ‘)， (u, u ‘)∈E\}T(v)={{v,u,u′}∣(v,u)，(v,u′)，(u,u′)∈E}表明节点$v$参加的三角形调集
• 度矩阵的符号为Dii=∑jAijD_{ii} =∑_j A_{ij}Dii​=∑j​Aij​
• F∈RnmF∈R^{nm}F∈Rnm表明提取的结构特征矩阵，其间每一行FiF_iFi​为节点viv_ivi​的$m$维特征向量

3.2 Feature Extraction

面向人物的网络表明学习是无监督的

当处理手艺结构特征作为输入时，生成的嵌入将合适特征。这种对特性的依赖性太强了，使得嵌入办法不能遍及适用。

为了缓解这些问题，咱们选择运用提取的特征作为辅导信息来练习咱们的面向人物的图主动编码器

---

咱们学习了refex[9]的经历，它递归地聚合了街坊的简略本地和egonet特性。关于每个节点v，提取的local和egonet特征如下:

然后将上述每种特征归一化到规模(0,1)。

咱们构造了首要结构特征矩阵F~\tilde FF~，其间每一行是一个归一化特征组成的7维向量

最后，经过核算每个egonet中节点特征的均值和和来聚合特征，如下所示:

其间

• $◦$是串联操作
• A=A+I\hat A = A + IA=A+I是添加自环的图G的邻接矩阵，其间I∈RnnI∈R^{nn}I∈Rnn是单位矩阵
• Dii=∑jAij\hat D_{ii} =∑_j\hat A_{ij}Dii​=∑j​Aij​

由于一个小的$F$就满足作为辅导信息，所以咱们只对特征进行一次聚合

每个节点的最终特征向量的维数只有m = 21

直观上，特征提取的整个进程简略高效，一起获取了高阶结构信息

3.3 Graph Auto-encoder

咱们的编码器由多层的图卷积网络(GCN)[14]组成

本来的GCN运用的传达规矩如下:

其间

• $l=1,2，\cdot \cdot \cdot ，L$
• H(l−1)∈RndH^{(l−1)}∈R^{nd}H(l−1)∈Rnd，第$l$层的激活矩阵
• (l)∈Rdc^{(l)}∈R^{dc}(l)∈Rdc，第$l$层的可练习权值矩阵
• H(0)H^{(0)}H(0)是A\hat AA或许一个随机初始化的矩阵
• $(\cdot )$为非线性激活函数

如[30]中所评论的，原始GCN的传达规矩本质上是各种均值池化

有时，均值池不能很好区域分部分结构，这对面向人物的使命是丧命的

---

为了更好的区别，咱们在咱们的图卷积编码器中应用以下求和池传达规矩:

• 图卷积网络第$L$层的输出H(L)H^{(L)}H(L)为表明矩阵
• 其第$i$行Hi(L)H^{(L)}_iHi(L)​为节点viv_ivi​的表明

然后咱们运用多层感知器对表明进行解码，如下所示:

式中

• $s=1,2，\cdot \cdot \cdot ，S$
• H(s−1)∈Rnd’\hat H^{(s−1)}∈R^{nd’}H(s−1)∈Rnd’为$s$层中的激活矩阵，
• W(l)∈Rd’c’W^{(l)}∈R^{d’c’}W(l)∈Rd’c’和b(s)b^{(s)}b(s)分别为可练习的权值矩阵和$s$层感知器的误差
• H(0)=H(L)\hat H^{(0)} = H^{(L)}H(0)=H(L)

重构后的结构特征由感知器的最后一层发生:

该模型用于构造丢失函数

3.4 Training

与大多数现有的将手艺结构特征作为输入的办法不同，咱们运用提取的特征作为算法的练习辅导

因而，咱们经过最小化如下界说的制导丢失来使重构的特征矩阵F\hat FF挨近提取的特征矩阵$F$：

式中‖⋅‖fro‖‖_{fro}‖⋅‖fro​表明Frobenius范数

为了添加模型的健壮性，咱们在图卷积主动编码器的参数中引进了以下L2正则化：

最终丢失函数如下：

其间是Lreg的权重

---

如上所述，经过大多数现有办法取得的嵌入契合彼此提取的特征

相反，咱们的办法能够供给包括更丰富的结构信息的嵌入，能够在最小化制导丢失的一起重建提取的特征

3.5 Computational Complexity

4 Experiments

4.1 Datasets

4.2 Model Configuration

咱们采用

• 两层图卷积网络作为编码器和两层多层感知器
• 非线性激活函数()选用sigmoid函数

咱们设置嵌入的维数为128,L2正则化的权重为0.8

模型运用Glorot初始化[4]进行初始化，运用Adam SGD优化器[13]进行练习，学习速率为0.001，最多200个epoch

咱们也运用提早止损的战略，以15个epoch的耐性。

4.3 Baselines

4.4 Role-Oriented Node Classification

4.5 Parameter Sensitivity

4.6 Propagation Rule Analysis

4.7 Visualization

5 Conclusion

本文评论了人物导向网络表明学习的重要性

为了避免现有办法的局限性，咱们引进了一种新的思维：

• 运用人工提取的结构特征作为辅导信息来练习面向人物的图神经网络模型

咱们经过咱们提出的办法GAS实现了这一思维，该办法运用和池传达图卷积层作为编码器，手艺结构特征作为练习的辅导

很多的试验验证了该思维的正确性和算法的有效性。

读后总结

这篇文章之前读过一次

果然 再读一遍 收成仍是有的

细节方面有点没有深究

大体思路有点知道

---

先需求得到两个矩阵$F$和F\hat FF

$F$

运用ReFex直接提取节点的特征向量F~\tilde FF~（7维）

然后再经过下面式子核算得到的特征向量（直接拼接，7 + 7 + 7 = 21维）

F\hat FF

采用AE的方法

• 编码器由两层图神经网络组成（输入直接是图，输出便是嵌入，流程图中的hih_ihi​就是节点$i$的嵌入）
• 解码器是多层感知器组成（输出矩阵F\hat FF）

---

G→hi→FG \rightarrow h_i \rightarrow \hat FG→hi​→F

• hih_ihi​是编码器得到的成果
• 第一个箭头：编码
• 第二个箭头：解码

---

练习这个AE靠总丢失

其间

结语

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

期望对您有一点点协助，如有错误欢迎小伙伴纠正

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