作者 | 俞壹齡編輯 | 李仲深
GNN的前世今生 Humility簡介GNN的分類網絡Embedding與GNN的異同GCN從CNN到GCN -- 卷積算子的泛化譜域卷積算法SCNN-- 譜圖卷積理論的直接應用ChebNet-- 利用切比雪夫多項式對譜圖卷積理論的近似GCN -- 在ChebNet基礎上更進一步的簡化空域卷積方法ConvGNNGraphSAGE其他GATGAEGGNGSTN附圖網絡基準數據集經典圖網絡實現參考文獻代碼實現
GNN的前世今生
簡介
從圖像分類, 視頻處理到語音識別, 自然語言處理. 深度學習通過端到端的訓練徹底改變了很多機器學習任務. 但是這些任務的數據都是歐式空間上的規則數據. 而現實中很多數據之間都有著相當複雜的關係, 一般表現為非歐空間之上的圖結構.
為處理圖數據之上的任務, 圖神經網絡就應運而生了.
GNN的分類
GCN -- 圖卷積神經網絡譜域空域池化模型GAT -- 圖注意力網絡GAE -- 圖自編碼器GGN -- 圖生成網絡GSTM -- 圖時空網絡
圖一: GNN的分類網絡Embedding與GNN的異同
網絡embedding旨在在保留網絡拓撲結構和節點信息的基礎之上, 在低維向量空間之中對網絡節點進行表示.
得到的嵌入向量可以用於後續的各類任務.
網絡embedding的方法可以大體分為如下三類 :
矩陣分解隨機遊走深度學習其中第三點深度學習的方法需要使用GNN的模型. 可以是GAE, 也可以是無監督的GCN.
GCN
圖二: 常見的GNN模型分析從CNN到GCN -- 卷積算子的泛化
CNN的成功在於他的卷積核能夠提取整個數據集上共享的局部特徵. 而CNN中卷積算子的定義依賴於圖像這種規則數據的平移不變性和局部連結性.
想要在圖網絡中複製CNN的成功, 泛化和定義新的卷積算子便是一種良好的方案.
圖三: 從2D卷積到圖卷積譜域卷積算法
圖四: 圖卷積發展歷史譜域卷積主要的理論依據是卷積定理 : 時域中的卷積同構與譜域中的乘法. 譜域卷積通過離散傅立葉變換把拓撲圖映射到譜域, 然後據此來定義自己的圖卷積算子.
主要的模型有SCNN、ChebNet和GCN(按發表時間升序排列). 這三個模型都是基於同一種算法, 可以說是一脈相承的了.
圖二:譜域卷積公式圖五: 圖離散卷積算法SCNN -- 譜圖卷積理論的直接應用
圖結構的刻畫 : (拉普拉斯矩陣)與特徵矩陣拉普拉斯矩陣用於刻畫圖的結構信息.
易知L是一個非負定矩陣, 對其進行相似對角化處理可得
其中的對應了圖中的離散傅立葉變換(具體推導可以參考傅立葉變換和拉普拉斯算子之間的關係).
圖中除了用拉普拉斯矩陣刻畫的結構信息之外, 還有每個節點上的信息. 這種節點信息我們一般會用特徵向量來對人工選擇的特徵進行量化. 每個節點的特徵組合起來就得到了我們的特徵矩陣, 也就是最底層的語義. 特徵矩陣和拉普拉斯矩陣一起完成了對圖中信息的量化.
卷積定理: 時域中的卷積同構於頻域中的乘法由此我們可以定義與兩個函數之間的卷積.
離散形式:為了便於參數的設置和反向傳播, 我們取作為卷積核.
這樣就給出了文中的卷積公式
前向傳播的公式其中是我們的第k層的卷積層. 他的行數是輸入的通道數, 列數為輸出的通道數.
ChebNet -- 利用切比雪夫多項式對譜圖卷積理論的近似
既然前文中提到的SCNN中特徵分解的開銷難以接受, 我們可以對其進行近似處理從而簡化運算.
ChebNet就是這樣一個在SCNN的基礎上做了近似處理的網絡.
採用Chebyshev多項式對譜域卷積的卷積核進行插值.這邊是Chebyshev多項式:這裡用於多項式插值.這是利用Chebyshev多項式近似後的卷積核.上述插值過程中還有一個小小的trick(你有沒有注意到呢?)這是一個標準化處理, 將中的特徵值全部化到[-1, 1]這個區間內, 旨在避免網絡迭代層數過深帶來的梯度爆炸問題.GCN -- 在ChebNet基礎上更進一步的簡化
GCN在前面ChebNet的基礎上再一次進行了簡化. 他只取了卷積核Chebyshev插值多項式的前兩項, 而且預設了這兩項前面的參數相等. 將每個卷積核可學習的參數量降低到了1.
這就是GCN的卷積核. 其中就是它可學習的參數.
除了更精簡的近似之外, GCN中還有兩點trick:
是在鄰接矩陣的基礎上加上了自環, 將節點自身的特徵也添加到了網絡之中.對拉普拉斯矩陣的標準化和對稱化.空域卷積方法
譜域卷積基於圖譜理論, 具有相當良好的可解釋性. 但是譜域上的模型一來只能對整幅圖進行處理, 而且無法處理變化的圖結構. 這時候空域卷積方法或許是更好的選擇.
卷積算子的定義: 採樣 + 聚合. 用於特徵提取ConvGNN
歐式空間上的卷積可以理解為先對固定數量的鄰域進行排序, 然後使用卷積核進行內積.
非歐空間之上圖結構的卷積也可以參考這種模式.
在這裡插入圖片描述圖六: 圖卷積的泛化定義 採樣 + 聚合利用隨機遊走這一馬爾科夫過程, 以步之內節點被訪問次數的期望進行排序.以標準化之後的圖相似度矩陣來作為狀態轉移矩陣.取期望最大的個節點作為的鄰域, 按期望由大到小排序.使用參數數量為的一維卷積和對鄰域進行卷積操作.
圖七: 空域卷積網絡GraphSAGE
*SAGE(Sample and AggreGatE)*不同於前面的GNN, GraphSAGE認為卷積是採樣加上的信息的聚合.
採樣均勻採樣法: 在節點一階相連的節點上均勻採樣, 構建固定大小的鄰域.
聚合GraphSAGE認為節點的鄰域中沒有順序可言, 所以要求聚合函數不依賴於鄰域節點的輸入順序.
均值聚合 : 取鄰域內節點的均值.LSTM聚合 : -- 這個真的是順序無關的嗎???Pooling聚合 : 採用Max Pooling.聚合函數聚合之後還需要結合自身信息然後進行卷積和激活.
最後進行標準化以防止梯度爆炸和梯度消失.
其他
空域卷積網絡還有著各種各樣的變體. 諸如LGCN, MoNet之類的, 在此不多贅述.
GAT
都說Attention is all you need.
GAT模型將attention機制引入圖卷積模型, 為更重要的節點分配更大的權重.
正常的圖卷積神經網絡卷積核的參數都是共享的, 這種就是所謂的分心模型. 他預設了輸入節點對不同的輸出節點的影響是相同的.
但是從我們人的認知模型出發, 輸入節點對不同的輸出節點影響肯定是不同的. 所以就提出了所謂的Attention機制. 通過每個輸出節點上掛載的權值數組來衡量各個輸入節點對該輸出的重要程度.
圖八: 注意力機制中權重的分配計算節點之間的關聯度 其中為注意力係數, 可以認為它正比於兩節點的關聯度.利用softmax歸一化, 求得注意力係數.以上文求得的注意力係數作為權重來對鄰域節點的信息進行聚合, 完成圖卷積操作.其中的是共享的權值, 而真正的差異化的卷積核為.
GAE
圖九: 自編碼器圖自編碼器, 一種自監督的學習框架. 通過編碼器學習網絡節點的低維表示, 然後通過解碼器重構圖數據.
GAE最早使用GCN來作為編碼器.
其中X為節點特徵, 為圖的鄰接矩陣.
解碼器:
採用變分法進行訓練, 最小化變分下界
近來又提出了一種對抗正則化自編碼器(ARGA), 利用GAN的方案訓練正則化圖自編碼器.
編碼器用節點的特徵編碼其結構信息, 也就是GCN中的隱層表示, 然後解碼器從編碼器的輸出中重構鄰接矩陣. GANs在訓練生成模型的時候在生成和判別模型之間進行一個最小-最大博弈. 生成器儘可能生成真實的「偽樣本」, 而判別器則儘可能從真實樣本中識別」偽樣本「.
圖十: 常見GAE總結GGN
圖生成網絡, 從數據中獲取圖的經驗分布, 然後根據經驗分布來生成全新圖結構的網絡.
特定領域有很多圖網絡模型, 比如用於分子圖生成的SMILES.
近來提出了一些統一的生成方法, 其中有一部分將圖生成看做節點和邊的交替生成的過程, 另一部分採用GAN的方案進行訓練.
GSTN
圖時空網絡, 處理時空圖的網絡. 利用GCN提取空間特徵, 然後將時間離散化使用CNN或者RNN來提取時間特徵.
圖十一: 圖時空網絡匯總附
圖網絡基準數據集
圖十二: 基準數據集匯總經典圖網絡實現
圖十三: 經典圖網絡實現匯總參考文獻
[[1901.00596] A Comprehensive Survey on Graph Neural Networks (arxiv.org)](https://arxiv.org/abs/1901.00596#:~:text=In this survey%2C we provide a comprehensive overview,networks%2C convolutional graph neural networks%2C graph autoencoders%2C )
[1710.10903v3] Graph Attention Networks (arxiv.org)
[1801.07455] Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition (arxiv.org)
[1312.6203] Spectral Networks and Locally Connected Networks on Graphs (arxiv.org)
[1706.02216] Inductive Representation Learning on Large Graphs (arxiv.org)
代碼實現
見圖十三