[5주차] 논문리뷰 - GNNExplainer: Generating Explanations for Graph Neural Networks

투빅스XAI 세미나·2021년 5월 19일

XAI

목록 보기

9/10

이번 시간에는 GNNExplainer: Generating Explanations for Graph Neural Networks 를 리뷰해보겠습니다. Graph Neural Networks를 설명할 수 있는 방법을 소개한 대표적인 논문입니다. (논문 흐름대로 리뷰되었으며 Graph에 대해서 공부한적이 없는 초심자를 위해서 작성되었습니다.)

Contents

0. Intro: Machine Learning with Graph

1. GNNExplainer의 이유

2. GNNExplainer Overview

3. GNNEXplainer explanations

4. Experiments & Conclusion

0. Intro : Machine Learning with Graph

그래프를 설명하는 법을 배우기 전에, 기본적으로 machine learning with graph에 대해서 간단히 알아보겠습니다.

Ways to Analyze Networks

Networks 분석은 크게 4가지로 나뉘어집니다.

Node classification -> 주어진 노드 종류 분류
Link Prediction -> 노드간의 연결 여부 예측
Community detection -> 군집 감지
Network Similarity -> (네트워크나 노드간의) 유사도 축정

Application

Network 분석이 사용되는 예시로는 Social Circle Detection, Infrastructure, Knowledge, Link Prediction(reccomendation system), Embedding Nodes, Online Media, Polarization on Twitter, Misinformation, Predicting Virality, Product Adoption, Biomedicine, Side Effect 등이 있었습니다

Recommendation

추천시스템에서 콘텐츠 추천에 graph를 이용한 link prediction이 사용됩니다.

Side Effect

부작용 탐색에 네트워크(그래프)가 사용됩니다. 많은 약을 한꺼번에 섭취했을 때 나타나는 부작용에 대한 예측은 실제로 많은 실험을 해보는 것이 불가능하기 때문에 서로다른 graph를 만들고 link를 예측하는 방법으로 side effect를 탐색합니다.

Structure of Graphs

Motifs

Adjacency Matrix

GNN Overview

1. GNNExplainer의 이유

기존의 XAI 방법론들은 그래프에 적용될 수 없습니다. 기존의 방법들은 그래프 특성상 그래프 구조와 노드 정보를 동시에 고려하지 못하기 때문입니다.

그래프 모델의 예측을 이해할 수 있게 하는 것은 3가지 관점에서 의의가 있습니다.

Trust
GNN모델의 신뢰성을 향상시킵니다.
Transparency
투명성있게 GNN모델을 만들 수 있기 때문에 의사결정이나 프라이버시문제, 보안성 등에 좋습니다.
Understanding
네트워크의 특징을 이해하는데에 도움을 주고 모델에 있는 문제를 식별하게 해줍니다.

2. GNNExplainer Overview

Subgraph

그래프 G가 있고 GNN model( $\Phi$ ) 이 학습 및 예측을 통해서 노드 $v_{i}$ 와 $v_{j}$ 에 대해서 node classification을 진행했습니다.
GNNExplainer를 사용해서 GNN의 예측을 설명합니다.
- $v_{i}$ 의 class 를 basketball로 분류할 때 영향을 준 subgraph를 보여줍니다.
- $v_{j}$ 의 class 를 sailing으로 분류할 때 영향을 준 subgraph를 보여줍니다.
- subgraph가 곧 graph의 explanation이 됩니다.
single-instance & multi-instance explanations
- single : 특정 인스턴스를 예측 -> node label, new link, graph-level label
- multi : 인스턴스 집합을 예측 -> 주어진 class들의 node들을 예측

GNNExplainer

노드 v의 클래스( $\widehat{y}$ )를 예측할 때, GNNExplainer의 목적은 다음과 같습니다.
(A) v노드 예측에 필요한 features set이나 pathway set을 찾는 것 (필요한 잉이웃 찾기)
(B) v노드 예측에 필요한 node feature 찾기 (d-dimension vector 중 필요한 정보만 사용하기)

3. GNNEXplainer explanations

처음부터 끝까지의 과정은 위와 같이 진행됩니다.

3-1. Single-instance explanations

Optimization framework

$\underset{G_{s}}{max} MI(Y,(G_{s},X_{s})) = H(Y) - H(Y|G=G_{s}, X=X_{s})$ (1)

Gs의 MI(mutual information)을 최대화시키는 방법은 위와 같은 엔트로피간의 차이를 이용해서 구합니다.
예를 들어서 그래프에서 노드 i에 대한 node classification을 수행중인데 근처 이웃 노드 j를 제거하면 예측값 y (노드i의) 을 예측 확률을 감소시키는 경우, 노드 j는 노드 i의 node classification을 위해서 중요한 노드라고 판단됩니다. 따라서 이러한 차이를 극대화하는 Gs를 구할 수록 전체 그래프에서 중요한 Gs를 구할 수 있게 됩니다.

$H(Y|G=G_{s}, X=X_{s}) = -E_{Y|G_{s},X_{s}}[\log P_{\Phi }(Y|G=G_{s}, X=X_{s}) ]$ (2)

그리고 결국 MI를 극대화 시키는 식은 조건부 엔트로피 $H(Y|G=G_{s}, X=X_{s})$ 부분을 최소화하는 문제로 바꿀 수 있습니다.

그런데 이때, 그래프 $G_{c}$ 가 수많은 서브그래프를 가지기 때문에 모든 서브그래프에 대해서 구해보는 것은 불가능하고, $G_{c}$ 에 대한 variational approximation of distribution of subgraphs를 사용합니다.

그리고 개별적 $G_{s}$ 의 Entropy 기댓값 대신에 $G_{s}$ 에 대한 기댓값을 사용합니다.

또한 완벽하게 수렴시킬 수는 없고 실험적으로 minimizing 합니다.

결과적으로 trained model이 특정 클래스를 예측을 왜 했는지, 어떻게 했는지 구하기 위해서는 수식 (5)와 같은 cross entropy를 구하게됩니다.

3-2. Joint Learning

Graph structure 와 node feature information의 joint learning을 보겠습니다.
3-1 에서 Single-instance explanations에서는 node feature의 선택에 대해서는 논하지 않았습니다. 따라서 이번에는 feature selector F가 선택한 정보에 대해서만 subgraph의 node feature을 사용하는 과정에 대해서 설명합니다.

수식 (1) -> 수식 (7)

앞서 봤던 (1) 을 (7) 과 같이 고쳐서, F를 같이 학습시킵니다.
중요하지 않은 정보에 대한 weight -> 0 으로 수렴하게 됩니다.
모든 feature에 대한 marginalize
Monte Carlo estimate sampling
reparametrization trick

Overview

4. Experiments & Conclusion

4-1. Setting

GNN을 사용한 node classification 및 graph classification task에 대해서 실험했고, 두 가지 부류의 데이터셋을 사용했습니다.

node classification
- Synthetic datasets : 총 4가지 종류의 인위적인 네트워크를 구성해서 실험
(1) BA-Shapes
(2) BA-Community
(3) Tree-Cycles
(4) Tree-Grid
- ground truth : Motif
graph classification
- Real-world datasets : 실제 네트워크 데이터
(1) Mutag : 분자그래프
(2) Reddit-Binary : Reddit 에 있는 QA 데이터
- ground truth : 미리지정