論文資訊

論文標題：Predict then Propagate: Graph Neural Networks meet Personalized PageRank
論文作者：Johannes Gasteiger, Aleksandar Bojchevski, Stephan Günnemann
論文來源：2019,ICLR
論文地址：download
論文程式碼：download

1-Abstract

　　本文主要將 PageRank 演演算法引入到 GNNs ，提出了  PPNP 模型 和APPNP 模型。 

2-Introduction

　　問題：

• • 增大鄰域範圍，充分利用領域資訊；【傳播多層——訊息傳遞機制的本質，也可以看做隨機遊走】
  • 解決過平滑問題（一般均為傳播多層造成的過平滑）；

　　受 帶重啟隨機遊走（random walk）的影響，本文利用 personalized PageRank 代替隨機遊走 ，來增加傳送到根節點的機會，以避免過平滑現象（主要是更多的考慮根節點的鄰域），此外該模型允許使用更多的傳播層數。【通過 $\text{Eq.4}$ 便於理解】

3 Graph convolutional networks and their limited range

　　半監督節點分類 GCN：

　　　　$\boldsymbol{Z}_{\mathrm{GCN}}=\operatorname{softmax}\left(\hat{\tilde{\tilde{A}}} \operatorname{ReLU}\left(\hat{\tilde{\tilde{A}}} \boldsymbol{X} \boldsymbol{W}_{0}\right) \boldsymbol{W}_{1}\right)  \quad\quad\quad(1)$

　　其中，$\hat{\tilde{\boldsymbol{A}}}=\tilde{\boldsymbol{D}}^{-1 / 2} \tilde{\boldsymbol{A}} \tilde{\boldsymbol{D}}^{-1 / 2}$。

　　存在的問題：【APPNP 所解決的問題 】

• • 不能使用更多的傳播層，因為會造成過平滑；
  • 層數增加，引數量增加；

4 Personalized propagation of neural predictions

　　早起版本 PageRank：

　　　　$\pi_{\mathrm{pr}}=A_{\mathrm{rw}} \pi_{\mathrm{pr}}, \quad\quad\text { with }\quad\quad A_{\mathrm{rw}}=A D^{-1}$

　　以及考慮根節點資訊，提出 personalized PageRank 演演算法：【類似帶重啟的隨機遊走，緩解過平滑】

　　其中：

• • $\hat{\tilde{A}}=\tilde{\boldsymbol{D}}^{-1 / 2} \tilde{\boldsymbol{A}} \tilde{\boldsymbol{D}}^{-1 / 2}$；
  • $i_x$ 表示初始根節點的特徵；

　　計算得到平穩狀態後的分佈：

　　用單位矩陣代替指標向量 $i_x$ 得  personalized PageRank matrix：

　　　　$\mathbf{\Pi}_{\mathrm{ppr}}=\alpha\left(\boldsymbol{I}_{n}-(1-\alpha) \hat{\tilde{ A }}\right)^{-1}$

　　$\mathbf{\Pi}_{\mathrm{ppr}}$ 中的元素 $yx$ 可以理解為 節點 $x$ 對節點 $y$ 的影響分數 $I(x, y) \propto \Pi_{\mathrm{ppr}}^{(y x)}$。【其實就是 節點 $x$ 轉移到節點 $y$ 的概率值】

　　Note：上述式子可逆的時候需要滿足  $\frac{1}{1-\alpha}>1$ 且不能為 $\hat{\tilde{A}}$ 的特徵值。

　　藉由上述闡述，得到 PPNP 模型：

　　　　$\boldsymbol{Z}_{\mathrm{PPNP}}=\operatorname{softmax}\left(\alpha\left(\boldsymbol{I}_{n}-(1-\alpha) \hat{\tilde{ A }}\right)^{-1} \boldsymbol{H}\right), \quad \boldsymbol{H}_{i,:}=f_{\theta}\left(\boldsymbol{X}_{i,:}\right)\quad\quad\quad(3)$

　　Note：直接計算  $\Pi_{\mathrm{ppr}}$ ，具有高計算複雜度且需要 $\mathcal{O}\left(n^{2}\right)$ 的記憶體空間。【APPNP 改進的地方】

　　APPNP 通過冪次迭代逼近 topic-sensitive PageRank 來實現線性計算複雜度。傳播過程為：

　　　　$\begin{array}{l}\boldsymbol{Z}^{(0)} &=&\boldsymbol{H}=f_{\theta}(\boldsymbol{X}) \\\boldsymbol{Z}^{(k+1)} &=&(1-\alpha) \hat{\tilde{A}} \boldsymbol{Z}^{(k)}+\alpha \boldsymbol{H} \\\boldsymbol{Z}^{(K)} &=&\operatorname{softmax}\left((1-\alpha) \hat{\tilde{\boldsymbol{A}}} \boldsymbol{Z}^{(K-1)}+\alpha \boldsymbol{H}\right)\end{array}\quad\quad\quad(4)$

　　這個迭代方案的收斂性證明如下：

　　在 PPNP 和 APPNP 中，影響每個節點的鄰域的大小都可以通過傳送概率 $\alpha $ 進行調整。

附：圖擴散

　　$\mathcal{T}_{\mathbf{A}}(\mathbf{A})=\sum_{k=0}^{\infty} \Theta_{k} \mathbf{S}^{k}$

其中：

• $\mathbf{S} \in \mathbb{R}^{N \times N}$  是廣泛的轉移矩陣 
• $\Theta$  是加權係數，且  $\sum_{k=0}^{\infty} \Theta_{k}=1 ， \Theta_{k} \in[0,1]$

Personalized PageRank (PPR) kernal

　　其中：

• • $\mathbf{S}=\mathbf{D}^{-1 / 2} \mathbf{A D}^{-1 / 2}$
  • $\Theta_{k}=\alpha(1-\alpha)^{k}$

　　得：

• • $\mathcal{T}_{\mathbf{A}}^{P P R}(\mathbf{A})=\alpha\left(\mathbf{I}_{n}-(1-\alpha) \mathbf{D}^{-1 / 2} \mathbf{A} \mathbf{D}^{-1 / 2}\right)^{-1}$　　

5 Experimental setup

　　訊息傳遞演演算法對 資料劃分 和 權重初始化 都非常敏感。

不同模型在亂資料劃分 和 隨機權重初始化的標準差

6 Conclusion

　　在本文中，我們介紹了神經預測(PPNP)及其快速近似APPNP。我們通過考慮GCN和PageRank之間的關係並將其擴充套件到個性化PageRank來導這個模型。這個簡單的模型解耦了預測和傳播，並解決了許多訊息傳遞模型中固有的有限範圍的問題，而沒有引入任何額外的引數。它使用來自一個大的、可調節的（通過傳送概率 $\alpha$）鄰域的資訊來對每個節點進行分類。該模型在計算上高效，優於目前最先進的研究，在多個圖上的半監督分類方法。