Graph Transformer Networks (GTN)
- Homogeneous Graphs
- 모든 노드의 종류가 동일한 그래프
- Heterogeneous Graphs
- 여러 종류(type)의 노드(node) 및 엣지(edge)로 구성된 그래프
- 더 많은 정보를 담을 수 있음
- 엣지 종류는 연결된 노드의 종류의 조합에 따라 결정 됨
- 여러 종류(type)의 노드(node) 및 엣지(edge)로 구성된 그래프
- Metha-Path
- Heterogenous graph에서 노드와 엣지의 type차원의 미리 지정해둔 경로(sequence)
- e.g. 음악 스트리밍 사이트 네트워크
- 노드의 종류: 사용자{user1, user2, …} / 가수{singer1, singer2, …} / 장르{rock, disco, …}
- Meta-Path: 사용자-가수-장르, 사용자-가수-장르-가수-사용자, …
GTN
Introduction
- limitations of GNNs
- 기존 GNN의 한계
- 그래프의 구조가 고정되어 있고, homogeneous하다는 것을 가정한 후 task 수행
- 만약, 일부가 생략되어 있거나 가짜고 형성된 noisy graph에 대해서 정확한 task를 수행하기 어려움
- 특히 Heterogeneous 그래프의 특성을 반영하지 못함
- 해결 방안
- 직접 설정한 meta-path를 이용해 heterogeneous 그래프를 homogeneous graph로 변환
- 변환된 homogeneous 그래프로 일반적인 task 수행
- 하지만 이러한 방법은 meta-path의 영향을 많이 받음 (=종속적)
- 기존 GNN의 한계
- Contributions of GTN
- GTN
- 입력된 heterogeneous 그래프를 meta-path를 통해 새로운 그래프 구조를 학습하는 네트워크
- meta-path의 길이와 edge 종류가 arbitrary 한 점을 다루는 것이 관건
- Contributions
- 효과적인 node representation 학습을 위해 유용한 pata-path와 multi-hop 연결을 확인하며 새로운 그래프 구조를 학습하는 Graph Transformer Network를 제안
- 새로운 그래프 구조를 생성하는 것은 해석 가능하며 모델을 통해 효과적인 meta-path를 찾을 수 있는 인사이트를 얻을 수 있음
- GTM을 통해 학습한 node representation 으로 heterogeneous 그래프의 node classfication task에서 SOTA 성능 달성
GTN에서는 학습을 통해 유용한 meta-path를 찾아내어 새로운 그래프를 변환함 핵심은 길이와 엣지 종류가 모두 의미적인 meta-path 중에서 의미있는 meta-path를 end-to-end 방식으로 찾아냈다는 점
- GTN
Realted Works
- Two approaches: Spectral vs. Non-Spectral
- Spectral
- 그래프 신호처리 이론 기반의 방법론
- 신호처리 이론의 푸리에 변환을 convolution으로 풀어냄
- Undirected graph 전제
- Normalized Laplacian Matrix 활용
- Laplacian Matrix: $L^{origin} = D - A$
- Normalized Laplacian Matrix: $L = I - D^{-1/2}AD^{-1/2} = U \Lambda U^{T} (by SVD)$
- 한계점
- SVD 계산의 복잡도가 높음
- 그래프의 변화가 있을 시 고유벡터가 변함
- Domain dependent하여 그래프 구조 변화 시 적용 불가
- Non-Spectral
- Spatial-based
- 노드의 공간적 관계에 기반 = 주변 이웃 노드와 먼 노드 구분
- 가까운 이웃 노드의 정보 이용
- Spectral-based 대비 장점
- 높은 계산 효율성: 그래프가 커져도 주변 노드들만 고려
- 그래프의 변화에 강건함
- Undirected와 directed graph 모두 다룰 수 있음
- 결과적으로 Spatial-based 방법론의 선호 증가
- Spatial-based
- Spectral
Method
- Graph Transformer Networks
- Goal of GTN
- 다수의 후보 인접행렬(Adjacency matrix) 중 graph convolution에 효과적인 새로운 그래프 구조를 찾아내는 것 (=유용한 meta-path를 찾아내는 것)
- 새로운 구조의 그래프를 생성하는 동시에 node representation을 학습하는 것
- Preliminaries
- Notations
-
$T^{v}$ : Set of node types / $T^{e}$ : Set of edge types / $V$ : Set of nodes, $N = V $ / $E$ : Set of edges / Graph : $G=(V,E)$ - $f_{v}:V \rightarrow T^{v}$ : Node type mapping function / $f_{e}:E \rightarrow T^{e}$ : Edge type mapping function
- Heterogeneous graph는 인접행렬의 모음으로 표현됨
-
- Meta-Path
- $P$: A path on G with heterogeneous edges
- $R$: Composite Relation = Sequence of edge types
- $A_{p}$: Adjacency matrix of the meta-path $P$ = multiplications of adfacency matrices
- Notations
- Goal of GTN
- GTN의 핵심은 유용한 meta-path를 찾아나가도록 학습하는 것
- 그러기 위해서 여러가지 후보 meta-path를 생성해야 함 (2가지 과정이 필요)
-
- 인접행렬 텐서로부터 두가지 인접행렬을 생성
- $\Phi$: convolution layer
- $W_{\Phi}$ :1x1xK 파라미터 텐서
- 이것을 softmax함수에 적용하면 각 파라미터는 엣지 타입별 가중치를 의미
- 소프트맥스가 적용된 1x1xk 컨볼루션 레이어와 인접행렬 텐서를 연산하여 Q를 구함
- 이 과정을 한번 더 반복해서 Q1과 Q2를 구함
- Q1과 Q2의 곱을 통해 새로운 구조의 인접행렬을 구함
- 이것을 degree 매트릭스를 이용해 표준화를 진행하면 meta-path 인접행렬을 얻게 되는 것
GTN의 input: adjacency tensor / output: 레이어를 거쳐 나오는 결과물은 길이가 1인 adjacency matrix
- 이런식으로 $l$개의 레이어가 쌓이면 NxNxC 형태의 meta-path가 형성되는데 이는 곧 서로 다른 C개의 길이가 $l$인 meta path의 adjacency tensor를 의미함
- 따라서 각 adjacency matrix와 input feature를 GCN 레이어에 입력하여 Z라는 multiple representation을 만들어 냄
- 최종적으로 이 Z가 일반적인 GCN 레이어와 같이 두개의 dense layer와 소프트맥스 layer를 거쳐서 classification이 이루어짐
GTN을 통해 길이가 $l$인 meta-path 후보 C개를 생성하여 이중에서 가장 유용한 meta-path를 찾아내는 것
- 인접행렬 텐서로부터 두가지 인접행렬을 생성
Conclusion
- Process
- Heterogeneous graph를 길이와 edge type이 임의적인 다수의 새로운 그래프로 변환
- =데이터 셋에 따라 길이가 $l$인 여러 개의 후보 meta-paths를 만듦
- GCN을 통ㅎ해 node representation 학습 진행
- Heterogeneous graph를 길이와 edge type이 임의적인 다수의 새로운 그래프로 변환
- Future works
- GCN이 아닌 다른 종류의 GNN으로의 학습 가능
- Node classification에 더해, link prediction 및 graph classification 등에 맞게 학습 진행
댓글남기기