圖神經網絡基礎理論及實操

推薦閱讀：
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算法步驟

• 第一步：對于每一個節點添加一個共享線性映射

其中\(W\in 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(W\vec{h_i}|| W\vec{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}[W\vec{h_i ||W\vec{h_j}}]))}{\sum_{k\in N_i}exp(LeakyReLU(\vec{a^T}[W\vec{h_i ||W\vec{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}=\sigma\left(\sum\alpha_{ij}\mathbf{W}\vec{h}_j\right) $：

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^k\leftarrow\sigma(\mathbf{W}\cdot\text{мЕА}\mathbf{N}(\{\mathbf{h}_v^{k-1}\}\cup\{\mathbf{h}_u^{k-1},\forall u\in\mathcal{N}(v)\}).\)；
2、LSTM aggregator：較之方法1表達能力更強；
3、Pooling aggregator：同時考慮對稱性和可訓練性。\(\text{AGGREGATE}_k^{\mathbf{pool}}=\max(\left\{\sigma\left(\mathbf{W}_{\mathrm{pool}}\mathbf{h}_{u_i}^{k}+\mathbf\right),\forall u_i\in\mathcal{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')

參考