点击上方 蓝字关注我们
题目：Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily
作者：王涛（天津大学）, 王锐（天津大学）, 金弟 (天津大学）, 何东晓（天津大学）, 黄禹霄(乔治华盛顿大学）
会议：The 36th AAAI Conference on Artificial Intelligence (AAAI-2022)
文章链接：https://github.com/hedongxiao-tju/HOG-GCN
代码链接：https://github.com/hedongxiao-tju/HOG-GCN
1. 内容简介
图卷积神经网络 (Graph Convolutional Network) 因其在处理图结构数据方面的强大能力而被广泛应用于各个领域。经典的 GCN 及其变体主要基于同质性假（Homophily Assumption）设计，即图中相同类型的节点倾向于相互连接。而该假设忽略了存在于现实世界网络中的异质性（Heterophily），即网络中不同类型的节点倾向于相互连接的性质。现有方法主要通过聚合高阶邻居或聚合中间表征来处理异质性，这会导致结果中产生噪声和不相关的信息。最重要的是，这些方法并没有改变基于同质假设而设计的传播机制（这是 GCN 的基本部分），这使得不同类型节点的表示之间难以区分。为了解决该问题，本文设计了一种新的传播机制，可以根据节点对之间的同质性或异质性自适应的改变传播和聚合过程。为了自适应地学习传播过程，我们引入了节点对之间的同质性度量（Homophily Degree），该度量融合了拓扑和属性信息。我们将可学习的同质性程度矩阵纳入到图卷积框架中，通过端到端的训练，使该模型能够超越同质性假设。我们从理论上证明了我们的模型可以根据节点之间的同质性来约束节点之间表征的相似性。在七个真实世界数据集上的实验表明，这种新方法在异质性或低同质性的数据集上的表现优于现有的代表性方法，并在同质数据集上也获得了有竞争力的性能。
2.方法
为了让 GCN 的传播机制能够同时适用于同质性和异质性，我们提出了一种新的同质性指导的图卷积框架HOG-GCN。该框架可以根据节点对之间的同质性程度来自动的学习传播过程。从直觉来说，类内标签之间的影响应该大于类间标签之间的影响。因此我们在传播过程中引入同质性程度矩阵，将其合并到图卷积框架中，进行在同质性指导下的传播，从而使框架能够根据邻域间的同质性程度自适应地改变特征传播权值。下图是模型的框架图。模型主要包含两个模块：同质性程度矩阵估计以及同质性引导的特征传播。
2.1 同质性程度矩阵估计（Homophily Degree Matrix Estimation）
在半监督任务下，只有部分标签信息可用，很难直接从节点标签中计算出同质性程度。为此，我们考虑分别从属性空间和拓扑空间估计节点对之间的同质性，然后将其结合。
属性同质性估计
估计过程利用不使用拓扑信息的多层感知机（Multi-Layer Perceptron）：
标签初步预估使用如下损失得到：
theta_m是最小化该损失的MLP全部参数。
根据标签B，我们可以计算出两个节点属于同一类的可能性，称为同质性程度矩阵：
拓扑同质性估计
经典的标签传播方法对第l次迭代的标签传播的定义如下（基于同质性假设）：
为了超越同质性假设，我们使用广义标签传播来估计拓扑空间中的同质性程度矩阵。先在网络的k阶结构上进行标签传播，以捕获更多同质性节点：
其中T*是使上方广义标签传播来预测标签的损失最小化的最优边权值。
将属性空间和拓扑空间估计的同质性程度矩阵与可调节超参数结合得到：
H即为同质性程度矩阵。
2.2 同质性指导下的传播（Homophily-guided Propagation）
得到了同质性程度矩阵后，我们将其作为指导，来自适应地学习同质性和异质性的传播过程。同质性程度矩阵表示两个节点属于同一类的程度，其可以反映网络的同质性或异质性的潜在分布。因此，我们将可学习的同性度矩阵合并到图卷积框架中，根据同性度自动改变邻域之间的传播权值。下式给出了HOG-GCN在第l次迭代中的特征传播过程：
2.3 优化目标（Optimization Objective）
整个框架由同质性程度矩阵估计和同质性指导下的传播两个部分组成。第一部分包含MLP和广义标签传播。前文已经给出了MLP和广义标签传播的目标函数：
在第二部分中，我们将同质性程度矩阵整合到图卷积框架当中。将图卷积运算的所有参数表示为Theta_g，然后根据HOG-GCN的最终输出Z得到最优的Theta_g*：
在传播过程中，同质性程度矩阵从属性和拓扑信息中学习得到，并进一步用于特征传播。传播过程反过来可以帮助学习更好的同质性程度矩阵。这两个部分相互增强，将3个目标损失函数结合起来，可以以端到端的方式训练整个过程：
其中λ和γ为超参数，用来调节3个损失的比重。
2.4 理论分析（Theoretical Analysis）
我们证明了HOG-GCN可以根据k阶邻域内节点之间的同质性来约束节点之间表示的相似性。也就是说，同质性程度较高的节点具有更相似的表示，即HOG-GCN的传播过程可以视为最小化下面的目标函数：
可以用下式来迭代近似：
若忽略非线性，即为HOG-GCN的聚合函数。
3.实验
本文在七个真实图数据集上进行了结点分类实验。数据集的统计信息如下：
节点分类结果
本文在七个数据集上进行了节点分类实验，结果如下：
可视化结果
本文在Citeseer数据集上进行了节点可视化实验，结果如下：
5.总结
本文提出了一种新的同质性指导传播的图卷积网络，该网络可以同时适用于同质性和异质性的网络。我们将一个可学习的同质性程度矩阵纳入图卷积框架，以建模网络的同质性和异质性，并根据节点对之间的同质性程度进一步自适应地改变传播过程。通过下游的半监督任务，传播过程反过来可以进一步帮助学习同相度矩阵。这两个过程可以相互增强并且共同训练。在七个真实世界数据集上的实验表明，该方法在异质性下优于现有方法，在同质性下获得了有竞争力的性能。
