CS224w - 17. Advanced Topics in Graph Neural Networks Part 2

Advanced Cluster-GCN

Advanced Cluster-GCN의 아이디어는 몇개의 node group을 mini-batch에서 합치는 것입니다. 이를 위해서 조금 더 작은 node group을 만들게 됩니다.

 

 

여러 노드 그룹을 쓰기 때문에 전체 그래프를 보다 잘 표현할 수 있습니다. 그리고 그룹 간의 링크가 있어, message가 그룹 사이에도 흐를 수 있습니다.

 

 

Pre-processing 단계에서는, vanilla와 같이 subgraph으로 나누되 더 작게 나눠서 나중에 aggregate 됐을 때 사이즈가 너무 커지지 않게 합니다.

 

 

Mini-batch training은 subgraph 중 random으로 일부 샘플링합니다. 그 다음 속한 node들을 전부 aggregate해서 하나의 subgraph으로 만듦니다. 이때 그룹 사이의, between-group edge를 포함시킵니다.

 

 

Time complexity를 neighbor sampling과 비교해보면, neighbor sampling은 $MH^K$입니다.

 

 

이와 비교하여 Cluster-GCN은 $KMD_{avg}$의 복잡도를 갖습니다.

 

 

이웃 노드 절반만 샘플링해서 $H=D_{avg}/2$ 라고 할 때, Cluster-GCN은 $2MHK$, neighbor sampling은 $MH^K$ 의 time complexity를 가지며, Cluster-GCN은 K에 대한 linear한 dependency를 가집니다.

 

 

요약하면 아래와 같습니다.

• Cluster-GCN은 전체 노드를 작은 노드 그룹으로 나누고 이를 mini-batch에서 합쳐 학습
• Layer-wise node embedding을 하기 때문에 layer 수가 많을 때 특히 neighbor sampling 보다 효율적
• 하지만 cross-community edge를 상실해 학습이 편향된다는 단점 존재

 

Simplifying GNN Architecture

앞선, non-linear activation을 없앤 LightGCN의 성능 저하가 크지 않은 것을 확인하였습니다. 그래서 scalability가 높은 Simplified GCN이 제안되었습니다. 먼저 LightGCN에 대해서 확인해보겠습니다.

 

 

먼저 LightGCN는 ReLU non-linearity가 없습니다. 

 

 

LightGCN에는 self-loop이 있고, Input embedding $E$가 학습되는 feature라기 보다 given feature에 가깝습니다. $\tilde{A}^KE$ 전처리 과정에 가까워서 는 한번만 계산되면 됩니다.

 

 

LightGCN은 linear model 학습시키는게 GCN과 비슷한 성능을 낸다는 것을 보여주었습니다. 다만 non-linearity가 없어 표현력이 떨어집니다. 하지만 semi-supervised node classification에서 simplified GCN은 original GNN과 거의 비슷한 성능을 보였습니다. 그 원리가 무엇일까요?

 

 

많은 node classification에서는 homophily structure가 관찰되었습니다. 따라서 연결된 노드들은 비슷한 라벨을 가질 가능성이 큽니다.

 

 

Simplified GCN은 neighbor node feature를 반복적으로 평균내는 것이기 때문에, 연결되어 있는 노드들은 비슷한 pre-processed feature를 갖게 됩니다.

 

 

그래서 연결되어 있는 노드들은 모델에 의해 같은 라벨로 예측되게 되고, Simplified GCN은 graph homophily를 잘 반영하는 모델인 것입니다. 이는 많은 node classification dataset에 적합한 방법입니다.