DuoGNN: Topology-aware Graph Neural Network with Homophily and Heterophily Interaction-Decoupling

DuoGNN 기술 요약

문제 정의
그래프 신경망(GNN)은 국소적 이웃 집계(local neighborhood aggregation)를 활용하여 단거리 공간 상호작용을 포착함으로써 의료 영상학을 포함한 다양한 영역에서 효능을 입증해 왔다. 그러나 이러한 패러다임은 모델의 표현력을 저해하고 심층 아키텍처의 효과적인 사용을 방해하는 두 가지 근본적인 한계점을 갖는다:

1. 오버-스무딩(Over-smoothing): 이종 결합(heterophilic) 노드 집계 시, 레이어 수가 증가함에 따라 노드 임베딩이 구별 불가능해지며 서로 다른 클래스의 노드 특징들이 수렴하게 된다.
2. 오버-스쿼싱(Over-squashing): 그래프 병목 현상이 메시 전달을 방해하여 노드의 수용 영역(receptive field)이 기하급적으로 성장하게 만들고, 상당한 양의 정보가 고정된 크기의 특징 벡터로 붕괴되도록 강제한다.

트랜스포머 기반 어텐션 메커니즘, 멀티 스케일 아키텍처, 위상적 그래프 리와이어링(topological graph rewiring)과 같은 기존 솔루션들은 심각한 단점들을 안고 있다. 어텐션 메커니즘은 이차 시간 복잡도($O(|V|^2)$)를 가지며 위상적 인지 능력이 부족하다. 멀티 스케일 모델은 종종 계산 비용이 많이 들고 위상 특이적인 클러스터링 알고리즘에 의존한다. 리와이어링 알고리즘은 병목 현상을 완화하는 데는 효과적이지만, 그래프 구조를 과도하게 왜곡하거나 매우 크거나 사슬 형태인 그래프에서의 문제를 해결하지 못할 수 있다. 결과적으로, 다양한 그래프 위상 전반에 걸쳐 단거리 및 장거리 상호작용(LRI)을 동시에 포착할 수 있는 확장 가능하고 일반화 가능한 접근 방식이 부족한 실정이다.

방법론: DuoGNN 아키텍처
저자들은 동종(homophilic) 상호작용과 이종(heterophilic) 상호작용을 분리하여 독립적으로 처리하도록 설계된 위상 인지 아키텍처인 DuoGNN을 제안한다. 이 모델은 3단계 파이프라인을 통해 작동한다:

1. 상호작용 분리 단계 (Interaction-Decoupling Stage):

   • 위상적 엣지 필터링 (Topological Edge Filtering): 모델은 입력 그래프의 엣지에 대해 위상적 척도(예: 중심성 또는 곡률)를 계산한다. 모델은 해당 지표의 가장 높은 값(예: 가장 높은 중심성)을 가진 $\kappa$개의 엣지를 제거하는데, 이는 해당 엣지들이 그래프 병목 현상에 가장 가까울 가능성이 높기 때문이다. 이는 효과적으로 그래프를 동종 연결 성분으로 분리한다. 이를 통해 오버-스무딩 위험을 완화하면서 단거리 상호작용을 보존하는 동종 그래프($G_{ho}$)를 생성한다.
   • 이종 그래프 응축 (Heterophilic Graph Condensation): 엣지 필터링 과정에서 손실된 장거리 상호작용을 복구하기 위해, 모델은 $G_{ho}$에서 가장 밀도가 높은 $\mu$개의 클러스터를 식별한다. 각 클러스터에 대해 가장 연결성이 높은 노드(가장 신뢰할 수 있는 표현을 가졌다고 가정됨)를 선택하고 별도의 완전 연결 그래프(fully-connected graph, $G_{he}$)를 구축한다. 이러한 응축은 노드 수를 획기적으로 줄이면서도 이종 상호작용과 장거리 상호작용(LRI)을 보존함으로써 확장성을 보장한다.

2. 병렬 변환 단계 (Parallel Transformation Stage):

   • 모델은 $G_{ho}$와 $G_{he}$를 독립적인 GNN 모듈을 통해 처리한다.
   • 동종 모듈 (Homophilic Module): 동일한 클래스 내의 노드 임베딩을 집계하기 위해 표준 집계 방식($X^{(i+1)}_{ho} = \phi_{ho}(\hat{A}_{ho}X^{(i)}_{ho}W^{(i)}_{ho})$)을 사용한다.
   • 이종 모듈 (Heterophilic Module): 오버-스무딩을 방지하기 위해 수정된 집계 전략을 채택한다. 원래의 특징을 보존하기 위해 첫 번째 레이어에서는 특징을 집계하지 않으며, 모든 레이어의 출력을 선형 레이어로 결합(concatenate)한다. 이를 통해 모델은 다양한 평활도(smoothness) 수준에서 서로 다른 이웃 간의 차이를 학습할 수 있다.

3. 예측 단계 (Prediction Stage):

   • 두 모듈의 출력은 결합되어 최종 선형 레이어를 통과하며, 이를 통해 분류를 위한 최종 노드 표현을 생성한다.

주요 기여
본 논문은 세 가지 핵심 기여를 명시한다:

1. 위상적 엣지 필터링 알고리즘: 병목 엣지를 제거함으로써 동종 상호작용을 추출하는 알고리즘으로, 모델이 어떤 그래프 위상에서도 일반화될 수 있게 한다.
2. 이종 그래프 응축: 클러스터를 더 작은 완전 연결 그래프로 응축하여 이종 상호작용을 추출하는 기술로, 확장성을 보장한다.
3. 이중 집계 파이프라인: 단일 집계 패러다임에 의존하는 대신, 동종 및 이종 상호작용을 독립적으로 처리함으로써 오버-스무딩과 오버-스쿼싱을 방지하는 메커니즘이다.

결과 및 평가
DuoGNN은 의료 및 비의료 데이터셋 모두에서 표준 베이스라인(GCN, GIN, GAT) 및 위상 필터링이 적용된 변형 모델들과 벤치마킹되었다:

• 데이터셋: MedMNIST (CT 스캔의 간 종양 분류를 포함하는 Organ-C 및 Organ-S)와 Cora (과학 출판물 분류).
• 성능: DuoGNN 변형 모델들은 모든 태스크에서 베이스라인 모델들을 일관되게 능가했다. 곡률 강화 변형(discrete Olivier's Ricci curvature 사용)이 가장 높은 성능을 달성했는데, 이는 오버-스무딩 또는 오버-스쿼싱의 영향을 받는 영역을 탐지하는 이론적 능력 덕분인 것으로 보인다.
• 확장성: DuoGNN은 이중 집계 패러다임으로 인해 작은 그래프에서는 더 높은 GPU 메모리 점유율을 보였으나, MedMNIST 데이터셋에서 실행 실패(OOM)를 겪은 어텐션 기반 모델(GAT 등)에 비해 대규모 그래프에서 우수한 확장성을 입증했다. 이종 응축 기술은 장거리 상호작용(LRI) 분석에 대한 계산 부하를 줄여주었다.
• 절제 실험 (Ablation): 단순한 전처리 기술(베이스라인에 필터링 적용)은 미미한 개선만을 보여주었으며, 이는 장거리 상호작용을 효과적으로 포착하기 위해 전체 아키텍처가 필요함을 시사한다.

의의 및 주장
저자들은 DuoGNN이 GNN의 고질적인 문제인 오버-스무딩과 오버-스쿼싱에 대한 확장 가능하고 일반화 가능한 솔루션을 제공한다고 주장한다. 위상적 특성을 활용하여 상호작용 유형을 분리함으로써, 이 모델은 의료 영상 및 복잡한 장거리 의존성을 가진 대규모 데이터셋이 포함된 분야에서 GNN의 적용 범위를 넓힌다. 본 논문은 기존 방법들이 위상에 따라 일반화에 실패하거나 과도한 계산 비용을 초래하는 것과 달리, DuoGNN은 성능 저하를 필연적으로 야기하는 심층 네트워크 없이도 그래프 밀도와 구조에 적응하는 정교한 집계 프로토콜을 제공한다는 점을 강조한다.