Kiến trúc mạng học sâu: từ nền tảng đến LLM·Chương 8 — GNN: từ message passing đến Graph Transformer

Chế độ xem

GNN: từ dữ liệu đồ thị đến message passing và GCN

Bài này trả lời: khi dữ liệu gồm thực thể và mối quan hệ, làm sao một mạng neural dùng được mối quan hệ đó, thay vì chỉ vector của từng thực thể. Thực thể là nút (node). Mối quan hệ là cạnh (edge). Họ mạng này là mạng nơ-ron đồ thị, GNN. Bạn chỉ cần biết vector, một dãy số, và láng giềng: nút nối trực tiếp bằng một cạnh. Bài không giả định bạn đã gặp GCN. Bài không chứng minh phổ Laplacian, không so hết GraphSAGE, GAT hay GIN, và không hướng dẫn cài thư viện.

Đường đọc nhanh: mục 1, 2, 6, 7, 9 và 16. Bỏ qua mục Đào sâu (mục 11, tích chập phổ) cho đến sau mục 16.

1. Tại sao cần một họ mạng riêng cho graph?

Lân cận là phần tử được phép ảnh hưởng tới phần tử đang tính. MLP chỉ nhận vector, không có láng giềng cố định. CNN lấy ô ảnh quanh pixel. RNN đi theo chuỗi. Transformer cho token chú ý lẫn nhau. GNN lấy lân cận từ cạnh.

Kiến trúcCấu trúc dữ liệuLân cận được xác định như thế nào?
MLPvector/bảngkhông có quan hệ lân cận cố định
CNNlưới ảnhpixel xung quanh theo vị trí không gian
RNN/LSTM/GRUchuỗiphần tử trước/sau theo thứ tự
Transformertập/chuỗi tokenattention có thể nối mọi token với nhau
GNNgraphlân cận do edge trong dữ liệu định nghĩa

Graph xuất hiện khi quan hệ giữa các thực thể là một phần của dữ liệu, không chỉ là metadata phụ.

Ví dụ:

Bài toánNodeEdgeFeature ví dụDự đoán
Mạng trích dẫnbài báoA trích dẫn Bembedding tiêu đề/abstractchủ đề bài báo
Mạng xã hộitài khoảnfollow/kết bạnhồ sơ, hành vifraud, community
Hệ gợi ýuser, itemclick/mua/ratinghồ sơ + thuộc tính itemtương tác tiếp theo
Phân tửnguyên tửliên kết hóa họcloại nguyên tử, điện tíchđộc tính/tính chất phân tử
Giao thôngnút giao/đoạn đườngkết nối đườnglưu lượng, tốc độdự báo congestion
Knowledge graphthực thểquan hệ có kiểuembedding thực thể/quan hệlink prediction

Một test đơn giản:

Nếu xóa toàn bộ edge mà bài toán vẫn gần như không đổi, có thể bạn không cần GNN. Nếu xóa edge làm mất thông tin cốt lõi, graph learning đáng để cân nhắc.

2. Graph trong máy tính: từ khái niệm đến tensor

Một đồ thị là một tập nút cùng một tập cạnh. Ký hiệu gói hai tập đó lại:

G=(V,E)G=(V,E)

trong đó:

  • VV: tập node, ∣V∣=N|V|=N;
  • EE: tập edge, ∣E∣=M|E|=M.

Node feature là vector số của từng nút. Edge feature là vector của cạnh, khi quan hệ có thuộc tính riêng. Ma trận kề là bảng vuông: ô bằng 1 nếu có cạnh, bằng 0 nếu không.

  • X∈RN×FX\in\mathbb{R}^{N\times F}: node feature;
  • Ef∈RM×FeE_f\in\mathbb{R}^{M\times F_e}: edge feature nếu có;
  • A∈{0,1}N×NA\in\{0,1\}^{N\times N}: adjacency matrix;
  • yy: nhãn ở mức node, edge hoặc graph.

GNN không học thuộc bảng kề. Nó viết lại vector mỗi nút bằng chính nút đó và các nút có cạnh nối với nó.

Ví dụ graph 4 node:

Nếu đánh số nút theo thứ tự A,B,C,DA,B,C,D, bảng kề của đồ thị bốn nút trên là:

A=[0110100110010110]A= \begin{bmatrix} 0&1&1&0\\ 1&0&0&1\\ 1&0&0&1\\ 0&1&1&0 \end{bmatrix}

Điểm cần chú ý: thứ tự đánh số node do ta chọn. Graph không thay đổi ý nghĩa chỉ vì đổi tên A thành node 17.

2.1 Có hướng và vô hướng

  • Vô hướng: quan hệ hai chiều, ví dụ “là bạn”.
  • Có hướng: quan hệ có chiều, ví dụ “A trích dẫn B”.
Undirected and directed graph edges

Edge vô hướng và có hướng. Nguồn: Sanchez-Lengeling et al., Distill (2021), CC-BY 4.0.

Trong code, graph vô hướng thường được lưu thành hai edge có hướng ngược nhau để message có thể truyền cả hai chiều.

2.2 Homogeneous và heterogeneous graph

  • Homogeneous graph: một kiểu node/edge chính. Ví dụ citation graph: node đều là paper.
  • Heterogeneous graph: nhiều kiểu node/edge. Ví dụ recommender:
    • node type: user, movie;
    • edge type: user --rates--> movie, user --follows--> user.

Đây không chỉ là khác biệt cách lưu dữ liệu. Với heterogeneous graph, từng loại quan hệ có thể cần tham số và phép biến đổi riêng.

3. Ba mức dự đoán cơ bản

3.1 Node-level

Ở mức nút, mô hình trả một dự đoán riêng cho từng nút:

y^i=f(G,X)i\hat{y}_i=f(G,X)_i

Ví dụ: dự đoán chủ đề của từng paper trong Cora.

3.2 Edge-level / link prediction

Ở mức cạnh, mô hình chấm một cặp nút, dù cạnh đó đã có hay đang được hỏi có nên có:

y^ij=g(hi,hj)\hat{y}_{ij}=g(h_i,h_j)

Ví dụ: liệu user ii có mua item jj không.

3.3 Graph-level

Ở mức đồ thị, mọi vector nút được gộp thành một dự đoán cho cả đồ thị:

y^=g({hi}i∈V)\hat{y}=g(\{h_i\}_{i\in V})

Ví dụ: một phân tử có độc tính hay không.

Sai lầm phổ biến: chọn model trước rồi mới nghĩ task. Với graph, hãy xác định đơn vị cần dự đoán trước: node, edge hay toàn graph.

4. Vì sao MLP thông thường chưa đủ?

Nếu mỗi nút chỉ được biến đổi từ vector của chính nó, một MLP độc lập cho:

hi=MLP(xi)h_i=\mathrm{MLP}(x_i)

Nếu hai graph có cùng node feature nhưng edge khác nhau, MLP này cho output giống hệt. Nó không nhìn thấy topology.

Một cách thô là flatten adjacency matrix rồi nối vào feature, nhưng có ba vấn đề:

  1. Kích thước thay đổi: graph 10 node và 10.000 node không có cùng kích thước AA.
  2. Đánh số node là tùy ý: đổi thứ tự node làm vector flatten thay đổi mạnh dù graph vẫn là graph đó.
  3. Graph thường thưa: AA có N2N^2 ô nhưng chỉ M≪N2M\ll N^2 edge; lưu dày gây lãng phí.

Ta cần kiến trúc biết tôn trọng cấu trúc graph.

5. Hai tính chất nền tảng: permutation invariance và equivariance

Đổi thứ tự đánh số nút là nhân với một ma trận hoán vị PP. Feature và bảng kề đổi theo, nhưng đồ thị vẫn là đồ thị đó:

X′=PX,A′=PAP⊤X' = PX,\qquad A' = PAP^\top

Với dự đoán theo từng nút, đầu ra phải bị xáo cùng cách với đầu vào. Đó là permutation equivariance, đồng biến theo hoán vị:

f(A′,X′)=Pf(A,X)f(A',X') = P f(A,X)

Với một số cho cả đồ thị, xáo nút không được đổi kết quả. Đó là permutation invariance, bất biến theo hoán vị:

g(PAP⊤,PX)=g(A,X)g(PAP^\top,PX)=g(A,X)

sum, mean và max gộp láng giềng vì chúng không phụ thuộc thứ tự:

sum⁡(a,b,c)=sum⁡(c,a,b)\operatorname{sum}(a,b,c)=\operatorname{sum}(c,a,b)

6. Message passing: khuôn mẫu trung tâm của GNN

Message passing là khuôn mẫu chung. Thông điệp là gói số một nút gửi cho nút kề. Gộp là biến nhiều gói thành một tóm tắt, không phụ thuộc thứ tự gói. Rồi nút viết lại vector của mình.

Tại lớp thứ ll, nút ii đang giữ một embedding, tức vector biểu diễn đã được biến đổi:

hi(l)∈Rdlh_i^{(l)}\in\mathbb{R}^{d_l}

Trước khi học, embedding đó thường chính là feature ban đầu của nút:

hi(0)=xih_i^{(0)}=x_i

Bước 1 — tạo message

Nút jj đóng gói từ trạng thái hai đầu và từ cạnh, nếu cạnh có feature:

mj→i(l)=ϕ(l)(hi(l),hj(l),eji)m_{j\rightarrow i}^{(l)}= \phi^{(l)}\left(h_i^{(l)},h_j^{(l)},e_{ji}\right)

Bước 2 — aggregate

Nút ii gộp các gói từ láng giềng N(i)\mathcal{N}(i), các nút nối trực tiếp với ii:

mi(l)=AGG⁡(l)({mj→i(l)∣j∈N(i)})m_i^{(l)}= \operatorname{AGG}^{(l)}\left( \left\{m_{j\rightarrow i}^{(l)}\mid j\in\mathcal{N}(i)\right\} \right)

Bước 3 — update

Vector mới là hàm của vector cũ và của bản tóm tắt vừa gộp:

hi(l+1)=ψ(l)(hi(l),mi(l))h_i^{(l+1)}= \psi^{(l)}\left(h_i^{(l)},m_i^{(l)}\right)

Có thể nhớ ba động từ: gửi, gộp, cập nhật.

Message passing layer

Sơ đồ một message-passing layer. Nguồn: Sanchez-Lengeling et al., Distill (2021), CC-BY 4.0.

6.1 Vì sao khuôn mẫu này linh hoạt?

Ta có thể thay đổi:

  • message có dùng edge feature hay không;
  • AGG là sum, mean, max hay attention;
  • có sample hàng xóm hay dùng toàn bộ;
  • update bằng linear layer, MLP, GRU hay residual block.

GCN, GraphSAGE, GAT, GIN… chủ yếu là các lựa chọn khác nhau trong khung này.

7. Ví dụ số: tự tính một vòng message passing

Lấy nút AA với feature hai chiều:

hA(0)=[2,1]h_A^{(0)}=[2,1]

Hai láng giềng của AA mang feature:

hB(0)=[4,0],hC(0)=[0,6]h_B^{(0)}=[4,0],\qquad h_C^{(0)}=[0,6]

Giả sử:

  • message = embedding của hàng xóm;
  • aggregate = mean;
  • update = cộng embedding cũ với mean rồi chia 2.

Gộp bằng trung bình cộng hai vector láng giềng cho bản tóm tắt đến AA:

mA=[4,0]+[0,6]2=[2,3]m_A=\frac{[4,0]+[0,6]}{2}=[2,3]

Cập nhật bằng cách cộng vector cũ của AA với bản tóm tắt đó rồi chia hai:

hA(1)=[2,1]+[2,3]2=[2,2]h_A^{(1)}=\frac{[2,1]+[2,3]}{2}=[2,2]

Sau một layer, AA không còn chỉ chứa thông tin của riêng nó.

7.1 Sum và mean khác nhau thế nào?

Bậc (degree) của một nút là số cạnh chạm vào nút đó. Nếu mọi láng giềng đều có feature [1,0][1,0]:

  • node có 2 neighbors: sum = [2,0], mean = [1,0];
  • node có 20 neighbors: sum = [20,0], mean = [1,0].

sum giữ lại phần nào thông tin về số lượng; mean chuẩn hóa theo degree. Không có phép nào luôn tốt nhất.

8. Từ message passing sang phép nhân ma trận

Khi thông điệp chỉ là feature của láng giềng và phép gộp là cộng, nút ii nhận đúng tổng feature các nút kề:

mi=∑j∈N(i)xjm_i=\sum_{j\in\mathcal{N}(i)}x_j

Làm phép cộng đó cho mọi nút cùng lúc chính là nhân ma trận kề với ma trận feature:

AXAX

Hàng ii của AA chỉ giữ các nút nối với ii, nên nhân ma trận chính là chọn láng giềng.

Với bảng kề và cột feature dưới đây, nút đầu có hai láng giềng mang số 2 và số 4:

A=[011100100],X=[124]A= \begin{bmatrix} 0&1&1\\ 1&0&0\\ 1&0&0 \end{bmatrix},\quad X= \begin{bmatrix} 1\\2\\4 \end{bmatrix}

Nhân hai ma trận đó ra tổng theo từng hàng, và ô đầu đúng bằng 2+42+4:

AX=[611]AX= \begin{bmatrix} 6\\1\\1 \end{bmatrix}

9. GCN: từ cộng hàng xóm tới convolution trên graph

Graph Convolutional Network (GCN) của Kipf và Welling là baseline kinh điển: một lớp tuyến tính dùng chung, cộng láng giềng đã cân theo bậc, rồi qua hàm phi tuyến.

H(l+1)=σ(D~−12A~D~−12H(l)W(l))H^{(l+1)}= \sigma\left( \tilde{D}^{-\frac12} \tilde{A} \tilde{D}^{-\frac12} H^{(l)}W^{(l)} \right)

Self-loop là một cạnh từ nút tới chính nó. Thêm self-loop vào bảng kề để nút không bị mất feature của mình:

A~=A+I\tilde{A}=A+I

D~\tilde{D} là ma trận bậc của A~\tilde{A}: đường chéo ghi bậc sau khi đã cộng self-loop.

9.1 Thêm self-loop: A+IA+I

Nếu chỉ dùng AA, node nhận neighbor nhưng có thể mất thông tin chính nó. Thêm II nghĩa là node cũng gửi message cho chính mình.

9.2 Chuẩn hóa theo degree

Nếu một nút hub có 10.000 láng giềng và nút khác có 3 láng giềng, cộng thẳng tạo hai thang số rất khác nhau.

GCN nhân mỗi cạnh j→ij\rightarrow i với một hệ số nhỏ khi bậc hai đầu lớn:

1d~id~j\frac{1}{\sqrt{\tilde{d}_i\tilde{d}_j}}

Viết lại cho từng nút, tổng đó chạy trên láng giềng và trên chính nút:

hi(l+1)=σ(∑j∈N(i)∪{i}1d~id~jW(l)hj(l))h_i^{(l+1)}= \sigma\left( \sum_{j\in\mathcal{N}(i)\cup\{i\}} \frac{1}{\sqrt{\tilde{d}_i\tilde{d}_j}} W^{(l)}h_j^{(l)} \right)

9.3 WW là phần học được

Phần học được là ma trận trọng số dùng chung cho mọi nút, như lớp tuyến tính của MLP:

W(l)∈Rdl×dl+1W^{(l)}\in\mathbb{R}^{d_l\times d_{l+1}}

9.4 σ\sigma tạo phi tuyến

Hàm phi tuyến phá tính thẳng: ReLU giữ phần dương và xóa phần âm.

σ(z)=max⁡(0,z)\sigma(z)=\max(0,z)

Nếu stack nhiều layer mà không có phi tuyến, cả mạng dễ quy về một phép biến đổi tuyến tính lớn.

GCN architecture schematic

Sơ đồ GCN cập nhật node từ neighborhood. Nguồn: Sanchez-Lengeling et al., Distill (2021), CC-BY 4.0.

10. Receptive field: một layer nhìn được bao xa?

Một hop là một bước đi dọc đúng một cạnh. Receptive field của một nút là vùng các nút mà thông tin còn tới được nút đó.

Nếu mỗi lớp chỉ truyền tin qua cạnh trực tiếp, vùng nhìn lớn dần theo số lớp:

  • 1 layer: 1-hop;
  • 2 layers: tối đa 2-hop;
  • KK layers: tối đa KK-hop.

Stack nhiều lớp làm vùng nhìn tăng, giống CNN. Degree của nút không cố định, nên số nút trong vùng KK hop có thể tăng rất nhanh.

Ví dụ degree trung bình khoảng 10:

  • 1-hop: cỡ 10 node;
  • 2-hop: có thể cỡ 100;
  • 3-hop: có thể cỡ 1.000.

Trong thực tế có overlap nên không đúng chính xác 10K10^K, nhưng hiện tượng neighborhood explosion vẫn là vấn đề quan trọng khi scale.

11. Đào sâu: vì sao gọi là “convolution” trên graph?

Phần này giải thích vì sao người ta gọi GCN là convolution. Bạn vẫn chạy được GCN chuẩn nếu bỏ qua mục này.

Trong xử lý tín hiệu trên đồ thị, bậc của từng nút được ghi trên đường chéo:

Dii=∑jAijD_{ii}=\sum_j A_{ij}

Laplacian chuẩn hóa lấy phần “lệch khỏi láng giềng” của một tín hiệu trên đồ thị:

L=I−D−12AD−12L=I-D^{-\frac12}AD^{-\frac12}

Ma trận này tách được thành các phương riêng, giống một hệ trục tần số:

L=UΛU⊤L=U\Lambda U^\top

Các vector riêng trong UU giống cơ sở Fourier. Tín hiệu trên nút, một số gắn với mỗi nút, đổi sang miền tần số đó bằng:

x^=U⊤x\hat{x}=U^\top x

Tích chập phổ là nhân tín hiệu, trong miền tần số, với một bộ lọc rồi đổi về miền nút:

gθ∗x=Ugθ(Λ)U⊤xg_\theta * x = Ug_\theta(\Lambda)U^\top x

Phân tích riêng tốn kém, và bộ lọc có thể không còn cục bộ. GCN của Kipf và Welling rút xấp xỉ bậc thấp đó thành phép lan truyền trên láng giềng:

D~−12A~D~−12XW\tilde{D}^{-\frac12}\tilde{A}\tilde{D}^{-\frac12}XW

Điều quan trọng về mặt thực hành:

Bạn không cần tính eigenvector để chạy GCN chuẩn. Công thức cuối cùng được thực hiện bằng sparse neighborhood aggregation.

12. Transductive và inductive: một phân biệt rất hay bị bỏ qua

Transductive: lúc train, đồ thị đã chứa nút sẽ bị chấm, chỉ nhãn bị giấu. Inductive: lúc dự đoán có nút hoặc đồ thị chưa thấy lúc train. Data leakage là tin của phần cần chấm lọt vào train trái protocol.

12.1 Transductive setting

Cora theo split cổ điển thường là ví dụ transductive.

Điều này không đồng nghĩa với data leakage nếu protocol cho phép dùng connectivity và feature của test nodes.

12.2 Inductive setting

Khi inference có node hoặc graph chưa từng xuất hiện khi train.

Ví dụ:

  • train trên một số protein graph, test trên protein graph mới;
  • social network có user mới;
  • hệ recommender liên tục nhận item mới.

Model inductive cần học hàm tạo embedding từ feature + neighborhood, thay vì chỉ lưu embedding riêng cho từng node ID.

GraphSAGE học hàm gộp, nên vẫn mã hóa được nút mới nếu nút đó có feature và láng giềng.

13. Quy trình huấn luyện một GCN node classifier

Giả sử:

  • NN node;
  • CC class;
  • model output logits Z∈RN×CZ\in\mathbb{R}^{N\times C}.

Lớp đầu trộn rồi qua ReLU. Lớp sau cho logit, điểm thô trước softmax, của từng nút:

H(1)=ReLU(A^XW(0))H^{(1)}=\mathrm{ReLU}(\hat{A}XW^{(0)}) Z=A^H(1)W(1)Z=\hat{A}H^{(1)}W^{(1)}

Ma trận A^\hat{A} ở cả hai lớp là bảng kề đã thêm self-loop và đã chuẩn hóa đối xứng theo bậc:

A^=D~−1/2A~D~−1/2\hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}

Nếu chỉ một phần nút có nhãn huấn luyện, loss là cross-entropy trung bình trên đúng các nút đó:

L=−1∣Vtrain∣∑i∈Vtrainlog⁡p(yi∣Zi)\mathcal{L} =-\frac{1}{|V_{train}|} \sum_{i\in V_{train}} \log p(y_i\mid Z_i)

Điểm đặc biệt: forward có thể tạo representation cho mọi node, nhưng loss chỉ tính trên train_mask.

14. Chi phí tính toán: GNN không nhất thiết dùng ma trận N×NN\times N

Graph thực tế thường sparse. Ta không cần materialize adjacency matrix dày.

Một lớp đi qua mỗi cạnh tốn số phép tính tỷ lệ với số cạnh nhân số chiều ẩn dd:

O(Md)O(Md)

Phép mọi cặp nút thì tỷ lệ với bình phương số nút:

O(N2d)O(N^2d)

nếu làm dense pairwise computation.

Đây là lý do thư viện như PyTorch Geometric lưu graph bằng edge_index dạng COO:

edge_index.shape = [2, num_edges]

mỗi cột là (source, target).

Ví dụ:

edge_index = [
    [0, 0, 1, 2],  # source
    [1, 2, 3, 3],  # target
]

15. GNN đang “học” cái gì?

Một cách hiểu sai là: “GNN chỉ làm trung bình feature của hàng xóm”.

Đúng hơn:

  1. topology quyết định ai có thể truyền thông tin cho ai;
  2. layer học phép biến đổi WW / MLP;
  3. qua nhiều layer, node embedding mã hóa pattern local quanh node;
  4. supervision ép embedding hữu ích cho task.

Do đó hai node có feature ban đầu giống nhau vẫn có thể có embedding khác nếu neighborhood khác nhau.

Hai nút có láng giềng đối xứng có thể không phân biệt được bằng message passing cơ bản. Expressive power là khả năng phân biệt hai cấu trúc khác nhau.

16. Những giả định ngầm cần kiểm tra trước khi dùng GNN

16.1 Edge có thật sự mang ý nghĩa không?

Không phải graph nào được tạo ra cũng hữu ích. K-NN graph tạo từ dữ liệu bảng là một thiết kế của người làm mô hình, không phải quan hệ tự nhiên. Kết quả phụ thuộc mạnh vào cách xây edge.

16.2 Neighbor có xu hướng cung cấp thông tin hữu ích không?

Nhiều mô hình kiểu GCN hoạt động rất tốt khi đồ thị có homophily: các nút nối với nhau thường giống nhau về feature hoặc về nhãn.

Đồ thị gian lận có thể ngược lại: tài khoản gian nối với người thường. Đó là heterophily, láng giềng khác nhãn. Trộn mù lúc ấy có thể làm xấu biểu diễn.

16.3 Hướng edge có quan trọng không?

Citation A -> B và B -> A không giống nhau. Tự chuyển mọi graph thành undirected có thể làm mất semantics.

16.4 Edge feature có quan trọng không?

Trong molecule, loại bond rất quan trọng. Dùng GCN chỉ đọc connectivity mà bỏ bond type có thể là một baseline quá yếu.

17. Liên hệ với CNN và Transformer

17.1 GNN với CNN

Giống nhau:

  • đều aggregate thông tin từ neighborhood;
  • chia sẻ parameter trên nhiều vị trí/node;
  • stack layer để tăng receptive field.

Khác nhau:

  • CNN có neighborhood cố định trên grid;
  • GNN có neighborhood thay đổi theo topology;
  • degree của node không cố định;
  • graph phải xử lý permutation symmetry.

17.2 GNN với Transformer

Self-attention chuẩn có thể xem như cho mọi token “kết nối” với mọi token khác.

GNN message passing thường giới hạn truyền thông tin theo edge thật.

GAT học trọng số trên cạnh thật. Graph Transformer cho nút nhìn rộng hơn một cạnh, và cần mã hóa cấu trúc để khỏi quên topology.

18. Những ý mang đi

Đồ thị là nút cộng cạnh. Đổi cách đánh số không được đổi kết quả, vì gộp bằng tổng, trung bình hoặc max không phụ thuộc thứ tự.

Một lớp gửi một gói số, gộp láng giềng, rồi viết lại vector. Một lớp nhìn một hop, một bước dọc một cạnh. Hai lớp nhìn tối đa hai hop.

GCN thêm self-loop, cạnh từ nút tới chính nó, và nhân cạnh với 1/didj1/\sqrt{d_i d_j} để nút bậc cao không át nút khác. Loss chỉ tính trên nút có nhãn train. Đồ thị thưa lưu bằng danh sách cạnh.

Dự đoán là một đầu ra mỗi nút, mỗi cặp, hoặc cả đồ thị. Transductive giấu nhãn nhưng vẫn thấy nút kiểm tra. Inductive mã hóa nút mới. Xóa hết cạnh mà bài toán không đổi thì có thể không cần GNN. Homophily, láng giềng giống nhau, giúp việc trộn. Heterophily, láng giềng khác nhau, có thể làm hại.

Bài sau tách GCN, GraphSAGE, GAT và GIN theo chỗ chúng đổi bước gửi, gộp và cập nhật.

19. Bài tập theo ba mức

Mức A — phải làm được

Cho graph:

Feature của bốn nút là bốn số vô hướng:

xA=1,xB=2,xC=4,xD=8x_A=1,\quad x_B=2,\quad x_C=4,\quad x_D=8
  1. Tính neighbor mean của A.
  2. Thêm self-loop rồi tính mean mới.
  3. Sau 2 layer message passing, thông tin từ D có thể tới C không? Giải thích đường đi.

Mức B — hiểu công thức

Với adjacency matrix AA cho trước:

  1. tính A~=A+I\tilde{A}=A+I;
  2. tính degree matrix D~\tilde{D};
  3. tính từng hệ số chuẩn hóa 1/d~id~j1/\sqrt{\tilde d_i\tilde d_j};
  4. so sánh output của sum, mean và GCN normalization.

Mức C — nếu bạn muốn chứng minh

Hàm một lớp dưới đây đồng biến theo hoán vị nút, miễn là chuẩn hóa bậc cũng bị hoán vị cùng cách. Nếu

F(A,X)=A^XWF(A,X)=\hat{A}XW

và hoán vị nút bằng PP, thì:

F(PAP⊤,PX)=PF(A,X)F(PAP^\top,PX)=PF(A,X)

20. Tài liệu tham khảo và đọc thêm

  1. T. N. Kipf, M. Welling, Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017. https://arxiv.org/abs/1609.02907
  2. J. Gilmer et al., Neural Message Passing for Quantum Chemistry, ICML 2017. https://arxiv.org/abs/1704.01212
  3. B. Sanchez-Lengeling et al., A Gentle Introduction to Graph Neural Networks, Distill, 2021. https://distill.pub/2021/gnn-intro/
  4. M. M. Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, 2021. https://arxiv.org/abs/2104.13478
  5. PyTorch Geometric documentation, hiện tại dòng 2.9.x: https://pytorch-geometric.readthedocs.io/

Các hình Distill dùng trong bài được phát hành theo CC-BY 4.0 trừ khi caption của hình gốc ghi khác; cần giữ attribution khi tái sử dụng.