Beyond Edge Deletion: A Comprehensive Approach to Counterfactual Explanation in Graph Neural Networks

이 논문은 기존 방법론이 주로 간선 삭제에만 국한되었던 그래프 신경망 (GNN) 의 반사실적 설명을 위해, 간선 삽입과 노드 특성 변형을 통합한 경량 기반 프레임워크 'XPlore'를 제안하고, 이를 통해 13 개의 실세계 및 5 개의 합성 벤치마크에서 기존 최첨단 기법 대비 유효성과 충실도를 크게 향상시켰음을 입증합니다.

핵심

1. 문제 상황: "검은 상자"와 "의심스러운 의사"

우리가 사용하는 AI(특히 그래프 신경망) 는 마치 **모든 것을 알고 있지만, 왜 그렇게 판단했는지 말해주지 않는 '검은 상자'**와 같습니다.

• 상황: AI 가 어떤 분자 구조를 보고 "이건 독성이 있다 (거짓)"라고 판단했다고 칩시다.
• 기존 방법의 한계: 과거의 설명 도구들은 AI 에게 "어떤 부분을 지우면 결과가 바뀔까?"라고만 물었습니다. 마치 의사가 환자에게 "약 한 알만 빼면 병이 낫습니다"라고만 말하는 것과 비슷합니다. 하지만 실제로는 약을 추가하거나, 성분을 조금만 바꾸는 것이 더 효과적일 수도 있는데, 기존 도구는 그런 가능성을 찾아주지 못했습니다.

2. 해결책: "XPlore"라는 새로운 탐정

이 논문에서 제안한 XPlore는 그 '검은 상자'를 더 깊이 파헤치는 초능력을 가진 탐정입니다.

🕵️‍♂️ 비유: 레고 조립과 해체

기존 방법은 **레고 블록을 떼어내는 것 (삭제)**만 허용했습니다. 하지만 XPlore 는 다음과 같이 합니다:

1. 블록을 떼어낼 수도 있고 (삭제): 기존에 있던 연결을 끊을 수 있습니다.
2. 새로운 블록을 붙일 수도 있습니다 (추가): 없던 연결을 만들어 새로운 구조를 만들 수 있습니다.
3. 블록의 색이나 재질을 바꿀 수도 있습니다 (속성 변경): 블록 자체의 성질을 미세하게 조절할 수 있습니다.

예시:

• 기존: "이 독성 분자를 치료하려면 이 원자 하나만 없애면 됩니다." (하지만 원자를 없애면 화학적으로 불가능한 분자가 될 수 있음)
• XPlore: "이 원자를 없애는 대신, 새로운 원자를 하나 붙여서 분자 구조를 살짝만 바꿔보세요. 그럼 독성이 사라집니다." (훨씬 더 현실적이고 다양한 해결책을 제시)

3. XPlore 의 핵심 기술 (세 가지 무기)

이 탐정 XPlore 가 어떻게 더 좋은 설명을 찾아내는지 세 가지 무기로 설명해 드립니다.

🔫 무기 1: "자유로운 수정" (Comprehensive Perturbation)

기존 탐정들은 "무엇을 지울까?"만 생각했지만, XPlore 는 **"무엇을 추가하고, 무엇을 고칠까?"**까지 생각합니다.

• 비유: 요리사가 "소금만 덜 넣으면 맛이 달라집니다"라고만 말하는 게 아니라, "설탕을 조금 더 넣거나, 식초를 살짝 뿌리면 훨씬 더 맛있는 요리가 됩니다"라고 제안하는 것과 같습니다. 이렇게 하면 AI 가 왜 그 결론을 내렸는지 훨씬 더 풍부하고 정확한 이유를 알 수 있습니다.

🔍 무기 2: "AI 의 뇌를 직접 읽기" (Gradient-Guided Optimization)

XPlore 는 AI 가 학습한 데이터의 흐름 (기울기) 을 직접 따라가며 가장 작은 변화로 결과를 뒤집는 지점을 찾습니다.

• 비유: 미로에서 길을 찾을 때, 무작위로 돌아다니는 게 아니라 **미로 벽에 숨겨진 나침반 (기울기 정보)**을 보고 가장 짧은 길로 목적지 (결과 변경) 에 도달하는 것입니다. 그래서 불필요한 시행착오 없이 가장 효율적인 설명을 찾아냅니다.

🎯 무기 3: "의미 있는 변화" 측정 (Cosine Similarity)

단순히 "블록 몇 개를 바꿨나?"만 세는 게 아니라, **"바뀐 후의 모양이 원래 모양과 얼마나 의미 있게 닮았나?"**를 측정합니다.

• 비유: 집 리모델링을 할 때, 벽을 무작정 부수고 새 벽을 세우는 것 (GED, 그래프 편집 거리) 만 중요한 게 아니라, **새 집이 원래 집의 '분위기'와 '구조'를 얼마나 잘 유지하면서 변신했는지 (코사인 유사도)**를 중요하게 봅니다. 이렇게 하면 AI 가 엉뚱한 (현실과 동떨어진) 결과를 만들어내는 실수를 줄여줍니다.

4. 실제 성과: 왜 이것이 중요한가?

이 논문은 13 개의 실제 데이터셋 (분자, 소셜 네트워크 등) 과 5 개의 가짜 데이터셋으로 실험을 했습니다. 결과는 놀라웠습니다.

• 정확도 향상: 기존 방법들보다 최대 56% 더 정확하게 "결과를 바꾸는 이유"를 찾아냈습니다.
• 신뢰도: AI 가 내린 결론이 왜 틀렸는지, 혹은 왜 맞았는지에 대한 설명이 훨씬 더 신뢰할 수 있고 (Faithful) 간결해졌습니다.
• 속도: 이렇게 많은 일을 하면서도, 계산 속도는 기존 방법들과 비슷하게 빠릅니다.

5. 결론: "단순한 삭제"를 넘어선 진보

이 논문의 핵심 메시지는 **"AI 의 결정을 설명할 때, 무조건 지우는 것만으로는 부족하다"**는 것입니다.

XPlore 는 지우기도 하고, 추가하기도 하고, 수정하기도 하는 종합적인 접근법을 통해, AI 가 왜 그런 판단을 내렸는지 인간이 이해할 수 있는 가장 자연스럽고 정확한 이유를 찾아냅니다. 이는 의료 (약물 개발), 금융 (사기 탐지) 등 실수하면 큰일이 나는 분야에서 AI 를 더 신뢰하고 사용할 수 있게 해주는 중요한 기술입니다.

한 줄 요약:

"기존에는 AI 의 실수를 고치기 위해 '무언가를 지우는 것'만 생각했다면, XPlore 는 '무엇을 추가하고 고쳐야 할지'까지 찾아내어 AI 의 마음을 더 정확하게 읽어냅니다."

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

그래프 신경망 (GNN) 은 분자 생물학, 소셜 네트워크 분석 등 다양한 분야에서 널리 사용되고 있지만, 그 '블랙박스' 특성으로 인해 해석 가능성과 신뢰성이 부족합니다. 특히 분자 독성 예측, 신약 개발, 금융 사기 탐지 등 고위험 분야에서는 투명한 설명이 필수적입니다.

기존의 반사실적 설명 (Counterfactual Explanation, CF) 기법들은 주로 입력 그래프의 엣지 삭제 (Edge Deletion) 에만 초점을 맞추는 경향이 있었습니다. 이는 다음과 같은 한계를 가집니다:

• 검색 공간의 제한: 엣지 삭제만으로는 모델의 예측을 반전시키는 데 필요한 최소한의 변경을 찾지 못할 수 있음 (예: 엣지 추가나 노드 속성 변경이 필요한 경우).
• 분포 외 (Out-of-Distribution, OOD) 문제: 단순히 엣지를 제거하여 생성된 반사실적 예시가 실제 데이터 분포에서 벗어난 비현실적인 구조를 가질 수 있으며, 이는 모델의 예측을 왜곡할 수 있음.
• 의미론적 일관성 부족: 구조적 변경만 고려할 때 생성된 그래프가 원래 그래프의 의미 (시맨틱) 를 유지하지 못할 수 있음.

2. 제안 방법론: XPlore (Methodology)

저자들은 기존 프레임워크 (Lucic et al., 2022) 를 확장하여 XPlore라는 새로운 기법을 제안했습니다. XPlore 는 엣지 삭제뿐만 아니라 엣지 추가 (Edge Insertion) 와 노드 특징 (Node Feature) 변경을 통합적으로 수행하는 통합적인 그라디언트 기반 프레임워크입니다.

핵심 기술적 요소:

1. 통합된 그라디언트 기반 최적화:

   • 엣지 조작: 기존에는 존재하는 엣지를 제거하는 방식이었으나, XPlore 는 엣지 추가를 가능하게 합니다. 이를 위해 인접 행렬 $A$와 페러터베이션 행렬 $P$의 역할을 뒤바꾸어, 초기에는 완전 연결 그래프를 가정하고 불필요한 엣지를 제거하거나 새로운 엣지를 추가하는 방식으로 최적화합니다.
   • 노드 특징 조작: 노드 특징 벡터에 대해 두 가지 모드를 지원합니다.
     • 게이팅 (Gating): 특정 특징을 유지하거나 제거하는 이진 마스크 적용.
     • 자유로운 조정 (Freedom): 특징 값을 그라디언트에 따라 연속적으로 증가/감소시킴.
   • 이는 모델의 예측을 반전시키는 데 엣지 삭제만으로는 불가능했던 경우 (예: 특정 화학 결합 추가 필요) 에도 유효한 설명을 생성할 수 있게 합니다.

2. 손실 함수 (Loss Function) 설계:

   • 예측 손실 ($L_{pred}$): 오라클 (GNN) 의 예측이 반전되도록 유도.
   • 거리 손실 ($L_{dist}$): 원본 그래프 $G$와 반사실적 그래프 $G'$ 간의 구조적 및 특징적 차이를 최소화.
   • 의미론적 유사성 (Cosine Similarity): 기존 거리 기반 지표 (GED 등) 의 한계를 보완하기 위해, 학습된 그래프 임베딩 간의 코사인 유사성을 도입하여 생성된 반사실적 예시가 원래 데이터 분포와 의미론적으로 얼마나 일치하는지 정량화합니다.

3. 알고리즘 흐름:

   • 입력 그래프 $G$와 훈련된 GNN 오라클 $\Phi$를 받음.
   • 인접 행렬과 노드 특징에 대한 페러터베이션 행렬을 초기화 (가우시안 노이즈 추가 등).
   • 그라디언트 하강법을 통해 예측 손실과 거리 손실을 동시에 최소화하는 방향으로 행렬을 업데이트.
   • 예측이 반전된 가장 가까운 (최소 변경) 그래프를 반사실적 예시로 반환.

3. 주요 기여 (Key Contributions)

1. 포괄적인 입력 페러터베이션: 엣지 추가, 삭제, 노드 특징 변경을 모두 지원하여 GNN 설명의 검색 공간을 대폭 확장했습니다. 이는 엣지 삭제만으로는 표현할 수 없는 richer counterfactual motifs 를 발견하게 합니다.
2. 그라디언트 유도 최적화: 오라클의 내부 손실 그라디언스를 직접 활용하여, 오라클의 결정 경계와 일관된 지역적으로 최소 (locally minimal) 인 페러터베이션을 보장합니다.
3. OOD 현상 완화: 엣지 추가와 특징 변경을 통해 분포 외 (OOD) 인공물을 줄이고, 코사인 유사성 지표를 도입하여 구조적 변경과 의미론적 충실도 (Fidelity) 를 동시에 평가합니다.
4. 강력한 실증적 성능: 13 개의 실세계 데이터셋과 5 개의 합성 데이터셋에서 기존 최첨단 (SoTA) 방법론들을 압도하는 성능을 입증했습니다.

4. 실험 결과 (Results)

• 유효성 (Validity): 제안된 XPlore 는 18 개 데이터셋 중 17 개에서 유효성 (예측 반전 성공률) 이 가장 높았습니다. 평균적으로 기존 2 위 방법론 대비 +56.3% 의 유효성 향상을 보였습니다.
• 충실도 (Fidelity): 생성된 반사실적 예시가 원본의 의미와 얼마나 일치하는지 측정하는 지표에서도 52.8% 향상되었습니다.
• OOD 및 의미론적 일관성: GED(그래프 편집 거리) 가 유사한 수준임에도 불구하고, XPlore 는 다른 방법론들보다 높은 코사인 유사성 (Cosine Similarity) 을 보여주었습니다. 이는 XPlore 가 생성한 그래프가 단순히 구조만 변한 것이 아니라, 목표 클래스의 분포 내에 의미 있게 위치함을 의미합니다.
• 노드 단위 설명: 노드 분류 작업에서도 기존 방법론 (CF-GNNExpl) 대비 평균 +62.30% 의 유효성 향상을 기록하며, 노드 수준의 미세한 특징 조작 능력을 입증했습니다.
• 효율성: 추가적인 학습이나 무거운 생성 모델 없이, 그라디언트 기반 최적화만으로 작동하여 SoTA 방법론들과 경쟁력 있는 실행 시간을 유지합니다.

5. 의의 및 결론 (Significance)

이 논문은 GNN 해석 가능성 분야에서 "엣지 삭제"라는 제한된 패러다임을 넘어선 첫 번째 포괄적인 접근법을 제시했다는 점에서 의의가 큽니다.

• 실용적 가치: 분자 구조 설계나 복잡한 네트워크 분석에서 단순히 "무엇을 지워야 하는가"가 아니라 "무엇을 추가하거나 어떻게 변형해야 하는가"에 대한 실질적인 통찰을 제공합니다.
• 신뢰성 향상: OOD 문제를 완화하고 의미론적 일관성을 높임으로써, 생성된 설명이 실제 도메인 지식 (예: 화학적 결합 규칙) 과 더 잘 부합하도록 하여 의사결정자의 신뢰를 높입니다.
• 미래 방향: 오라클의 표현력 부족으로 인한 OOD 문제를 완전히 해결하기 위해, 더 강력한 오라클 (예: 확산 모델 기반) 과의 결합이나 손실 함수의 정교화를 통해 향후 연구가 진행될 수 있음을 시사합니다.

요약하자면, XPlore는 GNN 의 블랙박스 문제를 해결하기 위해 구조적 (엣지) 과 속성적 (노드 특징) 변경을 통합적으로 최적화하는 강력한 도구로, 더 정확하고 해석 가능하며 신뢰할 수 있는 AI 시스템 구축에 기여합니다.