AAAI 2023 | DropMessage: 统一图神经网络中的随机删除

2023-02-21 05:02

©作者 | 桑士龙

单位 | 南京邮电大学

来源 | MIND Laboratory

论文简介

图神经网络 (GNNs) 经过多年的快速发展目前仍然存在着过拟合，过平滑和非鲁棒等特点。之前的工作指出可以通过随机删除的方法将增强以后的数据集成到模型中来缓解这些问题。但是对于不同的数据集而言有不同的属性，模型的性能也会因为使用不同的删除策略而大大改变，因此很难找到一种通用的方法。而且在 GNNs 中引入增强后的数据会导致参数覆盖不完整并且会使训练过程不稳定从而导致参数难以收敛。

除此之外，目前也没有 GNNs 关于随机删除方面在有效性上的理论分析。因此本文提出了新的随机删除方法 DropMessage，在消息传递过程中直接对传递的消息进行删除操作。

因为 GNNs 递归地聚合邻域的信息，所以 GNNs 中的节点表示往往会变得不可区分，这种过平滑现象就阻止了 GNNs 建模高阶的邻域关系。递归聚合也使得 GNNs 更容易受到输入图质量的影响，因此噪声图或者对抗攻击会很容易影响到 GNNs 的性能。

论文标题：

DropMessage: Unifying Random Dropping for Graph Neural Networks

论文链接：

https://arxiv.org/pdf/2204.10037.pdf

如图1，现有的随机删除方法对节点的特征矩阵或者邻接矩阵进行删除。

本文提出的 DropMessage 对传播的消息进行删除操作，允许一个节点将不同的消息传递给不同的邻居。并且本文将现有的随机删除方法统一到 DropMessage 框架中。文中还证明了在 GNNs 上进行随机删除等同于在损失函数中引入额外的正则化项，可以使模型更加鲁棒。

一般来说随机删除可以看作是一种特殊的特征-噪声模式，可以通过人为破坏训练数据来缓解过拟合的问题。

贡献

本文的主要贡献为：

1. 对所有的基于消息传递的 GNNs 提出了一个新的随机删除方法 DropMessage。现有的随机删除方法通过对消息矩阵按照一定规则进行掩码，都可以统一到该框架中，可以被看作是 DropMessage 的一个特殊形式；

2. 首次从理论上证明了随机丢弃方法的有效性。

方法

给定一张图

表示节点的特征矩阵，表示节点的特征维度。A 表示邻接矩阵，是节点的度，其中计算了节点的边的总和。在图上应用消息传递 GNNs 的时候，消息矩阵是，其中是节点之间传播的消息，是传播消息的总和，是消息的维度数。

目前大多数 GNNs 都使用消息传递框架，在消息传递的过程中，节点表示更新过程可以用如下的公式描述。

节点 i 的边，和是可微的函数，AGG 表示聚合操作。可以将所有传播的消息收集到一个消息矩阵中。中的每一行对应一条在有向边上传播的消息，可以表示为

，其中表示生成消息的映射，消息矩阵的行数表示图中有向边的个数。

DropMessage 基于删除率在消息矩阵上执行删除操作，也就是消息矩阵中有个元素将会被删除，这个操作也可以被看做是一种采样过程。对于消息矩阵中的每一个元素都生成一个单独的服从伯努利分布的掩码来决定是否保留。然后将每个元素与其掩码相乘得到扰动后的消息矩阵，接着使用系数进行缩放，保证扰动后的消息矩阵与原始消息矩阵在期望上相等。最终可以得到如下公式：

如表 1，Dropout，DropEdge，DropNode 和 DropMessage 都可以看做是伯努利采样过程，只是分别对不同的对象进行采样操作。

1. Dropout 在特征矩阵 X 中删除元素，等价于删除消息矩阵 M 中的元素 source ，其中表示在特征矩阵中对应的元素。

2. DropEdge 在邻接矩阵中删除元素：和，等价于删除消息矩阵中的元素

，其中表示在邻接矩阵中对应的元素。

3. DropNode 在特征矩阵 X 中删除元素，，等价于删除消息矩阵 M 中的元素

，其中表示在特征矩阵中对应的元素。

4. DropMessage 直接在消息矩阵 M 中进行随机删除。通过上述表示可以发现另外三种方法都可以看做是 DropMessage 的特殊形式。

3.1 理论证明

GNNs 上的无偏随机删除方法在目标函数中引入了额外的正则化项，让模型更加鲁棒。

假设下游任务是一个二分类问题，应用了一个单层的 GCN 模型，，是消息矩阵，是变化矩阵，B 指示了每个节点应该聚合哪些消息，就是他的归一化的形式。最终的结果采用 sigmoid 函数，表示为，使用交叉嫡作为损失函数，表示为：

当进行随机删除时，使用扰动后的消息矩阵代替原始消息矩阵，期望目标函数就可以变为如下形式：

通过上式可以看出，随机删除方法为目标函数引入了额外的正则化，对于二分类任务可以使分类概率趋近于 0 或者 1，从而可以得到更加清晰的判断。

只要拓展模型输出的维度，就可以推广到多分类任务，形式上可以表示为

，其中是节点的标签。

所有的随机删除方法在采样过程中都会产生随机噪声，会增加训练过程的不稳定性。因此本文从样本方差的角度来让模型变得更加鲁棒。

在基于消息传递的 GNNs 上，DropMessage 与其他随机删除方法相比，当删除率同为 δ 时，DropMessage 的样本方差最小。因为 DropMessage 是 GNNs 模型的最细粒度的随机删除方法，应用 DropMessage 时每个元素都会独立的判断是否应该被删除。

信息多样性包括特征多样性和拓扑多样性。特征多样性

，其中 | 是层数在之间，表示来自节点的边的对应的行号。拓扑多样性，在之间，计算集合中元素的个数。

因此，特征多样性可以看做是不同源的节点保留特征维度的总数，拓扑多样性定义为传播了至少一维消息的有向边的总数，只有在随机删除后特征多样性和拓扑多样性都不减少的情况下才能保证信息多样性。作者证明了 Dropout，DropNode 和 DropEdge 都不能保持信息多样性。

当节点的删除率时，DropMessage可以保持信息多样性，其中是节点的出度，是特征维度。

DropMessage 对消息矩阵进行随机删除，为了保证拓扑信息多样性，期望消息矩阵 M 中每一行至少有一个元素可以保留，因此可以产生如下表示：

为了保证特征信息多样性，特征矩阵 X 对应的消息矩阵中期望至少有一个元素保留：

因此删除率应该同时满足上面两个式子，。

实验结果

节点分类任务在四个公开数据集上进行测试准确率来衡量性能。使用了随机删除的 GNNs 框架结果始终优于不使用随机删除的 GNNs 框架。随机删除方法的效果在不同的数据集上，不同的模型和不同的下游任务上不同。

APPNP 使用随机删除方法在 CiteSeer 上平均精度提升为 1.4%，在 PubMed 上只提高了 0.1%。GCN 使用随机删除方法在 Cora 上提高了 2.1%，而 GAT 只提高了 0.8%。DropMessage 在 15 种情况下得到了最优的结果，在其余情况下是次优的，并且表现稳定，比如 DropEdge 在工业数据集上效果很好，但是在公共数据集上表现明显下降。因此 DropMessage 具有更强的通用性。

使用 MADGap 衡量过平滑的程度，值越小表明节点越难以区分，因此值越大越好。通过图 2a 和 2b 可以看出 DropMessage 的 MADGap 和精度经过多层卷积以后性能都比其他随机删除方法要高。当层数大于 3 的时候，DropMessage 的 MADGap 值平均提高了 3.3%，测试精度平均提高了 4.9%。

这表明了 DropMessage 可以在一定程度上阻止了节点收敛到相同的表示中。2c 测试了在 Cora 数据集上采用不同的随机丢弃方法时，GCN 训练过程中的损失的变化情况。可以看到 DropMessage 样本方差最小，收敛速度最快，性能最稳定。

总结

本文提出了一种用于消息传递 GNNs 模型的通用随机删除方法 DropMessage。首先对消息传递矩阵进行删除并分析影响，将所有随机删除方法统一到框架中，从理论上说明了 DropMessage 在稳定训练过程和保持信息多样性方面的优越性。因为 DropMessage 对消息矩阵进行了细粒度的删除操作，因此在大多数情况下都具有更强的适用性。最后通过实验证明了该模块的有效性。

更多阅读