안녕하세요 콥스랩(COBS LAB)입니다.
오늘 소개해 드릴 논문은 ‘Graph-BERT’입니다.
해당 내용은 유튜브 ‘딥러닝 논문읽기 모임' 중 ‘Graph-BERT’ 영상 스크립트를 편집한 내용으로, 영상으로도 확인하실 수 있습니다. (영상링크: https://youtu.be/2kQDL-byr0k)
Graph는 현실에서 다양한 정보를 가진 노드들과 그 연결성을 모델링화할 수 있는 형태의 데이터를 말합니다. 예를 들면 사람의 신경을 이미지화하거나 온라인 소셜미디어에 친구관계라든가 생물 분자와 같은 연결성을 가진 형태의 데이터를 Graph라고 합니다. Graph는 전통적인 머신러닝의 기법을 적용하기 어렵다는 점이 있는데 그래도 지난 몇 년간 node2vec, deepwalk, GCN 같은 Graph 뉴럴 네트워크 모델의 발전이 있었습니다. 그런데 이 모델들은 문제가 있는데, 모델들을 모두 노드와 노드를 연결하는 그 연결성에 학습을 진행하는 모델이기 때문에 모델이 너무 깊어지거나 어느 정도 특정 제한이 넘어가면 더 이상 트레이닝 데이터에 대한 학습을 진행하지 않고 또는 노드들이 평활화가 돼서 다른 노드들과 차이가 크게 없어져서 Over-smoothing problem 이 발생하여 더 이상 학습이 불가능해지는 현상이 일어났습니다. 또는 Graph가 커지면 커질수록 Graph 병렬 학습이 불가능하기 때문에 학습이 어렵다는 단점이 있습니다.
Graph-BERT는 이 Graph를 연결이 아닌 각 노드의 특성을 입력값으로 학습하여서 이 위에 문제점들을 해결하고자 하였습니다. 그리고 또한 자연어처리나 이미지 학습의 transfer learning 모델들처럼 추가적인 파인튜닝을 진행해서 다양한 테스크에도 적용이 가능합니다.
이 모델을 짧게 summarize 하자면 모델을 전체 Graph와 그의 연결이 아닌 subGraph로 나누고 그 sub-Graph안에 노드들의 특성을 따라 학습합니다. 그리고 그 해당 모델은 기존 모델과 다르게 학습의 횟수와 sub-Graph의 사이즈만 비용이 들어서 기존 모델보다 비용이 적게 든다는 장점이 있습니다. 그리고 자연어처리 BERT 모델이 가려진 단어를 찾고 다음 문장의 어떤 문장이 들어오는지 확인하는 사전 학습 과정처럼 이 모델에서도 사전 학습 과정이 두 가지가 있습니다. unlabeled 된 Graph로 각 노드의 속성을 재구성하거나 Graph를 재구성하는 두 가지 방법으로 pre training을 진행하고 다른 사전 학습 모델과 마찬가지로 fine-tuning을 진행하여 여러 가지 테스크에 적용 가능합니다.
Graph-BERT 모델에 연관이 있는 모델은 GNN 모델 중에 Graph convolution 네트워크 모델이 있고, Graph의 각 노드들에 연관성을 가진 Adjacent Matrix를 웨이트 값을 convolution을 적용해서 노드 피쳐 Matrix를 얻는 과정이 있습니다. 이렇게 얻은 Matrix 값들은 서로 연관이 있기 때문에 Matrix상의 위치가 같은 노드 와의 연결이지만 Matrix상에서 위치가 달라지는 현상이 발생하는데 이 현상을 줄이기 위해서 Readout이라는 Matrix를 더해주는 과정을 한번 거친 후에 다시 한번 fully connected layer를 적용하여 진행하는 것이 일반적인 GCN 모델의 구조입니다. 그리고 GCN 모델을 응용한 것이 Graph transformer attention 모델인데 self attention 기반의 i번째 노드에 대한 Matrix와 다음 연관이 있는 j번째 노드의 Matrix의 각각의 가중치를 곱해준 값을 더 하고 Relu를 해준 값을 관계 값으로 구하는데 이 Matrix 사이에 모든 노드의 관계 값을 합쳐 주는 값을 a라고 하고, a를 모든 convolution 네트워크 레이어에 적용해주는 모델을 Graph transformer attention 모델이라고 합니다.
다음으로, METHOD 부분을 살펴보겠습니다. 본 논문의 모델은 전체 Graph를 sub Graph로 나누고 그 각각의 sub Graph를 타겟 노드와 가장 연관이 높은 노드 k개를 선택한 후, 그 노드들에 대해서 임베딩을 진행하고 그렇게 임베딩이 진행된 Matrix에 대해서 Graph 트랜스포머를 진행합니다. 이렇게 나온 결과물을 Readout 과정을 통해서 모두 합쳐 주고 각각의 테스크에 맞춰서 출력합니다.
앞서 설명을 드렸던 것처럼, 본 논문은 전체 Graph를 sub Graph 쪽에서 입력을 해서 학습을 진행합니다. 그리고, Graph 노드 간의 intimacy 스코어를 계산하는데 구글의 페이지 링크 알고리즘을 응용한 모델을 사용해서 intimacy 스코어를 계산합니다. PageRank를 간단하게 설명을 하자면 웹사이트들 중에 어떤 웹사이트가 가장 중요한지 판단하는 방법에 사용되는 알고리즘으로 다른 웹사이트에서 가장 많이 이동한 웹 사이트가 가장 중요하다고 여기고 계산하는 방법은 C에서 연결된 웹사이트가 a와 b가 있을 때 a 웹사이트와 a웹사이트에 연결된 노드의 개수를 나눈 값과 C b웹사이트와 b웹사이트에 연결된 노드 값을 나눈 두 개를 a에 연결된 b와 c가 노드에 연결된 전체의 값을 합쳐 준 값이 A의 PageRank값이 됩니다. 이 방법을 응용한 방법으로 Graph 인접행렬에 Adjacent Matrix의 그 행렬값에 diagonal Matrix를 곱한 값을 A -라고 합니다. A-의 여기서 1-⍺ 이 모델에서는 ⍺값을 0.15로 사용합니다. 1에서 0.15를 빼준 0.85를 곱해준 다음에 그 값을 아이덴티티 Matrix에서 빼준 값을 인버스 해주고 그 인버스 해준 값에 다시 0.15를 곱해 준 방식으로 intimacy 스코어를 계산하고 있습니다. 이렇게 타겟 노드에 대해서 intimacy Matrix 값 안에서 타겟 노드에 대해서 특정 연관성이 높은 노드들만 타겟 노드에 대한 컨텍스트 노드가 될 수 있습니다. 이렇게 해서 Graph 형태로 나눠서 intimacy 형태로 나눈 벡터 값으로 나눠줬다면, 이제 입력값에 대해서 임베딩을 진행해주게 됩니다.
Graph 데이터는 이미지나 텍스 데이터와 같이 같지 않게 순서가 정해져 있지 않습니다. 그래서 노드들 중에 타겟 노드와 가장 연관성이 높은 노드들로만 순서대로 탑K개 순서로 입력받아서 임베딩을 진행합니다. 임베딩은 Raw Feature vector Embedding, Weisfeiler-heman absolute Role Embedding Intimacy based Relative Positional Embedding, Hope based Relative Distance Embedding 이렇게 네 가지를 통해서 진행이 됩니다.
첫 번째로 Raw Feature vector Embedding은 각각 sub Graph의 노드 V_j를 모두 같은 크기의 d_h의 피쳐 벡터 스페이스로 임베딩을 하는 과정을 말합니다. 이 과정은 데이터 형태에 따라서 다르게 준비가 됩니다. 이미지의 경우 CNN, 텍스트의 경우 LSTM 또는 BERT, 그 외 다른 데이터 같은 경우는 그냥 fully connected layer를 사용해서 진행이 됩니다. 그리고 이렇게 진행된 벡터들을 Weisfeiler-heman absolute Role Embedding이라는 과정을 진행하게 됩니다. 일명 WL 알고리즘이라고 부르기도 하는 이 알고리즘은 전체 Graph에 structure roles을 반영하기 위해서 진행한다고 합니다. 그래서 각 모든 노드들에게 숫자를 지정해주고, 예를 들어 1번 노드와 연결된 노드의 숫자들을 다시 1번 노드의 값이라고 지정해주는 방식입니다. 구체적으로, 1번 노드와 연결된 노드가 2번 노드와 5번 노드라고 하면 1번 노드의 값은 7번 노드가 됩니다. 이 과정을 이 논문에서 두 번 반복했습니다. 이렇게 두 번 반복한 값에 sin과 cos을 적용해 준 값을 Weisfeiler-heman absolute Role Embedding이라고 합니다. 이렇게 임베딩 된 값들은 각 노드의 전체 Graph에 대해서 structure roles를 반영하고 있습니다.
세 번째는 Intimacy based Relative Positional Embedding으로, Intimacy 순서대로 나열한 sub Graph들을 local information을 추출할 수 있도록 반영하는 임베딩입니다. 각 노드들에게 숫자 포지션을 반영하게 되는데 본인 노드와 본인 노드 사이의 포지션 인덱스는 0이고, 그 노드와 가장 가까운 노드는 1번 그다음 가까운 노드는 포지션 2 이런 식으로 각각의 subGraph 안에서 모든 노드들 사이에 포지션 인덱스를 가지게 됩니다. 그리고 네 번째는 Hope based Relative Distance Embedding으로 전체 Graph 안에서 타겟 노드 V_i와 sub Graph 안에서 다른 노드 사이의 거리를 비교하는 방식으로 같은 타겟 노드의 콘텍스트 관계인 v_j값은 다른 여러 가지 sub Graph안에서 값이 다룰 수 있기 때문에, 이 해당 방식으로 전체 Graph와 sub Graph 사이에 밸런싱을 조정한다고 합니다.
앞에서 설명드린 네 가지 방법으로 나온 각각의 임베딩을 전부 다 더해줍니다. 이 노드들의 전체의 Matrix를 L-1개의 레이어의 Graph 트랜스포머를 거치게 됩니다. Graph 트랜스포머는 앞서 설명드린 GCN 모델에 attention을 곱해주는 레이어를 L-1개 지나고 추가적으로 이 모델에서는 G-Res라는 Residual 값을 더 해줍니다. Residual 값은 아웃풋 값과 각각의 노드의 기존 Raw Feature값을 빼준 값을 Residual값을 가져 빼준 다음에 이 전체 모델의 Residual로 더해주는 형식으로 학습을 합니다. 그리고 마지막 타겟 노드를 기준으로 된 representation을 갖고 싶기 때문에 기존의 GCN 모델에서 ReadOut레이어를 적용해줘서 전체 Matrix를 다 더해줍니다. 여기서는 ReadOut 대신 Fusion 레이어를 진행해서 각 노드의 평균을 더하는 대신 평균을 진행해 줍니다.
이렇게 임베딩이 끝나면 다음으로 프리 트레이닝을 진행하게 됩니다. 프리 트레이닝 과정은 두 가지 방식을 통해서 진행이 됩니다. Node Attribute reconstruction과 Graph structure recovery 이렇게 두 가지 테스크가 있습니다. Node Attribute reconstruction은 타겟 노드 V_i가 기존에 Raw Graph 전체에서 가지는 값과 얼마나 차이가 있는가를 크로스 엔트로피로 두고 fully connected layer를 통해서 학습을 합니다. 그리고 Graph structure recovery는 두 개의 노드 V_i와 V_j에 연결 점수를 cos similarity로 계산하고, 마찬가지로 동일한 노드를 sub Graph 안에서 cos similarity를 계산하고 그 차이를 비교하며 학습을 진행합니다. 이 두 개의 과정으로 BERT Graph모델의 제작이 끝이 납니다. 그리고 이 모델을 마지막으로 사용하기 위해선 테스크에 맞는 파인튜닝을 진행하게 됩니다. 파인튜닝은 Node Classification과 Graph Clustering 이렇게 두 가지 테스크가 있는데 그 각각의 테스크에 맞춰서 파인튜닝을 진행하게 됩니다. Node Classification은 프리 트레인 된 아웃풋을 소프트맥스 값을 적용해서 0과 1 사이의 값을 가지도록 하고 트루 레이블과 비교해서 로지스틱 regression cost function을 사용한 fully connected layer로 재학습을 진행합니다. 그리고 다른 테스크인 Graph 클러스터는 클러스터들의 중심이 되는 백터와 다른 프리 트레인 벡터 값과 비교하면서 재학습을 진행합니다. 여기까지가 논문의 Graph BERT의 모델 학습 진행 과정이었습니다.
다음으로 이 논문의 experiment 부분입니다. 해당 논문은 Graph 데이터로 Cora, Citeseer, Pubmed 이렇게 세 개의 데이터를 사용하였습니다. 각 데이터는 Cora는 일곱 개의 서클, Citeseer는 다섯 개 Pubmed는 30개의 sub Graph 사이즈를 사용했다고 합니다. 그리고 히든 레이어의 길이는 32, attention 헤드는 2개 그리고 히든 레이어 개수도 두 개 사용했습니다. Learning rate는 각각 데이터에 대해서 Cora 0.01 , Citeseer는 0.001, pubmed 0.0005 그리고 weight decay는 동일하게 0.0005 그리고 Dropout rate도 동일하게 0.5 그리고 Training epoch는 Cora의 경우 150, Citeseer 2000 epoch 그리고 pubmed는 500 epoch을 사용하였다고 합니다.
앞서 설명드린 대로 각각 데이터들을 동일한 순서대로 학습을 진행하고 epoch을 200번을 두고 노드 reconstruction과 Graph recovery의 테스크를 진행했을 때 동일하게 트레이닝 로스가 줄어드는 것을 확인할 수 있습니다.
Graph BERT는 다양한 테스크에 적용할 수 있는데 기존 다른 모델의 레이어의 깊이가 깊어질수록 suspended animation problem 이 있는 것에 비해, Graph BERT는 50 가지의 Graph 깊이를 늘려도 학습이 계속 진행되고 있는 것을 확인할 수 있습니다. 그리고 다른 모델보다 모든 데이터에서 다른 GNN 모델들보다 Graph BERT가 모든 데이터에서 동일하게 가장 높은 정확도가 나온다는 것을 확인하였습니다.
다음으로는 모델을 sub Graph 사이즈 K 값에 대해서 Cora의 데이터를 가지고 비교했을 때 Cora의 경우 K의 sub Graph 사이즈가 k가 7일 때 가장 정확한 테스트 accuracy가 나왔기 때문에 해당 데이터로는 k를 7로 지정하고 학습을 진행하였다고 합니다. 그리고 프리 트레인 과정에서 앞서 Residual를 추가해주는 부분이 있었는데 그 Residual을 추가 해주는 것에 대한 영향을 확인했을 때, 모든 데이터에서 Graph와 Residual을 추가해줬을 때가 더 높은 정확도가 나오기 때문에, Graph와 Residual을 추가하는 방식으로 해당 모델에서 진행을 하였습니다.
그리고 모델에서 각각의 임베딩을 거친 과정에서 모든 네 개의 임베딩을 적용했을 때 모든 데이터셋에서 가장 정확도가 높게 나오기 때문에, 임베딩 네 개를 모두 적용하였다고 합니다.
그리고 마지막으로 기존 Graph의 BERT 대신 프리 트레인 되지 않은 모델을 사용했을 때 대부분의 데이터셋에서 낮은 정확도가 나온 반면에 Graph BERT를 진행하고, 각각의 파인튜닝 테스크를 진행했을 때 BERT를 사용하지 않은 모델들보다 epoch을 훨씬 적게 사용하더라도 학습이 가능하고 높은 정확도를 가진다고 합니다. Node Classification은 두 개의 프리 트레인 태스크를 진행했을 때 가장 높은 정확도를 가지는 반면에 Graph Clustering은 프리 트레인 테스크만 진행했을 때 더 높은 정확도를 가진다는 걸 확인할 수 있었습니다.
결론입니다. Graph BERT는 기존의 GNN 모델들이 가지고 있는 모든 문제로부터 자유롭고 전체 Graph가 아닌 타겟 노드에 대한 representation을 트랜스포머 레이어를 적용하는 학습법을 소개하고 있습니다. 또한 이 모델은 트랜스포머 모델이기 때문에 파인 튜닝으로 진행하여서 원하는 태스크로 진행할 수 있다고 합니다.
댓글