Các họ GNN: GCN, GraphSAGE, GAT, GIN, MPNN và cách chọn mô hình
Bài này trả lời nên chọn họ mạng nào khi mỗi nút đã nhận tin từ láng giềng. Nút là một thực thể. Cạnh là mối quan hệ giữa hai nút. Láng giềng là các nút nối trực tiếp. Message passing không đòi công thức bài trước. Mỗi nút gửi một thông điệp, một gói số, qua cạnh. Nút nhận gộp các gói thành một tóm tắt. Phép gộp đó gọi là aggregate, và không phụ thuộc thứ tự gói. Nút viết vector mới từ tóm tắt và từ vector cũ. Một hop là một bước dọc một cạnh. Bài không dạy cài PyTorch, không chứng minh đủ test Weisfeiler–Lehman, và không khảo sát Graph Transformer.
Đường đọc nhanh: mục 2 đến 5, rồi mục 11, 12, 13, 18 và 19. Mục Đào sâu (mục 6, test 1-WL) đọc sau khi đã có baseline.
1. Một khung chung cho nhiều họ GNN
Ba bước trên viết thành ký hiệu. Bản tóm tắt tại nút là phép gộp thông điệp từ láng giềng:
Vector lớp sau được viết từ vector hiện tại và từ bản tóm tắt vừa gộp:
Một kiến trúc GNN có thể được mô tả bằng 6 câu hỏi:
- Message: node gửi gì cho ?
- Weight: mọi neighbor quan trọng như nhau hay có trọng số khác nhau?
- Aggregate: sum, mean, max, attention hay nhiều thống kê cùng lúc?
- Sampling: dùng toàn bộ neighbor hay chỉ sample một phần?
- Update: cộng, concatenate, MLP, residual hay recurrent update?
- Readout: nếu task ở mức graph, gộp node thành graph embedding thế nào?
2. GCN — baseline mạnh khi graph có homophily tương đối tốt
Homophily là xu hướng hai nút nối nhau giống nhau về feature hoặc nhãn. Bậc là số cạnh chạm vào một nút. GCN hợp baseline khi homophily tương đối rõ: mỗi nút lấy tổng có trọng số của chính nó và của láng giềng, trọng số nhỏ khi bậc hai đầu lớn, rồi qua hàm phi tuyến.
2.1 Điểm mạnh
- đơn giản, ít tham số;
- dễ debug;
- tốt để kiểm tra graph structure có thực sự hữu ích không;
- chi phí gần tuyến tính theo số edge với sparse implementation;
- rất phù hợp làm baseline đầu tiên cho node classification.
2.2 Hạn chế
- aggregation khá cứng: neighbor contribution chủ yếu do degree normalization;
- không xử lý edge feature nhiều chiều một cách tự nhiên;
- full-neighborhood propagation khó scale với graph cực lớn;
- có thể kém trên đồ thị heterophily, tức láng giềng khác nhau về nhãn hoặc về feature;
- sâu quá dễ over-smoothing: sau nhiều lần trộn, các nút trở nên quá giống nhau. Mục 12 nói kỹ hơn.
2.3 Khi nên thử GCN trước
- citation/co-authorship graph;
- node classification;
- graph nhỏ/trung bình;
- cần baseline nhanh, minh bạch.
Quy tắc thực dụng: nếu GCN không thắng MLP feature-only, đừng vội thử GAT 8 heads. Hãy kiểm tra xem graph có thật sự chứa signal hay split/evaluation có vấn đề.
3. GraphSAGE — học hàm aggregation và có thể sample neighbor
GraphSAGE học một hàm tạo embedding cho nút chưa từng xuất hiện lúc huấn luyện. Dạng mean aggregator trước hết lấy trung bình láng giềng:
Vector mới là một lớp tuyến tính trên vector cũ nối với trung bình đó. Ký hiệu là phép nối hai vector:
3.1 Ý tưởng quan trọng nhất không phải concatenate
Điểm lịch sử quan trọng của GraphSAGE là:
sample một số neighbor rồi aggregate, thay vì luôn dùng toàn bộ graph.
Nếu mỗi lớp chỉ lấy mẫu láng giềng, một batch có nút đích và mạng có lớp, số nút phải đọc có thể tăng theo:
vẫn tăng nhanh, nhưng có thể kiểm soát bằng .
3.2 Inductive learning
GraphSAGE học một hàm từ feature của nút và của láng giềng ra embedding, chứ không học một vector tham số riêng cho từng mã nút:
3.3 Khi GraphSAGE hợp lý
- graph lớn;
- user/item liên tục xuất hiện mới;
- cần mini-batch neighbor sampling;
- inductive deployment.
4. GAT — neighbor không nhất thiết quan trọng như nhau
GCN lấy trọng số chủ yếu từ bậc. GAT học attention, trọng số nói láng giềng quan trọng với tới mức nào.
Mỗi nút được biến đổi tuyến tính trước:
Điểm thô giữa hai nút đi qua LeakyReLU:
Trong một láng giềng, các điểm thô được chuẩn hóa cho tổng bằng một:
Vector mới là tổng có trọng số ấy, rồi qua hàm phi tuyến:
4.1 Multi-head attention
Nhiều head là nhiều bộ trọng số. Nối chúng cho vector rộng hơn:
hoặc average các head ở layer cuối.
4.2 GAT có phải “Transformer trên graph” không?
Câu trả lời là không hoàn toàn.
- GAT cổ điển chỉ attention trong 1-hop neighborhood do edge thật quyết định.
- Transformer chuẩn cho phép mọi token attend mọi token.
- Graph Transformer hiện đại thường thêm global attention + structural encoding.
Bài cuối chương tách GAT, chỉ chú ý trong một hop, khỏi Graph Transformer.
4.3 Khi GAT đáng thử
- neighbor relevance không đồng đều;
- graph có nhiều noisy edges;
- cần interpretable attention như một tín hiệu phụ.
Nhưng:
Attention weight không tự động là explanation đáng tin cậy. Nó là một trọng số nội bộ của model, không phải bằng chứng nhân quả về tầm quan trọng.
5. GIN — khi cần khả năng phân biệt cấu trúc mạnh hơn
Graph Isomorphism Network (GIN) nhân vector của chính nút với một hệ số gần 1, cộng tổng láng giềng, rồi đưa qua một MLP đủ mạnh:
Hai lựa chọn đáng chú ý:
- sum aggregation thay vì mean;
- MLP đủ biểu đạt sau aggregation.
5.1 Tại sao sum có thể phân biệt tốt hơn mean?
Hai túi láng giềng sau đây có cùng các vector thành phần nhưng khác số lần lặp:
Túi thứ hai lặp cùng vector đó bốn lần:
Trung bình của cả hai túi đều là cùng một vector:
Tổng thì khác nhau: và .
Sum giữ được thông tin multiplicity mà mean làm mất.
5.2 Khi GIN thường đáng cân nhắc
- graph classification;
- phân tử;
- bài toán cần phân biệt substructure;
- cần baseline expressive nhưng vẫn thuần message passing.
6. Đào sâu: expressive power và Weisfeiler-Lehman test
Expressive power là khả năng phân biệt hai đồ thị khác cấu trúc. Mục này nằm ngoài đường đọc nhanh.
6.1 1-WL test làm gì?
Test 1-WL tô màu lại từng nút qua nhiều vòng. Hai đồ thị isomorphic khi cái này chính là cái kia sau khi đổi tên nút. Test lặp:
- mỗi node có một “màu” ban đầu;
- node tạo màu mới từ:
- màu hiện tại;
- multiset màu hàng xóm;
- nếu hai graph có histogram màu khác nhau ở một vòng nào đó, chúng không isomorphic.
Có thể hình dung:
6.2 Liên hệ với message-passing GNN
Một MPNN, tức message passing neural network, cũng viết trạng thái mới từ chính nút và từ túi màu của láng giềng:
Xu et al. chỉ ra lớp message-passing GNN phổ biến bị giới hạn bởi sức mạnh của 1-WL; GIN được thiết kế để đạt mức biểu đạt tương đương 1-WL trong điều kiện thích hợp.
6.3 Ý nghĩa thực tế
Có những graph không isomorphic nhưng 1-WL vẫn không phân biệt được. Khi đó GCN/GAT/GIN kiểu message passing cơ bản cũng có thể không phân biệt được chỉ từ structure.
Điều này giải thích vì sao các hướng hiện đại thêm:
- positional encoding;
- higher-order GNN;
- subgraph features;
- random features / node identifiers;
- global attention.
Không phải cứ thêm layer/hidden size là GNN tự vượt được giới hạn cấu trúc. Một phần giới hạn đến từ chính lớp hàm mà kiến trúc có thể biểu diễn.
7. MPNN và edge-aware message: khi edge mang semantics mạnh
Khuôn khổ Message Passing Neural Network của Gilmer et al. cho feature cạnh đi thẳng vào hàm thông điệp. Tổng các thông điệp đó là bản tóm tắt mới:
Trạng thái nút ở bước sau là một hàm cập nhật của trạng thái cũ và của bản tóm tắt:
Điểm quan trọng: edge feature đi trực tiếp vào message function.
7.1 Ví dụ phân tử
Node feature:
- atomic number;
- formal charge;
- aromatic flag.
Edge feature:
- single/double/triple/aromatic bond;
- bond distance;
- stereochemistry.
Nếu hai nguyên tử kết nối bằng single bond và double bond, chỉ biết “có edge” là chưa đủ.
7.2 GINE
GINE mở rộng GIN bằng feature cạnh: cộng feature cạnh vào vector láng giềng, rồi đưa qua MLP.
Khi edge attribute quan trọng, GINE/MPNN thường là baseline hợp lý hơn GCN thuần.
8. PNA — khi degree distribution rất khác nhau
Principal Neighbourhood Aggregation (PNA) kết hợp nhiều aggregator:
- mean;
- max;
- min;
- standard deviation;
và degree-dependent scalers.
Ý tưởng:
Một node degree 2 và node degree 200 có thống kê neighborhood rất khác; một aggregator duy nhất có thể không đủ.
PNA thường hữu ích khi dự đoán tính chất đồ thị, và là lựa chọn message passing trong kiến trúc lai như GraphGPS.
9. Graph-level prediction: GNN layer mới chỉ là nửa đầu
Sau lớp, mỗi nút có một vector, và tập các vector đó vẫn còn gắn với từng nút:
Phân loại cả đồ thị cần một vector không phụ thuộc số nút. Readout là phép gộp mọi vector nút thành vector đó:
9.1 Global sum/mean/max pooling
Tổng mọi vector nút giữ lại thông tin về số lượng:
Trung bình chia tổng đó cho số nút, nên ít bị kéo bởi đồ thị lớn hơn:
sum: nhạy với kích thước/count;mean: ổn định hơn khi graph size khác nhau;max: giữ feature nổi bật nhất.
9.2 Virtual/global node
Thêm một node đặc biệt nối tới mọi node:
Sau vài lớp, nút toàn cục có thể thành biểu diễn của cả đồ thị.
9.3 Attention/readout học được
Nếu chỉ một vài nút quyết định đầu ra, readout có thể là tổng có trọng số học được:
hữu ích nếu chỉ một số substructure quyết định output.
10. Link prediction: encoder và decoder là hai phần khác nhau
Một pipeline phổ biến:
- GNN encoder tạo node embedding ;
- decoder chấm điểm cặp node.
10.1 Dot-product decoder
Điểm của một cặp là tích vô hướng của hai embedding. Cặp cùng hướng cho điểm cao:
Xác suất cạnh là một hàm sigmoid của điểm đó:
10.2 MLP decoder
Một MLP trên hai embedding đã nối với nhau cho điểm linh hoạt hơn tích vô hướng:
10.3 Bilinear / relation-aware decoder
Knowledge graph có quan hệ mang kiểu riêng. Một ma trận cho từng kiểu quan hệ đổi cách chấm điểm:
hoặc dùng họ decoder như DistMult/ComplEx/RotatE.
Điểm rất dễ sai: nếu edge cần dự đoán vẫn nằm trong message-passing graph, model có thể “thấy đáp án”. Link prediction cần split edge cẩn thận.
11. Homophily và heterophily: graph không phải lúc nào cũng “hàng xóm giống nhau”
11.1 Homophily
Node nối nhau có xu hướng giống nhau.
Ví dụ citation:
- paper ML thường cite paper ML;
- paper systems thường cite systems.
GCN smoothing thường phù hợp.
11.2 Heterophily
Neighbor có thể khác class hoặc feature.
Ví dụ:
- buyer nối seller;
- fraud account tương tác với normal account;
- protein loại này tương tác protein loại khác;
- user-item bipartite graph.
Nếu label của node thường khác neighbor, phép “average neighbor” có thể pha loãng signal.
11.3 Đừng dùng một con số homophily duy nhất như chân lý
Heterophily là chủ đề nghiên cứu rộng. Có nhiều metric:
- edge homophily;
- node homophily;
- class compatibility;
- feature similarity.
Một graph có thể heterophilic về label nhưng vẫn có structural pattern hữu ích.
11.4 Chiến lược khi heterophily mạnh
- giữ self-feature mạnh hơn;
- tách self và neighbor channels;
- signed/compatibility-aware aggregation;
- higher-order neighborhoods;
- learnable graph rewiring;
- graph transformer / structural encoding;
- luôn so với MLP feature-only.
Thực hành tốt: nếu graph rất heterophilic, “GNN phải tốt hơn MLP” không còn là giả định an toàn.
12. Over-smoothing: càng sâu càng giống nhau
Over-smoothing là các nút trở nên quá giống khi trộn láng giềng nhiều lần. lớp làm trơn có thể viết như lũy thừa của ma trận lan truyền:
Triệu chứng:
- train/val performance tăng rồi giảm khi thêm layer;
- embedding giữa class khác nhau co lại;
- model 8 layer kém model 2 layer dù nhiều capacity hơn.
12.1 Giảm over-smoothing
- residual/skip connection;
- normalization;
- Jumping Knowledge;
- APPNP / personalized propagation;
- decouple feature transformation và propagation;
- không tăng depth nếu task chỉ cần local context.
13. Over-squashing: quá nhiều thông tin bị nén qua cổ chai
Over-squashing là quá nhiều tin từ xa bị ép qua vài cạnh vào một vector có số chiều cố định. Khác over-smoothing: over-smoothing làm nút giống nhau, over-squashing làm mất tin dọc đường. Một nút cách 5 hop phải nén cả vùng nhìn, receptive field, vào vector chiều.
Alon & Yahav gọi đây là over-squashing.
13.1 Phân biệt nhanh
| Vấn đề | Mô tả |
|---|---|
| Over-smoothing | representation của các node trở nên quá giống |
| Over-squashing | quá nhiều thông tin xa phải nén qua bottleneck |
13.2 Hướng khắc phục
- rewiring graph;
- thêm long-range edge;
- virtual/global node;
- global attention;
- positional encoding;
- kiến trúc hybrid local + global.
Đây là một động lực quan trọng cho Graph Transformer hiện đại.
14. Depth không nên chọn theo thói quen
Nếu task node classification phụ thuộc chủ yếu 2-hop context, 20 layer có thể không giúp.
Cách nghĩ tốt hơn:
- cần signal cách target bao xa?
- mỗi layer mở receptive field thêm bao nhiêu?
- graph có degree lớn không?
- có nguy cơ over-smoothing/squashing không?
- có global shortcut hoặc attention không?
Depth của GNN gắn trực tiếp với đường đi thông tin trên graph, không chỉ với “độ phức tạp feature” như MLP.
15. Heterogeneous GNN: nhiều loại node và relation
Ví dụ academic graph:
Một GCN dùng chung cho mọi edge type có thể bỏ mất semantics.
15.1 R-GCN
Relational GCN không dùng chung một ma trận cho mọi kiểu cạnh. Mỗi quan hệ có trọng số riêng, và nút vẫn giữ một nhánh của chính nó:
15.2 HGT
Heterogeneous Graph Transformer dùng attention có tham số phụ thuộc node/edge type, phù hợp heterogeneous graph lớn và giàu semantics.
15.3 Khi cần hetero model thật sự?
Nếu đổi tất cả node type/edge type thành một loại làm mất ý nghĩa quan trọng, dùng HeteroData + relation-aware architecture hợp lý hơn.
16. Temporal / dynamic graph: edge còn có thời gian
Nhiều đồ thị không đứng yên: mỗi sự kiện là một cặp nút, một mốc thời gian, và có thể thêm feature của cạnh.
Ví dụ:
- giao dịch ngân hàng;
- user click item;
- message giữa tài khoản;
- network traffic.
Nếu ta collapse tất cả event trong 1 năm thành một static graph, model có thể làm mất:
- thứ tự;
- recency;
- thời gian giữa event.
Temporal GNN như TGN thường kết hợp:
- node memory;
- temporal encoding;
- message function;
- neighborhood aggregation.
Nếu câu hỏi có dạng “sau sự kiện nào, trong bao lâu, theo thứ tự nào”, static GNN có thể không đủ.
17. Geometric / 3D GNN: graph structure chưa chắc là toàn bộ hình học
Trong molecule hoặc physical system, tọa độ 3D quan trọng.
Một model tốt có thể cần tôn trọng symmetry:
- translation;
- rotation;
- reflection tùy task.
Đây dẫn tới equivariant GNN và geometric deep learning, ví dụ SchNet, EGNN, SE(3)-Transformer, NequIP.
Không nên coi “molecule = graph” rồi bỏ hết geometry nếu target phụ thuộc mạnh vào cấu hình 3D.
18. Bảng chọn model theo tình huống
| Tình huống | Baseline đầu tiên | Bước nâng cấp hợp lý |
|---|---|---|
| Node classification, graph nhỏ, homophily tốt | MLP + GCN | GraphSAGE/GAT |
| Graph lớn, cần mini-batch | GraphSAGE | PNA / scalable GNN |
| Neighbor relevance khác nhau | GAT | GATv2 / local-global hybrid |
| Edge feature quan trọng | GINE / MPNN | PNA, domain-specific MPNN |
| Graph classification, cần structural count | GIN | GINE/PNA/GraphGPS |
| Heterophily mạnh | MLP + GNN baseline | heterophily-aware / rewiring / transformer |
| Heterogeneous graph | relation-aware baseline | R-GCN / HGT |
| Dynamic events | temporal baseline | TGN / temporal attention |
| Long-range dependency | MPNN baseline | virtual node / Graph Transformer / GPS |
| 3D geometry | MPNN + coordinates | equivariant GNN |
Bảng này không phải luật cứng. Nó là thứ tự thử nghiệm có kiểm soát.
19. Baseline ladder: cách làm thực nghiệm không bị “model chasing”
Một ladder tốt:
Bước 0 — majority / heuristic
Để biết bài toán có quá lệch class hay không.
Bước 1 — MLP feature-only
Baseline không dùng cạnh chỉ biến đổi vector của từng nút:
Nếu MLP đã rất mạnh, graph có thể chỉ thêm ít signal.
Bước 2 — GCN
Kiểm tra connectivity có giúp không.
Bước 3 — model phù hợp inductive bias
- GraphSAGE nếu scale;
- GAT nếu weighting neighbor;
- GINE nếu edge attr;
- GIN nếu graph-level structural pattern.
Bước 4 — modern/hybrid model
Chỉ sau khi hiểu baseline và bottleneck.
Nếu đổi đồng thời model, split, hidden size, optimizer, augmentation và metric thì không biết improvement đến từ đâu.
20. Một quyết định model nên dựa trên dữ liệu nào?
Trước khi chọn model, thống kê ít nhất:
Cấu trúc
- : số node;
- : số edge;
- degree mean/median/max;
- connected components;
- directed/undirected;
- self-loop, multi-edge.
Feature
- node feature dimension;
- missing feature;
- edge attribute;
- categorical/numerical/text.
Label/task
- node/link/graph;
- class balance;
- temporal split hay random split;
- inductive hay transductive.
Signal graph
- homophily/compatibility;
- shortest-path statistics;
- graph size distribution;
- edge semantics có đáng tin không.
21. Debug bằng ablation thay vì đoán
Ba ablation rất hữu ích:
21.1 Bỏ graph
MLP feature-only.
21.2 Xáo edge
Giữ số edge/degree tương tự nhưng phá quan hệ thật. Nếu performance không giảm, graph structure có thể không mang signal như kỳ vọng.
21.3 Bỏ feature
Dùng constant feature hoặc structural feature đơn giản. Nếu model vẫn mạnh, topology có thể là nguồn signal chính.
Từ ba thử nghiệm trên ta biết model đang dựa vào:
- feature;
- topology;
- hay cả hai.
22. Attention và giải thích: cần phân biệt
GAT tạo nhưng không nên kết luận:
“Edge có attention lớn là nguyên nhân model dự đoán class này.”
Muốn giải thích GNN, có thể dùng:
- gradient attribution;
- integrated gradients;
- GNNExplainer;
- PGExplainer;
- subgraph extraction;
- counterfactual explanation.

Attribution trên node/edge và trích xuất subgraph liên quan. Nguồn: Sanchez-Lengeling et al., Distill (2021), CC-BY 4.0.
23. Những ý mang đi
GCN là baseline khi láng giềng thường giống nhau. GraphSAGE học hàm gộp và có thể lấy mẫu, hợp nút mới. GAT học trọng số từng láng giềng, không phải giải thích nhân quả. GIN dùng tổng và MLP để giữ số lần lặp. Cạnh có kiểu thì dùng MPNN hoặc GINE.
Over-smoothing làm nút quá giống. Over-squashing nén tin xa vào vector cố định. Heterophily, láng giềng khác nhãn, có thể làm loãng tín hiệu. Hãy có MLP không dùng cạnh trước khi đổi kiến trúc.
Bài sau đưa các lựa chọn này vào PyTorch Geometric, bắt đầu từ một lỗi chia dữ liệu.
25. Tài liệu tham khảo và đọc thêm
- T. N. Kipf, M. Welling, Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017. https://arxiv.org/abs/1609.02907
- W. Hamilton, R. Ying, J. Leskovec, Inductive Representation Learning on Large Graphs, NeurIPS 2017. https://arxiv.org/abs/1706.02216
- P. Veličković et al., Graph Attention Networks, ICLR 2018. https://arxiv.org/abs/1710.10903
- K. Xu et al., How Powerful are Graph Neural Networks?, ICLR 2019. https://arxiv.org/abs/1810.00826
- J. Gilmer et al., Neural Message Passing for Quantum Chemistry, ICML 2017. https://arxiv.org/abs/1704.01212
- G. Corso et al., Principal Neighbourhood Aggregation for Graph Nets, NeurIPS 2020. https://arxiv.org/abs/2004.05718
- U. Alon, E. Yahav, On the Bottleneck of Graph Neural Networks and its Practical Implications, ICLR 2021. https://arxiv.org/abs/2006.05205
- C. Gong et al., A Survey on Learning from Graphs with Heterophily, 2024. https://arxiv.org/abs/2401.09769
- M. Fey, J. E. Lenssen et al., PyTorch Geometric, documentation and project. https://pytorch-geometric.readthedocs.io/