通过监督式块对角正则化器构建鲁棒的图神经网络

《Pattern Recognition》：Robust Graph Neural Networks via Supervised Block Diagonal Regularizer

图神经网络选择矩阵的块对角结构监督正则化及其框架研究。提出SuBDR正则化直接优化选择矩阵的块对角结构，结合标签信息增强判别性，构建鲁棒的SuBDR-GNN框架并设计收敛性证明的迭代算法，实验验证其有效性。

　　

陈志|王丽斌|王玉龙|李涵|何强|罗慧武|田金宇|唐远炎

华中农业大学信息学院，武汉，430070，中国

摘要

图神经网络（GNNs）对输入图中的结构扰动非常敏感。为了解决这个问题，提出了各种图稀疏化策略来学习最优的选择矩阵，理想情况下该矩阵具有块对角结构。然而，现有的工作要么忽略了这一关键先验，要么依赖于间接的结构先验，如稀疏性和低秩性，从而导致次优解。为了填补这一空白，我们提出了一种新颖的监督块对角正则化器（SuBDR），它具有两个关键优势：（1）直接性：它直接强制选择矩阵接近最优的块对角结构。（2）区分能力：它充分利用训练数据的标签信息来增强选择矩阵的区分能力。借助SuBDR，我们开发了一个通用且健壮的GNN框架，称为SuBDR-GNNs，该框架不仅直接利用了块对角结构的先验，还将训练数据的标签信息完全纳入选择矩阵的学习过程中，从而确保了更健壮和合理的节点表示。这项工作的另一个贡献是推导出了一种高效的优化算法，并严格证明了其收敛性。在多个基准数据集上的广泛实验证明了我们提出的SuBDR-GNNs框架的有效性、鲁棒性和通用性。代码可在https://github.com/ccmature/SuBDR-GNNs获取。

引言

作为基本的数据结构，图在各个领域得到了广泛应用，包括社交网络分析、推荐系统和药物发现[1]。图神经网络（GNNs）已成为建模此类数据的强大工具，在各种下游任务中表现出色，如节点分类[2]、链接预测[3]和推荐任务[4]。GNNs的核心在于消息传播。然而，传统的GNN[5]通常从所有邻居节点聚合信息，假设图拓扑是无噪声且可靠的。这一假设往往不成立，因为现实世界的图通常受到错误或冗余边的影响[6]。这会损害消息传播，导致节点表示不准确，从而降低节点分类性能。

为了解决这个问题，可以采用图稀疏化策略[7]、[8]、[9]。这些策略通过选择矩阵来精炼原始图结构，从而为下游任务提供更健壮的节点表示。具体方法在第2.2节中详细介绍。

在这些策略中，选择矩阵的学习对GNNs的有效性至关重要。在理想情况下，期望学习到的选择矩阵仅选择连接相同类别节点的边[10]、[11]、[12]。具体来说，如果两个节点u和v具有相同的标签，则$S_{uv}=1$，否则$y_u=y_v$，其中y_i表示节点i的标签。在这种情况下，选择矩阵S自然表现出块对角结构（见图1中的最优），块的数量等于节点类别的数量。如图1所示，通过最优的块对角选择矩阵可以恢复清晰的图结构，从而确保更健壮的节点表示。为了进一步说明这一点，我们使用标准的GCN[5]进行了实验，详细设置见A节。如图2所示，随着选择矩阵中非块元素比例的增加，性能持续下降。这一观察结果与先前的研究结果一致，即图的结构性规则性过低会降低模型性能[13]。在这项工作中，我们重点强调了块对角结构的重要性。特别是当选择矩阵理想地为块对角结构（非块比例=0）时，模型达到最高的准确率。这一结果进一步验证了块对角结构在选择矩阵中的关键作用。

然而，现有工作要么忽略了这一见解，如DropEdge[7]中所做的，要么使用间接结构先验（如稀疏性和低秩性）来近似块对角结构。如图3所示，稀疏性、低秩性和块对角模式是三种不同的结构属性。前两种属性已被广泛用于估计选择矩阵[8]、[9]、[14]。然而，最优选择矩阵遵循块对角结构。虽然稀疏性和低秩性有助于强制块对角结构，但它们并没有明确捕捉到块对角属性。例如，稀疏性确保了较少的连接，但不一定与基于类别的簇对齐。同样，低秩约束强制全局平滑性，可能导致不同类别的表示混合，而不是保持清晰的分离。因此，这些方法没有充分利用选择矩阵的固有块对角结构，从而导致次优解[15]。这激发了我们提出一个有趣的问题：是否有可能提出一种高效的方法来直接学习这个最优的块对角选择矩阵？

一种自然的方法是使用块对角正则化器（BDR）[15]，它可以直接近似块对角结构并控制块的数量。这种技术在子空间聚类中的亲和矩阵学习中得到了广泛应用。尽管在这一领域有效，但其在GNNs中学习选择矩阵的潜力仍未被探索。这项工作填补了这一空白。为了进一步增强BDR，我们提出了一个监督BDR（SuBDR），它充分利用训练数据的标签信息来增强学习到的选择矩阵的区分能力。如图4所示，SuBDR相比BDR实现了更准确的块结构学习，这一点也通过第5.5节中的消融研究结果得到了证明。与依赖间接结构先验并忽略训练数据标签信息的先前正则化器不同，SuBDR明确强制选择矩阵接近最优的块对角结构，同时结合标签信息来增强其区分能力。借助SuBDR，我们开发了一个健壮且通用的GNN框架，称为SuBDR-GNNs，它通过学习具有区分能力的选择矩阵来增强节点表示的健壮性。此外，我们提出的SuBDR-GNNs可以无缝集成到各种GNN架构中，以提高有效性和鲁棒性。实际上，由于SuBDR的非凸公式，其集成引入了额外的优化挑战。为了解决这个问题，我们设计了一种高效的迭代优化算法来解决SuBDR-GNNs，并提供了严格的理论分析以证明其收敛性。

总结来说，本研究的主要贡献如下：

• 我们提出了一种新颖的监督块对角正则化器（SuBDR）来优化选择矩阵。
• 借助SuBDR，我们开发了一个健壮且通用的GNN框架，称为SuBDR-GNNs。
• 我们为SuBDR-GNNs开发了一种高效的迭代优化算法，并提供了严格的理论分析以保证其收敛性。
• 我们在多个基准数据集上进行了广泛的实验，证明了所提出框架的有效性、鲁棒性和通用性。

小节片段

图神经网络

图神经网络（GNNs）通常分为基于谱的方法和基于空间的方法。基于谱的GNNs通过图拉普拉斯矩阵的谱分解来构建图卷积[16]。为了提高可扩展性，Kipf和Welling[5]用局部一阶卷积近似谱滤波器，Wu等人[17]进一步通过消除非线性和合并权重矩阵来简化这一方法。最近的研究继续丰富了这一研究方向。

符号说明

在本文中，我们用字母表示标量，例如，用粗体小写字母表示向量，例如，用粗体大写字母表示矩阵，例如。常用的符号列在表1中。

我们还介绍了一个有用的概念。

定义1

(k-块对角结构)) 如果$S\in R^{n\times n}$可以被划分为k个不同的对角块，则称其具有k-块对角结构，其中非零元素仅出现在块内，块外的所有条目均为零，

块对角正则化器

在本节中，我们介绍了一个块对角正则化器，它直接强制接近块对角结构。

重新审视最优选择矩阵并将其视为图的邻接矩阵，可以发现图包含个连通分量。因此，问题简化为控制图以确保它恰好有个连通分量。设< />为的拉普拉斯矩阵，即$\begin{array}{c}{L}_S=\text{Diag}\left(S1\right)?S。\end{array}$ 以下定理直接来自[29]，将< />与

实验

在本节中，我们在几个基准图数据集上进行了实验，以验证SuBDR-GNNs在节点分类任务上的有效性、鲁棒性和通用性。具体来说，我们旨在解决以下问题：

•

RQ1：所提出的SuBDR-GNN与现有技术方法在整体性能上相比如何？

•

RQ2：SuBDR-GNN在不同程度的结构噪声下能保持多大的鲁棒性能？

•

RQ3：SuBDR能否有效地推广到其他GNN

结论

在本文中，我们观察到最优选择矩阵表现出块对角结构。为了直接近似这种结构，我们引入了块对角正则化器（BDR）。与依赖间接结构先验的先前正则化器不同，BDR明确强制选择矩阵接近真实的块对角结构。为了进一步增强BDR学习到的选择矩阵的区分能力，我们提出了监督BDR（SuBDR），它结合了

CRediT作者贡献声明

陈志：撰写——原始草稿，可视化。王丽斌：撰写——审阅与编辑。王玉龙：撰写——审阅与编辑，监督，方法论。李涵：监督。何强：监督。罗慧武：监督。田金宇：监督。唐远炎：监督。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。