Graph Neural Network (GNN)

Mạng nơ-ron đồ thị (GNN) là một mạng nơ-ron hoạt động trực tiếp trên đồ thị: tập hợp các nút được nối với nhau bằng cạnh, trong đó cả nút và cạnh đều có thể mang đặc trưng. Phân tử (nguyên tử và liên kết), mạng xã hội (người dùng và quan hệ theo dõi), mạng lưới đường bộ (giao lộ và đoạn đường), lưới 3D và khớp của bộ xương người đều là đồ thị. Đồ thị không có lưới hoặc thứ tự cố định, còn mỗi nút có số lượng láng giềng khác nhau; vì vậy, các bộ lọc trượt của mạng nơ-ron tích chập (CNN) và cách đọc tuần tự của mạng nơ-ron hồi tiếp (RNN) không thể áp dụng trực tiếp. GNN xử lý đặc điểm này bằng truyền thông điệp: mỗi nút liên tục cập nhật vector đặc trưng của nó dựa trên đặc trưng của các nút lân cận, tạo ra embedding nút mã hóa cả thuộc tính riêng của nút lẫn vị trí của nút trong đồ thị.

Truyền thông điệp hoạt động như thế nào#

Một layer GNN cập nhật mọi node qua ba bước. Mỗi neighbor gửi một message, thường là phép biến đổi được học từ các feature của node đó. Node tổng hợp các message nhận được bằng một hàm không phụ thuộc vào thứ tự, chẳng hạn tổng, trung bình hoặc giá trị lớn nhất. Sau đó, node kết hợp kết quả tổng hợp với các feature của chính nó để tạo representation mới. Vì phép tổng hợp không phụ thuộc vào thứ tự nên kết quả không bị ảnh hưởng bởi cách đánh số các node. Năm 2017, Justin Gilmer và các cộng sự mô tả nhiều GNN như những trường hợp cụ thể của framework message passing neural network này. Sau layer cuối cùng, một head dành riêng cho tác vụ sử dụng các embedding của node để gán nhãn node, dự đoán cạnh bị thiếu hoặc phân loại toàn bộ graph:

Mỗi layer mở rộng phạm vi quan sát của một node thêm một hop, vì vậy sau k layer, embedding của node phụ thuộc vào mọi node cách nó không quá k cạnh — tức receptive field của node đó trong graph. Đoạn mã PyTorch dưới đây tạo graph đường đi gồm sáu node, áp dụng ba layer tích chập graph với phép chuẩn hóa trong GCN của Thomas Kipf và Max Welling, rồi dùng autograd để liệt kê những node đầu vào ảnh hưởng đến node 0 sau mỗi layer:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

Đoạn mã in ra [0, 1], [0, 1, 2] và [0, 1, 2, 3]: receptive field của node 0 tăng chính xác một hop sau mỗi layer.

Các kiến trúc GNN phổ biến#

• GCN: Mạng tích chập đồ thị tính H′ = σ(D̃^(−1/2) Ã D̃^(−1/2) H W), trong đó Ã là ma trận kề có self-loop và D̃ là ma trận bậc tương ứng: phép tính này lấy trung bình có trọng số theo bậc trên mỗi node cùng các neighbor của node đó, sau đó nhân với ma trận trọng số W dùng chung cho mọi node.
• GraphSAGE: Lấy mẫu một số lượng neighbor cố định cho mỗi node và học hàm tổng hợp, nhờ đó có thể mở rộng cho các graph rất lớn và tạo embedding cho những node xuất hiện sau khi huấn luyện.
• GAT: Mạng attention đồ thị gán trọng số cho mỗi neighbor bằng các điểm số attention được học, thay vì dùng trọng số cố định dựa trên bậc.
• GIN: Mạng đẳng cấu đồ thị cộng các neighbor rồi áp dụng MLP. Keyulu Xu và các cộng sự đã chứng minh rằng cách này giúp mô hình phân biệt graph tốt ngang với phép kiểm tra Weisfeiler-Lehman, giới hạn trên của phương pháp message passing tiêu chuẩn.
• Graph transformer: Áp dụng self-attention trên toàn bộ node và thêm positional encoding suy ra từ cấu trúc graph. Bản thân một transformer tiêu chuẩn cũng là một GNN trên graph đầy đủ kết nối gồm các token.

Việc xếp chồng nhiều layer gây ra hiện tượng over-smoothing: phép tính trung bình lặp đi lặp lại kéo các embedding node lại gần nhau cho đến khi chúng không còn phân biệt được. Vì vậy, nhiều GNN chỉ dùng hai hoặc ba layer, giống như GCN ban đầu với hai layer. PyTorch Geometric và Deep Graph Library (DGL) triển khai các layer này hiệu quả trên danh sách cạnh thưa.

Ứng dụng thực tế#

• Dự báo thời tiết: GraphCast của Google DeepMind, được công bố trên Science năm 2023, thực hiện message passing trên mesh đa tỷ lệ bao phủ toàn cầu và tạo dự báo 10 ngày ở độ phân giải 0.25° trong chưa đầy một phút; mô hình vượt trội hơn các hệ thống xác định vận hành chính xác nhất trên 90% trong số 1.380 mục tiêu đánh giá.
• Khám phá thuốc: Năm 2020, các nhà nghiên cứu MIT huấn luyện một mạng message passing có hướng để dự đoán hoạt tính kháng khuẩn từ graph phân tử, rồi dùng mạng này phát hiện halicin — một hợp chất có cấu trúc khác biệt với các kháng sinh đã biết và tiêu diệt được nhiều vi khuẩn kháng thuốc trong thử nghiệm phòng thí nghiệm.
• Hệ thống gợi ý: PinSage của Pinterest học embedding cho pin từ graph gồm 3 tỷ pin và board cùng 18 tỷ cạnh, được huấn luyện trên 7,5 tỷ mẫu.
• Nhận diện hành động dựa trên skeleton: ST-GCN xem các khớp cơ thể là node, nối chúng với nhau bằng xương trong mỗi frame và với cùng khớp đó ở các frame lân cận, rồi phân loại hành động từ graph không-thời gian thu được. Các model ước lượng pose YOLO26 trả về 17 keypoint COCO cho mỗi người trong từng frame; các tọa độ khớp này là dữ liệu dùng để xây dựng graph skeleton.

GNN và các khái niệm liên quan#

• Knowledge graph: Cấu trúc dữ liệu lưu trữ sự kiện dưới dạng bộ ba thực thể-quan hệ-thực thể. GNN là một model có thể học từ knowledge graph, chẳng hạn để dự đoán các liên kết còn thiếu.
• Học sâu hình học: Lĩnh vực rộng hơn, nghiên cứu các mạng được xây dựng dựa trên tính đối xứng của dữ liệu, bao gồm CNN trên lưới, GNN trên graph và model trên mesh cũng như đa tạp.
• CNN: CNN áp dụng cho ảnh là một trường hợp đặc biệt của message passing trên graph dạng lưới. Mỗi pixel ở đó có cùng số neighbor nằm tại các vị trí tương đối cố định, vì vậy CNN có thể học trọng số riêng cho từng vị trí neighbor — điều mà GNN trên graph không đều không làm được.