(An) orbit-based explainability method for graph neural networks

국문 초록 (Abstract)

현존하는 GNN의 설명 방법론들은 설명 범위에 따라 모델 레벨과 인스턴스 레벨로 분류될 수 있다. 인스턴스 레벨의 설명은 GNN이 각 input data를 가지고 작업을 수행할 때 중요하게 본 노드, 엣지 또는 서브 그래프를 설명으로 제시한다. 이러한 설명은 GNN이 개별 데이터들을 분류할 때 어떠한 패턴을 중요하게 인식하였는지 파악하는데 도움을 준다. 모델 레벨의 설명은 GNN이 각각의 input data가 아닌 전체 데이터들을 특정 클래스로 분류할 때 중요하게 본 노드, 엣지 또는 서브 그래프를 설명으로 제시한다. 이러한 설명은 GNN이 데이터들을 분류할 때 사용한 보편적인 패턴을 분석하는 데 도움을 준다. 이렇듯 두가지 설명 모두 다른 관점에서의 GNN을 설명하는데 도움이 되기 때문에 중요하다. 그러나 두 가지 관점에서의 설명을 모두 제공하는 방법론은 존재하지 않는다.

이러한 한계점을 극복하기 위해 본 연구는 노드 분류 작업에 대해 인스턴스, 모델 레벨의 설명을 모두 제공하는 새로운 GNN 설명 방법론인 O-GNNExplainer를 제시한다. 우리의 방법론은 모티프 단위의 설명을 제공하기 위해 non-isomorphic subgraph들의 집합인 graphlet과 각 graphlet 내부의 구조적으로 구별되는 노드들인 orbit를 설명 단위로 사용한다. 또한 GNN을 embedding-model와 downstream-model로 분리하여 설명하고자한다. O-GNNExplainer는 우선 노드 representation vector들과 각 노드 별 orbit 존재 유무를 활용하여 orbit weight를 학습한다. 이후 downstream-model의 각 클래스 분류에 기여하는 weight를 orbit weight 단위로 분해하여 각 orbit의 기여도들을 모델 레벨의 설명으로 제공한다. 또한 각 노드들의 예측 결과를 orbit weight로 분해함으로써 instance 레벨의 설명 또한 제공할 수 있다.

우리는 synthetic-dataset에서 새롭게 제시한 task를 통해 O-GNNExplainer가 ground-truth motif를 모델 레벨의 설명으로 제시할 수 있는지 검증하였다. 또한 기존의 연구들에서 사용된 평가 기준들을 개선하여 다양한 real, synthetic dataset에서의 실험을 통해 O-GNNExplainer가 baseline method들 보다 높은 성능을 보여주는 것을 확인하였다.

다국어 초록 (Multilingual Abstract)

Graph Neural Networks (GNNs) have achieved state-of-the-art performance on a variety of tasks involving graph data. Due to these impressive performances, numerous studies on GNN explainability have emerged. Existing GNN explainability studies can be categorized into model-level and instance-level methods. Model-level methods provide subgraphs that contribute significantly to the overall behavior of GNNs with respect to specific class labels. In contrast, instance-level methods aim to identify important subgraphs within individual data instances. While both perspectives are invaluable for understanding the behavior of a model, it is more beneficial to offer explanations in a more human-interpretable unit within a unified framework. In this paper, we propose an explanation model, O-GNNExplainer, capable of decomposing the predictions of existing GNNs at both the model-level and instance-level, using the orbit as the unit of explanation. Notably, O-GNNExplainer can decompose the learning results of GNNs into 73 orbit units in predefined graphlets, demonstrating interpretable results in various domains, including biology and social network. In our experiments, O-GNNExplainer consistently outperformed existing baselines in generating explanations across six distinct datasets.

목차 (Table of Contents)

• 1. Introduction 1
• 1.1. Overview of our works 1
• 2. Notation&Background 4
• 2.1. Graph Neural Networks 4
• 2.2. Explanations for GNNs 5
• 2.3. Graphlet&Orbit 9
• 3. Method 11
• 3.1. Problem Definition 11
• 3.2. Overview of O-GNNExplainer 12
• 3.3. Orbit Basis Learning 15
• 3.4. Class-Orbit Score Learning 17
• 4. Experiments 20
• 4.1. Experimental Settings 20
• A. Datasets 20
• B. Evaluation Metrics 22
• 4.2. Experimental Results 24
• A. Results: Orbit Identification Task with Synthetic Dataset 24
• B. Results: Model-level Explanations 26
• C. Instance-level Explanations 28
• 5. Conclusion 34
• References 35
• Appendix 40
• Korean Abstract 48