AM-GCN

《AM-GCN:Adaptive Multi-channel Graph Convolutional Networks》
论文题目：自适应多通道图形卷积网络

摘要

提出的问题：

  • GCNs是否能将节点特征和拓扑结构最优地整合在一个信息丰富的复杂图形中。

调查的结果：

  • 最新的GCN在融合节点特征和拓扑结构方面的能力与最佳甚至令人满意的目标相去甚远。 该弱点可能会严重阻碍某些分类任务中GCN的功能，因为GCN可能无法自适应地学习拓扑结构和节点特征之间的某些深层相关信息。

面临的挑战：

  • 是否可以弥补这一弱点并设计出一种新型的GCN，这些GCN既可以保留最新的GCN的优势，又可以大大增强融合拓扑结构和节点特征的能力？

解决方法:

  • 本文提出了一种用于半监督分类的自适应多通道图卷积网络（AM-GCN）
  • AM-GCN中心思想是，从节点特征，拓扑结构及其组合中同时提取特定的嵌入和常见的嵌入，并使用注意力机制来学习嵌入的自适应重要性权重。
  • 本文在基准数据集上进行的广泛实验清楚地表明，AM-GCN从节点特征和拓扑结构中提取出最相关的信息，并以明显的余量提高了分类精度。

介绍

图卷积网络（GCN），一种整个过程部分受节点标签的监督。GCN的巨大成功部分归功于GCN提供了一种拓扑结构和节点特征的融合策略以学习节点嵌入，并且融合过程受到了端到端的监督 学习框架。设计用于学习图数据的神经网络，在解决图分析问题方面表现出了很高的知名度，例如节点分类[1,31]，图分类[7,37]，链接预测[13，36]和推荐[6,34]。
典型的GCN [14]及其变量[11,16,27,30,36]通常遵循消息传递方式。 关键步骤是特征聚合，即节点在每个卷积层中聚合来自其拓扑邻居的特征信息。 这样，特征信息通过网络拓扑传播到节点嵌入，然后将这样学习的节点嵌入用于分类任务。整个过程部分受节点标签的监督。GCN的巨大成功部分归功于GCN提供了一种拓扑结构和节点特征的融合策略以学习节点嵌入，并且融合过程受到了端到端的学习框架的监督。
但是，最近的一些研究揭示了最新的GCN在融合节点特征和拓扑结构方面的某些弱点。 例如，Li等。 [15]表明，GCN实际上对节点特征执行拉普拉斯平滑化，并使嵌入网络的节点逐渐收敛。Nt和Maehara [20]和Wuet等[30]证明拓扑结构起着低通的作用。 当特征信息通过网络拓扑结构传播时，对节点特征进行过滤。 高等。 [8]在GCN中设计一个条件随机字段（CRF）层，以明确保留节点之间的连接性。
GCNs从拓扑结构和节点特征中真正学习和融合了哪些信息?这是一个基本的问题。GCNs经常被用作端到端的学习框架。正确回答这个问题，有助于我们有原则地理解GCNs的能力和局限性。这立即激励了我们的学习。

本文的贡献：

  • 我们通过实验评估了GCNs融合拓扑结构和节点特征的能力，并指出了GCN的不足之处。我们进一步研究了如何大幅度提高GCN的融合能力进行分类的问题。
  • 我们提出了一种新的自适应多通道GCN框架AM-GCN，它在拓扑空间和特征空间上执行图的卷积操作。结合注意机制，可以充分融合不同的信息。
  • 我们在一系列基准数据集上进行的大量实验清楚地表明，AM-GCN的性能优于目前最先进的GCNs，并且能够很好地从节点特征和拓扑结构中提取出最多的相关信息，用于具有挑战性的分类任务。

GCNs的融合能力：实验调研

在本节中，我们使用两个简单而直观的案例来检查最新的GCN是否可以从图中的节点特征和拓扑结构中自适应学习，并将它们充分融合以用于分类任务。
主要思想是，我们将清楚地分别建立具有网络拓扑的节点标情况1：随机拓扑和相关的节点特征
签和节点特征之间的高度相关性，然后我们将检查这两种简单情况下GCN的性能。 良好的GCN融合能力应在节点标签的监督下自适应地提取相关信息，从而获得良好的结果，但是，如果性能与基线相比急剧下降，则表明GCN无法从节点特征和拓扑中自适应地提取信息。 结构，即使节点特征或带有节点标签的拓扑结构之间也具有高度相关性。

情况1：随机拓扑和相关的节点特征

我们生成了一个由900个节点组成的随机网络，其中在任意两个节点之间构建边缘的概率为0.03。 每个节点都有一个50维的特征向量。 为了生成节点特征，我们为900个节点随机分配了3个标签，对于具有相同标签的节点，我们使用一种高斯分布来生成节点特征。 这三类节点的高斯分布具有相同的协方差矩阵，但三个彼此远离的不同中心。 在此数据集中，节点标签与节点特征高度相关，但与拓扑结构无关。

我们应用GCN [14]训练此网络。对于每个类，我们随机选择20个节点进行训练，另外选择200个节点进行测试。 我们仔细调整超参数以报告最佳性能，并避免过度平滑。 另外，我们仅将MLP [21]应用于节点特征。 GCN和MLP的分类准确度分别为75.2％和100％。
结果符合预期。 由于节点特征是与所述节点的标签高度相关的，MLP显示出优异的性能。 GCN从节点特征和拓扑结构中提取信息，但是无法自适应地融合它们以避免拓扑结构的干扰。 它无法比拟的MLP的高性能。

情况2：相关的拓扑和随机节点特征

我们生成另一个具有900个节点的网络。 这一次，将随机生成50个维中的每个维的节点特征。 对于拓扑结构，我们采用随机块模型（SBM）[12]将节点分为3个社区（分别为节点0-299、300-599、600-899）。 在每个社区内，建立边缘的概率设置为0.03，在不同社区的节点之间建立边缘的概率设置为0.0015。 在此数据集中，节点标签由社区确定，即，同一社区中的节点具有相同的标签。
同样，我们将GCN应用于此网络。 我们还将DeepWalk [22]应用于网络拓扑，也就是说，DeepWalk会忽略这些功能。 GCN和DeepWalk的分类准确度分别为87％和100％。
DeepWalk表现出色，因为它可以对网络拓扑结构进行全面建模。 GCN从节点特征和拓扑结构中提取信息，但是无法自适应地融合它们，以避免受到节点特征的干扰。 它无法比拟DeepWalk的高性能。

总结

这些情况表明，目前的GCN融合机制[14]远未达到理想甚至令人满意的程度。 即使节点标签与网络拓扑或节点特征之间的相关性很高，当前的GCN也无法充分利用节点标签的监督来自适应地提取最相关的信息。 但是，实际情况更加复杂，因为很难知道拓扑或节点特征是否与最终任务更加相关，这促使我们重新考虑当前的GCN机制。

AM-GCN: THE PROPOSED MODEL

Problem Settings

我们将重点放在属性图$G =（A，X）$上的半监督节点分类中，

  • $A\in \mathbb R^{n×n}$是具有$n$个节点的对称邻接矩阵
  • $X\in \mathbb R^{n×d}$是节点特征矩阵，$d$是节点特征的维数。

具体来说，$A_{ij} = 1$表示节点$i$和$j$之间存在一条边，否则，$A_{ij} = 0$。
我们假设每个节点都属于$C$中的一个类。

AM-GCN 的整体框架

image.png

关键思想：

  • AM-GCN不仅允许节点特征在拓扑空间中传播，而且还可以在特征空间中传播，并且应该从这两个空间中提取与节点标签最相关的信息。
  • 我们基于节点特征$X$构造了一个特征图。然后，通过两个特定的卷积模块，$X$能够在特征图和拓扑图上传播，以分别学习两个特定的嵌入$Z_F$和$Z_T$。
  • 此外，考虑到这两个空间中的信息具有共同的特征，我们设计了一个具有参数共享策略的共同卷积模块，以学习共同的嵌入$Z_{CF}$和$Z_{CT}$，并且一致性约束$\mathcal L_c$用于增强$Z_{CF}$和$Z_{CT}$的“公共”属性。
  • 此外，视差约束$\mathcal L_d$是为了确保$Z_F$和$Z_{CF}$之间以及$Z_T$和$Z_{CT}$之间的独立性。 考虑到节点标签可能与拓扑或特征或两者相关联，AM-GCN利用注意力机制将这些嵌入与学习的权重进行自适应融合，从而提取出最相关的信息$Z$进行最终分类任务。

Specific Convolution Module

首先，为了捕获特征空间中节点的底层结构，我们基于节点特征矩阵$X$构造了一个$k$最近邻（kNN）图$G_f =(A_f，X)$，其中$A_f$是$kNN$图的邻接矩阵。 具体来说，我们首先计算n个节点之间的相似度矩阵$S \in \mathbb R^{n×n}$。

得到$S$的两种方法：【其中$x_i$和$x_j$是节点$i$和$j$的特征向量】

  1. Cosine Similarity（余弦相似度）
    它使用两个向量之间的角度的余弦值来测量相似度：
    $$
    S_{ij} = \frac{x_i \cdot x_j}{|x_i||x_j|}
    $$

  2. Heat Kernel（热核）
    $$
    S_{ij} = e^{- \frac{\lVert x_i-x_j \rVert ^2}{t}}
    $$

    • 其中t是热传导方程中的时间参数，取t=2.

本文统一选择余弦相似度来获得相似度矩阵$S$，然后为每个节点选择top $k$个相似节点对来设置边，最终得到邻接矩阵$A_f$。
然后使用特征空间中的输入图$（A_f，X）$，第$l$层输出$Z^{（l）}_f$可以表示为：
$$
Z^{(l)}_f = ReLU(\tilde D_f^{- \frac{1}{2}} \tilde A_f \tilde D_f^{- \frac{1}{2}} Z^{(l-1)}_f W^{(l)}_f)
$$

  • $W^{(l)}_f$是GCN中第l层的权重矩阵（weight matrix）
  • ReLU是ReLU激活函数
  • 初始化$Z^{(0)}_f = X$
  • $\tilde A_f = A_f + I_f$和$\tilde D_f$是$\tilde A_f$的对角度矩阵(diagonal degree matrix)
  • 表示最后一层的输出嵌入作为$Z_F$

用上面的方式，可以学习到能够在特征空间中捕获到特殊的信息$Z_F$的节点嵌入；
对于拓扑空间，原始的输入图$G_t = (A_t,X_t)$，其中$A_t = A$和$X_t = X$；
将基于拓扑图的嵌入$Z_T$的学习输出嵌入可以在特征空间中以相同的方式计算。因此，可以提取出拓扑空间中编码的特定信息。

Common Convolution Module

存在的问题：

  • 事实上，特征空间和拓扑空间不是完全相关的；
  • 节点分类任务基本上可能与特征空间、拓扑空间或两者都存在关联，这是很难预先知道的。因此，我们不仅需要提取这两个空间中嵌入的特定节点，还需要提取这两个空间共享的公共信息。这样，任务就可以更加灵活地确定哪一部分信息是最相关的。

本文的解决方法：

  • 设计了一个具有参数共享策略的公共gcn，使嵌入共享到两个空间中。

过程：

  1. 首先，我们从拓扑图$(A_t,X)$中使用Common-GCN来提取节点嵌入$Z^{(l)}{ct}$
    $$
    Z^{(l)}    {ct} = ReLU(\tilde D_t^{- \frac{1}{2}} \tilde A_t \tilde D_t^{- \frac{1}{2}} Z^{(l-1)}_{ct} W_c^{(l)})
    $$
    • $W_c^{(l)}$ 是Common-GCN的第l层的权重矩阵(weight matrix)
    • $Z^{(l-1)}{ct}$ 是第l-1层的节点嵌入，且$Z^{(0)}{ct} = X$
  2. 利用Common-GCN从特征图(feature graph)$(A_f,X)$中学习节点嵌入,为了提取共享信息，本文对每一层Common-GCN共享相同的权值矩阵$W_c^{(l)}$
    $$
    Z^{(l-1)}_{ct} = ReLU(\tilde D_f^{- \frac{1}{2}} \tilde A_f \tilde D_f^{- \frac{1}{2}} Z^{(l-1)}_f W^{(l)}_c)
    $$
    • $Z^{(l-1)}_{cf}$ 是第l-1层的节点嵌入，且$Z^{(0)}_f = X$
  3. 共享权矩阵(shared weight matrix)可以过滤出两个空间中的共享特征。根据不同的输入图形，我们可以得到两个输出嵌入$Z_CT$和$Z_CF$，两个空间的共同嵌入$Z_C$为:
    $$
    Z_C = (Z_{CT} + Z_{CF})/2
    $$

Attention Mechanism

现在我们有两个特定的嵌入$Z_T$和$Z_F$，和一个常见的嵌入$Z_C$。考虑到节点标签可以与其中一个甚至是它们的组合关联，我们使用注意机制$att(Z_T, Z_C, Z_F)$来了解它们对应的重要性$(\alpha_t,\alpha_c,\alpha_f)$:
$$
(\alpha_t,\alpha_c,\alpha_f) = att(Z_T,Z_C,Z_F)
$$

  • $\alpha_t,\alpha_c,\alpha_f \in \mathbb R^{n \times 1}$表示嵌入$Z_T、Z_C、Z_F$的n个节点的注意值

这里我们关注节点$i$，它嵌入在$Z_T$中的是$z^i_T \in \mathbb R^{1 \times h}$(即$Z_T$的第$i$行).本文首先通过非线性变换对嵌入进行变换，然后使用一个共享的注意向量$q \in \mathbb R^{h’ \times 1}$去获得注意力值$\omega^i_T$
$$
\omega^i_T = q^T \cdot tanh(W \cdot (z^i_T)^T + b)
$$

  • $W \in \mathbb R^{h’ \times h}$ 是weight matrix
  • $b \in \mathbb R^{h’ \times 1}$ 是bias vector（偏差向量）

类似的，我们可以从嵌入矩阵$Z_C$和$Z_F$获取节点$i$的注意力值$\omega^i_C$和$\omega^i_F$。本文使用softmax函数去归一化注意力的值$\omega^i_T \omega^i_C, \omega^i_F$从而获得最终的权重。
$$
\alpha^i_T = softmax(\omega^i_T) = \frac{exp(\omega^i_T)}{exp(\omega^i_T)+exp(\omega^i_C)+exp(\omega^i_F)}
$$

  • $\alpha^i_T$越大，对应的嵌入越重要。
  • $\alpha^i_C = softmax(\omega^i_C)$,$\alpha^i_F = softmax(\omega^i_F)$

对于所有的n节点，我们学习的权重$\alpha_t=[\alpha^i_T],\alpha_c=[\alpha^i_C],\alpha_f=[\alpha^i_F] \in \mathbb R^{n \times 1}$,并且表示$\alpha_T = diag(\alpha_t)$,$\alpha_C = diag(\alpha_c)$和$\alpha_F = diag(\alpha_f)$，然后我们结合这三个嵌入来得到最终的嵌入$Z$:
$$
Z = \alpha_T \cdot Z_T + \alpha_C \cdot Z_C + \alpha_F \cdot Z_F
$$

Objective Function(目标函数)

Consistency Constraint（一致性约束）

对于两个输出嵌入Common-GCN的$Z_{CT}$和$Z_{CF}$，虽然Common-GCN的权值矩阵是共享的，但是这里我们设计了一个一致性约束来进一步增强它们的通用性。

  1. 首先用l2归一化的方法将嵌入矩阵归一化为$Z_{CTnor}, Z_{CFnor}$。
  2. 然后，这两个归一化矩阵可以用来捕获n个节点的相似度，如$S_T$和$S_F$
    $$
    S_T = Z_{CTnor} \cdot Z_{CTnor}^T \
    S_F = Z_{CFnor} \cdot Z_{CFnor}^T
    $$
    一致性意味着两个相似矩阵应该是相似的，这就产生了下面的约束:
    $$
    \mathcal L_c = \lVert S_T - S_F \rVert ^2_F
    $$

Disparity Constraint（视差约束）

这里因为嵌入$Z_T$和$Z_{CT}$是从相同图$G_t = (A_t,X_t)$中学习得到,为了确保他们能捕获不同的信息，本文应用Hilbert-Schmidt Independence Criterion (HSIC)【一个简单而有效的独立措施，以增强这两个嵌入的差距】

$Z_T$和$Z_{CT}$的HSIC约束
$$
HSIC(Z_T,Z_{CT}) = (n-1)^{-2} tr(RK_T RK_CT)
$$

  • $K_T$ 是$k_{T,ij} = k_T(z^i_T,z^j_T)$的 Gram matrices
  • $K_CT$ 是$k_{CT,ij} = k_CT(z^i_CT,z^j_CT)$的 Gram matrices
  • $R = I - \frac{1}{n}ee^T$
    • $I$ 是单位矩阵
    • $e$ 是一个全一的列向量
      在本文的实现中，我们对$K_T$和$K_{CT}$使用内积核函数(inner product kernel function)
      同样，考虑到ZF和ZCF的嵌入，也可以从同一个图(Af)中学习到,他们的差距也应该通过HSIC得到加强:
      $$
      HSIC(Z_F,Z_{CF}) = (n-1)^{-2} tr(RK_F RK_CF)
      $$
      视差约束$\mathcal L_d$
      $$
      \mathcal L_d = HSIC(Z_T,Z_{CT}) + HSIC(Z_F,Z_{CF})
      $$

Optimization Objective (优化目标)

n个节点的预测表示为$\hat Y =[\mathcal{\hat{y_{ic}}}] \in \mathbb R^{n \times C}$
其中$\mathcal{\hat{y_{ic}}}$ 是节点i属于类c的概率
$$
\hat Y = softmax(W \cdot Z + b)
$$

  • $softmax(x) = \frac{exp(x)}{\sum^C_{c=1} exp(x_c)}$是跨所有类的normalizer

假设训练集是L,对于每个$L∈L$真正的标签是$Y_l$和预测的标签是$\hat Y_L$,则所有训练节点的节点分类交叉熵损失表示为$\mathcal L_t$
$$
\mathcal L_t = -\sum_{l \in L} \sum^C_{i = 1} Y_{li} ln \hat Y_{li}
$$

结合节点分类任务和约束条件，得到如下总体目标函数
$$
\mathcal L = \mathcal L_t + \gamma \mathcal L_c + \beta \mathcal L_d
$$

  • $\gamma$和$\beta$是一致性和视差约束条件的参数

在标签数据的引导下，我们可以通过反向传播来优化所提出的模型，学习用于分类的节点嵌入

实验

实验设置

数据集

本文提出的AM-GCN是在6个真实世界数据集上进行评估的，这些数据集总结在表1中。此外，为了重现性，我们在附录中提供了所有的数据网站

  • Citeseer

Citeseer是一个研究论文引文网络，节点为出版物，边缘为引文链接。节点属性是论文的单词包表示，所有节点被划分为6个区域。

  • UAI2010

本文使用的数据集有3067个节点和28311条边已在图卷积网络中测试，用于[28]中的社区检测

  • ACM

这个网络是从ACM数据集中提取的，其中节点代表论文，如果两篇论文的作者相同，那么它们之间就会有一条边。所有论文分为3个类(Database, Wireless Communication,
DataMining)。特征是论文关键词的词包表示

  • BlogCatalog

这是一个博客和他们的社会关系从博客目录网站的社交网络。节点属性由用户配置文件的关键字构造，标签代表作者提供的主题类别，所有节点被划分为6个类

  • Flickr

Flickr是一个图片和视频托管网站，在这里用户可以通过照片分享来相互交流。它是一个社交网络，节点代表用户，边代表用户之间的关系，所有节点根据用户的兴趣分组被分成9个类。

  • CoraFull

这是著名的引文网络Cora数据集的放大版，其中节点表示论文，边表示它们的引用，节点根据论文主题进行标记。

基线

本文比较了AM-GCN和两种最先进的方法，包括两种网络嵌入算法和六种基于图神经网络的方法。此外，我们为了重现性在补充中提供了所有的代码网站

  • DeepWalk
  • LINE
  • Chebyshev
  • GCN
  • kNN-GCN
  • GAT
  • DEMO-Net
  • MixHop

参数设置

更全面地评估我们的模型,我们选择三个标签利率训练集(例如,20、40、60标记节点每个类),选择1000个节点作为测试集。所有的基线都使用相同的参数初始化提出了他们的论文,我们也进一步仔细把参数来获得最佳的性能。

  • 对于我们的模型，我们同时训练三个具有相同隐含层维数($nhid1$)和相同输出维数($nhid2$)的两层GCNs，其中$nhid1 ∈ { 512, 768 }$ 和 $nhid2 ∈ { 32, 128, 256}$。
  • learning rate with Adam optimizer（Adam优化器的学习率）：$ 0.0001 ∼ 0.0005 $
  • the dropout rate（丢包率）：$ 0.5 $
  • $weight decay（权重衰减） ∈ { 5e − 3, 5e − 4} $
  • $k ∈ { 2 … 10}$ for k-nearest neighbor graph（k近邻邻居图）.
  • The coefficient of consistency constraint and disparity constraints：${ 0.01, 0.001, 0.0001}$和${ 1e−10, 5e−9, 1e−9, 5e−8, 1e−8}$
  • 对于所有方法，本文在同一个分区上运行5次，并报告平均结果。
  • 本文使用Accuracy (ACC)和macro F1-score (F1)来评价模型的性能。

节点分类

image.png

节点分类结果如上图所示，其中L/C表示每类标注节点的数量。本文有以下几点看法:

  • 与所有基线相比，本文提出的AM-GCN在所有标签率的数据集上通常都能获得最佳性能。特别对于ACC，AM-GCN获得了最大的相关提高，在BlogCatalog是8.59%，在Flickr是8.63%。结果表示AM-GCN的方法是有效的。
  • 在所有数据集上，AM-GCN的表现都优于GCN和kNN-GCN，说明了AM-GCN自适应融合机制的有效性，因为它比分别执行GCN和kNNGCN可以提取更多有用的信息。
  • 通过与GCN和kNN-GCN进行比较，可以发现拓扑图和特征图之间存在结构上的差异，在传统拓扑图上进行GCN并不总是比在特征图上进行GCN效果更好。例如，在BlogCatalog、Flickr和UAI2010中，特征图的性能优于拓扑。这进一步证实了在GCN中引入特征图的必要性
  • 此外，与GCN相比，AMGCN在feature graph (kNN)更好的数据集(如UAI2010、BlogCatalog、Flickr)上的改进更为实质性。这说明AM-GCN引入了一个更好更适合标签的kNN图来监督特征传播和节点表示学习。

变体分析 Analysis of Variants

在本节中，我们将在所有数据集中比较AM-GCN与其三个变体，以验证约束的有效性。

  • AM-GCN-w/o: AM-GCN without constraints $\mathcal L_c$ and $\mathcal L_d$
  • AM-GCN-c: AM-GCN with the consistency constraint $\mathcal L_c$ .
  • AM-GCN-d: AM-GCN with the disparity constraint $\mathcal L_d$

image.png

从上图中可以得出以下的结论：

  • AM-GCN的结果始终优于其他三种变体，说明了这两种约束同时使用的有效性。
  • 对于所有标签率的数据集，AM-GCN-c和AM-GCN-d的结果通常都优于AM-GCN-w/o，验证了这两个约束条件的有效性。
  • AM-GCNc在所有数据集上都优于AM-GCN-d，说明一致性约束在该框架中发挥了更重要的作用。
  • 对比图2和表2的结果可以发现AM-GCN-w/o虽然没有任何限制，但仍然取得了成功

Visualization

为了更直观地进行比较并进一步展示我们所提出模型的有效性，我们对BlogCatalog数据集进行了可视化。我们将输出嵌入在softmax之前的AM-GCN(或GCN, GAT)的最后一层上，用t-SNE[26]将学习到的测试集嵌入图绘制出来。图3中的BlogCatalog的结果由真实的标签着色。

image.png

Analysis of Attention Mechanism

为了考察我们所提出的模型所学习到的注意值是否有意义，我们分别分析了注意力分布和注意力学习趋势。

Analysis of attention distributions

AM-GCN学习了两个特定的嵌入和一个常见的嵌入，每个嵌入都与注意值相关。我们对标签率为20的所有数据集进行了注意分布分析，结果显示为图4。

可以看出，对于Citeseer、ACM、CoraFull，拓扑空间中特定嵌入的注意值大于特征空间中的注意值，而公共嵌入的注意值介于它们之间。这意味着拓扑空间中的信息应该比特征空间中的信息更重要。为了验证这一点，我们可以看到，在表2中这些数据集上，GCN的结果优于kNN-GCN。