기술 요약: CQD-SHAP

문제 정의

지식 그래프(KG)에서의 복잡한 질의 응답(Complex Query Answering, CQA)은 단순한 링크 예측을 넘어 다중 홉 추론 및 논리 연산자(논리곱, 논리합)를 처리하는 과정을 포함합니다. CQD(Complex Query Decomposition)와 같은 신경-기호(neurosymbolic) 접근 방식은 불완전한 실제 지식 그래프의 문제를 해결하기 위해 누락된 링크를 추론하는 방식으로 등장했지만, 주로 블랙박스 모델로 작동합니다. 기존의 링크 예측을 위한 설명 가능성 방법들은 단일 홉 예측을 위한 중요한 트리플이나 경로를 식별하는 데 집중되어 있으며, 복잡한 질의에 직접적으로 적용되지 않습니다. 또한, 현재의 신경-기호 CQA 방식은 특정 질의 구성 요소(atom)가 최종 순위에 기여하는 정도에 대한 투명성이 부족합니다. 이러한 불투명성은 사용자의 신뢰를 저해하고, 디버깅을 어렵게 하며, 도메인 전문가가 지식 그래프의 공백을 식별하거나 질의를 정교화하는 것을 방해합니다.

방법론: CQD-SHAP

본 논문은 협력 게임 이론의 **샤플리 값(Shapley values)**을 사용하여 각 질의 원자(atom)가 특정 정답 엔티티의 순위에 기여하는 정도를 정량화함으로써, 신경-기호 CQA 모델(특히 CQD)의 결과를 설명하는 프레임워크인 CQD-SHAP을 제안합니다.

핵심 정의

1. 플레이어(Players): 복잡한 질의 $Q$의 구성 요소인 원자(atoms)들을 협력 게임의 플레이어로 간주합니다.
2. 연합(Coalitions): 원자들의 부분 집합 $S$는 신경적 접근 방식(링크 예측기를 통한 누락된 링크 추론)을 사용하여 실행되는 반면, 나머지 원자들은 기호적 접근 방식(KG 내의 관찰된 사실에 엄격히 의존)을 사용하여 실행됩니다.
3. 가치 함수(Value Function): 대상 엔티티 $e_i$에 대한 연합 $S$의 가치는 **$\Delta$Rank 관심량(Quantity of Interest, QoI)**으로 정의됩니다. 이는 전체 질의를 순수하게 기호적으로 실행했을 때와 비교하여, 원자 $S$를 신경적으로 실행했을 때 $e_i$의 순위 위치가 얼마나 개선되는지를 측정합니다.
   • 형식적으로: $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$이며, 여기서 $r_i$는 필터링된 설정에서의 엔티티 $e_i$의 순위입니다.
4. 샤플리 값 계산: 특정 원자 $a$의 기여도는 다른 모든 원자들로 구성된 가능한 모든 연합 조합에 대한 해당 원자의 평균 한계 기여도로 계산됩니다. 이는 효율성(모든 원자의 기여도 합이 전체 순위 개선량과 같음)을 포함한 샤플리 공리들을 충족합니다.

실행 세부 사항

• 신경적 실행(Neural Execution): 링크 예측기(예: CQD의 일부)를 사용하여 엔티티에 점수를 할당하며, 이를 통해 불완전한 그래프 상에서 추론을 수행합니다.
• 기호적 실행(Symbolic Execution): 관찰된(불완전한) KG 상에서 그래프 트래버설을 수행하며, 존재하는 사실에는 상수 점수를, 존재하지 않는 사실에는 낮은 점수를 할당합니다.
• 정확한 계산(Exact Computation): 복잡한 질의의 원자 수가 적기 때문에(통상 $\le 4$), 근사치 없이 정확한 샤플리 값을 계산합니다.

주요 기여

1. CQA를 위한 최초의 샤플리 기반 설명: 저자들의 지식에 따르면, 이는 샤플리 값을 사용하여 신경적 복잡 질의 응답 모델을 설명하는 최초의 접근 방식입니다.
2. 원자 수준 설명의 공식적 정의: 본 논문은 링크 예측에서 사용되는 트리플 수준 또는 경로 수준의 설명과 구별되는, 질의 원자 수준에서의 공식적인 설명 프레임워크를 정의합니다.
3. 새로운 메트릭(CQD-SHAP): 특정 원자의 신경적 실행이 타겟 정답의 순위에 얼마나 기여하는지를 기호적 실행과 비교하여 정량화하는 방법을 도입했습니다.
4. 평가 기준의 재정의: 링크 예측의 필요성(Necessary) 및 충분성(Sufficient) 개념을 CQA 영역으로 확장했습니다.
   • 필요성: 가장 중요한 원자를 기호적 실행으로 교체했을 때 정답의 순위가 크게 하락하는 경우( $\Delta$MRR로 측정)를 의미합니다.
   • 충분성: 가장 중요한 원자만을 신경적으로 실행하고 나머지는 기호적으로 실행했을 때, 순수 기호적 베이스라인보다 순위가 유의미하게 개선되는 경우를 의미합니다.

실험 결과

저자들은 FB15k-237, NELL995 및 이들의 더 어려운 변형(+H)에 대해 다양한 질의 유형(투영, 교집합, 합집합)에 걸쳐 CQD-SHAP을 평가했습니다.

• 성능: CQD-SHAP은 필요성 및 충분성 평가 시나리오 모두에서 모든 베이스라인(First, Last, Random, Score-based selection)보다 일관되게 우수한 성능을 보였습니다.
  • 필요성 시나리오에서, CQD-SHAP은 NELL995의 2u 쿼리에 대해 MRR을 최대 45.70% 감소시켰으며, 이는 가장 우수한 베이스라인보다 훨씬 큰 수치입니다.
  • 충분성 시나리오에서, CQD-SHAP은 NELL995+H의 2u 쿼리에 대해 MRR을 최대 58.90% 증가시켰습니다.
• 질의 구조 민감도: 이 방법은 투영(projection) 쿼리에 비해 교집합 쿼리(예: 3i, 4i)에서 더 높은 효과를 보였습니다. 저자들은 이를 t-norm을 사용하는 교집합의 구조적 특성 때문이라고 설명하는데, 즉 하나의 결정적인 브랜치가 강력한 필터 역할을 하는 반면, 투영 쿼리는 대안적인 경로를 갖는 경우가 많기 때문입니다.
• 효율성: 샤플리 값의 NP-hard 특성에도 불구하고, 적은 수의 원자 덕분에 낮은 지연 시간(데이터셋에 따라 쿼리-정답 쌍당 평균 약 30~140ms)으로 정확한 계산이 가능했습니다.
• 통찰: 분석 결과, 가장 중요한 원자가 항상 "누락된 링크"인 것은 아님이 밝혀졌습니다. 어떤 경우에는 임베딩 근접성이나 다른 부분의 신경적 실행으로 인한 노이즈로 인해, KG에 이미 존재하는 사실에 해당하는 원자가 순위의 주요 동인이 될 수 있습니다.

의의 및 주장

본 논문은 CQD-SHAP이 신경-기호 질의 응답을 해석하는 수학적으로 엄밀하고 효과적인 방법을 제공한다고 주장합니다. 샤플리 공리를 만족함으로써, 질의 구성 요소에 대한 공정한 공로 배분을 보장합니다. 저자들은 이 접근 방식이 다음과 같은 도움을 준다고 단언합니다:

• 도메인 전문가가 어떤 질의 부분이 추론된 지식에 크게 의존하는지를 드러냄으로써 지식 그래프의 공백을 식별하도록 돕습니다.
• 어떤 원자가 최종 순위에 가장 큰 영향을 미치는지 보여줌으로써 질의 디버깅을 지원합니다.
• 신경적 예측기가 불완전한 데이터를 어떻게 활용하는지에 대한 투명한 관점을 제공합니다.

저자들은 이것이 샤플리 값을 적용하여 복잡한 질의 응답 결과를 설명하는 최초의 연구임을 명시하며, 기존의 링크 예측 설명 방법의 한계를 넘어선다고 언급했습니다. 또한, 현재는 로컬 설명(단일 정답)에 집중하고 있지만, 향후 글로벌 설명 및 인간이 읽기 쉬운 자연어 생성으로 확장할 계획이라고 밝혔습니다.