기술 요약: 정보 이론의 관점을 통한 이질적 그래프의 불확실성 추정

문제 제기

그래프 신경망 (GNN) 에 대한 불확실성 추정은 상당한 관심을 받아 왔으나, 대부분의 기존 방법은 동질성 (homophily)—즉, 노드가 동일한 클래스의 다른 노드와 연결되는 경향—에 대한 가정에 크게 의존합니다. 이러한 방법들은 종종 불확실성을 전파하기 위해 그래프 확산 또는 평활화 커널을 사용하는데, 이는 의미적으로 유사한 노드가 연결되어 있을 때 효과적입니다. 그러나 서로 다른 클래스의 이웃 노드와 주로 연결되는 이질적 (heterophilic) 환경에서는 이러한 접근 방식이 성능이 저하됩니다. 이질적 그래프에서는 평활화를 통한 (불)확실성 전파에 대한 근거가 약하며, 이로 인해 분포 외 (O.O.D.) 감지 및 불확실성 정량화에서 낮은 성능을 보입니다. 더 나아가, 기존 연구는 동질성 가정이 위반될 때 불확실성 추정기가 어떻게 작동하는지를 체계적으로 연구한 바가 없으며, 동질성을 명시적으로 활용하지 않는 이질적 그래프를 위한 전용 접근법도 존재하지 않았습니다.

방법론

저자들은 정보 이론적 관점에서 이 문제에 접근하여, 잠재 노드 표현이 계층을 통해 어떻게 진화하는지 이해하기 위해 메시지 전달 신경망 (MPNN) 을 분석합니다.

1. MPNN 의 정보 이론적 분석

정보 병목 (Information Bottleneck) 원리 (Tishby & Zaslavsky, 2015) 에서 영감을 받아, 저자들은 MPNN 내의 정보 흐름을 모델링합니다. 독립적이고 동일하게 분포된 (i.i.d.) 데이터를 위한 표준 신경망에서는 대상 변수에 대한 정보가 계층을 거치면서 감소하거나 일정하게 유지된다는 데이터 처리 부등식 (DPI) 이 적용되는 반면, 저자들은 MPNN 에 대해 **데이터 처리 등식 (Data Processing Equality, DPE)**을 유도합니다.

주요 이론적 통찰은 다음과 같습니다:

• 정보 회복 및 획득: MPNN 에서 노드 레이블 $Y$에 대한 정보는 노드 자체의 특징에만 국한되지 않고 에고 그래프 (ego-graph) 전반에 분포되어 있습니다. 저자들은 홉 (hop) 거리를 기반으로 분할된 집합 $G_v^{(i)}$로 분해된 에고 그래프 $G_v$를 정의합니다.
• 등식: $i+1$ 계층의 표현이 가진 상호 정보 $I(Y; Z^{(i+1)})$는 다음과 같이 가법적으로 분해됩니다:
  $$I(Y; Z^{(i+1)}) = I(Y; Z^{(i)}) - \Delta_{(-)}^{(0:i)} + \Delta_{(+)}^{(i+1)}$$
  여기서 $\Delta_{(-)}^{(0:i)}$는 기존 에고 그래프에 대한 정보 손실 (또는 회복) 을 나타내고, $\Delta_{(+)}^{(i+1)}$는 새로운 $i+1$ 홉 이웃으로부터의 정보 획득을 나타냅니다.
• 이질성 vs 동질성:
  • 동질적 그래프에서는 인접 노드가 유사한 의미를 공유합니다. 따라서 깊이가 깊어질수록 정보 획득량 $\Delta_{(+)}^{(i+1)}$은 감소하는데, 이는 더 깊은 계층이 대상에 대한 새로운 의미 정보를 제공하지 않기 때문입니다.
  • 이질적 그래프에서는 인접 노드가 서로 다른 의미를 가집니다. 정보 획득량 $\Delta_{(+)}^{(i+1)}$은 크고 양수일 수 있으며, 이는 더 깊은 잠재 임베딩이 더 얕은 임베딩이 놓친 데이터 분포에 대한 유일하고 독특한 정보를 포함하고 있음을 의미합니다.

2. 결합 잠재 밀도 추정 (JLDE)

이질적 그래프는 전체 데이터 분포를 포착하기 위해 모든 노드 표현을 결합적으로 고려해야 한다는 발견에 기반하여, 저자들은 **결합 잠재 밀도 추정 (Joint Latent Density Estimation, JLDE)**을 제안합니다.

• 메커니즘: i.i.d 환경에서 일반적이듯이 단일 최종 계층에서 밀도를 추정하거나 그래프 확산을 사용하는 대신, JLDE 는 MPNN 의 모든 계층에서 추출된 잠재 임베딩 ($Z^{(0)}, Z^{(1)}, \dots, Z^{(L)}$) 을 연결합니다.
• 구현: 이 연결된 결합 임베딩 공간에 간단한 사후 (post-hoc) K-최근접 이웃 (KNN) 밀도 추정기를 적용합니다. 인식론적 불확실성 $u_{epi}(v)$는 훈련 분포 내 노드의 결합 표현에 대한 음의 로그 가능도로 계산됩니다.
• 설계 원칙: 이 접근법은 평활화 (smoothing) 와 같은 후처리를 통해 동질성을 명시적으로 활용하지 않으며, 모든 MPNN 백본에 적용 가능합니다.

주요 기여

1. 이론적 프레임워크: 본 논문은 MPNN 에 대한 데이터 처리 부등식의 새로운 유사체를 유도하여, 서로 다른 거리의 이웃이 제공하는 고유한 의미 정보로 인해 이질적 환경에서 모델 깊이에 따라 정보가 증가할 수 있음을 증명합니다.
2. 정보 기반 동질성 정의: 저자들은 목표 레이블과 관련된 공유 정보와 관련 없는 노이즈를 구분하는 상호 정보에 기반한 동질성 정의를 도입합니다.
3. JLDE 방법: 모든 잠재 표현을 결합적으로 모델링하는 간단하고 사후적인 설계 원칙인 결합 잠재 밀도 추정을 제안합니다. 이 방법은 동질성 가정에 의존하지 않고 이질적 그래프의 불확실성 정량화를 명시적으로 목표로 하는 최초의 방법입니다.
4. 실증적 검증: 이 방법은 여러 데이터셋, 분포 변화, 백본 아키텍처에 걸쳐 평가되어 최첨단 성능을 입증했습니다.

실험 결과

저자들은 세 가지 유형의 분포 변화 (Leave-Out-Class, Near Feature Perturbations, Far Feature Perturbations) 하에서 여섯 개의 데이터셋 (네 개의 이질적: Amazon Ratings, Roman Empire, Chameleon, Squirrel; 두 개의 동질적: CoraML, PubMed) 에서 JLDE 를 평가했습니다.

• 이질적 성능: 이질적 데이터셋에서 JLDE 는 일관되게 최첨단 인식론적 불확실성 (O.O.D. 감지 AUC-ROC 및 AUC-PR 로 측정) 을 달성합니다. 특히 깊은 계층의 정보가 중요한 시나리오에서 그래프 확산에 의존하는 방법 (예: GPN, GEBM) 이나 표준 앙상블 방법보다 훨씬 우수한 성능을 보입니다.
• 동질적 성능: 동질적 데이터셋에서 JLDE 는 다른 모델 무관 추정기와 경쟁력 있는 성능을 보이며, 동질성을 활용하는 후처리를 사용하지 않음에도 불구하고 동질성을 위해 명시적으로 설계된 방법과 동등한 성능을 달성합니다.
• 애블레이션 연구: 실험은 이질적 그래프의 경우 모든 계층의 결합 연결에 비해 최종 계층만 사용하거나 계층별 밀도를 평균내는 것이 열악한 결과를 초래함을 확인했습니다. 반면, 동질적 그래프에서는 결합 접근 방식이 최종 계층만 사용하는 것과 동등한 성능을 발휘하여, 이러한 환경에서는 더 깊은 계층이 새로운 정보를 추가하지 않는다는 이론을 검증했습니다.
• 백본 무관성: 이 방법은 다양한 백본 (Res-GCN, Res-GAT-Sep, Res-GATE, GPRGNN) 에 사후적으로 적용되어 다양한 아키텍처에서 항상 최상위 또는 차상위 추정기로 평가되었습니다.

중요성과 주장

본 논문은 동질성 가정을 넘어선 그래프 기반 불확실성 추정을 위한 이론적 토대를 제공한다고 주장합니다. 이질적 그래프에서는 각 임베딩 계층이 데이터 분포에 대한 고유한 정보를 제공한다는 점을 밝혀냄으로써, 저자들은 다음과 같은 핵심 설계 원칙을 확립합니다: 불확실성 추정은 모든 노드 표현을 결합적으로 고려해야 한다.

저자들은 그들의 작업이 다음과 같은 점을 강조한다고 명시합니다:

• 불확실성 정량화를 위해 이질적 그래프를 명시적으로 대상으로 삼은 기존 연구가 없다는 문헌의 격차를 해소합니다.
• 동질성 가정이 위반될 때 기존 추정기들이 종종 실패함을 보여줍니다.
• 복잡한 아키텍처 변경이나 명시적 동질성 활용 없이 최첨단 결과를 달성하는 간단하고 효과적이며 모델 무관한 솔루션 (JLDE) 을 제공합니다.
• 비동질적 데이터에서 모델 불확실성을 이해하는 것이 중요한 고위험 분야에서 신뢰할 수 있고 신뢰할 만한 AI 개발에 기여합니다.

저자들은 JLDE 가 인식론적 불확실성을 개선하지만, 본질적으로 우연적 불확실성 (aleatoric uncertainty) 이나 모델 보정을 개선하지는 않으며, 이는 향후 연구의 독립적인 방향임을 명시하며 범위에 대해 겸손한 태도를 유지합니다. 또한 그들은 더 정교한 밀도 모델이 단순한 KNN 기반 구현을 더 개선할 수 있을 것이라고 추측합니다.