【每日一读】Policy-GNN: Aggregation Optimization for Graph Neural Netw

@[TOC](目录)


# 简介
> Hello！
> 非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
>  
> **ଘ(੭ˊᵕˋ)੭**
> 昵称：海轰
> 标签：程序猿｜C++选手｜学生
> 简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖...已保研
> 学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
>  
> 唯有努力💪
> 
> **【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）**

# 论文简介

原文链接：https://dl.acm.org/doi/10.1145/3394486.3403088

会议：KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining **（CCF A类）**

代码：https://github.com/datamllab/Policy-GNN

年度：2020年8月20日

# ABSTRACT
图形数据在许多现实世界的应用程序中无处不在

最近，图神经网络 (GNN) 受到越来越多的关注，它旨在通过使用可堆叠的网络模块聚合来自邻居的信息来对局部图结构进行建模并捕获层次模式

由于观察到**不同的节点通常需要不同的聚合迭代来完全捕获结构信息**，因此在本文中，我们建议**对不同节点的不同聚合迭代进行显式采样**，以提高 GNN 的性能

给定复杂的图形和稀疏的特征，为每个节点开发有效的聚合策略是一项具有挑战性的任务

此外，由于我们需要将采样节点馈送到不同数量的网络层，因此推导出一个有效的算法并不简单

为了应对上述挑战，我们提出了 Policy-GNN，这是一个元策略框架，将 GNN 的采样过程和消息传递建模为一个组合学习过程

具体来说，Policy-GNN 使**用元策略来自适应地确定每个节点的聚合数量**

通过利用模型的反馈，使用深度强化学习 (RL) 对元策略进行训练

我们进一步引入参数共享和缓冲机制来提高训练效率
- 三个真实世界基准数据集的实验结果表明，Policy-GNN 显着优于最先进的替代方案，显示了 GNN 聚合优化的前景。

# 1 INTRODUCTION
图数据在许多实际应用中无处不在，例如异常检测 [24]、分子结构生成 [40]、社交网络分析 [16] 和推荐系统 [15]

这些应用程序背后的关键技术之一是图表示学习 [13]，其旨在将图结构数据的基础信息提取为低维向量表示

随着卷积神经网络 [22] 的巨大成功，图卷积网络 (GCNs) [5, 20] 和图神经网络 (GNNs) [1, 2, 37, 41, 44] 获得了很大的发展势头
>对图的局部结构和层次模式进行建模

---

最近，许多研究工作都集中在推动 GNN 的性能边界上

先前关于推进 GNN 的研究主要分为两个方向
- 首先，提出了批量采样[14]和重要性采样[3]等采样策略来提高学习效率。但是，采样策略可能会导致信息丢失，从而提供次优性能
- 其次，引入了一些新的消息传递函数来更好地捕获图结构背后的信息，例如池化层 [7] 和多头注意力 [37]

最近的工作 [11, 31] 专注于深度架构并研究了过度平滑问题，这会导致梯度消失并使顶点的特征具有相同的值 [11]

**解决过度平滑问题并使 GNN 更深入的一种方法是使用跳过连接 [7,17,23]**
> 
> 参考：https://blog.csdn.net/weixin_39653948/article/details/109137230

**尽管在 GNN 中引入跳跃连接可以获得有希望的性能，但这种机制可能不是最佳的，因为它需要手动指定起始层和结束层来构建跳跃连接**

预定义的消息传递架构可能不适用于图中的所有顶点

---

在这项工作中，我们提倡对不同节点的不同聚合迭代进行显式采样，以实现两全其美

具体来说，我们假设不同的节点需要不同的聚合迭代来完全捕获结构信息

为了理解我们的假设，我们应用具有不同层的标准 GCN 对 Cora 数据集进行节点分类

图 1 说明了在 20 个随机采样节点的 100 次运行中正确预测的比率


我们观察到一些节点可以通过更多的 GNN 层实现更好的分类性能

虽然大多数节点在 2 跳聚合中分类良好，但某些节点（例如节点 17 和 20）仅在聚合 4 次迭代时表现良好，而某些节点（例如节点 2）需要更多的聚合迭代

上述观察**促使我们研究如何为每个节点自适应地聚合不同的邻居跳，以提高 GNN 的性能**

---

然而，由于以下挑战，这项任务并非易事
- 首先，现实世界的图通常很复杂，具有多种类型的属性：很难为每个节点确定合适的聚合迭代。例如，在 Cora 数据集等引文网络中，每个节点代表一张具有 1,433 维词袋特征的论文。基于这种稀疏和大量特征的聚合策略很难设计
- 其次，即使我们可以为每个节点定义适当的聚合策略，在这些节点上训练 GNN 仍然具有挑战性，因为我们需要将这些节点馈送到不同数量的网络层中。对采样节点的管理不当会极大地影响算法的训练效率。

---

为了应对上述挑战，在本文中，我们提出了 PolicyGNN，这是一种用于对复杂聚合策略进行建模的元策略框架

受元策略学习最近成功的启发[43]，我们将图表示学习制定为马尔可夫决策过程（MDP），它通过利用模型的反馈来优化元策略

具体来说，MDP 使用元策略迭代地采样当前节点和相应相邻节点的跳数，并通过聚合采样跳内节点的信息来训练 GNN

所提出的 MDP 成功地将采样过程和消息传递集成到一个组合学习过程中

为了解决这个 MDP，我们采用由定制奖励函数增强的深度强化学习算法来训练元策略

此外，我们引入了参数共享和缓冲机制，可以进行批量训练以提高训练效率

---

我们通过深度 Q 学习 (DQN) [30] 和 GCN 来展示我们框架的一个实例，它们分别是强化学习和 GNN 的基本算法

为了验证所提出框架的有效性，我们针对各种最先进的基线对几个真实世界的数据集进行了广泛的实验，包括网络嵌入方法、静态 GNN 方法和图神经架构搜索方法

实验结果表明，所提出的框架在三个基准数据集上实现了最先进的性能，即 Cora、CiteSeer 和 PubMed

主要贡献总结如下：
- 我们发现向节点引入不同的聚合可以显着提高 GNN 的性能。
- 我们将 GNN 训练问题表述为马尔可夫决策过程，并提出了一个元策略框架，该框架使用强化学习来自适应地优化聚合策略。
- 我们开发了一个基于 DQN 和 GCN 的框架的实际实例，具有定制的奖励功能。在三个真实世界的基准数据集上，所提出的算法显着优于我们所知道的所有最先进的替代方案。

# 2 PRELIMINARIES
在本节中，我们首先定义聚合优化问题。然后我们介绍了图神经网络、马尔可夫决策过程和深度强化学习的背景。

# 3 METHODOLOGY

# 5 RELATED WORK
本节介绍以往关于图神经网络、图神经架构搜索和元策略学习的研究。

`图神经网络`。 神经网络模型 [34] 已被研究多年，以将图的信息保存到向量空间中。 基于图谱理论，已经提出了图卷积网络来捕获图结构数据的接近度信息 [5, 20]。 为了处理大规模的现实世界数据，基于空间的 GNN 被提出了一种消息传递策略，称为图卷积。 具体来说，图卷积通过聚合其邻居的特征来学习节点表示。 通过𝑘次图卷积，将节点的𝑘-hop邻域信息编码为特征向量。最近，已经提出了各种策略来推进 GNN 中的消息传递，包括高级聚合函数 [14]、节点注意机制 [37]、图结构池 [7]、邻域采样方法 [3]、图循环网络 [18] ] 和多通道 GNN [46]。在这项工作中，我们探索了一个正交方向，该方向学习一个元策略来为图中的每个节点定制消息传递策略。

`图神经架构搜索`。给定特定任务，神经架构搜索 (NAS) 旨在发现最佳模型，而无需从预定义的架构搜索空间 [19, 25, 26, 33, 47] 进行费力的神经架构调整。随着 NAS 的成功，自动化的概念已扩展到 GNN 架构 [9, 45]。搜索空间由 GNN 架构的所有可能变体组成。然后设计一个控制器来探索搜索空间以找到最佳模型并最大化性能。 Policy-GNN 中元策略的概念类似于 NAS 中的控制器。我们的元策略不是专注于搜索神经架构的空间，而是学习为每个节点采样最佳的聚合迭代，并在现实世界的基准测试中获得更好的性能。

`元策略学习`。深度强化学习 (RL) 的最新进展已显示出其广泛的适用性，例如游戏 [28, 42] 和神经架构搜索 [47]。一般来说，深度神经网络的策略用于从观察中提取特征并做出相应的决策。元策略学习 [43] 的想法是通过利用模型的反馈来优化性能来训练元策略。元策略学习已被广泛研究以生成和重放经验数据 [43]，学习提高智能体样本效率的双重策略 [21]，并通过学习奖励和折扣因子 [39] 来最大化性能。然而，这些研究的成功仅限于模拟环境，这与现实世界的应用相去甚远。我们的工作证明了元策略学习在 GNN 的背景下在现实世界场景中的有效性。

# 6 CONCLUSIONS AND FUTURE WORK
我们提出了 Policy-GNN，这是一个元策略框架，它**自适应地学习聚合策略，以对不同节点的聚合的不同迭代进行采样**

 Policy-GNN 将图表示学习问题制定为马尔可夫决策过程，并采用具有定制奖励函数的深度强化学习来训练元策略

为了加速学习过程，我们设计了一种缓冲机制来启用批量训练并引入参数共享以降低训练成本

在三个真实世界基准数据集上进行的实验表明，Policy-GNN 在所有数据集上显着且始终优于最先进的替代方案

我们的工作展示了学习 GNN 聚合策略的前景，这可能为未来研究通过自适应采样和聚合提高 GNN 的性能开辟了一条新途径

Policy-GNN 的一个已知限制是训练效率

为了学习一个有效的元策略，我们需要数百次训练迭代，这对于大图可能是有问题的

未来，我们对为大图开发更具可扩展性和更高效的元策略算法的可能性特别感兴趣

此外，我们将探索不同的深度强化学习算法和更高级的聚合函数，以进一步提高性能

另一个有趣的方向是将我们的元策略与神经架构搜索结合起来，共同优化神经架构和聚合策略

# 读后总结

mark一下
- **尽管在 GNN 中引入跳跃连接可以获得有希望的性能，但这种机制可能不是最佳的，因为它需要手动指定起始层和结束层来构建跳跃连接**
- 自适应地学习聚合策略，以`对不同节点的聚合的不同迭代进行采样`

# 结语

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

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