图神经网络(GCN)

本文主要记录对GCN的相关内容的学习，其中包含基本原理、示例以及代码实现

图网络

图网络的核心思想就是依据图结构的空间依赖关系来表征真实特征之间的相互作用关系，通过对节点特征聚合生成新的节点特征表示

上图为一张交通系统的图结构，在6个位置上分别有一个传感器记录了一段时间的交通流量数据，现在的目标是要预测接下来每个位置上未来一段时间的流量。该怎么去思考？从时间序列本身的角度来思考，未来的数据一定是与过去的数据相关，因此我们可以对6个位置的时间序列单独进行预测生成6个位置未来的预测值，但是这样做有一个缺点，没有考虑到节点之间的空间依赖关系，假设4节点流量非常大，那么他相邻的3/5/6节点大概率流量也是非常大的，既然已经用图结构表示出了这种空间关系，那么我们怎么去应用它？这就是图网络所要解决的问题。

图卷积网络

图卷积网络的本质就是提取图结构的空间特征，聚合邻居节点的信息。

基于提取方式不同可以分为：

• 基于空间域的图网络。从图结构出发，聚合邻居节点的信息作为新特征，不断的进行消息传递的过程
• 基于谱域的图网络。将原始数据转换成谱域中，利用图谱理论引入滤波器进行滤波，再转换回时域的过程

基于空间域的图网络

邻接矩阵A

假设输入为x，网络权重为W图卷积神经网络可以表示为
$$
f=σ(Axw)
$$
BP神经网络可以表示为
$$
f=σ(xw)
$$
对于BP网络，输入X经过网络的计算后，表示对每个样本的各个特征进行线性组合生成新的特征，再使用激活函数对其进行激活的过程。而图神经网络再输入X前乘了一个A图结构矩阵，那么AX就表示利用图结构来对各个样本的特征进行重新整合作为新的输入，然后再输入到BP神经网络中，这样就考虑到了特征之间的空间依赖关系。

如上图需重新计算E的特征的话，根据GCN的思想就需要聚合其邻居节点的信息，就是对ABCD节点的特征以一定方式进行聚合(平均、求和、拼接等)，这里以求和为例：

引入邻接矩阵A，则聚合求和又可以表示为

设n为节点数，f为每个节点的特征维度，则邻接矩阵A的形状为 (n,n) ,特征矩阵的形状为 (n,f) ，AX相乘后表示考虑到邻居节点信息的新的特征矩阵，形状为 (n,f) ，每一行表示一个节点的特征，可以看出新的E节点，也就是矩阵相乘后的最后一行就是ABCD节点的相加。相比于手动计算，采用邻接矩阵，我们能一次性将所有的节点特征表示出来。

但再上面新的特征矩阵中B和C的特征向量是一样的，因为他两的邻居节点是相同的。但由于两个点是不同位置不同特征的节点，得到新的特征向量是不合理的。所以不仅要考虑邻居的节点，还需要考虑自身的节点。

新的邻接矩阵为：

将新的邻接矩阵左乘特征矩阵X得到新的特征矩阵

从上面可以看到，为了避免B和C拥有相同的邻居而导致新特征也一样的情况，需要考虑自身节点的影响，所以对原来的邻接矩阵添加一个单位矩阵I来表示自身节点。可以看到新的邻接矩阵得到的特征矩阵B和C特征向量不一样。

求平均(归一化)

对于上面的求和聚合变相的改变了特征的量级。若要求收入的话，则使用求平均聚合方式。类比到图结构就是左乘度矩阵。

度矩阵就是与该节点相邻节点的数据，因此邻接矩阵A的每一行的求和组成的对角矩阵，如下

通用也需要考虑到自身节点的影响，也对度矩阵加单位矩阵得到新的度矩阵

所以最终的求平均矩阵就是

由于左成初等矩阵相当于行变换，相当于对前面求和的特征矩阵X‘每一行除以度，就是对每一个节点求和后的特征做的平均

renormalization

上面求平均的方式存在不合理的地方，假设节点自身数据很小，但由于邻居节点数据很大，平均下来节点的数据自然也变大了

上面的改进公式相当于对新的邻接矩阵进行初等行列变换，这个变换就相当于 i节点与 j 节点的关系系数再除以 i 节点度的平当根与 j 节点系数平方根的积，这样节点之间的关系系数（权重）不再与某一个节点优点，而分别考虑到了两个节点的度，邻居节点的度越大，权重越小，也即一个节点的边越多，由于节点的总的信息是一定的，那么他通过每条边的信息量越少，即通过某条边向外发送的信息越少。

整体流程

图网络就是不断考虑邻居节点以及自身信息的迭代过程，每一次迭代就是一次特征重组

一个两层的GCN网络为

对比前面的BP神经网络，GCN就是一种BP神经网络，只不过是将输入经过邻接矩阵及度矩阵变换的考虑到空间信息的特征输入。

基于频域角度

GCN是一种基于频域的方法，空间域的GCN只是频域GCN推导的一个特例，然后从空间角度解读出来而已。卷积和空间域变换一样就是为了提取相邻节点的信息，对节点特征进行重新表示。

傅里叶变换

数学上的卷积是两个函数的卷积等于各自傅里叶变换后的乘积的逆傅里叶变换

本质上就是一个基空间变换，找到一组函数正交基，将原函数向各个基上进行投影得到基上的坐标，从而将原函数改写为新的坐标下（模态、谱）的表示：
$$
f(x) = f(\hat\lambda_1)u_1+f(\hat\lambda_2)u_2+…+f(\hat\lambda_n)u_n
\f(\hat\lambda)为原函数f(x)在新基上的坐标值
$$
基上的坐标为原函数与基函数的内积除以基函数自身的内积(函数内积为积分)，公式如下:
$$
x=\frac{\int_b^a(f,g)dx}{\int_b^a(g,g)dx}=\frac{\sum(f_ig_i)}{\sum(g_ig_i)}
$$
所以各个坐标基上的坐标值可以用矩阵表示

逆傅里叶变换为

卷积

对一节点特征的卷积就是为了对特征进行重组，重组后的特征包含了节点之间的空间关系。

从两种视角来理解这个公式

特征矩阵U

矩阵U是一个正交矩阵，是原函数在新的坐标系下的坐标基，因此U的每一列都是单位向量且各列两两正交

根据线性代数可得，实对称矩阵一定可以对角化，且不同特征值对应的特征向量相互正交，设实对称矩阵A的特征矩阵为P，则$\Lambda$是特征值组成的对角矩阵

由此可以推出上面的H滤波器就是一个对称矩阵，U就是H的特征向量组成的特征矩阵，$\Lambda_H$是特征值组成的对角矩阵。而$\Lambda_H$则在图卷积中一般采用拉普拉斯矩阵计算。

拉普拉斯算子

拉普拉斯算子是一个标量，是梯度的散度，对一个函数，散度是该函数在坐标轴上偏导数之和：
$$
\Delta f = \frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}
$$
一阶偏导数可以表示为

图中每个节点都是离散的，取h为1，则

则二阶偏导为

所以在二维平面上f的拉普拉斯算子为：

上面这个式子就是中心点的上下左右四个方向的邻居节点的和与4倍的中心节点之间的差值

拉普拉斯矩阵

类比到图中，拉普拉斯算子定义在中心节点i与邻居节点之间的运算，即：
$$
\Delta f_i = \sum_i(f_i-f_j)
$$
引入邻接矩阵A，$a_ij$表示邻接矩阵中第i行j列的值，可进一步推导，其中$d_i$表示第i个节点的度

对图网络类比表示如下

其中，D为度矩阵，A为邻接矩阵，L就是拉普拉斯矩阵，他是度矩阵与邻接矩阵的差。为了避免某些邻居节点对主节点产生很大的影响，需要正则化，因此公式优化为

正则化后的拉普拉斯矩阵的最小特征值为0，最大特征值小于2。

Spectral CNN

上面说到，对某一节点特征的卷积就是为了对特征进行重组，重组后的特征就是滤波器H和重组前特征X相乘，所以图卷积的关键就是滤波器的选择。这里将上面正则化后的拉普拉斯矩阵$\hat{L}$作为滤波器，公式为：

则网络输出为：

Spectral CNN中将特征值组成的对角阵 $A_\hat{L}$ 替换为可学习参数$\theta_i$ ，通过神经网络自主调节各频率分量。

缺点

①需要对拉普拉斯矩阵进行特征分解，每一次的特征重组都要进行一次矩阵乘法，时间复杂度为 $O(n^2)$ ，计算开销大；
②卷积核需要n个参数，当图特别大的时候，参数也越多。
③模型是全局连接的，并不是局部连接，也就是模型在每一次更新特征的时候用到了全部的节点，而不是仅仅是邻居节点，

pytorch实现

由于频域的GCN需要具体问题具体分析，下面只实现基于空域的GCN

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import torch 
import torch.nn as nn
import torch.nn.functional as F

class GCN(nn.Module):
    def  __init__(self, nfeat, nhid, nclass, dropout):
        super(GCN, self).__init__()

        self.gc1 = GraphConvolution(nfeat, nhid)
        self.gc2 = GraphConvolution(nhid, nclass)
        self.dropout = dropout

    def forward(self, x, adj):    #x特征矩阵,agj邻接矩阵 
        x = F.relu(self.gc1(x, adj))
        x = F.dropout(x, self.dropout, training=self.training)
        x = self.gc2(x, adj)
        return F.log_softmax(x, dim=1)

class GraphConvolution(Module):
    """
    Simple GCN layer, similar to https://arxiv.org/abs/1609.02907
    """

    def __init__(self, in_features, out_features, bias=True):
        super(GraphConvolution, self).__init__()
        self.in_features = in_features
        self.out_features = out_features
        self.weight = Parameter(torch.FloatTensor(in_features, out_features))
        if bias:
            self.bias = Parameter(torch.FloatTensor(out_features))
        else:
            self.register_parameter('bias', None)
        self.reset_parameters()

    def reset_parameters(self):
        stdv = 1. / math.sqrt(self.weight.size(1))
        self.weight.data.uniform_(-stdv, stdv)
        if self.bias is not None:
            self.bias.data.uniform_(-stdv, stdv)

    def forward(self, input, adj):
        support = torch.mm(input, self.weight)
        output = torch.spmm(adj, support)
        if self.bias is not None:
            return output + self.bias
        else:
            return output

PYG是torch_geometric，是一个python专门用于处理图数据的包，里面封装好了各种图算法，下面实现一个GCN算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from torch_geometric.nn import GCNConv,SAGEConv,GATConv 

class GCN(torch.nn.Module):
    def __init__(self,f,h,c):
        super().__init__()
        self.conv1=GCNConv(f,h)
        self.conv2=GCNConv(h,c)
    def forward(self,data):
        x,edge_index=data.x,data.edge_index      #edge_index为PYG邻接矩阵格式的数据
        x=self.conv1(x,edge_index)
        x=F.relu(x)
        x=F.dropout(x,training=self.training)
        x=self.conv2(x,edge_index)
        
        return x