今天給大家介紹香港科技大學的Yilun Jin等人在AAAI 2020發表的一篇文章“GraLSP:Graph Neural Networks with Local Structural Patterns”。作者在文章中提出了一個新的圖神經網絡模型——GraLSP，針對目前GNN難以識别局部結構模式這一缺點，該模型通過随機匿名遊走将局部結構模式納入節點的鄰域特征聚合中，充分利用結構模式使得該模型能夠在多個資料集上的各種預測任務中優于其它模型。
1
研究背景
采用圖神經網絡(GNN)進行圖表示學習時，雖然基于節點鄰域内特征聚合的神經網絡表現很好，但GNN難以識别常見的節點結構模式，而這些結構模式往往在各種網絡中發揮重要作用，并且GNN在對節點鄰域進行編碼時，無法為具有不同結構模式的節點生成獨特的編碼結果。針對這一問題，作者提出了一個新的GNN架構——GraLSP，該架構首先通過随機的匿名遊走和表示結構模式的工具來捕獲局部圖結構，之後将這些遊走序列輸入到特征聚合中，在實作鄰域聚合時考慮的是如何在局部結構模式的影響下聚合節點特征，通過自适應接收半徑、注意力和放大機制來結合結構和節點的特性，而不是使用級聯将節點特征和遊走序列簡單的聚合在一起。
2
模型
GraLSP模型設計如圖1所示，首先對某個節點的随機匿名遊走進行采樣，然後将匿名遊走映射為向量，之後通過注意力和放大機制沿着結構感覺的鄰域對向量進行聚合，最後利用結構和節點鄰近度的聯合損失優化模型。
圖1 GraLSP模型設計
2.1提取結構模式
通過匿名遊走提取結構模式，對于每個節點，采樣一組長度為的随機遊走序列，然後計算它們潛在的匿名遊走的經驗分布和整個圖上的平均經驗分布作為真實分布。
2.2 結構模式聚合
在聚合結構以及節點級特征時，将重點放在如何在局部結構模式的影響下聚合節點特征，而不是使用級聯将二者簡單地聚合在一起。作者指出結構模式對圖上資訊的聚合有三個主要影響：（1）定義接收路徑；（2）确定鄰域重要性；（3）選擇性收集資訊。另外，作者提出了鄰域采樣的自适應接收半徑來解決遊走過程中通路過多或過少不同節點的問題，引用注意力子產品來模拟鄰域節點的重要性，并且引入放大子產品來模拟節點特征在鄰域中的選擇性聚合。
2.3學習模型
如果兩個匿名遊走都經常出現在同一個鄰域内，那麼它們描述的是相似的結構資訊——相同的鄰域，是以需要針對遊走鄰近度設計一個目标函數。為了保留節點特性，還需要一個目标函數來保留節點鄰近度。把以上兩個目标函數結合在一起，得到一個多任務目标函數，可以同時保留成對節點之間以及成對遊走之間的鄰近度。
3
實驗
實驗中使用的四個資料集的統計資料如表1所示：
表1 資料集統計
為了驗證GraLSP的有效性，作者将GraLSP與其它三類基線方法進行比較：（1）skip-gram models: 包括DeepWalk和LINE，它們優化了節點之間的鄰近度。（2）Structure models: 包括struct2vec和Graphwave，專注于拓撲相似性。（3）GNNs: 包括GraphSAGE、GCN和GAT。
3.1節點分類
該實驗對四個資料集進行節點分類，并且使用整個圖來學習表示向量。實驗中使用20%的節點作為測試資料集，使用80%的節點作為訓練資料集，以宏觀和微觀的F1-score對分類結果進行評估，此外，每個實驗結果都是對10個獨立實驗的結果平均值。實驗結果如表2所示，結果表明從原始GNN到GraLSP的性能增益非常大，這表明GraLSP能夠彌補GNN識别局部結構模式的缺陷。
表2 不同資料集節點分類的macro-f1 score和micro-f1 score
3.2可視化真實資料集
該實驗在真實資料集上進行可視化以定性地評估GraLSP模型，學習Cora資料集的表示向量之後利用PCA将其降維成二維向量。實驗中選擇了DeepWalk 、GraphSAGE和struc2vec與GraLSP模型進行比較，實驗結果如圖2所示， 其中黃色、綠色、藍色和紅色點對應于Cora中的4個标簽，結果表明與DeepWalk和GraphSAGE相比，GraLSP能夠産生更清晰的邊界。
圖2 二維空間中各算法的表示向量的可視化
4
總結
在論文中，作者提出了一個GNN架構——GraLSP，該架構可将局部結構模式合并到目前的GNN中。作者先分析目前GNN存在難以識别某些結構模式的缺點，之後指出匿名遊走是衡量局部結構模式的有效替代方法，然後用向量表示匿名遊走序列，并将它們合并到具有多個子產品的鄰域聚合中，最後提出一個多任務目标函數，該函數可以通過保留成對節點和遊走的鄰近度來保留特定結構下的語義。通過充分考慮局部結構模式，GraLSP模型在實驗中的表現優于各種基準模型。