기술 요약: TN-SHAP-G

문제 정의

블랙박스 그래프 신경망(GNN)의 예측을 설명하기 위해서는 개별 노드와 그 상호작용에 대한 중요도를 할당해야 합니다. 샤플리 값(Shapley values)과 고차 상호작용 지수는 원칙적이고 공리적인 할당 방식을 제공하지만, 그래프에서의 정확한 계산은 노드 수 $n$에 따라 $O(2^n)$으로 기하급수적으로 증가하여 계산이 불가능합니다. 기존의 근사 방법들은 상당한 트레이드오프에 직면해 있습니다. 예를 들어, GNNExplainer와 같은 아키텍처 특정적 설명 도구는 일반적인 블랙박스 모델에 적용할 수 없으며, GraphSVX나 SHAP-IQ와 같은 샘플링 기반 접근 방식은 수천 번의 모델 평가를 요구하고 특히 고차 상호작용에서 높은 분산을 보입니다. 또한, 이러한 샘PLING 방식은 정확한 열거가 불가능한 대규모 그래프로 확장하는 데 한계가 있습니다.

방법론: TN-SHAP-G

저자들은 그래프 구조를 가진 입력의 구조적 특성을 활용하여 샤플리 값과 상호작용을 효율적이고 결정론적으로 계산하는 프레임워크인 TN-SHAP-G를 제안합니다. 핵심 아이디어는 마스킹된 입력(masked-input)의 거동을 근사하는 압축된 그래프 정렬 텐서 네트워크(graph-aligned tensor network, TN) 대리 모델(surrogate)을 학습하는 것입니다.

1. 마스킹된 그래프 게임 (The Masked Graph Game)

이 방법은 그래프 설명을 노드 마스킹에 의해 유도된 협력 게임으로 공식화합니다. 고정된 입력 그래프 $G=(V, E)$, 특징 $X$, 그리고 베이스라인 $X^0$가 있을 때, 연합(coalition) $S \subseteq V$는 $S$에 속한 노드는 원래의 특징을 유지하고 $S$에 속하지 않은 노드는 베이스라인 특징으로 대체되는 마스킹된 특징 행렬 $X_S$를 정의합니다. 게임의 가치는 $\nu(S) = f(G, X_S)$이며, 여기서 $f$는 블랙박스 예측기입니다.

2. 다선형 확장 및 텐서 수축 (Multilinear Extension and Tensor Contraction)

샤플리 값을 직접 계산하려면 $2^n$개의 연합을 모두 합산해야 합니다. 저자들은 이산 게임의 연속적 완화(continuous relaxation)인 $z \in [0, 1]^n$ 상의 다선형 확장(multilinear extension) $\hat{\nu}(z)$를 활용합니다.

• 텐서 정식화: 다선형 확장은 텐서 수축으로 정확하게 표현될 수 있습니다: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$, 여기서 $T$는 연합 텐서이고 $b_v(z_v)$는 베르누이 선택 벡터입니다.
• 결정론적 회복: 샤플리 값과 상호작용 지수는 대각선 $z = t\mathbf{1}$을 따른 $\hat{\nu}$의 편미분의 적분에 해당합니다. $\hat{\nu}$는 다선형이므로, 이러한 미분값은 차수가 최대 $n-1$인 단변수 다항식입니다. 따라서, 소수의 프로브 포인트(probe points)로부터 **반데르몽드 보간법(Vandermonde interpolation)**을 통해 정확한 할당량을 회복할 수 있으며, 이를 통해 몬테카를로 분산을 제거할 수 있습니다.

3. 그래프 정렬 텐서 네트워크 대리 모델 (Graph-Aligned Tensor Network Surrogate)

전체 연합 텐서 $T$는 $2^n$개의 엔트리를 가지므로, TN-SHAP-G는 다선형 확장을 근사하기 위해 그래프 정렬 텐서 네트워크 대리 모델 $\hat{\nu}$를 학습합니다.

• 토폴로지: TN 토폴로지는 입력 그래프 $G$를 반영합니다. 각 노드 $v$는 하나의 물리적 인덱스(연합 멤버십 인코딩)와 이웃로 연결되는 본드(bond) 인덱스를 가진 코어 텐서 $A^{(v)}$에 대응합니다.
• 표현력: 본드 차원(bond dimension) $\chi$는 그래프 세퍼레이터(separator)를 통한 정보 흐름의 용량을 제어합니다. 저자들은 많은 로컬 의존성 패턴을 가진 게임에서 이 그래프 정렬 구조가 순환적이거나 복잡한 그래프에서 랭크 팽창(rank inflation) 문제를 겪는 체인 기반 인수 분해 방식인 텐서 트레인(Tensor Trains, TT)보다 더 적은 파라미터로 더 높은 표현력을 달성함을 증명합니다.
• 학습: 대리 모델은 적은 수의 샘플링된 연합($M \ll 2^n$)에 대한 경험적 위험 최소화(empirical risk minimization)를 통해 학습됩니다. 이론적 보증에 따르면, 요구되는 쿼리 예산은 유계 차수(bounded-degree) 그래프에 대해 노드 수에 거의 선형적으로 비례하여 확장됩니다.

4. 추론 (Inference)

학습된 후, 대리 모델은 다음을 결정론적으로 계산할 수 있게 합니다:

• 1차 샤플리 값: 대각선 미분의 1차 적분을 통해 계산합니다.
• 고차 상호작용: 혼합 편미분 및 적분을 통해 계산합니다.
  모든 양은 추가적인 블랙박스 모델 쿼리 없이 단일 학습된 대리 모델로부터 계산됩니다.

주요 기여

1. 원칙적인 그래프 정렬 표현: 지수적인 연합-가치 테이블을 저차원, 그래프 정렬 다선형 표현으로 압축하는 텐서 네트워크 대리 모델을 도입했습니다. 이는 대리 모델의 귀납적 편향(inductive bias)을 그래프 예측자의 로컬 의 dependency 패턴과 일치시킵니다.
2. 아모티즈된 결정론적 계산 (Amortized Deterministic Computation): 다선형 구조를 활용하여 반데르몽드 보간법을 통해 샤플리 값과 상호작용을 결정론적으로 계산합니다. 이는 $O(n)$개의 대리 모델 평가만을 필요로 하며 몬테카를로 분산을 발생시키지 않습니다. 단일 대리 모델은 모든 1차 및 고차 지수의 계산 비용을 아모티즈(amortize)합니다.
3. 이론적 보증:
   • 학습된 대리 모델이 다선형 확장을 유일하게 결정함을 증명하여, 대리 모델 상에서 할당량의 정확한 회복을 보장합니다.
   • 컷 랭크(cut-rank) 논증을 통해 표현력을 규명하여, 그래프 정렬 TN이 체인 인수 분해(TT 등)보다 우수함을 증명합니다.
   • 유계 차수 그래프에 대해 근선형(near-linear) 교사 쿼리(teacher-query) 복잡도 경계를 제시합니다.
   • 게임 근사 오차와 샤플리 오차 사이의 관계를 연결하는 안정성 보증을 제공합니다.
4. 실험적 성능: 분자 벤치마크에서 높은 정확도를 입증하였으며, 단 50회의 모델 평가만으로도 정확한 샤플리 값과 0.99 이상의 코사인 유사도를 달축성하였습니다(기존 베이스라인 대비 10~100배 적은 쿼리).

실험 결과

저자들은 분자 벤치마크(Mutagenicity, Benzene)와 단백질 그래프(PROTEINS)에서 TN-SHAP-G를 평가했습니다.

• 정확성: 작은 그래프($n \le 20$)에서 TN-SHAP-G는 정확한 샤플리 값(O1) 및 상호작용 지수(O2)와 매우 밀접하게 일치하며, 정확도와 분산 측면 모두에서 GraphSVX 및 순열 샘플링을 크게 능가했습니다.
• 쿼리 효율성: TN-SHAP-G는 샘플링 기반 추정기(SHAP-IQ, GraphSVX)보다 10~100배 적은 모델 쿼리로 높은 할당 정확도를 달성했습니다.
• 확장성: TN-SHAP-G는 코어닝(coarsening) 기반 대리 모델 아키텍처를 사용하여 최대 600개의 노드를 가진 그래프까지 효율적으로 확장 가능하며, 이는 샘플링 기반 방법이 실질적으로 불가능한 영역입니다.
• 구조 절제 연구 (Structure Ablation): 그래프 정렬 TN은 파라미터가 동일한 조건에서 TT 대리 모델보다 일관되게 우수한 성능을 보였으며, 이는 토폴로지 정렬 인수 분해의 이론적 이점을 확인시켜 줍니다.
• 충실도 프록시 (Fidelity Proxy): 대리 모델의 테스트 $R^2$와 회복된 샤플리 값의 코사인 유사도 사이에 강한 상관관계가 관찰되었으며, 이는 $R^2$가 할당 정확도의 실용적인 프록시로서 유효함을 입증합니다.

의의 및 주장

본 논문은 TN-SHAP-G가 샤플리 계산의 지수적 복잡성을 극克服하는 원칙적이고 모델 불가지론적인 프레임워크를 제공함으로써 그래프 설명 가능성의 최첨단 기술(SOTA)을 발전시킨다고 주장합니다. 그래프 구조를 가진 협력 게임에 내재된 저계수(low-rank) 구조를 활용함으로써, 이 방법은 결정론적이고 분산이 없는 할당을 근선형 쿼리 복잡도로 가능하게 합니다.

저자들은 이 접근 방식이 제한된 계산 자원을 가진 실무자들, 특히 신약 개발 및 분자 특성 예측과 같은 고위험 분야의 실무자들이 엄격한 설명 방법론에 접근할 수 있도록 민주화한다고 강조합니다. 이 프레임워크는 다양한 게임 세만틱스(예: 노드 마스킹, 노드 제거, Myerson 값)와 특징 유형을 지원하도록 유연하며, 표준 메시 패싱 GNN을 넘어 다른 그래프 예측기로도 확장 가능합니다. 이 연구는 텐서 네트워크를 단순한 압축 도구가 아니라, 구조화된 데이터에 대한 실행 가능한 게임 이론적 분석을 위한 근본적인 메커니즘으로 자리매김합니다.