기술 요약: TreeX - 규칙-그래프 리드아웃을 통한 모델 수준 GNN 설명

문제 제기

그래프 신경망 (GNN) 은 강력한 예측 성능을 달성하지만, 그 의사결정 논리를 이해하는 것은 여전히 어렵습니다. 기존 접근법은 주로 인스턴스 수준 설명에 초점을 맞추어 단일 예측에 책임 있는 특정 노드나 서브그래프를 식별합니다. 그러나 지역적 설명은 증거가 데이터셋 전반에 걸쳐 체계적으로 사용되는지, 모델이 허위 단서 (spurious shortcuts) 에 의존하는지, 또는 여러 개념이 어떻게 클래스 수준의 의사결정 경계를 공동으로 정의하는지 밝히지 못합니다.

현재의 모델 수준 설명기들은 일반적으로 특정 클래스와 관련된 그래프 패턴이나 기호 규칙을 식별하려 시도합니다. 이러한 방법들의 결정적 한계는 규칙을 사후적 (post-hoc) 클래스 설명자로 취급할 뿐 기능적 계산 단위로 다루지 않는다는 점입니다. 그들은 여러 규칙이 어떻게 GNN 의 최종 결정을 공동으로 생성하거나 모델의 원시 예측 로짓 (logits) 을 재구성하는지 설명하지 못합니다. 결과적으로 이들은 테스트 시 규칙 수준의 기여도 분석을 수행하거나 경쟁 클래스의 억제 메커니즘을 설명할 능력이 부족합니다.

방법론: TreeX

저자들은 TreeX를 제안합니다. 이는 설명 대상을 클래스별 규칙 추출에서 규칙 기반 로짓 재구성으로 전환하는 새로운 모델 수준 GNN 설명 프레임워크입니다. TreeX 는 사전 훈련된 GNN 의 리드아웃 (readout) 인터페이스에서 개입하여, 메시지 전달 계층과 분류기 헤드는 고정된 채로 유지하면서 기존 노드-대-그래프 리드아웃을 가중치 규칙-대-그래프 리드아웃으로 대체합니다.

이 방법론은 네 가지 주요 단계로 구성됩니다:

1. 서브트리에서 영감을 받은 개념 마이닝

전역 규칙을 지역 인스턴스에 기반하기 위해 TreeX 는 GNN 의 숨겨진 상태 (hidden states) 에서 서브그래프 개념을 마이닝합니다:

• 지역 마이닝: 그래프 내 노드 임베딩을 클러스터링합니다. 각 클러스터는 구성 노드들의 $l$-홉 수용 영역 (receptive fields) 을 집계하여 지지 서브그래프로 변환됩니다 (서브트리). 이는 개념이 노이즈보다 구조적으로 안정적인 증거를 향하도록 편향을 줍니다.
• 전역 마이닝: 지역 개념 임베딩을 다시 클러스터링하여 전역 개념 은행을 형성합니다. 대표 서브그래프는 (형태와 차수 서명 기반의) 2 단계 사전적 다수 필터를 거친 후 중심-거리 동점자 처리를 통해 선택됩니다.
• 이론적 정당화: 이 논문은 최대 성능을 내는 MPNN(예: GIN) 의 경우, $l$-번째 계층 노드 임베딩이 전체 $l$-홉 서브트리의 "완벽한 루트 지정 트리 표현 (Perfect Rooted Tree Representation)"이라고 주장하며, 서브구조를 표현하기 위해 노드 임베딩을 사용하는 것을 정당화합니다.

2. 신경-기호 규칙 학습

TreeX 는 CNF(Conjunctive Normal Form, 결합 정규형) 구조, 구체적으로 OR-of-CNF 완화를 사용하여 전역 서브그래프 개념 위에 기호 규칙을 학습합니다:

• 클래스별 발견: 규칙은 각 대상 클래스에 대해 원-대-다 (one-vs-rest) 방식으로 초기에 학습됩니다. 긍정 리터럴 ($P[k]$) 과 부정 리터럴 ($\neg P[k]$) 은 전역 개념의 판별력에 따라 인스턴스화됩니다.
• 미분 가능 논리: 계층적 미분 가능 논리 파라미터화가 사용됩니다. 절 (clauses) 은 게이트된 리터럴에 대한 최대값 (Gödel t-conorm) 을 통해 만족되며, 규칙은 절 간 제품 스타일 소프트 AND 를 통해 형성됩니다. 최종 클래스 예측은 후보 규칙에 대한 확률적 합 (noisy-OR) 을 사용합니다.
• 병합: 클래스별 규칙 후보는 통합 공유 규칙 은행으로 병합됩니다. 이 2 단계 설계는 다중 클래스 재구성을 위한 공유 구조를 유지하면서 클래스별 판별 규칙을 발견하도록 보장합니다.

3. 규칙-대-그래프 리드아웃

핵심 혁신은 리드아웃 계층을 재정의하는 것입니다:

• 규칙 임베딩: 규칙 임베딩은 구성 리터럴의 임베딩을 (게이트 활성화로 가중치하여) 집계함으로써 계산됩니다. 부정 리터럴은 해당 긍정 리터럴의 부호화된 임베딩으로 표현됩니다.
• 로짓 재구성: 활성화된 규칙은 학습된 전역 가중치 벡터 $w$로 가중됩니다. 활성화된 규칙 임베딩의 가중 조합은 기본 GNN 의 고정된 분류기 헤드를 통과하여 원시 다중 클래스 로짓 ($\hat{o}_G$) 을 재구성합니다.
• 목적: 모델은 재구성된 로짓과 원래 GNN 의 원시 로짓 간의 평균 제곱 오차 (MSE) 를 최소화하도록 훈련됩니다.

4. 테스트 시 기반 설정 및 분석

테스트 시, TreeX 는 보지 못한 그래프를 공유 개념 공간으로 투영하고 고정된 규칙을 평가하여 인스턴스별 설명을 생성합니다. 이는 다음을 가능하게 합니다:

• 기반 설정 (Grounding): 만족된 리터럴을 구체적인 지역 서브그래프 증거 (긍정 리터럴의 경우) 또는 개념의 부재 (부정 리터럴의 경우) 에 매핑합니다.
• 어블레이션 (Ablation): 규칙의 가중치를 0 으로 설정하고 재구성된 로짓의 변화 ($\Delta_{g,r}$) 를 관찰하여 각 규칙의 기여도를 측정합니다.

주요 기여

1. 새로운 설명 대상: 모델 수준 GNN 설명을 규칙 기반 로짓 재구성으로 공식화하여, 단순한 패턴과 라벨의 연관성을 넘어 원시 예측 로짓의 생성을 설명하는 방향으로 전환합니다.
2. 기호 리드아웃 인터페이스: 기반 설정된 논리 규칙이 계산 단위로 작용하는 규칙-대-그래프 리드아웃을 도입합니다. 활성화된 규칙 임베딩은 집계되어 고정된 분류기를 통과하여 다중 클래스 로짓을 재구성합니다.
3. 기반 설정되고 구성적인 규칙 구축: 연속 임베딩과 구체적인 증거를 위해 서브트리에서 영감을 받은 서브그래프 개념을 마이닝합니다. 이는 OR-of-CNF 규칙을 학습하여 필요한 제약 내에서 대안적 실현을 보존하며, 동일한 규칙 예산 하에서 DNF 스타일 공식보다 더 큰 구조적 표현력을 제공합니다.
4. 기능적이고 충실한 설명: 식별된 핵심 규칙이 예측 클래스를 능동적으로 지원하고 비대상 클래스를 억제하여 단순한 사후적 산물이 아닌 기능적 단위로 작용함을 입증합니다.

실험 결과

TreeX 는 세 가지 합성 (BA-2Motifs, BAMultiShapes, BA-Neg) 과 두 가지 실제 분자 (Mutagenicity, NCI1) 데이터셋에서 평가되었습니다.

• 로짓 충실도: TreeX 는 기본 GNN 의 원시 다중 클래스 로짓을 충실히 재구성하며, 높은 **절대 확률 충실도 (APF)**를 달성합니다 (예: BA-2Motifs 에서 >97%, 실제 데이터셋에서 >75%).
• 규칙 영향: 어블레이션 연구는 상위 활성화 규칙이 일관되게 대상 클래스의 로짓을 증가시키고 비대상 클래스를 억제하여 의사결정 과정에서의 기능적 역할을 확인합니다.
• 설계의 필요성: 어블레이션 실험은 규칙 모듈, 병합 단계, 또는 부정 리터럴을 제거하면 특히 원시 로짓 재구성 측면에서 성능이 크게 저하됨을 확인합니다.
• 효율성 및 비교: 기존 클래스별 규칙 기반 설명기 (LogicXGNN, GLGExplainer, GraphTrail) 와 비교할 때 TreeX 는 경쟁력 있거나 더 나은 **예측 일치도 (PA)**를 달성하면서 최대 20 배 더 빠릅니다. 기존 방법들과 달리 TreeX 는 규칙 가중치, 테스트 시 기반 설정, 로짓 수준 기여도 분석을 제공합니다.

중요성과 주장

이 논문은 TreeX 가 전역적, 테스트 시 인스턴스화 가능, 서브그래프 기반 설명 프레임워크를 제공한다고 주장합니다. 로짓 재구성에 초점을 전환함으로써 TreeX 는 설명 가능성에 대한 더 엄격한 평가를 제공합니다: 규칙은 단순히 기술적인 것이 아니라 의사결정 마진을 능동적으로 형성하는 기능적 단위임이 입증됩니다.

저자들은 TreeX 가 단순한 사후 요약 도구가 아니라 GNN 의 의사결정 논리가 어떻게 재사용 가능한 가중 기호 규칙으로 분해될 수 있는지를 드러내는 메커니즘임을 강조합니다. 이 접근법은 규칙이 예측 클래스를 어떻게 지원하고 경쟁자를 억제하는지 분석할 수 있게 하여, 여러 규칙과 최종 의사결정 경계 간의 상호작용이 불투명했던 현재 모델 수준 해석 가능성의 격차를 해소합니다. 이 프레임워크는 인간이 해석 가능한 개념을 식별하고 이를 기호 규칙으로 구성한 후, 이러한 규칙을 리드아웃 수준 단위로 사용하여 모델 행동을 재구성함으로써 신경 모델을 설명하는 더 넓은 경로를 제시합니다.