持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第12天，ieeexplore.ieee.org/document/89…

期刊：IEEE Transactions on Knowledge and Data Engineering （CCF A类）

年度：2021年6月1日（发表日期）

Abstract

网络表示学习 (NRL) 最基本的任务是节点分类，它需要一种算法将节点映射到向量并使用机器学习模型来预测节点的标签

最近，许多基于邻域聚合的方法在这项任务中取得了辉煌的成果

然而，邻域聚合的递归扩展给深度模型带来了可扩展性和效率问题

现有方法仅限于浅层架构，无法捕捉网络中的高阶接近度

在本文中，我们提出了深度聚合网络（DAN）

• DAN 使用逐层贪婪优化策略，将几个顺序训练的基础模型堆叠起来形成最终的深度模型
• 高阶邻域聚合以动态规划的方式执行，从而消除了邻域聚合的递归性质
• 还提出了反向随机游走，并结合经典的随机游走制定了一种新颖的采样策略，使 DAN 可以灵活地适应与社区或结构角色相关的不同任务

DAN 比以前基于邻域聚合的方法更有效，尤其是当它旨在处理具有密集连接的大规模网络时

在合成网络和真实世界网络上进行了广泛的实验，以经验证明所提出方法的有效性和效率。

1 I NTRODUCTION

网络分析最基本的任务之一是节点分类，它需要预测节点的标签 [1]。随着大规模网络数据集的可用性，利用机器学习技术在涉及大型数据集的许多问题上取得了巨大成功是很直观的 [2]。 NRL 是一种将节点嵌入低维向量空间的有效方法，在该空间中可以细化和保留有用的特征 [3]。 NRL 生成的低维节点嵌入可以直接馈送到常见的机器学习分类器中，这导致了重大进展 [4]。

NRL 的早期工作主要基于矩阵分解技术 [5]、[6]、[7]、[8]。这些方法中的大多数都存在可扩展性问题，因为它们需要将网络的矩阵表示形式馈送到内存中。深度协作嵌入 (DCE) 使用矩阵分解框架进行协作社交图像理解，由于 DCE 将图像特征直接映射到嵌入空间，端到端学习使得 DCE 在推理阶段具有可扩展性 [8]。基于随机游走的方法 (RWBM) 使用 word2vec 模型 [9]、[10] 通过比较随机游走生成的路径到句子和节点到词 [1]、[11] 的路径来嵌入节点。由于路径可以在内存中增量输入，因此 RWBM 具有出色的可扩展性。然而，RWBMs 不能直接为训练阶段看不见的节点生成嵌入，这称为转导。实际上，网络总是随着时间的推移而发展[7]，[12]。如果添加或删除了一些节点，RWBM 需要额外的优化轮次才能生成新的嵌入。

基于邻域聚合的方法 [13] (NABM) 是最近相对成功的 NRL 算法。 NABM 通过聚合其本地邻居的特征为节点生成嵌入。 NABMs 的架构可以用以下表达式来概括：

其中xk i 和a kð:Þ 分别表示节点vi 的特征和第k 层的聚合函数。 Nðv iÞ 表示节点 v i 的邻居集合。设 x K i 为最终的输出嵌入，K 也称为模型深度。 x0i 通常是原始节点的特征。

由于聚合函数相对独立于特定的网络结构，NABMs 有可能为在训练阶段看不见的节点生成嵌入，这被称为归纳 [14]。然而，表达式（1）实际上是一个递归公式。以节点vi 为例，计算k ð:Þ over vi 需要计算k 1ð:Þ 超过vi 的邻居。并且 k 1ð:Þ 的计算也依赖于 k 2ð:Þ 对 vi 的邻居的邻居的计算。最后，k ð:Þ 的计算涉及 v i 的 K-hops 邻居，其数量与 K 成指数关系。NABMs 的时间和空间复杂度都随着 K 的增长呈指数增长。

递归性质将大多数 NABM 限制在浅层架构或可扩展性差的全批处理设置 [15]。在本文中，我们提供了一种新颖的逐层贪心优化策略，其中深度邻域聚合模型由一组浅基模型堆叠。浅基模型仅聚合节点直接邻居的特征，即K 1/4 1。这些基模型是顺序训练的，之前训练的基模型用于生成节点嵌入，这些嵌入被存储并用作新节点的特征用于下一个基本模型。通过这种优化策略，NABM 中的递归特性被消除，NABM 可以在线性时间内加深到更深的深度，同时保持可扩展性。

许多现实世界的网络都有密集的连接，采样技术可以进一步提高 NABMs [14] 的效率。受均匀采样邻居的图样本和聚合（GraSAGE）[14] 的启发，我们将随机游走引入 NABM 进行采样。具体来说，我们根据随机游走的转移概率为节点采样固定数量的邻居，这比均匀采样更复杂。为此，通过考虑现实世界网络的统计特性，提出了一种灵活的一阶随机游走，称为反向随机游走。

通过逐层贪心优化策略和反向随机游走进行采样，本文提出了深度聚合网络（DAN）。与以前的 NABM 相比，DAN 具有更少的内存空间需求和运行时间开销，同时具有更深的模型深度。 在 K 1/4 2 的情况下，与 GraSAGE 相比，DAN 可以节省大约 10 倍的内存空间和一半的运行时间，这是在不牺牲精度的情况下实现的。综上所述，本文的贡献如下：

• 提出了一种新颖的逐层贪心优化策略来消除 NABM 中的递归性质。通过这种策略，NABM 可以在线性时间内加深到更深的深度，同时保持可扩展性。
• 我们基于复杂网络的层次结构来解释节点的社区和结构角色属性。基于解释，我们提出了反向随机游走。
• 反向随机游走与经典随机游走相结合，形成一种新颖的采样策略，使 DAN 能够适应具有不同特征的任务。

2 RELATED W ORKS AND MOTIVATIONS

我们的工作主要受到 NABM 和 RWBM 的启发。在下文中，我们将简要概述这些领域。

2.1 Primary Definition

图表示为 G 1/4 ðV； EÞ，其中 V 是节点集，E 是边集。我们使用 jV j 和 jEj 分别表示节点和边的数量。 v i 2 V 是第 i 个节点，e i;j 2 如果在 v i 和 v j 之间存在边，则 E 是边

2.2 Neighborhood Aggregation Based Methods

NABMs 与谱卷积神经网络（SCNNs [16] 和 Chebyshev 网络 (ChebyNet) [17] 有关。SCNNs 利用图拉普拉斯算子的特征向量来定义节点特征的傅里叶变换和傅里叶逆变换。然后是谱卷积运算源自卷积定理 [16]。原始 SCNN 计算量很大，因为特征分解的时间复杂度为 OðjV j3Þ。ChebyNet 通过 Chebyshev 多项式逼近谱卷积，以避免计算特征分解。

图卷积网络 (GCN) 是 ChebyNet [15]、[18] 的粗略近似，可以看作是聚合了局部邻居的特征。 GCN 可以被认为是 WeisfeilerLehman (WL) [19] 算法 [15] 的一个实例，用于同构测试。有许多中介可以遵循 GCN 的思想，例如关系 GCN (RGCN) [20]、列网络 [21]、GraSAGE 和图注意力网络 (GAT) [22]。

GCN 一次嵌入所有节点，这是不可扩展的。为了克服这个问题，GraSAGE 在 NABM 中引入了采样和小批量机制。对固定数量的邻居进行采样可以稀疏网络并受益于优化的矩阵计算。 Mini-batch 机制使 GraSAGE 在大规模网络上具有可扩展性。

有许多工作专注于提高 NABM 的效率，例如 FastGCN [23]、StoGCN [24] 和 LGCN [25]。然而，它们都不能有效地消除邻域聚合的递归性质。

如式（1）所示，深层聚合函数所涉及的节点数，也就是通常所说的感受野，随深度呈指数增长。时间和空间复杂度分别为 OðdKþ1Þ 和 Oðd KÞ。其中 d 是网络的平均程度，Kis 是模型深度。实际上，NABMs的深度通常设置为K=2。当K>2时，效率问题会突出。换句话说，很难处理深层架构。如何以有效的方式增加 NABM 的模型深度仍然是一个挑战。

还值得注意的是，现有的 NABM 依赖于代表性节点的功能，并假设这些功能是完整且可用的。但对于大规模网络，很难为下游的 NABM 设计代表节点的特征。增加模型深度允许 NABMs 使用更多的网络拓扑信息，这是我们工作的动机之一。

2.3 Random Walk Based Methods

在 RWBMs 中，首先给每个节点一个初始的可训练嵌入，然后在网络上执行随机游走以生成一组固定长度的路径。这些生成路径的似然概率可以通过节点的嵌入来建模。通过迭代地最大化生成路径的似然概率来获得最终的嵌入。

DeepWalk [11] 和 node2vec [1] 是 RWBM 的两个代表。 DeepWalk 使用经典的随机游走，而 node2vec 开发了一种有偏的二阶随机游走，以在深度优先搜索 (DFS) 和广度优先搜索 (BFS) [1] 之间进行权衡。

RWBM 在 NRL 中的成功说明了随机游走的结构意识，这激发了我们将随机游走引入 NABM。对于随机游走，节点之间存在转移概率，我们可以通过转移概率为中心节点采样固定数量的邻居。

node2vec 中的二阶随机游走效率低下，因为二阶随机游走的时间复杂度为 OðjV jd2Þ。在本文中，我们提出了一种新颖的一阶随机游走进行采样。

3 THE R EVERSE RANDOM W ALK

6 CONCLUSION AND DISCUSSION

在本文中，我们提出了用于节点分类的深度聚合网络（DAN）。在 DAN 中，引入了逐层贪心优化策略和反向随机游走。逐层贪婪优化策略带来了效率和性能的显着提升。反向随机游走为适应不同类型的节点分类任务提供了选择。 DAN 可与最先进的算法相媲美。 DAN 的时间复杂度与网络规模和模型深度呈线性关系，对于大规模密集连接的网络具有可扩展性。我们论文中介绍的技术可以应用于大多数 NABM。然而，当前的 DAN 主要是为节点分类任务而设计的。将 DAN 扩展到其他 NRL 任务是很有价值的，例如链接预测、推荐和图分类。普通的邻域聚合函数可能不适用于深度模型。如何设计更复杂的聚合函数是一个有趣的方向。 DAN 产生大量中间隐藏节点表示，这可能对节点的多级层次表示有用。

读后总结

mark！ 值得后面再深读一遍！

结语

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

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