그래프 신경망(GNN)에 대한 사후 설명 기법은 모델 재학습 없이 블랙박스 그래프 모델의 내부 작동 원리를 경제적으로 해석할 수 있는 솔루션을 제공한다. 다양한 벤치마크에서 많은 GNN 설명 기법들이 최신 기술 수준의 설명 성능을 달성하고 있으나, 이러한 기법들은 본질적인 특성과 설명 능력에 대한 이론적 분석을 거의 제공하지 못하고 있다. 본 연구에서는 GNN 설명의 구조 인지 특성과 특징 간 상호작용 문제를 해결하기 위해, 구조 인지형 셰플리 기반 다조각 설명(Structure-Aware Shapley-based Multipiece Explanation, SAME) 방법을 제안한다. 구체적으로, SAME는 다중 해상도의 구조 인지형 연결된 부분구조를 탐색하기 위해 확장 기반 몬테카를로 트리 탐색(Monte Carlo tree search)을 활용한다. 이후, 서로 다른 단일 부분구조들의 조합을 최적화함으로써 그래프의 특성을 잘 반영하는 설명 결과를 도출한다. 여러 중요한 연결된 부분구조를 탐색하는 과정에서 특징 간 공정한 상호작용을 고려함으로써, SAME가 다항 시간 내에 이론적으로 최적의 셰플리 값을 도출한 설명과 유사한 설명 가능성을 지닌다. 실제 데이터 및 합성 벤치마크에서 실시한 광범위한 실험 결과, SAME는 동일한 테스트 조건 하에서 BBBP에서 12.9%, MUTAG에서 7.01%, Graph-SST2에서 42.3%, Graph-SST5에서 38.9%, BA-2Motifs에서 11.3%, BA-Shapes에서 18.2%의 기존 최고 성능 대비 정밀도(fidelity) 향상을 달성하였다. 코드는 https://github.com/same2023neurips/same 에서 공개되어 있다. 제출 번호: 12143