Predict then Propagate: Graph Neural Networks meet Personalized PageRank

# 論文情報
- Title: Predict then Propagate: Graph Neural Networks meet Personalized PageRank [PDF](https://arxiv.org/abs/1810.05997), [Source](https://github.com/benedekrozemberczki/APPNP)
- Author: Johannes Klicpera, Aleksandar Bojchevski, Stephan Günnemann

# どんなもの？
## 問題点
- 従来のGraph Convolutional Networks(GCN)には
    - ノード情報がtwo-hope先のノードにしか届かない
    - もっと遠くまで伝搬させようとすると学習パラーメータが増える
    - 伝搬先を遠くすることにより、oversmoothing問題が発生
![image.png (210.9 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/2a6c0179-c980-415e-8de5-2e5e74a13d30.png)

## 提案
- Neural Network + personalized page rank のコラボで上の問題を解決
    -  推論の過程を NNによるクラス予測とクラス情報の伝搬二つのステップに分離して考える!
![スクリーンショット 2019-07-12 14.19.12.png (33.0 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/6af4cf5c-e63e-4cae-9d68-009e95f18706.png)

![スクリーンショット 2019-07-12 14.22.00.png (146.5 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/81b3e2df-e6ac-439e-954d-10d924403500.png)
![スクリーンショット 2019-07-12 14.22.09.png (168.7 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/257a32be-44f4-4ff9-9fc4-da351cefdfcc.png)

# 先行研究と比べてどこがすごい？
- GCNとPageRankを結合することで性能向上が図れた
    - limited range problem (情報伝搬が短い隣ノードにしか届かない問題)を解決
    - 情報伝搬rangeを増やすことで学習パラーメータが増える問題を解決

# どうやって有効だと検証した？
## 実験
### データセット
![スクリーンショット 2019-07-12 11.34.35.png (64.9 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/f05176a8-44be-4fd6-8b1b-ef90dfc5d9fb.png)
- these graphs indeed have average shortest path lengths between 5 and 10.
- データ分割と初期化を含め実験を100回行う
- 全てのデータセットで同じhyperparameterを使う
    - same number of layers and hidden units, dropout rate d, L2 regularization parameter $\lambda$, learning rate l
- ノード特徴量: bag-of-words representation of abstracts

### 結果
#### Overall accuracy
![スクリーンショット 2019-07-12 11.49.03.png (123.6 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/122d068e-3538-457d-af98-c002e8dca45d.png)
- 提案手法がSOTAを達成している
- **厳密に実験を行った結果、最近提案された手法より、実はoriginal GCNがより良い結果を出していた**
#### Training time per epoch
![スクリーンショット 2019-07-12 11.52.53.png (75.7 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/e579861f-55a3-4c2e-be3d-2d875e84683b.png)
- APPNPがGCNより25%遅い。情報伝搬ステップのせいだと思われる。
    - higher number of matrix multiplications

#### Training set size
![スクリーンショット 2019-07-12 11.52.58.png (43.4 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/8d386aa4-929e-496a-b772-dbf739efbcf2.png)
- 情報伝搬が遠くまで達するだけで、少ないlabelデータでも高精度の訓練が可能になる

#### Number of power iteration steps
![スクリーンショット 2019-07-12 12.41.10.png (90.7 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/1b65c34f-2548-4ce6-9ed1-b919dca1fac1.png)
- APPNPはstepsの増加に連れて収束していく
- step数は大体平均頂点間距離と一致していることが分かる

#### Teleport probability ($\alpha$)
![スクリーンショット 2019-07-12 12.41.23.png (83.7 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/4ea4c41a-e10b-42e7-9c8e-4ae44b3146c0.png)
- データによって違う遷移確率を持つ
- a higher $\alpha$ improves convergence speed

#### Neural network without propagation
![スクリーンショット 2019-07-12 12.41.30.png (73.7 kB)](https://img.esa.io/uploads/production/attachments/9992/2019/07/12/41906/59932b7e-ad5b-4214-b404-68964bf20d26.png)
- 推論段階だけに情報伝搬を適応しても性能向上が見える
- large scaleデータを扱う時は、train段階で情報伝搬をしないことが考えられる
- pretrained neural networksにgraph informationを取り入れた情報伝搬を加えることで精度向上が図れることが分かる

# 議論はある？
- GCNとPageRankを結合することで性能向上が図れた
    - limited range problem (情報伝搬が短い隣ノードにしか届かない問題)を解決
    - 情報伝搬rangeを増やすことで学習パラーメータが増える問題を解決
- **PPNP, APPNPは予測モデルと伝搬スキーマを完全に分離して考える仕組みの有効性を証明した**
    - **それぞれのステップでもっと有効な手法を組み合わせることが考えられる**

# 次に読むべき論文は？
- message passing algorithmsのサーベイ
    - graph node embeddings
    - spectral graph convolutional neural networks
    - neighbor aggregations
    - neighbor aggregation via recurrent neural networks