TL;DR
- I read this because.. : NeurIPS 2023
- task : graph representation
- problem : message passing 접근론들(MPNN)은 NLP의 long-term dependency와 비슷한 문제인 over-smoothing, over-squashing 문제가 있음. transformer를 graph에 바로 넣으면 global attention을 하기에 node 들이 많아질 경우 연산량이 quadratic.
- idea : MPNN + Transformer, 기존에 있었던 Positional Embedding과 Structural Embedding을 정리하고 각각이 MPNN에 얼마나 영향을 미치는지 봄.
- architecture : global attention + MPNN 한다
- baseline : GCN, GAT, SAN, Graphormer, …
- data : ZINC, PATTERN, CLIST, MNIST, CIFAR10, ….
- evaluation : MAE, Accuracy, …
- result : benchmark 중 몇개 sota, 준수한 성적
Details
Related work
first fully transformer graph netowrk https://arxiv.org/pdf/2012.09699.pdf
Positional Encoding(PE)
- local node cluster 내에서의 position을 아는 것.
- global graph 내에서의 position을 아는 것
- relative 노드 pair 끼리의 상대적인 거리를 아는 것.
Structural Encoding(SE)
graph나 subgraph의 구조를 임베딩해서 GNN의 표현력과 일반화를 늘리려는 목표
GPS Layer: an MPNN + Transformer Hybrid
- $A\in\mathbb{R}^{N\times N}$ : adjacency matric of a graph with N nodes and E edges
- $X^l\in \mathbb{R}^{N\times d_l}$ : $d_l$ 차원의 node feature
- $E^l\in \mathbb{R}^{N\times d_l}$ : $d_l$ 차원의 edge feature
Result
Ablation
