Do Transformers Really Perform Bad for Graph Representation?

Graph representation에서 Transformer 계열 모델이 실제로 약한지, inductive bias와 구조 정보를 중심으로 비교한 우수 보고서입니다.

발행일: 2026년 6월 13일
작성자: YAI

Do Transformers Really Perform Bad for Graph Representation?

16기 · GNN · 논문리뷰 · 4주차

Graph representation에서 Transformer 계열 모델이 실제로 약한지, inductive bias와 구조 정보를 중심으로 비교한 우수 보고서입니다.

그래프 구조를 모델에 주입하는 방식과 attention 기반 구조학습의 한계를 함께 토론했습니다.

Do Transformers Really Perform Bad for Graph Representation?

0. Abstract

Transformer 구조 : CV, NLP 등 많은 도메인에서 우세하게 많이 채택된 구조이지만 아직 GNN에서는 대표적인 graph-level prediction 방법론에 비해서는 좋은 성과를 보이지 못함

이런 점에서 transformer 구조가 graph representation learning에 정작 유용한 지에 대하여 의구심이 들기 시작함

이러한 의구심을 해결하기 위해 “Graphomer”이라는 기존 standard Transformer 구조 base model을 제안

이는 기존 transformer based graph method와 달리 다양한 범위의 graph representation learning에서 좋은 성과를 보이며 특히 OGB Large-Scale Challenge에 좋은 성능을 보임

Graphomer에서 transformer를 graph에 적용한 방법의 핵심은 graph의 structural information을 효율적으로 encoding을 진행하여 model에 적용하는 것이다.

1. Introductory Concepts

Transformer : natural language, speech와 같은 sequential data를 modeling하는데 가장 powerful한 network이며 CV와 PL에서도 transformer based variant들이 좋은 성과를 보임

하지만, graph representation에 있어서는 transformer-based approach는 그다지 좋은 성능을 보이지 못함

실제로 transformer를 graph domain에 적용하려는 시도는 많았으나 유일한 효율적인 성능을 보인 approach는 class GNN 계열 model에서 feature aggregation같이 몇몇 key model을 softmax attention을 이용하여 대체하는 방식으로 근본적으로 transformer based model은 설계하지는 못하였다.

이런 점에서 transformer architecture 자체가 과연 graph representation learning과 graph modeling에 정작 상성이 맞고 유용한 지에 대하여 의구심을 가지기 시작함

이런 기존 transformer based model의 문제점을 해결하기 위해 “Graphomer”이라는 새로운 model을 제안하며 이는 기존 approach와는 달리 standard transformer에 직접적으로 built-in한 transformer-based approach로 Open Graph Benchmark Large-Scale Challenge(OGB-LSC)와 같은 graph level representation task에서 SOTA 성과를 보임

Transformer는 원래 sequential modeling을 위해 설계되었는데 이를 graph에도 잘 적용하기 위해서는 graph의 structural information을 model에 적적하게 적용하는 것이 관건이다.

이는 각 node $i$에 대하여 self-attention은 $i$와 다른 node간 semantic similarity만 계산을 하기 때문에 이는 node와 node pair간 관계를 반영한 graph의 structural information이 포함되지 못함

이러한 structural information을 반영하기 위해 Graphomer은 다양한 효율적인 encoding method를 적용하여 graph의 structural information을 반영함

Encoding methods

Centrality Encoding

Graph 내 node importance를 포착하는 encoding 기법

Social network에서 일반인과 유명인 차이와 같이 graph 내에서는 서로 다른 node는 각기 다른 중요도를 가지고 있다.

하지만 이러한 정보를 self-attention을 통해서는 반영을 하지 못하는데, 이는 self-attention module은 node의 semantic feature을 기반으로 유사도를 계산하기 때문이다.

이러한 문제를 해결하기 위해 Centrality Encoding에서는 degree centrality를 반영하는데, 이는 학습이 가능한 vector를 degree에 따른 각 node에 반영하여 여기에 node feature와 함께 input layer에 반영한다.

실제로 simple centrality encoding이 transformer가 graph data를 modeling하는데 좋은 성능을 보인 사례가 입증됨

Spatial Encoding

Graph 내 node 간 structural relation을 포착하는 encoding 기법

Graph data가 다른 형태의 data와 구분되는 커다란 특징 중 하나는 graph에 embedding할 수 있는 canonical “grid-type” 형태로 나타내지 못하다는 것이다.

이러한 arbitrary한 structure를 modeling하기 위해서는 학습이 가능한 embedding을 spatial relation에 기반을 두어 각 node pair에 반영을 한다.

이러한 spatial relation을 modeling하기 위해 여러 가지 요소들을 반영함

대표적으로 임의의 두 node 간 최단 거리 등을 사용하여 softmax attention에서 bias term으로 encoding을 진행하였는데, graph 내 spatial dependency를 정확히 포착하는데 도움을 줌

또한 molecular graph에서 두 atom간 molecular bond의 종류와 같이 edge 간 feature에서도 spatial information을 포착할 수 있었음

이러한 spatial information signal을 transformer layer에 적용하기 위해 spatial encoding을 사용함

이는 각 node pair마다 edge feature의 dot product의 평균과 최단 거리 내에서 학습이 가능한 embedding을 계산하고 이를 attention module에 적용하는 방식이다.

이러한 방식으로 Graphomer는 node pair간 relationship을 modeling을 잘하게 되어 graph representation이 좋아짐

이러한 encoding method를 사용함으로써 Graphomer는 major GNN 계열과 같이 강한 표현력을 가지며 Graphomer의 가장 큰 capacity는 실제로 다양한 task에서 SOTA performance를 보임

2. Referred Information

GNN

Graph $G=(V,E)$에서 node 집합 $V=\{v_1,...,v_n\}$에 대하여 $n=|V|$는 node의 개수이고 node $v_i$의 feature vector를 $x_i$라 정의함

GNN은 graph와 node의 representation을 학습하는 것을 목표로 함

특히 최근 GNN들의 경우 node representation update을 처음 또는 더 높은 order 이웃으로 representation aggregation 방식을 사용함

$h_i^{(l)}$을 $v_i$의 $l$번째 layer에서의 representation이라 정의하며 $h_i^{(0)}=x_i$로 초기화한다.

이때 $l$번째 aggregation인 $\texttt{AGGREGATE-COMBINE}$ step은 아래와 같이 나타낼 수 있음

a_i^{(l)}=\texttt{AGGREGATE}^{(l)}(\{h_j^{(l-1)}:j\in \mathcal N(v_i)\}),~~h_i^{(l)}=\texttt{COMBINE}^{(l)}(h_i^{(l-1)},a_i^{(l)})

여기서 $\mathcal N(v_i)$는 $v_i$의 처음 또는 더 높은 order 이웃의 집합을 의미하며 $\texttt{AGGREGATE}$ function은 이웃 정보를 집계하는 데 사용함

이러한 $\texttt{AGGREGATE}$ function으로는 mean, max, sum 등 대표값을 사용하면 되는데 GNN의 종류에 따라 상이함

$\texttt{COMBINE}$ function의 목표는 node representation에 이웃 정보를 결합하는 것이다.

추가적으로 graph representation task에 대해서는 아래와 같이 $\texttt{READOUT}$ function을 사용하여 final iteration의 node feature $h_i^{(L)}$의 aggregation을 진행하여 전체 graph $G$에 대한 representation $h_G$에 적용한다.

h_G=\texttt{READOUT}(\{h_i^{(L)}|v_i\in G\})

이때, $\texttt{READOUT}$ function은 summation 또는 보다 더 정교한 graph-level pooling function 등을 이용하여 구현이 가능함

Transformer

Transformer layer들로 구성되며 각 transformer layer는 아래와 같이 2가지로 구성됨

Self-attention model

Position-wise feed-forward network (FFN)

Self attention model의 input을 $H=[h_1^T,...,h_n^T]^T\in\mathbb R^{n\times d}$라 할 때 $d$는 hidden dimension, $h_i\in\mathbb R^{1\times d}$는 position $i$에서의 hidden representation을 의미함

여기서 input $H$는 3개의 matrix $W_Q\in\mathbb R^{d\times d_K},W_K\in\mathbb R^{d\times d_K},W_V\in\mathbb R^{d\times d_V}$에 의해 각각의 대응되는 $Q,K,V$에 대하여 projection이 진행되며 이로 인한 self-attention 계산은 아래와 같다.

Q=HW_Q,~K=HW_K,~V=HW_V,\\A=\frac{QK^T}{\sqrt{d_K}},~\texttt{Attn}(H)=\texttt{softmax}(A)V

이때 $A$는 query와 key간 유사도를 포착하는 matrix이고, 위 식은 simplicity를 위해 bias term은 배제하고 single-head self-attention과 $d_K=d_V=d$로 가정하였으며 multi-head attention으로 확장은 standard하게 진행하면 됨

3. Approach

Structural Encodings in Graphormer

Transformer model에 graph의 structural information을 반영하는 것이 중요하기 때문에 간단하지만 효율적인 encoding 방식을 고려할 필요가 있음

Centrality Encoding

기존 transformer model에서의 self-attention mechanism은 node간 semantic correlation을 기반으로 연산을 수행함

이와 달리 node centrality를 사용하면 node간 중요도를 비교할 수 있기 때문에 graph 이해에 좋은 signal을 줄 수 있음

Graphomer에서는 neural network에 degree centrality signal을 추가하여 구현하였는데, 이는 각 node의 2개의 indegree와 outdegree 기반 실제값 embedding vector를 배치하는 centrality encoding 기법을 사용함

이를 이용하여 centrality encoding을 각 node에 적용하여 input으로 아래와 같이 node feature에 단순히 반영하기만 하면 된다.

h_i^{(0)}=x_i+z^-_{\deg^-(v_i)}+z^+_{\deg^+(v_i)}

여기서 $z^-,z^+\in\mathbb R^d$는 각각 indegree와 outdegree 기반으로 주어진 학습 가능한 embedding vector에 해당하며 undirected graph의 경우 $\deg^-(v_i)=\deg^+(v_i)=\deg(v_i)$로 간주하면 됨

이렇게 centrality encoding을 input으로 사용하면, softmax attention은 query와 key 내의 node의 중요도를 포착할 수 있게 되어 model은 semantic correlation과 node의 중요도를 attention mechanism에서 모두 포착할 수 있게 된다.

Spatial Encoding

Transformer의 가장 큰 장점은 global receptive field를 가진다는 점이며, 각 token은 어떠한 position에 있는 information에 관해서도 반영하여 representation을 나타낼 수 있다.

하지만 위와 같은 방법을 사용하면 model이 명시적으로 서로 다른 position에 대하여 분류하거나 locality와 같은 positional dependency 등을 layer에 직접 encoding을 해야 한다는 번거로움이 있다.

Sequential data의 경우, input으로 각 position을 embedding으로 하거나 임의의 2개의 position에 대하여 relative distance를 encoding하는 relative positional encoding을 transformer layer에 적용하면 된다.

하지만, graph의 경우 sequential data가 아닌 multi-dimensional spatial space 내에 node들이 edge와 arbitrary하게 연결되어 있는 형태를 지님

이러한 graph의 structural information을 encoding하기 위해서 Spatial Encoding이라는 방법을 제안함

어떠한 graph $G$에 대하여, graph 내 $v_i$와 $v_j$ 간 spatial relation을 측정하는 함수 $\phi(v_i,v_j):V\times V\to\mathbb R$을 정의할 수 있으며 이 함수는 graph 내 node간 connectivity로 정의될 수 있음

Graphomer에서는 $\phi(v_i,v_j)$로 서로 연결된 node에 관해서 shortest path distance(SPD)를 사용하였고, 연결되어 있지 않다면 $\phi$의 output을 -1등 특정 값으로 초기화하는 방식을 사용함

각 output value의 경우 학습이 가능한 scalar형태로 self-attention model의 bias term으로 반영하여 Query-Key product matrix $A_{ij}$를 아래와 같이 나타냄

A_{ij}=\frac{(h_iW_Q)(hW_K)^T}{\sqrt{d}}+b_{\phi(v_i,v_j)}

여기서 $b_{\phi(v_i,v_j)}$는 $\phi(v_i,v_j)$에 의해 index를 정한 학습이 가능한 scalar로 모든 layer에 공유함

이와 같이 spatial encoding을 진행하면 다음과 같은 이점을 지님

기존 GNN와는 달리 receptive field가 이웃에 국한되기 때문에 transformer layer이 각 node가 다른 node에 대하여 global information을 전부 전달할 수 있게 된다.

$b_{\phi(v_i,v_j)}$를 사용함으로써 단일 transformer layer에 있는 각 node는 graph structural information에 따라 다른 모든 node들에도 적용할 수 있음, 예를 들어 $b_{\phi(v_i,v_j)}$가 $\phi(v_i,v_j)$에 대하여 감소함수 관계이면, model인 멀리 있는 node보다 인접한 node에 대하여 더 주의 깊게 볼 것이다.

Edge Encoding in the Attention

Edge 또한 graph 내에서 structural feature를 보임 (예를 들어 분자 graph에서 원자 간 화학 결합은 서로 다른 edge feature를 나타냄)

이러한 feature들은 graph representation에 있어서 중요하고, node feature와 더불어 이러한 edge feature를 network에 encoding을 하는 것이 핵심적이다.

기존의 edge encoding 방법으로는 edge feature를 이와 결합된 node feature에 단순히 더해지는 방법이나, 각 node에 대하여 단순히 더해지는 방법이나, 각 node에 대하여 edge feature가 node feature와 함께 aggregation 형태로 나타내는 방법이 있다. 하지만, 이러한 방법들은 edge information을 결합된 node에 대해서만 propagation이 일어나기 때문에 graph 전체에 대한 representation을 반영하기에는 효율적인 방법이 아니다.

이를 해결하기 위해 Graphomer는 다른 방법으로 edge feature를 attention layer에 encoding하는 방법을 사용함

이때 attention mechanism은 각 node pair $(v_i,v_j)$에 대하여 상관관계를 추정할 수 있어야 하고 이들과 연결되어 있는 edge 역시 상관관계에 고려되어야 한다.

위와 같은 방법을 수행하기 위해 각 정렬된 node pair $(v_i,v_j)$에 대하여 $v_i$에서 $v_j$로의 최단경로 $\text{SP}_{ij}=(e_1,...,e_N)$을 탐색하여 edge feature와 학습이 가능한 embedding에 대하여 dot product의 평균에 대하여 computation을 진행

이와 같은 edge encoding을 진행하면 edge feature를 attention module의 bias term으로 도모하게 되며 아래와 같이 $A$의 $(i,j)$번째 element에 대하여 edge encoding $c_{ij}$를 반영한 modification을 진행할 수 있다.

A_{ij}=\frac{(h_iW_Q)(h_jW_K)^T}{\sqrt d}+b_{\phi(v_i,v_j)}+c_{ij},~\text{where }c_{ij}=\frac 1 N \overset{N}{\underset{n=1}\sum}x_{e_n}(w_n^E)^T

여기서 $x_{e_n}$은 $\text{SP}_{ij}$에서 $n$번째 edge $e_n$의 feature를 의미하고, $w_n^E\in\mathbb R^{d_E}$는 $n$번째 weight embedding을 의미하며, $d_E$는 edge feature의 dimensionality를 나타냄

Implementation Details of Graphomer

Graphomer Layer

Classic transformer encoder 기반으로 설계되었는데 추가적으로 layer normalisation을 multi-head self attention과 feed forward block 이전에 적용을 하였는데 그 결과 optimisation에 있어서 좋은 효율성을 보임

특히 FFN sub-layer에 대하여, input, output, inner layer의 dimensionality를 $d$로 설정해 놓고 아래와 같이 Graphomer layer를 구현함

h^{'(l)}=\texttt{MHA}(\texttt{LN}(h^{(l-1)}))+h^{(l-1)}\\h^{(l)}=\texttt{FFN}(\texttt{LN}(h^{'(l)}))+h^{'(l)}

Special Node

Graph embedding을 나타내기 위해 여러 graph pooling function이 사용됨

Grpaphormer의 경우 $\texttt{[VNode]}$라는 node를 추가하여 각 node와 $[\texttt{VNode}]$를 개별적으로 모두 연결함

이때, $\texttt{AGGREGATE-COMBINE}$ step에서 $\texttt{[VNode]}$의 representation을 일반 node로 update을 진행하고 graph 전체의 representation $h_G$는 최종 layer에서 $\texttt{[VNode]}$의 node feature가 된다.

이는 $\texttt{BERT}$ model에서 각 sequence의 첫 부분에 반영하여 downstream task에 sequence-level feature representation을 보여주는 $\texttt{[CLS]}$ token과 유사한 역할을 수행함

$\texttt{[VNode]}$가 서로 다른 node들과 모두 연결되어 있을때, 임의의 $\phi(\texttt{[VNode]},v_j)$와 $\phi(v_i,\texttt{[VNode]})$ 간의 최단거리가 1일 경우, 물리적으로 연결되지 않음을 의미함

이때, 물리적 연결과 가상 연결을 구분하기 위해 $b_{\phi(\texttt{[VNode]},v_j)}$와 $b_{\phi(v_i,\texttt{[VNode]})}$ 간 모든 spatial encoding을 distinct한 학습이 가능한 scalar로 reset한다.

How Powerful is Graphomer?

Graphomer은 주요 GNN model에서 $\texttt{AGGREGATE}$와 $\texttt{COMBINE}$ step 모두 나타낼 수 있다.

Referred information 1

적절한 weight, distance function $\phi$를 선택하기 위해 Graphormer는 $\texttt{GIN, GCN, GraphSAGE}$ 등 유명한 GNN model에서 $\texttt{AGGREGATE, COMBINE}$ 등과 같은 step을 구현할 수 있음

Proof

Spatial encoding은 self-attention model로 하여금 node $v_i$의 이웃 집합 $\mathcal N(v_i)$을 구분할 수 있게 하여 softmax function이 $\mathcal N(v_i)$의 mean statistic computation이 가능하게 함

Node degree를 알고 있으면, 이웃과 관련된 평균은 이웃 간 총합으로 해석이 가능함

여러 head와 FFN을 가지고 있기에, $v_i$와 $\mathcal N(v_i)$의 representation은 따로 분리해서 process가 가능하고 추후 결합하는 방식을 가능하게 한다.

이러한 spatial encoding을 이용함으로써 Graphormer는 최대 역량이 1-Weisfeiler-Lehman test 수준인 전통적인 message passing GNN을 능가하는 성능을 보이며, 무엇보다도 1-WL test를 실패한 graph에 대하여 Graphormer는 이들을 분류할 수 있도록 도와준다.

Connection between Self-attention and Virtual Node

Self-attention과 virtual node 간 heuristic connection도 하나의 큰 특징이다.

OGB leaderboard에서도 알 수 있듯이 graph를 추가적인 supernode를 도입하여 기존 graph의 모든 node와 연결하여 augmentation을 진행하는 virtual node trick을 이용하여 GNN의 성능을 개선할 수 있었음

일단 virtual node의 가장 큰 이점은 $\texttt{READOUT}$ function과 같이 전체 graph에 대한 정보의 aggregation이 가능하여 각 node에 propagation이 진행이 가능하다.

하지만, 단순하게 graph에 supernode를 도입하게 되면, 잠재적으로 information propagation에 있어서 oversmoothing problem이 도래할 수 있기 때문에, graph-level aggregation과 propagation 연산을 추가적인 encoding 없이 vanilla self-attention으로 충족하였다.

Referred information 2

적절한 weight을 선택함으로써, Graphormer layer의 output의 각 node representation을 추가적인 encoding 없이 $\texttt{MEAN READOUT}$ function을 나타낼 수 있기 때문에 self-attention을 통해 각 node가 다른 모든 node에 반영을 할 수 있다는 이점을 가짐

무엇보다도 Graphormer는 oversmoothing problem을 가지고 있지 않기 때문에 더 좋은 성능을 보일 수 있었고 이와 같은 배경이 있었기에 graph readout에 special node를 도입하는 방법이 가능하였음