Chapter 6. Graph Neural Networks in Practice

Graph Representation Learning Book 읽고 정리하기 시리즈 중 다섯 번째 이야기. 부디 완주하게 기도해주세요 !

6.1 Applications and Loss Functions

GNN은 주로 다음 세 가지 문제를 해결하는데 많이 사용된다.

• 노드 분류 및 회귀 (예) 소셜 네트워크에서 한 계정이 실제 사용자인지 봇인지 분류
• 그래프 분류 및 회귀 (예) 분자 성질 분류 및 회귀
• 관계 예측 (예) 추천 시스템 (한 사용자와 연결 확률이 높은 상품을 추천)

섹션 $6.1$에서는 위 세 가지 문제를 해결하기 위해서 각각 어떤 손실 함수를 사용해야 하는지 알아본다. 그리고 섹션의 후반부에서는 비지도 학습 기반으로 GNN을 사전 훈련 (pre-training)하는 방법에 대해 알아본다. 사전 훈련된 GNN을 위 세 가지 문제에 사용할 경우 모델의 예측 성능을 향상시킬 수도 있다. (지도/비지도/자가지도 학습으로 모델 가중치를 사전 훈련한 후 모델의 끝부분만 바꿔서 문제를 해결하는 접근 방법이 많다. 이때,사전 훈련된 네트워크로 풀려고자 하는 문제를 downstream task라고 부른다.)

6.1.1 GNN for Node Classification

노드 분류 문제 해결을 위해서는 다음 손실 함수를 사용한다. \[\mathcal{L}=\sum\limits_{u \in \mathcal{V}_\text{train}}-\operatorname{log}(\operatorname{softmax}(\mathbf{z}_u, \mathbf{y}_u)), \quad \quad (6.1)\]

이때 손실 함수는 훈련 노드 집합 $\mathcal{V}_{\text{train}}$에 있는 모든 원소에 대한 negative log likelihood를 나타낸다. 여기서 $\mathbf{z}_u$은 GNN의 마지막 레이어를 통과한 hidden state 벡터 $\mathbf{h}_u^{(K)}$이고, $\mathbf{y}_u$는 노드 $u$의 클래스에 대한 원핫 벡터이다. 물론 GNN의 출력값 $\mathbf{z}_u$를 바로 소프트 맥스 함수에 넣어줘도 되겠지만 일반적으로는 학습 가능한 벡터를 곱해준 후 넣어준다. \[\operatorname{softmax}(\mathbf{z}_u,\mathbf{y}_u)=\sum\limits_{i=1}^{c}\mathbf{y}_u[i]\frac{e^{-\mathbf{z}_u^\top\mathbf{w}_i}}{\sum_{j=1}^{c}e^{-\mathbf{z}_u^\top\mathbf{w}_j}}, \quad \quad (6.2)\]

여기서 $\mathbf{w}_i \in \mathbb{R}^d, i=1,2,\cdots,c$는 학습 가능한 벡터이다. $\mathbf{y}_u[i]$는 $i$가 $u$가 속한 클래스일 경우에만 1이고 나머지는 0이다. 따라서 소프트 맥스는 보이는 식보다 더 간단한데, 모델이 노드 $u$가 실제 $u$의 클래스에 속할 것이라고 예측한 확률 값이다. 식 $(6.1)$의 변형체들도 있지만 보통 식 $(6.1)$을 가장 많이 사용한다.

6.1.2 GNN for Graph Classification

$\mathcal{T}=\{\mathcal{G}_1, \mathcal{G}_2, \cdots, \mathcal{G}_n\}$을 우리가 갖고 있는 $n$개의 그래프라고 하자. 그리고 $\mathbf{z}_{\mathcal{G}_i}, i=1,2,\cdots,n$를 GNN을 통해 만든 각 그래프에 대한 임베딩 벡터라고 하자. 그래프의 임베딩 벡터는 GNN의 마지막 레이어를 통과한 노드들의 hidden state 벡터들을 적절히 취합해서 만들어진다. 보통은 $\mathbf{z}_\mathcal{G}$를 바로 분류나 회귀에 사용하지 않고 다층 퍼텝트론을 통과시킨 $\operatorname{MLP}(\mathbf{z}_\mathcal{G})$를 사용한다. 분류 문제의 경우 위에서 다뤘던 손실 함수를 사용하면 된다. 회귀 문제의 경우 평범한 평균 오차 제곱 손실 함수를 사용한다. \[\mathcal{L}=\sum\limits_{i=1}^n \lVert \operatorname{MLP}(\mathbf{z}_{\mathcal{G}_i})-y_{\mathcal{G}_i} \rVert_2^2, \quad \quad (6.3)\]

6.1.3 GNNs for Relation Prediction

Shallow embedding 대신 GNN을 통과하여 만들어진 노드 임베딩 벡터들을 사용하여 Chapter $3$과 $4$에서 배웠던 손실 함수를 사용하면 된다고 한다. (자세히 좀 설명해달라고~)

6.1.4 Pretraining GNNs

우리가 Chapter $3$에서 배웠던 노드 임베딩 방법들은 모두 비지도 학습이었다. 따라서 Chapter $3$에서 다뤘던 손실 함수 (reconstruction loss)를 사용하면 레이블 없이도 네트워크 학습이 가능하다. 네트워크를 먼저 사전 훈련하고 이후 downstream 문제에 사용하면 성능 향상을 기대할 수 있다.

하지만 놀랍게도 위 방법으로 사전 훈련한 네트워크를 사용해도 그렇게 큰 성능 향상은 없다고 한다. Chapter $3$에서 배운 방법들은 이웃 노드 또는 $k$-hop 노드 정보를 사용하는데, 임의로 초기화된 GNN이더라도 충분히 그런 정보를 학습할 수 있기 때문이다. 따라서 reconstruction loss를 사용해서 모델을 사전 훈련하는 것은 그렇게 좋은 방법은 아니다.

비지도 학습 기반으로 모델을 사전 훈련시킬 수 있는 방법으로는 2019년에 소개된 Deep Graph Infomax (DGI) 이 있다. DGI에서는 노드 임베딩 벡터 $\mathbf{z}_u$와 그래프 임베딩 벡터 $\mathbf{z}_\mathcal{G}$ 사이의 상호 정보량 (mutual information)을 최대화하는 방법으로 네트워크를 사전 훈련한다. DGI의 손실 함수는 다음과 같다. \[\mathcal{L}=-\sum\limits_{u \in \mathcal{V}_\text{train} }\mathbb{E}_\mathcal{G}\operatorname{log}(D(\mathbf{z}_u, \mathbf{z}_\mathcal{G}))+\gamma\mathbb{E}_{\tilde{\mathcal{G}}}\operatorname{log}(1-D(\tilde{\mathbf{z}_u},\mathbf{z}_\mathcal{G})). \quad \quad (6.4)\]

GAN의 손실 함수와 매우 유사하다. 표기를 설명하기 전에 직관적인 설명은 다음과 같다.

• $D$가 노드 임베딩 벡터와 그래프 임베딩 벡터를 입력 받아서 해당 그래프가 원래 그래프인지 또는 변형된 그래프인지 구분하는 분류 모델이다.
• $\tilde{\mathcal{G}}$는 변형된 (corrupted) 그래프이다. 원래 그래프 $\mathcal{G}$에서 노드의 feature 벡터나 인접 행렬의 원소의 순서를 임의로 섞어서 만들게 된다.
• $\mathbf{z}_u$는 원래 그래프 $\mathcal{G}$를 GNN에 입력했을 때 나온 노드 임베딩 벡터, $\tilde{\mathbf{z}}_u$는 변형된 그래프 $\tilde{\mathcal{G}}$를 입력했을 때 나온 임베딩 벡터이다.
• 분류기 $D$는 $\mathbf{z}_u$와 $\mathbf{z}_\mathcal{G}$를 입력 받았을 때는 1이라 예측을 해야 손실 함수가 작아지고, $\tilde{\mathbf{z}}_u$와 $\mathbf{z}_\mathcal{G}$를 입력 받았을 때는 0이라고 예측을 해야 손실 함수가 작아진다.
• 따라서 $\mathbf{z}_u$와 $\mathbf{z}_\mathcal{G}$가 서로 서로 잘 예측할 수 있도록 임베딩 된다.

이런 류의 실제 그래프와 변형된 그래프를 사용해서 네트워크를 사전 훈련시키는 방법이 좋은 성과를 보이고 있고, 그래서 연구도 많이 되고 있다고 한다. 흥미로운 논문인 것 같다. 하지만 나는 논문을 읽지 않았기 떄문에 책을 읽고 이해한 내용만 적어 놓았다. 관심 있는 분들은 논문을 읽어보면 좋을 것 같다.

6.2 Efficiency Concerns and Node Sampling

Chapter $5$에서 다양한 GNN 모델들의 AGGREGATE 와 UPDATE함수를 기술할 때, 노드 단위의 hidden state 벡터 업데이트 식을 사용했다. 예를 들어, GNN 기초 모델의 업데이트 식은 다음과 같다. \[\mathbf{h}^{(k)}_u=\sigma(\mathbf{W}^{(k)}_{\text{self}}\mathbf{h}^{(k-1)}_u+\mathbf{W}^{(k)}_{\text{neigh}}\sum\limits_{v \in \mathcal{N}(v)}\mathbf{h}^{(k-1)}_v+\mathbf{b}^{(k)}), \quad \quad (5.7)\]

이런 방식으로 업데이트 식을 표현할 경우 생길 수 있는 문제점을 알아보자. 예를 들어, 두 노드 $v$와 $v’$이 노드 $u$를 이웃 노드로 갖는다고 하자. 그럼 $\mathbf{h}_{u}^{(k-1)}$은 $\mathbf{h}_v^{(k)}$를 구할 때와 $\mathbf{h}_{v’}^{(k)}$를 구할 때 각각 한 번씩 총 두 번 계산된다. 중복된 계산이 발생하는 것이다. 노드가 많은 그래프일 수록 이런 중복된 계산이 점점 더 많아지게 될 것이다. 섹션 $6.1.1$에서는 중복되는 계산 없이 노드들의 hidden state 벡터를 업데이트 하는 방법을 알아본다. 섹션 $6.1.2$에서는 노드가 너무 많아서 메모리에 그래프 전체를 할당하지 못할 때 사용할 수 있는 노드 샘플링에 대해 알아본다.

6.2.1 Graph-level Implementations

식 $(5.7)$과 같이 노드 단위의 업데이트 식을 사용하면 노드들의 hidden state 벡터가 어떻게 업데이트되는지 쉽게 알 수 있다. 노드 단위로 업데이트를 하지 않고 hidden state들을 모아놓은 행렬을 이용해서도 hidden state를 업데이트할 수 있다. \[\mathbf{H}^{(k)}=\sigma\left( \mathbf{H}^{(k-1)}\mathbf{W}_{\text{self}}^{(k-1)}+\mathbf{A}\mathbf{H}^{(k-1)}\mathbf{W}_{\text{neigh}}^{(k-1)}\right), \quad \quad (6.5)\]

여기서 $\mathbf{H}^{(k-1)}$은 모든 노드들의 hidden state 벡터를 행벡터로 갖는 행렬이다 (bias 텀 표기 생략). 이렇게 행렬을 이용해서 hidden state를 업데이트 하면 각 노드의 hidden state $\mathbf{h}_u^{(k)}$는 레이어마다 딱 한 번씩만 계산된다는 장점이 있다. 하지만 노드가 굉장히 많은 그래프의 경우 메모리의 한계 때문에 식 $(6.5)$와 같은 행렬 단위 업데이트가 어려울 수 있다.

6.2.2 Subsampling and Mini-Batching

노드가 너무 많아서 전체 그래프에 대한 행렬은 만들 수 없지만 여전히 행렬 단위 업데이트를 사용하고 싶을 것이다. 이럴 때는 전체 노드 집합 $\mathcal{V}$를 사용하는 대신에 노드를 서브 샘플링하여 만든 노드 부분 집합 $\mathcal{V}’ \subset \mathcal{V}$을 사용한다. $\mathcal{V}$를 포함하는 가장 큰 그래프 $\mathcal{G’}=(\mathcal{V}’, \mathcal{E}’), \text{ where }\mathcal{E}’=\{(u, v) : u, v \in \mathcal{V}’ \}$에 대한 행렬을 사용해서 업데이트를 한다. 이 방법은 어찌 됐는 큰 그래프에 대해서도 행렬 업데이트식을 사용할 수 있다는 장점이 있다. 하지만 노드 부분 집합 $\mathcal{V}’$에서 제외된 노드들의 엣지 정보는 다 날리기 때문에 정보 손실이 있을 수 밖에 없다.

Hamilton et al. 2017 [4]에서는 정보 손실을 줄일 수 있는 방법을 제안하고 있다. 노드들을 임의로 샘플링하여 $\mathcal{V}’$을 만드는 것이 아니라, 일부 타겟 노드들을 먼저 샘플링하고 그들의 이웃 노드 몇 개를 따로 추가하여 부분 집합을 만드는 것이다. 이때 추가되는 이웃 노드들을 반복적으로 바꿔가면서 GNN을 학습시켜 그래프의 연결성을 최대한 보존하게 된다. 이 외 노드 서브 샘플링에 대한 연구들도 있다고 하니 큰 그래프를 다루는 분들께서는 찾아보면 좋을 것 같다. (Chen et al., 2018 [5], Ying et al., 2018 [6])

6.3 Parameter Sharing and Regularization

GNN 모델들도 다른 머신러닝 모델들처럼 오버피팅이 발생할 수 있다. 이미 잘 알려진 오버피팅을 줄일 수 있는 방법들 (L2 regularization, dropout, layer normalization)은 GNN에 대해서도 잘 작동한다고 한다. 한편, GNN을 위해 고안된 regularization 방법들도 있다.

Parameter Sharing Across Layers

제목이 곧 내용이다. GNN 안에 있는 모든 AGGREAGATE와 UPDATE 함수에서 파라미터들을 공유하는 것이다. 이 방법은 6층보다 깊은 GNN에 대해서 효과가 좋다고 한다. 한편, 파라미터 공유는 Gated update function (식 $5.30$)과 함께 사용하는 것이 관례라고 한다.

Edge Dropout

제목이 곧 내용이다. 인접 행렬에서 몇 개의 엣지를 임의로 0으로 바꿔서 학습에 사용하는 방법이다. 엣지 dropout은 knowledge graphs에서 성공적으로 성능 향상을 보였다고 한다. 그리고 GAT 논문에서 핵심적인 기술이라고 한다.

참고문헌

[1] https://pixabay.com/ko/illustrations/지구-회로망-3537401/

[2] Hamilton, William L.,Graph Representation Learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, 14, pp.1-159

[3] CS224W: Machine Learning with Graphs

[4] W.L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017b

[5] J. Chen, J. Zhu, and L. Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, 2018

[6] R. Ying, R. He, K. Chen, P. Eksombatchai, W.L. Hamilton, and J. Leskovec.Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018a.