您的位置: 首页  >  文章  >  图卷积网络GCN

图卷积网络GCN

分类: 文章 • 2024-10-23 23:35:52

原文：https://tkipf.github.io/graph-convolutional-networks/

图卷积网络GCN

一阶滤波器的多层图卷积网络(GCN)

GCN Part I: 定义

我们的目的是在一个在图G=(V,ϵ)G=(V, \epsilon)上学习一个signals/feature的函数作为输入：

  • 每个节点 i 的特征描述xix_i；总结为一个N x D的特征矩阵X，N为节点数，D为输入特征数
  • 图结构在矩阵形式中的一个代表性描述；通常以邻接矩阵A（或其他某些函数）表示。

之后生成一个节点级输出 Z（N x F 的特征矩阵，其中F是每个节点输出特征的数量）。图级输出可以通过引入某种形式的池化操作建模。

每个神经网络层可以写成非线性函数 Hl+1=f(H(l),A)H^{l+1} = f(H^{(l)} ,A)，其中H(0)=XH^{(0)}=X and H(L)=ZH^{(L)}=Z，或将 z 作为图级输出，L是层数。模型的特异性仅表现在函数 f(⋅,⋅)f(⋅,⋅)的选择和参数化的不同。

GCN Part II: 一个简单的例子

下列是一个简单的分层传播规则形式，f(H(l),A)=σ(AH(l)W(l))f(H^{(l)}, A)=\sigma(AH^{(l)}W^{(l)})其中W(l)W^{(l)}是第 l 层神经网络的权重矩阵，σ(⋅)是非线性**函数，例如ReLU函数。尽管这个模型简单，但是他已经非常强大了。

首先说下这个简单模型的两个局限：
1、乘以A矩阵意味着，对于每个节点，我们把所有相邻特征矢量加起来但不包括他本身，我们通过在图中添加一个自循环来弥补：对A矩阵加一个单位矩阵。
2、A通常是不归一化的，因此与 A 相乘将完全改变特征向量的分布范围（我们可以通过查看 A 的特征值来理解）。归一化 A 使得所有行总和为 1，例如D−1AD^{-1}A，其中D是一个对角节点度矩阵，这样即可避免这个问题。与D−1AD^{-1}A相乘相当于取相邻节点特征值的平均值。在实际应用中可使用对称归一化，例如D−1/2AD−1/2D^{-1/2}AD^{-1/2}，模型动态会变得更有趣，因为这不再等于相邻节点的平均值。
结合这两个技巧，我们得到了【Semi-Supervised Classification with Graph Convolutional Networks】介绍的传播规则f(H(l),A)=σ(D^−1/2A^D^−1/2H(l)W(l))f(H^{(l)}, A) = \sigma(\widehat{D}^{-1/2}\widehat{A}\widehat{D}^{-1/2}H^{(l)}W^{(l)})其中A^=A+I\widehat{A}=A+I，I是单位矩阵，D^\widehat{D}是A的对角节点度矩阵。

GCN Part III: 嵌入karate club网络

图卷积网络GCN

颜色表示通过基于模块的聚类得到的共同体

让我们来看看我们的简单GCN模型(见上一节或Kipf & Welling, ICLR 2017)如何在一个著名的图形数据集上工作:Zachary的karate club网络(见上图)。

我们采用一个三层的GCN随机初始化权重。即使在训练权重之前，我们只需将图的邻接矩阵和X=IX=I（即单位矩阵，因为我们没有任何节点特征）插入到模型中。三层 GCN 在正向传传播间执行了三个传播步骤，并有效地卷积每个节点的三阶邻域（所有节点都达到了三级"跳跃"）。值得注意的是，该模型为这些节点生成了一个与图的共同体结构非常相似的嵌入（见下图）。到目前为止，我们已经完全随机地初始化了权重，并且还没有做任何训练。
图卷积网络GCN

GCN embedding (with random weights) for nodes in the karate club network.

这似乎有点令人惊讶。 最近关于名为DeepWalk的模型的论文（Perozzi et al.，KDD 2014）表明，他们可以在复杂的无监督训练过程中得到相似的嵌入。那怎么可能仅仅使用我们未经训练的简单 GCN 模型，就得到这样的嵌入呢？

我们可以通过将 GCN 模型视为图论中著名的 Weisfeiler-Lehman 算法的广义可微版本，并从中得到一些启发。Weisfeiler-Lehman 算法是一维的，其工作原理如下 ：

对于所有节点vi∈Gv_i∈G：

  • 从相邻节点{vjv_j}得到特征{hvjh_{v_j}}
  • 更新节点特征hvi←hash(∑jhvj)h_{v_i}←hash(\sum_jh_{v_j})，其中hash(⋅)(理想情况下)是单射哈希函数

重复 k 步或直到函数收敛。

在实际应用中，Weisfeiler-Lehman 算法可以为大多数图赋予一组独特的特征。这意味着每个节点都被分配了一个独一无二的特征，该特征描述了该节点在图中的作用。但这对于像网格、链等高度规则的图是不适用的。对大多数不规则的图而言，特征分配可用于检查图的同构（即从节点排列，看两个图是否相同）。

回到我们图卷积的层传播规则（以向量形式表示）：
hvi(l+1)=σ(∑j)hvj(l)W(l)/cijh_{v_i}^{(l+1)}=\sigma(\sum_j)h^{(l)}_{v_j}W^{(l)}/c_{ij}
其中j索引相邻节点viv_i，cijc_{ij}是边(vi,vj)(v_i, v_j)归一化常数，它源于在我们的GCN模型中使用对称归一化邻接矩阵D−1/2AD−1/2D^{-1/2}AD^{-1/2}，我们现在看到，这个传播规则可以被解释为在原始的 Weisfeiler-Lehman 算法中使用的 hash 函数的可微和参数化（W(l)W^{(l)}）变体，如果我们现在选择一个适当的、非线性的的矩阵，并且初始化其随机权重，使它是正交的（或者例如使用初始化来自Glorot & Bengio, AISTATS 2010），那么这个更新规则在实际应用中会变得稳定（也归功于归一化cijc_{ij}），我们得出了很有见地的结论，即我们得到了一个很有意义的平滑嵌入，其中可以用距离远近表示局部图结构的（不）相似性！

GCN Part IV: 半监督学习

由于我们模型中的所有内容都是可微分且参数化的，因此可以添加一些标签，使用这些标签训练模型并观察嵌入如何反应。我们可以使用Kipf & Welling中引入的GCN半监督学习算法。我们只需对每类/共同体（下面视频中突出显示的节点）的一个节点进行标记，然后开始进行几次迭代训练：
视频链接

请注意，该模型直接产生一个我们可以立即可视化的二维潜在空间。我们观察到3层GCN模型设法线性地分离群落，每个类只给出一个标记的例子。考虑到模型没有接收到节点的特性描述，这是一个相当显著的结果。同时，可以提供初始节点特征，这正是我们在本文(Kipf & Welling, ICLR 2017)中描述的实验中所做的，以实现对多个图数据集的最先进分类结果。

结论

这个课题的研究才刚刚开始。过去几个月出现了令人兴奋的进展，但到目前为止，我们可能只触及了这些类型模型的皮毛。如何将图上的神经网络进一步泰勒到特定类型的问题，例如，在有向图或关系图上学习，以及如何将学习到的图嵌入到未来的任务中，等等，还有待观察。这个列表绝不是详尽的，我希望在不久的将来会出现更多有趣的应用程序和扩展。如果你有一些令人兴奋的想法或问题要分享，请在下方留言告诉我!

完整性说明

这篇博客文章绝不是对图上神经网络领域的详尽回顾。为了让这篇文章更具可读性，并让它有一个连贯的故事情节，我省略了一些近期和较早的论文。尽管如此，如果您想更深入地研究这个主题，并对周围的内容和到目前为止尝试过的内容有一个完整的概述，那么我在这里提到的这些论文将是一个良好的开端。

code

github：https://github.com/tkipf/gcn

  1. 谱图卷积的定义：signal与filter在图的傅里叶空间的乘积。
    图傅里叶变换的定义：图信号XX(即每个节点的特征向量)与图拉普拉斯矩阵LL的特征向量矩阵UU的乘积。 利用对称归一化图邻接矩阵A~\widetilde{A}可以方便地计算出(归一化)图的拉普拉斯矩阵 L=I−A~L=I-\widetilde{A}。
  2. 用谱方法是要付出代价的: filter必须定义在傅里叶空间且图傅里叶变换计算成本高(为节点特征与图拉普拉斯矩阵的特征相邻矩阵的乘积。对于N个节点计算复杂度为O(N2)O (N2)；首先计算特征向量矩阵计算成本更高)
  3. 这里做个简化，对Weisfeiler-Lehman算法进行广泛的数学讨论，可以看看Douglas的论文
  4. weisfeler-lehman算法的节点特性通常被选择为标量整数，通常被称为颜色
  5. 由于在这个例子中我们没有退出学习率，一旦模型收敛到一个好的解决方案，事情就会变得相当“不稳定”。

补充：那么怎么将其应用到图片甚至视频分类呢？？？欢迎交流

相关推荐