摘要：圖神經網絡，graphsage

GraphSage概述

GraphSage是基于GCN的改進策略，它對GCN進行了兩點改進：

• 子圖隨機組合訓練：將GCN的全圖訓練方式改造成以節(jié)點為中心的小批量訓練方式，使得模型可以在大規(guī)模的圖數據上進行訓練，并且可以在新的圖結構上做預測，大大提供了工業(yè)場景的應用性
• 鄰居聚合操作拓展：提出了替換卷積操作的其他集中提取鄰居特征的方式

采樣鄰居

GraphSage從一組一組中心節(jié)點出發(fā)進行模型訓練，而不是GCN從全圖角度出發(fā)，因此GraphSage對節(jié)點的聚合操作需要考慮高階下的復雜度，GraphSage采用對鄰居進行隨機采樣來控制節(jié)點k階子圖的數據規(guī)模，在此基礎上對采樣的子圖進行隨機組個來完成小批量式的訓練。

節(jié)點多階/層聚合的節(jié)點范圍

節(jié)點在第k+1層的特征只與節(jié)點的第k階的鄰居有關，如果GCN的層數是2，則拿到中心節(jié)點經過2階卷積之后的特征需要將下圖中所有的節(jié)點納入計算。

采樣鄰居

鄰居節(jié)點的指數級增長和超級節(jié)點問題

假設圖上一個節(jié)點的平均度是d，如果要進行k層的GCN，一共需要納入的節(jié)點數量1+d+d²+...+d^k，其中1為中心節(jié)點自己，d為第一階，后面分別是第k階，整個呈指數級增長，導致計算復雜度極高，同時會存在某些節(jié)點的度非常大，就會進一步放大指數問題，導致高階的特征計算成本昂貴。

GraphSage的采樣策略

鄰居節(jié)點的指數級增長和超級節(jié)點的問題導致從中心節(jié)點遍歷子圖聚合計算變得非常不穩(wěn)定和不可控。GraphSage使用采樣鄰居的方式來控制子圖散發(fā)的增長率。具體的做法是給每一層的采樣設置采樣倍率S_k，例如

S₁ = 3，S₂ = 2： 所有中心節(jié)點第一階的鄰居不超過3，第二階的鄰居節(jié)點不超過2，因此一個二階模型的中心節(jié)點涉及的最多節(jié)點個數是1+3+3×2=10個（分別代表中心節(jié)點，第一層節(jié)點，第二層節(jié)點）

因此一個k階模型所有節(jié)點的數量復雜度為S_k的階乘（最后一階，個數是每層S_k相乘），采樣的時候GraphSage默認采用隨機均勻分布采樣。GraphSage的采樣策略使得模型節(jié)點的規(guī)模維持在階乘級別。

聚合鄰居

GraphSage提出了幾種新的集合操作（aggregator），首先節(jié)點聚合輸出的要求：

• 聚合輸出維度一致：在GCN中輸出維度通過鄰接矩陣乘以節(jié)點特征控制，輸出為每個節(jié)點相同維度的特征向量，在GraphSage中每層都有采樣倍率S_k，也要保證聚合之后輸出維度一致
• 聚合操作具有排列不變性：即Agg(v₁, v₂)=Agg(v₂, v₁)，聚合方式要保證和順序無關

比較簡單的符合致謝要求的聚合方式有：
*（1）平均/加和聚合算子：類似GCN的鄰居特征相加求和取平均，公式如下

Agg^sum=α(SUM{Wh_j + b, v_j∈N(v_i)})

其中w和b是聚合操作的學習參數，注意聚合結束有激活函數

*（2）池化聚合算子：類似CNN中的最大值池化，公式如下

Agg^pool=MAX{α(Wh_j + b), v_j∈N(v_i)}

其中w和b是聚合操作的學習參數，對激活函數之后的特征向量的逐個元素取最大值

GraphSage算法過程

GraphSage實現小批量訓練的具體流程如下

GraphSage算法流程

（1）采樣操作部分

其中1~7行是采樣部分

（2）聚合操作部分