Graphormer는 그래프의 구조적인 특성들을 파악할 수 있는 Transformer 기반 모델로, 각 노드의 중요성 정보를 받는 centrality encoding, 노드 간의 구조적 정보를 받는 spatial encoding, 그리고 edge feature 정보를 받는 edge encoding을 attention에 반영한다. 이번 글에서는 Graphormer가 무엇인지에 대해 알아보겠다.
Motivation
트랜스포머를 그래프 데이터에 적용시키기 위해 단순히 그래프를 시퀀스 형태로 바꾸거나, GNN의 기본적인 형태에 attention을 적용하는 등의 방법들이 활용되어 왔다. 하지만 그래프는 단순한 시퀀스 데이터와는 다르게, 노드와 노드 사이의 엣지 정보를 통해서 어떤 구조를 형성한다. 이러한 구조적 정보를 모델이 학습할 수 있도록 하는 것이 중요하기 때문에 Graphormer는 그래프의 구조적인 정보를 반영하는 Transformer를 만드는 것을 목적으로 한다.
Method
Graphormer가 그래프의 구조적인 정보를 반영하는 방법은 크게 세 가지로, 1) centrality encoding, 2) spatial encoding, 그리고 3) edge encoding이 있다. Centrality encoding은 각 노드의 중요성 정보를 반영하고, spatial encoding은 노드와 노드 사이의 구조적 정보를 반영하고, edge encoding은 edge feature 정보를 반영한다.
Centrality encoding
Centrality encoding은 각 노드의 중요성 정보를 반영하는 encoding으로, 그래프 내에서 각 노드가 얼마나 중요한 역할을 하는지를 의미한다. 많은 centrality measure들 중 Graphormer는 degree cnetrality를 사용한다. Degree centrality는 in-degree와 out-degree를 각각 다른 learnable embedding으로 학습하여 기존의 node feature에 더하는 식으로 계산된다. Degree centrality를 반영한 각 노드의 hidden vector 값은 다음과 같이 계산된다.
Spatial encoding
Spatial encoding은 노드와 노드 사이의 spatial relation을 반영하는 encoding이다. 기존의 시퀀스를 다루는 트랜스포머는 시퀀스 내의 각 토큰들의 위치 정보를 positional encoding을 통해서 반영했다. 하지만 그래프는 시퀀스 형태가 아니기 때문에 이러한 방식으로는 정보를 적절히 반영할 수 없다. 그렇기 때문에 Graphormer는 그래프 상에서의 노드와 노드 사이의 shortest path로 상대적인 position을 encoding한다. 이를 통해 계산되는 query와 key 사이의 similarity matrix는 다음과 같이 계산된다. 아래 식에서 h는 node의 hidden vector를, W는 query와 key의 weight matrix를, b는 노드 간 shortest path를 input으로 받는 learnable scalar이다.
이 matrix를 softmax function에 넣고 value 값을 곱하면 attention matrix가 된다. 이러한 spatial encoding의 장점은 노드 간의 attention을 계산할 때 항상 그래프 구조적인 정보를 Transformer가 학습할 수 있게 한다는 점이다.
Edge encoding
Edge encoding은 edge feature를 반영하는 encoding이다. Transformer에 edge feature를 반영하기 위해 Graphormer는 spatial encoding에서 정의한 similarity matrix에 edge feature를 추가한다. 즉, 노드 i로부터 노드 j로까지의 shortest path에 있는 모든 엣지들의 edge feature를 평균내어서 해당 matrix에 더하는 것이다. 이는 식으로 나타내면 다음과 같다. 아래 식에서 $c_{ij}$는 edge encoding을, $x_{e_n}$는 edge feature를 의미한다.
Other techniques
이외에 Graphormer는 구현을 할 때에 virtual node를 이용한다는 특징을 가진다. 이 virtual node는 모든 노드에 연결되어 있고, 이에 따라 message passing을 통해 feature가 업데이트되며, BERT에서의 [CLS] 토큰이 문장 전체의 representation을 나타냈듯이 이는 그래프 전체의 representation을 나타내게 된다. 이를 통해 Graphormer는 graph-level prediction task가 가능해질 뿐만 아니라 over-smoothing도 어느 정도 방지할 수 있게 된다.
Graphormer의 또 하나의 중요한 의의 중 하나는 적절한 weight와 노드와 노드 사이의 distance function을 정의하면, Graphormer가 다른 GIN, GCN 등의 모델을 표현할 수 있다는 점이다. 예를 들어, spatial encoding을 할 때에 노드 간 거리가 1이면 1, 나머지는 0으로 매핑을 하면 이는 이웃한 노드와 이웃하지 않은 노드를 구별할 수 있게 하기 때문에 GCN과 비슷한 효과를 낼 수 있을 것이다.
Experiments
Graphormer의 실험은 graph-level prediction인 quantum chemistry regression task에 대해서 진행되었다. 실험 결과를 통해다른 GNN 모델들보다 Graphormer가 더 좋은 성능을 냄을 알 수 있다.
이번 글에서는 Graphormer에 대해서 알아보았다. 올해 graph transformer intro 논문들을 마무리하는 것이 소박한 목표인데 2개 남았다..!
References
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., ... & Liu, T. Y. (2021). Do transformers really perform badly for graph representation?. Advances in Neural Information Processing Systems, 34, 28877-28888.
최근댓글