GNNExplainer 요약

GNNExplainer

Abstract

GNN : graph구조를 이용하여 input 을 graph를 edge를 통하여 전파시키며 연산을 하는 ? 그런느낌. 그런데 갈수록 그래프가 복잡해짐에 따라서 GNN의 결과에 대한 설명을 하는 것은 아직도 숙제로 남아있음. 그래서 GNNExplainer을 소개한다.

1. GNN기반의 모델이든 그래프 기반의 모델이든 설명할 수 있을만하게 기계학습 작업을 진행한다.
2. GNNExplainer은 그래프에서 중요한 역할을 수행하는 간결한 subgraph과 작은 node features 들의 subset 들을 식별한다.
3. gnnexplainer은 간결하고 일관성있는 전체 클래스 인스턴스에 대한 설명을 제작?제공 할 수 있다.
4. GNN의 (예측과 가능한 하위 그래프 구조 분포) 간의 상호 정보를 최대화하는 최적화 작업을 공식화한다.
5. 인공+real-world 그래프에 대한 실험은 GNNEXplainer가 기존에 존재하던 다른 대채적인 방안보다 설명하는 정확도가 43%가량의 node features같이 중요한 graph 구조를 식별할 수 있음을 알 수 있었다.
6. 의미론적으로 관련된 구조를 시각화하는 능력에서 해석 가능성에 이르기까지 결함이 있는 GNN의 오류에 대한 통찰력을 제공한다.

Introduction

real-world 에서는 사회,정보,화학,생물학 관련 데이터들이 graphs를 통해서 모델링 될 수 있다. 그래프 자체는 강력한 데이터 표현 방법이나, 데이터들 사이에 존재하는 관련성있는 풍부한 정보들을 node feature 정보로 만드는 작업을 하는 과정에서 고전하고 있다. 이러한 문제에서 GNN은 그래프에 최첨단 머신러닝을 적용시켰고, 이웃하는 노드에서 정보를 재귀적으로 포함시키는 능력 때문에 자연스럽게 그래프 구조와 node feature들을 얻을 수 있습니다.

이러한 강점에도 불구하고, GNN은 그들의 예측을 투명도 있게 제공하지 않아서, 사람이 이해하기에는 어려운 부분이 있습니다.

GNN의 예측을 해석해야 하는 이유

1. GNN모델에 대한 신뢰도를 올릴 수 있다
2. 공정성, privaty 에 같은 의사 결정에 중요한 application 의 투명도를 높일 수 있습니다.
3. 모델을 사용하는 실무자들에 대해서 real-world과의 네트워크 모델의 성격, 시스템적 패턴의 오류 같은 것들을 판단하고 이해할 수 있게 해 준다.
4. 기존의 접근들에는 features을 중심으로(관련 있는 feature, high level featuers에 대한 질적으로 좋은 인터프리터들) 의 방식들을 사용했는데 이러한 방식들은 graph 구조에 적용시키기에는 적합하지 않다. 즉 그래프 구조의 GNN에서는 각각의 노드 뿐만이 아니라 노드 사이에 존재하는 관계(간선) 도 GNN의 예측에 대한 설명의 지표로써 활용하여야 한다.

GNNExplainer은 trained GNN과 그 예측 결과를 입력받아서, 그것에 대한 설명으로 small subgraph 와 node features 에 대한 small subset을 제공한다. node classification, link prediction, and graph classification등 graph 를 이용한 여러가지 방면의 모델들에 대하여 평가를 진행할 수 있다. (single, multi instance 에도 동작)

subgraph 를 이용하여 mean-filed에 대한 변화를 근사하고 real-valued 그래프 마스크(gnn 계산에 대한 중요한 subgraph)에 대한 학습으로 최종적으로 node features들에 대하여 중요한부분만 남기고 중요하지 않은 부분은 다 쳐내는 학습을 하게 된다.

의문점

we show that
GNNEXPLAINER accurately identifies the subgraphs/motifs as well as node features that determine
node labels outperforming alternative baseline approaches by up to 43.0% in explanation accuracy

라고 하는데 도대체 어떻게 43.0% 의 explanation accuracy를 측정했을까? exaplanation 에 대한 측정 방법이 따로 존재하는 건가? 어떻게 잘 설명했다는 것을 측정하지?

Related work

non-graph neural network의 경우에는 interpretability를 구하는 방법으로 크게 두가지 방법이 있다.

• 결과에 대한 간단한 프록시 모델의 공식화를 통하여 설명하는 방법( 선형 모델에 있어서의 관계의 유추는 매우 쉽다.) 이에 대한 대해서 locally faithful 한 부분에 대한 근사를 학습하는 방법을 사용한다.
• 결과에 이르기까지에 계산 과정(feature gradient, backpropagation 으로 얼마나 영향을 주는지, counterfactual reasoning(반사실적 추론)) 의 유추를 이용한다.

그런데 이러한 것들의 문제점으로는, 인접행렬(그래프를 이어진 점들끼리 연결 상태를 나타낸 행렬) 이나, 좀 분리되어있는 input들(0값 들이 많은) 그러한 구조의 input들이 들어올 때에는 gradient saturation, 값 손실이 일어날 수 있다. 그래서 그래프 구조로 표현할 수 있는 문제들에 대해서는 기존의 neural network를 통한 접근이 알맞지 않다.

기존에 내가 했던 프로젝트 중 steam game recommend system 에서 각 [사용자x플레이 게임] 의 관계를 좀 더 개선 해 볼 수 있지 않을까?

지금까지 graph 구조에 대한 explaining을 제공하는 방법들을 거의 없었다.

최근의 gnn 모델들은 어텐션을 이용하여 interpretability를 증강시켰다. 하지만 특정 노드에 대한 prediction 만 제공하지 노드 전체적인 값에 대한 prediction 을 제공하는데에는 한계가 있다.

The goal of GNNEXPLAINER is to identify a small set of important
features and pathways that are crucial for prediction

Formulating explanations for graph neural networks

Background on graph neural networks

특정 node 사이의 두 message에 대한 function 을 MSG라고 정의하고 정점 i,j가 존재하면, layer l 에서의 i와 j사이의 메세지는 다음과 같이 구할 수 있다.

여기서 h는 각 node를 표현하고 r은 각 node사이에 존재하는 relation 을 뜻한다.

각각의 노드에서는 그 노드의 이웃(N)들에 의하여 message들이 aggreagate된다(이때 사용하는 aggregation method 을 AGG라고 칭한다).

그다음에 non-linear한 transform 을 통하여

값을 업데이트 해 나가게 된다. 맨 마지막 최후의 값을

로 설정하게 된다.

GNNEXPLAINER: Problem formulation

gnn에서 output값을 계산하기 위해서는 그래프 자체와 associated feature을 고려하여 output에 대한 explain을 위해서는 해당 두 정보만 알고 있으면 된다. 그리고 gnn의 output 의 행태는 subgraph(computation graph) 와 node features 들의 subset이 되게 된다. 여기서 node features 들의 subset은 subgraph 에 존재하는 node에 대한 associated features들이라고 보면 된다.

GNNExplainer

single-instance explanation

정보 이득을 많이 취할 수 있는 쪽으로 움직여야 한다. 이억을 mutual information MI라고 하고 이것을

이러한 방식으로 계산하여 최적의 G_s를 찾는다. 그 후에 최적의 G_s를 찾게 된다면 예측 y를 계산하게 된다.

예를 들어 G_c에 속한 원소중 하나를 제외하고 v_i에 대한 최종 확률을 계산하였을 때 그 예측 값에 대한 확률이 많이 감소된다면 제외한 원소는 v_i 에 대한 좋은 counterfactual explanation 이라고 할 수 있는 것이다.

결국

해당 값을 최소화 하는 것이 목적이다.

이 값에 대한 계산 식은

로 표현된다. 또한 여기서 설명의 복잡도를 줄이기 위하여 G_s의 크기를 K_M으로 제한해 놓는다. 이 말은 G_s의 subgraph 에서 가질 수 있는 노드의 갯수가 최대 K_M이라는 것을 뜻한다. 이것은 다르게 의미하면 G_c에서 K_M개의 노드를 택했을 경우 가장 높은 mutual information(정보 이득이 가장 큰 경우, 분류를 통하여 엔트로피가 작아지게 되면 결국 정보 이득은 커지기 때문이다.)

최적화

G_c 에대한 subgraph G_s는 무수히 많은 종류들이 있다. 그래서 G_s에 대한 fractional adjacency matrix을 구해야 한다. 그리고 위의 절차로 엔트로피가 최소가 되는 값을 구해야 하는데, 이를 구하기 위해서는 neural network 의 복잡성으로 인해서 함수의 볼록성이 성사하지 않는다.(어디가 최적의 값인지 찾기가 힘들다는 뜻이겠지?), 반면, 실험적으로 reularization 을 통하여 이러한 것들을 minimizae하게 되면 높은 질적인 explanation 과 함께 local minimum에 도달할 수 있다. 그리고 위에서 나오게 된 G_S 에다가 masking 행렬을 elementwise multiplication을 통하여 필요한 부분의 정보만 이용하는 방식을 사용할 수 있다.

여기에다가 특정한 클래스들에 대한 예측이나 분류를 원할 경우에는 엔트로피 측정 방법을 교차 엔트로피로 바꾸어 주면 된다.

Joint learning of graph structural and node feature information

어떤 node features이 중요한지에 대해서 알기 위해서 GNNExplainer은 feature selecor F 를 사용한다. (GNN에서는 X_s 를 정의하여서 사용하였다. 이는 G_s에 포함된 node들의 모든 features들을 의미하였었는데 이제는 이중에서도 특정 feature들을 선택하여 사용하겠다는 뜻이다.) 그래서 위에 나와있던 식을

로 바꾸어 줄 수 있다.

binary feature selector 학습

X^F_S를 우리는 X_s에 F 를 elementwise multiplication 을 시행한 결과로 정의할 수 있다. 즉 feature mask 기능을 하는 것이다. 만약에 특징이 중요하면 그 특징을 마스킹해 걸래내었을 때 예측 결과가 큰 폭으로 하락할 것이고 그렇지 않을 경우에는 예측 결과에 변동이 거의 없을 것이다. 그런데 이러한 방법을 쓸 때 어쩌다가 한번씩 중요한 값들을 0 으로 전파하는 일들이 발생할 수 있었고 그걸 방지하기 위해서 몬테-카를로 방법을 사용하여 reparametrization 을 수행한다. 이 수행 방법에 대해서는

의 식을 사용하여 구할 수 있다.

Integrating additional constraints into explanations

추가 속성을 부여하고싶으면 위의 F와 함께 사용한 MI 식에 regulization term 을 추가하여 사용하면 된다. 그 방식중 masking으로 대부분의 방식을 처리한다.

결과적으로 최종 구서하게 된 그래프에 대해서 관련성이 있더라도 끊어진 부분에 대해서는 computation graph 에서 영향을 받는 노드가 될 수 없으므로(masking에 의하여 사라지게 되므로) 특성들이 사라질 수도 있다. 그래서 최종적인 경향은 작은 연결 서브그래프가 되는 경향이 있다.

Multi-instance explanations through graph prototypes

single instance explanation 은 input graph 에 대하여 영량력이 있는 작은 subgraph와 node features 들의 작은 subset으로 구성된다. 그리고 특정한 노드의 subgraph 과 어떻게 전체 클래스의 그래프 구조를 설명하는지에 대한 근거를 제공하는지에 대한 것이 목표이다 이에대한 2가지 단계적 접근이 있다.

1. 주어진 클래스에 대해서 참조 노드를 하나 선택한다.(선택 방법에는 여러가지가 있을 수 있지만 여기의 예시로는 주어진 클래스와 관련 있는 모든 노드들에 대하여 mean embedding을 사용하였다.) 그거에 대하여 관련 G_s을 얻은 후 관련 있는 노드들에 대하여 정렬?할당?한다. 이러한 방법을 single-instance를 통하여 적용한다.
2. 그 노드들에 대한 aggregation 으로 prototype을 만들고 이를 학습한다.