기술 요약: CoRe-GNN: 축약된 그래프에서의 다층 메시지 패싱 (Multilevel Message Passing on Coarsened Graphs)

문제 정의

대규모 그래프에서 그래프 신경망(GNN)을 학습시키는 것은 레이어를 거치며 노드 표현(representation)을 저장하는 데 필요한 메모리 비용에 의해 근본적으로 제약을 받습니다. 표준 메시지 패싱 아키텍처에서 레이어 $l$의 노드 표현은 $l$-홉 이웃에 의존합니다. 대규모 그래프의 경우, 이 이웃은 깊이가 깊어짐에 따라 기하급수적으로 증가하며, 이는 훈련 및 추론 과정 모두에서 GPU 메모리를 포화시키는 메모리 병목 현상을 초래합니다.

기존의 확장 가능한 접근 방식들은 일반적으로 두 가지 범주로 나뉘며, 두 방식 모두 상호 보완적인 한계를 가집니다:

1. 그래프 축약 (Graph Coarsening): Coarsen-GNN과 같은 방법은 원래의 노드들을 "슈퍼노드(supernodes)"로 매핑하여 더 작은 그래프를 생성합니다. 이는 효율적인 전파를 가능하게 하고 스펙트럼 보장을 제공하지만, 슈퍼노드 내의 모든 노드가 동일한 표현을 공유하도록 강제합니다. 이러한 "균일성(uniformity)"은 인접한 노드들이 서로 다른 레이블을 가질 수 있는 이종성(heterophilic) 환경에서 개별 노드의 판별력을 제한합니다.
2. 클러스터 기반 제한 (Cluster-Based Restriction): Cluster-GCN과 같은 방법은 메시지 패싱을 클러스터 내부 연결으로만 제한하고, 클러스터 간 연결을 제거합니다. 이는 클러스터를 독립적인 서브그래프로 취급함으로써 효율적인 배칭(batching)을 가능하게 합니다. 그러나 클러스터 간 연결을 끊는 것은 장거리 의존성(long-range dependencies)을 제거하여, 여러 홉에 걸친 정보 집계가 필요한 작업에서 성능을 저하시킵니다.

두 접근 방식 모두 노드를 그룹으로 분해하는 방식에 의외하고 있으나, 장거리 구조를 보존하는 것과 로컬 노드의 판별력을 유지하는 것 사이의 트레이드오프를 조절하는 데 실패하고 있습니다.

방법론: CoRe-GNN

저자들은 그래프 축약의 정확도 한계와 Cluster-GCN의 장거리 정보 결여 문제를 동시에 해결하기 위해 설계된 아키텍처인 **CoRe-GNN (Coarsen and Restore)**을 제안합니다.

통합 행렬 정식화 (Unified Matrix Formulation)

논문은 먼저 압축 그래프 GNN을 표준 전파 행렬 $S$의 구조적 수정으로 간주함으로써 압축 그래프 GNN에 대한 통합된 관점을 확립합니다.

• Coarsen-GNN은 $S$를 $\Pi S \Pi$로 대체합니다. 여기서 $\Pi = QP$는 노드를 슈퍼노드로 매핑하고 다시 되돌리는 블록 상수 연산자입니다.
• Cluster-GCN은 $S$를 클러스터 내부 엣지만 유지하는 블록 대각 행렬인 $S_{intra}$로 대체합니다.

CoRe-GNN 아키텍처

CoRe-GNN은 각 레이어에서 축약된 공간과 원래의 노드 공간을 결합하여 두 개의 병렬 전파를 수행합니다:

1. 클러스터 간 전파 (축약된 형태): $S_{inter}^c$ 항이 축약된 그래프(슈퍼노드) 상에서 작동합니다. 이는 장거리 구조 정보를 효율적으로 포착합니다.
2. 클러스터 내 전파 (로컬 형태): $S_{intra}$ 항이 원래의 노드 공간에서 작동하여, 클러스터 내에서의 개별 노드 판별력을 보존합니다.

레이어 $l$에 대한 업데이트 규칙은 다음과 같습니다:
$$H^{(l)} = Q \sigma(S_{inter}^c P H^{(l-1)} \theta_c^{(l)}) + \sigma(S_{intra} H^{(l-1)} \theta^{(l)})$$
여기서 $P$와 $Q$는 그래프 분할에서 유도된 축소 및 리프팅 행렬입니다. 아키텍처는 두 개의 병렬 상태, 즉 축약된 공간의 $H_c^{(l)}$와 원래 공간의 $H^{(l)}$를 유지합니다. 가중치 $\theta^{(l)}$와 $\theta_c^{(l)}$는 독립적이며, 이를 통해 네트워크는 로컬 상호작용과 장거리 상호작용에 대해 서로 다른 변환을 학습할 수 있습니다.

배칭 체계 (Batching Scheme)

수백만 개의 노드가 있는 그래프로 확장하기 위해, CoRe-GNN은 자연스러운 배칭 전략을 도입합니다:

• 클러스터 간 항 (Inter-cluster term): 매 단계마다 모든 $n$개의 슈퍼노드에 대해 계산됩니다 (여기서 $n \ll N$). 이는 계산 비용이 매우 저렴합니다.
• 클러스터 내 항 (Intra-cluster term): 현재 배치 $B$에 속한 클러스터들에 대해서만 계산됩니다. 배치되지 않은 슈퍼노드의 경우, 훈련 중에는 축약된 공간에서의 **셀프 루프 프록시(self-loop proxy)**로 근사됩니다.
  이 접근 방식은 메모리 복잡도를 전체 노드 수 $N$과 무관하게 $O(K(n+b)d)$로 줄여, 기존에는 GPU 메모리를 초과했을 그래프에서도 훈련이 가능하게 합니다.

정확한 추론 (Exact Inference): 훈련 배칭 방식은 근사치를 사용하지만, 저자들은 이 병목 현상을 피하는 비자명한 정확한 추론 절차를 도출했습니다. 이 모드에서는 인터-클러스터 항이 GPU 상의 모든 슈퍼노드에 대해 계산되는 반면, 인트라-클러스터 항은 클러스터 단위로 계산되며, CPU에서 GPU로 블록을 요청 시 로드하고 즉시 폐기합니다. 이를 통해 전체 계산 그래프를 레이어 전체에 걸쳐 유지하지 않고도 매우 큰 그래프에 대해 정확한 추론을 수행할 수 있습니다.

이론적 보장

저자들은 CoRe-GNN이 그래프 축약과 유사한 근사 보장을 상속받음을 증명합니다. 구체적으로, 제한된 스펙트럼 근사(Restricted Spectral Approximation, RSA) 상수를 사용하여 원래 그래프에서의 메시지 패싱과 CoRe-GNN 사이의 오차를 경계 지었습니다. CoRe-GNN에 대한 이론적 경계는 전체 그래프보다는 인터-클러스터 서브그래프($S_{inter}$)의 특성에 의존하며, 이는 축약 비율이 증가함에 따라 표준 축약 방식보다 오차 경계가 개선될 수 있음을 시사합니다.

주요 기여

1. 통합적 관점: 본 논문은 그래프 축약과 Cluster-GCN이 전파 행렬의 상호 보완적인 구조적 수정임을 보여주는 행렬 정식화를 제공하여 각각의 한계를 명확히 합니다.
2. CoRe-GNN 아키텍처: 클러스터 간(축약된) 전파와 클러스터 내(로컬) 전파를 병렬로 결합하여, 축약에 의한 판별력 손실과 클러스터링에 의한 장거리 정보 결여 문제를 완화하는 새로운 아키텍처를 제안합니다.
3. 확장 가능한 배칭: 수백만 개의 노드가 있는 그래프를 학습할 수 있게 하는 자연스러운 배칭 체계와, 근사를 피하는 정확한 추론 절차를 제공합니다.
4. 이론적 분석: 인터-클러스터 구조에 의존하는 스무딩 신호(smooth signals)를 보존함을 보여주는 CoRe-GNN의 전파 보장을 도출했습니다.
5. 실증적 검증: 동종성(homophilic), 이종성(heterophilic), 대규모, 장거리 벤치마크에 대한 포괄적인 평가를 수행했습니다.

실험 결과

저자들은 다음과 같은 다양한 데이터셋에 대해 CoRe-GNN을 평가했습니다:

• 동종성 (Homophilic): Cora, CiteSeer, PubMed.
• 이종성 (Heterophilic): Chameleon, Squirrel, Amazon Ratings.
• 대규모 (Large-scale): ogbn-arxiv, Reddit, ogbn-products.
• 장거리 (Long-range): Paris 및 London 도로 네트워크.

주요 결과:

• 성능: CoRe-GNN은 모든 카테고리에서 Coarsen-GNN 및 Cluster-GCN 베이스라인을 일관되게 능가합니다.
• 장거리 작업: Paris 및 London 데이터셋에서 CoRe-GNN은 가장 높은 정확도를 달성하여, Cluster-GCN이 놓치는 장거리 의존성과 순수 Coarsen-GNN이 부족한 판별력을 포착하는 능력을 입증했습니다.
• 이종성: 이종성 데이터셋(예: Squirrel)에서 CoRe-GNN은 동일한 슈퍼노드 내의 노드들이 서로 다른 레이블을 가질 때 어려움을 겪는 Coarsen-GNN보다 성능이 크게 뛰어납니다.
• 확장성: Reddit 및 ogbn-products와 같은 대규모 데이터셋에서 표준 GCN 및 비배칭(non-batched) CoRe-GNN은 메모리 부족(OOM) 오류가 발생합니다. 반면, CoRe-GNN의 배칭 버전은 성공적으로 훈련되며 Cluster-GCN과 대등하거나 더 우수한 정확도를 달성합니다.
• 절제 연구 (Ablation): 두 브랜치에 독립적인 가중치를 사용하고, 전체 축약 행렬 대신 인터-클러스터 전용 전파 행렬($S_{inter}^c$)을 사용하는 것이 더 나은 성능을 낸다는 것을 실험을 통해 확인했습니다.

의의 및 주장

본 논문은 CoRe-GNN이 그래프 축약과 클러스터 기반 제한의 이점을 성공적으로 통합한다고 주장합니다. 병렬 전파를 수행함으로써, 기존의 확장 가능한 방법들이 가진 상호 보완적인 실패 요소들, 즉 축약에 의한 노드 수준 세부 정보의 손실과 클러스터링에 의한 장거리 의존성 단절 문제를 극복합니다.

저자들은 CoRe-GNN이 다음을 제공하는 프레임워크임을 강조합니다:

1. 스무스 신호 전파를 위한 스펙트럼 보장을 유지합니다.
2. 이종성 환경에서 개별 노드의 판별력을 보존합니다.
3. 복잡한 그래프 작업을 위해 필수적인 장거리 의존성을 포착합니다.
4. 메모리 효율적인 배칭 체계를 통해 수백만 개의 노드로 확장 가능합니다.

이 연구는 그래프를 그룹으로 분해하는 것이 정확도와 확장성 사이의 트레이드오프가 될 필요가 없으며, 오히려 다층적 접근 방식을 통해 두 가지를 모두 달eric 수 있음을 시사합니다. 저자들은 현재 이 프레임워크가 고정된 전파 행렬을 가진 GNN(어텐션 메커니즘 제외)에 국한되어 있으며, 향후 연구에서 잔차 연결(residual connections) 및 비동기 연합 학습(asynchronous federated learning) 시나리오로의 확장을 탐구할 수 있다고 언급했습니다.