GNN hiện đại: Graph Transformer, long-range learning, scaling và Graph Foundation Models

GAT không phải Graph Transformer. GAT, Graph Attention Network, chỉ tính trọng số chú ý giữa một nút và các láng giềng nối bởi cạnh thật. Nút là một thực thể. Cạnh là một mối quan hệ. Láng giềng là các nút nối trực tiếp với một nút. Graph Transformer cho các nút tương tác rộng hơn, thường là cả đồ thị, và phải đưa cấu trúc vào bằng mã hóa vị trí hoặc mã hóa cấu trúc. Câu hỏi của bài là vì sao một Transformer thông thường không tự biết đồ thị, mã hóa nào đưa topology vào attention, và foundation model trên đồ thị đang hứa điều gì cùng giới hạn nào. Attention là trọng số học được cho biết một phần tử đáng chú ý tới mức nào. Bài không viết lại message passing từ đầu, không hướng dẫn train GAT trên Cora, và không khẳng định một kiến trúc đã thắng cuộc.

Đường đọc nhanh: mục 2, 3 và 4, rồi mục 13, 16 và 17. Đó là Transformer thuần, khác biệt với GAT, các kiểu mã hóa, foundation model, và khi nào nên thử. Mục Đào sâu về GraphGPS và Exphormer nằm ngoài đường này.

1. Tại sao message passing local chưa phải câu trả lời cuối cùng?

Một MPNN, message passing neural network, là mạng mà mỗi lớp chỉ gửi tin dọc theo cạnh thật. Một hop là một bước đi dọc đúng một cạnh. Mạng $L$ lớp đưa tin đi xa tối đa $L$ hop.

Điều này tạo ba giới hạn lớn:

Long-range dependency: hai nút xa nhau cần nhiều lớp mới tương tác. Long-range là phụ thuộc vào thông tin ở xa, không chỉ ở láng giềng một cạnh.
Over-squashing: quá nhiều tin từ xa bị ép qua một vài cạnh vào một vector có số chiều cố định.
Over-smoothing: sau nhiều lần trộn láng giềng, biểu diễn các nút trở nên quá giống nhau.

Một cách cho nút xa nói chuyện ngay là cho mọi nút chú ý tới mọi nút. Attention chuẩn viết thành softmax của tích query và key, rồi nhân value:

\mathrm{Attention}(Q,K,V) = \mathrm{softmax}\left(\frac{QK^\top}{\sqrt d}\right)V

Nhưng Transformer chuẩn có vấn đề khác.

2. Vì sao vanilla Transformer chưa phải Graph Transformer?

Giả sử ta biến mỗi nút thành một token, tức một phần tử trong chuỗi đưa vào Transformer, rồi để Transformer xử lý.

Nếu không thêm gì khác, Transformer biết:

node feature;
quan hệ attention học được.

Nhưng nó không tự biết:

node nào có edge trực tiếp;
shortest-path distance;
degree;
loại edge;
node nào đóng vai trò cấu trúc tương tự;
graph được đánh số node thế nào.

Trong văn bản, positional encoding là một vectơ nói vị trí của token trong chuỗi. Với đồ thị không có một trục vị trí duy nhất như 1,2,3,.... Bậc, degree, là số cạnh chạm vào một nút. Shortest-path distance là số cạnh ít nhất trên một đường đi giữa hai nút.

Do đó Graph Transformer phải trả lời:

“Làm thế nào đưa topology vào attention mà vẫn giữ symmetry hợp lý của graph?”

3. GAT và Graph Transformer khác nhau ở đâu?

GAT

GAT chỉ đặt trọng số dương trên cạnh thật: $j$ phải là láng giềng của $i$ .

\alpha_{ij}>0 \quad \text{for } j\in\mathcal N(i)

Chi phí vì thế đi theo số cạnh, không theo mọi cặp nút:

O(Md)

Full Graph Transformer

Một Graph Transformer đầy đủ có thể cho mọi cặp nút một trọng số, kể cả khi không có cạnh:

\alpha_{ij}>0\quad\forall i,j

Ma trận chú ý đó dày, nên chi phí đi theo bình phương số nút:

O(N^2d)

So sánh

Thuộc tính	GAT	Full Graph Transformer
Attention scope	local edge	global all-pairs
Graph bias	mạnh, edge quyết định	cần encode topology thêm
Long-range	cần nhiều layer	1 layer có thể global
Complexity	gần $O(M)$	$O(N^2)$
Scale graph lớn	dễ hơn	khó hơn

GAT là attention-based MPNN. Graph Transformer là họ rộng hơn, thường có global interaction và structural encoding.

4. Structural và positional encoding trên graph

Graph không có absolute position đơn giản. Có nhiều cách mô tả “vị trí cấu trúc”.

4.1 Degree encoding

Một mã hóa đơn giản biến bậc thành feature, để nút nhiều cạnh khác nút lá:

PE_i=f(\deg(i))

Node hub và leaf được phân biệt.

4.2 Shortest-path distance

Khoảng cách ngắn nhất giữa hai nút là số cạnh trên đường đi ngắn nhất:

d(i,j)=\text{shortest path length}

Điểm attention có thể cộng thêm một số lệch phụ thuộc khoảng cách đó, nên cặp gần và cặp xa không bị chấm cùng cách:

\mathrm{score}_{ij} = \frac{q_i^\top k_j}{\sqrt d} +b_{d(i,j)}

Node gần nhau theo topology nhận bias khác node xa.

4.3 Laplacian positional encoding

Laplacian của đồ thị là ma trận ghi độ lệch giữa một nút và hỗn hợp láng giềng đã cân theo bậc:

L=I-D^{-1/2}AD^{-1/2}

Mỗi vector riêng là một hướng mà Laplacian chỉ co giãn, không xoay. Giá trị riêng $\lambda_k$ là hệ số co giãn đó:

L u_k=\lambda_k u_k

Lấy vài tọa độ của các vector riêng tại nút $i$ thì được một mã vị trí phổ:

PE_i=[u_1(i),u_2(i),...,u_k(i)]

Đây giống “tọa độ spectral” của node.

Nhưng eigenvector có sign ambiguity:

$u_k$ và $-u_k$

đều là eigenvector hợp lệ. Model hiện đại phải xử lý ambiguity này thay vì coi dấu là absolute.

4.4 Random-walk structural encoding

Ma trận chuyển $P$ của một bước đi ngẫu nhiên cho xác suất, sau $t$ bước, đứng lại đúng nút xuất phát. Số trên đường chéo là xác suất đó:

(P^t)_{ii}

cho thông tin local structure ở nhiều scale.

GraphGPS dùng các lựa chọn như RWSE (Random Walk Structural Encoding), LapPE và các biến thể xử lý sign/equivariance.

5. Graphormer: đưa structural bias vào Transformer

Graphormer là một trong các Graph Transformer có ảnh hưởng lớn.

Các thành phần chính có thể hiểu như sau:

5.1 Centrality encoding

Degree/centrality của node được encode vào representation.

5.2 Spatial encoding

Shortest-path distance giữa $i,j$ tạo bias cho attention.

5.3 Edge encoding

Thông tin edge trên shortest path có thể được đưa vào score.

Điểm attention của Graphormer là điểm Transformer thông thường, cộng thêm lệch theo khoảng cách và theo cạnh trên đường đi:

A_{ij} = \frac{(h_iW_Q)(h_jW_K)^\top}{\sqrt d} +b_{spatial}(i,j) +b_{edge}(i,j)

Ý tưởng quan trọng:

Transformer không bị thay đổi hoàn toàn; topology được đưa vào như inductive bias cho attention.

Graphormer cho thấy structural encoding là điều kiện rất quan trọng để Transformer hoạt động tốt trên graph.

6. Đào sâu: Local + global, tư tưởng GraphGPS

Một lựa chọn khác là không bắt Transformer làm toàn bộ công việc.

GraphGPS tách layer thành ba thành phần:

positional/structural encoding;
local message passing trên real edges;
global attention.

GraphGPS architecture — Kiến trúc GraphGPS: positional/structural encoding + local message passing + global attention. Nguồn: Rampášek et al., GraphGPS repository / NeurIPS 2022, MIT-licensed repository.

6.1 Vì sao hybrid hợp lý?

Local GNN có inductive bias mạnh:

edge thật;
edge feature;
local chemistry/relationship.

Global attention giải quyết:

long-range interaction;
shortcut information flow;
graph-level context.

Thay vì hỏi “GNN hay Transformer?”, GraphGPS hỏi:

“Local graph operation nào + global interaction nào + structural encoding nào phù hợp?”

7. Full attention quá đắt: scalable Graph Transformer

Full attention cần một ô cho mọi cặp nút, tức một ma trận vuông:

N\times N

Với một trăm nghìn nút, số ô là mười tỷ, không thực tế để tạo ra trực tiếp:

N^2=10^{10}

Các hướng giảm chi phí:

7.1 Sparse attention

Chỉ attention một số cặp node:

real edges;
sampled long-range edges;
expander edges;
landmark/global nodes.

7.2 Linear attention

Xấp xỉ/rearrange attention để tránh ma trận $N^2$ .

7.3 Hierarchical/coarsened graph

Tạo graph ở nhiều resolution.

7.4 Virtual node

Thêm một hoặc vài global nodes tạo đường truyền ngắn giữa các vùng graph.

8. Đào sâu: Exphormer và kết nối toàn cục thưa

Exphormer là một ví dụ đáng học vì nó làm rõ trade-off:

không full-connect mọi node;
thêm sparse expander edges;
thêm virtual global nodes;
vẫn tạo đường truyền global hiệu quả.

Mục tiêu là giữ complexity gần tuyến tính theo graph size trong khi tăng khả năng long-range.

Không cần nhớ chi tiết expander graph để dùng bài này. Ý chính:

Global communication không nhất thiết phải trả giá $N^2$ . Ta có thể thiết kế sparse topology phụ để tạo shortcut.

9. Long-range benchmark: tại sao benchmark kiểu Cora chưa đủ?

Cora chủ yếu đánh giá local citation structure và graph rất nhỏ.

Long Range Graph Benchmark (LRGB) được thiết kế để stress-test các task cần long-range reasoning hơn.

Các dataset tiêu biểu gồm:

PascalVOC-SP;
COCO-SP;
PCQM-Contact;
Peptides-func;
Peptides-struct.

Điểm sư phạm:

Một model thắng Cora chưa chứng minh nó xử lý long-range dependency tốt.

Khi đánh giá kiến trúc hiện đại, cần benchmark phản ánh đúng năng lực muốn kiểm tra.

10. Scaling GNN: vấn đề không chỉ nằm ở số parameter

Graph learning scale lớn có nhiều bottleneck riêng:

10.1 Neighbor explosion

Nếu mỗi nút có 20 láng giềng và ta đi 3 hop, trường hợp không trùng nút cho tới tám nghìn đường đi ứng viên:

20^3=8000

10.2 Irregular memory access

Graph không có grid memory access đều như image tensor.

10.3 Full-batch dependence

Một graph có hàng triệu node/edge không thể đưa nguyên graph lên GPU.

10.4 Sampling bias

Neighbor sampling giúp scale nhưng đổi distribution của neighborhood.

10.5 Partition boundary

Cluster/partition training có thể cắt mất cross-partition context.

Do đó “mô hình ít FLOPs” chưa chắc chạy nhanh trên graph thật; memory locality và sparse kernel rất quan trọng.

11. OGB và OGB-LSC: từ toy benchmark sang realistic graph

Open Graph Benchmark chuẩn hóa:

dataset;
split;
evaluator;
leaderboard.

OGB có task:

node property prediction;
link property prediction;
graph property prediction.

OGB-LSC đẩy scale lên mức rất lớn, ví dụ:

MAG240M: heterogeneous academic graph;
WikiKG90Mv2: knowledge graph link prediction;
PCQM4Mv2: molecular graph regression.

Bài học quan trọng:

Trên graph lớn, scalability là một phần của thuật toán, không chỉ là engineering sau cùng.

12. Pretraining trên graph: tại sao khó hơn text?

Trong NLP, next-token prediction cho hàng nghìn tỷ token là objective tự nhiên và thống nhất.

Graph không có một token order duy nhất và khác nhau rất mạnh giữa domain:

molecule;
social network;
knowledge graph;
citation graph;
road network.

Pretraining objective phổ biến gồm:

12.1 Masked attribute prediction

Mask node/edge feature rồi dự đoán lại.

12.2 Link reconstruction

Dự đoán edge tồn tại hay không.

12.3 Contrastive learning

Contrastive learning kéo hai bản tăng cường của cùng một đồ thị lại gần, và đẩy các bản khác ra xa. Augmentation là một biến thể của đồ thị vẫn được xem là cùng một mẫu. Loss dưới đây đặt cặp dương ở tử số và các mẫu còn lại ở mẫu số:

\mathcal{L}_{contrast} =-\log \frac{\exp(\mathrm{sim}(z,z^+)/\tau)} {\sum_k\exp(\mathrm{sim}(z,z_k)/\tau)}

12.4 Graph-context prediction

Dự đoán subgraph/context hoặc motif.

Graph + text, ví dụ molecule graph + textual description.

13. Graph Foundation Models: xu hướng 2025–2026

Graph Foundation Model (GFM) hướng tới một model pretrained có thể transfer giữa:

nhiều graph;
nhiều domain;
nhiều task;
ít label/few-shot;
đôi khi zero-shot hoặc in-context.

Các survey 2025 mô tả GFM theo ba trục lớn:

backbone architecture;
pretraining strategy;
adaptation mechanism.

Nhưng cần đánh giá tỉnh táo:

Tính đến 2026, graph foundation models vẫn là lĩnh vực đang phát triển; chưa có một kiến trúc duy nhất thống trị như Transformer trong NLP.

Một benchmark GFM năm 2026 nhấn mạnh rằng generalization cần xét cả:

topic/domain shift: graph nói về lĩnh vực khác;
format shift: graph được biểu diễn/định dạng khác.

Điều này cho thấy “pretrain trên nhiều graph” chưa tự động đồng nghĩa generalize tốt cho mọi graph.

14. Graph prompting

Tư tưởng tương tự prompt/adaptation trong foundation models:

pretrained graph encoder giữ tương đối cố định;
thêm prompt/prompt graph/trainable tokens;
adaptation với ít parameter.

Các hướng gồm:

feature prompt;
structure prompt;
task prompt;
virtual node/token prompt.

Graph prompting còn non-standard hơn text prompting vì input structure giữa dataset khác nhau rất mạnh.

15. LLM + graph: hai hướng khác nhau cần phân biệt

15.1 LLM hỗ trợ graph learning

Node có text:

paper node -> title + abstract
product node -> description
entity node -> textual profile

LLM/text encoder tạo semantic embedding rồi GNN học structure.

15.2 Graph hỗ trợ LLM

Graph cung cấp:

knowledge structure;
entity relation;
retrieval path;
constrained reasoning context.

Đây gần với GraphRAG/knowledge-graph retrieval, sẽ học ở chương sau.

15.3 Đừng đồng nhất GNN với GraphRAG

GraphRAG có thể dùng graph database/retrieval mà không dùng GNN.

GNN là một learnable architecture trên graph; GraphRAG là system pattern truy xuất/generation dùng graph structure.

16. Graph Transformer có thay thế GNN không?

Câu trả lời thực tế: không theo kiểu thay thế hoàn toàn.

Nhiều model mạnh là hybrid:

local MPNN + global attention + structural encoding

Lý do:

local edge có semantics mạnh;
global attention giải quyết long-range;
structural encoding cho attention biết topology;
sparse/hybrid design giúp scale.

Do đó tư duy hiện đại là phối hợp inductive biases, không phải chọn phe.

17. Khi nào Graph Transformer đáng thử?

Nên cân nhắc khi

task cần long-range dependency;
message passing sâu bị bottleneck;
graph nhỏ/trung bình nhưng structural pattern phức tạp;
có đủ compute;
benchmark cho thấy local GNN đã chạm trần;
cần pretraining/hybrid architecture.

Chưa nên dùng ngay khi

dataset rất nhỏ;
GCN/GIN baseline chưa làm sạch;
edge feature local quyết định phần lớn target;
latency/VRAM nghiêm ngặt;
không có protocol evaluation đáng tin.

Một Graph Transformer phức tạp không sửa được split sai hay data leakage.

18. Positional encoding có thể gây leakage không?

Có thể, tùy cách tính.

Ví dụ node classification inductive:

nếu positional encoding được tính trên toàn graph có chứa future/test structure;
nhưng deployment không có cấu trúc đó ở thời điểm inference;

thì evaluation có thể lạc quan.

Cần hỏi:

Structural feature này có thật sự tồn tại tại thời điểm dự đoán ngoài đời không?

Nguyên tắc này giống feature leakage trong tabular ML nhưng dễ bị bỏ qua ở graph.

19. Bảy ý còn đúng khi tên mô hình đổi

Thay vì cố nhớ hàng trăm model mới, nên nắm 7 ý bền vững:

graph symmetry và representation;
message passing;
aggregation và expressive power;
local-vs-global information flow;
structural/positional encoding;
sampling/scaling/evaluation;
task/domain-specific inductive bias.

Model name sẽ thay đổi. Bảy câu hỏi trên vẫn dùng được để đọc paper mới.

20. Cách đọc một paper GNN/Graph Transformer mới

Đọc theo checklist:

Architecture

token/node representation là gì?
local operation là gì?
global operation là gì?
edge feature đi vào đâu?
positional/structural encoding nào?

Complexity

theoretical $O(N)$ , $O(M)$ hay $O(N^2)$ ?
có materialize attention matrix không?
sampling/partition thế nào?

Evaluation

benchmark nào?
split nào?
baseline có mạnh/công bằng không?
nhiều seed không?
parameter/runtime có báo không?

Claim

improvement do architecture hay pretraining/data augmentation?
có ablation từng thành phần không?
chỉ thắng toy dataset hay realistic benchmark?

21. Ví dụ thiết kế hybrid cho bài toán thực tế

Giả sử molecule graph cần dự đoán một property phụ thuộc:

local chemical bond;
long-range relation giữa hai functional groups.

Một design hợp lý:

Giải thích:

GINE giữ chemistry local;
structural encoding cung cấp vị trí graph;
global attention tạo long-range interaction;
pooling tạo graph embedding.

22. Bài tập theo mức

Mức A — phân biệt khái niệm

GAT khác full Graph Transformer ở attention scope thế nào?
Vì sao vanilla Transformer không biết shortest-path distance?
Positional encoding trên graph khác positional encoding chuỗi ở đâu?

Mức B — thiết kế

Cho graph 10.000 node, 100.000 edge. So sánh complexity sơ bộ:

GAT local;
full global attention.

Tại sao graph sparse có thể làm GAT rẻ hơn nhiều?

Mức C — đọc GraphGPS

Tìm ba thành phần trong GraphGPS:

positional/structural encoding;
local MPNN;
global attention.

Đề xuất một cấu hình khác cho molecule và một cấu hình cho social graph.

Mức C+ — nghiên cứu

Thiết kế experiment kiểm tra giả thuyết:

“Global attention giúp vì giải quyết long-range dependency, không chỉ vì tăng parameter count.”

Yêu cầu có:

local-only baseline;
global-only baseline;
local+global;
matched parameter budget;
benchmark có long-range signal;
multi-seed report.

Những ý mang đi

GAT không phải Graph Transformer: GAT chỉ chú ý trên cạnh thật, Graph Transformer cho nút nhìn rộng hơn và cần mã hóa cấu trúc. Transformer thuần biết feature và trọng số học được, nhưng không tự biết cạnh, bậc hay khoảng cách ngắn nhất. Mã hóa bậc, khoảng cách, Laplacian hoặc bước đi ngẫu nhiên là cách đưa topology vào attention. Foundation model trên đồ thị là hướng pretrained rồi chuyển miền, và tính đến 2026 vẫn chưa có một kiến trúc thống trị như Transformer trong ngôn ngữ. Graph Transformer phức tạp không sửa một split sai.

Bài kế chuyển sang mô hình sinh: dữ liệu thô có thể được gom vào một vector ẩn như thế nào.

23. Tài liệu tham khảo cập nhật

C. Ying et al., Do Transformers Really Perform Bad for Graph Representation? (Graphormer), NeurIPS 2021. https://arxiv.org/abs/2106.05234
L. Rampášek et al., Recipe for a General, Powerful, Scalable Graph Transformer (GraphGPS), NeurIPS 2022. https://arxiv.org/abs/2205.12454
H. Shirzad et al., Exphormer: Sparse Transformers for Graphs, ICML 2023. https://arxiv.org/abs/2303.06147
V. P. Dwivedi et al., Long Range Graph Benchmark, NeurIPS 2022 datasets/benchmark work. https://github.com/vijaydwivedi75/lrgb
A. Shehzad et al., Graph Transformers: A Survey, 2024. https://arxiv.org/abs/2407.09777
Z. Wang et al., Graph Foundation Models: A Comprehensive Survey, 2025 / KDD 2025 survey. https://arxiv.org/abs/2505.15116
Z. Wang et al., Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees, ICML 2025. https://proceedings.mlr.press/v267/wang25eq.html
X. Yu et al., Evaluating Progress in Graph Foundation Models: A Comprehensive Benchmark and New Insights, 2026. https://arxiv.org/abs/2603.10033
Open Graph Benchmark: https://ogb.stanford.edu/
GraphGPS repository (MIT): https://github.com/rampasek/GraphGPS

Bản tiếng Anh đang soạn.