理解和减少图神经网络中的图结构噪声

1. 基本信息

• 题目:理解和减少图神经网络中的图结构噪声
• 作者:Mingze Dong, Yuval Kluger
• 机构:耶鲁大学病理学系,耶鲁大学应用数学项目

2. 摘要

本文着眼于理解和减轻图结构噪声对图神经网络性能的影响。首先,作者提出了一种新的指标“边信噪比”,用于估计真实数据图中的整体图结构噪声水平。作者在各种模拟和真实数据集上验证了该指标与图神经网络性能之间的高度一致性。其次,作者提出了一种基于自监督学习的图重连框架“图倾向分数”,以减轻图结构噪声的影响。作者给出了该框架的理论保证,并通过全面的基准测试证明了其有效性。本文为理解和优化图神经网络在噪声图数据上的训练提供了新的视角。

3. 介绍

• 图神经网络通过消息传递机制在关系数据上进行学习,但当应用于具有结构问题的图时,其性能可能会受到影响。
• 目前对图结构噪声对图神经网络性能的影响还没有系统的理解和量化指标。
• 目前基于图重连的方法存在局限性,特别是缺乏基于特征的任务无关的图去噪方法。
• 本文的贡献:1) 提出了一种新的指标“边信噪比”来评估图结构噪声水平;2) 提出了一种基于自监督的图重连框架“图倾向分数”以减轻图结构噪声的影响。

4. 方法

4.1 边信噪比(ESNR)

• 定义图的生成模型:邻接矩阵A的每个条目独立地从一个潜在概率矩阵进行采样。
• 将A按预定义的节点分割(例如标签)进行行聚合得到矩阵C,将C分解为信号C_p和噪声C_ε。
• 通过白化变换去除C_ε的异方差性,使其谱分布收敛到Marchenko-Pastur分布。
• ESNR定义为C'的奇异值(去除均值后)相对于MP右边界的平均强度。

• 在简化的CSBM中,证明了ESNR与边的互信息呈单调关系,从而反映信号水平。
• 在各种模拟和真实数据中验证了ESNR与GNN性能的高度一致性。

4.2 基于图倾向分数的图重连

• 定义图的倾向分数为边A_{ij}存在的条件概率:

• 通过自监督的链接预测任务学习倾向分数。
• 在简化CSBM设置下,证明了基于倾向分数重连的图使边的互信息最大化。
• 将倾向分数矩阵稀疏化后作为新的图进行GNN训练。

5. 实验发现

• 在各种模拟和真实数据集中,ESNR指标均与GNN性能高度一致,明显优于同质性等指标。

• 基于图倾向分数的图重连方法在多个数据集的节点分类任务中优于多种基准方法,特别是在异质性强的数据集上获得显著提升。
• GPS重连后的图连接性与原图的ESNR呈相关,低ESNR的图会更多地“修剪”边,而高ESNR的图会更多地加入新边。

6. 结论

• 本文通过提出ESNR指标和GPS图重连框架,从理解和优化的角度系统地处理了图结构噪声对GNN训练的影响。
• ESNR为跨数据集理解GNN性能提供了新的视角。
• GPS框架为降低图结构噪声提供了有效的方法,特别适用于异质性强的数据集。
• 本文为GNN在噪声图数据上的训练提供了新的理论和实践工具。