[논문리뷰] Heterogeneous Graph Attention Network

태환·2023년 11월 30일

Paper

Paper Review

목록 보기

8/15

📌 Heterogeneous Graph Attention Network

📖 ABSTRACT

저자는 그래프 신경망이 딥러닝을 기반으로 우수한 성능을 보이는 그래프 표현 기술이지만, heterogeneous graph를 위한 그래프 신경망이 아직 고려되지 않았음을 말한다.

본 논문은 당시 딥러닝에서 가장 흥미로운 발전 중 하나인 attention mechanism을 기반으로한 새로운 heterogeneous graph neural network를 제안한다.

제안된 모델은 세 가지 실제 heterogeneous graph에서 기존 SOTA 모델에 비해 우수한 성능을 보이는데 더불어 그래프 분석에 대한 잠재적으로 좋은 해석성을 보인다.

📖 PRELIMINARY

Heterogeneous Graph

heterogeneous graph는 이질적인 특성을 갖는 그래프로 다양한 유형의 노드와 엣지를 포함한다.

예를 들어 위 그림의 heterogeneous graph는 배우 노드 $a_1, a_2, a_3$ 와 영화 노드 $m_1, m_2, m_3$ 그리고 감독 노드 $d_1, d_2$ 를 갖으며, 이러한 객체들은 meta-path라 불리는 다양한 의미 경로를 통해 연결될 수 있다.

Meta-Path

두 영화는 여러 meat-path를 통해 연결될 수 있다.

예를 들어 위 그림의 첫 번째와 같이 <영화-배우-영화>의 형태로 연결될 수 있으며,
두 번째와 같이 <영화-감독-영화>의 형태로도 연결될 수 있다.

<영화-배우-영화>는 두 영화가 공동으로 출연한 배우로 인해 연결성을 지니게 되며,
<영화-감독-영화>는 두 영화가 동일한 감독으로 인해 연결성을 갖게 된다.

그래프에 meta-path가 있으면 각 노드는 다양한 구조 정보와 풍부한 의미를 나타낼 수 있는 meta-path 기반 이웃의 집합이 존재하게 된다.

Meta-Path based Neighbors

heterogeneous graph에서 노드 $i$ 의 mata-path 기반 이웃 $N^Φ_i$ 는 노드 $i$ 와 meta-path $Φ$ 를 통해 연결된 노드의 집합으로 정의된다.

heterogeneous graph를 정의할 때 보인 그림을 예로 들어,
meta-path <영화-배우-영화>가 주어졌을 때 $m_1$ 의 meta-path 기반 이웃은 $m_1, m_2, m_3$ 를 포함하며,
meta-path <영화-감독-영화>가 주어졌을 때 $m_1$ 의 meta-path 기반 이웃은
$m_1, m_2$ 를 포함한다.

📖 INTRODUCTION

본 논문은 hierarchical attention을 기반으로한 heterogeneous 그래프 신경망을 제안한다.
해당 신경망은 node-level attention과 semantic-level attention, 총 2번의 attention 과정을 포함한다.
attention mechanism은 GAN 논문 리뷰를 참고하면 이해하는데 도움이 될 것이다.

node-level attention

node-level attention은 노드와 해당 노드의 meta-path 기반 이웃 간의 중요도를 학습하는 것을 목표로한다.

예를 들어 meta-path <영화-감독-영화>가 주어졌을 때,
영화 <터미네이터>는 <제임스 카메론> 감독을 통해 <타이타닉>및 <터미네이터2>와 연결되어있을 것이다.

이러한 그래프에서 <터미네이터>의 장르를 과학 소설 영화로 잘 식별하기 위해 각 meta-path 이웃 노드들 마다의 가중치를 부여하는 것이 node-level attention 과정이며, 모델은 로맨스 장로인 <타이타닉>보다 과학 소설 장르인 <터미네이터2>에 더 많은 중요도를 부여하도록 학습된다.

semantic-level attention

semantic-level attention은 서로 다른 meta-path의 중요성을 학습하는 것을 목표로한다.

예를 들어 <터미네이터>는 meta-path <영화-배우-영화>를 통해 <터미네이터2>와 연결될 수 있다.
또한 <터미네이터>는 meta-path <영화-연도-영화>를 통해 1984년 같은 연도에 개봉한 영화 <버디>와 연결될 수 있다.

이 중 <터미네티어> 영화의 장르를 식별할 때 <영화-배우-영화>가 <영화-연도-영화>보다 더 중요한 역할을 하는 경우가 일반적이다.

따라서 meta-path를 동등하게 취급하는 것은 비현실적이며, 이는 일부 유용한 meta-path에서 제공되는 의미 정보를 약화시킬 수 있기 때문에 semantic-level attention의 필요성을 주장한다.

📖 THE PROPOSED MODEL

본 논문은 heterogeneous graph에 대한 새로운 semi-supervised graph neural network를 소개한다.
다음 그림은 HAN의 전체 구조를 시각적으로 보여준다.

모델은 우선 node-level attention을 수행해 meta-path 기반 이웃의 가중치를 학습하고, 이를 집계하여 의미별 노드 임베딩을 얻는다.
이후에는 semantic-level attention을 통해 meta-path 간의 차이를 구별하고, 특정 작업에 대한 최적의 가중 조합으로 의미별 노드 임베딩을 얻는다.

Node-level attention

노드의 이질성으로 인해 다양한 유형의 노드가 다른 특징 공간을 갖는다.
따라서 서로 다른 유형의 노드의 특징을 동일한 특징 공간으로 투영하기 위해 유형별 변환 행렬 $M_{∅𝑖}$ 를 설계한다.
여기서 유형별 변환 행렬 $M_{∅𝑖}$ 은 엣지 유형이 아닌 노드 유형을 기반으로 한다.
투영 과정은 다음과 같이 나타낼 수 있다.

이후에는 self-attention을 활용하여 다양한 종류의 노드 간의 가중치를 학습한다.
meta-path 기반 노드 쌍 $(i, j)$ 의 중요성은 다음과 같이 정의할 수 있다.

여기서 $att_{node}$ 는 node-level attention을 수행하는 딥 뉴럴 네트워크를 나타내며, meta-path $∅$ 가 주어진 경우, $att_{node}$ 는 모든 meta-path기반 노드 쌍에 대해 공유된다.

추가로 노드 $i$ 에서 노드 $j$ 로의 중요성과 노드 $j$ 에서 노드 $i$ 로의 중요성이 다를 수 있다.
이는 node-level attention이 heterogeneous graph의 중요한 특성인 비대칭성을 보존할 수 있음을 보인다.

그 후 모델에 구조적 정보를 주입하기 위해 masked attention을 통해 구조적 정보를 삽입한다.

meta-path $∅$ 에 따른 노드 쌍의 중요성을 얻은 후에는 이를 소프트맥스 함수를 사용하여 정규화하여 가중 계수 $a^∅_{ij}$ 를 얻는다.

위 식에서 볼 수 있듯이 각 노드는 서로 다른 이웃을 가지고 있기 때문에 정규화 항이 다를 수 있으며 이는 비대칭성의 원인이 된다.

노드 $i$ 의 meta-path 기반 임베딩은 이웃의 투영된 특징과 그에 따른 가중 계수에 의해 집계된다.

heterogeneous graph는 규모가 크다는 특성을 가지고 있어 그래프 데이터의 분산이 매우 높다.
이를 해결하기 위해 node-level attention을 다중 헤드 어텐션으로 확장하여 훈련 프로세스를 안정적으로 만든다.
즉, node-level attentiondmf $K$ 번 반복하고 학습된 임베딩을 의미별 특정 임베딩으로 연결한다.

meta-path 집합 { $∅_1. . . .\, ∅_P$ }를 노드 특징에 적용하여 node-level attention을 수행한 후, $P$ 개의 의미별 노드 임베딩 그룹을 얻을 수 있으며 이는 { $Z_{∅_1}, . . .\, Z_{∅_P}$ }로 표기한다.

위 과정을 그림으로 표현하면 (a) Nodel-level Aggregating 부분의 그림과 같다.

다음은 아래의 그림 (b) Semantic-level Aggregating 부분을 설명한다.

Semantic-level Attention

의미별로 나눠진 노드 임베딩은 노드를 한 측면에서만 반영할 수 있기 때문에 보다 포괄적인 노드 임베딩을 학습하기 위해서는 meta-path가 나타내는 여러 의미를 융합해야한다.
본 논문은 특정 작업을 위해 다양한 meta-path의 중요성을 자동으로 학습하는 새로운 semantic-level attention을 제안한다.

node-level attention에서 학습한 $P$ 개의 의미별 특정 노드 임베딩을 입력으로 받아 각 meta-path의 학습된 가중치는 다음과 같이 나타낼 수 있다.

각 meta-path의 중요성을 학습하기 위해 먼저 의미별 특정 임베딩을 비선형 변환을 통해 변환한다.
그런 다음 변환된 임베딩의 중요성을 semantic-level attention 벡터 $q$ 와의 유사성으로 측정한다.
마지막으로 각 의미별 특정 노드 임베딩의 중요성을 평균화하여 각 meta-path의 중요성을 나타낸다.
수식으로 표현하면 다음과 같다.

위 수식을 통해 각 meta-path의 중요성을 얻은 후, softmax 함수를 사용하여 정규화한다.
meta-path $∅_i$ 의 가중치인 $β_{∅_i}$ 의 수식은 다음과 같이 표현된다.

위의 과정을 통해 학습한 가중치를 계수로 사용하여 의미별 특정 임베딩을 융합하면 최종 임베딩 $Z$ 를 얻을 수 있다.

최종 임베딩을 semi-supervised node classification 작업에 적용할 경우, 레이블이 지정된 모든 노드를 대상으로 예측과 실제 간에 Cross-Entropy를 최소화하는 손실 함수를 다음과 같이 설계할 수 있다.

앞서 설명한 모델 HAN의 전반적인 알고리즘은 다음과 같다.

📖 EXPERIMENTS

Classification

$k=5$ dls KNN 분류기를 사용하여 노드 분류를 수행한다.
그래프 구조 데이터의 분산이 높을 수 있기 때문에 이 프로세스를 10회 반복하고 다음의 표에 평균 Macro-F1 및 Micro-F1을 보인다.

위 표의 분석을 통해 제안된 HAN이 모든 데이터 세트에서 가장 우수한 성능을 달성한다는 것을 확인할 수 있다.
결과는 heterogeneous graph 분석에서 노드 및 meta-path의 중요성을 포착하는 것이 매우 중요하다는 것을 보인다.

Clustering

노드 클러스터링을 수행하기 위해 KMeans를 활용한다.
군집 결과의 품질을 평가하기 위해 NMI 및 ARI를 채택한다.
KMeans의 성능은 초기 중심성에 영향을 받기 때문에 프로세스를 10번 반복하고 다음의 표에 평균 결과를 보인다.

위 표의 분석을 통해 제안된 HAN이 heterogeneous graph를 포괄적으로 설명하고 상당한 개선을 달성할 수 있다는 것을 알 수 있다.

Analysis of Hierarchical Attention Mechanism

HAN의 중요한 특징 중 하나는 계층적 메커니즘의 통합이다.
본 섹션에서는 계층적 어텐션 메커니즘에 대한 분석을 통해 이웃과 meta-path의 중요성을 이해한다.

Analysis of node-level attention

ACM 데이터 셋의 논문 P831을 예시로 들었다.
위 그림은 논문 P831의 meta-path 기반 이웃 및 각 이웃의 어텐션 값을 의미한다.

그림을 통해 P831과 같은 class에 해당하는 본인 노드 P831을 포함하여 P699와 P133이 node-level attention에서 가장 높은 어텐션 값을 얻었음을 보인다.

Analysis of semantic-level attention

위 그림은 DBLP 및 ACM 데이터 셋을 예로 들어 클러스터링의 결과(NMI)와 어텐션 값을 보인다.

클러스터링의 결과와 어텐션 값 간에는 긍정적인 상관 관계가 있음을 보인다.
DBLP의 경우 HAN은 APCPA에 가장 큰 가중치를 부여하며, 이는 HAN이 작성자의 연구 분야를 식별하는데 APCPA를 가장 중요한 meta-path라 간주한다는 것을 의미한다.

Visualization

다음 그림은 t-SNE를 사용하여 DBLP의 저자 임베딩을 시각화하고 노드를 그들의 연구 분야에 따라 색칠했다.

homogeneous 그래프에 설계된 GCN과 GAT는 성능이 좋지 않아 보인다.
metapath2vec은 homogeneous 그래프 신경망보다 훨씬 우수한 성능을 보이지만, metapath2vec은 하나의 메타패스만 고려할 수 있기 때문에 경계가 여전히 흐릿하다.
다중 meta-path의 지도를 받아 HAN에 의해 학습된 임베딩은 클래스 내 유사성이 높으며 서로 다른 연구 분야의 저자를 명확한 경계로 분리한다.

Parameters Experiments

본 섹션에서는 파라미터의 민감성을 조사하고 ACM 데이터셋에서 클러스터링 결과를 다양한 파라미터로 보인다.

최종 임베딩 Z의 차원 : 임베딩 차원이 증가함에 따라 성능이 상승하고 이후 천천히 감소하는 것을 보인다.
Semantic-level atttention vector $q$ 의 차원 : Han의 성능은 Semantic-level attention vector의 차원과 함계 성장하며, q의 차원이 128로 설정될 때 최고의 성능을 달성한다.
그 이후에는 성능이 감소하기 시작한다.
Attention head의 수 $K$ : attention head의 수가 증가할수록 Han의 성능이 일반적으로 향상되지만 중간에 다소 감소함을 보인다.
그럼에도 꾸준한 성능의 향상을 보이며 multihead attention이 훈련 프로세스를 더 안정적으로 만들 수 있음을 의미한다.

📖 CONCLUSION

본 논문을 통해 heterogeneous graph의 이해도를 높였으며, 해당 데이터셋을 위한 추천 시스템 모델 논문을 찾아보고자 하는 계기가 되었다.
heterogeneous graph를 추천 시스템에 적용함으로써 추천의 해석가능성을 높이고, 더욱 풍부한 의미를 적용할 수 있어 흥미로울 것이라 생각한다.

Reference

Heterogeneous Graph Attention Network
[Paper Review] Heterogeneous Graph Attention Network

태환

연세대학교 컴퓨터과학과 석사 과정

이전 포스트

[논문 리뷰] GRAPH ATTENTION NETWORKS

다음 포스트