Meaningful

Meaningful

Greeting :)

[논문리뷰]Heterogeneous Graph Attention Network

Date:     Updated:

카테고리:

Paper: Heterogeneous Graph Attention Network

Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Peng Cui, P. Yu, Yanfang Ye (2019, WWW)

1. Problem Statement

1

1) GNN 모델들에 “Attention Mechanism”이 적용된 적이 없다.

Attention Mechanism은 특히 Transformer기반 모델들을 이용하는 자연어 처리 분야나 딥러닝 분야에서는 많이 사용되고 있다. 하지만, GNN 기반의 모델들에는 적용하려는 시도 자체도 적었고, 특히 Heterogeneous Graph 를 이용하는 분야에는 적용 사례가 없었다.

실제로 세상에 있는 많은 그래프는 Heterogeneous Graph이기 때문에 이 분야에 대한 모델 개선의 필요성이 증가하고 있다.

2) 전통적인 GNN은 Heterogeneous Graph를 처리하는데 부적합하다.

Heterogeneous Graph의 복잡성 때문에 기존의 전통적인 GNN 기반의 모델들은 직접적인 적용이 어렵다.

  • Node Embedding
  • GNN
  • GAN
  • Attetnion Mechanism
  • Heterogeneity of Graph

3. Method

Overview

1

Overview of HAN Structure

Heterogeneous Graph Attention Network(HAN) 모델의 전체적인 구조를 보면 위와 같다. HAN은 크게 두 가지 Step으로 구성되어 있다.

  • Node-Level Attention
  • Semantic-Level Attention

Node-Level Attention은 Heterogeneous graph의 노드들의 타입이 여러개이고 이들의 feature의 차원수가 다를 수 있으므로 차원수를 맞춰주기 위해 선형 변환을 해주고, 그런다음 노드들의 정보를 Meta-path 별로 aggregation한다.

Semantic-Level Attention은 앞서 Meta-path 별로 취합 된 정보들을 다시 하나로 aggregation. 이렇게 나온 최종 임베딩 출력값으로 Loss를 Cross-entropy로 하여 MLP를 수행하여 Prediction을 한다.

Background - Heterogeneous Graph

1

Heterogeneous Graph는 왼쪽 그림을 보면 이해하기 쉽다. 노드들이 총 8개로 구성된 그래프인데, 노드들의 Type이 Actor, Movie, Director로 여러 개인 것을 볼 수 있다. 이처럼 노드 타입이 여러개인 그래프를 Heterogeneous Graph이다. 노드의 타입이 여러 개이면 노드와 노드의 관계의 다양성이 증가한다. 다시 말해, 노드마다 타입이 다르기 때문에 모든 엣지들이 같은 유형의 정보만을 표현하지 않는다.

Ex)
오른쪽 그래프에서 A와 B는 사람 타입의 노드이고, 학회1과 학회2는 학회 이름 타입의 노드이며 NLP는 연구 주제의 노드 타입이다. 즉, 총 3가지의 노드 타입으로 이루어진 그래프이다. A와 B가 무슨 연구 주제를 연구하는지 맞추는 문제를 푼다고 할 때, 만약 NLP라는 노드가 없는 타입 종류가 2개일 때 다른 사람 노드들이 학회1과 학회2에 동시에 투고하는 논문 수가 많아질수록 학습이 잘 되어 ‘A와 B의 연구주제가 같다’ 또는 ‘‘학회1과 학회2는 비슷한 주제를 다룬다’‘라고 판단한다.(기존의 방식)

하지만 NLP라는 노드가 있는 상태에서는 학회1과 학회2가 같은 연구 주제를 다룬다는 정보가 이미 있는 것이다. 즉 학회에 다른 정보가 반영되어 있는 것이기 때문에 A와 B의 유사함을 판단하게 된다.(Meta-path방식)

Background - Meta-Path

1

Meta-Path라는 건 Heterogeneous에서 노드 타입별로 일종의 Path를 정의하는 것이다. (d)번을 보면 그 의미를 쉽게 파악할 수 있다.

  • Movie - Actor - Movie
  • Movie - Director - Movie

이처럼 노드 타입별로 유의미한 정보를 이끌어 낼 수 있는 Path이다. 관계를 가지고 다른 유형의 정보를 추출하는데 용이하게 해준다. 이를 이해하기 쉽게 설명하자면, 영화배우 ‘드웨인 존슨’을 Actor라는 노드에 그가 출연한 영화들을 각각 Movie 노드에 할당해준다. 이 때 우리는 ‘드웨인 존슨’이라는 배우가 어떤 영화에 출연했었는지를 안다면, 그가 출연한 영화들 중 내가 모르는 영화가 있더라고 “액션”적 요소가 많이 있는 영화라고 추측할 수 있다. 다른 유형의 정보를 추출하는데 이처럼 Meta-Path는 유용하다.

Structure - Step1. Node-Level Attention

1

  • Node-Level Attention
    • Input : Node Feature
    • Output : Meta-Path based Node Embedding

1. 선형 변환

먼저 Node-Level Attention이다. 먼저 빨간색 부분에 집중해서 보면 \(h_i\) 는 노드들의 feature이다. 이 feature들은 노드 타입별로 그 사이즈가 다를수도 있다. 즉, 타입별로 Input node feature의 차원 수가 다를 수 있다. 따라서, 선형 변환을 통해 feature들의 크기를 맞춰줘야 한다.

이 선형 변환을 할 때 변환되는 Weight 같은 경우 노드별로 공유되지 않고 각각의 노드 타입별로 다르다. 즉, 노드 타입에 따라서 다른 가중치를 부여하지만, 같은 공간으로 임베딩을 시키려고 Projection하는 것이다.

Due to the heterogeneity of nodes, different types of nodes have different feature spaces. Therefore, for each type of nodes (e.g.,node with type \(\phi_i\) ), we design the type-specific transformation matrix \(M_{\phi_i}\) to project the features of different types of nodes into the same feature space. Unlike [13], the type-specific transformation matrix is based on node-type rather than edge-type.

그래서, Type-Specific Transformation Matrix라는 것을 도입해 다른 타입의 노드들의 Input feature를 크기가 맞게 정제하는 과정, Projection을 한다. 이를 수식화하면 다음과 같다.

\[h^{'}_i = M_{\phi_i} \cdot h_i \;\;\;(Projection)\]

Type-Specific Transformation Matrix 와 Input node feature를 내적하면 Projected node feature가 된다.

  • Type-Specific Transformation Matrix(\(M_{\phi_i}\)): 노드 feature들의 크기를 맞춰주기위해 노드 타입별로 정해주는 행렬.
    • 내적(Inner Product)
    • 선형변환(Linear Transformation)

1

2. Attention Mechanism

Projection을 통해서 feature들의 크기가 맞춰졌으면 이제 Attention을 한다. 여기서 주의할 점은 (2)식이다. Attention을 같은 Meta-path별로 해야한다. 그래서 식에 조건부로서 Meta-path를 의미하는 \(\Phi\) 가 있는 것이다. 이를 좀 더 이해하기 쉽게 보여주자면 다음 그림과 같다.

1

동그라미를 Movie, 세모를 Actor, 네모를 Director라고 했을 때, Move-Actor-Movie와 Movie-Director-Movie의 두 Meta-Path에 대 Subgraph를 만드는 것이다. 이 Subgraph끼리 Attention을 하여 Attention Energy(Score)를 구한다. 이 때 구해진 energy(score)를 논문에서는 Importance 라고 지칭하였다.

  • 이 때 Attention은 Self-Attention이다.

Node- Level Attention에서의 Attention Score를 ‘Importance of meta-path based node pair \((i, j)\)’ 라고 한다. 이는 meta-path마다 다른 Attention vector를 i노드의 Projected feature와 j노드의 Projected vector를 concatenation한 vector와 내적을 한 후 Non-linear function을 먹인것과 같다.

3. Weight of meta-path based node pair

구해진 attention score, Importance를 Softmax 함수를 먹이면 일종의 확률값이 얻어지는데 결론적으로 이것이 Weight(가중치)가된다. 이를 Weight of meta-path based node pair \((i,j)\) 라고 한다. 이를 식으로 나타내면 (3)식과 같다.

4. Aggregation

이제 Weight를 구했으니 meta-path별 노드 쌍의 정보를 취합해주면 된다. 즉, Weight Sum을 해줘야한다. (4)식은 먼저 노드 레벨에서 임베딩을 한 것인데, node \(i\) 에 대한 학습된 임베딩이 \(\mathbf{z}_i^{\Phi}\) 이다.

1

모든 노드 임베딩을 이웃 노드들로부터 Aggregating된다. 여기서 중요한 것은 하나의 single meta-path에 대하여 attention weight \(\alpha_{ij}^{\Phi}\) 가 만들어졌기 때문에, semantic-specific하며 하나의 의미가 있는 정보가 된다.

Heterogeneous graph는 ‘Scale free’ 특성을 가지고 있기 때문에 데이터들의 분산(variance)이 매우 큰 편이다. 이를 해결하기 위해 논문에서는 node-level attention을 Multi-head Attention 으로 구성하였고, 이는 학습 과정을 더 안정화 시켰다. 구체적으로, Node-Level attention을 총 K번 반복하고 Aggregation까지 한 결과들을 모두 Concatenation한 식이 (5)식이다.

Given the meta-path set {\(\Phi_1, \dots , \Phi_P\)}, after feeding node features into node-level attention, we can obtain 𝑃 groups of semantic-specific node embeddings, denoted as {\(Z_1, \dots, Z_P\)}

총 P개의 meta-path가 주어졌을 때, node feature를 node-level attention에 먹인 후 우리는 P group의 semantic-specific한 노드 임베딩을 얻고 그 것이 {\(Z_1, \dots, Z_P\)} 이다. 이것이 Node Level-Attention의 최종 결과이다.

Structure - Step2. Semantic-Level Attention

1

1. Importance

  • Semantic-Level Attention
    • Input : P개의 Node Embedding(Meta-path별 임베딩)
    • Output : Final Embedding \(Z\)

Node-Level Attention의 결과로 얻은 {\(Z_1, \dots, Z_P\)} 있는데, 결론적으로 총 P 개의 meta-path별 노드 임베딩 값을 가진 것이다. 이를 우리는 하나의 값으로 다시 Aggregation 해주어야 한다. 여기서도 Attention Mechanism이 사용된다.(Self-Attention)

논문에서는 이 Aggregation을 위해서 하나의 Semantic-Level Attention을 제시한다. 이는 Specific한 Task를 위해 다른 meta-path별 Importance를 자동으로 학습하고 그 Importance들을 Aggregation한다. Node-Level Attention에서 학습된 P개의 Semantic-Specific한 노드 임베딩 그룹을 Input으로 받아 self-attention을 진행하면 각 meta-path 에 대한 weight들이 학습된다. 이를 수식으로 표현하면 (1)번 식과 같다.

그 결과\(\beta_{\Phi_P}\)가 나오고 이는 P meta-path의 가충치이다. Attention을 하기 위해서는 먼저 Importance를 구해야하고, Importance를 구하려면 비선형 변환(Nonlinear transformation)을 해야한다. 그러면 semantic-specific 임베딩의 Importance를 semantic-level attention vector \(\bf{q}\) 와 변환된 임베딩의 유사도로서 측정한다. 거기에 Importance의 평균을 취한다. 이를 수식으로 표현하면 (2)식이다.

  • Importance

    1. Meta-path별 노드 임베딩을 Attention

    2. 비선형 변환 (tanh, hyperbolic tangent function) ➜ \(\bf{q}\) 와 Transformed Embedding의 유사도 ➜ Importance
    3. Importance에 평균을 취함. ➜ \(w_{\Phi_P}\)

(2)번 식을 다시 한 번 보면 다음과 같다.

1

Semantic-Level Attention에서의 출력값인 Meta-path별 노드 임베딩 \(z_i^{\Phi_P}\) 를 Weight matrix \(W\)와 곱해주고 bias를 더해준다. 이를 비선형 함수인 tanh에 대입하고, \(\bf{q}\)와 곱해주면 유사도로서의 역활을 할 수 있는 importance가 나온다. 이를 다시 평균을 취하는데, 모든 Vertex set(\(V\)) 에 대하여 summation을 해주면 최종 Importance값이 나온다.

2. Output of Attention, Weight

앞에서 구한 Importance값을 이제 Weight로서 사용하기 위해서 확률값으로 바꿔주면 된다. 그렇게 되면 Semantic-Level Attention에서 attention 식(1)이 완료된다.

앞서 구한 Importance값을 확률값으로 바꾸기 위해서는 Step 1) Node-Level Attention에서 했던 것과 같이 softmax함수를 이용하면 된다. 이를 수식화하면 (3)식이고 다음과 같다.

1

Softmax 함수를 통해 확률로 표현한 값을 meta-path의 weight로 만든 것이다.

​

3. Aggregation

이제 1) Semantic-Specific Node Embedding과 2)Meta-path에 대한 Weight가 모두 구해졌으니 최종 목표인 Meta-path에 대한 정보를 Aggregation 할 수 있다. 이는 앞서 1) Semantic-Specific Node Embedding(Output of Node-Level Attention)을 Weighted Sum 해준 것이다. 식(4)와 같다.

1

최종적으로 Meta-path별 노드의 정보를 취합한 것과 모든 Meta-path의 정보를 합한 \(\bf{Z}\) 최종 임베딩 결과가 된다.

Structure - Step3. Prediction

1

마지막으로 최종 임베딩 결과를 이용해서 Prediction을 할 수 있다. 이 최종 임베딩 결과를 specific한 task에 적용할 수 있고, 다른 Loss function을 설계할 수 있다.

Semi-Supervised node classification 논문에서 푸는 주 된 Task이고, Loss는 Cross-Entropy이다.

  • Task: Semi-Supervised Node Classification
  • Loss: Cross-Entropy ➜ minimization

이를 수식화하면 위의 식과 같다. Loss가 Cross-Entropy이고, 모든 Ground-Truth와 예측 사이의 모든 레이블링된 노드에서 Cross-Entropy를 최소화할 수 있다.

1

여기서 C는 Classifier 파라미터이고, Y는 레이블링된 노드, Z는 최종 임베딩 값이다. 레이블링된 데이터를 이용하여 제안된 모델을 Backpropagation을 이용해 최적화 할 수 있고, 노드의 임베딩을 학습할 수 있다.

1

Summary of Structure

​

Summary of Structure

1

먼저 Target Node와 Target Node를 중심으로 하는 이웃노드로부터의 정보를 Aggregation해야 한다. 그러기 위해서 공유되는 Attention Vector(Attention Weight)를 도입해 Target Node와 Source Node의 Attention Score를 계산해준다. Step1의 핵심은 Attention을 이용해 meta-path기반의 노드의 Weight를 만들어 내는것이다.(Attention으로 Importance를 만들고, 이를 SoftMax에 먹이면 Weight가됨)

1

이 과정을 하나의 Meta-Path에서 Target Node에 대한 Source 노드의 정보까지 포함하고 있는 ‘하나의 대표 Node’를 만들기 위함이다. 즉, 이웃 노드들의 정보를 Aggregation하는 노드 임베딩을 진행한 것이다. Aggregation을 위해 Attention Mechanism으로 구한 Weight를 이용해 Weighted Sum을 하면 된다.

  • Result: 대각선 빗금, 20차원의 대표 node

1

이렇게 노드 임베딩을 통해서(Attention을 이용한 노드 임베딩) Step 2로 넘어간다. Step 2에서의 핵심은 Meta-Path에 대한 Weight를 Attention Mechanism을 이용해 만들어 내는 것이다. Step1에서 결과(대각선 빗금)이 Fully connected layer에서 tanh로 비선형 변환 후 만들어진 Importance에 Normalize를 하여 Importance를 만들고, SoftMax 함수를 거치면 Meta-path에 대한 Weight를 만들어 낼 수 있다.

1

이렇게 만들어진 Meta Path의 Weight를 이제 Target Node의 대표노드(Step1의 결과)와 곱해준다.

  • (Step1의 결과인 Node Embedding) x (Step2의 결과인 Meta-Path Weight) = Target Node의 최종 Embedding

Mult-head이므로 Head별로 곱해서 구해준다. Target node의 최종 임베딩의 의미를 분석하자면 각각의 Head가 영화의 장르를 의미한다.

1

이로써 Target 노드의 장르를 말할 수 있는 각각의 head들이 최종적으로 만들어진다. 이를 Concatenation해서 K = 5인 Knn-Classification을 하면 되는데, 이 때 Loss를 Cross-Entropy로 한다. 이로써 Movie Node가 Ground-Truth가 되어 이를 통해 학습한다.

예를 다시 한 번 들어 설명하면, 배우 ‘황정민’을 Target node로, S1을 ‘베테랑’, S2 = ‘남자가 사랑할 때’ 로 두고 임베딩을 진행해서 최종적으로 나온 결과로 Classification을 한다. 이 때 ‘베테랑’의 경우 코미디적 요소가 들어있는 액션 영화이고, ‘남자가 사랑할 때’의 경우 코미디가 섞여있는 로맨스 영화이다. Multi-head를 통해 각각의 ‘액션’, ‘코미디’, ‘로맨스’에 해당하는 값이 나왔다면 배우 ‘황정민’이 출연하는 다른 영화에 댜해서 저 세 개의 장르일 것이라 추축이 가능해 지는 것이다.

4. Experiment & Result

DataSet

1

Data Set으로는 총 3개의 Data Set을 사용했고, 예시로 들었던 영화-배우, 영화-감독에 대한 Data Set이 IMDB이다. 그 밖에 논문 저자와 논문, 논문 저자와 주제의 관계의 Meta-Path가 있는 ACM등이 있다.

(1) Classification

1

기존 모델들은 Homogeneous Graph를 사용해 학습한 결과이고, HAN은 모두 Heterogeneous Graph를 사용했다. 위의 결과는 앞서 말했듯 Classification의 결과이다.

  • \(HAN_{nd}\): Step1인 Node-Level Attention의 과정을 없애고, 각각의 이웃 노드들에 동일한 Importance를 준 모델이다.
  • \(HAN_{sem}\): Step2인 Semantic-Level Attention의 과정을 없애고, 각각의 Meta-Path에 대해 동일한 Importance를 준 것이다.

거의 모든 Training ratio에서 기존의 GNN기반의 모델들에 비해, Heterogeneous Graph Attention Network 모델이 압도적인 성능 향상을 보여준다. 하물며, Original \(HAN\) 모델이 아닌 \(HAN_{nd}\) 나 \(HAN_{sem}\)이 기존의 모델들보다도 성능이 좋은 것을 확인할 수 있다.

또한 기존의 Graph Attention Network보다도 성능이 향상되었다는 것이 의의이다.

(2) Clustering

1

Clustering은 K-means Clustering으로 진행하였다. 전체 과정을 10번씩 반복하였다.

위의 결과에서도 보이듯이, HAN모델들이 기존의 모델들보다 성능이 좋은 것을 볼 수 있다.

  • 기존의 모델들은 Clustering의 결과에서 같은 Class에 대한 분산도 크고, 제대로 Clustering되지 않은 데이터들이 많은 것을 볼 수 있다.
  • 반면, HAN이나 metapath2vec의 경우는 Clustering의 결과 제대로 분류되지 않은 데이터의 수가 비교적 적은 것을 볼 수 있다.

metapath2vec의 경우는 기존에 존재하던 Heterogeneous graph를 분류하는 모델인데, HAN에 비해서 결과 데이터들의 분산(Variance)가 큰 것을 확인할 수 있다. 이는 다른 데이터가 들어왔을 때 잘못 clustering될 확률을 증가시킨다.

반면, HAN 모델은 Attention으로 인해 데이터들이 같은 class의 데이터들이 잘 뭉쳐져 있다.

(3) Parameter Sensitivity

1

가장 좋은 성능을 보여주는

  • Z의 차원수
  • q의 차원수
  • Attention Head K의 갯수

Contribution

I. First attempt to study the heterogeneous graph neural network based on attention mechanism

II. Propose a novel heterogeneous graph attention network (HAN) which includes both of node-level and semantic-level attentions

III. Conduct extensive experiments to evaluate the performance of the proposed model

  • 처음으로 Heterogeneous Graph를 Attention Model에 적용
  • HAN이라는 novel network model을 제시
  • 실 데이터 적용해서 유용성을 입증

Reference

paper
Youtube, 고려대 논문 발표

GR 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)