Mạng Chú Ý Đồ Thị (Graph Attention Networks)¶

Mạng chú ý đồ thị thay thế việc tập hợp hàng xóm đồng đều bằng trọng số học được, phụ thuộc vào dữ liệu. File này bao gồm GAT, chú ý đồ thị đa đầu (multi-head graph attention), GATv2, Graph Transformers, mã hóa vị trí và cấu trúc (positional and structural encodings), và khả năng mở rộng.

Trong GCN (file 3), mỗi nút tập hợp các đặc trưng của hàng xóm dùng trọng số cố định được xác định bởi cấu trúc đồ thị (ma trận kề chuẩn hóa). Một nút với ba hàng xóm cho mỗi hàng xóm trọng số xấp xỉ bằng nhau (\(\approx 1/3\)). Nhưng không phải tất cả hàng xóm đều quan trọng như nhau: một thông điệp từ cộng sự thân cận nên có trọng số hơn một thông điệp từ người quen xa.
Mạng chú ý đồ thị (Graph Attention Networks) giải quyết vấn đề này bằng cách học hàng xóm nào cần chú ý tới, sử dụng cùng cơ chế chú ý (attention) đã cung cấp sức mạnh cho transformer (chương 7). Thay vì trọng số cố định dựa trên cấu trúc, mỗi nút tính toán điểm chú ý động, dựa trên nội dung (content-based) trên các hàng xóm của nó.

GAT: Graph Attention Network¶

GAT (Veličković et al., 2018) tính các hệ số chú ý giữa mỗi nút và hàng xóm của nó. Với nút \(i\) và hàng xóm \(j\):

\[e_{ij} = \text{LeakyReLU}\left(\mathbf{a}^T \left[W\mathbf{h}_i \| W\mathbf{h}_j\right]\right)\]

trong đó \(W \in \mathbb{R}^{d' \times d}\) là một phép biến đổi tuyến tính chia sẻ, \(\|\) là phép nối, và \(\mathbf{a} \in \mathbb{R}^{2d'}\) là một vector chú ý học được. Điểm số \(e_{ij}\) đo lường mức độ quan trọng của các đặc trưng nút \(j\) đối với nút \(i\).
Các điểm số thô được chuẩn hóa trên tất cả các hàng xóm dùng softmax:

\[\alpha_{ij} = \text{softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \exp(e_{ik})}\]

Điều này đảm bảo các trọng số chú ý có tổng bằng 1 trên mỗi lân cận của nút, giống như chú ý trong transformer (chương 7). Các đặc trưng đã cập nhật của nút là:

\[\mathbf{h}_i' = \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij} W\mathbf{h}_j\right)\]

GCN gán trọng số cố định bằng nhau cho tất cả hàng xóm; GAT học trọng số chú ý phụ thuộc vào dữ liệu

Sự khác biệt quan trọng so với GCN: các trọng số \(\alpha_{ij}\) được học từ dữ liệu, không cố định bởi cấu trúc đồ thị. Một nút có thể học để tập trung vào các hàng xóm chứa nhiều thông tin nhất trong khi bỏ qua các hàng xóm nhiễu hoặc không liên quan.
Lưu ý rằng chú ý chỉ được tính trên các cạnh (nút \(i\) chỉ chú ý đến hàng xóm \(\mathcal{N}(i)\) của nó), không phải trên tất cả các cặp nút. Điều này giữ chi phí tính toán tỷ lệ với số cạnh, không phải bình phương số nút.

Chú Ý Đồ Thị Đa Đầu (Multi-Head Graph Attention)¶

Giống như trong transformer (chương 7), chú ý đa đầu (multi-head attention) chạy \(K\) cơ chế chú ý độc lập song song, mỗi cơ chế có tham số \(W^k\) và \(\mathbf{a}^k\) riêng. Các kết quả được nối (trong các tầng trung gian) hoặc lấy trung bình (trong tầng cuối):

\[\mathbf{h}_i' = \Big\|_{k=1}^{K} \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij}^k W^k \mathbf{h}_j\right)\]

Mỗi đầu có thể chú ý đến các khía cạnh khác nhau của lân cận: một đầu có thể tập trung vào các đặc trưng cấu trúc, một đầu khác vào sự tương tự ngữ nghĩa. Đây là cùng động lực như chú ý đa đầu trong transformer: các đầu khác nhau nắm bắt các loại quan hệ khác nhau.
Với \(K\) đầu và chiều đầu ra \(d'\) mỗi đầu, đầu ra đã nối có chiều \(K \times d'\). Tầng cuối cùng thường lấy trung bình thay vì nối để tạo ra đầu ra có kích thước cố định.

GATv2: Khắc Phục Chú Ý Tĩnh (Fixing Static Attention)¶

GAT gốc có một hạn chế tinh tế: hàm chú ý của nó là tĩnh (static) (còn gọi là dựa trên xếp hạng). Điểm chú ý phụ thuộc vào phép nối \([W\mathbf{h}_i \| W\mathbf{h}_j]\), nhưng vì vector chú ý \(\mathbf{a}\) được áp dụng sau khi nối, nó có thể được phân tích thành hai thành phần độc lập: \(\mathbf{a}^T [W\mathbf{h}_i \| W\mathbf{h}_j] = \mathbf{a}_1^T W\mathbf{h}_i + \mathbf{a}_2^T W\mathbf{h}_j\).
Điều này nghĩa là thứ tự xếp hạng các hàng xóm cho một nút \(i\) được xác định hoàn toàn bởi các đặc trưng \(\mathbf{h}_j\) của hàng xóm (số hạng \(\mathbf{a}_1^T W\mathbf{h}_i\) là hằng trên tất cả các hàng xóm của \(i\)). Thứ tự chú ý không thực sự phụ thuộc vào các đặc trưng của nút truy vấn. Nút \(i\) và nút \(k\) sẽ xếp hạng cùng một tập hàng xóm giống hệt nhau, điều này giới hạn sức mạnh biểu cảm.
GATv2 (Brody et al., 2022) khắc phục điều này bằng cách áp dụng tính phi tuyến trước vector chú ý:

\[e_{ij} = \mathbf{a}^T \text{LeakyReLU}\left(W \left[\mathbf{h}_i \| \mathbf{h}_j\right]\right)\]

Di chuyển LeakyReLU vào trong phép tính nghĩa là điểm chú ý là một hàm phi tuyến của các đặc trưng kết hợp, không thể phân tích thành các số hạng độc lập. Điều này làm cho chú ý trở nên động (dynamic): thứ tự xếp hạng các hàng xóm bây giờ phụ thuộc vào nút truy vấn cụ thể. GATv2 có sức mạnh biểu cảm cao hơn hẳn GAT mà không có thêm chi phí tính toán.

Graph Transformers¶

Các GNN truyền thông điệp tiêu chuẩn bị giới hạn bởi cấu trúc đồ thị: một nút chỉ có thể chú ý đến hàng xóm trực tiếp của nó. Sau \(k\) tầng, thông tin từ các hàng xóm cách \(k\) bước nhảy đã bị pha trộn qua nhiều bước tập hợp, mất độ chính xác. Nút thắt cục bộ này (kết hợp với quá mượt, file 3) giới hạn khả năng nắm bắt các phụ thuộc tầm xa.
Graph Transformers phá vỡ nút thắt này bằng cách áp dụng tự chú ý toàn cục (global self-attention) trên tất cả các cặp nút, bất kể chúng có chia sẻ cạnh hay không. Mọi nút có thể chú ý đến mọi nút khác trong một tầng duy nhất, giống như trong transformer tiêu chuẩn (chương 7).
Ý tưởng cơ bản: coi tất cả các nút như các token và áp dụng tự chú ý của transformer:

\[\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V\]

trong đó \(Q = XW_Q\), \(K = XW_K\), \(V = XW_V\) là các phép chiếu query, key, value của các đặc trưng nút \(X\) (chính xác như trong chương 7). Đây là một GNN trên đồ thị đầy đủ (complete graph \(K_n\), file 2).
Vấn đề: một đồ thị đầy đủ bỏ qua cấu trúc đồ thị thực tế. Thông tin cạnh (ai thực sự kết nối với ai) bị mất. Hai cách tiếp cận phục hồi điều này:
Graphormer (Ying et al., 2021) tiêm cấu trúc đồ thị vào transformer qua các số hạng độ chệch (bias terms) trong điểm chú ý:

\[A_{ij} = \frac{(\mathbf{h}_i W_Q)(W_K^T \mathbf{h}_j^T)}{\sqrt{d_k}} + b_{\text{spatial}}(i, j) + b_{\text{edge}}(i, j)\]

Độ chệch không gian \(b_{\text{spatial}}\) mã hóa khoảng cách đường đi ngắn nhất giữa các nút \(i\) và \(j\). Độ chệch cạnh \(b_{\text{edge}}\) mã hóa các đặc trưng cạnh dọc theo đường đi ngắn nhất. Ngoài ra, Graphormer dùng một mã hóa độ trung tâm (centrality encoding) thêm bậc của nút vào embedding đầu vào, cung cấp cho mô hình thông tin về vai trò cấu trúc của mỗi nút.
GPS (General, Powerful, Scalable Graph Transformer — Rampášek et al., 2022) kết hợp truyền thông điệp cục bộ với chú ý toàn cục trong mỗi tầng:

\[\mathbf{h}_i' = \text{MLP}\left(\mathbf{h}_i^{\text{MPNN}} + \mathbf{h}_i^{\text{Attention}}\right)\]

Mỗi tầng áp dụng cả GNN tiêu chuẩn (cho cấu trúc cục bộ) và transformer (cho ngữ cảnh toàn cục), sau đó kết hợp kết quả. Điều này đạt được ưu điểm của cả hai: cấu trúc cục bộ từ truyền thông điệp và phụ thuộc tầm xa từ chú ý.

Mã Hóa Vị Trí và Cấu Trúc (Positional and Structural Encodings)¶

Transformer trên chuỗi dùng mã hóa vị trí (chương 7) để tiêm thông tin thứ tự. Đồ thị không có thứ tự chuẩn tắc, vì vậy cần các mã hóa đặc thù cho đồ thị.
Mã hóa vector riêng Laplacian (Laplacian eigenvector encodings) dùng các vector riêng của Laplacian đồ thị (file 2) như các đặc trưng vị trí. \(k\) vector riêng không tầm thường nhỏ nhất cung cấp một embedding phổ của đồ thị: các nút "gần nhau" trong đồ thị có các giá trị vector riêng tương tự. Chúng được nối vào các đặc trưng nút.
Một điểm tinh tế: các vector riêng Laplacian có sự mơ hồ về dấu (nếu \(\mathbf{u}\) là một vector riêng, thì \(-\mathbf{u}\) cũng là). Mô hình phải bất biến với các lật dấu này. Các giải pháp bao gồm dùng lật dấu ngẫu nhiên như tăng cường dữ liệu trong quá trình huấn luyện, hoặc học các phép biến đổi bất biến với dấu.
Mã hóa bước đi ngẫu nhiên (Random walk encodings) tính xác suất một bước đi ngẫu nhiên bắt đầu tại nút \(i\) quay lại nút \(i\) sau \(k\) bước, với \(k = 1, 2, \ldots, K\). Các xác suất này mã hóa thông tin cấu trúc cục bộ: các nút trong cụm dày đặc có xác suất quay lại cao, trong khi các nút trong vùng thưa thớt có xác suất thấp. Xác suất đáp \(p_{ii}^{(k)} = (A_{\text{rw}}^k)_{ii}\) trong đó \(A_{\text{rw}} = D^{-1}A\) là ma trận chuyển tiếp bước đi ngẫu nhiên.
Mã hóa bậc (Degree encodings) đơn giản thêm bậc nút như một đặc trưng. Điều này hiệu quả đáng ngạc nhiên vì bậc là một tín hiệu cấu trúc mạnh: các nút lá (bậc 1), nút cầu, và nút trung tâm có hành vi khác nhau.
Các mã hóa này cung cấp thông tin cấu trúc mà transformer thuần thiếu, cho phép Graph Transformers vượt trội hơn các GNN truyền thông điệp tiêu chuẩn trong các tác vụ yêu cầu suy luận tầm xa.

Khả Năng Mở Rộng (Scalability)¶

Thách thức mở rộng cơ bản cho GNN là đồ thị có thể có hàng triệu nút và hàng tỷ cạnh. Huấn luyện một GNN trên toàn bộ đồ thị yêu cầu lưu trữ tất cả các đặc trưng nút và toàn bộ ma trận kề trong bộ nhớ, điều thường không khả thi.
Huấn luyện mini-batch cho GNN phức tạp hơn cho ảnh hoặc chuỗi vì các nút được kết nối liên kết với nhau. Lấy mẫu ngây thơ một batch các nút yêu cầu hàng xóm của chúng (tầng 1), hàng xóm của hàng xóm (tầng 2), và cứ thế. Sự bùng nổ lân cận (neighbourhood explosion) này nghĩa là một batch 1000 nút mục tiêu có thể yêu cầu hàng triệu nút trong đồ thị tính toán.
Lấy mẫu lân cận (Neighbourhood sampling) (kiểu GraphSAGE, file 3) giới hạn sự bùng nổ bằng cách lấy mẫu một số lượng cố định hàng xóm cho mỗi nút mỗi tầng. Với 2 tầng và 15 mẫu mỗi tầng, đồ thị con của mỗi nút mục tiêu có nhiều nhất \(15^2 = 225\) nút, bất kể kích thước đồ thị đầy đủ.
Cluster-GCN (Chiang et al., 2019) phân hoạch đồ thị thành các cụm dùng một thuật toán phân cụm đồ thị (ví dụ: METIS), sau đó huấn luyện trên một cụm tại một thời điểm. Các cạnh trong cụm dày đặc (hầu hết hàng xóm ở trong cùng cụm), vì vậy đồ thị con nắm bắt được cấu trúc liên quan. Các cạnh xuyên cụm được xử lý bằng cách thỉnh thoảng bao gồm các cạnh giữa các cụm.
Khả năng mở rộng của Graph Transformer khó hơn vì chú ý toàn cục là \(O(n^2)\). Với đồ thị có hàng triệu nút, chú ý đầy đủ là không khả thi. Các giải pháp bao gồm:
- Các mẫu chú ý thưa (sparse attention patterns) (chỉ chú ý đến \(k\) nút gần nhất trong đồ thị)
- Các xấp xỉ chú ý tuyến tính
- Kết hợp truyền thông điệp cục bộ (rẻ, \(O(|E|)\)) với chú ý toàn cục trên một đồ thị đã làm thô (ít nút hơn)

Đồ Thị Thời Gian và Động (Temporal and Dynamic Graphs)¶

Các đồ thị chúng ta đã nghiên cứu cho đến nay là tĩnh (static): các nút, cạnh, và đặc trưng là cố định. Nhưng nhiều đồ thị thế giới thực tiến hóa theo thời gian: người dùng mới tham gia mạng xã hội, giao dịch tài chính tạo ra các cạnh, mẫu giao thông thay đổi trong ngày, và tương tác phân tử dao động.
Một đồ thị thời gian (temporal graph) bổ sung cho mỗi cạnh một nhãn thời gian: \((i, j, t)\) nghĩa là nút \(i\) tương tác với nút \(j\) tại thời điểm \(t\). Thách thức là học các biểu diễn nắm bắt cả cấu trúc đồ thị lẫn động lực thời gian.
Có hai mô hình:
Đồ thị động thời gian rời rạc (DTDG — Discrete-time dynamic graphs): đồ thị được biểu diễn dưới dạng một dãy các ảnh chụp nhanh \(G_1, G_2, \ldots, G_T\), mỗi ảnh tại một bước thời gian. Một GNN xử lý từng ảnh chụp nhanh, và một RNN hoặc cơ chế chú ý thời gian nắm bắt sự tiến hóa qua các ảnh chụp nhanh. Điều này đơn giản nhưng mất thông tin thời gian chi tiết (các sự kiện giữa các ảnh chụp nhanh bị mất) và yêu cầu chọn tần số chụp.
Đồ thị động thời gian liên tục (CTDG — Continuous-time dynamic graphs): các sự kiện được mô hình hóa như một luồng các tương tác có nhãn thời gian. Mỗi sự kiện \((i, j, t)\) cập nhật biểu diễn của các nút \(i\) và \(j\) tại đúng thời điểm nó xảy ra. Điều này bảo toàn tất cả thông tin thời gian.
TGN (Temporal Graph Network) (Rossi et al., 2020) là kiến trúc CTDG hàng đầu. Mỗi nút duy trì một trạng thái bộ nhớ (memory state) \(\mathbf{s}_i(t)\) được cập nhật mỗi khi nút tham gia vào một tương tác:

\[\mathbf{s}_i(t^+) = \text{GRU}\left(\mathbf{s}_i(t^-), \; \mathbf{m}_i(t)\right)\]

trong đó \(\mathbf{m}_i(t)\) là một thông điệp được tính từ tương tác (kết hợp các đặc trưng của cả hai nút, đặc trưng cạnh, và mã hóa thời gian). GRU (chương 6) giữ lại và quên thông tin trong quá khứ một cách có chọn lọc, cho phép bộ nhớ nắm bắt các mẫu dài hạn trong khi thích ứng với các sự kiện gần đây.
Mã hóa thời gian (Time encoding) biểu diễn thời gian trôi qua kể từ tương tác cuối cùng như một vector đặc trưng, tương tự như mã hóa vị trí trong transformer (chương 7). Một cách tiếp cận phổ biến dùng các đặc trưng Fourier học được:

\[\Phi(t) = \left[\cos(\omega_1 t), \sin(\omega_1 t), \ldots, \cos(\omega_d t), \sin(\omega_d t)\right]\]

Điều này cung cấp cho mô hình một biểu diễn phong phú về các khoảng thời gian: "người dùng này hoạt động lần cuối 5 phút trước" so với "3 tháng trước" được nhúng khác nhau.
TGAT (Temporal Graph Attention) áp dụng tự chú ý trên lân cận thời gian của một nút: tập hợp các tương tác gần đây, mỗi tương tác được trong số bởi cả mức độ liên quan đặc trưng (như GAT) và tính gần đây về thời gian. Các tương tác từ quá khứ xa xôi tự nhiên bị giảm trọng số.
Các ứng dụng bao gồm phát hiện gian lận (mẫu giao dịch bất thường trong đồ thị tài chính), dự báo giao thông (dự đoán tắc nghẽn từ mẫu dòng chảy lịch sử), động lực mạng xã hội (dự đoán lan truyền nội dung viral), và dự đoán tương tác thuốc theo thời gian.

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

Cài đặt một đầu chú ý GAT từ đầu. Tính trọng số chú ý giữa một nút và các hàng xóm và kiểm tra chúng có tổng bằng 1.

import jax
import jax.numpy as jnp

rng = jax.random.PRNGKey(0)
k1, k2, k3 = jax.random.split(rng, 3)

n_nodes, d_in, d_out = 5, 4, 3

# Random node features
H = jax.random.normal(k1, (n_nodes, d_in))

# Learnable parameters
W = jax.random.normal(k2, (d_in, d_out)) * 0.5
a = jax.random.normal(k3, (2 * d_out,)) * 0.5

# Adjacency (node 0 connects to 1, 2, 3)
neighbours_of_0 = [1, 2, 3]

# Transform features
Wh = H @ W  # (n_nodes, d_out)

# Compute attention scores for node 0
h_i = Wh[0]
scores = []
for j in neighbours_of_0:
    h_j = Wh[j]
    e_ij = jnp.dot(a, jnp.concatenate([h_i, h_j]))
    e_ij = jax.nn.leaky_relu(e_ij, negative_slope=0.2)
    scores.append(float(e_ij))

scores = jnp.array(scores)
alpha = jax.nn.softmax(scores)

print(f"Raw scores: {scores}")
print(f"Attention weights: {alpha}")
print(f"Sum of weights: {alpha.sum():.4f}")

# Weighted aggregation
h_new = sum(alpha[k] * Wh[neighbours_of_0[k]] for k in range(len(neighbours_of_0)))
print(f"Updated node 0 features: {h_new}")

So sánh gộp của GCN (trọng số cố định) và GAT (trọng số học được). Cho thấy GAT có thể gán trọng số khác nhau cho các hàng xóm trong khi GCN xử lý chúng đồng đều.

import jax
import jax.numpy as jnp

# 4 nodes: node 0 connects to 1, 2, 3
A = jnp.array([[0,1,1,1],
               [1,0,0,0],
               [1,0,0,0],
               [1,0,0,0]], dtype=float)

# Features: node 1 is very relevant, node 2 is noise, node 3 is moderate
H = jnp.array([[0.0, 0.0],   # node 0
               [1.0, 0.0],   # node 1 (signal)
               [0.0, 0.0],   # node 2 (noise)
               [0.5, 0.0]])  # node 3 (moderate)

# GCN: normalised adjacency weights
A_hat = A + jnp.eye(4)
D_inv = jnp.diag(1.0 / A_hat.sum(axis=1))
gcn_weights = (D_inv @ A_hat)[0]  # weights for node 0
print(f"GCN weights for node 0: {gcn_weights}")
print("  → All neighbours get roughly equal weight")

# GAT: learned attention (simulated)
# Suppose the attention mechanism learns to focus on node 1
gat_weights = jnp.array([0.1, 0.7, 0.05, 0.15])  # learned
print(f"\nGAT weights for node 0: {gat_weights}")
print("  → Node 1 (informative) gets most attention")

gcn_output = gcn_weights @ H
gat_output = gat_weights @ H
print(f"\nGCN output: {gcn_output}  (diluted by noise)")
print(f"GAT output: {gat_output}  (focused on signal)")

Minh họa lợi ích của mã hóa vị trí. Tính mã hóa vector riêng Laplacian cho một đồ thị và cho thấy các nút có cấu trúc tương tự nhận được mã hóa tương tự.

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

# Barbell graph: two cliques connected by a bridge
n = 10
A = jnp.zeros((n, n))
# Clique 1: nodes 0-4
for i in range(5):
    for j in range(i+1, 5):
        A = A.at[i,j].set(1).at[j,i].set(1)
# Clique 2: nodes 5-9
for i in range(5, 10):
    for j in range(i+1, 10):
        A = A.at[i,j].set(1).at[j,i].set(1)
# Bridge
A = A.at[4,5].set(1).at[5,4].set(1)

D = jnp.diag(A.sum(axis=1))
L = D - A
eigenvalues, eigenvectors = jnp.linalg.eigh(L)

# Use first 3 non-trivial eigenvectors as positional encoding
pe = eigenvectors[:, 1:4]

print("Laplacian Positional Encodings:")
for i in range(n):
    group = "Clique 1" if i < 5 else "Clique 2"
    bridge = " (bridge)" if i in [4, 5] else ""
    print(f"  Node {i} ({group}{bridge}): {pe[i]}")

plt.scatter(pe[:5, 0], pe[:5, 1], c="#3498db", s=80, label="Clique 1")
plt.scatter(pe[5:, 0], pe[5:, 1], c="#e74c3c", s=80, label="Clique 2")
plt.scatter(pe[[4,5], 0], pe[[4,5], 1], c="black", s=120, marker="*",
            label="Bridge nodes", zorder=5)
plt.legend(); plt.grid(True)
plt.title("Laplacian Eigenvector Positional Encodings")
plt.xlabel("Eigenvector 1"); plt.ylabel("Eigenvector 2")
plt.show()