Graph Neural Network là gì: cách AI học trên dữ liệu đồ thị

Graph Neural Network (GNN) là lớp mạng nơ-ron được thiết kế riêng cho dữ liệu có cấu trúc đồ thị, nơi các thực thể liên kết với nhau qua những cạnh. Mạng xã hội, phân tử hóa học, hệ thống đường thông hay đồ thị giao dịch đều thuộc nhóm này. GNN học bằng cách truyền thông điệp giữa các nút lân cận, sau mỗi bước lại cập nhật biểu diễn của từng nút dựa trên thông điệp nhận được. Nhờ vậy mô hình nắm được cả cấu trúc cục bộ lẫn toàn cục mà không phụ thuộc vào thứ tự của các nút, điểm quan trọng vì đồ thị hầu như không có thứ tự tự nhiên.

Công thức cơ bản của Message Passing

Sơ đồ một lớp MPNN, biểu diễn mỗi nút được cập nhật sau khi gom điệp từ hàng xóm

Một GNN tiêu chuẩn tuân theo khung Message Passing Neural Network (MPNN), mỗi bước thời gian t gồm hai giai đoạn:

Gửi điệp: mỗi nút u gửi điệp tới các nút lân cận w, tính từ biểu diễn hiện tại của chính nó, của hàng xóm và đặc trưng cạnh nối giữa hai nút: m_u^(t+1) = Σ M_t(h_u^t, h_w^t, e_uw).
Cập nhật nút: mỗi nút tổng hợp toàn bộ điệp nhận được rồi cập nhật biểu diễn của mình: h_v^(t+1) = U_t(h_v^t, m_v^(t+1)).

Hai hàm M_t và U_t là các hàm học được, thường là một mạng nhiều lớp nhỏ. Ở bước cuối, hàm readout R gộp các biểu diễn nút lại để dự đoán ở mức cả đồ thị. Điểm bắt buộc là R phải bất biến theo phép hoán vị: đổi thứ tự khai báo các nút thì kết quả dự đoán không được đổi.

Sơ đồ các khối cấu thành của một Graph Neural Network gồm hàm gửi điệp, cập nhật nút và readout

Các biến thể phổ biến: GCN, GAT, GraphSAGE

Graph Convolutional Network (GCN)

GCN trượt tín hiệu trên ma trận liên kết đã chuẩn hóa. Với A là ma trận liên kết và D là ma trận đường chéo bậc, bài báo gốc của Kipf và Welling dùng phép chuẩn hóa:

Ã = D̃^(−1/2) Ã D̃^(−1/2)

Một lớp GCN đơn giản có dạng H^(l+1) = σ(Ã H^(l) W^(l)), trong đó H là ma trận biểu diễn nút, W là ma trận trọng số học được, và hàm kích hoạt σ thường là ReLU. Mô hình hai lớp của bài báo viết gọn là Z = softmax(Ã ReLU(Ã X W^0) W^1), trong đó X là ma trận đặc trưng đầu vào. Vì Ã không phụ thuộc vào trọng số, nó được tính trước một lần và tái sử dụng cho mọi lớp.

Graph Attention Network (GAT)

GCN coi mọi hàng xóm như nhau, điều không đúng với nhiều đồ thị thực tế. GAT thay ma trận cố định bằng cơ chế tự chú ý để tự học trọng số cho từng cạnh. Hệ số giữa nút i và nút j được chuẩn hóa trên tập lân cận của i:

α_ij = exp(LeakyReLU(a^T [W h_i || W h_j])) / Σ exp(LeakyReLU(a^T [W h_i || W h_k]))

Trong đó a là vectơ trọng số học được, dấu || nối hai vectơ, và LeakyReLU dùng độ dốc âm 0,2. Tham số cấu hình trong bài báo: 8 đầu chú ý ở lớp đầu với 8 đặc trưng mỗi đầu, lớp sau dùng một đầu để sinh số lớp, hệ số chuẩn hóa L2 là 0,0005, dropout 0,6 và tốc độ học 0,005 (là 0,01 với Pubmed).

GraphSAGE

GraphSAGE giải bài toán quy mô bằng cách không lấy toàn bộ hàng xóm. Mỗi vòng lặp, mô hình lấy một mẫu hàng xóm kích thước cố định, rồi tổng hợp bằng một trong ba hàm: trung bình theo phần tử, LSTM, hoặc pooling lấy giá trị lớn nhất. Trong cấu hình của bài báo, số hàng xóm lấy mẫu ở tầng một là 25 và ở tầng hai là 10. Nhờ cách học theo mẫu, GraphSAGE suy luận được cho cả những nút chưa từng xuất hiện trong tập huấn luyện, một tính năng mà GCN không có.

Sơ đồ các cặp đồ thị mà phép thử Weisfeiler-Lehman không phân biệt được

Bộ dữ liệu chuẩn và kết quả đo

Ba bộ dữ liệu kinh điển gồm Cora, Citeseer và Pubmed. Mỗi nút là một tài liệu khoa học, mỗi cạnh là trích dẫn. Cora có 2.708 nút, 5.429 cạnh và 7 lớp; Citeseer có 3.327 nút, 4.732 cạnh và 6 lớp; Pubmed có 19.717 nút, 44.338 cạnh và 3 lớp. Trên Cora, GCN đạt 81,5% độ chính xác và GAT đạt 83,0% theo đúng cách chia tập mà hai bài báo công bố.

Ứng dụng thực tế

Dự đoán tính chất phân tử: trên bộ QM9 gồm khoảng 134.000 phân tử, các mô hình message passing dự đoán đúng cả 13 mục tiêu với độ chính xác hoá học trên 11 trong số đó.
Gợi ý nội dung và kết nối: bài báo GraphSAGE đánh giá mô hình trên mạng xã hội Reddit và cho thấy vector biểu diễn thu được dùng được cho các nút chưa từng xuất hiện trong tập huấn luyện.
Phát hiện gian lận tài chính: nhiều nghiên cứu dùng GNN trên đồ thị đồng nhất và khác nhau để phát hiện chuỗi giao dịch rửa tiền hoặc thao túng thị trường.
Dự đoán lưu lượng giao thông: Graph WaveNet kết hợp đồ thị không gian với chuỗi thời gian để dự báo tốc độ và mật độ phương tiện tại các nút giao thông.

Giới hạn và hướng phát triển

GNN vẫn có ba hạn chế rõ ràng. Một là chất lượng đồ thị đầu vào: thiếu cạnh hoặc gán nhãn sai cạnh làm mô hình học sai cấu trúc. Hai là chi phí tính toán khi đồ thị vượt hàng triệu nút, vì mỗi bước truyền điệp đội với số cạnh. Ba là giới hạn lý thuyết: các thuật toán dựa trên phép thử Weisfeiler-Lehman không phân biệt được một số cặp đồ thị cấu trúc khác nhau, như hình minh họa cho thấy.

Các hướng khắc phục gồm lấy mẫu đồ thị con thay vì toàn bộ đồ thị (GraphSAINT), gom cụm trước rồi huấn luyện (Cluster-GNN), và chuẩn hóa theo kỳ vọng để đồng nhất biểu diễn (PairNorm). Trên thực tế, hầu hết dự án dùng thư viện mã nguồn mở PyTorch Geometric vì nó cung cấp sẵn các lớp GCNConv, SAGEConv, bộ nạp dữ liệu theo lô và hỗ trợ chạy nhiều GPU.

Nguồn tham khảo

Neural Message Passing for Quantum Chemistry (Gilmer và cộng sự) — định nghĩa khung truyền điệp chuẩn và kết quả trên QM9.
Semi-Supervised Classification with Graph Convolutional Networks (Kipf và Welling) — công thức chuẩn hóa ma trận liên kết và mô hình hai lớp.
Graph Attention Networks (Velickovic và cộng sự) — cơ chế tự chú ý, số đầu chú ý và bộ siêu tham số.
Inductive Representation Learning on Large Graphs (Hamilton và cộng sự) — GraphSAGE, lấy mẫu hàng xóm và ba hàm tổng hợp.
Graph WaveNet for Deep Spatial-Temporal Graph Modeling — ứng dụng dự báo giao thông.
Khắc phục vấn đề không nhất quán khi dùng GNN cho phát hiện gian lận.
Tài liệu PyTorch Geometric — thư viện mã nguồn mở phổ biến nhất để huấn luyện GNN.