目录
Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。
| 论文概况 | 详细 |
|---|---|
| 标题 | 《Cooperative Graph Neural Networks》 |
| 作者 | Ben Finkelshtein, Xingyue Huang, Michael Bronstein, ˙Ismail ˙Ilkan Ceylan |
| 发表会议 | International Conference on Machine Learning(ICML) |
| 发表年份 | 2024 |
| 会议等级 | CCF-A |
| 论文代码 | https://github.com/benfinkelshtein/CoGNN |
作者单位：
- Department of Computer Science, University of Oxford.
研究动机
图神经网络 GNN 是一类用于学习图结构数据的架构，在各种图机器学习任务中的表现出高效的预测性能。绝大多数 GNN 通过消息传递机制实现，其基本思想是基于节点邻居的消息流聚合来更新每个节点的表示。但是消息传递机制具有与图上的信息流相关的限制，主要是远程依赖关系问题：为了从 k 跳邻居处接收信息，网络需要至少 k 层，这通常意味着节点的接受域呈指数增长。越来越多的信息需要被压缩到固定大小的节点嵌入中，可能导致信息丢失，称为过度压缩问题。另一个限制是过度平滑，也就是随着层数的增加，节点特征会变得越来越相似。
本文的目标是通过允许每个节点决定如何将信息从其邻居传播或传播到邻居，从而实现更灵活的信息流。一个示例如下图所示，其中顶部行展示了跨三层相对于节点 u 的信息流，底部行展示了跨三层相对于节点 v 的信息流。节点 u 监听第一层的所有邻居，第二层只监听 v，最后一层监听 s 和 r。同时节点 v 在前两层监听节点 w，在最后一层监听节点 u。要实现这样的效果，每个节点能够决定是否在每一层监听特定节点：动态和异步消息传递方案，这显然不属于标准消息传递。
文章贡献
本文提出了一种新的 GNN 架构，称为协作图神经网络 Co-GNN。在 Co-GNN 网络中，图中的每个节点都被视为可以执行 STANDARD(S)、LISTEN(L)、BROADCAST(B)、ISOLATE(I) 动作之一的参与者。Co-GNN 结构由两个联合训练的“合作”消息传递神经网络组成，分别是用于解决给定任务的环境网络 η 和一个用于选择最佳行动的行动网络 π。本文对新的消息传递方案进行了理论分析，并通过对合成数据和现实世界数据的对 Co-GNN 的性能进行了验证。
预备知识
图神经网络
考虑无向属性图 G=(V,E,X)，消息传递神经网络 MPNN 基于自身状态及其邻居状态 Nv，在 0≤l≤L−1 次迭代中，更新每个节点 v 的表示 h(0)v=xv 为：
Gumbel-softmax 估计器
依靠动作网络来预测图中节点的分类动作是不可微的，解决这个问题的一个方法是使用 Gumbel-softmax 估计器。它提供了离散动作采样的可微连续逼近，考虑一个有限的动作集合 Ω，需要关注的是学习 Ω 上的分类分布，它可以用概率向量 p∈R|Ω| 表示。用 p(a) 表示动作 a∈Ω 的概率，Gumbel-softmax 借助 gumbel 分布向量 g∈R|Ω| 来估计分类分布 p∈R|Ω|。
本文方法
节点更新方式
Co-GNN 将每个节点视为一个玩家，在每一层中可以采取以下行动：
| Actions | 说明 |
|---|---|
| STANDARD(S) | 向动作为监听的邻居广播，并监听邻居的广播信息 |
| LISTEN(L) | 监听邻居的广播信息 |
| BROADCAST(B) | 向动作为监听的邻居广播本节点的信息 |
| ISOLATE(I) | 既不监听也不广播 |
当所有节点执行 STANDARD 操作时，整体为标准的消息传递机制。当所有的节点执行 ISOLATE 操作时，对应于从图中删除所有的边的情况，这意味着节点仅依照其特征进行预测。这些操作之间的相互作用以及动态更新的能力使整个方法更加丰富，并允许将输入图与计算图解耦，并将方向性合并到消息传递中。
Co-GNN 结构
Co-GNN 将图中的每个节点视为多人游戏中的玩家，每个节点都可以决定如何在其邻居之间传播信息或向其邻居传播信息。节点的更新过程分为两个阶段:
- 第一阶段：每个节点根据其当前状态和邻近节点的状态，从一组动作中选择一个动作；
- 第二阶段：每个节点状态根据其当前状态和相邻节点子集的状态（由第一阶段中的操作确定）进行更新。
CO-GNN(π,η) 的架构由两个协作 GNN 给出，Co-GNN 层次主要目的是更新每个节点 v 的表示 h(l)v。
| GNN | 功能 |
|---|---|
| π | 选择最佳动作的动作网络 |
| η | 更新节点表示的环境网络 |
首先通过动作网络 π 预测每个节点的动作，每个节点 v 在给定其状态及其邻居 Nv 的状态下，v 可以采取的动作 {S,L,B,I} 的概率分布 p(l)v∈R4 使用如下公式表示：
然后对于每个节点 v，使用直通式 Gumbel Softmax 对一个动作进行采样 a(l)v~p(l)v，根据采样的动作通过环境网络 η 更新每个节点的状态，如下公式所示。该步骤是一个单层更新，通过堆叠 L≥1 层，得到每个节点 v 的表示 h(l)v。
CO-GNN(π,η) 结构可以在有向图上运行，并使用任何 GNN 结构作为动作网络 π 和环境网络 η。为了评估这种新的消息传递范式的优点，本文使用了如 SUMGNNs、MEANGNNs、GCN、GIN、GAT 所示的相对简单的架构，它们分别用 ∑、µ、∗、λ、α 表示，例如 CO-GNN(Σ,µ) 表示 CO-GNN 使用 SUMGNN 作为动作网络，MEANGNN 作为环境网络。
理论分析
Co-GNN 的特点
- 任务相关的：标准消息传递基于节点的邻居更新节点，这是与任务无关的范式。通过允许每个节点只听取来自“相关”邻居的信息，CO-GNN 可以确定最适合目标任务的计算图。例如，如果任务只需要从邻居那里获得一定程度的信息，则可以通过动作网络实现只监听部分节点。
- 定向：相当于 Co-GNN 具有对输入图进行重构的能力，一条边可以被丢弃也可以保持无向，或者一条边可以变成定向的。此时消息传递可以被看作是操作在每一层的动作选择所引起的潜在不同的有向图上，如下图所示。
形式上给定一个图 G=(V,E)，使用 G(l)=(V,E(l)) 表示由在第 l 层选择的动作所引起的有向计算图，其中 E(l) 是第 l 层的有向边集。可以将更新方式改写为如下公式：
- 动态性：Co-GNN 中的每个节点与“相关”邻居交互，它不是在固定的计算图上运行，而是在学习的计算图上运行，这是跨层动态的。
- 基于特征和结构：标准消息传递由图的结构决定，具有相同邻域的两个节点获得相同的聚合消息。在 Co-GNN 的设置中并不一定如此，因为动作网络可以为两个具有不同节点特征的节点学习不同的动作，允许不同的节点发送不同的消息。
- 异步：标准消息传递同步更新所有节点，这并不总是最佳的，Co-GNN 支持跨节点的异步更新。
- 条件聚合：Co-GNN 的动作网络可以看作是一个前瞻函数，环境网络在第 l 层的聚集是由行动网络的 k+l 层表示决定的，这种的聚集机制以前瞻性能力为条件。
- 正交注意力：注意力机制可以权衡不同邻居的贡献，但注意力有一定的局限性，例如加权平均聚合不能计算节点度。Co-GNN 的条件聚合机制超出了基于注意力的架构的能力，Co-GNN 的贡献与基于注意力的架构是正交的。
- 减轻过度平滑：当顶点的邻居特征的信息不够丰富时，Co-GNN 的动作网络可以为其设置动作 ISOLATE，这种机制可以减轻过度平滑。
- 高效：虽然本方法的顶点更新机制更复杂，但本文方法在运行时方面是高效的。同时 Co-GNN 也是参数高效的，其结构跨层共享相同的行动网络，参数数量与其基线模型相当。
Co-GNN 的表达能力
Co-GNN 的环境和动作网络由标准 MPNN 参数化，针对 CO-GNN 架构的表达能力的明显问题：CO-GNN 在区分图方面也受 1-WL 的限制吗？本文给出了一个理论分析的结论。
该结论的解释是：Co-GNN 结构在每一层和每个节点 u 上学习动作的概率分布，这些分布对于两个同构节点是相同的。然而该过程依赖于这些分布的抽样行为，显然来自相同分布的样本可能不同。这使得 Co-GNN 模型在期望上不变，并且采样过程引入的方差有助于区分 1-WL 不可区分的节点。
远程任务的动态消息传递
远程任务需要在远程节点之间传播信息，因为该任务只能传播相关的特定于任务的信息，因此 Co-GNN 是有效的。Co-GNN 可以通过学习关注连接这两个节点的路径来有效地过滤不相关信息，从而最大化信息流到目标节点。本文通过证明得出了如下结论，这意味着如果一个节点 v 的属性是 k 个远节点的函数，则 Co-GNN 可以近似这个函数。
实验结果
合成数据集实验
合成数据集实验在 ROOTNEIGHBORS 数据集上比较了 Co-GNN 和 MPNN。考虑以下回归任务：给定一棵有根树，预测 6 度的根邻居特征的平均值。该任务要求首先识别出度为 6 的根节点的邻居，然后返回这些节点的平均特征。ROOTNEIGHBORS 由深度为 2 的树和维度为 5 的随机特征组成，生成时确保每个树根至少有一个 6 度邻居。
以 GCN、GAT、SUMGNN、MEANGNN 为基准模型，与 CO-GNN(Σ,Σ)、CO-GNN(µ,µ)、CO-GNN(Σ,α)、CO-GNN(Σ,µ) 进行比较，使用 Adam 作为优化器，使用 MAE 作为评估指标。
实验结果如下表所示，可见所有 MPNN 的性能都很差，GCN、GAT 和 MEANGNN 无法识别节点度，因此无法检测到具有特定度的节点。MEANGNN 的性能明显好于基线，这是因为 MEANGNN 在源节点上使用了不同的变换，而不是将其视为邻居。SUMGNN 可以识别节点度，但在平均节点特征时遇到困难，这产生了与 MEANGNN 相当的 MAE。CO-GNN 具有识别节点度的能力，CO-GNN(Σ,µ) 的效果最好，CO-GNN(Σ,Σ) 也表现良好，可见该模型精确地学习了诱导所示最优子图的动作。
异亲图节点分类实验
CO-GNN 的优势之一是能够利用特定于任务的信息传播，此处评估了 CO-GNN 在异亲节点分类数据集上的性能。根据 Platonov 等人的 10 次数据分割和方法，在 5 个异亲图上进行了比较，对比方法包括 GCN、GraphSAGE、GAT、GAT-sep、GT、GT-sep。结果如下表所示，可见 CO-GNN 能实现最优秀的结果。与所有基线方法相比，CO-GNN 在所有数据集上的平均精度提高了2.23%，超过了更复杂模型的性能。
优点和创新点
个人认为，本文有如下一些优点和创新点可供参考学习：
基于传统消息传递机制的局限性，本文设计了一种新型的图神经网络架构。该架构通过允许不同的节点采取不同行动的策略，有效应对了现有架构的缺点，是一种新颖的 GNN 网络架构。