目录
- 前言
- 简介
- 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语言知识编程，然后转到计算机专业，获得国家奖学金，有幸获得一些国家奖、省级奖…已保研。 学习经验：扎实基础 多做笔记 多敲代码 多思考 学好英语！ 只有努力，只有努力，只有努力，只有努力，只有努力，只有努力，只有努力，只有努力，只有努力？
知其然 知其所以然！
本文仅记录您感兴趣的内容
简介
原文链接：https://ieeexplore.ieee.org/abstract/document/9517031
期刊：IEEE Transactions on Systems, Man, and Cybernetics: Systems
代码：https://github.com/cspjiao/RDAA
年度：2021/06/29
Abstract
近年来，网络嵌入(network embedding, NE)它是复杂网络研究的热点，致力于各种任务
几乎所有的网络模型和方法都是基于网络的局部相似性、高阶相似性或整体相似性，很少有研究关注角色发现或结构相似性，这对传播动力学和网络理论具有重要意义
同时，:
- 无法建模每个节点与相邻节点之间的依赖关系
- 不能捕获有助于角色发现的有效节点特征
依据role发现的NE方法的一些缺陷
这使得这些方法在角色发现任务时失效
为了解决NE我们对角色发现或结构相似性提出了统一的深度学习框架RDAA
- 该框架能有效地表示节点的特征
- 用深度自编码器引导角色找到NE有益
- 同时使用Attention机制建模局部链接
另外，我们精心设计了一种绑定技术，将两者结合起来，统一优化框架
我们做了不同的实验，包括可视化、角色分类、角色发现和流行NE该方法在相邻性和结构相似性方面的运行时间
RDAA在所有数据集中都有更好的性能和良好的权衡
I. INTRODUCTION
社交媒体的爆炸性增长促进了社交网络分析的快速发展
由于现实世界中大规模网络的稀疏性，如何有效地表达节点信息对许多网络任务[1]至关重要
网络嵌入(Network embedding, NE)它是近年来表达和分析大规模网络最流行的工具。其目的是将网络节点嵌入低维空间，保留网络拓扑[2]的重要特征
然后，学留结构信息的节点表示可以应用于网络分析的下游任务，如节点分类[3]、团体检测[4]、推荐系统[5]、链路预测[6]
针对NE提出了多种方法和模型，一般可分为随机步行、矩阵分解、统计网络模型和机器学习
- DeepWalk[8]首先，我们致力于学习基于经典图片随机步行的节点嵌入，并通过分层Softmax优化，然后为不同类型的随机行走[6]开发其他方法
奇异值分解(SVD)和非负矩阵分解因其对低秩特征的最优性而在NE它得到了广泛的应用
此外，基于神经网络，特别是深度学习NE方法也不断提出[1]，[9]。
- SDNE[10]节点可以基于自编码器联合嵌入一阶和二阶
- DVNE基于变分的自编码器可以集成[11](VAEs)维持网络结构的不确定性
- GraphSAGE[12]节点特征信息可以有效地生成节点，嵌入以前从未见过的数据
- [13]提出了分析嵌入图神经网络的理论框架。提出了更高效的鲁棒优化[14]和社区增强[15]方法
- 在[16]-[18]中可以看到更详细的评论
本质上，这些作品大多试图保留局部(第一和第二相似性)或组合的网络结构[19]或高阶(motif与群落相似或全球相邻性
然而，在各种现实世界的网络中，在某些情况下
，这也被称为结构相似性问题
我们的目标是学习嵌入分配节点角色的嵌入
如图1所示，尽管节点 f f f和节点 d d d在网络中距离较远，但它们的作用是相同的，因为它们都被红节点包围
这通常对应于复杂网络中角色发现或结构相似的内涵，可用于在线社交网络(如Facebook、Twitter、Yelp)在线广告活动在传播、网络理论和网络分析[16]中具有重要意义
但是，考虑一下，所有这些方法都无一例外地失败了
具体来说，角色发现或结构相似性[21]通常表示络中搜索一组连接模式相似的节点
原则上，确实有一些不同类型的传统方法可以解决这个问题[22]，例如，基于图的方法、基于特性的方法和混合方法
在所有这些方法中，角色发现最重要的步骤是从复杂网络中提取节点特征，或者根据网络的邻接矩阵计算相似度
然而，这些传统的基于特征工程[23]或矩阵分解[24]的角色发现工作，无法处理大规模的社交网络
在NE化趋势下，由于该问题与以往的节点嵌入有本质区别，如何学习角色发现引导的网元仍然是一个开放而重要的问题[25]。
近年来，在[20]和[26]-[29]中已经开发出了一些专注于角色发现或结构相似性的学习嵌入方案
然而，对于角色或结构相似性的节点嵌入仍然面临如下许多挑战
- [30]。如图1所示，相邻节点结构相似的节点，如节点d和节点f，在网络中通常相距较远。
- 。 如图1所示，节点 f f f和节点 s s s具有相同的角色，因为它们都连接到多个红色节点，而节点f的角色独立于节点e和节点u的角色。然而，目前的工作如DRNE[20]忽略了每个节点与其邻居节点之间不同的依赖关系。。
- 从网络中提取隐含的角色特征来指导基于角色的NE是一项有趣但困难的工作。虽然node2vec[6]可以通过结构相似性[31]在一定程度上提取角色特征，但利用宽度优先搜索获得局部特征来发现角色是不够的。有必要研究一种角色发现引导的网元方法来解决这些挑战。
一方面，，不仅通过递归学习步骤驱动递归相似性21，而且自然聚合其嵌入的邻居节点(挑战2)
另一方面，
尽管这两个部分对角色发现至关重要，但要保持每个节点及其邻居和特性之间的不同依赖关系是不现实的，而且效率低下
然后，最重要的问题是如何通过统一的模型学习嵌入角色注意和角色特征矩阵的节点，使嵌入的节点更有效地揭示角色特征
为了解决上述挑战，我们设计了一个统一的深度学习框架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
给定一个无向无权网络 G = ( V , E ) G = (V, E) G=(V,E)
- V V V为节点集
- E ⊆ V × V E⊆V × V E⊆V×V为边集
- 节点 i i i的邻居为 N ( i ) = { j ∣ ( i , j ) ∈ E } N_{(i)} = \{j|(i, j)∈E\} N(i)={ j∣(i,j)∈E}
- A A A表示邻接矩阵，其中 A i , j = 1 A_{i,j} = 1 Ai,j=1表示 { ( i , j ) ∈ E } \{(i, j)∈E\} { (i,j)∈E}，否则表示 A i , j = 0 A_{i,j} = 0 Ai,j=0
通常表示网元学习一个映射 F : V → R d F: V→R^d F:V→Rd
- 其中 d < < ∣ V ∣ d << |V| d<<∣V∣为嵌入维数
- n = ∣ V ∣ n = |V| n=∣V∣为节点数
给定网络G的拓扑信息(如邻接矩阵)，，使这些向量能够揭示网络的统计结构特征
角色发现或基于结构相似性的NE通常可以定义为
设 r ( i ) r(i) r(i)是节点 i i i的角色，角色发现的NE应用自己学习嵌入向量 z j z_j zj，使
- 式中， S ( ⋅ ) S(·) S(⋅)是衡量嵌入 z i z_i zi和 z j z_j zj相似度的函数
- 、
（1）式的意思大概是：如果节点 i i i和节点 j j j的角色一样，那么其嵌入向量相似度应该接近1
根据上述定义和问题公式，给定任意网络 G G G，我们的目的是
- 基于边的集合学习每个节点的嵌入向量
- 同时，我们需要保持节点 i i i和 j j j在嵌入空间中相同角色或相同结构的相似性，即 z i z_i zi和 z j z_j zj应该接近
需要强调的是，我们的问题不同于经典的NE问题
- 在经典的NE问题中，节点嵌入几乎只在它们接近时才进行
- 基于这些嵌入，，例如k-means聚类
B. Overall Framework
我们的框架RDAA的说明如图2所示
- 首先，我们采用递归特征提取算法提取能够揭示角色信息的高维特征
- 然后，我们利用自动编码器框架将网络编码到一个潜在空间，并设计一种注意机制来有效地
- 最后，通过设计一种巧妙的技术，，获得嵌入。事实上，我们从两个方面来利用网络拓扑的信息，即
- (1)特征提取
- (2)注意机制
C. Role Feature Extraction
由于具有相同角色的节点通常不相邻，即在网络中距离较远，因此邻接矩阵(一种描述网络拓扑结构的高维特征)在提取基于角色的特征时非常薄弱
因此，我们引入了一种提取维数小于 ∣ V ∣ |V| ∣V∣的高维结构特征的方法
在众多的特征提取方法中，我们采用了[23]中描述的递归特征提取方法(ReFex)
- 该方法以递归的方式聚合局部特征和邻域特征，获取全局结构信息，从而可以提取足够的角色特征
- 具体来说，对于每个节点，它首先通过计算其相邻边和节点egonet中的边来生成主特征
- 然后，通过在egonet上应用一些简单的聚合算子，如求和和均值，递归地对主要特征进行聚合
- 显然，随着递归次数的增加，可以获得更高阶的结构特性
ReFex算法如下：
D. Encoder–Decoder
虽然RDAA模型在特征提取方面很灵活，但为了将各种特征嵌入到低维向量空间中，并集成下一节描述的角色注意机制
我们在这里
编码器由组成，它将特征编码为低维表示。具体来说，给定feature x i x_i xi，每层的隐藏表示可以表示为
其中
- x i x_i xi表示节点 i i i的高维特征
利用编码器的一部分，我们可以生成节点 i i i的嵌入 z i = h i ( K ) z_i = h^{(K)}_i zi=hi(K)，然后将编码器的过程颠倒如下，得到重构数据 x ^ i \hat x_i x^i
其中节点嵌入 z i z_i zi为方便记为 z i = h ^ i ( K ) z_i = \hat h^{(K)}_i zi=h^i(K)
编码器-解码器结构的
重构的损失函数表示为:
最小化重构损失可以使节点表示平滑地捕获数据流形，并保持节点在低维空间中的角色特征
但是考虑到如果特征中有大量的零元素，我们的模型会很容易重构 x i x_i xi中的零元素，这是不可取的
为了解决这一问题，我们引入系数对重构损失函数进行修正如下:
- ⊙ \odot ⊙表示 Hadamard product
- 设 x i l x_{il} xil表示 x i x_i xi中的第 l l l个元素， β i l β_{il} βil表示 β i β_i βi中的第 l l l个元素，则如果 x i l = 0 ， β i l = 1 x_{il} =0， β_{il} = 1 xil=0，βil=1，否则 β i l = β > 1 β_{il} = β > 1 βil=β>1，其中 β β β是控制非零元素贡献的超参数
- 事实上，通过为每个节点 i i i引入 β i β_i βi，我们可以捕捉到不同节点的不同重要性
E. Role Attention Mechanism
正如在第1节中提到的，我们通过角色发现或结构相似性来定义NE
根据定义2，通过，以的方式约束节点嵌入
使用聚类的方式
然后，我们可以根据约束设计一个损失函数如下: