Predict then propagate : Graph Neural Network meet Personalized PageRank

1. Introduction

최근 Link prediction, Graph classification, Node classification 과 같은 중요한 그래프 문제에 대해서 딥러닝으로 접근하여 큰 발전을 이루고 있다.

 

Node embedding 방법의 경우, random walk나 matrix factorization을 통해서 바로 개별 노드의 embedding을 학습한다. 이 방법은 Node 자체의 feature를 사용하지 않고(단점이 될 수 있다) 주로 비지도학습적인 방법(가까운 노드의 similarity가 높아지도록 or adjacency matrix와 비슷한 A행렬을 만들도록)을 사용한다.

그래프 구조와 Node feature를 이용하는 방법도 존재한다. 

• Spectral graph convolution - 새로운 domain 도입(spectral domain)하여 컨벌루션을 진행
• Message passing(Neighbor aggregation) - 이웃한 노드의 feature를 모아서 정보를 전달하는 방식

Message passing 방법이 flexibility와 성능면에서 좋은 결과를 보였다.

더 나아가 Messange passing(neighborhood aggregation) 방법을 Attention mechanism, random walk, edge feature와 결합해 큰 그래프에서도 scalable 하도록 함.

그러나 이러한 방법도 각 노드의 제한된 이웃에 대한 정보만 이용하는 한계가 있다.

 

GCN의 layer가 증가함에 따라서 random walk의 stationary 분포로 수렴하는 경향이 있다.(이후 2번에서 설명) 이 분포는 그래프 전체의 특성이기 때문에 root node의 이웃을 나타내기에는 부적합 → GCN의 성능은 layer가 많아질수록 악화된다.

이러한 Over smoothing 문제를 해결하기 위해서 Personalized pagerank 도입!

Personalized pagerank는 root node로 돌아가는 확률을 추가해서 모든 root node에서 local neighborhood를 encode할 수 있도록 함. 이 새로운 확률은 root node에 가까이 있는 것과 관련한 locality를 보존하는 것과, 멀리 있는 이웃으로부터의 영향력을 조절함.

 

Message passing에서 propagation과 classification은 연관되어 있는데 PPR이 신경망(신경망 자체를 바꾸지 않고)과 propagation scheme을 분리한다. → Propagation scheme과 SOTA prediction method를 결합해서 네트워크의 정확도를 높일 수 있다!

 

2. Graph Convolutional Network and their limited range

 

2 Message passing layers

A hat - Normalized adjacency matrix with self-loop

2 layers의 경우 A행렬이 2번 사용되기 때문에 2 hop neighbors 만 고려한다.

 

GCN과 같은 message passing 알고리즘이 넓은 범위의 이웃에 대해 확장할 수 없는 이유

1. 너무 많은 layer들이 사용될 경우 평균(GCN aggregation 방법)을 하는 방법이 oversmoothing 야기한다.
2. 각 layer에서 learnable한 가중치 행렬을 사용하기 때문에 넓은 범위의 이웃을 사용하는 것은 신경망의 깊이를 늘릴 수 밖에 없다.

GCN influence score

GCN influence score의 의미? : k-layer GCN의 경우 root node x에서 출발해서 y로 향하는 k-step random walk distribution의 기댓값

k→∞ 가 되면 이 random walk distribution은 stationary distribution에 수렴한다. 이 분포는 x_lim = A*x_lim의 방정식으로 구할 수 있으며 이는 그래프 전체를 나타낸 것이기 때문에 node x에서 출발하는 random walk와 무관하다.

 

3. Personalized propagation of neural predictions

PageRank와 Personalized PageRank의 차이 - Self-loop의 유무와 인접 행렬의 normalization

i_x : Teleport vector - 원 핫 벡터, Root node 마다 벡터가 다름 

인접행렬은 기존 A행렬에 self loop(I matrix)를 더한 행렬

좌변의 의미? - x라는 root node에서의 influence score

 

PPNP(Personalized propagation of neural predictions)

 X - feature matrix 

f_theta - Prediction H를 만드는 neural network

 

Node feature를 가지고 neural network를 통해 prediction을 생성 → 이를 fully PPR matrix와 행렬 곱

∴ Propagation scheme으로부터 prediction을 만드는 neural network를 분리하였다.

GCN의 2번째 문제가 해결되는데 그 이유는 propagation과 neural network의 깊이는 독립적이기 때문

∴ PPR을 사용하면 기존에 message passing framework에서 사용할 수 없었던 매우 깊은 층의 neural network를 사용할 수 있다.

 

APPNP(Approximate personalized propagation of neural predictions)

2번 식처럼 PPR 행렬을 연산하는 것은 비효율적이기 때문에 power iteration을 통해서 PPR 행렬을 근사할 수 있음.

PageRank에서의 power iteration - Regular random walk

Personalized PageRank에서의 power iteration - Random walk with restart

 

H 행렬은 starting vector(4번식 첫번째 행)와 teleport set(2~3행)의 역할을 함.

별도의 propagation layer에서 추가적인 parameter가 필요한 일반적인 GCN과 달리 매우 적은 파라미터로도 학습을 효율적으로 진행할 수 있음.

 

Result

Message passing 알고리즘은 data split과 weight initialization에 크게 의존하기 때문에 evaluation protocol을 디자인하는 것이 매우 중요하다.

논문에서 설계한 평가 방법

1. 실험을 100번 실행 → Random split과 weight initialization진행
2. Test set 따로 분리 → Hyperparameter나 model에 대한 결정은 test set에서 하지 않음

이 외에도 과적합 막기 위한 Dropout, L2 regularization등이 사용

 

사용한 데이터 셋 : 4 Text-classification(CITESEER, CORA-ML, PUBMED, MICROSOFT ACADEMIC)

4개 데이터 셋에서 모두 좋은 성능을 보임. Figure 2에서 accuracy의 너비를 보면 다른 모델들보다 robust

Parameter가 적기 때문에 1 epoch training 시간도 효율적

일반적인 GCN의 경우 K가 커질수록 oversmoothing 문제가 발생, APPNP의 경우 오히려 정확도가 향상되는 양상을 보임.

Teleport prob alpha의 값에 대한 정확도, alpha가 높을수록 convergence speed는 빠름

Propagation 유무에 따른 성능 비교, Inference에서만 propagation을 해도 꽤 좋은 성능이 나왔다. Train을 할 때 propagation을 생략하면 시간이 상당히 단축되기 때문에 큰 그래프에서 용이하며 위 결과는 pretrain된 neural network와 결합할 수 있음을 의미함.