기술 요약: 설계 단계에서 해석 가능성을 갖춘 일반화된 티호노프 계층을 위한 그래프 신경망

문제 제기

그래프 신경망 (GNN) 은 그래프 토폴로지를 통해 특징을 집계하는 방법을 학습함으로써 그래프 및 노드 분류 작업에서 상당한 성과를 거두었습니다. 그러나 그 해석 가능성은 여전히 중요한 과제로 남아 있습니다. 고전적인 신경망과 달리, GNN 은 입력 특징이 어떻게 변환되는지뿐만 아니라 그래프 토폴로지 자체가 어떻게 활용되는지도 설명해야 합니다. 기존 해석 방법들은 종종 신뢰성 보장이 부족한 사후 근사 (예: GNNExplainer, 기울기 saliency) 에 의존하거나, 설명 추출기가 분류기로부터 분리된 2 모듈 아키텍처를 사용합니다. 이러한 경우 분류기는 손실을 최소화하는 동안 설명을 무시할 수 있습니다. 또한, 심층 GNN 은 노드 표현의 붕괴 (oversmoothing) 와 장거리 민감도의 지수적 감쇠 (oversquashing) 와 같은 병리 현상에 시달립니다.

방법론

저자들은 설계 단계에서 해석 가능하도록 고안된 그래프 신경망 계층인 **티호노프 계층 (Tikhonov layer)**을 제안합니다. 핵심 혁신은 일반화된 그래프 티호노프 정규화 문제에서 유도된 특정 폐형식 (closed-form) 해로 그래프 전파 행렬 $R$을 제약하는 데 있습니다.

전파 연산자

정규화된 라플라시안 $L$을 갖는 그래프에 대해, 입력 특징 $X$에 대한 계층 출력은 다음과 같습니다:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
여기서 전파 행렬 $R$은 다음과 같이 정의됩니다:
$$R = (p(L) + Q)^{-1} Q$$
여기서:

• $L$은 정규화된 그래프 라플라시안입니다.
• $Q = \text{diag}(q_1, \dots, q_n)$은 엄격히 양수인 노드 중요도 점수의 학습 가능한 대각 행렬입니다.
• $p(\cdot)$은 $\lambda \in [0, 2]$에 대해 $0 < p(\lambda) < 1$을 만족하는 학습 가능한 다항식입니다.
• $\sigma$는 점별 비선형 함수이고 $W$는 가중치 행렬입니다.

변분 해석

연산자 $R$은 일반화된 티호노프 문제의 유일한 폐형식 최소화자입니다:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
이 공식은 노드 수준의 데이터 충실도 (가중치 $q_i$로 가중됨) 와 토폴로지 주도 정규화 ($p(L)$에 의해 지배됨) 간의 명시적 절충을 나타냅니다.

• 큰 $q_i$: 노드 $i$는 자체 특징에 크게 의존합니다. 출력 $z_i$는 $x_i$와 가깝게 유지됩니다.
• 작은 $q_i$: 노드 $i$는 그래프 토폴로지에 의해 주도되는 해결책 (매끄러움 또는 $p$에 의해 정의된 특정 스펙트럼 특성) 을 선호하여 자체 특징을 버립니다.
• $p(\lambda)$의 형태: 토폴로지적 영향의 성질을 결정합니다. 증가하는 $p$는 고주파수를 패널티하여 (동질성/매끄러움을 선호) 감소하는 $p$는 저주파수를 패널티합니다 (이질성을 선호).

아키텍처와 표현력

해석 가능성을 희생하지 않으면서 높은 표현력을 유지하기 위해, 아키텍처는 관심사의 분리를 채택합니다:

1. Q-네트워크: 그래프 $(G, X)$를 입력으로 받아 노드 중요도 점수 $Q$를 출력하는 전용의 (심층일 수 있는) GNN(예: ChebNet 또는 ARMA) 입니다. 이 구성 요소는 복잡한 표현 학습을 처리하고 $q_i$를 국소 그래프 구조와 특징에 맞게 적응시킵니다.
2. 티호노프 계층: 전파 $R$을 적용하는 단일 투명한 계층입니다. 숨겨진 비선형성이나 복잡한 메시지 전달 단계가 없으며, 그 매개변수는 다항식 계수 $p$와 Q-네트워크의 출력입니다.
3. 헤드: 최종 예측을 위한 전역 풀링 연산과 MLP 가 뒤따릅니다.

이 모델은 여러 독립적인 Q-네트워크와 다항식을 사용하는 멀티채널 확장을 지원하지만, 실험은 단일 채널 경우 ($J=1$) 에 초점을 맞춥니다.

구현 세부 사항

• 계산: $(p(L) + Q)^{-1}QX$를 계산하는 것은 선형 시스템을 푸는 것을 포함합니다. 저자들은 밀집 역행렬의 $O(n^3)$ 비용을 피하기 위해 대각 (야코비) 프리컨디셔너를 사용하는 **프리컨디셔널 켄jugate Gradient (PCG)**를 사용합니다. 이는 $T$를 반복 횟수라고 할 때 $O(dTKm)$의 확장성을 달성합니다.
• 미분: 솔버의 계산 그래프를 저장하는 것을 피하기 위해, 저자들은 암시적 미분을 사용하여 $Q$와 $p$에 대한 기울기를 계산하기 위해 역방향 전달에서 PCG 솔브를 한 번만 추가로 수행합니다.
• 제약: 다항식 $p(\lambda)$는 시그모이드 활성화 함수를 사용하는 베른슈타인 다항식으로 매개변수화되어 $0 < p(\lambda) < 1$을 엄격하게 강제합니다. 점수 $q_i$는 로그 공간 클램핑 함수를 통해 엄격히 양수 값으로 매핑됩니다.

주요 기여 및 이론적 속성

1. 내장 해석 가능성: 쌍 $\{ \{q_i\}_{i \in V}, p(\cdot) \}$은 직접적이고 충실한 설명을 구성합니다. 큰 $q_i$는 특징 의존성을 나타내고, 작은 $q_i$는 토폴로지 의존성을 나타냅니다. $p$의 형태는 스펙트럼 편향 (동질성, 이질성, 대역 통과) 을 드러냅니다.
2. 구조적 결합: 저자들은 (Proposition 3.6) 매핑 $Q \mapsto R$이 단사 (injective) 임을 증명합니다. 사후 방법과 달리, 설명 ($Q$) 을 변경하면 전파 연산자 ($R$) 가 필연적으로 변경되어 설명이 계산에 충실함을 보장합니다.
3. 표현력: 동질적인 경우 이 계층은 연속 스펙트럼 필터 공간에서 조밀한 것으로 나타났습니다. 이질적인 $Q$를 사용하면 정상성 (stationarity) 을 깨뜨림으로써 (Proposition 3.3) 전통적인 스펙트럼 필터를 넘어 표현력을 엄격히 확장합니다.
4. GNN 병리 현상 완화:
   • 과다 평활화 (Oversmoothing): 단일 계층 사용과 $p(L) + Q$의 가역성을 통해 방지됩니다. 노드 붕괴는 모델이 고의적으로 모든 $q_i \to 0$을 유도할 때만 발생합니다.
   • 과다 압축 (Oversquashing): 장거리 민감도 $|R_{ij}|$의 감쇠율은 학습된 $Q$에 의존하는 시스템의 조건수 $\kappa$에 의해 지배됩니다. 모델은 필요한 곳에서 장거리 민감도를 높이기 위해 특정 $q_i$를 낮춤으로써 $\kappa$를 줄이는 방법을 학습할 수 있으며, 이는 국소 정밀도와 글로벌 도달 범위 간의 효과적인 절충입니다.

실험 결과

이 모델은 합성 및 표준 벤치마크에서 평가되어 성능과 해석 가능성을 모두 입증했습니다:

• 제어된 합성 작업:
  • Colors-3: 이 작업은 오직 노드 특징에만 의존합니다. 모델은 모든 곳에서 큰 $q_i$를 학습하여 토폴로지를 효과적으로 무시하고 MLP 처럼 행동하며, 특징이 예측을 주도한다는 것을 올바르게 식별했습니다.
  • Clique Distance: 순수 구조적 작업입니다. 모델은 경로 노드에 대해서는 작은 $q_i$를 (거리 감지를 위해 토폴로지에 의존), 클리크 노드에 대해서는 큰 $q_i$를 (앵커) 학습하여 100% 정확도를 달성했습니다.
  • Triangles: 삼각형을 감지하는 구조적 작업입니다. 모델은 일반적으로 작은 $q_i$를 할당했지만 삼각형 꼭짓점에는 더 큰 $q_i$를 할당하여 지도 없이 모티프를 정확히 지목했습니다.
• CSBM (Contextual Stochastic Block Model): 모델은 복구 이론적 위상 전이 임계값을 성공적으로 추적했습니다. 학습된 $q_i$ 값은 특징 주도 (큰 $q_i$) 에서 토폴로지 주도 (작은 $q_i$) 영역으로 부드럽게 전환되어 혼합 영역에서 신호의 원천을 올바르게 식별했습니다.
• ECHO-diam (장거리 전파): 그래프 지름 회귀 작업에서 모델은 평균 절대 오차 (MAE) 1.17 을 달성하여 심층 GNN 베이스라인 (~1.6) 을 능가하고 트랜스포머 성능 (1.05) 에 근접했습니다. 설명은 모델이 말단 노드 (끝점) 에 큰 $q_i$를, 내부 노드에 작은 $q_i$를 할당하여 고정된 끝단과 평활화된 내부 사이의 대비를 사용하여 지름을 추정했음을 드러냈습니다.

중요성과 주장

이 논문은 사후에 설명을 복구하는 대신 계층을 자체 설명 가능하도록 설계함으로써 GNN 해석 가능성에 대한 새로운 접근법을 제공한다고 주장합니다.

• 충실도: 설명은 모델 그 자체입니다. 분리된 서브그래프나 근사치가 없습니다.
• 세분화: 이진 서브그래프 선택이 아닌 연속적이고 공간적으로 분해된 답변 (등급화된 $q_i$ 값) 을 제공합니다.
• 성능: 이 모델은 다양한 작업에서 불투명한 베이스라인 (GIN, GAT, 트랜스포머 등) 과 일치하거나 능가하면서, 작업이 어떻게 해결되는지 (예: 특징 기반 추론과 토폴로지 기반 추론 구분) 에 대한 통찰력을 제공합니다.
• 한계: 저자들은 일부 설명이 인간이 해석하기 복잡할 수 있으며, 장거리 상호작용이 필요한 작업의 경우 PCG 의 계산 비용이 높을 수 있음을 인정합니다 (다만 추후 근사를 위한 무작위 수치 선형 대수를 제안합니다).

이 연구는 GNN 계층을 특정 변분 형태로 제약하여 복잡한 비정상 그래프 필터를 학습하는 능력을 희생하지 않으면서 해석 가능성을 얻을 수 있음을 입증합니다.