Mạng Nơ-ron Đồ thị: GCN, MPNN, và GAT – Giải Thích Đơn Giản

Mạng nơ-ron là một phát minh đáng kinh ngạc. Trong một thời gian dài cho đến nay, chúng được sử dụng như một thành phần quan trọng để giải quyết các vấn đề phức tạp của trí tuệ nhân tạo (AI). Về bản chất, mạng nơ-ron học một hàm toán học tinh vi để chuyển đổi dữ liệu đầu vào thành một kết quả mong muốn. Tuy nhiên, mạng nơ-ron thông thường không sử dụng kiến thức về mối quan hệ giữa các phần của dữ liệu đầu vào.

Ví dụ, để xử lý hình ảnh, người ta thường dùng phép tích chập (convolution) để kết hợp mỗi điểm ảnh với các điểm ảnh lân cận của nó, vì chúng có liên quan với nhau. Nếu không, mạng nơ-ron sẽ không biết điểm ảnh ở vị trí N có liên quan đến điểm ảnh ở vị trí N+1 hay không. Bối cảnh bổ sung này có thể cải thiện hiệu suất của mô hình. Điều này cũng đúng với đồ thị, một cấu trúc biểu diễn một tập hợp các đối tượng cùng với mối quan hệ giữa chúng.

Đồ thị có mặt ở khắp mọi nơi

Có rất nhiều đối tượng có thể được biểu diễn bằng đồ thị, chẳng hạn như các phân tử hóa học, mạng xã hội, các cầu thủ trong một trận bóng đá, hệ thống giao thông, hay bản đồ tàu điện ngầm. Đồ thị chứa đựng bối cảnh có giá trị và việc hiểu cách khai thác toàn bộ tiềm năng của chúng là rất quan trọng. Vì lý do đó, mạng nơ-ron đồ thị (Graph Neural Networks - GNN) đã ra đời, áp dụng mạng nơ-ron vào các cấu trúc đồ thị.

Một điểm tuyệt vời của GNN là sau khi được huấn luyện, chúng có thể được áp dụng cho các đồ thị mới với cấu trúc khác. Ví dụ, nếu một GNN được huấn luyện trên các phân tử của một loại nhất định, chúng ta vẫn có thể sử dụng GNN đó để thực hiện nhiệm vụ phân loại bằng cách đưa cho nó một phân tử có cấu trúc đồ thị hoàn toàn mới mà nó chưa từng thấy. Đây là cách mà, ví dụ, một trường hợp sử dụng phổ biến của GNN đã được ứng dụng: huấn luyện một mô hình để khám phá kháng sinh.

Mô tả quá trình biến đổi trạng thái đồ thị qua GNN

Sơ đồ minh họa trạng thái đồ thị đầu vào G(X, A) và đầu ra G(H, A) được tạo bởi GNN, cho thấy cấu trúc đồ thị được giữ nguyên nhưng đặc trưng của các nút được biến đổi thành các vector ẩn h[i].

Các thuật toán tích chập đồ thị (Graph Convolutional Networks - GCN)

Ý tưởng chính

Hãy quay lại với phép tích chập. Trong xử lý ảnh, chúng lấy một điểm ảnh và vùng lân cận của nó làm đầu vào, kết hợp chúng để tạo ra một giá trị mới cho điểm ảnh đó. Phương pháp này giả định có mối quan hệ giữa các điểm ảnh liền kề. Chúng ta có thể tự nhiên áp dụng ý tưởng này cho đồ thị: bằng cách chọn một nút cùng với các nút kề của nó, phương pháp của chúng ta sẽ kết hợp chúng và tạo ra một nút mới với các đặc trưng mới.

Điều thú vị là đồ thị có thể được coi là một sự tổng quát hóa của hình ảnh. Trên thực tế, mỗi điểm ảnh trong một hình ảnh được kết nối với tối đa 4 điểm ảnh liền kề. Do đó, có những điểm tương đồng về mặt ngữ nghĩa trong các quá trình tích chập của cả hai trường hợp.

Kiến trúc tầng

Thông thường, một GNN chứa một số lượng nhỏ các tầng (thường từ 2 đến 4). Số lượng tầng lớn hơn thường được tránh vì có thể gây ra vấn đề làm mượt quá mức (oversmoothing), mà chúng ta sẽ đề cập ở phần sau. Mỗi tầng biến đổi vector đặc trưng từ tầng trước bằng cách sử dụng các hàm tổng hợp (aggregation) áp dụng cho nó và các nút lân cận. Quá trình này được áp dụng song song cho từng nút một cách độc lập.

Minh họa quá trình tổng hợp thông tin của một nút

Ví dụ về một nút h[i] tổng hợp thông tin từ các nút lân cận h[1], h[2], h[3] để tạo ra biểu diễn h' cho tầng tiếp theo.

Quy tắc cập nhật

Để mô tả quy tắc cập nhật, chúng ta cần ba ma trận:

• A - Ma trận kề (adjacency matrix): A[i][j] = 1 nếu nút i và j kết nối với nhau, ngược lại A[i][j] = 0.
• H - Ma trận đặc trưng: Hàng thứ i của ma trận biểu diễn vector đặc trưng của nút thứ i.
• W - Ma trận biến đổi tuyến tính có thể học được, được chia sẻ trên tất cả các nút của đồ thị.

Bằng cách nhân A với H, chúng ta nhận được ma trận tổng đặc trưng hàng xóm. Nói cách khác, đối với mỗi nút trong A, phép nhân AH sẽ tổng hợp các giá trị đặc trưng được xác định chỉ cho các nút kề của nó. Hiểu một cách đơn giản, đây là bước đầu tiên để một nút "lắng nghe" những gì các nút xung quanh nó đang "nói".

Sau đó, chúng ta nhân kết quả AH với ma trận W – ma trận được học bởi mạng nơ-ron. Cuối cùng, áp dụng một phép biến đổi phi tuyến σ (thường là hàm ReLU hoặc LeakyReLU). Kết quả, quy tắc cập nhật là: H' = σ(AHW).

Điểm yếu của công thức cơ bản và cách khắc phục

Tuy nhiên, công thức trên có một số vấn đề:

1. Thiếu thông tin của chính nút đó: Quá trình tính toán không tính đến thông tin về bản thân nút (vì A[i][i] = 0). Giải pháp đơn giản là cộng ma trận đơn vị I vào A:  = A + I.

2. Vấn đề về tỷ lệ đặc trưng: Việc nhân ma trận làm thay đổi tỷ lệ của các đặc trưng. Để khắc phục, người ta thực hiện chuẩn hóa bằng ma trận bậc D (degree matrix), trong đó D[i][i] bằng số lượng nút kề của nút i (bao gồm cả chính nó). Công thức trở thành: H' = σ(D⁻¹ Â H W) (đây được gọi là chuẩn hóa trung bình – mean-pooling).

3. Một cách phổ biến khác để sửa tỷ lệ trong GCN là sử dụng chuẩn hóa đối xứng (Kipf & Welling, ICLR 2017): H' = σ(D⁻¹/² Â D⁻¹/² H W). Công thức này được sử dụng rộng rãi hơn vì tính ổn định của nó.

Huấn luyện và suy luận

Một điều tuyệt vời về GNN là chúng có thể khái quát hóa cho các cấu trúc đồ thị mới. Không giống như mạng nơ-ron kết nối đầy đủ (fully connected NN), nơi số lượng trọng số gắn liền với kích thước đầu vào, GNN học các phép biến đổi áp dụng cho từng nút, bất kể đồ thị có bao nhiêu nút hay cạnh. Tất cả những gì chúng cần là ma trận W được chia sẻ và có thể học.

Tuy nhiên, cần lưu ý rằng việc suy luận GNN trên một đồ thị mới thường hoạt động tốt khi cấu trúc của nó tương tự với đồ thị ban đầu dùng để huấn luyện. GNN có thể được huấn luyện trên một đồ thị lớn hoặc trên nhiều đồ thị cùng lúc. Việc huấn luyện trên nhiều đồ thị thường giúp mô hình khái quát hóa tốt hơn.

GNN đóng vai trò như một bộ trích xuất đặc trưng trung gian, tạo ra các node embeddings (vector biểu diễn nút), sau đó được đưa vào một mô hình nhỏ hơn để thực hiện các nhiệm vụ cụ thể như phân loại nút, cạnh hoặc toàn bộ đồ thị.

Mạng Nơ-ron Truyền Thông điệp (Message Passing Neural Networks - MPNN)

GCN chủ yếu hoạt động trên các đặc trưng của nút. MPNN tiến thêm một bước, cho phép mô hình hoạt động trên cả các cạnh của đồ thị. Ý tưởng cốt lõi là truyền thông điệp (message passing). Một "thông điệp" là một giá trị trừu tượng chảy dọc theo một cạnh trong quá trình tính toán.

Cách hoạt động

Hãy tưởng tượng một cặp nút i và j được kết nối với nhau qua cạnh e[i][j]. Một thông điệp gửi từ nút i đến nút j có thể được mô tả bằng một hàm (gọi là hàm thông điệp, f_e): m[j][i] = f_e(h[i], h[j], e[i][j]). Thông điệp m[j][i] là một vector (không phải là một số vô hướng).

Bước tiếp theo là tổng hợp tất cả các thông điệp đến một nút nhất định (sử dụng hàm đọc – readout function). Giá trị đặc trưng cập nhật cho nút i ở tầng tiếp theo là: h'[i] = f_v(h[i], Aggregation(m[j][i])).

Hình ảnh trực quan hóa quá trình tính toán trong MPNN

Hình ảnh trực quan quá trình tính toán cho nút h[1]. Hàm thông điệp f_e tạo ra các vector thông điệp m[2][1] và m[3][1], sau đó chúng được kết hợp với h[1] trong hàm readout để tạo ra vector đặc trưng h'[1].

MPNN rất mạnh mẽ nhưng đòi hỏi nhiều tính toán và bộ nhớ, vì phải tính toán một vector thông điệp riêng cho từng cạnh. Trong thực tế, chúng thường được sử dụng với các đồ thị nhỏ. Các hàm f_e và f_v thường là các MLP (multi-layer perceptrons) nhỏ.

Mạng Nơ-ron Chú Ý Đồ thị (Graph Attention Networks - GAT)

GAT là một sự tổng quát hóa của GCN. Chúng hoạt động giống như GCN, ngoại trừ việc thay vì sử dụng các giá trị thô của bậc (degree) của nút trong tính toán, mạng sẽ tự học các giá trị quan trọng. Khái niệm này được gọi là cơ chế chú ý (attention), tương tự như trong các mô hình Transformer nổi tiếng, có thể tự quyết định tầm quan trọng của từng cặp phần tử.

Thay vì sử dụng các hệ số cố định được xác định bởi ma trận kề, công thức cập nhật của GAT sử dụng các trọng số học được α[i][j]: h'[i] = σ(Σ α[i][j] * W * h[j])

Trọng số α[i][j] có thể hiểu là mức độ quan trọng của nút j đối với nút i. Mỗi trọng số này được tính bằng một hàm chú ý a, sau đó được chuẩn hóa bằng hàm softmax.

Ưu điểm của GAT

• Tiết kiệm bộ nhớ: Trong GAT, các hệ số học được α[i][j] chỉ là các giá trị vô hướng (scalar) cho mỗi cạnh. Trong khi đó, MPNN phải tính toán các vector thông điệp (được học) cho mỗi cạnh, tốn nhiều bộ nhớ hơn.
• Hiệu quả cao hơn: Tương tự như Transformer, GAT thường sử dụng đa đầu chú ý (multi-head attention) để thu thập nhiều tín hiệu khác nhau và tăng cường hiệu suất mô hình.

Hình ảnh minh họa cơ chế multi-head attention trong GAT

Sơ đồ minh họa việc sử dụng multi-head attention. Các mũi tên giữa các nút thể hiện các "đầu" (heads) khác nhau thu thập các tín hiệu khác nhau trong mạng.

Vấn đề "Oversmoothing" (Làm mượt quá mức)

Đây là một vấn đề khi có quá nhiều tầng xếp chồng trong GNN, biểu diễn đặc trưng của các nút trở nên gần như giống hệt nhau. Điều này xảy ra bởi vì với các hàm tổng hợp lặp đi lặp lại (ví dụ, lấy trung bình), mỗi nút dần dần hấp thụ ngày càng nhiều thông tin từ các nút lân cận và hội tụ về phía chúng.

Các kỹ thuật phổ biến để giảm oversmoothing bao gồm:

• Thêm kết nối tắt (skip connections): Vector đặc trưng của một nút được truyền trực tiếp lên tầng tiếp theo.
• Edge dropping: Giống như kỹ thuật dropout, các cạnh được chọn ngẫu nhiên sẽ bị loại bỏ trong quá trình huấn luyện, giúp giảm lượng thông tin dư thừa.

Đây cũng chính là lý do vì sao trong thực tế, GNN thường chỉ có một số lượng nhỏ các tầng (ví dụ từ 2 đến 4).

Kết luận

Trong bài viết này, chúng ta đã xem xét cách hoạt động của GNN và khám phá các kiến trúc chính. Hóa ra, chúng không có gì đặc biệt phức tạp: chúng hoạt động giống như các mạng nơ-ron tiêu chuẩn (bao gồm cả lan truyền ngược – backpropagation), ngoại trừ cách định nghĩa phép toán tích chập.

• GCN (Graph Convolutional Networks): Cơ bản nhất, hoạt động tốt với cấu trúc cục bộ, tính toán hiệu quả (O(|V|+|E|)).
• MPNN (Message Passing Neural Networks): Mạnh mẽ hơn, có thể xử lý thông tin trên cả nút và cạnh, nhưng yêu cầu nhiều tài nguyên tính toán.
• GAT (Graph Attention Networks): Linh hoạt nhất, tự học cách đánh giá tầm quan trọng của các nút lân cận, thường mang lại hiệu suất tốt nhất.

GNN đặc biệt phù hợp với các vấn đề liên quan đến dữ liệu có cấu trúc đồ thị. Dựa trên yêu cầu của bài toán, kích thước đồ thị và độ phức tạp mong muốn, bạn có thể chọn GCN, MPNN, GAT hoặc các biến thể khác. Đối với các nhà phát triển và nhà nghiên cứu tại Việt Nam, việc nắm vững các kiến trúc GNN này mở ra nhiều cơ hội trong các lĩnh vực như phân tích mạng xã hội, phát hiện gian lận tài chính, hay nghiên cứu vật liệu và thuốc mới.