[Study]Chapter 17. Scaling Up GNNs
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
I. Scaling Up GNN to Large Graphs
현대에 그래프 적용은 추천 시스템, ML Task 유저 아이템 분류, 아이템 추천 등으로 많이 사용되는데 빅데이터 시대의 ML 모델은 large-data를 어떻게 학습시키는지 이야기합니다.
Figure 1 : 미니 배치들의 평균 손실을 최소화
Figure 1에서 θ를 최적화하기 위해 무작위 샘플 M « N 인 data(mini-batches)에서 SGD를 수행합니다.
만약 표준적인 SGD를 GNN에 사용한다면 어떻게 될까요?
미니 배치에서 샘플 M개의 노드는 독립적입니다. 따라서, 이웃한 노드 특성을 종합해 노드 임베딩을 생성하는 GNN은 미니배치에서 이웃한 노드들에 접근할 수 없게 됩니다. 즉, 위의 언급한 SGD를 통해 GNN을 효과적으로 학습할 수 없습니다.
그래서 미니배치 방법이 아닌 단순하게 풀배치 방법으로 모든 노드의 임베딩을 통시에 생성합니다. 각 GNN 레이어에서 전체 그래프의 특성을 불러와 모든 노드의 임베딩을 이전 레이어에서 온 모든 노드 임베딩으로 계산합니다.
Figure 2 : Full-batch implementation
하지만 위와 같은 풀배치 방법은 거대한 그래프에서는 불가능합니다. 빠른 학습을 위해 GPU 사용해야 하는데, GPU 메모리는 제한되어 있어 전체 그래프와 특성을 GPU에 업로드하지 못하기 때문입니다.
따라서, 메시지 패싱을 각 미니배치에서 GPU에 올릴 수 있는 크기의 작은 부분그래프를 통해 수행하는 Neighbor sampling1, cluster-GCN2과 특성 전처리 작업으로 간단화하는 simplified GCN 3을 소개합니다.
II. GraphSAGE Neighbor Sampling
단일 노드의 임베딩을 위한 계산 그래프는 K-hop 이웃들이 필요합니다. 만약 M개의 다른 노드 집합들이 미니배치로 주어졌을때, M개의 계산 그래프를 사용하여 임베딩을 생성해 GPU에서도 계산할 수 있게 됩니다.
그리고 아래와 같이 SGD전략을 K-layer의 GNN을 학습하는데 사용합니다.
- 샘플 M(«N)인 노드를 무작위로 선택해 각 샘플 노드 v에서 K-hop 이웃들을 구하여 계산 그래프를 구축하고, v의 임베딩을 생성한다.
- M노드의 평균 loss \(ℓ_{sub}(\theta)\)를 계산
SGD 업데이트를 수행한다.
\[\theta \leftarrow \theta - \Deltaℓ_{sub}(\theta)\]
이러한 학습은 각 노드에서 k-hop 이웃들의 전체를 계산 그래프로 만들어야해서 하나의 노드 임베딩을 계산하기위해 많은 정보를 사용해 계산 비용이 높습니다. 이러한 계산 그래프는 K의 크기에 지수적으로 비례해 폭발(특히, hub-node라 불리는 차수가 높은 노드를 만나면)하게 됩니다.
1. Neighbor Sampling
이러한 계산 그래프가 커지는 문제를 막기 위해 각 hop에서 H개의 이웃을 샘플링(무작위하게)해서 계산 그래프를 구축합니다.
Figure 3 : 이웃 샘플링 전략
이처럼 이웃 샘플링을 통해 가지 치기한\(_{pruned}\) 계산 그래프를 사용하여 더 효과적으로 노드 임베딩을 계산합니다.
pseudo-code
for k: for node in k-hop neighborhood: (randomly) sample at most H_k neighbors
각, K-layer GNN은 \(\Pi_{k=1}^{K}H_k\) leaf nodes를 계산 그래프에서 얻게된다.
H(sampling number)는 trade-off 관계로 H가 작아질수록 효과적인 이웃의 종합이 가능하지만 학습에서의 결과는 이웃의 높은 분산 때문에 불안정해 질 것입니다. 이와 반대로 H가 커질수록 계산 비용이 더 높아질 것입니다.
또한, 노드들을 샘플링하는 방식으로 기본적인 무작위 샘플링은 중요하지 않은 노드들이 뽑히면서 최적화가 되지 않을것 입니다. 조금 더 나은 방법으로는 실제 그래프는 “scale free”해 무작위로 이웃을 샘플링하면 샘플은 낮은 degree의 잎 노드이기에 중요한 노드를 샘플링하는 전략으로 재시작과 무작위 보행을 사용하는 방법이 실제그래프에서 더 효과적일 것입니다.
III. Cluster-GCN
이웃을 샘플링할때 노드가 미니배치에서 이웃들을 공유하는 경우 추가 계산이 불필요\(_{redundant}\)한 점을 이용해 #GNN layer에 지수적인 문제를 해결합니다.
Figure 4 : 각 노드의 임베딩을 계산하는 과정에서 이웃들의 계산 그래프가 동일한 경우
풀-배치로 GNN을 실행할때, 모든 노드 임베딩은 이전 층의 임베딩을 사용하여 업데이트됩니다.
Figure 5 : 풀-배치 GNN에서 노드 임베딩 함수
각 레이어에서 2*#(edges) 메시지를 계산해야하고, K-layer GNN에서 2K*#(edges) 메시지를 계산해야 합니다. 따라서, GNN의 전체 계산은 edge의 수와 GNN layer 수의 선형적으로 빠르게 됩니다.
1. layer-wise embedding
layer-wise 노드 임베딩은 이전 층에서의 임베딩을 재활용하여 업데이트하는 방법으로 이웃 샘플링의 불필요한 계산을 상당히 줄여주는 효과가 있습니다. 그러나 layer-wise 업데이트는 큰 그래프에서 GPU 메모리의 문제로.실현불가능합니다.
따라서, 큰 그래프에서 작은 부분 그래프를 샘플링하고 효과적은 layer-wise 노드 임베딩 업데이트를 부분 그래프에서 수행합니다.
Figure 6 : Sampled subgraph Layer-wise node embedding update on GPU
부분 그래프 샘플링.
GNN은 edge를 통한 메시지를 전달해 노드 임베딩을 수행하기에 큰 그래프를 작은 부분 그래프로 샘플링하는 좋은 방법은 원래의 그래프에서 edge 연결성을 가능한 많이 얻어야합니다. 즉, 부분 그래프에서의 GNN이 원래의 그래프에서의 GNN과 유사하게 임베딩 되도록 하는 것입니다.
Figure 7 : 어떤 부분 그래프가 좋은 부분 그래프인가? (좌) 4개 노드 사이의 필수적인 커뮤니티 구조를 얻음 (우) 많은 연결 패턴을 버리므로 노드들이 독립적으로 만듦
실세계 그래프에서 커뮤니티 구조를 보이기 떄문에 큰 그래프는 수 많은 작은 커뮤니티들로 분해될 수 있어 샘플링하는 것은 각 부분그래프에서 원래의 그래프의 필수적인 지역 연결 패턴을 얻을\(_{exploiting}\) 수 있습니다.
2. Overview
기본적인 Cluster-GCN은 아래와 같이 두 단계로 구성됩니다.
Pre-processing
큰 그래프가 주어졌을때 부분 그래프로 분할합니다. 이 분할 과정에서는 여러 커뮤니티 탐지 방법들을 사용할 수 있습니다. 해당 부분 그래프간의 edge들은 포함되지 않습니다.
\[G=(V,E), V = {V_1, ..., V_c}, E_c = {(u,v)|u,v\in V_c}\]Figure 8 : Graph communities partitioning
미니 배치 학습
각 미니배치에서 무작위하게 선택된 노드 그룹($V_c$)을 부분그래프($G_c$)에 구축하여 GNN 메시지 패싱을 수행합니다.
Figure 9 : \(G_c\)에서 각 노드 \(v \in V_c\)의 임베딩 \(h_v\)를 얻기위해 layer-wide 노드 업데이트를 적용합니다
이러한 방법은 아래와 같은 문제들이 존재합니다.
- 부분그래프는 그룹간의 연결을 제거해 그룹 간 메시지를 잃게되어 성능에 영향을 미칠 수 있습니다.
- 그래프 커뮤니티 탐지 알고리즘은 유사한 노드를 같은 그룹에 놓게 되어 대표성이 떨어질 수 있습니다.
- 샘플 노드들은 전체 구조를 표현하기에 다양성(그룹간 많은 변동\(_{Fluctuates}\))이 충분하지 않아 평균 기울기(기울기가 높은 분산을 가짐)를 신뢰할 수 없어 SGD의 낮은 수렴성으로 귀결됩니다.
3. Advanced Cluster-GCN
위의 나열한 문제들을 해결하기 위해 미니 배치당 다양한 노드 그룹을 종합합니다.
그래프를 연결된 부분 그래프로 분할하고, 각 미니배치에서 다양한 부분 그래프로 샘플링하여 종합합니다.
다양한 multiple 부분 그래프를 샘프링하는 것은 전체 노드를 설명할 수 있고, 기울기 추정시에도 작은분산으로 이끌어 신뢰할 수 있게합니다. 또한, 그룹 간의 edge를 포함하고 있어 그룹간 메시지 정보가 포함되도록 합니다.
바닐라 cluster-GCN과 유사하고 똑같이 2 단계를 거친다.
pre-processing step
\(V = \{V_1, ..., V_C\}\)이 여러 그룹이 집계되더라도 그룹의 결과가 크지 않도록 작게 해야합니다.
미니 배치 학습
각 미니배치에서 노드 그룹의 집합에서 무작위하게 샘플링한다.
\[\{V_{t_1}, ..., V_{t_q}\} \subset \{V_1, ..., V_C\}\]노드 그룹의 표본들의 집계는 유도된 부분 그래프를 추출하고,
\[V_{aggr} = V_{t_1} \cup \cdots \cup v_{t_q} G_{aggr}=(V_{aggr}, E_{aggr})\]아래와 같이 그룹간의 edge를 포함하고 있다.
\[E_{aggr}={(u,v)|u,v\in V_{aggr}}E_{aggr}\]
Neighbor-sampling에서 각 노드의 K-layer 크기의 계산 그래프는 $H^K$ 이고, 각 M 노드에서 비용은 $M \cdot H^K$이 된다.
cluster_GCN에서는 $M \cdot D_{avg}$ edge를 포함하고 $D_{avg}$는 노드의 평균 차수이다. 즉, K-layer 메시지 패싱의 비용은 $K\cdot M \cdot D_{avg}$이다.
$H=D_{avg}/2$로 가정하면(다른말로 50%의 이웃을 샘플링하면) CLuster-GCN은 2MHK의 비용이고, K에 관해서 지수적인 의존성 대신하여 선형적으로 변화해 neighbor sampling $MH^K$보다 더 효과적이다.
\[H^{(k+1)}=\tilde{A}H^{(k)}W_k^T\]IV. Simplifying GNNs
GCN에서 비선형 activation을 제거함으로써 GCN을 단순화할것이다. 이러한 방법의 단순화를 통해 벤치마크 성능이 낮아지지 않는 것을 설명해 단순화한 GCN은 거대한 그래프에 대해서도 효과적으로 적용 가능하게 모델 디자인이 되어 나옵니다.
Figure 10 : 선형변환의 구성은 여전히 선형적이다.
위의 \(\tilde{A}^{k}X\)는 학습가능한 파라미터를 포함하고 있지 않아 희소행렬 벡터 내적의 시퀀스의 K번 반복으로 \(X \leftarrow \tilde{A}X \tilde{X}=\tilde{A}^{k}X\)처럼 행렬의 계산이 미리 가능합니다.
따라서, 마지막 임베딩은 \(H^{(K)}=\tilde{X}W^T\)가 되고 미리 계산된 행렬의 선형 조합이 된다.
노드 임베딩으로 돌아와서
\[h_v^{(K)}=W\tilde{X}_v\]위 수식에서 \(\tilde{X}_v\)는 노드 v의 미리 계산된 특성 벡터가 되어. 노드 v의 임베딩은 해당하는 자신의 특징에만 의존하게 됩니다.
간단화된 GCN의 두가지 단계로 요약하면 아래와 같은 절차가 됩니다/
Pre-processing step
\[\tilde{X}=\tilde{A}^KX\]CPU에서 미리 계산합니다.
Mini-batch training step
각 미니 배치에서 M 노드들의 무작위하게 샘플링({v1, …, v_M})합니다.
\[h_{v_1}^{(K)}=W\tilde{X}_{v_1}\]위와 같이 각 임베딩을 계산하고 해당 임베딩을 예측하거나 평균 loss를 계산해 SGD를 통한 업데이트를 수행합니다.
1. Comparison
neigbor sampling과 비교해서 간단화한 GCN은 각 노드의 계산 그래프를 구축할 필요가 없어 더 효과적으로 임베딩을 생성합니다.
또한, CLuster-GCN과 비교하여 간단화한 GCN의 미니 배치 노드들은 전체 노드에서 완벽하게 무작위적으로 샘플링(다양한 그룹에서 샘플할 필요가 없음)될 수 있다.
따라서 학습하는 동안 SGD 분산이 작게 유지됩니다. 하지만 해당 모델은 다른 모델들과 비교해서 노드 임베딩을 생성하는데 비선형성이 결여되어 표현력이 제한적입니다. 그럼에도 불구하고 노드 분류 준지도학습의 벤치마크에서는 간단화한 GCN이 original GNN과 동등하게 나타냈다.
2. Graph Homophily
위와 같이 비선형성이 결여되어도 동일한 성능을 나타내는지에 대한 답으로 그래프 동질성\(_{Homophily}\)이 해답이 됩니다.
많은 노드 분류 작업에서 동종 선호의 구조가 나타나는데, 노드들이 연결되어 있으면 같은 label을 공유하는 경향으로 예를들면 두 사람이 친구라면 같은 영화를 좋아하는 경향을 말합니다. 전처리된 특징은 반복적으로 이웃 노드들의 특징을 평균화함으로써 얻어집니다. 결과적으로 edge로 연결된 노드들은 이와 유사한 전처리된 특징을 가지는 경향이 존재합니다.
모델이 이러한 특징을 예측하는데 사용한다고 하면 edge로 연결된 노드들은 유사한 특징을 가지게 되어 모델에서도 같은 label을 예측하게 됩니다. 따라서, 단순화된 GCN의 예측이 많은 노드 분류 벤치마크 데이터셋에서 동종 선호 경향이 나타나 동등하게 나타나는 것입니다.
즉, 그래프에서 동종 선호는 비슷한 특성을 가진 노드들이 서로 연결되는 경향을 의미하여 정보 전파에 유리할 수 있어 유사한 특성을 공유하는 노드들간의 관계를 강조할 수 있으나 정보의 다양성이 부족하게 되어 정보가 다른 속성을 가진 노드들로 전파되기 어려워지거나 노이즈에 민감할 수 있습니다.