Predict then Propagate: Graph Neural Networks meet Personalized PageRank / ICLR 2019

Graph-based semi-supervised classification을 위한 neural message passing
문제: GNN에서 neighbor size를 늘리는 것은 (너무 많은 layer) oversmoothing을 유발하므로 일반적으로 제한된 수의 neighbor만 사용

❔ oversmoothing issue란

Transclude of oversmoothing-in-gnn

PPNP

= Personalized Propagation of Neural Predictions

Prediction과 Propagation의 분리

❓ PR, PPR recap

Transclude of pagerank--and--personalized-pagerank

PPNP는 사실상 propagation 단계에서 personalized page rank를 그대로 사용함
- prediction 단계에서 생성된 초기 예측 $H$ ( $H_i, j$ 는 노드 $i$ 가 클래스 $j$ 에 속할 예측 점수)
- personalized pagerank의 closed-form solution을 사용해서 최종 예측을 계산 $Z_P P N P = softmax (α (I_n - (1 - α) \hat{A})^{- 1} H)$
  - 원래 PPR은 곱하는 게 원핫벡터(원래 시작노드만 1이고 나머지는 0)였지만, 여기서는 $H$ 의 각 열을 곱하게 되는 것과 같은데 각 열은 $j$ 번째 클래스에 대한 모든 노드의 초기 예측 점수 벡터임 -> 즉 초기 예측 결과 해당 클래스와 관련이 높다고 여겨지는 노드들의 값이 높게 반영되게 됨
  - 즉 PPNP에서 각 클래스에 대해 예측(전파)할 때, 특정 확률로 초기 예측시 해당 클래스와 관련성이 높았던 노드들로 되돌아감(텔레포트함) = Topic-Sensitive

= Approximate Personalized Propagation of Neural Predictions

closed-form solution이 역행렬 계산으로 인해 대규모 그래프에는 적용이 어려우므로 이를 일반적인 power iteration 방식으로 접근하여 효율적인 근사해를 얻어낸 것
처음에 $Z^{(0)} = H$ 에서 시작해서 $Z^{(k + 1)} = (1 - α) \hat{A} Z^{(k)} + α H$ 전파횟수 $k$ 만큼 반복 행렬곱

네 가지 벤치마크 데이터셋(Citeseer, Cora-ML, PubMed, MS Academic)에서 PPNP와 APPNP를 포함한 여러 GNN 모델들의 평균 정확도(Accuracy, Micro F1-score)
PPNP는 PubMed와 MS Academic에서 메모리 부족(out of memory)으로 실행할 수 없었음 = 대규모 그래프에서는 부적합
APPNP는 PPNP와 거의 동등한 성능을 보이면서도 모든 데이터셋에서 성공적으로 실행되었고, 특히 큰 그래프에서 우수한 성능

전파 횟수 $K$ 에 따른 영향
- GCN-like propagation은 텔레포트 확률 $α$ 를 0으로 설정한 것
  - 이 경우 $K$ 가 증가하면서 정확도가 급격히 떨어짐 (oversmoothing)
- 반면 APPNP는 $K$ 가 증가할수록 정확도가 향상되다가 일정 이상 되면 안정화 (PPNP 해를 근사하는데 그렇게 엄청 큰 $K$ 가 필요하진 않음)

텔레포트 확률 $α$
- 너무 작지도(oversmoothing 경향 증가), 너무 크지도(지역성만 강조, 그래프 정보 부족) 않은 적절한 균형점을 찾는 것이 중요함