图神经网络：GCN原理学习笔记

2021-12-26 本文已影响0人 xiaogp

摘要：图神经网络，GCN

图数据的特征性质

图像数据是一种特殊的图数据，图像数据是标准的2D网格结构图数据。图像数据的CNN卷积神经网络算法不能直接用在图数据上，原因是图数据具有以下特殊性

节点分布不均匀：图像数据及网格数据诶个节点只有4个邻接点，因此可以定义均匀的卷积操作，但是图数据节点的度数可以任意变化，即邻节点不确定，因此无法直接卷积。
排列不变性：排列不变性（置换不变性）表示输入的顺序改变不会导致函数结果的变化（例如函数f(x, y, z) = x × y × z）。图数据具有排列不变性，即在空间中改变图中节点（对图进行折叠扭曲）的位置对最后的图关系没有影响，而图像数据只有变更了两个像素的位置整个图像的表达会发生变化，因此无法使用卷积，因为卷积的方式不符合排列不变性。
节点的额外属性：图数据的每个节点具有自身的属性，即每个节点都具有自身的特征向量，相比如图像数据中的三通道表达更加丰富。
边的额外属性：图中的节点可以拥有权重和类型，在图像网格数据中边没有任何属性或者权重，CNN卷积神经网络也没有而已处理边的机制。

GCN的目的和与CNN的联系

GCN要解决的是不规则的图结构数据的通用的特征提取方案，考虑节点自身的属性以及节点的邻接节点属性获得节点的特征向量，最终实现图节点分类，回归等任务。GCN和CNN一样都是对节点/像素的周边节点/像素进行加权求和套激活函数作为特征提取，经过多轮特征提取之后最后被一层套类似softmax函数实现分类。

图知识准备

（1）邻接矩阵

图的结构表示使用邻接矩阵（用A表示）进行表达，邻接矩阵就是统计Vij（V代表节点，ij代表从Vi->Vj）的连接权重，如果不考虑权重两个相连的节点的Vij值等于1，不相连的为0构成邻接矩阵，邻接矩阵是上下三角对称的。

邻接矩阵

（2）度矩阵

度矩阵（用D表示）是由节点的度构成的矩阵，度矩阵是对角阵，对角线上记录了各节点的度值，即Dii为节点i的度值，在无向图的情况下节点的度值是相连的边的数量，如上图度矩阵如下：

度矩阵

（3）矩阵的逆

设A是一个n阶矩阵，若存在另一个n阶矩阵B，使得： AB=BA=E ，E为单位阵，则称方阵A可逆，并称方阵B是A的逆矩阵。逆矩阵可以使用初等行变换求得，例如求上式的度矩阵，相当于每一行除以该节点的度。

初等行变换

（4）谱域和空域图神经网络

图神经网络分为基于谱域的模型和基于空域的模型，GCN起源于谱域模型，但也可以被认为是一个空域的神经网络，现在主流的方法都是以空域为主的GCN。谱域GCN理论知识多晦涩难懂，空域GCN很多套路和传统的神经网络比较类似。

GCN的输入输出

GCN每一次卷积（隐藏层）的输入是图的邻接矩阵A和节点的特征属性H（l），输出是新的节点特征属性H（l+1），在初始输入层特征属性H（l）就是特征矩阵X，若图上有n和节点，每个节点有d维特征，则X是一个n×d的矩阵X，即输入数据。

GCN公式理解

（1）GCN的卷积核表示

以函数f作为GCN的卷积表达式，即图卷积是一个对节点和邻接节点的函数操作，卷积的表达式如下

卷积表达式
图卷积实际上是对特征属性和邻接矩阵的操作，具体为每一层（或者说每一阶）卷积下邻接矩阵和该层的特征属性、该层权重相乘，再一层套激活函数，得到的结果作为新的特征属性继续循环操作，其中H0为初始的节点属性矩阵，由n行节点数，d维节点属性组成。由这个公式可知GCN的卷积核在每一层/阶是权重共享，即在同一阶下图上任意一个节点对周边邻居加权求和的权重表是一样的。

（2）邻居节点加权求和的矩阵表达

A 和 H 的乘积其实就是把所有的邻居节点向量进行相加，如下图所示，表示A × H

邻接矩阵和特征属性相乘

A表示的是邻接矩阵，H表示的是4个节点，每个节点有一个5维的特征向量，将A 和H点乘会得到右边矩阵AH的结果，得到 A×H 之后再和 W训练参数相乘，最后经过激活函数 σ 就得到下一层4个节点的特征向量了。

（3）融入中心节点自身特征属性

A×H只获得了某个节点的邻居信息，而忽略了节点本身信息。为了解决这个问题，在邻接矩阵A中将对角线的值设为 1，即每个节点会指向自身，新的卷积公式如下：

融入自身节点的图卷积

（4）节点向量聚合取平均

在上一步中聚合的结果由两部分组成：邻居属性加权求和+中心节点自身属性

聚合过程
下一步需要对加权求和的结果求平均（归一化）作为最终的这一层下节点的特征向量值，原因是如果不采取取平均的方式，度多的节点计算的特征向量会变得很大，度小的节点特征向量小，这样会改变每个节点特征原本的分布，产生一些不可预测的问题，可能会导致梯度消失或梯度爆炸，解决的办法是用度矩阵D的逆矩阵直接点乘（AX+X）

聚合求平均
最终的表达式代表节点Xi的经过卷积核聚合之后，新的特征向量为每一个邻居节点的特征向量乘以（该邻居节点和节点i的边权重 / i节点的度），使用度矩阵的逆刚好是度值的倒数，乘起来正好是（AX+X）的值除以度和自身得到平均值。

（5）对称矩阵归一化

D的逆矩阵乘上邻接矩阵是一种归一化手段，实际上是对各邻居节点的属性求平均，这样有两个问题：

结果不是对称阵：相乘之后A失去对称性，加入D的逆目的是归一化，但是不能归一化破坏了整体的对称性，影后后面和特征向量、权重相乘。对称阵元素以主对角线为对称轴对应相等，举例如下

D的逆乘邻接矩阵
聚合没有考虑节点权重：聚合时各个邻居的信息全部取平均聚合，没有考虑邻居节点自身所处的位置，比如自身的度信息，当经过多轮卷积提取，重复多次聚合循环之后，存在聚合值异常大的情况，例子如下

平均法的问题
在第一阶卷积之后B拿到了自身和周边的聚合向量，A拿到了B的初始向量，由于A只有B一个邻居，因此分母是2（和B的边以及自身），自身特征和B的特征各占1/2，A在第二阶卷积之后，A拿到了B的一阶特征向量，此时B聚合周边众多节点的特征，明显A和B的周多邻居没有连接，而经过多轮聚合之后这种仅有一个邻居且邻居为众多节点的邻居的情况。该节点计算失真。解决的方法是引入对称矩阵归一化，对邻接矩阵做对称归一化。
GCN的最终卷积表达
A波浪=A+I，I是单位矩阵
D波浪是A波浪的度矩阵
H是每一层的特征，对于输入层的话，H就是X
σ是非线性激活函数

该公式将逆拆开左乘D的-1/2右乘D的1/2，近似的归一化也保持了矩阵对称性。将公式中的对称归一化部分单独拿出来看某个中心节点i

对称归一化
在将i的周边节点j和自身一起聚合时，每次都考虑了两者的度，不论是自身i的度还是邻居j的度越大，来自于它的节点信息权重应该越小（分母越大），类似B->A<-C<-[D,E,F]这样的图关系，C和B在聚合到A时都会和A计算一次度的根号下乘积作为分母，C的作用应该比B的作用小，因为C的度大。

实际上它的目的是在
它不仅考虑了节点i对度，也考虑了邻接节点j的度，当邻居节点j度数较大时，它在聚合时贡献地会更少。

GCN实际使用

（1）GCN如何完成节点分类

GCN在对节点进行聚合、更新、循环之后，每个节点都会获得低维的特征向量表示，，维度大小和节点的特征属性向量长度一致，相当于GCN的结果是对是节点进行了embedding

GCN的计算过程

如上图所示经过几轮特征提取之后，每个节点的属性向量从Xn变成了Zn，最后基于Zn特征向量有监督地学习Yn值。即在在embedding结果之后再套一层全连接softmax即可实现节点分类，公式如下

GCN完成节点分类

此公式没有带入归一化，整体没有问题。

（2）GCN需要学习的参数

以numpy和networkx实现一个案例了解一下模型需要训练的参数个数。通过networkx导入karate_club_graph数据，数据包括34个节点，节点带有club属性，属性有Mr. Hi和Officer两种。

import numpy as np
import networkx as nx
from networkx import to_numpy_matrix
import matplotlib.pyplot as plt


zkc = nx.karate_club_graph()


def plot_graph(G):
    plt.figure()
    pos = nx.spring_layout(G)
    edges = G.edges()

    nodelist1 = []
    nodelist2 = []
    for i in range(zkc.number_of_nodes()):
        if zkc.nodes[i]['club'] == 'Mr. Hi':
            nodelist1.append(i)
        else:
            nodelist2.append(i)
    nx.draw_networkx(G, pos, edges=edges)
    nx.draw_networkx_nodes(G, pos, nodelist=nodelist1, node_size=300, node_color='r', alpha=0.8)
    nx.draw_networkx_nodes(G, pos, nodelist=nodelist2, node_size=300, node_color='b', alpha=0.8)


plot_graph(zkc)

通过上面可视化的方法将不同标签的两类节点标记为两种颜色

两类节点

假设这是一个节点分类问题，每个节点自身带有特征向量，预测节点的类型，设节点特征向量为一个34×10的随机数特征向量（34个节点，10维特征）

feature_num = 10
X = np.random.normal(loc=0, scale=1, size=(zkc.number_of_nodes(), feature_num))  # 10个特征

基于GCN的原理，图的邻接矩阵和逆矩阵是确定的，调用networkx的to_numpy_matrix得到邻接矩阵

order = sorted(list(zkc.nodes()))
A = to_numpy_matrix(zkc, nodelist=order)
I = np.eye(zkc.number_of_nodes())
A_hat = A + I  # 加上自身
D_hat = np.array(np.sum(A_hat, axis=0))[0]
D_hat = np.matrix(np.diag(D_hat))

在不考虑对称归一化的情况下，每轮卷积操作就是relu(DAXW)，下面先定义relu激活函数计算

def relu(x):
    return (abs(x) + x) / 2

relu的激活函数图像如下

relu激活函数

接下来设置权重W，设置两层W使用卷积提取两次

W_1 = np.random.normal(loc=0, scale=1, size=(feature_num, 4))
W_2 = np.random.normal(loc=0, size=(4, 2))

第一层W1承接DAX，DAX的列等于X的feature数，因此输入维度是feature_num，输出维度自定义为4，第二层W2承接W1，输入维度是4，输出维度自定义为2，这下整体打包一个函数表示DAXW和激活函数的操作

def gcn_layer(A_hat, D_hat, X, W):
    return relu(D_hat ** -1 * A_hat * X * W)

调用两次查看2层卷积之后的计算结果

H_1 = gcn_layer(A_hat, D_hat, X, W_1)
H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)

# H_2
matrix([[0.27327855, 0.        ],
        [0.75371181, 0.        ],
        [0.        , 0.        ],
        [0.87060424, 0.17736305],
        [0.        , 0.        ],
        [0.45686008, 0.        ],
        [0.41671791, 0.03714612],
        [0.826826  , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.95007397, 0.530803  ],
        [0.42302904, 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.82499985, 0.83492651],
        [0.6565228 , 0.        ],
        [0.        , 0.        ],
        [0.13741573, 0.        ],
        [0.        , 0.        ],
        [0.69028615, 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.5668888 , 0.29175253],
        [0.27512282, 0.        ],
        [0.        , 0.        ],
        [0.04185367, 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ],
        [0.        , 0.        ]])

下一步加入最后一层sigmoid

last_layer_w = np.random.normal(loc=0, scale=1, size=(2, 1))
last_layer_b = np.random.normal()
output = sigmoid(H_2 * last_layer_w + last_layer_b)

查看最终输出

matrix([[0.89480523],
        [0.92797   ],
        [0.87041837],
        [0.93672788],
        [0.87041837],
        [0.90882886],
        [0.90659049],
        [0.93208024],
        [0.87041837],
        [0.87041837],
        [0.87041837],
        [0.87041837],
        [0.944768  ],
        [0.90637759],
        [0.87041837],
        [0.87041837],
        [0.9424882 ],
        [0.9221511 ],
        [0.87041837],
        [0.88323198],
        [0.87041837],
        [0.92421981],
        [0.87041837],
        [0.87041837],
        [0.92107516],
        [0.89495514],
        [0.87041837],
        [0.87444298],
        [0.87041837],
        [0.87041837],
        [0.87041837],
        [0.87041837],
        [0.87041837],
        [0.87041837]])

此时根据标签可以计算loss梯度下降反向求导迭代了。总结一下计算过程中矩阵大小和需要训练的参数数量

计算阶段	矩阵大小	训练参数个数	备注
D_hat	34 × 34	0	邻接矩阵+自身的度矩阵
A_hat	34 × 34	0	邻接矩阵+自身
D*-1A	34 × 34	0	度逆矩阵*邻接矩阵
X	34 × 10	0	特征向量
D*-1A*X	34 × 10	0	度逆矩阵邻接矩阵特征向量
D*-1AXW1	34 × 4	10 × 4	度逆矩阵邻接矩阵特征向量*W1
D*-1AXW1*W2	34 × 2	4 × 2	度逆矩阵邻接矩阵特征向量W1 W2
(DAXW1W2)*w+b	34 × 1	2 + 1	sigmoid(w(度逆矩阵邻接矩阵特征向量W1 W2) +b)

需要训练的参数有两层卷积的W，以及最后sigmoid的w+b，一共有参数51个，邻接矩阵和度矩阵都是确定的，隐藏层的H特征向量每一层都更新，同一层下共享卷积权重W。