极市导读
本文提出了一种训练图神经网络的新框架“合作图神经网络”(Co-GNNs), 其中每一个节点可以被看作一个独立的玩家,可以在消息传递之前基于当前特征计算出一个动作分布,然后根据分布采样选择该节点在本层的动作。 >>加入极市CV技术交流群,走在计算机视觉的最前沿
宣传一下自己研究生最后与学长 Ben Finkelshtein 一起的工作。导师为牛津大学计算机系的 Professor Michael Bronstein 和 Dr. İsmail İlkan Ceylan。欢迎大家来 ICML 2024 维也纳进行交流!
01 摘要
本文提出了一种训练图神经网络的新框架“合作图神经网络”(Co-GNNs), 其中每一个节点可以被看作一个独立的玩家,可以在消息传递之前基于当前特征计算出一个动作分布,然后根据分布采样选择该节点在本层的动作。
可选择的动作分为以下几种:倾听”、“广播”、“倾听和广播(又称标准)”或“隔离”。Co-GNNs 提供了一种更灵活和动态的消息传递范式,其中每个节点可以根据其状态确定自己的策略,并有效地在学习过程中探索图拓扑结构。
论文链接:
https://arxiv.org/abs/2310.01267
代码链接:
https://github.com/benfinkelshtein/CoGNN
Towards Data Science:
https://towardsdatascience.com/co-operative-graph-neural-networks-34c59bf6805e
02 消息传递与信息瓶颈
大多数图神经网络都属于消息传递神经网络(Message passing neural networks,MPNNs),其中每一个节点在每一层都沿着图的边进行信息的交换,然后通过聚合函数来更新当前节点特征。
我们注意到,因为 MPNN 需要至少 k 层才能收到 k-hop 邻居的信息,增加 MPNN 层数会导致感受野的指数增长。因为最终必须将越来越多的领域信息压缩成固定大小的节点嵌入,导致大量信息丢失。这个现象被称为消息传递神经网络的过度压缩(Over-squashing)。
一些常见的解决过度压缩的方法有 动态图重写(dynamic graph rewiring),注意力机制(attention),或者门控机制(gating)。主要的思路都是通过修改邻域矩阵或者降低权重。
03 合作图神经网络
为了更好的解决过度压缩问题, 我们提出了合作图神经网络(Co-GNNs),通过两个图神经网络来决定模型最后的输出。其中第一个图神经网络被称为 动作网络 (Action network),输入当前节点嵌入与图本身,对每一个节点选择以下四个动作:
倾听和广播/标准(S): 广播自己的节点嵌入给所有倾听的邻居,并倾听正在广播的邻居。
倾听(L): 只倾听正在广播的邻居,而不广播自己。
广播(B): 只广播自己,而不倾听任何邻居。
隔离(I): 既不广播也不倾听,保持自己当前状态。
注意到当所有节点都选择标准(S)动作时,Co-GNN 会退化成标准的消息传递神经网络(MPNNs)。当所有节点都选择隔离(I)动作时,Co-GNNs 会退化成 DeepSets,完全不考虑图的邻居信息。
当动作选择完后,第二个图神经网络 环境网络(Environment network)会在一个通过所选择的动作重写的子图上进行消息传递并得到输出。Co-GNNs 其中一个特点是两个网络同时通过一个损失函数进行训练,就像两个网络在“合作”解决一个问题一样。
04 Co-GNN的优势
以具体任务为导向: 通过允许每个节点仅从相关的邻居处倾听信息,Co-GNNs 可以确定最适合目标任务的计算图。
定向: 节点可以采取的动作结果相当于输入图的一种特殊形式的“定向重连”。例如一条边可以被删除(两个邻居都倾听但不广播);保持无向边(两个邻居都倾听和广播);或者变成一条有向边(一个邻居倾听同时另一个邻居广播)。
动态: Co-GNNs 并不在预先固定的计算图上操作,而是在通过节点动作选择学到的计算图上操作,这个计算图在各层之间可以是不一样的。
基于特征和结构: Co-GNNs 可以为具有不同节点特征的两个节点学习不同的动作。
异步: Co-GNNs 可以允许节点间的异步更新。
比1-WL更有表达力: Co-GNNs有一定概率对于 1-WL 无法区分的一对节点会采样到不同的动作,导致这两个节点在消息传递时考虑到的邻域不同,以此区分该对节点。
适用于长距离任务: 长距离任务通常需要在远距离节点之间传递信息。我们的消息传递模式可以通过学习专注于连接这两个节点的最短路径来有效过滤无关信息,从而最大化信息流向目标节点。
防止过度压缩: 由于 Co-GNNs 可以灵活地选择消息传递路径和动作,它能够减少信息在压缩过程中丢失。
防止过度平滑:“过度平滑(Over-smoothing)”是指随着消息传递层数的增加,节点嵌入在整个图中变得越来越相似的趋势。Co-GNNs 通过选择 隔离(I) 动作,可以模拟门控机制自适应地禁用来自特征相似的邻居的节点更新,从而有效防止过度平滑。
05 实验结果
Co-GNNs 在异质节点分类任务中超过了所有已有的模型。
其中我们发现,Co-GNNs 在同质图与异质图的表现有明显的区别。同质图(homophilic)指的是图中的节点倾向于与具有相似特征或标签的节点相连接。这种类型的图在社交网络、生物网络和知识图谱等领域中很常见。同质图中的节点关系通常较为均匀,信息在图中的传播和聚合更为直接和有效。
实验中我们发现,Co-GNNs 倾向于首先保留大量原图的边,优先聚合周围邻居的信息。在之后层里会逐渐减少边的链接,防止信息过度传播。
相反,异质图(heterophilic)则指的是图中的节点倾向于与具有不同特征或标签的节点相连接。这类图在一些特殊场景中出现,例如跨领域的推荐系统或多样化的社会网络。在异质图中,节点关系较为复杂,信息的传播和聚合需要更为灵活和动态的机制,因此 Co-GNNs 在这种类型的图中可以更好地发挥其优势。
实验发现,Co-GNNs 在异质图中会先优先限制邻居节点的信息交流,让更远处的节点信息传递来以后,在之后的层里再进行处理和融合。通过这种方式,Co-GNNs 可以有效避免信息过度压缩和过度平滑的问题,从而在复杂的异质图结构中保留更多的有用信息。
公众号后台回复“数据集”获取100+深度学习各方向资源整理
极市干货
点击阅读原文进入CV社区
收获更多技术干货