[CS224w] Label Propagation on Graphs (3) - Correct & Smooth (C&S)

Reference

Combining Label Propagation and Simple Models Out-performs Graph Neural Networks

 

Introduction

Correct & Smooth (C&S)는 node classification method에서 SOTA 이다.

이 글을 포스팅하는 (2023.07.12) ogbn-products의 top-10 중에서 5개는 C&S 방법을 적용하였다.

OGB leaderboard

Label Propagation (LP)는 homophily(또는 associativity)를 이용하지만 정작 node feature vector를 이용하지 않는다. 즉 LP는 neighbor averaging이다.

Graph Neural Network (GNN)은 feature vector를 이용하지만 label 정보는 이용하지 않는다. 즉 GNN은 aggregating feature이다.

GNNs make uncorrelated predictions

GNN in predictions

GNN은 local neighborhood로부터 구조를 만들어 노드 $v$의 representation $\mathbf{h}_v$를 구한다.

이렇게 얻은 $\mathbf{h}$로 prediction을 수행한다.

즉, node feature가 충분히 예측력이 있다면 GNN으로도 충분하다. (그러나 현실적으로 그렇지가 않을 수 있다.)

New labels, but same predictions

그러나 같은 구조임에도 label이 다른 경우가 생길 수 있다. 위 그림은 원래 그림에서 label의 분포만 바뀐 경우이다. 그러나 local neighborhood 구조가 동일하기 때문에 prediction 결과가 동일해지는 문제가 발생한다.

이 경우에는 LP가 더 predictive할 것이다.

반응형

Correct & Smooth (C&S)

C&S Settings

settings: 일부 노드만 label이 있고, 모든 노드들은 feature vector를 갖는 그래프가 주어진다.

C&S는 크게 3단계 알고리즘으로 이루어진다.

1. Train base predictor
2. predict soft labels of all nodes
3. post-process the predictions using graph structure

Step 1. Train Base Predictor

labeled node는 train/validation에 사용된다.

base predictor는 단순한 모델을 사용하며 보통 linear, MLP, full GNN 등이 사용된다.

Train Base Predictor that predict soft labels

Step 2. Predict Over All Nodes

Step 1에서 학습한 base predictor를 이용하여 나머지 모든 노드의 label을 예측한다. 이렇게 얻은 label은 soft label이라 부르고, 얼추 비슷한 것이라 기대한다.

Obtain soft labels for all the nodes

이제 step 3에서 post-process를 통해 soft label을 더 정확하게 만들 것이다.

Step 3. Post-Process Predictions

후처리는 correct step과 smooth step으로 이루어진다.

correct step에서는 error bias를 조정(correct)한다.

smooth step에서는 soft label을 smooth하게 만든다. (이웃하는 노드끼리 비슷한 label을 가지게, homophily)

Correct & Smooth Steps

Correct Step

각 노드의 training error를 계산한다. 

training error = (ground-truth label) - (soft label)

unlabeled node의 경우 training error = 0으로 정의한다.

Computing Training Error

training error matrix $E$ 를 이용하여 edge로 확산(diffuse)시킨다.

Initial training error matrix

인접행렬 $A$의 diffusion matrix를 $\tilde{A}$라 할 때 다음과 같이 training error를 업데이트한다.

Assumption: Prediction errors are similar for nearby nodes

\[ \mathbf{E}^{(t+1)} \leftarrow (1 - \alpha) \mathbf{E}^{(t)} + \alpha \tilde{\mathbf{A}} \mathbf{E}^{(t)} \]

$\alpha$는 hyperparameter이다.

※ Diffusion Matrix $\tilde{A}$

Normalized diffusion matrix

\[ \tilde{A} \equiv D^{-1/2} A D^{-1/2} \]

$A$에 self-loop을 추가하고(i.e. A_{ii}=1) $D \equiv diag(d_1, \dots, d_N)$ 이다.

 

두 노드 $i$와 $j$가 연결되어있다면, $\tilde{A}_{ij} = \cfrac{1}{\sqrt{d_i} \sqrt{d_j}}$ 이다.

Intuitions for $\tilde{A}$

 

Diffusion of training errors

Correct step의 마지막 단계로, soft label과 diffused training error를 합친다. (이때 scale hyperparameter 상수 $s$배를 적용한다)

Corrected Soft Labels

Smooth Step

Correct step에서 얻은 corrected soft label을 부드럽게(smoothen) 하는 단계이다.

Assumption: Neighboring nodes tend to share the same labels

Input to the smooth step

Diffuse label $\mathbf{Z}$를 학습한다.

Corrected label matrix

\[ Z^{(t+1)} \leftarrow (1 - \alpha) A^{(t)} + \alpha \tilde{A} Z^{(t)} \]

Before and After Smoothing

최종적으로 C&S로 얻은 class prediction(예시에서 $\mathbf{Z}^{(3)}$)은 확률이 아니므로 확률로 해석해서는 안된다. 물론 큰 숫자는 더 큰 가능성(likely)을 나타내긴 한다.

 

C&S Summary

C&S는 그래프 구조에서 후처리(post-process)를 통해 soft node label을 예측한다.

Correction step: base predictor로 예측한 training error를 확산 및 조정(diffuse and correct)한다.

Smooth step: prediction을 smoothen한다. (일종의 label propagation의 변형)

C&S는 GNN과 결합할 수 있다. 특히 semi-supervised node classification에서 좋은 성능을 보여준다.