论文题目：Probabilistic Graph Rewiring via Virtual Nodes
论文领域：图神经网络，图重连
论文发表：NeurIPS 2024
论文算法：IPRMPNN
论文背景：
消息传递图神经网络（MPNN）已经成为基于图的机器学习的强大范式。尽管它们很有效，但MPNNs面临着诸如接触不足和过度挤压等挑战，在这些挑战中，有限的接受域和结构瓶颈阻碍了图中的信息流动。虽然图变换器有望解决这些问题，但由于节点数量的二次复杂性，它们的可扩展性有限，这使得它们对于更大的图来说不切实际。在这里，我们提出了隐式重连消息传递神经网络（IPR MPNN），这是一种将隐式概率图重连集成到MPNN中的新方法。通过引入少量的虚拟节点，即在给定的图中添加额外的节点并将其以可微的端到端方式连接到现有节点，IPR MPNN实现了长距离消息传播，避免了二次复杂性。理论上，我们证明了IPR MPNN超越了传统MPNN的表现力。根据经验，我们通过展示其减轻欠伸和过度挤压效应的能力来验证我们的方法，在多个图形数据集中实现最先进的性能。值得注意的是，IPR MPNN的性能优于图变换器，同时保持了更快的计算效率。
1，提出新方法IPR-MPNN，给图增加虚拟节点，并且使用端到端学习去连接虚拟节点和图节点。IPR-MPNN方法克服了graph transformer的二次计算复杂度和提高了图重连算法的表现效果
2，我们理论上证明IPR-MPNNs超越了标准MPNNs的表达能力，后者通常受限于一维Weisfeiler-Leman算法。
3，从实验上证明了IPR-MPNN比标准的MPNN和GT表现更好，且更快的计算效率
MPNN一般是基于局部特征的编码，具体而言，它们的判别能力至多与区分非同构图或具有不同结构角色的节点相当，正如一维魏斯费勒-莱曼算法所展示的那样——该算法是图同构问题中一个经过深入研究的启发式方法。
Graph Transformer 全局的注意力机制，但其注意力矩阵的二次计算量很大。
对于图的节点分类任务，节点特征为
对于图级别的任务，整个图的特征为
其中READOUT是一个参数化的函数（比如是神经网络）
为了学习连线原始节点和添加的虚拟节点，IPR-MPNN使用一个upstream模型，通常是MPNN，来产生分数或者先验知识
IPR-MPNN使用upstream模型得到的先验θ，可以在原始节点和m个虚拟节点之间采样新的边，为服从后验分布的k条边。
与PR-MPNNs不同——后者在最坏情况下需要为所有n²条可能的待重连边显式建模边分布——IPR-MPNNs通过虚拟节点实现隐式重连和远程信息传递。虚拟节点的作用是作为中转，降低节点连线之间的边的数量。
相较于学习图中所有可能边的显式分布，通过少量虚拟节点连接的边分布建模也更为简便。
该算法是一种迭代方法，从用度数或其他信息为两个图中的顶点打标签或着色开始，并根据节点自身颜色及其邻居颜色来更新节点颜色。在迭代过程中，若具有相同标签的两个顶点其相同标签邻居数量不等，则会被赋予不同标签。每次迭代最终形成顶点颜色划分，当划分结果不再被算法优化时（即获得稳定着色或稳定划分），算法终止。
如果颜色不一，说明两个图非同构。
图结构学习类似图重连，主要动机在于优化图结构的同时联合学习图表示。一般是使用特殊的损失函数来优化图结构，使用边计分函数，离散的边采样方法，都是常见方法。
DGM算法，通过利用Gumbel离散采样来预测潜在的图结构；
还有作者Franceschi的算法是通过超梯度下降学习伯努利分布来预测潜在的图结构；
作者Saha方法是通过学习平滑-海维赛德函数进行采样，为轨迹预测和点云分类任务习得自适应邻域特征；
作者Younesian的研究则采用GFlowNets框架对用于下游任务的节点进行采样。
还有一些GSL基于非监督学习来。
算法的整个流程图
边的采样：上游模型将邻接矩阵及其节点属性转换为一组未归一化的节点先验θ∈Θ⊆Rⁿˣᵐ，其中m表示预定义的虚拟节点数量。
先验概率矩阵θ作为条件概率肿块函数的参数矩阵，从中采样得到赋值矩阵H ∈ {0, 1}n×m。
矩阵的每一行i都代表着每一个虚拟节点连接初始节点的未归一化的概率。
其中有
采样分配矩阵的每一行恰好有k个非零项
因此，我们将逆向分配定义为分配给虚拟节点c的所有原始节点的集合，即a⁻¹(c) := {v ∈ V(G) | c ∈ a(v)}。在整个图中，这些逆向分配的并集等于原始节点集合。
初始化的虚拟节点特征：相同标签的样本被划分为一个子图，那么某个虚拟节点c的关联到对应子图Gc的公式为
我们可以为每个虚拟节点生成散发特征作为初始节点特征，或者为它们分配唯一标识符。
更新虚拟节点，从原始节点得到特征来去获得虚拟节点特征
表示AGGn专为多重集设计的某种置换等变聚合函数。
虚拟节点之间的更新
更新原始节点：此次更新过程同时考虑了原始图中的相邻节点以及原始节点被分配到的虚拟节点。
损失函数为
在downstream的模型训练可以直接基于损失函数的反向传播；在upstream模型上获取梯度比较困难使用SIMPLE算法，可以高效的从k子集的限制中获取梯度。在前向传播中使用的先验为
和
分析IPR-MPNN可以区分非同构图但在一维WL同构图测试却失败的情况，这个可以证明IPR-MPNN可以比一维WL同构图测试效果更好。
该推论告诉我们，即使存在同构图可能导致分离的风险，我们仍将保持绝大多数同构对之间的同构关系。
先前的定理表明，我们在保持同构性方面优于纯随机化方法，同时比1-WL更具判别力，因为我们能以严格大于0的概率分离非同构图。
研究问题一，IPR-MPNN可以减缓过度挤压和失去连接问题吗？
研究问题二，IPR-MPNN比一般的MPNN有更强的表达能力吗？
研究问题三，IPR-MPNN比其他的图重连问题和GT方法在生物数据集上表现更好吗？
研究问题四，IPR-MPNN在理论上的更低计算复杂度，是否在实践上也是表现更快？
实验数据为
相较于基础模型，IPR-MPNNs能保持较高的逐层敏感度，这意味着即使叠加多个网络层，该模型仍能有效捕捉长程依赖关系。实验如下
虚拟节点和对应的连线，相当于一个简单的全局连接机制，去找到最有用的信息。和GT的思路类似，同时使用虚拟节点来降低计算量。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。