1. 论文介绍

论文题目：Probabilistically Rewired Message-Passing Neural Networks
论文领域：图神经网络
论文发表：ICLR 2024
论文代码： https://github.com/chendiqian/PR-MPNN
论文背景：

2. 论文摘要

消息传递图神经网络（MPNN）是处理图结构输入的强大工具。然而，它们在固定的输入图结构上运行，忽略潜在的噪声和丢失的信息。此外，它们的局部聚合机制可能导致捕获相关图结构时出现过度挤压和表达能力有限等问题。这些挑战的现有解决方案主要依赖于启发式方法，通常忽略了底层数据分布。因此，设计用于学习推断与给定预测任务相关的图结构的原则方法仍然是一个公开的挑战。在这项工作中，利用精确和可微的K子集采样的最新进展，我们设计了概率重组消息传递神经网络（PR MPNNs），它学习添加相关边，同时忽略不太有利的边。我们的理论分析首次探索了PR-MPN如何增强表达能力，并确定了它们优于纯随机方法的精确条件。从经验上讲，我们证明了我们的方法有效地缓解了过度挤压和接触不足等问题。此外，在已建立的真实世界数据集上，与传统的MPNN模型和最近的图转换器架构相比，我们的方法显示出竞争性或优越的预测性能。

3. 介绍

总的来说，PRMPNN给出了一条去设计更灵活MPNN的设计思路，使得神经网络对潜在噪声和缺失信息更加有稳定性。

3.1 相关工作

3.1.1 图重连

目前很多的图重连工作，目标是减缓过度挤压问题，方式有两种，一是依赖于启发式图重连方法，二是使用纯随机方法。

3.1.2 Graph transformers

Graph transformer和相类似的全局注意力机制的方法，标志着从局部信息到全局信息提取的一个转变。尽管还没有在实证理论上证明全局的作用，但是相关实验说明了全局机制可以减缓过度挤压的现象。但是所有的transformer都需要去计算一个很大的注意力矩阵所导致的巨大计算消耗。

3.1.3 一维WL算法

1维的WL算法的颜色迭代优化过程是一个图同构问题中的很好学习的启发式学习问题。
在每一次的迭代中，一维WL算法计算的节点颜色取决于邻居节点的颜色。

如果两个图G和H是非同构的，那么在多次迭代后，两个图的颜色节点的数量不一致。

3.2 消息传递图神经网络

当t>0时，每一层的节点的特征为

其中UPD和AGG是不同的参数化函数。

4. PRMPNN 基于概率重连的MPNN

本文的核心算法PR MPNN，是基于最新的进展研究得到来的，离散梯度估计和可控采样技术。整个算法架构为

本文算法引入了基于条件概率的k子集限制的图的边与边依赖。所以，采样给定 的K边邻接矩阵的概率为

原始图G，通过重新增加N个样本，重连为一个新邻接矩阵A。相当于对原始的邻接矩阵使用一个不一样的聚合函数。

4.1 对学习采样

为了能够学习到模型上行和下行的参数，PRMPNN的损失函数为

其中l是点级的损失，可采用交叉熵或者MSE；
对于其中的概率质量函数，需要使用高效的Monte-Carlo采样来完成，同时基于概率来完成对梯度的估计。

4.2 采样

为了在k边限制下从p中采样一个邻接矩阵，同时为了实现端到端的训练。使用了SIMPLE的算法，一个最近提出的梯度估计算法。
在神经网络的前向传播中，使用SIMPLE去采样邻接矩阵，在反向传播中，基于前一层的权重来计算近似梯度。

SIMPLE是一个高效精准有效的算法，在反向传播的计算中取得了更低的偏差和方差。

4.3 计算复杂度

向量复杂度，PRMPNN最差训练复杂度就是o(l)，l是采样的最大边数量。
如果让n是图的节点数，如果增加的边或删除的边达到理论最大值，那么这个复杂度理论最大为o(n^2)
为了减少计算复杂度，使用简单启发式来选择一个可能边的子集，比如考虑距离较远的节点的边。

4.4 PRMPNN的表达能力

首先PRMPNN能够比流行的随机去点去边方法更好，是本文首先通过引入一种概率性且普遍适用的图分离概念，来精确界定概率性分离图集的具体含义。
我们的框架可以轻松推广到节点移除的情况，我们可以从邻接矩阵采样k个边和从原图中删除，可以得到基于概率质量函数下的分离属性。

定理4.1基于绝大部分的图有一个离散的一维WL图着色算法。对于一个图来说，一维WL图着色包含离散和非离散的两部分。

以下结果表明，存在不基于离散着色对应部分同构来区分图的分布p(θ,k)，所以有命理4.2

下面的定理表明，与随机一致删除边或节点的概率质量函数相比，PRMPNN更可能分离非同构图。

同时，也有一个负面的结论，存在一些类型的图，PRMPNN表现不能优于随机采样。

5. 实验设置

关于本文算法的哪些因素导致更好的表现的，详细来说有三个问题

• 1，基于概率的图重连是否可以减缓过度挤压和缺乏接触等问题
• 2，标准MPNN的表达能力是否通过基于概率的图重连而增强？也就是说，能否从实验验证分离概率质量函数可以用PRMPNNs学习，并且多个先验有帮助？
• 3，基于概率的图重连算法，能否适用于图级别的任务，或是异质图的节点级别任务。

为了回答问题1，使用了TREES-NEIGHBORSMATCH数据集
为了回答问题2，使用EXP和CSL数据集来验证图重连的增强程度，还使用了4-CYCLES数据集来对比DropGNN模型，进行消融实验，来看不同数量的先验样本的影响。
为了回答问题3，使用图级别的回归数据集ALCHEMY，ZINC，OGBR-MOLHIV，QM9，LRGB和TUD数据集的五个子集，对于异构图的节点级别任务，使用CORNELL，WISCONSIN，TEXAS数据集。

基线模型
所有的下行的模型都采用基于GIN层的MPNN。

实验结果
算法比较，表格1说明了本文图重连算法可以比其他的基线模型在各个数据集上更好效果。

回答问题1的测试

在EXP数据集上的表现，对比其他的GIN基础模型

对比其他的GIN基础模型和基于概率图重连算法结合

本文核心算法PRMPNN和其他方法的对比

6. 总结

算法基于最新的研究对比，本文是2024的，核心采样算法SIMPLE来源2023年，很新。