기술 요약: GRAPHLCP

문제 제기

그래프 신경망 (GNN) 은 신약 개발, 기상 예측, 사기 탐지 등 고위험 분야에서 점점 더 널리 배포되고 있어, 신뢰할 수 있는 불확실성 정량화 (UQ) 가 필수적입니다. 컨포멀 예측 (CP) 은 유한 표본 보장을 가진 집합형 예측을 구성하는 분포 자유 프레임워크를 제공합니다. 그러나 GNN 에 CP 를 적용하는 것은 고유한 도전 과제를 제시합니다:

1. 구조적 의존성: 그래프의 노드들은 본질적으로 의존적이므로, 고전적 CP 에 필요한 표준적인 독립 동일 분포 (i.i.d.) 가정을 위반합니다.
2. 임베딩의 한계: 기존 그래프용 지역화 CP 방법들은 종종 GNN 임베딩의 커널 밀도 추정과 같은 임베딩 공간 근접성에 의존하여 지역적 이웃을 정의합니다. 이 접근법은 다음과 같은 이유로 자주 신뢰할 수 없습니다:
   • 과도한 평활화 (Over-smoothing): 깊은 메시지 전달은 유사성 측정의 분산을 감소시켜 임베딩을 구별 불가능하게 만듭니다.
   • 과도한 압축 (Over-squashing): 위상적 병목 현상은 특히 이질성 (heterophily) 하에서 글로벌 정보 흐름을 제한합니다.
   • 낮은 자신감 (Under-confidence): GNN 은 학습된 표현에서 종종 불충분한 분리성을 보입니다.
3. 기존 해결책의 비효율성: 현재 그래프 특화 CP 방법들은 보조 모델 학습에 의존하여 (계산 오버헤드 증가) 또는 미세한 지역적 이질성을 포착하지 못하는 경직된 구조적 분할 (예: 하드 클러스터링) 을 사용합니다. 결과적으로 기존 방법들은 복잡한 위상에서 지나치게 보수적이거나 지역화가 잘 되지 않은 예측 집합을 산출하는 경우가 많습니다.

방법론: GRAPHLCP

저자들은 그래프 위상과 노드 간 의존성을 지역화 및 가중치 단계에 명시적으로 통합하도록 설계된 근접 기반 지역화 컨포멀 예측 프레임워크인 GRAPHLCP를 제안합니다. 이 방법은 GNN 이 사전 학습되고 고정된 전도식 (transductive) 설정에서 작동합니다. 프레임워크는 네 가지 주요 단계로 구성됩니다:

1. 특징 인식 밀도화 (Feature-Aware Densification)

희소 그래프에서의 지역성 편향을 완화하고 장기적 의미 의존성을 포착하기 위해, 저자들은 커널 계산 전에 밀도화 단계를 도입합니다.

• PCA 투영: 노드 임베딩은 먼저 주성분 분석 (PCA) 을 통해 투영되어 상관된 특징 차원을 분리하고 공간을 압축함으로써, 과도한 평활화로 인한 노이즈와 중복성을 해결합니다.
• 적응형 이방성 커널: PCA 변환된 임베딩을 사용하여 이방성 가우스 커널을 구성합니다. 대역폭은 차원 간 다양한 스케일을 고려하기 위해 공분산 행렬의 고유값에 기반하여 적응됩니다.
• 엣지 증강: 비연결 노드 간의 유사성 (가우스 커널을 통해 계산됨) 이 동적 임계값 $\tau_d$를 초과할 경우, 새로운 엣지가 그래프 인접 행렬에 추가됩니다. 이 임계값은 그래프의 동질성 비율에 기반하여 자동 조정되어, 정보성 엣지 추가와 노이즈 도입 사이의 균형을 맞춥니다.

2. 개인화 페이지랭크 (PPR) 커널

임베딩 거리에만 의존하는 대신, GRAPHLCP 는 구조적 근접성을 모델링하기 위해 PPR 을 활용합니다.

• 지역화: PPR 은 재시작 확률 ($\beta$) 을 통해 지역성을 유지하면서 멀티홉 영향을 포착합니다. 이는 가중치 CP 와 자연스럽게 정렬되는 부드럽고 확률적인 근접성 개념을 제공합니다.
• 샘플링: 테스트 노드의 경우, 테스트 노드를 중심으로 PPR 유도 분포에서 앵커 노드가 샘플링됩니다. 이는 인접한 노드가 분위수 추정에 더 큰 영향을 미치도록 보장합니다.
• 가중치 부여: 보정 노드와 테스트 노드는 샘플링된 앵커에 대한 구조적 근접성에 따라 가중치가 부여됩니다. 저자들은 차수 정규화된 PPR 대칭성 ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) 을 활용하여, 보정 샘플 수가 테스트 샘플 수를 초과할 때도 효율적으로 가중치를 계산합니다.

3. 무작위 지역화 컨포멀 예측 (RLCP) 통합

GRAPHLCP 는 RLCP 프레임워크를 적응합니다. 테스트 노드 $u_{n+1}$의 PPR 분포에서 앵커 노드 $\tilde{u}_{n+1}$을 샘플링함으로써, 이 방법은 비동일성 점수의 가중치 분위수에 기반한 예측 집합을 구성합니다. 가중치는 샘플링된 앵커에 대한 PPR 점수에서 유도되므로, 이 방법은 지역적 그래프 컨텍스트에 적응할 수 있습니다.

4. 예측 구성

최종 예측 집합 $\hat{C}_n(u_{n+1})$은 비동일성 점수 $s(u_{n+1}, y)$가 가중치 분위수 $\hat{q}_{1-\alpha}$보다 작거나 같은 레이블 $y$의 집합으로 구성됩니다. 이 분위수는 PPR 커널에서 유도된 가중치와 보정 집합의 비동일성 점수를 사용하여 계산됩니다.

주요 기여

1. 구조 인식 지역화: 이 논문은 임베딩 전용 근접성을 PPR 기반 커널로 대체함으로써 구조 기반 및 특징 기반 지역화 간의 격차를 해소합니다. 이는 그래프 위상을 컨포멀 가중치 과정에 명시적으로 통합합니다.
2. 특징 인식 밀도화: PCA 와 적응형 이방성 커널을 통한 임베딩 유사성을 사용하여 그래프 위상을 증강하는 새로운 전처리 단계로, 임베딩의 잠재적 노이즈가 있는 연속 가중치에 의존하지 않고도 희소성을 완화하고 장기적 의존성을 포착합니다.
3. 효율적인 가중치 부여 체계: 이 방법은 차수 정규화된 대칭성을 활용하여 무방향 그래프에 대한 PPR 기반 가중치를 효율적으로 계산하는 방법을 제공하며, 대규모 보정 집합에 대한 전체 PPR 벡터 계산의 계산적 비효율성을 피합니다.
4. 이론적 유효성: 이 접근법은 전도식 설정에서 주변 커버리지를 위해 필요한 교환성 보장을 유지하면서, 완화된 테스트 조건부 커버리지를 개선하는 것을 목표로 합니다.

실험 결과

저자들은 인용 네트워크, 아마존 공동 구매, 지리 데이터셋을 포함한 7 개의 노드 회귀 및 8 개의 노드 분류 데이터셋에서 GRAPHLCP 를 평가했습니다.

• 주변 커버리지: GRAPHLCP 를 포함한 모든 방법이 목표 오커버리지율 ($\alpha = 0.1$) 을 만족하여 접근법의 유효성을 확인했습니다.
• 조건부 커버리지 (WSC): 투영 방향 전반에 걸쳐 최소 커버리지를 적대적으로 찾는 Worst-Case Slab (WSC) 진단에서, GRAPHLCP 는 대부분의 데이터셋에서 CalLCP, RLCP, SCP 와 같은 베이스라인을 능가하며 가장 좋거나 두 번째로 좋은 결과를 달성했습니다.
• 그룹 기반 커버리지: GRAPHLCP 는 동질성, 특징 클러스터링, 클러스터링 계수, 노드 차수에 기반한 분할 전반에 걸쳐 우수한 커버리지를 보여주었습니다. 이 방법은 표준 방법들이 어려움을 겪는 이질성 영역에서 특히 효과적이었습니다.
• 예측 효율성: CalLCP 는 종종 과도하게 큰 예측 집합 (과커버리지) 을 생성하는 반면, GRAPHLCP 는 유리한 정규화 예측 길이를 달성하여 커버리지와 집합 크기 사이의 더 나은 균형을 제공했습니다.
• 절차 제거 연구 (Ablation Studies):
  • PPR 커널을 가우스 커널 (GSS) 로 대체하면 커버리지가 낮아지고 예측 집합이 커져, 구조 인식 지역화의 중요성이 확인되었습니다.
  • 밀도화 단계는 특히 회귀 작업에서 가장 중요한 구성 요소로 확인되었습니다.
  • PCA 투영은 상관된 임베딩 특징의 부정적 영향을 완화하는 데 결정적인 것으로 나타났습니다.

중요성과 주장

이 논문은 GRAPHLCP 가 구조적 의존성을 명시적으로 모델링함으로써 기존 그래프 CP 방법의 한계를 성공적으로 해결한다고 주장합니다. 잠재적 손실이 있는 GNN 인코더에서 가중치를 분리하고 PPR 기반 커널을 활용함으로써, 이 방법은 불확실성 정량화를 위한 "저노이즈 잔여 경로"를 생성합니다.

저자들은 GRAPHLCP 가 유한 표본으로 주변 커버리지를 보장하면서도 다양한 조건부 시나리오에서 유리한 테스트 조건부 커버리지를 효율적으로 달성한다고 주장합니다. 그들은 이 방법이 과도한 평활화나 과도한 압축으로 인해 임베딩 기반 유사성이 실패하는 복잡한 위상에서 특히 강력하다고 강조합니다. 이 연구는 특징 공간 근접성에만 의존하는 것을 넘어, 그래프에서의 효과적인 UQ 를 위해 구조 인식 지역화의 필요성을 강조합니다. 저자들은 미래 방향으로는 진화하는 위상을 가진 동적 그래프로 이 프레임워크를 확장하는 것을 포함한다고 겸손하게 언급합니다.