论文分析 | GNN什么时候有效？理解和提升邻居聚合

2020 年 9 月 30 日 AINLP

When Do GNNs Work: Understanding and Improving Neighborhood Aggregation

1. 摘要

GNN的关键是邻域聚集，其中每个节点的嵌入都是通过聚合其邻居的特征来进行的。本文旨在通过提出以下问题来更好地理解这种机制：邻居聚集总是必要且有益的吗？简而言之，答案是否定的。作者提出了两个条件，在这些条件下，邻居聚合是无用的：（1）当节点的邻居非常不相似时；（2）当节点的嵌入已经与其邻居非常相似时。本文提出了两个新的度量标准，可以定量地测量这两种情况，并将它们集成到自适应层模块中。实验表明，与当前GNN相比，允许特定于节点的聚合度具有明显的优势。

2. 主要方法

尽管GNN在多个数据集中取得了巨大成功，但可以观察到，在度较大的节点附近进行聚集时，不管怎么修改聚合方式，提升总是有限的，所以我们深入思考一下图上有些邻居的聚集是否是不必要的甚至是有害处？

作者发现：（1）如果学习到的中心节点邻居的特征/标签不一致（具有较高的熵），则进一步的聚合可能会损害性能；（2）当中心节点的学习特征/标签与其相邻节点几乎相同时，则无需进一步聚合。对于每种情况，作者都基于信息论设计一个直观的指标以量化。具体来说，作者定义了两个指标：Neighborhood Entropy；Center-Neighbor Similarity

Neighborhood Entropy

邻域聚合其实暗含了一种假设：也就是网络中的同源效应，即互相连接的节点应该是相似的，更进一步，节点的邻居之间应该是相似的。当邻居们不一致时，我们需要谨慎一些，因为此时假设可能不成立，换句话说聚合的信息可能是噪音。为了度量一个特定节点邻域的多样性，我们计算相邻节点之间的熵，

其中x是特征空间，f节点u周围的是PDF。但是计算起来比较困难，因此采用预测的标签来衡量离散的熵，也就是下面的公式

该公式表明如果计算出来的score值比较大，那么以node 为中心的多样性是非常大的。比如俱乐部的一个图，节点9处于边界的位置，节点6处于社区内部的位置，通过上面的公式计算出来P(9)>P(6)

Center-Neighbor Similarity

当节点的特征与邻居足够相似时，邻域聚集可能是多余的。例如，上面图中节点25的标签已经与其所有邻居相同，聚合操作将不会更改其标签，因此是不必要的。我们通过计算以下点来描述这种相似性：中心节点及其邻居特征/标签之间的互信息（PMI）

可以证明，当上面这个值大于某一个数值时，聚合产生的影响是非常有限的.

结论：当邻域熵或中心邻居相似度很高时，我们在执行聚合时应更加谨慎。作者提出了一个自适应层模块，该模块允许节点在每轮邻域聚合中做出单独的决策。不同的节点可能会经历不同的聚合度。具体来说，在每一层中，采用门函数控制邻域信息的影响。它的值由Score_sim和Score_etp确定。

其中是一个引导函数

当Score_sim或Score_etp中的一个较大时，z取一个接近0的小值。范数是批量归一化操作，用于重新缩放分数，以便它们在各层之间可比。为简单起见，在模型中使用one-hot预测标签来计算Score_sim和Score_etp。当然也可和attention结合在一起：

其中是attention 系数

3. 实验结果

在本文中，作者分析了GNN模型中普遍存在的关键组成部分：邻域聚合操作。不同的节点可能需要不同的聚合度才能达到正确的预测。过度的聚合可能是多余的，甚至是有害的，从而导致过度平滑的现象，其中所有节点最终都收敛到同一固定点。为了表征何时可能不需要邻域聚集，本文提出了两个指标：邻域熵和中心邻域相似度。

从实验和理论上都表明，所提出的指标可以成功地识别出无法从邻域聚合中受益的节点。未来工作的一个潜在方向是将分析扩展到其他任务，例如图分类和链接预测。

http://jiyang3.web.engr.illinois.edu/files/alagnn.pdf

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入图神经网络技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注GNN

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。