图神经网络基础理论及实操

推荐阅读：
1、https://github.com/PacktPublishing/Hands-On-Graph-Neural-Networks-Using-Python
2、GAT：http://arxiv.org/abs/1710.10903
3、GCN：http://arxiv.org/abs/1609.02907
4、GraphSAGE：http://arxiv.org/abs/1706.02216

任务经常加。。。
1、实操任务

• 节点分类任务实操解释
• 边任务实操
• 等

2、GCN GAT等内容细节补充：

• 结构细节
• 结构解释
• GAT详细了解
• 等

1、图神经网络基础知识

1.1 图基本理论

对于图神经网络的提出背景：常规算法（机器学习、卷积神经网络等）处理的大多为欧几里得空间数据（Euclidean space）[一般指：图片等数据]

欧几里德数据：数据特点是排列整齐。对于某个节点，很容易可以找出其邻居节点，就在旁边，不偏不倚。最常见到的是图片(image)和视频(video)以及语音(voice)。
非欧几里德数据：排列不整齐，比较的随意。具体体现在：对于数据中的某个点，难以定义出其邻居节点出来，或者是不同节点的邻居节点的数量是不同的。

但是对于一些非欧几里得空间数据（比如家族图谱、人物关系图谱等）对于传统神经网络来说几乎是处理不了的（换句话来说：世间万物之间都是彼此相互联系的，传统的深度学习、机器学习处理的都是单一，简单数据问题），因此提出图神经网络（(Graph quad Neural quad Network)）

对于一组图定义为：(G=(V,E,R,T))其中：1、节点：(v_i in V)；2、不同节点之间联系：((v_i, r, v_j))；3、节点之间相关性：(r in R)；4、节点类型：(T(v_i))。简单上理解一幅“图”就是若干个节点在若干节点之间彼此联系（连接| 联系类型分为：有向、无向、权重、自循环等）。

比如说：

在上图中有3个人（A、B、C 紫色代表男生）彼此之间是联系的，并且我们定义各自的特征：V1、V2（比如说生高、体重）。比如我们在做节点分类任务时候，就需要根据其特征进行分类。

from torch_geometric.data import Data
import torch
x = torch.Tensor([[185, 75], [160, 65], [192,80]])
edge_index = torch.Tensor(
   [[0,0,1,1,2,2],
   [1,2,0,2,0,1]]
)
y = torch.Tensor([[0, 0], [1, 0], [2, 1]])
data = Data(x= x, edge_index= edge_index, y= y)
print(f'点的数量: {data.num_nodes}')
print(f'边的数量: {int(data.num_edges/2)}')
print(f'节点特征维度: {data.num_edges / data.num_nodes:.2f}')   #2E/N 
# print(f'训练节点数量: {data.train_mask.sum()}')
# print(f'训练节点比率: {int(data.train_mask.sum()) / data.num_nodes:.2f}')
print(f'包含孤立节点: {data.contains_isolated_nodes()}')
print(f'包含自循环: {data.contains_self_loops()}')
print(f'是否为无向图: {data.is_undirected()}')

点的数量: 3
边的数量: 3
节点特征维度: 2.00
包含孤立节点: False
包含自循环: False
是否为无向图: True

便于数学上理解将一幅图（定义比较宽泛：可以是人物关系图谱、图片像素联系等）转化成一组邻接矩阵（Adjacency Matrices）

更加简单定义：(G=(V,E))其中：(V)代表图中的节点；(E)代表不同节点之间的边（点之间权重、有向/无向）；

对于图的生成上借助networkx^[1]进行操作：

• 1、定义图(有向/无向)

import networkx as nx
G1 = nx.Graph() # 定义有向图
G2 = nx.DiGraph() # 定义无向图
"""
可以直接对数组等进行操作
a=np.random.randint(0,2,size=(5,5))   #产生5行5列的随机整矩阵,因为要生成图，所以必须是方阵
G=nx.DiGraph(a)
"""

• 2、添加/删除边
  如果需要设置权重，只需要在定义边时，添加{参数说明： 参数值}这样一来所有的边与边之间都会使用参数说明(如：{"color":"red"})

G1.add_edges_from([('A', 'B'), ('C','D'), ('B', 'C')])
G1.remove_edges_from([("A", "B")])
"""
G1.remove_edge("A", "B")
"""
G1.add_edges_from([('A', 'B', {"weight": 10}), ('C','D',{"weight": 10})])
# nx.get_edge_attributes(G2, "weight") 即可访问参数weights
# G1.edges() 访问边之间联系

• 3、添加/删除点

G1.add_node("spam") 

基础理论：

1、邻接矩阵 (A)

2、度矩阵 (D)

也就是说计算与节点(i)连接的边的个数

(D^{- 1/2}) 相当于对于每一个元素开根号

nx.to_numpy_array(G1)

0### 1.2 图embedding方法

1.2.1 DeepWalk算法^[2][3]

将自然语言处理的算法（work2vec^[4]）引入到图神经网络中来。word2vec通过语料库中的句子序列来描述词与词的共现关系，进而学习到词语的向量表示。DeepWalk算法与word2vec类似，使用图中节点与节点的共现关系来学习节点的向量表示。在DeepWalk中通过使用随机游走(RandomWalk: 从图中随机选择节点)的方式在图中进行节点采样来模拟语料库中的预料，进而使用word2vec的方式学习出节点的共现关系^[5]。DeepWalk在算法上首先通过随机游走采样节点序列，而后使用skip-gram model学习表达向量。

skip-gram介绍
在论文中，作者介绍了两个结构CBOW以及skip-gram

skip-gram从当前位置词去预测前后的词，比如服务器托管网说:：我叫小明，选择参数 (input word, skip window, window size)，（设置 skip window=1, window size=2，也就是说对于input word我们去访问其前后“窗口”1个词，window size那么就将input word与开始选择的“窗口”中的词进行组合， 选择出2个词）那么在获取第一个词我的时候，其“窗口”为：我叫（因为前面没有词）那么得到为（我叫）

1.2.2node2vec

2、基本图神经网络

2.1 图卷积神经网络

沿用论文^[6]中对图神经网络的定义：

其中：

从函数定义上，和一般的神经网络很相似：设计一个网络结构（就是我们的参数(W)），输出数据然后通过优化算法去对参数进行优化。

• 1、(A+I) 理解

我们知道在一组图（社交网络等）中节点之间彼此联系，并且节点自身具有特性（ 那么就需要对两个都进行考虑 ），那么在构建模型过程中需要保证 对于节点自身以及节点之间信息 进行充分考虑（亦或者说：对信息进行传递）。正如上面（图的定义）所提到的，我们需要把一组图转化为一个邻接矩阵(A)对其进行数学表示，而后将得到的邻接矩阵和(XW)就行相乘，这样一来就考虑到了节点之间联系了。但是为什么不将函数设计成(VanillaGNN)：

给出了解释^[7][8]。

• 1、没有考虑到自身节点信息自传递的问题；
• 2、(A)通常未标准化，因此与(A)相乘将完全改变特征向量的尺度
• 更加直观的解释：比如说节点A有1000个邻居节点，而节点B只有1个邻居节点，这样一来计算得到的值之间差距就较大。

所以对于邻接矩阵（(A)）加上单位矩阵（(I)）就相当于在图中添加一个自循环

• 2、(D^{- 1/2}(A+I)D^{- 1/2}) 的理解

对于(D^{- 1/2}(A+I)D^{- 1/2}) 被称为：normalize the adjacency matrix

为什么要执行标准化 ？为什么不直接用

回顾图的定义：一组图由两部分构成点和边（以节点分类任务为例）；对于结点 (i) 我们需要通过结合与节点 (i) 相连接的其它节点和他们之间的边的信息来对 (i) 进行判断。那么也就是说我们要首先对邻接节点信息进行汇聚（Aggregate information）而后后续操作。既然要对对数据进行汇聚，那么问题来了：在图中有些结点与其它节点之间存在较多连接，而有些节点可能就只有一个节点和他连接。

如果直接用公式((2)) 这样虽然考虑到节点之间信息但是在后续对于参数优化上就会造成困难，所以一个最直接的例子就是：既然连接点数量之间存在差异，那么我直接去除以你的节点个数！！

2.1.1 卷积图神经网络理解

对上述公式(f(X,A)= sigma(D^{- 1/2}(A+I)D^{- 1/2}XW))将其简化为(f(X,A)=sigma(widehat{A}XW))
借用如下图^[9]理解图卷积算法(其中(H)对应上述公式中的(X))

回顾简化的图卷积函数（ (f(X,A)=sigma(widehat{A}XW)) ），图卷积网络在设计上借鉴了卷积神经网络，矩阵(widehat{A})中存在许多0也就是说，我们可以通过对于某个节点设计一个 “卷积核” ，去对与之相连接的节点进行“卷积运算”而后进行“池化”操作

2.1.2 GCN代码

from torch_geometric.nn import GCNConv
import torch.nn.functional as F

# 实现形式1
class GCN(nn.Module):
    def __init__(self, input_dim: int, class_label: int):
        super(GCN, self).__init__()
        self.conv1 = GCNConv(input_dim, 16)
        self.conv2 = GCNConv(16, class_label)

    def forward(self, data):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        output = self.conv2(x, edge_index)

        return output

# GCN定义
from dgl.nn import GraphConv
class GCN(nn.Module):
    def __init__(self, in_feats, h_feats, num_classes) -> None:
        super(GCN, self).__init__()
        self.conv1 = GraphConv(in_feats, h_feats)
        self.conv2 = GraphConv(h_feats, num_classes)
    
    def forward(self, g, in_feats):
        h = self.conv1(g, in_feats)
        h = F.relu(h)
        h = self.conv2(g, h)
        return h

参考：
1、http://arxiv.org/abs/1609.02907
2、https://mbernste.github.io/posts/gcn/
3、https://zhuanlan.zhihu.com/p/89503068
4、https://blog.csdn.net/zbp_12138/article/details/110246797

2.2 图注意力网络 GAT

GAT网络特征：

• 1、可以跨越节点就行并行化操作
• 2、它可以通过为邻居节点指定任意权重，应用于具有不同度的图节点

此处区别GCN，GCN是直接计算邻居节点的平均（权重是恒定的）

• 3、该模型直接适用于归纳学习问题，包括模型必须泛化到完全看不见的图形的任务

Global graph attention^[10]
就是每一个顶点(i)都对于图上任意顶点都进行attention运算。完全不依赖于图的结构，可能造成：（1）丢掉了图结构的这个特征，效果可能会很差（2）运算面临着高昂的成本

(1) the operation is efficient, since it is parallelizable across nodeneighbor pairs;
(2) it can be applied to graph nodes having different degrees by specifying arbitrary weights to the neighbors;
(3) the model is directly applicable to inductive learning problems, including tasks where the model has to generalize to completely unseen graphs.

2.2.1 GAT网络定义

论文^[11]中定义：输入一系列节点特征(h={vec{h_1},…,vec{h_N} })其中(vec{h_i} in R^F)，(N)代表节点的数量，(F)代表每一个节点特征数量。GAT算法步骤

• 第一步：对于每一个节点添加一个共享线性映射

其中(Win R^{{F^ prime}*F})，通过计算进而对顶点特征就行增维，(||)去对特征就行拼接(axis=1)

• 第二步：对于线性映射的节点添加注意力机制(self-attention)

其中(e_{ij})代表 注意力系数 用来计算节点 (i) 邻居节点 (j) 对其的重要性，(a)是一层前馈神经网络。这样一来模型允许每个节点参与到其它节点上，进而省去了所有的结构信息，并且使用(LeakyReLU)作为激活函数。

masked attention
we only compute eij for nodes j ∈ Ni, where Ni is some neighborhood of node i in the graph.
也就是说对于节点(i)只计算与之相联系的节点

此处也印证了GAT的特征3，对于inductive learning problems，在GAT中去改变网络结构无非就是改变(N_i)

• 第三步：添加激活函数以及计算(softmax)

其中(T)代表转置，(||)代表串联操作

• 第四步：多头注意力处理

其中(sigma)代表非线性激活。对于多头注意力：

算法流程图：

对于上图左半部分（ 注意力机制 ）很好理解：就相当于对节点做一个矩阵相乘（(W)），而后通过前馈神经网络（(LeakyReLU)和(softmax)）进行处理得到(alpha_{ij})。对于右半部分：对于节点(vec{h_1})假设6个节点与其联系。对于每一个联系节点通过 3层（上述图中3中颜色）注意力进行处理。对后续结果进行拼接/平均（(concat/avg)）得到(vec{h_1^})。

代码解释上述过程(以如下网络为例)

那么可以定义我们如下数据图A数据X：

import numpy as np 
np.random.seed(0) 
A = np.array([[1, 1, 1, 1], [1, 1, 0, 0], [1, 0, 1, 1], [1, 0, 1, 1] ])
X = np.random.uniform(-1, 1, (4,4))

那么计算(e_{ij}=a(Wvec{h_i}|| Wvec{h_j}))（(a)代表前馈神经网络）这样一来就需要定义两个参数：

W = np.random.uniform(-1,1, (4,4)) # 内部矩阵乘法
W_att = np.random.uniform(-1, 1, (4,4)) #外层的前馈神经网络

connections = np.where(A>0) # 这样一来就可以知道那些点之间是连接的
"""
输出：
(array([0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3]),
 array([0, 1, 2, 3, 0, 1, 0, 2, 3, 0, 2, 3]))
 代表(0,0) (0,1) (0,2), (0,3)是连接的
"""
a = W_att@ np.concatenate([(X@W.T)[connections[0]], (X@ W.T)[connections[1]]], axis=1).T

计算(alpha_{ij}=frac{exp(LeakyReLU(vec{a^T}[Wvec{h_i ||Wvec{h_j}}]))}{sum_{kin N_i}exp(LeakyReLU(vec{a^T}[Wvec{h_i ||Wvec{h_k}}]))})

def leaky_relu(x, alpha=0.2):
    return np.maximum(alpha*x, x)
def softmax2D(x, axis): 
    e = np.exp(x - np.expand_dims(np.max(x, axis=axis), axis)) 
    sum = np.expand_dims(np.sum(e, axis=axis), axis) 
    return e / sum 
e = leaky_relu(a)
E = np.zeros(A.shape)
E[connections[0], connections[1]] = e[0]
W_alpha = softmax2D(E, 1)

最后计算$vec{h}i^{prime}=sigmaleft(sumalpha_{ij}mathbf{W}vec{h}_jright) $：

H = A.T @ W_alpha @ X @ W.T

对于多头注意力只需要重复设置W,W_att即可

3.其他图神经网络结构

3.1 STGNN（Spatio-Temporal Graph Convolutional Networks）

作者^[12]在处理交通网络预测过程中出现：交通流的非服务器托管网线性以及复杂性，不是借助传统的 卷积单元 和 循环单元 而是通过图神经网络进行处理。并且提出时空图卷积网络（STGNN）
作者对于交通预测描述如下：

也就是说：根据(M)个过去时间节点数据预测未来(H)时刻数据，其中(v_t in R^n)代表在(n)条道路在时间(t)下的观察向量（记录道路的流量）

因此作者将上述结构定义如下图神经网络：$G_t= (V_t, varepsilon, w) $分别代表有限节点集合、边、权重。

3.1.1 网络结构

输入数据（(V_{t-M+1},…,V_t)）而后通过两层ST-Conv Blovk以及全连接层进行预测输出。ST-Conv Block结构（中间部分）包含两个时间门控卷积层（Temporal Gated-Conv），中间包含一个空间图形卷积层（Spatial Graph-Conv）。在每个块内部应用了残差连接和瓶颈策略。

• ST-Conv Block

ST-Conv Block结构由：Temporal Gated-Conv（TGC） + Spatial Graph-Conv（SGC） + Temporal Gated-Conv，对于此类结构作者给出的解释：可以通过时间卷积实现从图卷积到空间状态的快速传播。”三明治”结构还帮助网络充分运用瓶颈策略，通过图卷积层对通道C进行降尺度和升尺度处理，实现尺度压缩和特征压缩。此外，在每个ST-Conv块中使用层归一化来防止过拟合

Can achieve fast spatial-state propagation from graph convolution through temporal convolutions. The “sandwich” structure also helps the network sufficiently apply bottleneck strategy to achieve scale compression and feature squeezing by downscaling and upscaling of channels C through the graph convolutional layer. Moreover, layer normalization is utilized within every ST-Conv block to prevent overfitting

• Temporal Gated-Conv（TGC）

对于TGC通过 1-D casual convolution 和 gated linear units（GLU^[13]） 构成

参考
1、http://arxiv.org/abs/1709.04875
2、https://zhuanlan.zhihu.com/p/286445515

3.2 Gated Graph Sequence Neural Network^[14]

从名字上很好理解，(GGSNN)（门控序列图神经网络）是作为一种可以对序列进行预测的图神经网络，作者提到该网络添加：1、门控序列单元（gated recurrent units）；2、“优化”方法（modern optimization techniques）

• 1、门控图神经网络（Gated Graph Neural Network）

3.3 GraphSAGE

GrapgSAGE一种处理大规模图的GNN结构，它利用节点特征信息（例如文本属性）来高效生成先前未见数据的节点嵌入。相较之之前的神经网络结构对于生成节点嵌入本质上是传导性，方法上也都基于矩阵分解。^[15]

• 1、前向传播算法（forward propagation algorithm）

从伪代码上很好理解，上述参数中：K：网络的层数，也代表着每个顶点能够聚合的邻接点的跳数。算法步骤：在每一层的循环k中，对每个顶点v，首先便用 v 的邻接点的k-1层的embedding表示 (h_u^{k-1})其临近顶点的第k层聚合表示 (h_{N(v)}^k)，之后将(h_{N(v)}^k)和顶点(v)的第(k-1)层表示(h_u^{k-1})一个非线性变换产生顶点(v)的第(k)层embedding表示(h_v^k)。进行拼接，经过一个非线性变换产生顶点v的第k层embedding表示(h_v^k)

比如说在(k=1)时并不是将其所有的联系节点信息进行聚合，而是通过采样之后再去汇聚

• 2、聚合结构（Aggregator Architecture）

聚合结构就和卷积神经网络中的池化层一样，对于节点(h_v^0)在 (K=k)与之连接的节点信息进行“聚合”。在论文中提供了：
1、Mean aggregator：(mathbf{h}_v^kleftarrowsigma(mathbf{W}cdottext{}mathbf{N}({mathbf{h}_v^{k-1}}cup{mathbf{h}_u^{k-1},forall uinmathcal{N}(v)}).)；
2、LSTM aggregator：较之方法1表达能力更强；
3、Pooling aggregator：同时考虑对称性和可训练性。(text{AGGREGATE}_k^{mathbf{pool}}=max(left{sigmaleft(mathbf{W}_{mathrm{pool}}mathbf{h}_{u_i}^{k}+mathbf{b}right),forall u_iinmathcal{N}(v)right}),)

3、GNN实操

3.1 节点分类^[3:1]

使用数据集：Facebook Page-Page dataset
任务分析
编程理解：节点分类任务，其实对于图神经网络，就是一个大型的矩阵，设计算法也就是去对矩阵进行分析

from torch_geometric.datasets import FacebookPagePage
import pandas as pd
import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.utils import to_dense_adj

facebook_data = FacebookPagePage(root='./GNN-data/facebook') # 下载数据集
data = facebook_data[0]
# print(f'Dataset: {facebook_data}') 
# print('-----------------------') 
# print(f'Number of graphs: {len(facebook_data)}') 
# print(f'Number of nodes: {data.x.shape[0]}') 
# print(f'Number of features: {facebook_data.num_features}') 
# print(f'Number of classes: {facebook_data.num_classes}')

data.train_mask = range(18000)
data.val_mask = range(18001, 20000) 
data.test_mask = range(20001, 22470)

df_x = pd.DataFrame(data.x.numpy()) # 得到所有节点数据：x:点特征;y:点标签
df_x['labels'] = pd.DataFrame(data.y)

def accuracy(pred, true):
    return torch.sum(pred == true)/ len(true)

class MLP(nn.Module):
    def __init__(self, dim_in, dim_h, dim_out) -> None:
        super().__init__()
        self.l1 = nn.Linear(dim_in, dim_h)
        self.l2 = nn.Linear(dim_h, dim_out)
    
    def forward(self, x, **kwargs):
        return F.log_softmax(self.l2(torch.relu(self.l1(x))), dim=1)

class VanGNNLayer(nn.Module):
    """
    计算：A^TXW^T
    """
    def __init__(self, dim_in, dim_out) -> None:
        super().__init__()
        self.l1 = nn.Linear(dim_in, dim_out)
    def forward(self, x, adjacency):
        x = self.l1(x)
        x = torch.sparse.mm(adjacency, x)
        return x
    
class VanGNN(nn.Module):
    def __init__(self, dim_in, dim_h, dim_out) -> None:
        super().__init__()
        self.gnn1 = VanGNNLayer(dim_in, dim_h)
        self.gnn2 = VanGNNLayer(dim_h, dim_out)
    def forward(self, x, adjacency):
        out = self.gnn1(x, adjacency)
        out = torch.relu(out)
        out = self.gnn2(out, adjacency)
        return F.log_softmax(out, dim=1)
    
def fit(model, data, epchos: int=50, learning_rate: float=0.0001, adjacency: torch.Tensor=None):
    loss_fn = torch.nn.CrossEntropyLoss()
    optimizer = torch.optim.Adam(model.parameters(), lr= learning_rate)
    model.train()
    for epcho in range(epchos):
        out = model(data.x, adjacency= adjacency) 

        loss = loss_fn(out[data.train_mask], data.y[data.train_mask])
        acc = accuracy(out[data.train_mask].argmax(dim=1), data.y[data.train_mask])
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()
        if epcho %20==0:
            val_loss = loss_fn(out[data.val_mask], data.y[data.val_mask])
            val_acc = accuracy(out[data.val_mask].argmax(dim=1), data.y[data.val_mask])
            print(f'Epchos{epcho:>3} || train loss:{loss:.3f} || Train Acc: {acc:.3f}
                    Val loss{val_loss:.3f} || Val Acc{val_acc:.3f}')
            
def test(model, data):
    model.eval()
    out = model(data.x, adjacency= adjacency) #此处修改
    acc = accuracy(out.argmax(dim=1)[data.test_mask], data.y[data.test_mask])
    return acc

adjacency = to_dense_adj(data.edge_index)[0] # data.edge_index表示节点之间联系
adjacency += torch.eye(len(adjacency))

print('MLP:')
mlp = MLP(facebook_data.num_features, 16, facebook_data.num_classes)
fit(mlp, data, epchos=100)
acc_mlp = test(mlp, data)
print(f'MLP test accuracy:{acc_mlp*100:.2f}%n')

print('VanGNN:')
van = VanGNN(facebook_data.num_features, 16, facebook_data.num_classes)
fit(van, data, epchos=200, adjacency= adjacency)
acc_van = test(van, data)
print(f'VanillaGNN test accuracy:{acc_van*100:.2f}%n')

参考

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net