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

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

公众号新闻
©作者 | 桑士龙
单位 | 南京邮电大学

来源 | 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 对消息矩阵进行了细粒度的删除操作,因此在大多数情况下都具有更强的适用性。最后通过实验证明了该模块的有效性。

更多阅读



#投 稿 通 道#

 让你的文字被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。


总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析科研心得竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。


📝 稿件基本要求:

• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注 

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:[email protected] 

• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编



🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧


·

微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
我用ChatGPT写神经网络:一字不改,结果竟然很好用理解并统一14种归因算法,让神经网络具有可解释性说中国人没有宗教就好象说邻居老王不戴假发一样。灵魂无处安放的才需要外在宗教,中式思维就是宗教,不需要另有宗教。怎样让ChatGPT在其内部训练神经网络?NeurIPS 2022 | ​NAS-Bench-Graph: 图神经网络架构搜索BenchmarkNpj Comput. Mater.: 水粘度模拟—第一性原理-深度神经网络怎样让ChatGPT在其内部训练神经网络?先让它想象自己有4块3090业界首个适用于固体系统的神经网络波函数,登上Nature子刊6种卷积神经网络压缩方法转:2023 回国探亲(5)WSDM 2023 | 学习蒸馏图神经网络Hiring | Resource Development Manager(Full Time)​ICLR 2023 | 标识分支结点,提升图神经网络对环的计数能力Chinese University Fires Professor Accused of Sexual Harassment「图神经网络前沿进展与应用」要还饶毅一个“清白”​AAAI 2023 | 利用脉冲神经网络扩展动态图表示学习情商这高级玩意儿不是谁都有的详解神经网络中反向传播和梯度下降ICLR 2023 | 漂移感知动态神经网络:基于贝叶斯理论的时间域泛化框架GNN如何建模时空信息?伦敦玛丽女王大学「时空图神经网络」综述,简明阐述时空图神经网络方法Transformer:一种图灵完备的神经网络台湾的高营ChatGPT写神经网络:一字不改,结果竟然很好用日本啊,日本(十四)中国茶道,日本茶道国际要闻简报,轻松了解天下事(03Npj Comput. Mater.: 多主元素合金硬度—集成神经网络模型ICLR 2023 | 清华大学龙明盛组提出通用时间序列神经网络骨干—TimesNetEruope 2023Chinese TV Drama Normalizes Women Dating Younger MenDALL-E和Flamingo能相互理解吗?三个预训练SOTA神经网络统一图像和文本10行代码搞定图Transformer,图神经网络框架DGL迎来1.0版本详解神经网络基础部件BN层最新综述:等变图神经网络中国学者引领图神经网络技术的重要突破,再次刷新了蛋白质性能预测榜单记录国际要闻简报,轻松了解天下事(03Shanghai Eases Driving License Process for Deaf Drivers王啸@北京航空航天大学:图神经网络的“共性”与“个性”2023 春 祝姐妹们周末快乐!Cut Children’s Access to Vulgar Memes: State Media Commentary
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。