Cluster-GCN: 깊고 큰 그래프 컨볼루션 네트워크를 효율적으로 학습하는 알고리즘

그래프 컨볼루션 네트워크(GCN)는 많은 그래프 기반 응용 분야에 성공적으로 적용되었지만, 대규모 GCN의 학습은 여전히 어려움을 겪고 있습니다. 현재 SGD(확률적 경사 하강법) 기반 알고리즘들은 GCN 레이어 수가 증가함에 따라 지수적으로 증가하는 높은 계산 비용이나, 전체 그래프와 각 노드의 임베딩을 메모리에 저장하기 위한 큰 공간 요구 중 하나를 겪고 있습니다. 본 논문에서는 그래프 클러스터링 구조를 활용하여 SGD 기반 학습에 적합한 새로운 GCN 알고리즘인 Cluster-GCN을 제안합니다.Cluster-GCN의 작동 방식은 다음과 같습니다: 각 단계에서, 그래프 클러스터링 알고리즘으로 식별된 밀집된 부분 그래프와 관련된 노드 블록을 샘플링하고, 이 부분 그래프 내에서만 이웃 검색을 제한합니다. 이 간단하지만 효과적인 전략은 이전 알고리즘과 유사한 테스트 정확도를 유지하면서도 메모리와 계산 효율성을 크게 향상시킵니다. 우리의 알고리즘의 확장성을 테스트하기 위해, 200만 개의 노드와 6100만 개의 엣지를 가진 새로운 Amazon2M 데이터셋을 생성했습니다. 이 데이터셋은 이전 최대 규모의 공개 데이터셋(Reddit)보다 5배 이상 큽니다.이 데이터에서 3층 GCN을 학습시키기 위해 Cluster-GCN은 이전 최신 VR-GCN(1523초 vs 1961초)보다 더 빠르며, 훨씬 적은 메모리를 사용합니다(2.2GB vs 11.2GB). 또한, 이 데이터에서 4층 GCN을 학습시키기 위해서는 모든 기존 GCN 학습 알고리즘이 메모리 부족 문제로 인해 실패하지만, 우리의 알고리즘은 약 36분 만에 완료할 수 있습니다. 더욱이, Cluster-GCN은 시간과 메모리 오버헤드를 크게 늘리지 않고도 매우 깊은 GCN을 학습할 수 있게 해주어 예측 정확도를 향상시킵니다. 5층 Cluster-GCN을 사용하여 PPI 데이터셋에서 최신 테스트 F1 점수 99.36를 달성했으며, 이는 이전 최고 결과인 [16]의 98.71보다 우수합니다.우리는 코드를 공개적으로 제공하고 있으며, 해당 코드는 다음 주소에서 확인할 수 있습니다: https://github.com/google-research/google-research/tree/master/cluster_gcn.