[89] Relational Attention: Generalizing Transformers for Graph-Structured Tasks

[long8v]

paper

TL;DR

• I read this because.. : 제목이 attention을 통해 relation 뽑겠다는 개념인 것 같고 자기 방법론이 우아하다고 해서 읽음
• task : Graph representation
• problem : transformer로 그래프 표현해보자. 트랜스포머는 그래프와 달리 순서가 없는 set을 input으로 받고 GNN과 달리 relational한 inductive bias가 없다.
• idea : edge와 node를 concat해서 Q, K, V로 사용하자
• architecture : transformer + edge update for neighbor nodes and edges
• baseline : Deep Sets, Graph ATtention network, Message Passing Neural Network, Pointer Graph Networks
• data : CLRS-30 graph로 알고리즘 푸는 벤치마크인 듯하다.
• result : SOTA
• limitation / things I cannot understand : 아니 이 접근이 정말 없었나? ㅋㅋ

  Details

  motivation

  

transformer는 edge가 없는 graph인 set을 받고 이를 표현하는 모델이라고 생각할 수 있음. transformer에 edge까지 넣어보자

Previous work

https://arxiv.org/pdf/2207.02505.pdf

Graph Neural Networks

notation 설명.

• graph G는 node $N$과 edge $\varepsilon$으로 구성됨
  • $N$ : 순서가 없는 node vectors $n_i\in \mathbb{R}^{d_n}$ set으로 구성됨
  • $\varepsilon$ : edge vector $e_{ij}\in\mathbb{R}^{d_e}$ 셋으로 구성됨
• 각 레이어 $l$에서는 그래프 $G^l$을 받고 같은 구조의 $G^{l+1}$을 return.
• $\phi$ : update function
• $\oplus$ : aggregation function
• $L_i$ : i번째 node의 neighbor들
• 기본적인 GNN은 모든 Edge (i, j)에서 $e{ij}^{l+1}=e{ij}^l$임

Relational Transformer

우아..하면서 간단.. edge node concat해서 qkv projection의 x로 쓰자

연산 간단히 하려고 행렬 잘라서 아래와 같이 표현

그림으로 표현하면 이렇다.

Edge update

edge를 모든 node, 모든 edge들에 대해서 업데이트를 하면 복잡도가 $O(n^3)$이 되니 인접한 두개의 노드, 자기 자신, 반대 방향으로 가는 Edge 이렇게 4가지에 대해서만 aggregation해서 message passing을 한다.