Mạng Nơ-ron Đồ Thị (Graph Neural Networks)¶

Mạng nơ-ron đồ thị (GNN) học từ dữ liệu có cấu trúc đồ thị bằng cách truyền thông điệp giữa các nút kết nối. File này bao gồm khuôn khổ truyền thông điệp (message-passing), GCN, GraphSAGE, GIN, quá mượt (over-smoothing), gộp đồ thị (graph pooling), và các tác vụ cấp nút/cạnh/đồ thị — những kiến trúc cốt lõi cung cấp sức mạnh cho dự đoán tính chất phân tử, phân tích mạng xã hội, và hệ thống gợi ý.

Trong các file trước, chúng ta đã thiết lập các nền tảng toán học: học sâu hình học (file 1) bảo chúng ta khai thác các đối xứng, và lý thuyết đồ thị (file 2) cho chúng ta ngôn ngữ của các nút, cạnh, và ma trận kề. Bây giờ chúng ta xây dựng các mạng nơ-ron hoạt động trực tiếp trên đồ thị.
Thách thức cốt lõi: dữ liệu đồ thị không đều (irregular). Không giống như ảnh (lưới cố định) hay chuỗi (thứ tự cố định), đồ thị có số lượng nút thay đổi, tính kết nối thay đổi, và không có thứ tự nút chuẩn tắc. Một mạng nơ-ron cho đồ thị phải xử lý tất cả những điều này trong khi vẫn tương đẳng với hoán vị (gán lại nhãn các nút không nên thay đổi đầu ra).

Khuôn Khổ Truyền Thông Điệp (The Message-Passing Framework)¶

Hầu như tất cả các GNN đều tuân theo cùng một công thức, gọi là truyền thông điệp (message passing) (còn gọi là tập hợp lân cận — neighbourhood aggregation). Ý tưởng đơn giản và tao nhã: mỗi nút cập nhật biểu diễn của nó bằng cách thu thập thông tin từ các hàng xóm của nó.
Tại mỗi tầng \(l\), mọi nút \(i\) thực hiện ba việc:
1. Thông điệp (Message): mỗi hàng xóm \(j\) của nút \(i\) tính một thông điệp \(\mathbf{m}_{j \to i}\) dựa trên các đặc trưng hiện tại của nó.
2. Tập hợp (Aggregate): nút \(i\) thu thập tất cả các thông điệp đến và kết hợp chúng bằng một hàm bất biến với hoán vị (tổng, trung bình, hoặc max).
3. Cập nhật (Update): nút \(i\) kết hợp thông điệp đã tập hợp với các đặc trưng của chính nó để tạo ra một biểu diễn mới.
Một cách hình thức:

\[\mathbf{m}_i^{(l)} = \bigoplus_{j \in \mathcal{N}(i)} \phi^{(l)}\left(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{e}_{ij}\right)\]

\[\mathbf{h}_i^{(l+1)} = \psi^{(l)}\left(\mathbf{h}_i^{(l)}, \mathbf{m}_i^{(l)}\right)\]

trong đó \(\mathcal{N}(i)\) là tập hợp hàng xóm của nút \(i\), \(\bigoplus\) là một phép tập hợp bất biến với hoán vị (tổng, trung bình, max), \(\phi\) là hàm thông điệp, \(\psi\) là hàm cập nhật, và \(\mathbf{e}_{ij}\) là đặc trưng cạnh tùy chọn.

Truyền thông điệp: các hàng xóm gửi thông điệp, một hàm bất biến với hoán vị tập hợp chúng, và nút cập nhật các đặc trưng của nó

Phép tập hợp \(\bigoplus\) phải bất biến với hoán vị (thứ tự các hàng xóm được xử lý không quan trọng) để đảm bảo toàn bộ hàm là tương đẳng với hoán vị. Điều này hiện thực hóa trực tiếp nguyên lý đối xứng từ file 1.
Sau \(k\) tầng truyền thông điệp, biểu diễn của mỗi nút mã hóa thông tin từ lân cận \(k\) bước nhảy (\(k\)-hop neighbourhood) của nó: tất cả các nút có thể đến được trong \(k\) cạnh. Tầng 1 thấy các hàng xóm trực tiếp, tầng 2 thấy hàng xóm của hàng xóm, và cứ thế tiếp tục. Đây là cách thông tin cục bộ lan truyền để xây dựng sự hiểu biết toàn cục.
Trường tiếp nhận (receptive field) của một GNN tăng lên theo độ sâu, giống như trường tiếp nhận của CNN tăng lên theo số tầng (chương 8). Nhưng không giống CNN trên lưới đều, hình dạng trường tiếp nhận thay đổi tùy theo nút tùy thuộc vào cấu trúc đồ thị.

Mạng Tích Chập Đồ Thị (GCN — Graph Convolutional Network)¶

GCN (Kipf & Welling, 2017) là kiến trúc GNN nền tảng. Nó đơn giản hóa tích chập đồ thị phổ (từ file 2) thành một công thức thanh lịch, hiệu quả.
Bắt đầu từ tích chập phổ \(g_\theta \star \mathbf{x} = U \, \text{diag}(\hat{g}_\theta) \, U^T \mathbf{x}\), Kipf và Welling xấp xỉ bộ lọc phổ bằng một đa thức Chebyshev bậc một, tránh hoàn toàn việc tính phân rã trị riêng. Sau khi đơn giản hóa, phép cập nhật theo từng tầng trở thành:

\[H^{(l+1)} = \sigma\left(\hat{A} H^{(l)} W^{(l)}\right)\]

trong đó:
- \(H^{(l)} \in \mathbb{R}^{n \times d}\) là ma trận các đặc trưng nút tại tầng \(l\)
- \(W^{(l)} \in \mathbb{R}^{d \times d'}\) là một ma trận trọng số học được
- \(\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\) là ma trận kề được chuẩn hóa đối xứng có vòng tự thân
- \(\tilde{A} = A + I\) thêm vòng tự thân (để mỗi nút cũng nhận thông điệp của chính nó)
- \(\tilde{D}\) là ma trận bậc của \(\tilde{A}\)
- \(\sigma\) là một hàm kích hoạt phi tuyến (ReLU, như trong chương 6)
Phép nhân ma trận \(\hat{A} H^{(l)}\) là bước tập hợp: với mỗi nút, nó tính trung bình có trọng số các đặc trưng của hàng xóm (cộng với của chính nó, qua vòng tự thân). Ma trận trọng số \(W^{(l)}\) là phép biến đổi học được, được chia sẻ trên tất cả các nút. Hàm kích hoạt thêm tính phi tuyến.
Điều này thật sự đơn giản: nó chỉ là phép nhân ma trận theo sau bởi một ánh xạ tuyến tính học được và hàm kích hoạt. Toàn bộ tầng GCN có thể được viết trong một dòng code. Việc chuẩn hóa bằng \(\tilde{D}^{-1/2}\) ngăn các nút có nhiều hàng xóm chiếm ưu thế: các nút bậc cao có thông điệp được thu nhỏ lại.
Trong khuôn khổ truyền thông điệp, GCN dùng:
- Thông điệp: \(\phi(\mathbf{h}_j) = \mathbf{h}_j\) (chỉ gửi đặc trưng của bạn)
- Tập hợp: tổng được chuẩn hóa (có trọng số theo bậc)
- Cập nhật: phép biến đổi tuyến tính + hàm kích hoạt

GraphSAGE¶

GCN là thuyết quy nạp (transductive): nó yêu cầu toàn bộ đồ thị trong quá trình huấn luyện và không thể xử lý các nút mới, chưa thấy. Nếu một người dùng mới tham gia mạng xã hội, GCN phải được huấn luyện lại trên toàn bộ đồ thị. GraphSAGE (Hamilton et al., 2017) khắc phục điều này bằng một cách tiếp cận quy nạp (inductive).
Ý tưởng chính là lấy mẫu lân cận (neighbourhood sampling): thay vì dùng tất cả hàng xóm, lấy mẫu một tập hợp con có kích thước cố định. Điều này làm tính toán độc lập với cấu trúc đồ thị đầy đủ và cho phép tổng quát hóa cho các nút và đồ thị chưa thấy.
Phép cập nhật GraphSAGE cho nút \(i\):

\[\mathbf{h}_i^{(l+1)} = \sigma\left(W^{(l)} \cdot \text{CONCAT}\left(\mathbf{h}_i^{(l)}, \text{AGG}\left(\{\mathbf{h}_j^{(l)} : j \in \mathcal{S}(i)\}\right)\right)\right)\]

trong đó \(\mathcal{S}(i)\) là một tập hợp con hàng xóm được lấy mẫu (ví dụ: lấy mẫu ngẫu nhiên 10 trong số 500 hàng xóm). Phép CONCAT tách biệt rõ ràng các đặc trưng của nút khỏi các đặc trưng hàng xóm đã tập hợp, cho phép mạng học các phép biến đổi khác nhau cho "tự thân" và "lân cận."
GraphSAGE hỗ trợ nhiều hàm tập hợp:
- Mean (trung bình): \(\text{AGG} = \frac{1}{|\mathcal{S}|} \sum_{j \in \mathcal{S}} \mathbf{h}_j\) (đơn giản, hiệu quả)
- LSTM: đưa các hàng xóm đã lấy mẫu qua một LSTM (nhưng điều này đưa vào sự phụ thuộc thứ tự, vi phạm một phần tính bất biến với hoán vị)
- Pool: \(\text{AGG} = \max(\{\sigma(W_{\text{pool}} \mathbf{h}_j + \mathbf{b})\})\) (biến đổi phi tuyến sau đó lấy max)
Chiến lược lấy mẫu làm GraphSAGE có thể mở rộng cho các đồ thị rất lớn. Huấn luyện dùng các mini-batch nút: với mỗi nút mục tiêu, lấy mẫu \(k_1\) hàng xóm tại tầng 1, sau đó \(k_2\) hàng xóm của mỗi nút đó tại tầng 2. Với \(k_1 = k_2 = 10\) và 2 tầng, cây tính toán của mỗi nút có nhiều nhất \(10 \times 10 = 100\) nút, bất kể kích thước đồ thị.

Mạng Đẳng Cấu Đồ Thị (GIN — Graph Isomorphism Network)¶

Các kiến trúc GNN khác nhau có sức mạnh biểu cảm (expressive power) khác nhau: khả năng phân biệt các đồ thị có cấu trúc khác nhau. GCN và GraphSAGE, mặc dù hiệu quả trong thực tế, được chứng minh là bị giới hạn trong những cấu trúc đồ thị mà chúng có thể phân biệt.
Công cụ lý thuyết để đo sức mạnh biểu cảm của GNN là kiểm tra Weisfeiler-Lehman (WL), một thuật toán cổ điển để kiểm tra đẳng cấu đồ thị (hai đồ thị có cấu trúc giống hệt nhau hay không). Kiểm tra WL lặp đi lặp lại tinh chỉnh nhãn nút bằng cách băm nhãn của mỗi nút cùng với đa tập (multiset) các nhãn hàng xóm của nó.
GIN (Xu et al., 2019) được thiết kế để có sức mạnh biểu cảm ngang với kiểm tra WL, làm cho nó trở thành GNN truyền thông điệp mạnh mẽ nhất (trong các giới hạn lý thuyết của truyền thông điệp). Ý tưởng chính: hàm tập hợp phải đơn ánh (injective) trên các đa tập (các đa tập đặc trưng hàng xóm khác nhau phải tạo ra các giá trị đã tập hợp khác nhau).
Tổng hợp bằng tổng là đơn ánh trên các đa tập (tổng của \(\{1, 1, 2\}\) cho 4, trong khi \(\{1, 3\}\) cũng cho 4, nhưng trên các vector đặc trưng với đủ số chiều, tổng của các đa tập khác nhau thì nói chung là phân biệt được). Trung bình và max không đơn ánh: trung bình không thể phân biệt \(\{1, 1\}\) với \(\{2, 2\}\), và max không thể phân biệt \(\{1, 2, 3\}\) với \(\{1, 1, 3\}\).
Phép cập nhật GIN là:

\[\mathbf{h}_i^{(l+1)} = \text{MLP}^{(l)}\left((1 + \epsilon^{(l)}) \cdot \mathbf{h}_i^{(l)} + \sum_{j \in \mathcal{N}(i)} \mathbf{h}_j^{(l)}\right)\]

trong đó \(\epsilon\) là một vô hướng học được (hoặc cố định bằng 0) và MLP cung cấp ánh xạ phi tuyến, đơn ánh. Phép tổng hợp bảo toàn cấu trúc đa tập, và MLP có thể học để phân biệt bất kỳ hai giá trị đã tập hợp nào khác nhau.

Quá Mượt (Over-Smoothing)¶

Một thách thức lớn trong GNN là quá mượt (over-smoothing): khi số tầng tăng lên, tất cả các biểu diễn nút hội tụ về cùng một giá trị, mất khả năng phân biệt các nút khác nhau.

Quá mượt: các đặc trưng nút riêng biệt ở tầng 1 dần hòa lẫn vào các đặc trưng đồng nhất ở các tầng sâu hơn

Cơ chế này trực quan. Mỗi tầng truyền thông điệp lấy trung bình các đặc trưng của một nút với hàng xóm của nó. Sau nhiều vòng lấy trung bình, mọi nút đã "thấy" (và hòa lẫn với) mọi nút khác trong thành phần liên thông của nó. Các đặc trưng trở thành một trung bình đồng nhất, tương đương đồ thị của việc làm mờ một ảnh quá nhiều lần cho đến khi nó trở thành một màu đồng nhất.
Một cách hình thức, áp dụng lặp đi lặp lại ma trận kề chuẩn hóa \(\hat{A}\) hội tụ về một ma trận hạng 1 (mọi hàng trở thành tỷ lệ với phân bố dừng của một bước đi ngẫu nhiên trên đồ thị). Đây là cùng sự hội tụ như lặp quyền (power iteration) tiến tới vector riêng trội (chương 2).
Quá mượt giới hạn GNN ở độ sâu nông (thường 2-4 tầng), không giống CNN và transformer được hưởng lợi từ hàng chục hoặc hàng trăm tầng. Điều này nghĩa là mỗi nút chỉ có thể thấy một lân cận hạn chế, điều có vấn đề cho các tác vụ yêu cầu thông tin tầm xa.
Các biện pháp giảm thiểu bao gồm:
- Kết nối dư (Residual connections) (từ ResNets, chương 8): \(\mathbf{h}_i^{(l+1)} = \mathbf{h}_i^{(l+1)} + \mathbf{h}_i^{(l)}\), bảo toàn thông tin từ các tầng trước.
- Jumping knowledge: nối (concatenate) hoặc gộp-chú-ý (attention-pool) các biểu diễn từ tất cả các tầng, không chỉ tầng cuối.
- DropEdge: xóa ngẫu nhiên các cạnh trong quá trình huấn luyện, làm chậm sự lan truyền thông tin.
- Graph Transformers (file 4): vượt qua nút thắt truyền thông điệp cục bộ bằng chú ý toàn cục.

Gộp Đồ Thị (Graph Pooling)¶

Với các tác vụ cấp đồ thị (graph-level tasks) (dự đoán một tính chất của toàn bộ đồ thị, như độc tính của một phân tử), chúng ta cần thu gọn tất cả các biểu diễn nút thành một vector cấp đồ thị duy nhất. Đây là gộp đồ thị (graph pooling), tương đẳng đồ thị của gộp trung bình toàn cục trong CNN (chương 8).
Cách tiếp cận đơn giản nhất là readout: áp dụng một hàm bất biến với hoán vị lên tập hợp tất cả các đặc trưng nút:

\[\mathbf{h}_G = \text{READOUT}(\{\mathbf{h}_i^{(L)} : i \in V\}) = \sum_i \mathbf{h}_i^{(L)} \quad \text{hoặc} \quad \frac{1}{|V|} \sum_i \mathbf{h}_i^{(L)} \quad \text{hoặc} \quad \max_i \mathbf{h}_i^{(L)}\]

Đây là sự gộp kiểu DeepSets từ file 1, được áp dụng sau tầng GNN cuối cùng. Tổng bảo toàn thông tin kích thước (một đồ thị với 100 nút sẽ có tổng lớn hơn một đồ thị với 10 nút), trong khi trung bình chuẩn hóa theo kích thước.
Gộp phân cấp (hierarchical pooling) dần dần làm thô đồ thị (coarsen), phản chiếu cách CNN dần dần giảm mẫu ảnh. Ở mỗi cấp, các nhóm nút được gộp thành "các siêu nút":
DiffPool (Differentiable Pooling — Gộp khả vi) học một ma trận gán mềm \(S^{(l)} \in \mathbb{R}^{n_l \times n_{l+1}}\) gán mỗi nút cho một cụm:

\[X^{(l+1)} = S^{(l)T} H^{(l)}, \quad A^{(l+1)} = S^{(l)T} A^{(l)} S^{(l)}\]

Ma trận gán được dự đoán bởi một GNN riêng biệt, làm cho việc phân cụm có thể vi phân end-to-end. Điều này tạo ra một hệ thống phân cấp: đồ thị gốc → một đồ thị thô hơn với ít nút hơn → một đồ thị thậm chí thô hơn → một nút duy nhất (biểu diễn đồ thị).
TopKPool dùng một cách tiếp cận đơn giản hơn: học một điểm số vô hướng cho mỗi nút, giữ lại \(k\) nút có điểm cao nhất, và loại bỏ phần còn lại. Đây là một lựa chọn cứng (không phải gán mềm) và rẻ hơn về tính toán so với DiffPool.

Đồ Thị Không Thuần Nhất (Heterogeneous Graphs)¶

Tất cả các GNN cho đến nay đều giả định một đồ thị thuần nhất (homogeneous graph): một loại nút, một loại cạnh. Nhưng hầu hết các đồ thị thế giới thực là không thuần nhất (heterogeneous): nhiều loại nút và nhiều loại cạnh. Một đồ thị tri thức có các nút người, nút tổ chức, và nút địa điểm, được kết nối bởi các cạnh "làm việc tại," "sinh ra tại," và "nằm tại." Một hệ thống gợi ý có các nút người dùng và nút mặt hàng được kết nối bởi các cạnh "đã mua," "đã xem," và "đã đánh giá."
Một đồ thị không thuần nhất có một lược đồ (schema) (còn gọi là metagraph) xác định các loại nút và loại cạnh được phép. Mỗi loại cạnh kết nối một loại nguồn cụ thể với một loại đích cụ thể. Ví dụ, "làm việc tại" kết nối Person → Organisation.
R-GCN (Relational GCN) (Schlichtkrull et al., 2018) xử lý các cạnh không thuần nhất bằng cách dùng một ma trận trọng số riêng cho mỗi loại cạnh:

\[\mathbf{h}_i^{(l+1)} = \sigma\left(\sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_r(i)} \frac{1}{|\mathcal{N}_r(i)|} W_r^{(l)} \mathbf{h}_j^{(l)} + W_0^{(l)} \mathbf{h}_i^{(l)}\right)\]

trong đó \(\mathcal{R}\) là tập hợp các loại cạnh, \(\mathcal{N}_r(i)\) là tập hợp các hàng xóm được kết nối với nút \(i\) qua quan hệ \(r\), và \(W_r\) là ma trận trọng số cụ thể cho quan hệ \(r\). Kết nối tự thân \(W_0\) xử lý các đặc trưng của nút một cách riêng biệt.
Vấn đề: với nhiều loại quan hệ, số lượng tham số bùng nổ (một ma trận \(d \times d\) cho mỗi quan hệ). R-GCN giảm thiểu điều này bằng phân rã cơ sở (basis decomposition): \(W_r = \sum_{b=1}^{B} a_{rb} V_b\), trong đó \(V_b\) là các ma trận cơ sở chia sẻ và \(a_{rb}\) là các hệ số vô hướng cho mỗi quan hệ. Điều này tương tự như phân rã hạng thấp (chương 2): các ma trận đặc thù cho quan hệ nằm trong một không gian con chiều thấp.
HGT (Heterogeneous Graph Transformer) (Hu et al., 2020) áp dụng cơ chế chú ý cho các đồ thị không thuần nhất. Ý tưởng chính là chú ý nên phụ thuộc vào cả loại nút và loại cạnh kết nối chúng. HGT dùng các ma trận chiếu đặc thù cho loại (type-specific) cho query, key, và value:

\[\text{Attention}(i, j) = \left(W_{\tau(i)}^Q \mathbf{h}_i\right)^T \cdot \frac{W_{\phi(i,j)}^{\text{ATT}}}{\sqrt{d}} \cdot \left(W_{\tau(j)}^K \mathbf{h}_j\right)\]

trong đó \(\tau(i)\) là loại của nút \(i\) và \(\phi(i,j)\) là loại cạnh giữa chúng. Điều này đảm bảo mô hình chú ý khác nhau đến các loại quan hệ khác nhau: một bài báo chú ý đến các tác giả của nó nên dùng trọng số chú ý khác so với khi chú ý đến các tài liệu tham khảo của nó.
Các phương pháp dựa trên metapath (Metapath-based methods) xác định các đường dẫn có ý nghĩa qua lược đồ (ví dụ: Author → Paper → Author cho đồng tác giả) và tập hợp thông tin dọc theo các đường dẫn này. HAN (Heterogeneous Attention Network) áp dụng chú ý ở hai mức: trong mỗi metapath (những hàng xóm nào dọc theo đường dẫn này quan trọng?) và giữa các metapath (những mẫu quan hệ nào quan trọng?).

Dự Đoán Liên Kết và Hoàn Thiện Đồ Thị Tri Thức (Link Prediction and Knowledge Graph Completion)¶

Dự đoán liên kết (Link prediction) đặt câu hỏi: với các cạnh hiện có, những cạnh bị thiếu nào có khả năng tồn tại? Đây là tác vụ cốt lõi cho hoàn thiện đồ thị tri thức (dự đoán các sự thật bị thiếu), gợi ý (dự đoán mặt hàng nào người dùng sẽ thích), và phân tích mạng xã hội (dự đoán các tình bạn tương lai).
Các phương pháp dựa trên embedding (Embedding-based methods) học một vector cho mỗi thực thể và một phép biến đổi cho mỗi quan hệ, sau đó chấm điểm các cạnh tiềm năng bằng cách chúng phù hợp với nhau đến đâu:
TransE mô hình hóa các quan hệ như các phép tịnh tiến trong không gian embedding: nếu \((h, r, t)\) là một bộ ba hợp lệ (thực thể đầu, quan hệ, thực thể đuôi), thì \(\mathbf{h} + \mathbf{r} \approx \mathbf{t}\). Hàm chấm điểm là \(f(h, r, t) = -\|\mathbf{h} + \mathbf{r} - \mathbf{t}\|\). Một cách trực giác, vector quan hệ "di chuyển" thực thể đầu đến thực thể đuôi trong không gian embedding.
RotatE mô hình hóa các quan hệ như các phép quay trong không gian phức: \(\mathbf{t} = \mathbf{h} \circ \mathbf{r}\), trong đó \(\circ\) là phép nhân theo từng phần tử phức và \(|\mathbf{r}_i| = 1\) (các số phức đơn vị là các phép quay). Điều này có thể mô hình hóa các mẫu đối xứng, phản xạ, đảo, và hợp thành mà TransE không thể.
ComplEx dùng các embedding có giá trị phức với một tích vô hướng Hermitian, cho phép nó mô hình hóa các quan hệ không đối xứng (nếu A là sếp của B, B không phải là sếp của A).
Dự đoán liên kết dựa trên GNN tính các embedding nút với truyền thông điệp, sau đó chấm điểm các cạnh dùng các embedding đầu mút. Điều này kết hợp lập luận cấu trúc của GNN với mô hình hóa quan hệ của các phương pháp embedding. Bộ mã hóa GNN nắm bắt cấu trúc lân cận đa bước nhảy mà các phương pháp embedding đơn lẻ bỏ lỡ.

Các Loại Tác Vụ (Task Types)¶

GNN giải quyết ba loại tác vụ:
Tác vụ cấp nút (Node-level tasks): dự đoán một tính chất cho mỗi nút. Ví dụ: phân lớp người dùng trong mạng xã hội (bot hay người), dự đoán chức năng của mỗi protein trong mạng tương tác, phân lớp nút bán giám sát (gán nhãn một vài nút, dự đoán phần còn lại). Đầu ra là embedding nút \(\mathbf{h}_i^{(L)}\) được đưa qua một bộ phân lớp.
Tác vụ cấp cạnh (Edge-level tasks): dự đoán một tính chất cho mỗi cạnh hoặc dự đoán một cạnh có tồn tại hay không. Ví dụ: dự đoán liên kết (hai người dùng này có trở thành bạn không?), hoàn thiện đồ thị tri thức (quan hệ này có giữ giữa các thực thể này không?), dự đoán tương tác thuốc-thuốc. Đầu ra thường dùng các embedding của cả hai nút đầu mút: \(\hat{y}_{ij} = f(\mathbf{h}_i, \mathbf{h}_j)\), trong đó \(f\) là tích vô hướng, nối-concat + MLP, hoặc sự kết hợp khác.
Tác vụ cấp đồ thị (Graph-level tasks): dự đoán một tính chất cho toàn bộ đồ thị. Ví dụ: dự đoán tính chất phân tử (phân tử này có độc không?), phân lớp đồ thị (mạng xã hội này có phải là mạng bot không?), sinh đồ thị (thiết kế một phân tử có tính chất mong muốn). Đầu ra dùng gộp đồ thị để tạo ra \(\mathbf{h}_G\), sau đó được phân lớp hoặc hồi quy.

Bài tập lập trình (dùng CoLab hoặc notebook)¶

Cài đặt một tầng GCN đơn từ đầu dùng ma trận kề chuẩn hóa. Áp dụng nó lên một đồ thị nhỏ và quan sát các đặc trưng nút được làm mượt như thế nào.

import jax
import jax.numpy as jnp

# Graph: 5 nodes, simple chain with a branch
A = jnp.array([[0, 1, 0, 0, 0],
               [1, 0, 1, 0, 0],
               [0, 1, 0, 1, 1],
               [0, 0, 1, 0, 0],
               [0, 0, 1, 0, 0]], dtype=float)

# Add self-loops
A_hat = A + jnp.eye(5)
D_hat = jnp.diag(A_hat.sum(axis=1))
D_inv_sqrt = jnp.diag(1.0 / jnp.sqrt(A_hat.sum(axis=1)))
A_norm = D_inv_sqrt @ A_hat @ D_inv_sqrt

# Node features: one-hot identity
H = jnp.eye(5)

# Weight matrix (random initialisation)
rng = jax.random.PRNGKey(0)
W = jax.random.normal(rng, (5, 3)) * 0.5

# GCN layer: H' = ReLU(A_norm @ H @ W)
H_new = jax.nn.relu(A_norm @ H @ W)

print("Original features (one-hot):")
print(H)
print("\nAfter GCN layer:")
print(jnp.round(H_new, 3))
print("\nNotice: connected nodes now have similar representations")

Cài đặt truyền thông điệp với tập hợp tổng (kiểu GIN) và so sánh với tập hợp trung bình (kiểu GCN). Cho thấy tổng có thể phân biệt các đa tập mà trung bình không thể.

import jax.numpy as jnp

# Two different neighbourhood multisets that have the same mean
# Node A: neighbours have features [1, 1, 1, 1]  (four neighbours, all 1)
# Node B: neighbours have features [2, 2]          (two neighbours, all 2)

neighbours_A = jnp.array([[1.0], [1.0], [1.0], [1.0]])
neighbours_B = jnp.array([[2.0], [2.0]])

# Mean aggregation
mean_A = neighbours_A.mean(axis=0)
mean_B = neighbours_B.mean(axis=0)
print(f"Mean A: {mean_A}, Mean B: {mean_B}, Same: {jnp.allclose(mean_A, mean_B)}")

# Sum aggregation
sum_A = neighbours_A.sum(axis=0)
sum_B = neighbours_B.sum(axis=0)
print(f"Sum A:  {sum_A},  Sum B:  {sum_B},  Same: {jnp.allclose(sum_A, sum_B)}")
print("\nSum distinguishes these multisets; mean does not!")

Minh họa quá mượt. Áp dụng ma trận kề chuẩn hóa lặp đi lặp lại và xem các đặc trưng nút hội tụ.

import jax.numpy as jnp
import matplotlib.pyplot as plt

# Random graph
A = jnp.array([[0,1,1,0,0,0],
               [1,0,1,0,0,0],
               [1,1,0,1,0,0],
               [0,0,1,0,1,1],
               [0,0,0,1,0,1],
               [0,0,0,1,1,0]], dtype=float)

A_hat = A + jnp.eye(6)
D_inv_sqrt = jnp.diag(1.0 / jnp.sqrt(A_hat.sum(axis=1)))
A_norm = D_inv_sqrt @ A_hat @ D_inv_sqrt

# Initial features: distinct per node
H = jnp.array([[1,0], [0,1], [1,1], [-1,0], [0,-1], [-1,-1]], dtype=float)

distances = []
for k in range(20):
    H = A_norm @ H
    # Measure how distinct the features are (std across nodes)
    spread = jnp.std(H, axis=0).mean()
    distances.append(float(spread))

plt.plot(distances, "o-")
plt.xlabel("Number of message-passing rounds")
plt.ylabel("Feature spread (std across nodes)")
plt.title("Over-Smoothing: Features Converge with Depth")
plt.show()