KDD20 | AM-GCN：自适应多通道图卷积网络

2020 年 8 月 26 日 专知

作者：北邮 GAMMA Lab 硕士生朱美琪

题目：AM-GCN: Adaptive Multi-channel Graph Convolutional Networks

会议：ACM SIGKDD 2020

论文链接：http://shichuan.org/doc/86.pdf

代码与数据：https://github.com/zhumeiqiBUPT/AM-GCN

图卷积网络(GCNs)在处理图和网络数据的各种分析任务中得到了广泛的应用。然而，最近的一些研究也陆续针对GCNs的机制提出了一些质疑：GCNs能否在一个具有丰富信息的复杂图中最优地对节点特征和拓扑结构进行融合？本文首先对GCNs融合能力进行了实验探究。令人惊讶的是，我们的实验结果清楚地表明，最先进的GCNs融合节点特征和拓扑结构的能力远远达不到最优甚至令人满意的水平。而相对应的，由于GCNs不能自适应地学习拓扑结构与节点特征之间的深度相关性信息，因此在一些分类任务中，该弱点可能会严重阻碍GCNs的表达能力。因此我们的工作对“能否弥补不足，设计出一种新型的GCNs类模型，既能保留现有GCNs的优点，又能大幅度提高拓扑结构与节点特征的融合能力？”该问题进行了深入研究。针对存在的一些挑战，我们提出了一种用于半监督节点分类任务的自适应多通道图卷积网络(AM-GCN: Adaptive Multi-channel Graph Convolutional Networks)。其核心思想是能够同时从节点特征、拓扑结构及其组合中提取特殊嵌入项和公共嵌入项，并利用注意机制学习嵌入项的自适应融合权重。我们通过数据集上的大量实验表明，AM-GCN能够自适应地提取最相关的信息，并提高了分类精度与实验效果。

1 引言

图卷积网络(Graph Convolutional Networks, GCNs)作为一种学习图结构数据的神经网络，在处理图数据分析问题上表现出了极大的人气，被用于如节点分类、图分类、链路预测、推荐等任务中。典型的GCN及其变体通常采用消息传递方式，其关键步骤是特征聚合，即一个节点在每个卷积层中聚合来自其拓扑邻居的特征信息。这样，特征信息通过网络拓扑结构传播到邻居节点表示中，然后通过学习所有节点嵌入表示用于下游任务如分类等，该学习过程是由部分节点标签来监督的。实际上，GCNs能够取得巨大的成功部分归功于它提供了一种拓扑结构和节点特征的融合策略来学习节点表示，而这种融合策略的学习训练过程由一个端到端的模型框架来监督。

这里我们首先思考了一个问题：作为端到端框架的GCNs，从拓扑结构和节点特征中真正学习和融合了什么样的信息? 在第二小节我们通过实验设计评估了GCNs融合拓扑结构和节点特征的能力。实验结果表明，GCNs在融合网络拓扑结构和节点特征上能力上与最理想的水平相差甚远。即使在一些简单的情况下（节点的特性/拓扑与节点标签的关联是非常明确的）GCN仍不能自适应地融合节点特性和拓扑结构并提取最相关的信息。而无法自适应学习到拓扑结构、节点特征与最终任务之间最相关的信息，可能会严重阻碍GCNs在分类任务中的表现能力，并且由于实际应用中图数据与任务之间的相关性往往非常复杂且不可知，因此自适应能力也是很重要的。

针对这些问题，我们提出了一种灵活地用于半监督节点分类的自适应多通道图卷积网络方案。其核心思想是同时学习基于节点特征、拓扑结构及其组合的节点嵌入，并依据特征与结构之间的相似性对标签预测的作用往往是互补的这一事实，采用设计的自适应融合机制来获取对分类任务最有帮助且最深层次的相关信息。

2 GCN融合能力的实验探究

本节中我们使用两个简单但直观的例子来验证GCNs能否自适应地将图的节点特征和拓扑结构融合在一起，并用于分类任务。主要思想是我们分别生成与节点标签之间具有网络拓扑高相关性和节点特征高相关性的两种数据分布，然后检查GCNs在这两个简单直观的情况下性能是否依旧理想。如果GCNs性能与基准模型相比下降，则证明GCNs并不能自适应地从节点特征和拓扑结构中提取信息，即使是在二者与节点标签之间有很直接的高相关性的情况下。

2.1 案例一：随机的拓扑结构与相关的节点特征

我们生成了一个900点的结构随机网络，然后给900个节点随机分配3类标签，并将有相同标签的节点使用同一个高斯分布来生成他们的特征。在该数据集中，节点标签与节点特征高度相关，而与拓扑结构基本无关。接着我们对比GCN与MLP的节点分类准确率分别为75.2%和100%。

对该结果分析：由于节点特征与节点标签高度相关，因此直接对特征利用MLP进行分类就能够表现出良好的性能。而由于GCN从节点特征和拓扑结构中同时提取信息，但不能自适应地根据任务来融合与选择它们，因此GCN的效果大幅下降。

2.2 案例二：相关的拓扑结构和随机的节点特征

我们生成另外一个900个节点的网络，此时特征是完全随机生成的，而拓扑结构上我们将节点划分为3个社区，并且在这个数据集中，节点标签由社区决定，即同一社区的节点具有相同的标签。我们对比GCN和DeepWalk的节点分类准确率为87%和100%。

对该结果分析：DeepWalk只对此数据的网络拓扑结构进行了全面的建模。而GCN从节点特征和拓扑结构中同时提取信息，但不能自适应地根据任务进行选择融合，因此在这种情况下GCNs无法达到DeepWalk的高性能。

3 方法

图1：AM-GCN模型框架

为了充分铺捉到特征空间中的结构信息，我们使用由节点特征生成的k近邻图作为特征结构图 (Feature Graph)。通过同时利用特征图 (Feature Graph) 和拓扑图 (Topology Graph)，我们将节点特征传播到拓扑空间和特征空间，并利用两个特殊的图卷积模块 (Specific Convolution) 在这两个空间中提取两个特殊的嵌入。考虑到两个空间之间有存在共同特性的可能，我们设计了一个具有参数共享策略的公共图卷积模块 (Common Convolution) 来提取它们共有的嵌入。然后我们进一步利用注意机制 (Attention Mechanism) 来自动学习不同嵌入的重要性权重，从而自适应地融合它们。通过这种方式，节点标签能够监督学习过程，自适应调整权重，提取出图数据中与任务相关性最强的信息。此外，我们设计了一致性约束 (Consistency Constraint) 和差异性约束 (Disparity Constraint)，以确保所学习的节点表示的一致性和差异。

3.1 特殊卷积模块

首先，为了捕获特征空间中节点的结构特性，我们基于节点特征矩阵构造一个近邻图，其中为近邻图的邻接矩阵。在特殊图卷积模块，对于输入图第层的输出可以表示为：

并把该GCN的最后一层输出记为。同样的，对于拓扑空间，我们使用原始输入图，这里，并且基于拓扑的学习输出嵌入的计算方法与特征空间的计算方法相同。

3.2 公共卷积模块

我们利用一个具有参数共享的公共卷积模块来实现两个空间的嵌入共享。首先，我们抽取拓扑图的共享节点表示：

这里是第层的权重，是拓扑图在公共卷积模块上的上一层输出，且。然后，我们使用同样的共享权中矩阵，并输入特征图：

利用公共卷积模块可以在两个空间中过滤出共享特征，根据不同的输入图，我们可以得到两个输出表示和，并将这两个空间的公用的嵌入表示为。

3.3 注意力机制

最后，基于这些所学的表示，我们使用注意力融合机制来自动学习不同嵌入表示的权重，以便可以自适应的融合这些信息：

其中， , , 分别表示自适应学习得到的对应权重。并且有：

3.4 优化目标

3.4.1 一致性约束

对于公共图卷积模块两个输出嵌入项和，尽管他们具有共享的权重矩阵，这里我们仍通过约束两个相似性矩阵和相近来作为一致性约束：

3.4.2 差异性约束

和表示是以相同的图作为输入学习的，为了确保它们能够捕获不同的信息，我们使用Hilbert-Schmidt独立性准则(HSIC)来增强这两个表示的差异，这是一种简单而有效的独立性度量方法。

并且差异性约束为：

3.4.3 目标函数

我们最终的任务是半监督节点分类任务，使用AM-GCN的输出获得最终预测的标签计算交叉熵损失作为任务损失。最终的优化目标函数为：

其中和分别为两个约束对应的超参数。

4 实验

本文在六个真实数据集上分别进行了节点分类，变体分析，注意力机制分析，可视化，参数分析等实验分析。实验数据参数如下：

表1：实验数据集信息

4.1 节点分类实验

表2：节点分类实验结果。黑色加粗表示最高值，下划线表示第二高值

4.2 变体分析实验

图2：AM-GCN变体（不使用约束/仅使用一致性约束/仅使用差异性约束）节点分类结果对比

4.3 注意力机制分析

图3：拓扑嵌入、公共嵌入、特征嵌入学得的注意力分布结果

4.4 可视化实验

图4：BlogCatalog数据集的可视化结果

5 总结

本文对GCN对拓扑结构与节点特征的融合机制进行了重新思考，并通过实验发现其与理想的融合机制还相差甚远。基于这一重要问题，我们研究了如何自适应地从拓扑结构和节点特征中获取最相关的信息，并将这些信息融合到分类中，因此提出了一种自适应多通路模型AM-GCN，来同时学习拓扑结构信息和特征结构信息并自适应融合。通过在6个真实世界数据集上的大量实验证明了AM-GCN的性能。

本期责任编辑：杨成

本期编辑：刘佳玮

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：王啸、杨成

编辑：刘佳玮

副编辑：郝燕如，纪厚业

长按下图并点击“识别图中二维码”

即可关注北邮 GAMMA Lab 公众号