今天為大家介紹Felix L. Opolka和Pietro Li`o在ELLIS上的一篇文章，這篇文章是關于圖的連結預測的。作者介紹了一種新的在圖節點上運作的圖卷積高斯過程模型，先是通過圖形卷積變換将歐幾裡得域上的高斯過程轉換成圖形卷積高斯過程，再進一步調整節點上的生成模型來适應節點對上的高斯過程，以此來進行連結預測。
1
介紹
近期在連結預測領域的工作專注于具有兩個關鍵屬性的方法。第一，這些方法可以根據圖結構本身和圖節點上的信号(通常稱為節點特征)來預測缺失的連結。其次，這些方法不僅從每個節點的孤立特征計算節點嵌入，還考慮了每個節點的局部鄰域特征，進而為預測缺失連結提供了更多的上下文資訊。這些方法的核心通常是具有參數化圖卷積操作的神經網絡，雖然這些神經網絡模型達到了最先進的性能，但由于使用最大似然估計優化了大量參數，它們需要大量的标記資料。為了克服以上不足，作者提出用高斯過程模型來處理鍊路預測任務。所提出的模型在識别圖結構和節點特征的同時，利用圖卷積在預測連結時納入鄰域資訊。通過在貝葉斯推理設定中邊緣化參數和使用變分下界優化超參數來對抗過拟合，是以無需為early stop設定驗證集。此外，高斯過程為下遊任務提供了擷取估值的方法。
2
背景
1.1高斯過程
1.2圖卷積
圖卷積通過将本地模式嵌入節點表示中，抓住本地特征的歸納。圖卷積的出現得益于卷積神經網絡的啟發，并将卷積運算從規則網格的域推廣到一般圖的域。
3
相關工作
3.1 圖結構資料的高斯處理
先前圖結構資料的高斯過程模型已經在關系學習這個術語下進行了研究。這些方法已應用于圖中節點的半監督分類，例如：關系高斯處理、混合圖高斯過程、标簽傳播算法等。受圖形神經網絡的啟發，最近的研究開發了高斯過程模型，明确地考慮節點及其鄰近節點的特征。2018年NG提出的圖高斯過程通過平均1跳鄰域的節點特征來計算節點表示，然後執行半監督節點分類。與作者提出的圖卷積高斯過程不同，它隻考慮1跳節點的鄰域，進而限制了模型對節點鄰域資訊的通路。2017年van der Wilk提出的圖形卷積高斯過程使用圖卷積産生圖中小塊的表示，并通過累積的高斯過程模型總結這些小塊。與目前所描述的模型不同，它用于圖像或網格分類等圖級預測。目前唯一的另一個用于鍊路預測的高斯處理模型是由Yu，K.和Chu,W. 2008年提出的， 但它不包含來自鄰居節點的資訊，這限制了它的預測性能。
3.2連結預測模型
2018年Zhang, M.和Chen, Y.系統探索了由啟發式模型表示的一種常見的連結預測方法，這些方法計算節點相似性的啟發式算法，并将其作為連結的可能性輸出。流行的啟發式方法包括共同鄰居、Jaccard、偏好連結、Adamic-Adar等。其他方法則側重于基于從圖結構中導出的潛在節點特征來預測連結。例如，通過光譜聚類計算出的節點特征可以用于鍊路預測。其他的潛在特征方法是矩陣分解和鍊路預測的随機塊模型(SBM)
另一類鍊路預測方法利用神經網絡。2017年提出的MLNM利用鄰接矩陣訓練全連接配接神經網絡。2018年的SEAL在非機率設定中使用圖形神經網絡。網絡運作在節點特性和手工制作的節點标簽上，表明一個節點在它的鄰居的作用。與作者模型最相似的是，Kipf, T. N.和 Welling, M. 2016年提出的的圖變分自動編碼器結合了機率模組化和圖卷積，是以也考慮了鄰域資訊。由于依賴節點表示之間的内積，連結上分布的形式受到了更大的限制。相反，作者通過選擇變分分布作為一個高斯過程來評估誘導點，而誘導點本身是自由參數，進而實作了很高的靈活性。
4
模型
4.1 圖卷積高斯過程
作者從一個正常的高斯過程開始，它隻作用于對圖結構無關的節點特征。每個節點特征被視為歐幾裡得域 上的一個觀測。這個高斯過程被轉換使用簡化的圖形卷積，以産生一個圖形卷積對圖的節點 進行高斯處理g. 最後，定義的一系列圖卷積高斯過程按下面公式在邊緣上生成一個卷積高斯過程r的圖。上面過程中的函數值分别通過節點的大小和連結的厚度來表示。
4.2使用稀疏變分高斯過程的連結預測
作者要将節點上的這種高斯過程轉換為節點對上的高斯過程以預測它們之間的潛在邊緣。預測節點對之間的潛在連結可以歸結為一個二進制分類問題，它規定了伯努利可能性。這将導緻一個難以處理的後驗分布，作者将用一個變分分布來近似它。作者還将使用一組m誘導點來降低推理的計算複雜度。
5
實驗
5.1資料集
資料集如下圖所示：
5.2實驗裝置
5.3結果
作者将自己提出的圖卷積高斯過程與2008年提出的帶核函數的非卷積高斯過程、2016年提出的變分圖自動編碼器對比試驗，以兩種标準進行比較：ROC曲線下面積(AUC)和平均準确率(AP)。AUC的标準下結果如下圖所示：
AP标準下結果如下圖所示：
在比較作者提出的的GCLGP與非卷積LGP相比，我們發現前者在大多數資料集上優于後者，某些資料集的AUC高達10.0。我們發現，在AUC方面，8個資料集中有6個資料集的性能有所改善，在AP方面，同樣8個資料集中有6個資料集的性能有所改善。在其他情況下，比如NS資料集，LGP在AUC方面的表現僅略好于标準偏差。結果表明，GCLGP能夠使用本地社群資訊，這确實對我們正在評估的大部分資料集有益。在AUC方面，8個資料集中的6個資料集GCLGP都要優于VGAE，且通常有一個大的差額(在Router資料集上超過15.0)。在AP方面，GCLGP與VGAE大緻相當，在8個資料集中的4個上優于它。結果突出了這種高度靈活的機率模組化方法的優點。
6
結論
作者描述了一個包含節點特征和局部鄰域資訊的鍊路預測的高斯過程模型。作者介紹了在基于在不同大小的節點鄰居之間可進行插值的核的節點之上的一個圖卷積高斯過程。作者展示了該模型如何應用于鍊路預測的任務，并介紹了一種針對成對節點的高斯過程的變分誘導點方法，該方法将誘導點放置在随機生成的連接配接誘導圖的節點上。最後，作者實驗證明其所提出的模型在一系列圖資料集上表現出了強大的性能，在許多情況下優于非卷積高斯過程和基于圖神經網絡的變分自編碼器。