ICML  2022 | Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

文章信息

「来源」：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
「标题」：Finding Global Homophily in Graph Neural Networks When Meeting Heterophily
「作者」：Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, Weining Qian
「链接」：https://proceedings.mlr.press/v162/li22ad.html

内容简介

本文研究了具有异亲性的图上的图神经网络。现有的一些方法用多跳邻居放大一个节点的邻域，以同构的方式包含更多的节点。然而，为不同的节点设置个性化的邻域大小是一个重大的挑战。此外，对于邻域中排除的其他同源节点，为了进行信息聚合而忽略它们。针对这些问题，本文提出了两个模型GLOGNN和GLOGNN++，通过聚合图中全局节点的信息来生成节点的嵌入。在每一层中，两个模型都学习一个系数矩阵来捕捉节点之间的相关性，并在此基础上进行邻域聚集。系数矩阵允许符号值，并从具有闭式解的优化问题中导出。本文进一步加速了邻域聚集，并导出了线性时间复杂度。通过证明系数矩阵和生成的节点嵌入矩阵都具有预期的分组效果，从理论上解释了模型的有效性。本文进行了广泛的实验，将所提模型与其他11个竞争对手在15个基准数据集上在广泛的领域、尺度和图的异质性中进行比较。实验结果表明，本文的方法取得了较好的性能，也是非常有效的。

本文提出了一种有效的、可扩展的GNN模型，即GLOGNN。在L-卷积层中，受线性子空间模型（Liu et al.，2012)的启发，用图中的所有节点来线性刻画每个节点，并导出一个系数矩阵，使得 描述节点 对节点 的重要性。本文把刻画问题表述为一个对有闭式解的优化问题。然后，以为权重矩阵，聚合全局节点的信息，生成节点嵌入矩阵。注意，直接计算这种基于和的邻域聚集导致三次和二次时间复杂度。因此，避免了直接计算和在邻域聚集中对矩阵乘法重新排序，有效地将时间复杂度降低到线性。最后，从数学上证明了和生成的节点嵌入矩阵都具有分组效应（Lu et al.，2012)，即对于图中的任意两个节点，无论它们有多远，如果它们具有相似的特征和局部结构，它们的嵌入向量都将彼此接近。这有助于解释我们模型的有效性。

「本文的主要贡献」

• 本文提出了两个有效的GNN模型GLOGNN和GLOGNN++。
• 本文从理论上证明了和生成的节点嵌入矩阵都具有分组效应。
• 由于允许符号值，在邻域聚合中结合了低通和高通卷积滤波器。
• 在15个不同领域、大小和图的异质性的基准数据集上，展示了本文的模型与其他11种方法相比的优越性。

算法

本文首先展示了如何捕获节点相关性，并推导出每一层的系数矩阵。然后介绍了如何在的基础上加速邻域聚集，进一步从理论上证明了和都具有预期的聚类效果。最后对Glognn进行了总结，并将模型升级到Glognn++。下图给出了Glognn的总体框架。：

系数矩阵

在具有异亲性的图中，连通的结点更有可能具有不同的标记，而距离较远的结点可能来自同一个类。因此，必须扩大节点的邻域，以利用更远的节点。一个简单的方法是使用图中的所有节点。受线性子空间模型（Liu et al.，2012)的启发，用图中的所有节点来刻画每个节点。具体来说，在第L层，可以确定一个系数矩阵:

其中是噪声矩阵。人们可以将解释为反映节点如何表征的值，因此扮演了权重矩阵的角色。注意，允许有符号的值。

聚合加速

基于，可以在第层编写邻域聚合：

然而，由于计算的三次时间复杂度和计算的二次时间复杂度，用上式直接更新是不可行的。为了加速的更新，而不是直接计算，可以将上式转换为：

其中：

GloGNN++

给定，系数矩阵起着“纵向”注意的作用，它表征了一个节点对另一个节点的重要性。在邻域聚合中，不仅节点邻域的重要性不同，隐藏特征的重要性也不同。例如，在节点分类中，节点标签的不平衡会导致不同标签对应的隐藏特征的重要性不同。因此，进一步升级模型，考虑“水平”注意。本文引入了一个对角矩阵，使得描述了中第维的重要性:

并导出最优解:

实验分析

下表总结了所有方法在15个基准数据集上的性能结果。

可以得出以下结论：

• 仅使用节点特性的MLP在一些具有较大异质性的数据集上表现出奇地好，如actor。这说明了节点特征对于异亲图中节点分类的重要性。
• 与普通GNN模型GCN和GAT相比，MIXHOP和GCNII总体表现更好。一方面，MixHop利用节点的多跳邻居放大了节点的邻域。这为节点引入了更多的同源邻居。另一方面，GCNII中的初始残差和身份映射机制隐式地结合了中间节点表示来提高模型的性能。
• 虽然H2GCN、WRGAT和GGCN在小规模数据集上可以获得良好的性能，但由于OOM错误，它们无法在超大规模数据集上运行。这阻碍了这些模型的广泛应用。对于ACM-GCN和LinkX，它们不能始终如一地提供优越的结果。例如，LinkX在大规模数据集上排名第三，但在小规模数据集上表现不佳（排名第八）。ACM-GCN是得克萨斯上的赢家，但它在POKEC上的精度得分仅为0.6381（最好成绩为0.8305）。虽然GPR-GNN同时利用了低通和高通滤波器，但它在每一层中只使用一种卷积滤波器，这限制了它的有效性。
• Glognn++在所有数据集上的平均排名第一，而Glognn是亚军。这表明，这两种方法都可以在广泛的多样性范围内对数据集始终如一地提供优越的结果。一方面，这两种方法都学会了利用更多具有同源性的邻居进行节点邻域聚合。这提高了模型的性能。另一方面，Glognn++进一步学习节点隐藏特征的重要性，提高了分类精度。

总结

本文将GNNS推广到具有异亲性的图。本文提出了GLOGNN和GLOGNN++，它们通过聚合图中全局节点的信息来生成节点的嵌入。在每一层中，本文提出一个优化问题，导出了一个描述节点之间关系的系数矩阵。然后基于进行邻域聚集。本文通过矩阵乘法重排序来加速聚集过程。本文从数学上证明了和生成的节点嵌入矩阵都具有预期的分组效果，从而解释了模型的有效性。本文进行了广泛的实验来评估我们的模型的性能。实验结果表明，本文的方法在15个不同异质度的数据集上优于其他11个竞争对手；它们也是高效的，收敛速度非常快。