DL GCN

图卷积网络知识汇总

Posted by MY on March 14, 2019

一、简介

　　近年来，深度学习彻底改变了机器学习，从图像分类和视频处理到语音识别和自然语言理解等任务都发挥着巨大的作用。 这些任务中的数据通常表示在欧几里德空间中。 然而，越来越多的应用从非欧几里德域生成数据，并表示为具有复杂关系和对象之间相互依赖性的图。 图数据的复杂性给现有的机器学习算法带来了重大挑战。最近，出现了许多关于扩展图形数据的深度学习方法的研究。

二、CNN中的卷积

　　在CNN中，卷积核的系数是通过随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。卷积核的参数通过优化求出才能实现特征提取的作用，如下图所示，CNN中的卷积本质上就是利用一个共享参数的过滤器（kernel），通过计算中心像素点以及相邻像素点的加权和来构成feature+map实现空间特征的提取，加权系数就是卷积核的权重系数。 1

三、CNN与GCN的区别

　　CNN处理的数据如图像等，属于Euclidean Structure的数据，像素点是规整的矩阵，很容易提取特征。但是对于一些Non Euclidean Structure的数据，如社交网络、信息网络、论文引用等，CNN无法使用一个同样尺寸的卷积核对这样结构的数据进行卷积运算。因此，人们开始使用GCN来提取拓扑图的空间特征。 2

四、提取拓扑图特征的方式

  • Spatial-based Graph Convolutional Networks：基于空间的图卷积网络，该方法用聚合相邻节点的信息来表示图卷积。
  • Spectral-based Graph Convolutional Networks：基于谱的图卷积网络，该方法将图卷积解释为从图像信号中去除噪声。该方法在图像信号处理领域的基础上，模仿傅里叶变换定义了graph的卷积，并进一步与深度学习结合提出了GCN。它所基于的数学理论为谱图理论，研究图的性质与图的相关矩阵（如邻接矩阵、拉普拉斯矩阵）的特征多项式、特征值和特征向量的关系

五、图网络的基本概念（偏向基于空间的图卷积网络）

5.1 定义

图卷积网络(GCN)是一种在图上操作的神经网络。给定一个图$G=(E,V)$， 一个GCN的输入如下：

  • 一个$N \times F$的输入特征矩阵$X$，其中$N$是图中的节点个数，$F$是每个节点的输入特征个数；
  • 一个$N \times N$的图结构表示矩阵，比如$G$的邻接矩阵$A$。 因此，GCN中的隐藏层可以写成$H^{i}=f(H^{i-1},A)$，其中$H^{0}=X$，$f$是传播函数。每层$H^{i}$对应于$N \times F^{i}$的特征矩阵。在每一层，这些特征被聚合后再用传播规则$f$形成下一层的特征。这样，特征在每一个连续的层上都变得越来越抽象。在这个框架中，GCN的变体仅在传播规则$f$的选择上有所不同。

5.2 一个简单的例子

最简单的传播规则如下：

\[f(H^{i},A)=\sigma(AH^{i}W^{i})\]

其中$W^{i}$是第$i$层的权重矩，$\sigma$是一个非线性激活函数，如ReLu函数。权重矩阵具有维数$F^{i}\times F^{i+1}$，即权重矩阵的第二维的大小决定下一层的特征个数。因为这些权重在节点之间是共享的，因此这就相当于卷积神经网络中的滤波操作。
我们将传播规则简化为$f(X,A)=AX$，对下图进行演示： 0 使用每个顶点的出度用于构建邻接矩阵$A$为：

In [1]: import numpy as np
        A = np.matrix([
            [0, 1, 0, 0],
            [0, 0, 1, 1],
            [0, 1, 0, 0],
            [1, 0, 1, 0]],
            dtype=float
        )

为每个节点生成两个整数特征，方便确认对应的节点，特征矩阵$X$：

In [2]: X = np.matrix([
            [i, -i]
            for i in range(A.shape[0])
        ], dtype=float)
        X
        
Out[2]: matrix([[ 0.,  0.],
                [ 1., -1.],
                [ 2., -2.],
                [ 3., -3.]])

应用传播规则$AX$：

In [3]: A * X
Out[3]: matrix([
         [ 1., -1.],
         [ 5., -5.],
         [ 1., -1.],
         [ 2., -2.]])

我们发现每个节点(每一行)的表示现在是其邻居特征的总和。换句话说，图卷积层将每个节点表示为其邻域的集合。例如，第二行的元素为5，表示节点1的两个邻居节点2和3的特征之和。但是这样的特征聚合存在两个问题：

  1. 节点的聚合表示不包括它自己的特征。这个表示只是其邻居节点特征的集合，因此只有具有自环的节点才会在聚合中包含自己的特征。
  2. 大度的节点在特征表示中会有较大的值，而小度的节点将具有较小的值。这可能导致梯度消失或爆炸。

针对这两个问题，对应的解决方法是：

  1. 向每个节点添加自环。在实践中，通过在应用传播规则之前将对角矩阵$I$添加到邻接矩阵$A$来实现的。 
    In [4]: 
     I = np.matrix(np.eye(A.shape[0]))
     I
Out[4]: 
     matrix([[1., 0., 0., 0.],
             [0., 1., 0., 0.],
             [0., 0., 1., 0.],
             [0., 0., 0., 1.]])

    In [5]: 
     A_hat = A + I
     A_hat * X
Out[5]: 
     matrix([[ 1., -1.],
             [ 6., -6.],
             [ 3., -3.],
             [ 5., -5.]])

    由于节点现在成了自己的邻居，所以在加和其邻居节点的特征时，节点本身的特征也包括在内。

  2. 特征表示归一化。通过将邻接矩阵$A$与节点的度矩阵$D$的逆相乘，可以将特征表示按节点度进行归一化。我们将传播规则修改为：
\[f(X,A)=D^{-1}AX\]

首先计算度矩阵：

In [6]: 
        D = np.array(np.sum(A, axis=1))
        D = np.matrix(np.diag(np.squeeze(D)))
        D 
Out[6]:         
        matrix([[1., 0., 0., 0.],
                [0., 2., 0., 0.],
                [0., 0., 1., 0.],
                [0., 0., 0., 2.]])

使用度矩阵对邻接矩阵进行变换：

In [7]:
        A = np.matrix([
            [0, 1, 0, 0],
            [0, 0, 1, 1],
            [0, 1, 0, 0],
            [1, 0, 1, 0]],
            dtype=float
        )
        D**-1 * A
Out[7]:
        matrix([[0. , 1. , 0. , 0. ],
                [0. , 0. , 0.5, 0.5],
                [0. , 1. , 0. , 0. ],
                [0.5, 0. , 0.5, 0. ]])

观察到邻接矩阵的每一行中的权重(值)已被对应行的节点的度所除。对变换后的邻接矩阵应用传播规则，即：

In [8]: 
         D**-1 * A * X
Out[8]:
         matrix([
          [ 1. , -1. ],
          [ 2.5, -2.5],
          [ 1. , -1. ],
          [ 1. , -1. ]])

得到每个节点的相邻节点特征值的均值。

最终，我们现在将自环和归一化操作结合起来，并重新引入先前丢弃的权重和激活函数，便可得到一个完整的隐藏层，包含邻接矩阵、输入特征、权重和激活函数。

5.3 特征聚合

5.3.1 Sum Rule

上述将邻近节点的特征值相加的特征聚合称为Sum Rule。我们来看如何计算聚合中的第$i$行：

\[aggregate(A,X)\_{i}=A_{i}X=\sum_{j=1}^{N} A_{i,j}X{j}\]

由上式可知，每个邻居节点的贡献仅仅取决于邻接矩阵定义的邻域。

5.3.2 Mean Rule

使用邻近节点的特征值的均值的特征聚合称为Mean Rule。考虑不带自环的邻接矩阵：

\[aggregate(A,X)\_{i}=D^{-1}A_{i}X=\sum_{k=1}^{N}D_{i,k}^{-1}\sum_{j=1}^{N}A_{i,j}X_{j}=\sum_{j=1}^{N}D_{i,i}^{-1}A_{i,j}X_{j}=\sum_{j=1}^{N}\frac{A_{i,j}}{D_{i,i}}X_{j}\]

由上式可知，Mean Rule取决于邻接矩阵定义的邻域与节点的度。

5.3.3 Spectral Rule

用类似于上面的方法，我们可以从聚合特征的角度来解释基于频谱的规则。这种解释对于后面内容的理解具有一定的帮助。
\(\begin{align*} aggregate(A,X)_{i}&=D^{-0.5}A_{i}D^{-0.5}X\\ &=\sum_{k=1}^{N}D_{i,k}^{-0.5}\sum_{j=1}^{N}A_{i,j}\sum_{l=1}^{N}D_{j,l}^{-0.5}X_{j}\\ &=\sum_{j=1}^{N}D_{i,i}^{-0.5}A_{i,j}D_{j,j}^{-0.5}X_{j}\\ &=\sum_{j=1}^{N}\frac{1}{D_{i,i}^{0.5}}A_{i,j}\frac{1}{D_{j,j}^{0.5}}X_{j} \end{align*}\tag{0}\) 在计算第$i$个节点的聚合特征时，我们不仅要考虑第$i$个节点的度，还要考虑第$j$个节点的度。类似于Mean Rule，Spectral Rule对聚合进行归一化，使得聚合特征大致保持与输入特征相同的比例。当邻居节点的度很低时，spectral rule会更多地考虑将邻居节点的特征权重增大，反之亦然。这样在小度的邻居节点比大度的邻居节点提供的信息更有用时，这种规则是很有效的。

六、基于谱的图卷积网络

6.1 拉普拉斯矩阵

　　拉普拉斯矩阵是图论中用到的一种重要矩阵，给定一个有n个顶点的图$G=(V,E)$，其拉普拉斯矩阵被定义为 $L = D-A$，$D$其中为图的度矩阵，$A$为图的邻接矩阵。例如，给定一个简单的图： 3 将它转换为邻接矩阵的表示，记为$A$： \(\left\{ \begin{matrix} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix} \right\} \tag{1}\)
　　把矩阵(1)的每一列元素加起来得到N个数，然后把它们放在对角线上（其它地方都是零），组成一个N×N的对角矩阵，记为度矩阵D，如矩阵(2)所示。其实度矩阵（对角线元素）表示的就是原图中每个点的度数，即由该点发出的边之数量： \(\left\{ \begin{matrix} 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} \right\} \tag{2}\)
　　根据拉普拉斯矩阵的定义$L = D-A$，可得拉普拉斯矩阵$L$ 为： \(\left\{ \begin{matrix} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1 \end{matrix} \right\} \tag{3}\)
　　显然，拉普拉斯矩阵都是对称的。此外，另外一种更为常用的拉普拉斯矩阵形式是正则化的拉普拉斯矩阵（Symmetric normalized Laplacian），定义为：

\[L^{sym}:=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \tag{4}\]

　　该矩阵中的元素由下面的式子给出：
\(L_{i,j}^{sym}:=\left\{\begin{matrix} 1 & if\ i = j\ and\ deg(v_{i})\neq 0\\ -\frac{1}{\sqrt{deg(v_{i})deg(v_{j}))}} & if\ i\neq j\ and\ v_{i}\ is\ adjacent\ to\ v_{j}\\ 0 & otherwise \end{matrix}\right. \tag{5}\)

6.2 拉普拉斯矩阵的谱分解（特征分解）

　　谱分解又称作特征分解，是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法，其充要条件为n阶方阵存在n个线性无关的特征向量。
拉普拉斯矩阵是半正定对称矩阵，具有如下特点：

  • 对称矩阵一定有n个线性无关的特征向量。
  • 半正定矩阵的特征值一定非负。
  • 对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。 　　由上可以知道拉普拉斯矩阵一定可以谱分解，且分解后有特殊的形式，即$L=U \Lambda U^{-1}$，其中$U=[u_{0},u_{1},…,u_{n-1}]\in R^{N\times N}$是按照特征值大小排列的特征矩阵向量,$\Lambda$为n个特征值构成的对角矩阵,$\Lambda_{ii} = \lambda_{i}$由于$U$为正交矩阵，即$UU^{T}=I$，因此拉普拉斯矩阵的谱分解又可以写成$L=U \Lambda U^{T}$。

6.3 GCN使用拉普拉斯矩阵的原因

  • 拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这与GCN的spectral domain相对应
  • 通过拉普拉斯算子可以与拉普拉斯矩阵进行类比
  • 由于卷积在傅里叶域的计算相对简单，为了在graph上做傅里叶变换，需要找到graph的连续的正交基对应于傅里叶变换的基，因此要使用拉普拉斯矩阵的特征向量。

6.4 Graph上的傅里叶变换及卷积

  • 傅里叶变换：将一个时域非周期的连续信号，转换为一个在频域非周期的连续信号。可以理解为把任意一个函数表示成了若干个正交函数（由sin, cos 构成）的线性组合。
  • 卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积。“时域相卷等于频域相乘，时域相乘等于频域相卷”。

　　在图像信号处理的领域里，一个图像信号$x\in R^{N}$代表graph的节点的特征向量，其中$x_{i}$是第$i$个节点的值。
　　类比于传统的傅里叶变换与逆傅里叶变换，定义“图傅里叶变换”为$F(x)=U^{T}x$，“逆图傅里叶变换”为$F^{-1}(\hat{x})=U\hat{x}$，其中$\hat{x}$是信号$x$经过图傅里叶变换得到的信号。具体的推导过程可以在这篇论文中找到：The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains。
　　图傅里叶变换将输入图的信号投影到了正交空间，相当于把图上定义的任意向量，表示成了拉普拉斯矩阵特征向量的线性组合。由于n维空间中n个线性无关的向量可以构成空间的一组基（而且拉普拉斯矩阵的特征向量还是一组正交基），因此归一化拉普拉斯矩阵算子的特征向量构成了图傅里叶变换的基。
　　对图傅里叶变换应用卷积定理，可得输入信号$x$与滤波器$g\in R^{N}$的卷积为：

\[x* g = F^{-1}(F(x)\odot F(g)))=U(U^{T}x\odot U^{T}g)\]

其中$\odot$代表哈达玛积，对于两个向量，就是进行内积运算；对于维度相同的两个矩阵，就是对应元素的乘积运算。令$g_{\theta}=diag(U^{T}g)$，则上述公式可以简化为：

\[x * g = F^{-1}(F(x)\odot F(g)))=Ug_{\theta}U^{T}x\]

　　在这里我们可以把$g_{\theta}$理解为$L$特征值的函数。以上便是图卷积的定义。所以基于谱的图卷积都符合这个定义，只是选择滤波器$g_{\theta}$时有区别。

6.5 三种经典的谱图卷积网络

6.5.1 Spectral CNN

　　Spectral networks and locally connected networks on graphs直接粗暴地将$g_{\theta}$变成卷积核$diag(\theta_{l})$，即： \(y_{output}=\sigma \left(U\left( \begin{matrix} \theta_{1} & \\ & \ddots & \\ & & \theta_{n} \\ \end{matrix} \right) U^{T}x\right) \tag{6}\)
公式(6)就是初代GCN。其中$\sigma$为激活函数（如ReLu），$\theta_{l}$与神经网络中的权重一样是任意的参数，通过初始化赋值然后利用误差反向传播进行调整。这种方法在每一次前向传播时都要计算$U$、$diag(\theta_{l})$与$U^{T}$的乘积，对于大规模的graph来说计算成本非常高。

6.5.2 Chebyshev Spectral CNN

　　Convolutional neural networks on graphs with fast localized spectral filtering用切比雪夫多项式来近似$g_{\theta}$，即 \(y_{output}=\sigma \left(U\left( \begin{matrix} \sum_{j=0}^{K}\alpha_{j}\lambda_{1}^{j} & \\ & \ddots & \\ & & \sum_{j=0}^{K}\alpha_{j}\lambda_{n}^{j} \\ \end{matrix} \right) U^{T}x\right) \tag{7}\)
利用矩阵乘法进行变换： \(\left( \begin{matrix} \sum_{j=0}^{K}\alpha_{j}\lambda_{1}^{j} & \\ & \ddots & \\ & & \sum_{j=0}^{K}\alpha_{j}\lambda_{n}^{j} \\ \end{matrix} \right)=\sum_{j=0}^{K}\alpha_{j}\Lambda^{j} \tag{8}\)
进而推出\(U\sum_{j=0}^{K}\alpha_{j}\Lambda^{j}U^{T}=\sum_{j=0}^{K}\alpha_{j}U\Lambda^{j}U^{T}=\sum_{j=0}^{K}\alpha_{j}L^{j}\)

因此，公式(7)可以写作

\[y_{output}=\sigma(\sum_{j=0}^{K}\alpha_{j}L^{j}x) \tag{7}\]

其中$\alpha_{1},\alpha_{2},…,\alpha_{K}$是任意参数，通过初始化赋值然后利用误差反向传播进行调整。矩阵变换后，不需要做特征分解了，直接用拉普拉斯矩阵$L$进行变换，计算复杂度大大下降。卷积核相比于9.1中的包含n个参数的卷积核，只有K个参数。同时它具有很好的spatial localization。K值同时也是感受域receptive field的大小。即每次卷积会将中心顶点K-hop neighbor上的特征进行加权求和，权系数就是$\alpha_{K}$。例如，当k=1时，对每个顶点上一阶neighbor的特征（图中红色节点）进行加权求和： 3

6.5.3 First order of ChebNet

　　Semi-Supervised Classification with Graph Convolutional Networks是在9.2的基础上进一步推演得到的。

七、GCN常用数据集

  1. KarateClub：数据为无向图，来源于论文An Information Flow Model for Conflict and Fission in Small Groups
  2. TUDataset：包括58个基础的分类数据集集合，数据都为无向图，如”IMDB-BINARY”，”PROTEINS”等，来源于TU Dortmund University
  3. Planetoid：引用网络数据集，包括“Cora”, “CiteSeer” and “PubMed”，数据都为无向图，来源于论文Revisiting Semi-Supervised Learning with Graph Embeddings。节点代表文档，边代表引用关系。
  4. CoraFull：完整的”Cora”引用网络数据集，数据为无向图，来源于论文Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking。节点代表文档，边代表引用关系。
  5. Coauthor：共同作者网络数据集，包括”CS”和”Physics”，数据都为无向图，来源于论文Pitfalls of Graph Neural Network Evaluation。节点代表作者，若是共同作者则被边相连。学习任务是将作者映射到各自的研究领域中。
  6. Amazon：亚马逊网络数据集，包括”Computers”和”Photo”，数据都为无向图，来源于论文Pitfalls of Graph Neural Network Evaluation。节点代表货物i，边代表两种货物经常被同时购买。学习任务是将货物映射到各自的种类里。
  7. PPI：蛋白质-蛋白质反应网络，数据为无向图，来源于论文Predicting multicellular function through multi-layer tissue networks
  8. Entities：关系实体网络，包括“AIFB”, “MUTAG”, “BGS” 和“AM”，数据都为无向图，来源于论文Modeling Relational Data with Graph Convolutional Networks
  9. BitcoinOTC：数据为有向图，包括138个”who-trusts-whom”网络，来源于论文EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs，数据链接为Bitcoin OTC trust weighted signed network

参考

  1. A Comprehensive Survey on Graph Neural Networks
  2. 如何理解 Graph Convolutional Network（GCN）？
  3. How to do deep learning on graphs with graph convolutional networks
  4. 傅里叶分析之掐死教程（完整版）
  5. GRAPH CONVOLUTIONAL NETWORKS
  6. Pytorch Geometric

未完待续…

赏 支付宝打赏 微信打赏

您的打赏是对我最大的鼓励！

Share
Comments
Advertisements
CATALOG
    FEATURED TAGS
    DRL Adversarial Attack DL RL 生活 经验总结 RL basic knowledge RL advanced algorithms Model-Free RL Deep Q-Learning Exploration in RL MARL Analysis of Emergent Behaviors Deterministic Policy Gradients Learning Cooperation Contrastive Learning Offline Reinforcement Learning Offline RL
    FRIENDS