本文发表于NeurIPS 2022

本文关注的问题是什么

当前GNN的关系归纳偏差（同质性假设）并不完全成立，在异质图上尤其严重。本文研究了如何提高现有GNN在异质图上的性能

本文提出了何种方法来解决问题

• 证明了现有的图同质性度量指标存在缺陷，并提出了一个新的同质性度量指标

• 提出了自适应通道融合策略（Adaptive Channel Mixing, ACM），这个策略根据每个节点不同的异质性，自适应地为节点提取丰富的局部信息（ richer localized information ）

Abstract

图神经网络（GNN）通过使用基于关系归纳偏差（同质性假设）的图结构来扩展神经网络（Neural Network，NN）。虽然人们普遍认为GNN在实际任务中优于NN，但最近的工作发现了一组非平凡的数据集（异质图数据集），与NN相比，GNN的性能并不令人满意。异质性被认为是GNN性能不好的主要原因，并提出了许多工作来解决这一问题。在本文中，我们首先回顾了广泛使用的同质性度量指标，并指出它们只考虑图和标签的一致性是一个缺点。然后，我们从聚合后节点相似性的角度研究异质性，并定义了新的同质性度量指标，这些度量指标与现有度量指标相比具有潜在的优势。基于这一调查，我们证明了一些有害的图异质性情况可以通过局部多样化操作（local diversification operation）得到有效解决。然后，我们提出了自适应信道混合（Adaptive Channel Mixing, ACM），这是一个框架，可以灵活地针对每个节点（node-wisely）利用聚合、多样化和恒等通道，为不同节点的异质性情况提取更丰富的局部化信息。ACM比通常使用的单通道框架在异质图的节点分类任务上更强大，并且易于在现有GNN中实现。当在10个基准节点分类任务上进行评估时，ACM增强的基线一致地实现了显著的性能增益，在大多数任务上超过了最先进的GNN，而不会产生显著的计算负担。

Introduction

深度神经网络（NN）[22]已经彻底改变了许多机器学习领域，包括图像识别[21]、语音识别[13]和自然语言处理[2]，因为它们在从欧几里德数据学习潜在表示方面的有效性。最近的研究将重点转移到了非欧几里德数据[6]上，例如关系数据或图表。结合图信号处理和卷积神经网络[23]，已经提出了许多图神经网络（GNN）架构[38、10、15、40、19、29]，这些架构在基于图的机器学习任务（如节点分类、图分类、链路预测和图生成）方面的经验优于传统的NN，GNN建立在同质性假设的基础上[34]：连接的节点倾向于彼此共享相似的属性[14]，这提供了节点特征之外的额外信息。这种关系归纳偏差[3]被认为是导致GNN在许多任务中优于NN的关键因素。

然而，越来越多的经验证据表明，GNN与传统NN相比并不总是有利的。在某些情况下，即使是简单的多层感知器（MLP），在关系数据上也能比GNN表现出色[45,28,31,8]。一个重要的原因被认为是异质性问题： 同质性假设并不总是成立的，因此连接的节点实际上可能具有不同的属性。近来，异质性受到了很多关注，越来越多的模型被提出来解决这个问题[45、28、31、8、44、43、32、16、24]。在本文中，我们首先表明，仅考虑图和标签的一致性，现有的同态度量指标不能描述某些异质性对基于聚合的GNN的影响。我们提出了一个聚合后节点相似性矩阵，并在此基础上导出了新的同态度量，其优点在合成图上得到了说明（第3节）。然后，我们证明多元化经营有助于解决一些有害的异质性案例（第4节）。基于此，我们提出了自适应信道混合（ACM）GNN框架，该框架增强了单信道基线GNN，允许它们在每个层中自适应地、node-wisely和locally利用聚合、多样化和恒等通道。ACM显著提高了3个单通道基线GNN的性能2.04%∼ 在7个广泛使用的基准异亲图上，节点分类任务占27.5%，超过了SOTA模型（第6节）。对于3个同质图，ACM增强GNN的性能至少与单通道基线一样好，并且与SOTA相比具有竞争力。

贡献

1. 据我们所知，我们是第一个从聚合后节点相似性角度分析异质性的人。

2. 所提出的ACM框架与具有多个信道的自适应滤波器组和现有的用于异构的GNN有很大不同：1）传统自适应滤波器组信道[39]为每个滤波器使用标量权重，并且该权重由所有节点共享。相反，ACM提供了一种机制，使得不同的节点可以学习不同的权重，以利用来自不同信道的信息来解释不同的本地异质性；2） 与利用高阶滤波器和高频信号的全局特性的现有方法不同[45,28,8,16]，这些方法需要更多的计算资源，ACM通过自适应地仅考虑整个节点的局部信息成功地解决了异质性问题。

3. 与现有方法不同，现有方法试图促进具有高表达能力的滤波器的学习[45，44，8，16]，ACM的目标是，当给定具有一定表达能力的滤波器时，我们可以以某种方式从额外的信道中提取更丰富的信息，以解决异质性问题。这使得ACM更灵活，更易于实现。

同质性度量指标

文章的2.2节的公式3给出了现有的3种图同质性度量指标：edge homophily [1, 45], node homophily [35] and class homophily

3.1节中的图1给出了一个例子，这个例子证明了现有的同质性度量指标失效了。

作者提出的同质性度量指标

首先，定义聚合后节点相似矩阵（post-aggregation node similarity matrix）

然后，定义聚合相似性得分（aggregation similarity score）

然后再归一化到[0,1]

the graph (G) aggregation ( ˆ A) homophily and its modified version

Adaptive Channel Mixing (ACM)

这部分是论文的核心内容

在先前的工作[31,8,4]中，已经表明，可以通过高通滤波器（HP）提取的高频图信号在解决异质性方面是经验上有用的。在本节中，基于等式6中的相似度矩阵，我们从理论上证明了多样化操作，即高通滤波器，可以局部解决一些有害的异质性情况。此外，逐节点分析表明，不同的节点可能需要不同的过滤器来处理其邻居信息。基于上述分析，在第4.2节中，我们提出了自适应信道混合（ACM），这是一种3通道架构，可以自适应地利用聚合、多样化和恒等通道中的本地和节点信息 local and node-wise。

ACM中一共有3个通道，分别是 aggregation（低通滤波器，这个是现有GNN中广泛采用的，相当于Message Passing中的聚合操作，我认为也是GNN过平滑的原因）, diversification（多样化操作，其实就是高通滤波器，之前的论文发现高频成分对图的异质性是有帮助的，本文作者进行了理论证明） and identity （这个就是恒等，相当于全通滤波器，不进行任何变化）

本文ACM的思想和数字信号处理中的自适应滤波器非常像，目的都是自适应地对当前的输入配置不同参数的滤波器。在这里，每个不同的输入是节点，而因为每个节点具有不同的异质性，所以需要自适应。ACM自适应的方法是让模型学习到3个通道的权重系数，然后进行相加。

Diversification Helps with Harmful Heterophily

4.1节用图3展示了为什么高通滤波器有效果

可以看到，图3中右边的图的矩阵，有正有负，比较有区分度。而图3中间的矩阵，数值都比较均衡，看不出区分度，效果不好。因此，高通滤波器对异质性是有帮助的。

Filterbank and Adaptive Channel Mixing (ACM) Framework

4.2节介绍了图中的高通滤波器和低通滤波器的概念

2.1节的最后，作者说明了ACM中的高通和低通滤波器到底是哪个

可以看到，ACM的算法步骤并不是非常复杂，而且可以方便地插入到其他的GNN中。