1. 论文介绍

论文题目：PANDA: Expanded Width-Aware Message Passing Beyond Rewiring
论文领域：图神经网络，图重连算法
论文发表： ICML 2024
论文代码： https://github.com/jeongwhanchoi/panda
论文背景：

2. 论文摘要

最近在图神经网络（GNN）领域的研究发现了一个关键问题，即“过度挤压”，这是由于图结构中的瓶颈现象导致的，它阻碍了远程信息的传播。以前的工作已经提出了各种各样的图重布线概念，旨在优化图的空间或光谱特性以促进信号传播。然而，这些方法不可避免地会破坏原有的图拓扑结构，从而导致信息流的失真。为了解决这一问题，我们引入了扩展宽度感知（PANDA）消息传递，这是一种新的消息传递范式，其中具有高中心性的节点（一种潜在的过度挤压源）被选择性地扩展宽度以封装来自远地节点的不断增加的信号流入。实验结果表明，该方法优于现有的重布线方法，表明有选择地扩展节点的隐藏状态是解决过度挤压问题的一种有说服力的方法。

3. 相关介绍

3.1 现有研究的缺点

给出了现有研究的图重连算法的失败案例

先前的研究试图通过节点特征的雅可比灵敏度分析的视角来识别与过度挤压相关的各种因素，得到一个理论：增加模型的宽度（即隐藏维度）有助于提高模型的灵敏度，但是扩大模型的宽度以解决过度挤压问题的同时，全局增加隐藏维度会影响整个网络而牺牲了模型的泛化能力。

3.2 主要思想

本文的方法的设计灵感是基于现有图重连算法的局限性和宽度扩展在解决过度挤压问题上的作用。
对于图瓶颈问题，可定义为具有高中心性的节点。具有高中心性的节点表现出枢纽的行为。（因为它们连接到位于图不同部分的一组相对较大的节点，从而经过它们的信息过多），增加这些节点的特征向量宽度，为它们提供了更多空间来处理来自其他节点的信息。

3.3 本文贡献

1，引入了一种扩展宽度消息传递算法，新的消息传递范式，为潜在瓶颈系欸按扩展了宽度。
2，讨论PANDA如何减缓过度挤压问题，克服拓扑瓶颈，在较大的有效电阻下也保持一致的信号传播
3，实验证明了PANDA算法的有效性

3.4 过度挤压问题

通过敏感性分析的视角来对过度挤压问题进行理解，过度挤压影响了三个因素：1）模型中非线性的Lipschitz连续性，2）模型的宽度，3）图的拓扑结构。从$h_v^{{(l)}$到$h_u}$的敏感度，存在着假设节点u和v之前存在着一个路径，

一个小的雅可比范数表明，模型学习到的节点的最终表示不受其相邻输入变化的影响太大，这意味着网络受到过度挤压的影响。当由于信息过度聚合（即通过多层消息传递压缩到一个小的隐藏向量）而导致信息没有在图上充分传播时，通常会出现这种情况。

使用节点中心性指标来将节点识别为图中瓶颈的潜在来源。中间中心性是瓶颈的重要指标，衡量了通过节点的最短路径的数量。一个节点出现在不同节点对的最短路径上的频率越高，越有可能造成瓶颈。

4. 扩展的宽度感知消息传递

可以将节点分为两类：高维和低维。分层基于每个节点的特定中心性，该中心性可以是度，中间性，接近度，PageRank，或负载中心性。中心性值标为$c \in R^n$，按照降序对元素c进行排序，根据排序后的c，选择顶部节点k，得到一个二进制掩码向量，$b \in {0, 1}^n$，有
$$ \mathbf{b}_v = \begin{cases} 1 & \text{if } v \text{ is among the top } k \text{ nodes in } c, \ 0 & \text{otherwise}. \end{cases} $$

定义邻域的子集
基于中心性度量，定义了相邻节点的四个子集。

对于分类为低维的节点

对于高维度的节点

5. 新框架：PANDA消息传递框架

给定任何的MPNN，可以让它在节点的不同宽度下工作。对于标准邻居聚合器可以分为4种不同的聚合器，每个聚合器都应用于相应类型的邻居，从层l到层l+1的最终消息

节点的隐藏向量v是从四个消息中更新的，聚合函数为f，更新函数为g。f⁢是一种线性变换，它将节点特征投影到扩展的维度空间

其中$W_f^{(l)} \in R^{P_{high}Xp}$， 对于更新函数，定义g为一个维度选择器

PANDA中具有低维和高维特征的节点在整个网络层中各自的维空间中进行处理。这意味着在最后一层之前，这些节点保持其不同的维度。

框架的实例化
将PANDA集成到两经典的MPNN上，如GCN和GIN。首先介绍 PANDA-GCN。
低维节点的v的特征为

高维节点的特征为

6. PANDA的性质讨论

6.1 方向性

宽度相等的节点保持无定向，而不同宽度的节点之间的边可以定向。通过确保仅对不同宽度的边的方向性，我们的方法可以比无向方法 更具表现力。

6.2 关系图

PANDA 可以被视为关系图卷积网络 （R-GCN）， 应用于包含两种类型关系的增强关系图。不仅根据邻集的关系进行消息传播，低暗节点和高暗节点也使用不同的权重矩阵。从这个意义上说，我们的 PANDA 类似于 R-GCN。然而，R-GCN 并不是旨在缓解过度挤压的模型。

6.3 计算复杂度

PANDA 增加了中心性计算和四种不同消息传递的复杂性，而不是图重新布线。具体的复杂度取决于使用哪种算法来计算中心性。例如，度中心性的时间复杂度为 $𝒪⁢(|ℰ|)$ ，对于中间中心性，它是 $𝒪⁢(|𝒱|^3)$。

7. 算法讨论

7.1 经验敏感性分析

灵敏度随着宽度p的增加而提高，如图，PANDA 表现出更高的灵敏度，即使在更深的层中也能保持，而其他技术则表现出下降趋势。

7.2 有效电阻的研究

通用 GNN 的信息传播与总有效电阻 $R_{t⁢o⁢t}$ 成反比。

8. 实验设置

有节点分类和图分类任务，实验数据集为TUDataset和LRGB数据集
对图分类任务，对比算法为DIGL，FA，SDRF，FoSR，BOLF，GTR，CT层，

实验结果为

PANDA-GCN 在所有数据集中均优于 R-GCN。与并非旨在减轻过度压扁的 R-GCN 相比，这些结果显示了 PANDA 的功效。

PANDA 的性能根据中心性指标的不同而有何不同。比较了使用不同类型的中心性指标获得的结果。在 IMDB-Binary 中，PageRank 中心性优于其他指标，表明较大的节点宽度可以有效地接收来自有影响力的节点的消息。接近度中心性在蛋白质和协作上显示出最佳性能。

9. 总结

论文引入高于图重连的算法，使用增大图瓶颈处的宽度来传递消息。同时提高整个网路的灵敏度，灵敏度可以说是在另一个维度上的网路连通性。

10. 个人感悟

新的传递方式，当路径变长而导致消息传递挤压的解决思路可以是增大路径的传递量来达到的。新的思路。