How Powerful are Graph Neural Networks?
그래프 신경망은 얼마나 강력한가?
Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka (2019)
그래프 신경망(GNN)의 표현력을 이론적으로 분석하여, 대부분의 GNN이 1차 Weisfeiler-Leman(WL) 그래프 동형 테스트만큼 강력하지 않음을 밝히고, WL 테스트와 동등한 표현력을 가진 GIN(Graph Isomorphism Network)을 설계했다.
배경
GCN, GraphSAGE, GAT 등 다양한 GNN 아키텍처가 제안되었지만, 이들의 표현력(어떤 그래프 구조를 구분할 수 있는지)에 대한 이론적 이해가 부족했다. 실험적으로는 많은 태스크에서 좋은 성능을 보였지만, 어떤 GNN이 왜 더 나은지, 어떤 구조적 정보를 포착할 수 있는지에 대한 원칙적 분석이 없었다. 그래프 이론에서 WL 테스트는 그래프 동형성을 효율적으로 판별하는 고전적 알고리즘으로, GNN과의 관계가 주목되었다.
핵심 아이디어
이 논문의 핵심 기여는 GNN의 표현력을 WL 테스트와의 관계를 통해 엄밀하게 분석한 것이다. 주요 이론적 결과는 다음과 같다: (1) 임의의 MPNN 기반 GNN은 1-WL 테스트보다 강력할 수 없다(상한). (2) 이웃 집합의 집계 함수가 단사(injective)이면 GNN은 1-WL 테스트와 동등한 구별력을 가진다. (3) GCN의 mean 집계와 GraphSAGE의 max 집계는 단사가 아니므로 특정 멀티셋을 구분하지 못하여 표현력이 제한된다. 이 분석을 바탕으로 MLP + sum 집계로 구성된 GIN을 설계하여, 이론적으로 가장 강력한 MPNN임을 증명한다.
방법론
GIN의 업데이트 규칙은 h_v^{(k)} = MLP^{(k)}((1 + epsilon^{(k)}) * h_v^{(k-1)} + sum_{u in N(v)} h_u^{(k-1)})이다. 여기서 epsilon은 학습 가능한 파라미터이고, sum 집계는 멀티셋에 대한 단사 함수를 구현한다. MLP는 범용 근사 정리(universal approximation theorem)에 의해 임의의 연속 함수를 근사할 수 있으므로, 전체 업데이트가 단사 함수가 된다. 그래프 수준 표현은 모든 레이어의 노드 표현을 합산(sum)한 뒤 연결(concatenation)하여 구성한다. mean 집계를 사용하는 GIN-mean, max 집계를 사용하는 GIN-max 변형도 비교 실험을 위해 구현했다.
주요 결과
9개의 그래프 분류 벤치마크(MUTAG, PTC, PROTEINS, COLLAB, IMDB-BINARY 등)에서 GIN은 기존 GNN(GCN, GraphSAGE, GAT) 및 WL 서브트리 커널과 비교하여 대부분의 데이터셋에서 최고 또는 동등한 성능을 달성했다. 특히 GIN-sum이 GIN-mean과 GIN-max를 일관되게 능가하여 이론적 분석을 실험적으로 뒷받침했다. 합성 데이터에서 GIN이 GCN/GraphSAGE가 구분하지 못하는 그래프 쌍을 올바르게 구분함을 확인했다.
임팩트
GIN은 GNN의 표현력에 대한 이론적 기초를 확립하여, 이후 GNN 연구의 방향에 지대한 영향을 미쳤다. WL 테스트와의 연결은 더 강력한 GNN(k-WL, k>1에 대응) 설계를 위한 연구(3WLGNN, k-IGN 등)를 촉발했으며, 집계 함수의 설계 원칙(sum이 mean/max보다 표현력이 높음)은 이후 GNN 아키텍처 설계의 기본 지침이 되었다. OGB 벤치마크에서 GIN은 기본 기준선(baseline)으로 널리 사용되고 있으며, GNN 이론 연구의 출발점으로서 수천 회 인용되었다.