기술 요약: 귀납적 설명에서 SGC 노드 분류를 위한 전역 논리 규칙으로

문제 정의

그래프 신경망(GNN)은 노드 분류 작업의 표준이 되었으나, 이들의 예측을 설명하는 것은 여전히 큰 과제로 남아 있다. LogicXGNN과 같은 최근의 논리 기반 접근 방식은 설명적 서브그래프로부터 전역 논리 규칙을 도출하지만, 이러한 방법들은 종종 구조적 구성 요소(예: Weisfeiler–Lehman 해시)와 임베딩 이진화에 의존하며, 이는 개별 노드에 특화된 중복된 구조적 정보를 도입할 수 있다. 이러한 중복성은 추출된 규칙의 일반성을 제한할 수 있다. 또한, 노드 수준 작업을 위한 기존의 규칙 기반 전역 설명은 상대적으로 미개척 분야이며, 현재 프레임워크에서 사용되는 술어(predicates)는 노드 수준에서의 형식적 충분성 보장이 부족한 경우가 많다.

저자들은 Simple Graph Convolution(SGC)이 규칙 기반 설명을 위한 자연스러운 대상임을 식별하였다. SGC는 메시지 전달 레이어 사이의 비선형성을 제거하여, 변환 과정을 고정된 특징 전파에 적용되는 단일 선형 분류기로 압축한다. 결과적으로 Slass, SGC 로짓(logits)은 노드 특징들의 선형 함수가 되며, 이 속성은 형식적 설명을 효율적으로 계산할 수 있게 한다.

방법론: AXSGC

본 논문은 최소 abductive 설명(abductive explanations)을 중간 표현으로 사용하여 전역 논리 규칙을 도출하는 3단계 논리 기반 프레임워크인 AXSGC(Abduction-based Explanations for SGC)를 제안한다.

1. 노드-특징 Abductive 설명 (NF-AXps)

첫 번째 단계는 각 노드의 예측 클래스를 유지하기에 충분한 노드-특징 쌍의 최소 집합을 계산한다.

• 형식화: Abductive Explanation (AXp)은 입력 특징 할당의 최소 부분 집합으로 정의되며, 이 집합이 고정될 때 나머지 입력값에 관계없이 모델의 출력이 변하지 않음을 보장한다.
• SGC 적응: SGC를 위해, 분류 규칙은 $K$-hop 수용 영역(receptive field) 내의 노드-특징 쌍에 대한 선형 부등식 시스템으로 재구성된다. 클래스 $c$에 대한 점수는 이러한 쌍들의 선형 결합이다.
• 계산: 저자들은 **Node-Feature AXp (NF-AXp)**를 현재 존재하는 노드-특징 쌍 $(u, j)$ (여기서 특징 $j$가 노드 $u$에서 활성화됨)의 최소 부분 집합으로 정의한다. 이는 나머지 특징들이 최악의 경우로 할당되더라도 예측 클래스와 다른 경쟁 클래스 간의 마진(margin)을 유지하도록 한다.
• 알고리즘: 탐욕적 삭제(greedy deletion) 절차가 사용된다. 수용 영역 내의 모든 활성 노드-특징 쌍 전체 집합에서 시작하여, 최악의 경우 마진 조건이 여전히 성립하는 경우 해당 쌍을 반복적으로 제거한다. 이 과정은 다항 시간 내에 실행되며, 구체적으로 $O((C-1)|C_v|^2)$이다 (여기서 $C$는 클래스 수, $|C_v|$는 후보 집합의 크기이다).

2. 거리 인덱스 술어를 통한 추상화

두 번째 단계는 노드별 NF-AXp를 전역 명제 표현으로 집계한다.

• 술어 정의: 그래프 전반에 걸쳐 일반화하기 위해, 구체적인 노드 식별자는 **거리 인덱스 술어(distance-indexed predicates)**로 대체된다. 특징 $j$와 홉 거리 $k$에 대해, 정확히 $k$ 홉 떨어진 적어도 하나의 노드를 통해 특징 $j$가 NF-AXp에 나타나면 술어 $P_{k,j}(v)$는 참이 된다.
• 설명 행렬: 이러한 술어들은 불리언 행렬 $M$을 형성하며, 여기서 행은 노드를 나타내고 열은 특정 특징-홉 조합이 각각의 NF-AXp에 존재하는지 여부를 나타낸다. 이 추상화는 기여의 거리는 보존하면서 특정 이웃의 정체성은 버림으로써, 구조적으로 유사한 노드들이 술어를 공유할 수 있게 한다.

3. 전역 규칙 추출

세 번째 단계는 설명 행렬에서 전역 논리 규칙을 추출한다.

• 의사결정 나무 학습: 행렬 $M$에 대해 SGC 예측($c^*(v)$)을 타겟 레이블로 사용하여 얕은 다중 클래스 의사결정 나무를 학습시킨다. 결정적으로, 감독 신호(supervision signal)는 ground-truth 데이터셋 레이블이 아닌 SGC 자체의 예측이다.
• 규칙 도출: 전역 규칙은 트리의 루트에서 리프까지의 경로로부터 직접 읽어낸다. 각 경로는 거리 인indexed 술어들의 결합(DNF 규칙)에 해당한다. 이 경로들의 집합을 클래스별로 그룹화하면 최종 전역 규칙 집합이 형성된다.
• 충실도(Fidelity) 지표: 규칙의 품질은 추출된 규칙이 SGC 예측을 재현하는 테스트 노드의 비율인 **충실도(fidelity)**로 측정된다. 이는 규칙 추출기의 성능을 기저 분류기의 정확도로부터 분리한다.

주요 기여

1. 노드 수준에서의 형식적 충분성: 휴리스틱한 서브그래프 선택에 의존하는 이전 방법들과 달리, AXSGC는 SGC 예측에 대해 형식적으로 인증된 충분성과 무잉여성(irredundancy)을 갖는 NF-AXp를 계산한다.
2. 다항 시간 계산: SGC의 선형성을 활용함으로써, 이 프레임워크는 일반적인 GNN에 필요한 조합 탐색을 피하고 다항 시간 내에 최소 설명을 계산한다.
3. 조밀한 전역 규칙: 이 방법은 원래 모델에 높은 충실도를 유지하면서 작은 규모의 전역 논리 규칙 세트를 생성한다. 거리 인덱스 술어를 통한 추상화는 중복된 노드별 설명을 간결한 전역 패턴으로 효과적으로 압축한다.
4. 경험적 검증: 프레임워크는 BAShapes, Cora, Citeseer, PubMed의 네 가지 벤치마크 데이터셋에 대해 LogicXGNN과 비교하여 평가된다.

실험 결과

실험 결과, AXSGC는 충실도와 간결성 모두에서 LogicXGNN보다 우수한 성능을 보였다:

• 충실도(Fidelity): AXSGC는 SGC 모델에 대해 일관되게 더 높은 충실도를 달성했다. 예를 들어, PubMed 데이터셋에서 AXSGC는 99.9%의 충실도를 달성한 반면 LogicXGNN은 **69.7%**를 기록했다. Cora에서는 90.7% 대 **78.6%**를 기록했다.
• 규칙 수: AXSGC는 현저히 적은 수의 규칙을 추출한다. Citeseer에서 AXSGC는 72개의 규칙을 사용하여 (83.8% 적음) LogicXGNN의 445개와 대비되었다. PubMed에서는 31개 대 153개를 기록했다.
• 커버리지(Coverage): AXSGC가 추출한 규칙은 더 집중되어 있다. 상위 10개 규칙이 차지하는 데이터셋의 비율은 LogicXGNN(53.4%)에 비해 훨씬 높다 (예: PubMed의 경우 98.8%).
• 규칙 길이: PubMed와 같은 큰 데이터셋에서 AXSGC는 LogicXGNN(평균 7.62개 조건)에 비해 더 짧은 규칙(평균 4.21개 조건)을 생성한다.

의의 및 주장

본 논문은 AXSGC가 노드 분류를 위한 국소적(local), 형식적으로 인증된 설명과 전역적(global), 해석 가능한 규칙 사이의 간극을 메운다고 주장한다. SGC의 선형성을 활용함으로써, 이 방법은 이전의 논리 기반 접근 방식에서 발견되는 중복성과 형식적 보장의 결여를 피하는 엄격한 설명의 토대를 제공한다.

저자들은 자신들의 방법이 높은 충실도를 유지하면서도 조밀한 전역 규칙을 생성한다고 명시한다. 그들은 AXSGC를 노드별로 인증된 충분성과 경험적으로 충실하며 모델에 부합하는 전역 규칙을 제공함으로써, 그래프 학습에서의 신뢰할 수 있는 AI를 향한 단계로 포지셔닝한다. 논문은 현재 작업이 SGC를 대상으로 하지만, 증류(distillation) 단계를 통해 이 접근 방식이 다른 GNN 아키텍처로 이론적으로 확장될 수 있음을 언급하였으나, 이를 현재의 기여가 아닌 향후 과제로 식별하였다.