4 The GNN analysis

This one is untranslated from a collaborator. Proceed with discretion on yourself.

Author: Lường Văn Tâm in accordance with the laboratory double descent research.

4.1 I.Phân tích loại đồ thị $G(V, E)$

Để phân tích loại đồ thị $G(V, E)$ trong bối cảnh toán học và lý thuyết chặt chẽ, chúng ta hãy khám phá các loại đồ thị phổ biến liên quan đến các ứng dụng học máy, đặc biệt chú ý đến cách các loại này liên quan đến các mô hình và nhiệm vụ cụ thể. Trong lý thuyết đồ thị và học máy, loại đồ thị không chỉ ảnh hưởng đến các thuộc tính cấu trúc của nó mà còn ảnh hưởng đến thiết kế của các thuật toán học tập và các phương pháp nhúng áp dụng cho nó. Chúng ta hãy đi sâu vào từng phân loại tiềm năng cho $G(V, E)$:

4.1.1 1. Đồ thị song phương (Bilateral Graphs)

Trong học máy, khái niệm đồ thị song phương “Bilateral” có thể không phải là tiêu chuẩn nhưng có thể được hiểu trong bối cảnh kết nối mạng nơ-ron. Trong mạng nơ-ron, các lớp được kết nối đầy đủ (hoặc dày đặc) kết nối mọi nút trong một lớp với mọi nút trong lớp tiếp theo, có thể được khái niệm hóa một cách lỏng lẻo là “Bilateral” vì kết nối là hai chiều. Tuy nhiên, thiết lập này không hoàn toàn phù hợp với định nghĩa cổ điển về đồ thị song phương trong lý thuyết đồ thị. Trong đồ thị song phương, chúng ta có thể mong đợi mỗi cạnh xuất hiện theo cả hai hướng giữa hai nút, tạo ra các kết nối không có hướng (đôi khi cho phép các kết nối có hướng qua lại theo cả hai hướng cho mỗi cạnh).

Do đó, nếu chúng ta xem xét một đồ thị “song phương” theo nghĩa này, thì nó sẽ ngụ ý một đồ thị vô hướng $G(V, E)$ trong đó đối với mỗi cạnh $(u, v) \in E$, tồn tại một cạnh tương ứng $(v, u) \in E$. Nói một cách toán học, điều này ngụ ý rằng nếu $G$ là song phương, thì nó đối xứng trong ma trận kề $A$ của nó, trong đó $A_{ij} = A_{ji}$. Các cấu trúc như vậy phổ biến trong các ứng dụng như mạng xã hội, nơi các kết nối (ví dụ: tình bạn) thường là lẫn nhau. Tuy nhiên, nhiều tác vụ học máy, đặc biệt là các tác vụ trong mô hình trình tự (sequence modeling) hoặc biểu diễn dựa trên luồng( flow - based representation ), không yêu cầu các kết nối song phương như vậy và thường sử dụng đồ thị có hướng.

4.1.2 2. Đồ thị có hướng và đồ thị Digraph

Đồ thị có hướng hoặc digraph là đồ thị mà các cạnh có hướng, được biểu diễn bằng các cặp đỉnh có thứ tự $(u, v)$. Trong bối cảnh học máy, đồ thị có hướng đặc biệt quan trọng khi biểu diễn các phụ thuộc hoặc luồng thông tin. Ví dụ: trong mạng nơ-ron truyền thẳng như perceptron nhiều lớp (MLP), mỗi lớp sẽ đưa vào lớp tiếp theo theo một hướng cụ thể mà không có chu kỳ hoặc kết nối ngược. Trong trường hợp này, đồ thị biểu diễn mạng sẽ có hướng, với các cạnh chỉ hướng về phía trước.

Ví dụ: - Nếu mỗi đỉnh đại diện cho một lớp trong mạng, thì các cạnh chỉ được hướng từ các lớp trước đó sang các lớp sau, phù hợp với luồng dữ liệu. - Đồ thị có hướng cũng được sử dụng để biểu diễn các phụ thuộc chuỗi, như trong xử lý ngôn ngữ tự nhiên hoặc mạng nơ-ron hồi quy (RNN), trong đó thứ tự thời gian hoặc thứ tự tuần tự là quan trọng. Ở đây, các cạnh có thể đại diện cho sự chuyển đổi từ trạng thái này sang trạng thái tiếp theo trong một chuỗi.

Về mặt hình thức, đồ thị có hướng $G = (V, E)$ có ma trận kề không đối xứng $A$, trong đó $A_{ij} \neq A_{ji}$ nói chung. Việc thiếu tính đối xứng trong $A$ thể hiện tính định hướng của các kết nối, điều cần thiết để mô hình hóa dữ liệu tuần tự hoặc dữ liệu có thứ tự nhân quả.

4.1.3 3. Đồ thị đa cạnh

Đồ thị đa cạnh là đồ thị cho phép nhiều cạnh giữa các cặp đỉnh. Điều này có nghĩa là đối với các đỉnh $u$ và $v$, có thể tồn tại một số cạnh riêng biệt, mỗi cạnh có khả năng đại diện cho các loại quan hệ khác nhau hoặc nhiều tương tác.

Trong các ứng dụng học máy: - Đồ thị đa cạnh có thể đại diện cho các mạng phức tạp với nhiều loại quan hệ. Ví dụ: trong mạng xã hội, các cạnh khác nhau có thể đại diện cho các loại quan hệ khác nhau: tình bạn, kết nối nghề nghiệp, gia đình, v.v. - Trong đồ thị tri thức hoặc hệ thống đề xuất, đồ thị đa cạnh có thể đại diện cho các loại tương tác khác nhau giữa người dùng và mặt hàng, chẳng hạn như mua hàng, lượt thích hoặc lượt xem.

Trong biểu diễn ma trận, đồ thị đa cạnh thường sử dụng biểu diễn tenxơ thay vì một ma trận kề duy nhất để giải thích cho sự đa dạng của các cạnh. Ngoài ra, đồ thị đa cạnh có thể được biểu diễn bằng cách liên kết trọng số hoặc các thuộc tính bổ sung với các cạnh để phân biệt chúng. Bằng cách này, chúng ta có thể mã hóa các loại quan hệ đa dạng trong một cấu trúc duy nhất.

4.1.4 4. Đồ thị có trọng số

Đồ thị có trọng số là đồ thị mà mỗi cạnh $(u, v) \in E$ được liên kết với trọng số $w_{uv}$, thường được biểu diễn bằng ma trận kề có trọng số $W$, trong đó mỗi mục nhập $W_{uv}$ đại diện cho trọng số của cạnh giữa$u$và$v$. Đồ thị có trọng số rất quan trọng trong các ứng dụng mà cường độ hoặc khả năng của các kết nối là quan trọng, chẳng hạn như: - Mạng nơ-ron đồ thị (GNN): Nhiều GNN tận dụng đồ thị có trọng số, trong đó trọng số cạnh có thể đại diện cho cường độ tương tác hoặc sự giống nhau giữa các nút. - Bài toán tối ưu hóa: Trong các bài toán như người bán hàng đi du lịch hoặc đường đi ngắn nhất, trọng số cạnh đại diện cho khoảng cách hoặc chi phí.

Trọng số thêm một lớp phức tạp cho đồ thị, vì các thuật toán phải tính đến những điều này khi tính toán các thuộc tính như đường dẫn, kết nối và cụm. Ma trận kề có trọng số thường đối xứng đối với đồ thị không có hướng và không đối xứng đối với đồ thị có hướng.

4.1.5 5. Đồ thị không có hướng

Trong đồ thị không có hướng, các cạnh không có hướng, có nghĩa là nếu có một cạnh giữa $u$ và $v$, nó có thể được đi qua theo cả hai hướng. Loại đồ thị này phổ biến khi biểu diễn các mối quan hệ lẫn nhau hoặc tương tác hai chiều trong đó hướng của kết nối không quan trọng về mặt nội tại.

Đồ thị không có hướng được biểu diễn bằng ma trận kề đối xứng, trong đó $A_{ij} = A_{ji}$. Các trường hợp sử dụng phổ biến bao gồm: - Mạng xã hội: Nếu chúng ta đang đại diện cho tình bạn lẫn nhau, thì đồ thị không có hướng là phù hợp. - Lọc cộng tác trong hệ thống đề xuất: Nếu cả người dùng và mặt hàng đều được coi là đối xứng, thì đồ thị không có hướng giúp nắm bắt bản chất có đi có lại của sở thích hoặc ái lực.

Trong đồ thị không có hướng, các cạnh thường dễ xử lý hơn về mặt tính toán vì tính đối xứng có thể làm giảm số lượng phép tính cần thiết cho các phép toán nhất định (ví dụ: phân rã giá trị riêng).

4.1.6 6. Siêu đồ thị và đồ thị lưỡng phân

Mặc dù không được đề cập trực tiếp trong bài báo, siêu đồ thị và đồ thị lưỡng phân là các cấu trúc khác đáng xem xét trong các ứng dụng học máy: - Siêu đồ thị cho phép các cạnh (siêu cạnh) kết nối nhiều hơn hai nút. Điều này có thể hữu ích trong các ứng dụng như nhóm người dùng dựa trên các hoạt động hoặc mặt hàng được chia sẻ, trong đó mỗi siêu cạnh có thể đại diện cho một nhóm. - Đồ thị lưỡng phân bao gồm hai tập hợp nút rời rạc, trong đó các cạnh chỉ kết nối các nút giữa các tập hợp (không nằm trong cùng một tập hợp). Các đồ thị này rất phù hợp trong các hệ thống đề xuất, trong đó một tập hợp các nút đại diện cho người dùng và tập hợp còn lại đại diện cho các mặt hàng.

Tóm tắt các loại đồ thị và tính phù hợp của chúng đối với học máy Dựa trên loại dữ liệu và tác vụ học $G(V,E)$ có thể được phân loại thành bất kỳ loại nào sau đây:

Song phương/Vô hướng(Bilateral/Undirected) cho các mối quan hệ tương hỗ, trong đó hướng cạnh không quan trọng và các kết nối là có đi có lại.
Có định hướng/Điểu đồ hướng(Directed/Digraph) đối với dữ liệu có thứ tự cố hữu, chẳng hạn như kiến trúc dựa trên luồng (MLP hoặc RNN) hoặc cấu trúc nhân quả.
Đa đồ thị(Multigraph) khi tồn tại nhiều mối quan hệ riêng biệt giữa các nút.
Đồ thị có trọng số(Weighted Graph) nếu cường độ cạnh thay đổi và những biến thể này rất quan trọng đối với mô hình.
Đồ thị vô hướng(Undirected Graph) trong các ứng dụng mà các kết nối vốn có bản chất song phương và đối xứng.

Mỗi loại áp đặt các ràng buộc và khả năng khác nhau về mặt biểu diễn tính toán, khả năng diễn giải và tiềm năng học tập trong các mô hình học máy dựa trên đồ thị. Việc lựa chọn loại cẩn thận là rất quan trọng vì nó ảnh hưởng đến các chiến lược nhúng, phương pháp tổng hợp lân cận và khả năng diễn giải các tính năng nút đã học trong các mô hình như GNN.

4.1.7 8Không gian nhúng của đồ thị $G(V, E)$

Không gian nhúng của đồ thị $G(V, E)$ là một không gian vectơ có cấu trúc, thường có số chiều thấp hơn, trong đó các đỉnh $v \in V$ được biểu diễn bằng các vectơ. Việc lựa chọn không gian này là rất quan trọng, vì nó xác định mức độ nắm bắt thông tin cấu trúc về đồ thị. Các đặc điểm của không gian nhúng như độ sâu, số chiều và độ phong phú có thể ảnh hưởng lớn đến khả năng khái quát hóa của mô hình, diễn giải các thuộc tính cấu trúc và cho phép tính toán hiệu quả cho các tác vụ tiếp theo.

4.1.7.1 Xác định không gian nhúng cho đồ thị $G(V, E)$

Không gian nhúng là gì? Trong bối cảnh đồ thị, không gian nhúng là một không gian vectơ $\mathbb{R}^d$ (trong đó $d \ll |V|$) trong đó mỗi đỉnh $v \in V$ được biểu diễn bằng một vectơ $\mathbf{z}_v \in \mathbb{R}^d$. Các nhúng này được học hoặc tính toán sao cho các mối quan hệ hình học (khoảng cách, góc hoặc thuộc tính topo) trong không gian vectơ phản ánh các mối quan hệ trong đồ thị $G$.

Số chiều $d$ của không gian nhúng và hàm ánh xạ được thiết kế để nắm bắt càng nhiều càng tốt thông tin cấu trúc và quan hệ có liên quan trong $G$. Mục đích là để các nút “gần” trong đồ thị (dựa trên đường dẫn, kề nhau hoặc vai trò cấu trúc) có các nhúng gần nhau trong $\mathbb{R}^d$ theo một số số liệu khoảng cách.

Ví dụ trong bài toán người bán hàng đi du lịch (TSP) Đối với các tác vụ như TSP, không gian nhúng thường sử dụng không gian Euclide 2D trong đó các đỉnh được định vị dựa trên tọa độ trong thế giới thực (ví dụ: các thành phố trên bản đồ). Ở đây, ma trận kề hoặc khoảng cách biểu thị khoảng cách theo cặp giữa các đỉnh trong $\mathbb{R}^2$ , nắm bắt khoảng cách hình học là mối quan hệ chính giữa các đỉnh. Số chiều $d = 2$ là đủ vì bài toán vốn có tính chất không gian.
Nhúng đồ thị trong học máy Trong các bối cảnh học máy phức tạp hơn (chẳng hạn như đối với Mạng nơ-ron đồ thị hoặc phân loại nút), không gian nhúng có thể thay đổi đáng kể về số chiều và thường là số chiều cao. Số chiều $d$ được chọn dựa trên độ phức tạp của cấu trúc đồ thị, độ phong phú của thông tin mà mỗi nút cần nắm bắt và các yêu cầu của tác vụ học tập.

4.2 II. Thuộc tính của không gian nhúng: Độ sâu, kích thước và độ phong phú

Bây giờ, chúng ta hãy phân tích từng thuộc tính của không gian nhúng một cách chi tiết hơn.

4.2.0.0.1 1. Độ sâu và kích thước của không gian nhúng

- Độ sâu(Depth): có thể được xem như là mức độ mà một nhúng có thể nắm bắt các quan hệ đồ thị phức tạp hoặc bậc cao hơn thông qua nhiều lớp hoặc cấp độ tổng hợp. Nói một cách thực tế, điều này thường liên quan đến số lượng lớp trong một mô hình, chẳng hạn như trong Mạng nơ-ron đồ thị (GNN), trong đó độ sâu có thể đề cập đến số lượng lớp tổng hợp lân cận (bước nhảy) được sử dụng để tạo ra mỗi nhúng.

- Số chiều Dimensionality ($d$): Kích thước của không gian nhúng, tức là số chiều $d$, có thể dao động từ số chiều thấp (ví dụ: $d = 2$ hoặc $3$ cho nhúng trực quan hoặc không gian) đến số chiều cao (ví dụ: $d = 128$ hoặc $d = 512$ trong mạng xã hội phức tạp hoặc đồ thị tri thức). Số chiều cao hơn cho phép nhúng nắm bắt các mối quan hệ phức tạp hơn và các điểm tinh tế trong cấu trúc đồ thị. Ví dụ: - Nhúng nông(Shallow embeddings): Các phương pháp như Laplacian Eigenmaps hoặc DeepWalk có thể sử dụng số chiều thấp hơn (ví dụ: $d \sim 10$ đến $100$), tập trung vào việc bảo toàn cấu trúc lân cận cục bộ. - Nhúng sâu(Deep embeddings): GNN hiện đại thường tận dụng số chiều $d \sim 100$ đến $512$ hoặc thậm chí cao hơn, đặc biệt là trong đồ thị dày đặc hoặc cho các ứng dụng như phân loại nút và dự đoán liên kết, trong đó các chi tiết cấu trúc chi tiết là rất quan trọng.

- Kích thước nhúng so với độ phức tạp của đồ thị $G$: Không gian nhúng cần đủ lớn để phản ánh độ đa dạng cấu trúc và khả năng kết nối trong đồ thị. Đối với các mạng có kết nối cao, phức tạp với các loại nút hoặc vai trò đa dạng (ví dụ: mạng xã hội hoặc mạng sinh học), kích thước nhúng lớn hơn cho phép biểu diễn đặc trưng phong phú hơn. Ngược lại, các đồ thị đơn giản hơn có thể không hưởng lợi đáng kể từ các nhúng có số chiều cao.

4.2.0.0.2 2. Độ phong phú của không gian nhúng

Để xác định độ phong phú của không gian nhúng, chúng ta xem xét mức độ hiệu quả của nó trong việc nắm bắt các sắc thái cấu trúc, mối quan hệ và sự đa dạng của các nút trong đồ thị. Độ phong phú có thể được đánh giá dựa trên:

- Bảo toàn lân cận(Neighborhood Preservation): Không gian nhúng phong phú nên nắm bắt cấu trúc lân cận cục bộ(local neighborhood) một cách chính xác, có nghĩa là các nút gần nhau trong đồ thị cũng nên gần nhau trong không gian nhúng. Ví dụ: - Các kỹ thuật như node2vec sử dụng bước đi ngẫu nhiên có thiên vị để tạo ra các nhúng nhấn mạnh sự giống nhau của lân cận. - GraphSAGE và các phương pháp dựa trên GNN tương tự tổng hợp thông tin từ nhiều bước nhảy, nắm bắt thông tin lân cận đa cấp, làm phong phú thêm không gian nhúng bằng cách mã hóa cả ngữ cảnh cục bộ và toàn cục.

- Vai trò cấu trúc và phát hiện cộng đồng: Không gian nhúng phong phú nên phân biệt vai trò cấu trúc (ví dụ: nút trung tâm so với nút ngoại vi, nút cầu nối) và có khả năng tách các nút thành cộng đồng hoặc cụm. Các phương pháp nhúng đạt được điều này bằng cách sử dụng các thuộc tính như mẫu kết nối, hệ số phân cụm và mô-típ bậc cao hơn: - Các phương pháp như struc2vec hoặc GraphWave nhúng các nút dựa trên sự giống nhau về cấu trúc, giúp không gian nhúng nắm bắt các vai trò vượt ra ngoài khả năng kết nối đơn giản. - Kiến trúc GNN cũng có thể kết hợp thông tin cộng đồng bằng cách tổng hợp các đặc trưng lân cận trên một số lớp.

- Mã hóa các mối quan hệ bậc cao(Encoding Higher-Order Relationships): Không gian nhúng phong phú cũng có thể nắm bắt mô-típ đồ thị bậc cao(higher-order graph motifs) (ví dụ: hình tam giác, clique) hoặc cấu trúc đồ thị con. Điều này đặc biệt phù hợp trong các ứng dụng như hóa học hoặc sinh học, trong đó các mẫu nhất định trong mạng tương tác phân tử hoặc protein mang ý nghĩa ngữ nghĩa. Không gian nhúng nắm bắt các mô-típ như vậy thường được thiết kế bằng cách sử dụng: - Các phương pháp dựa trên bước đi ngẫu nhiên mã hóa gián tiếp các cấu trúc này bằng cách tổng hợp thống kê đồng xuất hiện. - Phương pháp phổ(Spectral methods) và GNN tích chập(convolutional GNNs) nắm bắt cấu trúc topo thông qua các bộ lọc phổ hoặc tổng hợp lân cận.

- Tích hợp thuộc tính và đặc trưng: Trong đồ thị mà các nút có các đặc trưng liên quan (ví dụ: hồ sơ trong mạng xã hội, thuộc tính phân tử), độ phong phú cũng có thể đề cập đến mức độ không gian nhúng kết hợp các đặc trưng này cùng với thông tin cấu trúc. GNN, đặc biệt là những GNN sử dụng cơ chế chú ý hoặc bộ mã hóa nhận biết thuộc tính, đạt được độ phong phú cao hơn bằng cách nhúng thông tin đặc trưng cùng với cấu trúc đồ thị.

4.2.0.1 Độ sâu, kích thước và độ phong phú: Một góc nhìn kết hợp

Tóm tắt:

- Độ sâu của không gian nhúng (được biểu thị bằng các lớp tổng hợp hoặc các lớp mô hình) xác định ngữ cảnh của mỗi nhúng nút trong đồ thị có phạm vi bao xa. - Kích thước (số chiều $d$) lý tưởng nên cân bằng giữa hiệu quả tính toán với nhu cầu biểu diễn độ phức tạp cấu trúc của đồ thị. - Độ phong phú đề cập đến khả năng của không gian nhúng trong việc mã hóa các mối quan hệ đa dạng, vai trò cấu trúc và các mẫu bậc cao, cùng với thông tin dựa trên thuộc tính khi có thể áp dụng. Độ phong phú có thể được đánh giá định lượng bằng cách đo lường chất lượng phân cụm, độ chính xác phân loại trong các tác vụ tiếp theo hoặc tính nhất quán tôpô (ví dụ: bảo toàn khoảng cách đường đi ngắn nhất hoặc cấu trúc cộng đồng).

Đối với các mạng có số chiều cao, giàu thông tin (chẳng hạn như mạng xã hội hoặc mạng sinh học), không gian nhúng có độ sâu cao, số chiều lớn và các cơ chế tổng hợp lân cận và đặc trưng được điều chỉnh cẩn thận sẽ cung cấp các biểu diễn mạnh mẽ và “phong phú” nhất, cho phép phân tích phức tạp tiếp theo như phân loại nút, phát hiện cộng đồng và dự đoán liên kết.

4.3 III. Mã hóa nút (Node encoding) $\mathsf{ENC}(V, E_{\text{neigh}})$

Mã hóa nút $\mathsf{ENC}(V, E_{\text{neigh}})$ là một biểu diễn nắm bắt thông tin về mỗi đỉnh $v \in V$ và các lân cận$E_{\text{neigh}}$ của nó, tức là tập hợp các cạnh kết nối $v$ với các nút lân cận. Mã hóa $\mathsf{ENC}(v)$ được định hình bằng cách tổng hợp các đặc trưng từ các nút và cạnh lân cận, tạo ra một biểu diễn vectơ tích hợp cấu trúc đồ thị cục bộ với các thuộc tính nút. Chúng ta hãy phân tích các thành phần chính của mã hóa này, hình dạng của nó và các xu hướng như độ thưa thớt.

4.3.0.1 1. Hình dạng của mã hóa nút $\mathsf{ENC}(V, E_{\text{neigh}})$

Hình dạng của $\mathsf{ENC}(v)$, biểu diễn vectơ được mã hóa của nút $v$, phụ thuộc vào một số yếu tố:

Số chiều của không gian nhúng ($d$): Thông thường, $\mathsf{ENC}(v) \in \mathbb{R}^d$, trong đó $d$ là số chiều nhúng được chọn cho mô hình. Ví dụ: - Trong các nhúng đơn giản hơn, số chiều thấp, $d$ có thể nhỏ tới 10–50. - Đối với các mô hình đồ thị sâu, đặc biệt là trong các mạng phức tạp, $d$ có thể dao động từ 128 đến 512 hoặc thậm chí cao hơn, vì số chiều lớn hơn giúp nắm bắt các cấu trúc phức tạp hơn.
Tổng hợp phân lớp: Trong các phương pháp như Mạng nơ-ron đồ thị (GNN), mã hóa nút thường được cập nhật lặp đi lặp lại trên nhiều lớp, trong đó mỗi lớp tổng hợp thông tin từ các nút ở khoảng cách ngày càng lớn hơn. Nếu GNN có $K$ lớp, thì mã hóa cuối cùng $\mathsf{ENC}(v)$ biểu thị thông tin được tổng hợp từ các nút cách xa tới $K$ - bước nhảy. Số chiều $d$ vẫn cố định trên các lớp, nhưng nội dung của $\mathsf{ENC}(v)$ trở nên phong phú hơn dần với mỗi lớp.

Ví dụ: nếu sử dụng Mạng tích chập đồ thị (GCN), mã hóa cho mỗi nút $v$ sau $K$ lớp có thể trông giống như sau: \[ \mathsf{ENC}(v) = f\left(\sigma\left(W^{(K)} \cdots \sigma\left(W^{(1)} X_v^{(1)} \right)\right)\right) \] trong đó $W^{(k)}$ là trọng số đã học,$\sigma$là hàm kích hoạt và $X_v^{(1)}$ biểu thị các đặc trưng nút ban đầu.

4.3.0.2 2. Các thành phần của mã hóa

Mã hóa nút $\mathsf{ENC}(v)$ thường nhận một số loại thông tin từ chính nút đó và các nút lân cận của nó. Các thành phần phổ biến bao gồm:

Đặc trưng nút: Mỗi nút$v$thường có các đặc trưng được liên kết, được biểu thị bằng vectơ đặc trưng $X_v$ (ví dụ: nhân khẩu học cho người dùng trong mạng xã hội, thuộc tính phân tử cho các nguyên tử trong phân tử). Vectơ đặc trưng này thường là đầu vào ban đầu cho quá trình mã hóa và được biến đổi qua các lớp để làm phong phú thêm biểu diễn.
Tổng hợp lân cận: Mã hóa kết hợp thông tin tổng hợp từ các nút lân cận. Tổng hợp này có thể được tính toán thông qua các chiến lược khác nhau: - Trung bình: Tính trung bình các đặc trưng của các nút lân cận, điều này cho biết cảm nhận chung về vùng lân cận đồng thời đơn giản và hiệu quả. - Tổng hoặc gộp: Cộng hoặc sử dụng gộp max/trung bình trên các đặc trưng lân cận, có thể nắm bắt thông tin biểu cảm hoặc đại diện hơn. - Cơ chế chú ý: Trong một số mô hình nâng cao (ví dụ: Mạng chú ý đồ thị, GAT), tổng hợp được tính trọng số bằng điểm chú ý, cho phép mã hóa ưu tiên các nút lân cận nhất định dựa trên mức độ liên quan của chúng.
Đặc trưng cạnh: Nếu các cạnh có các đặc trưng được liên kết (ví dụ: trọng số, loại hoặc mối quan hệ), thì những đặc trưng này cũng có thể được bao gồm trong mã hóa. Các mô hình như GCN quan hệ (R-GCN) và Mạng chú ý đồ thị (GAT) có thể sử dụng các đặc trưng cạnh này để sửa đổi cách tổng hợp các đặc trưng nút lân cận.

4.3.0.3 3. Thuộc tính của mã hóa: Độ thưa thớt và nội dung thông tin

Mã hóa $\mathsf{ENC}(v)$ có một số thuộc tính đáng chú ý phụ thuộc vào cấu trúc và đặc điểm của đồ thị:

Xu hướng thưa thớt: Trong nhiều đồ thị trong thế giới thực, đặc biệt là các mạng quy mô lớn, các kết nối nút là thưa thớt (tức là mỗi nút kết nối với một tập hợp con nhỏ các nút khác so với tổng số). Độ thưa thớt này thường mở rộng đến mã hóa, đặc biệt là trong các mô hình sử dụng biểu diễn thưa thớt (ví dụ: ma trận kề thưa thớt). Trong những trường hợp như vậy: - Tổng hợp thưa thớt: Tổng hợp các đặc trưng từ vùng lân cận thưa thớt dẫn đến các vectơ mã hóa có thể chứa hầu hết các số 0 hoặc giá trị thấp cho các chiều không được kết nối. - Độ thưa thớt đặc trưng: Nếu bản thân các đặc trưng nút là thưa thớt (ví dụ: thuộc tính được mã hóa nhị phân hoặc một nóng), thì $\mathsf{ENC}(v)$ kết quả cũng có thể biểu hiện độ thưa thớt, đặc biệt là sau các lớp tổng hợp duy trì hoặc khuếch đại các đặc trưng thưa thớt này.
Thông tin cục bộ: Trong GNN nông (với số lượng lớp nhỏ), mã hóa $\mathsf{ENC}(v)$ chủ yếu phản ánh thông tin về vùng lân cận ngay lập tức của nút. Biểu diễn cục bộ này có hiệu quả đối với các tác vụ mà ngữ cảnh cục bộ (ví dụ: lân cận bậc nhất hoặc bậc hai) là phù hợp nhất.
Lan truyền các thuộc tính cấu trúc: Với các mạng sâu hơn (nhiều lớp hơn), mã hóa tích hợp thông tin từ một phần lớn hơn của đồ thị, nắm bắt không chỉ cấu trúc cục bộ mà còn nhiều vai trò toàn cục hoặc cấu trúc hơn (ví dụ: tính trung tâm, phân cụm trong một cộng đồng). Điều này quan trọng đối với các tác vụ yêu cầu hiểu các cấu trúc đồ thị rộng hơn.
Độ phong phú đặc trưng so với giảm số chiều: Trong khi số chiều $d$ của $\mathsf{ENC}(v)$ có thể vẫn cố định, độ phong phú của mã hóa tăng lên với mỗi lớp tổng hợp khi kết hợp nhiều thông tin lân cận đa dạng hơn. Tuy nhiên, để duy trì hiệu quả tính toán, một số GNN sử dụng các kỹ thuật giảm số chiều trong các lớp, giảm kích thước đặc trưng đồng thời bảo toàn các đặc điểm cấu trúc chính.

4.3.0.4 Ví dụ về hình dạng và thuộc tính trong các mô hình đồ thị cụ thể

Chúng ta hãy xem xét một số mô hình cụ thể và cách chúng định hình $\mathsf{ENC}(v)$:

Mạng tích chập đồ thị (GCN): - GCN sử dụng trung bình hoặc tổng trọng số để tổng hợp các đặc trưng nút lân cận. Sau mỗi lớp, hình dạng của $\mathsf{ENC}(v)$ được kiểm soát bởi số chiều nhúng$d$đã chọn, với mỗi lớp thêm thông tin lân cận. - Các vectơ được mã hóa có xu hướng giữ lại các mẫu cấu trúc dày đặc, mặc dù độ thưa thớt có thể xuất hiện nếu các đặc trưng ban đầu hoặc cấu trúc kề là thưa thớt.
Mạng chú ý đồ thị Graph Attention Networks (GAT): - Trong GAT, hình dạng mã hóa $\mathsf{ENC}(v)$ vẫn ở trong $\mathbb{R}^d$, nhưng mỗi phần tử trong vectơ được tính trọng số bằng điểm chú ý được áp dụng cho các đặc trưng lân cận. Điều này cho phép mã hóa phong phú hơn, thường thưa thớt hơn, vì các nút lân cận ít liên quan hơn bị giảm trọng số hoặc bỏ qua. - Mã hóa có thể thể hiện độ thưa thớt có chọn lọc dựa trên cơ chế chú ý, trong đó chỉ một tập hợp con thông tin lân cận đóng góp đáng kể vào $\mathsf{ENC}(v)$.

Tính toán điểm chú ý: GAT tính toán điểm chú ý giữa mỗi cặp nút dựa trên đặc trưng của chúng và đặc trưng của cạnh nối chúng. Điểm chú ý này phản ánh mức độ quan trọng của nút lân cận đối với nút hiện tại.
Tổng hợp lân cận dựa trên chú ý: GAT sử dụng điểm chú ý để tính trọng số cho đặc trưng của các nút lân cận trước khi tổng hợp chúng.
Ví dụ: Trong đồ thị tri thức, nếu một cạnh có trọng số cao hơn, GAT sẽ gán điểm chú ý cao hơn cho nút lân cận được kết nối bởi cạnh đó, cho phép mô hình tập trung vào các nút lân cận quan trọng hơn.

Công thức tính điểm chú ý trong GAT có thể được viết như sau:

\[ e_{ij} = \alpha \left( \mathbf{W} h_i , \mathbf{W} h_j, \mathbf{e}_{ij} \right) \]

Trong đó:

$e_{ij}$ là điểm chú ý giữa nút i và nút j.
$α$ là hàm tính điểm chú ý (ví dụ: một lớp perceptron một lớp).
$W$ là ma trận trọng số được chia sẻ.
$h_i$ và $h_j$ là mã hóa của nút i và nút j.
$e_{ij}$ là đặc trưng của cạnh nối nút i và nút j.

Sau khi tính toán điểm chú ý, GAT chuẩn hóa chúng bằng hàm softmax và sử dụng chúng để tính trọng số cho đặc trưng của các nút lân cận:

\[ \alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}_i} \exp(e_{ik})} \]

Cuối cùng, GAT tổng hợp thông tin từ các nút lân cận dựa trên trọng số chú ý:

\[ h_i^{(l+1)} = \sigma \left( \sum_{j \in \mathcal{N}_i} \alpha_{ij} \mathbf{W} h_j^{(l)} \right) \]

Tóm lại, cả R-GCN và GAT đều cho phép tích hợp đặc trưng cạnh vào quá trình mã hóa nút. R-GCN sử dụng ma trận trọng số riêng biệt cho từng loại quan hệ, trong khi GAT sử dụng cơ chế chú ý để tính trọng số cho đặc trưng của các nút lân cận dựa trên đặc trưng cạnh. Bằng cách kết hợp đặc trưng cạnh, các mô hình này có thể học các biểu diễn phong phú hơn và nắm bắt các sắc thái quan trọng trong cấu trúc đồ thị.

Mạng tích chập đồ thị quan hệ Relational Graph Convolutional Networks (R-GCN): R-GCN xử lý các đồ thị có nhiều loại quan hệ (tức là các loại cạnh khác nhau) bằng cách sử dụng các phép biến đổi cụ thể cho từng loại quan hệ trong quá trình tổng hợp lân cận.

Ma trận trọng số riêng biệt: Đối với mỗi loại quan hệ $r$, R-GCN sử dụng một ma trận trọng số riêng biệt $W_r$. Điều này cho phép mô hình học các mẫu khác nhau cho các loại quan hệ khác nhau.
Tổng hợp lân cận dựa trên quan hệ: Khi tổng hợp thông tin từ các nút lân cận, R-GCN áp dụng ma trận trọng số tương ứng với loại quan hệ của cạnh nối nút hiện tại với nút lân cận đó.
Ví dụ: Trong mạng xã hội, nếu có các loại quan hệ “bạn bè”, “đồng nghiệp” và “gia đình”, R-GCN sẽ sử dụng ba ma trận trọng số khác nhau để tổng hợp thông tin từ các nút lân cận thuộc mỗi loại quan hệ.

Công thức cập nhật mã hóa nút trong R-GCN có thể được viết như sau:

\[ h_i^{(l+1)} = \sigma \left( \sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_i^r} \frac{1}{c_{i,r}} W_r^{(l)} h_j^{(l)} + W_0^{(l)} h_i^{(l)} \right) \]

Trong đó:

$h_i(l)$ là mã hóa của nút i tại lớp l.
$R$ là tập hợp các loại quan hệ.
$N_i^r$ là tập hợp các nút lân cận của nút i thông qua quan hệ r.
$c{i,r}$ là hằng số chuẩn hóa (ví dụ: bậc của nút i đối với quan hệ r).
$W_r(l)$là ma trận trọng số cho quan hệ r tại lớp l.
W$_0(l)$là ma trận trọng số cho tự kết nối tại lớp l.
$σ$ là hàm kích hoạt phi tuyến.

4.3.0.5 Tóm tắt

Hình dạng của $\mathsf{ENC}(v)$ chủ yếu được xác định bởi số chiều nhúng $d$, được chọn dựa trên nhiệm vụ và độ phức tạp của đồ thị. Hình dạng này nhất quán trên các nút trong một lớp nhất định nhưng có thể thay đổi trên các lớp trong các mô hình sâu.
Các thành phần: Đặc trưng nút, tổng hợp lân cận và đặc trưng cạnh đều góp phần vào $\mathsf{ENC}(v)$, với các hàm tổng hợp như trung bình, tổng và chú ý tinh chỉnh mã hóa.
Thuộc tính: - Độ thưa thớt(Sparsity) thường phát sinh trong đồ thị thưa thớt hoặc khi sử dụng các đặc trưng ban đầu thưa thớt. - Cục bộ so với toàn cục(Local vs. Global): Mã hóa có thể dao động từ thông tin cục bộ đến nhận thức toàn cục tùy thuộc vào độ sâu của tổng hợp. - Độ phong phú(Richness) là một hàm của độ sâu lân cận và sự đa dạng đặc trưng, với mã hóa phong phú hơn nắm bắt nhiều vai trò cấu trúc và thông tin cấp cộng đồng hơn.

Thông qua tổng hợp trên nhiều lớp, mã hóa$\mathsf{ENC}(v)$cuối cùng trở thành một biểu diễn nhỏ gọn nhưng biểu cảm của cả các thuộc tính nội tại của nút và ngữ cảnh cấu trúc của nó trong đồ thị. ## IV. Độ thưa thớt kết nối (Connectivity sparsity) trong đồ thị $G(V, E)$

Trong bối cảnh đồ thị $G(V, E)$, độ thưa thớt kết nối của các nút trung bình định lượng mức độ thưa thớt kết nối của đồ thị. Số liệu này giúp hiểu số lượng cạnh trung bình trên mỗi nút so với số lượng kết nối tối đa có thể có và cung cấp thông tin chi tiết về mật độ hoặc độ thưa thớt của cấu trúc đồ thị. Dưới đây là cách chúng tôi phân tích khái niệm này chính xác hơn:

4.3.0.6 1. Định nghĩa độ thưa thớt kết nối

Độ thưa thớt kết nối có thể được định nghĩa chính thức là tỷ lệ giữa số lượng cạnh thực tế với số lượng cạnh tối đa có thể có, tập trung vào bậc trung bình hoặc kết nối trung bình trên mỗi nút.

Đối với đồ thị vô hướng $G(V, E)$, số lượng cạnh tối đa có thể có là $\binom{|V|}{2} = \frac{|V|(|V|-1)}{2}$, trong khi đối với đồ thị có hướng, đó là $|V|(|V|-1)$ vì mỗi nút có thể có một cạnh có hướng đến mọi nút khác.

Do đó, độ thưa thớt (Connectivity Sparsity) kết nối của $G$ có thể được tính bằng: \[ \text{Connectivity Sparsity} = 1 - \frac{2|E|}{|V|(|V|-1)} \] cho đồ thị vô hướng.

hoặc \[ \text{Connectivity Sparsity} = 1 - \frac{|E|}{|V|(|V|-1)} \] cho đồ thị có hướng. Thước đo này cho giá trị từ 0 đến 1, trong đó giá trị gần bằng 1 cho biết độ thưa thớt cao (ít kết nối so với mức tối đa có thể có) và giá trị gần bằng 0 cho biết đồ thị dày đặc. #### 2. Bậc nút trung bình

Một cách khác để đo lường độ thưa thớt là thông qua bậc trung bình(Average Degree) của các nút, là số lượng kết nối trung bình trên mỗi nút: \[ \text{Average Degree} = \frac{2|E|}{|V|} \] cho đồ thị vô hướng, hoặc \[ \text{Average Degree} = \frac{|E|}{|V|} \] cho đồ thị có hướng.

Bậc của nút $v$, được ký hiệu là $\deg(v)$, là số lượng cạnh được kết nối với $v$. Đối với đồ thị thưa thớt, bậc trung bình thường thấp hơn nhiều so với$|V| - 1$, số lượng kết nối có thể có trên mỗi nút trong đồ thị đầy đủ.

4.3.0.7 3. Diễn giải độ thưa thớt kết nối

Độ thưa thớt kết nối cho chúng ta biết cụm cục bộ hoặc kết nối lỏng lẻo của đồ thị trung bình như thế nào. Đồ thị thưa thớt có xu hướng thể hiện: - Phân cụm cục bộ(Localized clustering): Các nút có ít kết nối, dẫn đến các cụm nhỏ, biệt lập thay vì cấu trúc được kết nối đầy đủ. - Đường kính lớn và đường dẫn dài hơn(High diameter and longer paths): Với ít kết nối hơn, các đường dẫn giữa hai nút ngẫu nhiên có xu hướng dài hơn, làm tăng độ dài đường dẫn ngắn nhất trung bình.

Trong các ứng dụng học máy, độ thưa thớt kết nối có thể ảnh hưởng đến: - Truyền tin trong GNN: Đồ thị thưa thớt có thể yêu cầu nhiều lớp hơn trong GNN để nắm bắt đủ thông tin trên các nút ở xa. - Hiệu quả tính toán: Đồ thị thưa thớt thường hiệu quả về mặt tính toán để xử lý do ít cạnh hơn, làm cho chúng phù hợp để lưu trữ và tính toán bằng cách sử dụng biểu diễn ma trận thưa thớt.

4.3.0.8 4. Ví dụ tính toán

Để minh họa, hãy xem xét một đồ thị có nút $|V| = 1000$ và cạnh $|E| = 3000$ : - Độ thưa thớt vô hướng: Đối với đồ thị vô hướng, \[ \text{Connectivity Sparsity} = 1 - \frac{2 \cdot 3000}{1000 \times 999} = 1 - \frac{6000}{999000} \approx 0.994\] Giá trị gần 1 này cho biết đồ thị rất thưa thớt.

Bậc trung bình: Bậc trung bình của mỗi nút trong đồ thị vô hướng này sẽ là: \[ \text{Average Degree} = \frac{2 \cdot 3000}{1000} =6\] Với trung bình 6 kết nối trên mỗi nút trong số 999 kết nối có thể có, đồ thị này có mật độ kết nối rất thấp, điển hình của mạng thưa thớt.

4.3.0.9 5. Ứng dụng trong đồ thị thế giới thực

Các đồ thị trong thế giới thực, như mạng xã hội hoặc mạng sinh học, thường thể hiện độ thưa thớt kết nối cao do hiện tượng thế giới nhỏ và phân phối bậc theo luật lũy thừa: - Mạng thế giới nhỏ: Các mạng này có phân cụm cục bộ cao nhưng tương đối ít cạnh kết nối các phần ở xa của đồ thị, dẫn đến các vùng lân cận cục bộ thưa thớt nhưng được kết nối với nhau cao. - Mạng không có quy mô: Trong các mạng này, một số nút (trung tâm) có bậc cao, nhưng hầu hết các nút có bậc thấp, góp phần vào độ thưa thớt chung.

4.3.0.10 Tóm tắt

Độ thưa thớt kết nối đo lường mức độ thưa thớt kết nối của đồ thị, với giá trị gần bằng 1 cho biết đồ thị thưa thớt.
Bậc trung bình cung cấp góc nhìn cấp nút về độ thưa thớt.
Đồ thị thưa thớt phổ biến trong các mạng trong thế giới thực, thường dựa vào các biểu diễn thưa thớt hiệu quả để có lợi thế về tính toán.

Hiểu biết về độ thưa thớt kết nối là rất quan trọng để thiết kế các mô hình học máy có thể thích ứng với cấu trúc độc đáo của đồ thị thưa thớt, đặc biệt là trong Mạng nơ-ron đồ thị, nơi sử dụng các thuật toán truyền tin.

4.4 V. Quan hệ thứ tự và vị trí trong học máy dựa trên đồ thị

Trong học máy dựa trên đồ thị, đặc biệt là trong các lĩnh vực như Xử lý ngôn ngữ tự nhiên (NLP), các quan hệ như thứ tự và quan hệ vị trí đóng vai trò quan trọng trong việc định hình mã hóa đồ thị và giải quyết vấn đề. Các quan hệ này xác định kết nối và cấu trúc của các nút, có thể ảnh hưởng đến cách thông tin được tổng hợp, mã hóa và cuối cùng được mô hình diễn giải. Chúng ta hãy khám phá các loại quan hệ và tác động của chúng đối với mã hóa đồ thị và hiệu suất mô hình.

4.4.0.1 1. Các loại quan hệ trong mã hóa đồ thị

4.4.0.1.1 A. Quan hệ thứ tự (Order relation)

Quan hệ thứ tự giữa các nút giới thiệu một cấu trúc tuần tự, cần thiết cho các ngữ cảnh mà chuỗi các phần tử mang ý nghĩa quan trọng (ví dụ: các từ trong câu). Quan hệ thứ tự đặc biệt phù hợp trong các tác vụ NLP, trong đó thứ tự xuất hiện của các từ ảnh hưởng đến ý nghĩa của câu.

Định nghĩa: Quan hệ thứ tự ngụ ý rằng có một thứ tự ưu tiên được xác định giữa các nút, trong đó$v_i$đứng trước $v_j$ (ví dụ: $v_i \rightarrow v_j$ biểu thị rằng $v_i$ đứng trước $v_j$).
Ví dụ trong NLP: Trong đồ thị câu, trong đó mỗi từ hoặc mã thông báo là một nút, quan hệ thứ tự sẽ phản ánh trình tự từ tự nhiên. Ví dụ: trong “Con mèo ngồi”, “Con” sẽ được sắp xếp trước “mèo” và “mèo” trước “ngồi”.

4.4.0.1.2 B. Quan hệ vị trí (Positional relation)

Quan hệ vị trí biểu thị vị trí của nút trong một cấu trúc rộng hơn, độc lập với thứ tự tuần tự của nó. Khái niệm này phổ biến trong các cấu trúc giống như lưới (ví dụ: hình ảnh 2D) và ngày càng được sử dụng trong NLP để nắm bắt ngữ cảnh dựa trên vị trí từ hoặc khoảng cách từ một điểm tiêu cự.

Định nghĩa: Quan hệ vị trí chỉ định vị trí của nút so với các nút khác, thường dựa trên vị trí không gian hoặc cú pháp. Không giống như quan hệ thứ tự, quan hệ vị trí không ngụ ý hướng mà là ngữ cảnh không gian.
Ví dụ trong NLP: Trong các mô hình dựa trên biến đổi như BERT, mã hóa vị trí được thêm vào mỗi nhúng mã thông báo để kết hợp thông tin vị trí, cho phép mô hình phân biệt giữa các mã thông báo giống hệt nhau dựa trên vị trí của chúng trong câu.

4.4.0.2 2. Quan hệ thứ tự và vị trí ảnh hưởng đến mã hóa như thế nào

Quan hệ thứ tự và vị trí ảnh hưởng đáng kể đến mã hóa nút $\mathsf{ENC}(v)$ theo những cách sau:

4.4.0.2.1 A. Tác động của quan hệ thứ tự đối với mã hóa

Khi mã hóa các nút có quan hệ thứ tự, các mô hình phải tôn trọng thông tin chuỗi, đảm bảo rằng mã hóa của mỗi nút kết hợp thông tin về vị trí của nó trong chuỗi.

Tổng hợp tuần tự: Trong Mạng nơ-ron đồ thị (GNN), thứ tự có thể quyết định chuỗi truyền tin. Ví dụ: trong GNN hồi quy hoặc Mạng hồi quy đồ thị (GRN), các nút truyền tin nhắn đến các nút kế nhiệm của chúng theo một thứ tự cụ thể, bảo toàn cấu trúc chuỗi ban đầu.
Mã hóa thời gian hoặc hướng: Trong đồ thị có hướng với quan hệ thứ tự, nhúng nút có thể nhấn mạnh các phụ thuộc, cho phép các mô hình tiếp theo hiểu các phụ thuộc dựa trên thời gian hoặc tuần tự. Ví dụ: - Trong NLP, chuỗi có thứ tự giúp các mô hình hiểu cú pháp, trong đó các mẫu nhất định như “danh từ theo sau là động từ” mang ý nghĩa quan trọng. Mã hóa nắm bắt thứ tự này có thể biểu diễn tốt hơn các phụ thuộc ngôn ngữ.
Ứng dụng: Quan hệ thứ tự rất quan trọng trong các tác vụ như dự đoán chuỗi, mô hình hóa ngôn ngữ và dịch máy. Ví dụ: trong tác vụ dịch máy, việc nắm bắt thứ tự của các từ trong câu nguồn là rất quan trọng để tạo ra các bản dịch chính xác về mặt ngữ pháp và ngữ nghĩa.

4.4.0.2.2 B. Tác động của quan hệ vị trí đối với mã hóa

Quan hệ vị trí thường nhấn mạnh ngữ cảnh không gian hoặc vị trí tương đối hơn là trình tự nghiêm ngặt. Điều này có thể rất quan trọng trong các tác vụ mà việc hiểu khoảng cách tương đối hoặc vị trí là quan trọng.

Nhúng thông tin vị trí: Trong biến đổi, mỗi mã thông báo được gán một nhúng vị trí được thêm vào nhúng ngữ nghĩa của nó, mã hóa vị trí của nó trong câu. Điều này giúp duy trì sự sắp xếp không gian mà không cần dựa vào một thứ tự nghiêm ngặt.
Tổng hợp dựa trên sự chú ý: Quan hệ vị trí cũng được mã hóa bằng cách sử dụng cơ chế chú ý, đặc biệt là trong các mô hình biến đổi. Ở đây, các lớp tự chú ý sử dụng mã hóa vị trí để xác định tầm quan trọng của mỗi mã thông báo so với các mã thông báo khác, cho phép mô hình nắm bắt các phụ thuộc tầm xa.
Ứng dụng: Quan hệ vị trí có lợi cho các tác vụ mà độ dài ngữ cảnh thay đổi (ví dụ: phân loại tài liệu hoặc trả lời câu hỏi), vì chúng cho phép mô hình giữ lại ngữ cảnh dựa trên sự gần gũi hơn là thứ tự cố định. Ví dụ: trong trả lời câu hỏi, việc biết vị trí của câu hỏi so với câu trả lời tiềm năng trong văn bản có thể cải thiện độ chính xác.

4.4.0.3 3. Ý nghĩa của quan hệ thứ tự và vị trí đối với học tập dựa trên đồ thị

4.4.0.3.1 A. Ảnh hưởng đến độ phức tạp và khả năng diễn giải của mô hình

Quan hệ thứ tự và vị trí thường làm tăng độ phức tạp của mô hình nhưng cũng có thể tăng cường khả năng diễn giải:

Độ phức tạp: Mã hóa thứ tự và vị trí yêu cầu các tham số bổ sung, như đã thấy với mã hóa vị trí trong biến đổi hoặc các cạnh có hướng trong GNN dựa trên RNN. Điều này làm tăng độ phức tạp của mô hình nhưng có thể dẫn đến hiệu suất tốt hơn trên các tác vụ yêu cầu nhận thức về chuỗi hoặc vị trí.
Khả năng diễn giải: Quan hệ vị trí và thứ tự làm cho quá trình ra quyết định của mô hình dễ hiểu hơn, đặc biệt là trong NLP. Ví dụ: trong phân tích cú pháp phụ thuộc, mã hóa tôn trọng thứ tự có thể giúp xác định cấu trúc cú pháp rõ ràng hơn, hỗ trợ khả năng diễn giải.

4.4.0.3.2 B. Tăng tính biểu cảm trong mã hóa

Các đồ thị nắm bắt quan hệ thứ tự và vị trí thường biểu cảm hơn và có khả năng biểu diễn các phụ thuộc phức tạp:

Phụ thuộc tầm xa(Long-Range Dependencies): Quan hệ thứ tự trong các mô hình tuần tự nắm bắt phụ thuộc tầm xa, cho phép các nút cách xa nhau trong một chuỗi ảnh hưởng lẫn nhau trong mã hóa. Ví dụ: trong phân tích tình cảm, các từ ở xa nhau trong câu có thể sửa đổi ý nghĩa của nhau, điều mà mã hóa có thứ tự có thể nắm bắt được.
Mối quan hệ ngữ cảnh: Mã hóa vị trí cho phép các mô hình kết hợp ngữ cảnh rộng hơn mà không cần kết nối rõ ràng, điều cần thiết trong các tài liệu lớn hoặc các cuộc trò chuyện dài, nơi ngữ cảnh cục bộ cần được bảo toàn trong một cấu trúc lớn hơn.

4.4.0.3.3 C. Thích ứng thuật toán học tập

Các thuật toán phải thích ứng để xử lý các yêu cầu cụ thể do quan hệ thứ tự và vị trí đưa ra. Ví dụ:

Lan truyền ngược tuần tự: Trong các mô hình có quan hệ thứ tự (ví dụ: GNN dựa trên RNN), lan truyền ngược xảy ra tuần tự để tôn trọng các phụ thuộc có thứ tự, yêu cầu mô hình tính toán gradient từng bước.
Trọng số vị trí trong cơ chế chú ý: Trong các mô hình như biến đổi, các lớp tự chú ý được sửa đổi để bao gồm mã hóa vị trí, cho phép các nút được tính trọng số dựa trên vị trí của chúng trong đầu vào thay vì độ kề của chúng trong đồ thị.

4.4.0.4 4. Thách thức và hạn chế

Mặc dù quan hệ thứ tự và vị trí làm phong phú thêm mã hóa, chúng cũng đưa ra những thách thức:

Khả năng mở rộng: Mã hóa cả quan hệ thứ tự và vị trí làm tăng số chiều và yêu cầu tính toán, có thể dẫn đến sự kém hiệu quả trong đồ thị quy mô lớn hoặc các tác vụ NLP với chuỗi dài.
Rủi ro Overfitting: Với thông tin vị trí và thứ tự, mô hình có thể quá khớp với các mẫu cụ thể, đặc biệt nếu dữ liệu huấn luyện lặp lại hoặc sai lệch. Điều này có thể cản trở khả năng khái quát hóa, đặc biệt là trên các chuỗi chưa nhìn thấy hoặc cấu trúc đồ thị mới.
Độ phức tạp trong mã hóa thông tin thời gian: Đối với các tác vụ liên quan đến thứ tự thời gian (ví dụ: dự đoán sự kiện), việc nắm bắt thời gian của các sự kiện yêu cầu điều chỉnh bổ sung cho nhúng, làm cho mã hóa cả thứ tự và vị trí trở nên phức tạp hơn.

4.4.0.5 Tóm tắt

Quan hệ thứ tự thêm một phụ thuộc có hướng hoặc tuần tự, cho phép mô hình mã hóa và tôn trọng luồng thông tin tự nhiên. Chúng rất quan trọng trong các tác vụ như mô hình hóa ngôn ngữ, phân tích tình cảm và dự đoán chuỗi, trong đó thứ tự từ ảnh hưởng đến ý nghĩa.
Quan hệ vị trí cung cấp thông tin không gian hoặc ngữ cảnh, thường hữu ích trong các tác vụ phi tuần tự hoặc nơi định vị tương đối là điều cần thiết để nắm bắt ngữ cảnh. Chúng được sử dụng nhiều trong các mô hình NLP dựa trên biến đổi, trong đó mã hóa vị trí giúp duy trì mức độ liên quan theo ngữ cảnh của các từ mà không cần phụ thuộc nghiêm ngặt vào thứ tự.
Tác động đến mã hóa: Cả hai quan hệ đều ảnh hưởng đến cách nhúng được tổng hợp, số chiều của chúng và độ phức tạp của các tác vụ tiếp theo. Các mô hình tính đến các quan hệ này có xu hướng biểu cảm hơn và có khả năng nắm bắt các phụ thuộc tinh tế.

Các quan hệ này, khi được mã hóa chính xác, có thể cải thiện đáng kể khả năng hiểu cấu trúc dữ liệu của mô hình, làm cho nó mạnh mẽ hơn, nhận biết ngữ cảnh hơn và phù hợp để nắm bắt các thuộc tính độc đáo của đồ thị, đặc biệt là trong các tác vụ NLP phức tạp.

4.5 VI. Đánh giá mô hình đồ thị dựa trên nguyên tắc truyền tin

Để phân tích các mô hình dựa trên đồ thị, đặc biệt là Mạng nơ-ron đồ thị (GNN), chúng ta có thể đánh giá hiệu suất bằng cách kiểm tra các thành phần chính ảnh hưởng trực tiếp đến cách thông tin được xử lý và học trong mô hình. Chúng ta hãy thảo luận về từng khía cạnh của việc đánh giá:

4.5.0.1 1. Sử dụng nguyên tắc truyền tin trong GNN

Truyền tin là một phép toán cơ bản trong GNN cho phép mỗi nút tổng hợp thông tin từ các nút lân cận của nó một cách lặp đi lặp lại. Quá trình lặp đi lặp lại này cho phép các nút thu thập ngữ cảnh từ vùng lân cận cục bộ của chúng và cuối cùng nắm bắt các phụ thuộc bậc cao hơn trong cấu trúc đồ thị. Việc đánh giá một mô hình bằng cách sử dụng nguyên tắc truyền tin bao gồm ba câu hỏi chính:

4.5.0.1.1 1.1 Độ sâu của vùng lân cận xung quanh $v \in V$ là bao nhiêu?

Độ sâu của vùng lân cận đề cập đến phạm vi tiếp nhận của một nút - về cơ bản, có bao nhiêu “bước nhảy” của các nút lân cận đóng góp thông tin cho biểu diễn cuối cùng của nút.

Định nghĩa: Trong GNN, độ sâu $K$ biểu thị số lớp hoặc số lần lặp của truyền tin, trong đó mỗi lớp tổng hợp thông tin từ các nút lân cận ở khoảng cách tương ứng. Ví dụ: - $K = 1$ nắm bắt thông tin từ các nút lân cận trực tiếp. - $K = 2$ nắm bắt thông tin từ các nút lân cận cách xa tối đa hai bước nhảy, kết hợp cả các nút lân cận trực tiếp và các nút lân cận của chúng.
Tác động đến mã hóa: - Vùng lân cận nông ( $K$ nhỏ): Nếu độ sâu bị giới hạn trong 1 hoặc 2 bước nhảy, mã hóa nút chủ yếu phản ánh thông tin cục bộ và tốt nhất để nắm bắt cấu trúc vi mô như cụm, cạnh hoặc mô-típ gần nút. - Vùng lân cận sâu ( $K$ lớn ): Độ sâu lớn hơn nắm bắt các cấu trúc toàn cục rộng hơn, hữu ích cho các tác vụ mà các phụ thuộc tầm xa quan trọng, chẳng hạn như phát hiện cộng đồng hoặc phân loại phân cấp. - Đánh đổi: Tăng độ sâu có thể dẫn đến vấn đề làm mịn quá mức - khi $K$ tăng, các nút có xu hướng có biểu diễn tương tự nhau, đặc biệt là trong đồ thị dày đặc, điều này có thể làm giảm khả năng phân biệt các nút ở các phần khác nhau của đồ thị của mô hình.
Cân nhắc đánh giá: Độ sâu được chọn phải phù hợp với yêu cầu nhiệm vụ: - Đối với các tác vụ cục bộ như dự đoán liên kết, vùng lân cận nông (ví dụ: $K = 1$ hoặc $2$ ) thường là đủ. - Đối với các tác vụ toàn cục, chẳng hạn như phân loại nút trên đồ thị có cấu trúc phân cấp, các lớp sâu hơn có thể cần thiết, nhưng chỉ khi chúng tránh được làm mịn quá mức.

4.5.0.1.2 1.2 Bối cảnh của người nhận dữ liệu là gì?

Bối cảnh(landscape) của người nhận dữ liệu đề cập đến ngữ cảnh dựa trên cấu trúc và thuộc tính mà một nút hoặc đồ thị con nhận được thông tin trong quá trình truyền tin. Bối cảnh này bị ảnh hưởng bởi cả tôpô đồ thị và thuộc tính nút.

Tôpô đồ thị: - Cấu trúc xung quanh mỗi nút - chẳng hạn như nó nằm trong một cụm dày đặc hay trên một vùng ngoại vi thưa thớt - ảnh hưởng đến lượng thông tin mà nó nhận được từ các nút lân cận của nó. - Ví dụ: các nút trong các cụm được kết nối dày đặc nhận được một lượng lớn thông tin cục bộ, trong khi các nút ngoại vi có thể có tương tác hạn chế.
Thuộc tính nút và cạnh: - Các nút thường đi kèm với các đặc trưng, có thể bao gồm các đặc trưng số đơn giản, các danh mục được mã hóa một nóng hoặc các vectơ phức tạp hơn (như nhúng trong NLP). - Các thuộc tính cạnh cũng có thể xác định bản chất của các kết nối giữa các nút (ví dụ: trọng số hoặc loại quan hệ), tác động đến cách tin nhắn được truyền và tổng hợp.
Mã hóa vị trí hoặc không gian: - Đối với đồ thị có cấu trúc không gian hoặc phân cấp tự nhiên, mã hóa vị trí (như trong biến đổi) có thể làm phong phú thêm bối cảnh nút bằng cách mã hóa các vị trí tương đối trong đồ thị.
Cân nhắc đánh giá: Hiểu bối cảnh bao gồm kiểm tra cách cấu trúc và các đặc trưng kết hợp để định hình trường tiếp nhận của nút: - Vùng dày đặc so với vùng thưa thớt: Các nút trong vùng dày đặc hơn có thể hưởng lợi nhiều hơn từ truyền tin, vì chúng nhận được ngữ cảnh phong phú hơn, trong khi các nút trong vùng thưa thớt có thể yêu cầu mã hóa vị trí hoặc cấu trúc bổ sung để bù đắp. - Độ biến thiên đặc trưng: Độ biến thiên lớn hơn trong các đặc trưng nút hoặc cạnh có thể cải thiện sự đa dạng của thông tin được trao đổi, điều này có thể có lợi cho các tác vụ dựa vào việc phân biệt các nút dựa trên thông tin dựa trên đặc trưng hoặc dựa trên thuộc tính.

4.5.0.1.3 1.3 Phương pháp tổng hợp được sử dụng là gì?

Phương pháp tổng hợp trong truyền tin là hàm được sử dụng để kết hợp thông tin từ các nút lân cận. Các phương pháp tổng hợp khác nhau có thể ảnh hưởng đáng kể đến chất lượng và loại thông tin mà một nút cuối cùng mã hóa.

Các phương pháp tổng hợp phổ biến bao gồm:

Tổng hợp trung bình: - Tính trung bình các đặc trưng của các nút lân cận. - Ưu điểm: Đơn giản và hiệu quả về mặt tính toán, nắm bắt xu hướng trung bình trong vùng lân cận. - Nhược điểm: Có thể bỏ lỡ các biến thể quan trọng trong vùng lân cận, vì nó chỉ tóm tắt giá trị trung bình.
Tổng hợp tổng: - Cộng các đặc trưng từ các nút lân cận. - Ưu điểm: Bảo toàn tổng lượng thông tin đặc trưng, hữu ích cho các tác vụ dựa trên đếm hoặc tích lũy. - Nhược điểm: Có thể dẫn đến độ lớn đặc trưng lớn hơn, có thể yêu cầu chuẩn hóa.
Gộp tối đa: - Lấy giá trị tối đa trên các đặc trưng từ các nút lân cận. - Ưu điểm: Làm nổi bật các tín hiệu mạnh nhất trong vùng lân cận, thường tăng cường các đặc trưng quan trọng hoặc chiếm ưu thế. - Nhược điểm: Mất thông tin về các nút lân cận khác, có khả năng bỏ qua cấu trúc tổng thể của vùng lân cận.
Cơ chế chú ý (được sử dụng trong Mạng chú ý đồ thị (GAT)): - Gán trọng số cho mỗi nút lân cận dựa trên mức độ liên quan của nó, cho phép nút chọn lọc chú ý đến các nút lân cận cụ thể. - Ưu điểm: Thích ứng và nhạy cảm với ngữ cảnh, vì mô hình học được nút lân cận nào phù hợp nhất. - Nhược điểm: Phức tạp hơn về mặt tính toán và có khả năng yêu cầu tập dữ liệu lớn hơn để học điểm chú ý có ý nghĩa.
Tổng hợp dựa trên LSTM hoặc GRU: - Bộ tổng hợp tuần tự như LSTM có thể được sử dụng trong đồ thị có thứ tự để nắm bắt các phụ thuộc tuần tự trong vùng lân cận. - Ưu điểm: Hiệu quả đối với đồ thị có thứ tự hoặc phụ thuộc tự nhiên. - Nhược điểm: Tốn nhiều tài nguyên tính toán và có thể gây ra sai lệch thứ tự.

4.5.0.2 Tóm tắt các nguyên tắc đánh giá bằng cách sử dụng nguyên tắc truyền tin

Để đánh giá GNN dựa trên truyền tin, các câu hỏi sau đây cung cấp một cách tiếp cận có cấu trúc:

Độ sâu của vùng lân cận: Xác định có bao nhiêu bước nhảy hoặc lớp là cần thiết để nắm bắt thông tin có ý nghĩa cho nhiệm vụ. - Chọn độ sâu nắm bắt cấu trúc liên quan mà không làm mịn quá mức. - Kiểm tra các độ sâu khác nhau trong quá trình thử nghiệm để tìm sự cân bằng tối ưu.
Bối cảnh của người nhận dữ liệu: Kiểm tra ngữ cảnh dựa trên cấu trúc và đặc trưng của mỗi nút, cụ thể là: - Các nút được kết nối dày đặc có thể hưởng lợi từ truyền tin trực tiếp hơn, trong khi các nút thưa thớt hoặc ngoại vi có thể cần mã hóa vị trí hoặc cấu trúc nâng cao. - Các nút có thông tin thuộc tính phong phú hoặc trọng số cạnh có ý nghĩa có thể cung cấp bối cảnh tinh tế hơn để tổng hợp.
Phương pháp tổng hợp: Chọn phương pháp tổng hợp phù hợp với nhiệm vụ và cấu trúc đồ thị. - Tổng hợp trung bình và tổng thường phù hợp với các tác vụ hoặc đồ thị đơn giản hơn với các vùng lân cận đồng nhất. - Gộp tối đa(Max pooling) và cơ chế chú ý(attention mechanisms) tốt hơn cho đồ thị phức tạp hoặc không đồng nhất, trong đó các nút hoặc cạnh nhất định có thể có ý nghĩa quan trọng hơn các nút hoặc cạnh khác.

Việc đánh giá các khía cạnh này trong quá trình huấn luyện và thử nghiệm mô hình giúp tinh chỉnh kiến trúc của GNN để tối đa hóa hiệu suất trên các tác vụ cụ thể, chẳng hạn như phân loại nút, dự đoán liên kết hoặc phân loại đồ thị. Bằng cách điều chỉnh cẩn thận độ sâu vùng lân cận, xem xét bối cảnh và phương pháp tổng hợp, mô hình có thể được tối ưu hóa để truyền tin hiệu quả và dễ hiểu, cuối cùng dẫn đến biểu diễn đồ thị mạnh mẽ hơn.

4.6 VII. Khả năng diễn giải và tính tương thích của lớp MLP trong cấu trúc GNN

Khả năng diễn giải của lớp MLP (Perceptron nhiều lớp) trong cấu trúc GNN, cũng như tính tương thích giữa các thành phần GNN và MLP, là những yếu tố quan trọng để hiểu và phân tích mức độ mô hình nắm bắt và sử dụng thông tin dựa trên đồ thị cho các tác vụ tiếp theo. Chúng ta hãy xem xét kỹ từng thành phần này:

4.6.0.1 1. Khả năng diễn giải của lớp MLP sau cấu trúc GNN

Khi GNN đưa đầu ra của nó vào lớp MLP, khả năng diễn giải của lớp cuối cùng này phụ thuộc vào mức độ MLP có thể xử lý nhúng nút do GNN tạo ra. Dưới đây là một số điểm chính cần xem xét:

4.6.0.1.1 A. Vai trò của MLP trong cấu trúc GNN

Lớp MLP thường đóng vai trò là bộ phân loại cuối cùng hoặc bộ hồi quy trong kiến trúc GNN. Các chức năng chính của nó bao gồm: - Tổng hợp các đặc trưng được học thông qua nhiều lớp truyền tin GNN. - Biến đổi nhúng do GNN tạo ra thành định dạng đầu ra mong muốn cho các tác vụ cụ thể, chẳng hạn như phân loại nút, dự đoán liên kết hoặc dự đoán cấp độ đồ thị.

Trong vai trò này, MLP: - Xử lý các nhúng phong phú do GNN tạo ra, kết hợp cả thông tin cấu trúc đồ thị cục bộ và toàn cục, thuộc tính nút và các mối quan hệ phức tạp, nhiều bước nhảy tiềm năng. - Áp dụng các phép biến đổi phi tuyến có thể tinh chỉnh hoặc lọc nhúng đồ thị, cung cấp thêm một mức độ trừu tượng hoặc ra quyết định.

4.6.0.1.2 B. Khả năng diễn giải của lớp MLP

Khả năng diễn giải của lớp MLP trong GNN phụ thuộc vào nhiệm vụ, cũng như cách chúng ta diễn giải ranh giới quyết định cuối cùng hoặc đầu ra mà nó tạo ra: - Trích xuất đặc trưng: Vì MLP đang học trực tiếp từ các nhúng được GNN xử lý, nên nó có thể được xem như là lớp trích xuất đặc trưng cuối cùng. Mỗi đơn vị ẩn trong MLP nắm bắt một tổ hợp khác nhau của các đặc trưng được GNN học, giúp có thể phân tích cách các đặc trưng riêng lẻ hoặc nhóm đặc trưng ảnh hưởng đến dự đoán cuối cùng. - Ranh giới quyết định: Trong các tác vụ phân loại, lớp MLP tạo ra ranh giới quyết định phi tuyến trên không gian nhúng do GNN tạo ra. Điều này cung cấp thông tin chi tiết về mẫu cấu trúc hoặc đặc trưng nào (được GNN học) mang tính quyết định hơn cho việc phân loại cuối cùng. Ví dụ: hình dung các ranh giới quyết định này hoặc kiểm tra cách các lớp cụ thể phân cụm trong không gian nhúng có thể cung cấp khả năng diễn giải về cách các mối quan hệ dựa trên đồ thị ảnh hưởng đến dự đoán.

Phân bổ và tầm quan trọng của đặc trưng: Các phương pháp như Lan truyền mức độ liên quan theo lớp (LRP) hoặc SHAP (SHapley Additive exPlanations) có thể được áp dụng để phân tích đặc trưng nút hoặc cạnh nào từ đồ thị ban đầu có ảnh hưởng nhất trong việc xác định đầu ra của MLP. Các phương pháp này có thể phân bổ tầm quan trọng cho các đặc trưng đồ thị cụ thể, hỗ trợ khả năng diễn giải vai trò của lớp MLP.

4.6.0.1.3 C. Ví dụ thực tế về khả năng diễn giải của MLP

Trong tác vụ phân loại nút, GNN có thể mã hóa mỗi nút bằng một vectơ nắm bắt cấu trúc vùng lân cận và thuộc tính đặc trưng. Khi mã hóa này được đưa vào MLP: - MLP gán trọng số khác nhau cho mỗi đặc trưng, tiết lộ khía cạnh nào của vùng lân cận của nút phù hợp nhất để phân loại. - Ví dụ: trong mạng trích dẫn, MLP có thể nhấn mạnh các đặc trưng nhất định (như “được kết nối với các bài báo được trích dẫn nhiều”) là chỉ báo mạnh mẽ về lớp của nút.

4.6.0.2 2. Tính tương thích giữa các lớp GNN và MLP

Tính tương thích giữa các cấu trúc GNN và MLP là rất quan trọng để học tập hiệu quả và phụ thuộc vào mức độ MLP có thể tận dụng nhúng đồ thị do GNN tạo ra. Các yếu tố tương thích bao gồm:

4.6.0.2.1 A. Tính tương thích đặc trưng

Tính tương thích của hai thành phần bị ảnh hưởng rất nhiều bởi mức độ nhúng của GNN phù hợp với yêu cầu của MLP để đưa ra dự đoán chính xác. Các yếu tố bao gồm:

Khớp số chiều: Số chiều đầu ra của GNN phải tương thích với yêu cầu đầu vào của MLP. Nếu GNN tạo ra nhúng có số chiều$d$, thì MLP phải có khả năng xử lý các vectơ đầu vào của số chiều này mà không cần đệm hoặc cắt bớt quá mức.
Tính biểu cảm: GNN thường tạo ra các nhúng thông tin có số chiều cao, nắm bắt thông tin cấu trúc và thuộc tính tinh tế. MLP phải có khả năng trích xuất các mẫu có liên quan từ các nhúng này; nếu không, lợi ích của sức mạnh biểu đạt của GNN sẽ bị mất. Lớp MLP được thiết kế tốt với chiều rộng và độ sâu đủ có thể học các ánh xạ phức tạp từ các nhúng này sang các lớp đầu ra, nhãn hoặc dự đoán.

4.6.0.2.2 B. Luồng thông tin và tính đầy đủ

Để có tính tương thích tối ưu, luồng thông tin giữa GNN và MLP phải đầy đủ - nghĩa là GNN lý tưởng nhất nên chuyển tất cả thông tin cần thiết đến MLP cho tác vụ tiếp theo.

Tính đầy đủ của nhúng GNN: Nhúng của GNN cần nắm bắt tất cả thông tin có liên quan (đặc trưng nút, mối quan hệ cấu trúc, thuộc tính cạnh) cần thiết cho tác vụ của MLP. Nếu thiếu các mối quan hệ quan trọng, MLP có thể không có đủ thông tin để đưa ra dự đoán chính xác.
Dư thừa và quá khớp (Overfitting): Nhúng có số chiều cao cũng có thể gây ra dư thừa, đặc biệt nếu GNN sâu hoặc nắm bắt các đặc trưng quá chi tiết. MLP được điều chỉnh tốt có thể quản lý dư thừa bằng cách chọn lọc các đặc trưng trọng số, nhưng cấu hình kém có thể dẫn đến quá khớp (overfitting).

4.6.0.2.3 C. Tính tương thích thực nghiệm: Hiệp lực hiệu suất GNN + MLP

Theo kinh nghiệm, tính tương thích giữa các lớp GNN và MLP được đánh giá dựa trên mức độ chúng hoạt động cùng nhau để cải thiện các số liệu cụ thể cho tác vụ (ví dụ: độ chính xác, điểm F1 hoặc sai số bình phương trung bình).

Đánh giá thực nghiệm: Các thí nghiệm thường chỉ ra rằng việc kết hợp GNN với MLP đạt được hiệu suất vượt trội trên các tác vụ phức tạp, chẳng hạn như phân loại nút và dự đoán cấp độ đồ thị. Điều này là do MLP tinh chỉnh các biểu diễn có cấu trúc do GNN tạo ra, cho phép mô hình tận dụng cả mẫu đồ thị cục bộ và toàn cục.
Nghiên cứu cắt bỏ: Nhiều nghiên cứu đánh giá tính tương thích của tổ hợp GNN-MLP bằng cách loại bỏ MLP hoặc sửa đổi GNN và quan sát những thay đổi về hiệu suất. Việc loại bỏ MLP thường dẫn đến giảm độ chính xác trong các tác vụ tiếp theo, vì MLP đóng một vai trò quan trọng trong việc biến đổi nhúng GNN thành đầu ra cụ thể cho tác vụ. ##### D. Ví dụ thực tế về tính tương thích Hãy xem xét mạng xã hội nơi chúng tôi muốn dự đoán sở thích của người dùng dựa trên các kết nối và thuộc tính hồ sơ:
GNN xử lý cấu trúc mạng, mã hóa từng người dùng dựa trên các kết nối và thuộc tính của những người hàng xóm.
Sau đó, MLP lấy các nhúng này và xác định ranh giới quyết định tốt nhất để phân loại sở thích của từng người dùng. Tính tương thích giữa GNN và MLP phụ thuộc vào khả năng của MLP trong việc tận dụng nhúng GNN để hình thành các cụm hoặc ranh giới riêng biệt cho các nhóm sở thích khác nhau.

Trong trường hợp này: - Nếu nhúng GNN rõ ràng và khác biệt, MLP có thể phân loại sở thích một cách hiệu quả. - Nếu các nhúng quá giống nhau hoặc thiếu thông tin cần thiết, MLP có thể gặp khó khăn, cho thấy khả năng tương thích kém.

4.6.0.3 Tóm tắt

Khả năng diễn giải của lớp MLP: MLP thêm một lớp tổng hợp đặc trưng và ra quyết định có thể diễn giải, tinh chỉnh các nhúng do GNN tạo ra. Nó cho phép chúng tôi hiểu cách các đặc trưng cụ thể hoặc tổ hợp các đặc trưng đóng góp vào dự đoán cuối cùng.
Tính tương thích giữa GNN và MLP: - Tính tương thích đặc trưng: Đảm bảo rằng MLP có thể xử lý hiệu quả số chiều và độ phức tạp của nhúng GNN. - Luồng thông tin và tính đầy đủ: Đảm bảo rằng nhúng GNN nắm bắt đủ thông tin để MLP đưa ra dự đoán chính xác. - Tính tương thích thực nghiệm: Được chứng minh thông qua kết quả thực nghiệm cho thấy hiệu suất tăng khi sử dụng GNN + MLP, thường được kiểm tra bằng các nghiên cứu cắt bỏ.

Sự kết hợp GNN-MLP thường tương thích với các tác vụ dựa trên đồ thị, vì GNN cung cấp nhúng có cấu trúc, quan hệ và MLP chuyển đổi chúng thành đầu ra cụ thể cho tác vụ. Hiệu quả của sự kết hợp này thường được xác nhận bằng thực nghiệm, làm cho nó trở thành lựa chọn phổ biến trong các ứng dụng học máy đồ thị.

4.7 VIII. Hàm mất mát và hàm rủi ro trong kiến trúc GNN+MLP

Hàm mất mát (loss function) được sử dụng trong kiến trúc GNN+MLP thường phụ thuộc vào loại nhiệm vụ (ví dụ: phân loại, hồi quy hoặc dự đoán liên kết) và đóng một vai trò quan trọng trong việc tối ưu hóa mô hình trong quá trình huấn luyện. Ngoài hàm mất mát, hàm rủi ro (risk function) (thường được xem là giá trị kỳ vọng của mất mát trên tập dữ liệu) được sử dụng để đo lường khả năng khái quát hóa của mô hình trên dữ liệu chưa nhìn thấy. Chúng ta hãy đi sâu vào các hàm này, cách chúng hoạt động và các yếu tố ảnh hưởng đến chúng trong quá trình huấn luyện.

4.7.0.1 1. Các loại hàm mất mát và vai trò của chúng

Hàm mất mát là số liệu đánh giá mức độ dự đoán của mô hình phù hợp với nhãn hoặc giá trị thực, hướng dẫn quá trình học bằng cách cung cấp thước đo định lượng về lỗi.

4.7.0.1.1 Các hàm mất mát phổ biến cho kiến trúc GNN+MLP

Mất mát chéo entropy (Cross-Entropy Loss) (cho các tác vụ phân loại): - Định nghĩa: Mất mát chéo entropy thường được sử dụng khi mô hình đang thực hiện tác vụ phân loại (ví dụ: phân loại nút). Nó đo lường sự phân kỳ giữa phân phối xác suất dự đoán (đầu ra của lớp softmax MLP) và phân phối nhãn thực. - Công thức: \[\text{Loss}_{\text{cross-entropy}}=-\sum_{i=1}^C y_i \log(\hat{y}_i)\] trong đó $C$ là số lớp, $y_i$ là nhãn thực (thường được mã hóa một nóng) và $\hat{y}_i$ là xác suất dự đoán cho lớp $i$. - Mục đích: Mất mát chéo entropy khuyến khích mô hình tối đa hóa xác suất của lớp chính xác, giảm thiểu sự khác biệt giữa các lớp dự đoán và thực tế. Điều này được sử dụng rộng rãi trong các tác vụ phân loại nút và phân loại cấp độ đồ thị.
Mất mát sai số bình phương trung bình (MSE - Mean Squared Error Loss) (cho các tác vụ hồi quy): - Định nghĩa: LOSS MSE được sử dụng khi mô hình thực hiện tác vụ hồi quy (ví dụ: dự đoán giá trị liên tục cho mỗi nút hoặc cạnh). Nó tính toán chênh lệch bình phương trung bình giữa các giá trị dự đoán và thực tế. - Công thức: \[\text{Loss}_{\text{MSE}} = \frac{1}{N} \sum_{i=1}^N (\hat{y}_i - y_i)^2\] trong đó $N$ là số lượng mẫu, $\hat{y}_i$ là giá trị dự đoán và$y_i$ là giá trị thực. - Mục đích: MSE xử phạt các lỗi lớn hơn nhiều hơn các lỗi nhỏ hơn, điều này có thể giúp mô hình học cách giảm thiểu các sai lệch đáng kể. Nó thường được sử dụng cho các tác vụ hồi quy nút, chẳng hạn như dự đoán các thuộc tính liên tục.
Mất mát chéo entropy nhị phân (Binary Cross-Entropy Loss) (cho các tác vụ phân loại nhị phân hoặc dự đoán liên kết): - Định nghĩa: Chéo entropy nhị phân được sử dụng để phân loại nhị phân, trong đó mỗi đầu ra được phân loại độc lập thành một trong hai lớp. Nó thường được áp dụng trong các tác vụ dự đoán liên kết, trong đó mục tiêu là xác định sự hiện diện hoặc vắng mặt của một cạnh giữa hai nút. - Công thức: \[\text{Loss}_{\text{binary}} = - \left( y \log(\hat{y}) + (1 - y) \log(1 - \hat{y}) \right)\] trong đó $y$ là nhãn thực (0 hoặc 1) và $\hat{y}$ là xác suất dự đoán. - Mục đích: Chéo entropy nhị phân tối ưu hóa mô hình để dự đoán khả năng xảy ra mối quan hệ tích cực hoặc tiêu cực trong dự đoán liên kết và các tác vụ nhị phân khác.
Mất mát tương phản (Contrastive Loss) (cho các tác vụ nhúng và dựa trên sự giống nhau): - Định nghĩa: Mất mát tương phản được sử dụng khi mục tiêu là học các biểu diễn đưa các cặp nút tương tự lại gần nhau trong không gian nhúng đồng thời đẩy các cặp không giống nhau ra xa nhau. - Công thức: \[\text{Loss}_{\text{contrastive}} = \frac{1}{N} \sum_{i,j} y_{ij} d(\mathbf{z}_i, \mathbf{z}_j)^2 + (1 - y_{ij}) \max(0, m - d(\mathbf{z}_i, \mathbf{z}_j))^2\] trong đó $y_{ij}$ là 1 nếu các nút$i$và$j$giống nhau và 0 nếu ngược lại, $d(\mathbf{z}_i, \mathbf{z}_j)$ là khoảng cách giữa các nhúng và $m$ là tham số lề. - Mục đích: Hàm mất mát này phổ biến trong học biểu diễn trên đồ thị, đặc biệt là trong các tác vụ học tập không giám sát, trong đó mục tiêu là nhúng các nút dựa trên sự giống nhau về cấu trúc.

4.7.0.2 2. Cách hàm mất mát lấy dữ liệu

Hàm mất mát lấy: - Đầu ra dự đoán: Đây là đầu ra của MLP, xử lý nhúng do GNN tạo ra. Đối với phân loại, đây là xác suất; đối với hồi quy, giá trị liên tục; đối với mất mát tương phản, khoảng cách trong không gian nhúng. - Nhãn hoặc giá trị thực: Đối với các tác vụ có giám sát, nhãn thực (ví dụ: nhãn lớp, mục tiêu hồi quy) được so sánh với dự đoán để tính toán mất mát. Mất mát được tính cho mỗi trường hợp (nút, cạnh hoặc đồ thị) và được tính trung bình trên tập dữ liệu hoặc lô nhỏ trong mỗi lần lặp huấn luyện, cung cấp giá trị mất mát vô hướng đóng vai trò là mục tiêu để tối ưu hóa dựa trên gradient.

4.7.0.3 3. Đánh giá hàm mất mát và hàm rủi ro trên mô hình

4.7.0.3.1 A. Hàm mất mát

Hàm mất mát đánh giá hiệu suất của mô hình trên lô dữ liệu hiện tại. Mất mát thấp cho biết dự đoán của mô hình khớp chặt chẽ với nhãn hoặc giá trị sự thật cơ bản, trong khi mất mát cao cho biết sự khác biệt đáng kể.

4.7.0.3.2 B. Hàm rủi ro (Khái quát hóa và mất mát dự kiến)

Hàm rủi ro biểu thị mất mát dự kiến trên toàn bộ phân phối dữ liệu, bao gồm cả các ví dụ chưa nhìn thấy. Trong khi hàm mất mát cung cấp ảnh chụp nhanh về hiệu suất mô hình trên lô hiện tại, thì hàm rủi ro đánh giá khả năng khái quát hóa của mô hình.

Giảm thiểu rủi ro: Mục tiêu của đào tạo là giảm thiểu hàm rủi ro, điều này ngụ ý đạt được lỗi thấp trên cả dữ liệu huấn luyện và dữ liệu kiểm tra chưa nhìn thấy.
Quá khớp (Overfitting) so với thiếu khớp (Underfitting): Giảm thiểu rủi ro bao gồm việc cân bằng giữa quá khớp (mất mát thấp khi huấn luyện nhưng cao trên dữ liệu kiểm tra) và thiếu khớp (mất mát cao trên cả dữ liệu huấn luyện và dữ liệu kiểm tra), thường được quản lý bằng cách điều chỉnh và điều chỉnh cẩn thận các tham số mô hình.

4.7.0.4 4. Các tham số và biến ảnh hưởng đến hàm mất mát trong quá trình huấn luyện

Một số tham số và biến chính ảnh hưởng đến hành vi của hàm mất mát và do đó, hiệu suất của mô hình trong quá trình huấn luyện:

4.7.0.4.1 A. Tham số mô hình

Tham số GNN: Trọng số của GNN, chiến lược tổng hợp và số lớp xác định chất lượng của nhúng nút được đưa vào MLP. - Số lượng lớp: Tăng số lượng lớp cho phép thông tin chạy từ các nút lân cận ở xa hơn nhưng có thể dẫn đến làm mịn quá mức nếu quá nhiều. - Hàm tổng hợp: Các phương pháp tổng hợp khác nhau (ví dụ: trung bình, tối đa, chú ý) ảnh hưởng đến cách kết hợp các đặc trưng nút, tác động đến độ phong phú và tính biểu cảm của nhúng.
Tham số MLP: Trọng số MLP xác định cách nhúng được biến đổi và phân loại hoặc hồi quy. - Độ sâu và chiều rộng: Số lượng lớp và số lượng nơ-ron trên mỗi lớp trong MLP ảnh hưởng đến khả năng nắm bắt các mối quan hệ phi tuyến của mô hình. - Hàm kích hoạt: Các hàm như ReLU, tanh hoặc softmax ảnh hưởng đến phép biến đổi phi tuyến của nhúng, tác động đến tính biểu cảm và hội tụ của mô hình.

4.7.0.4.2 B. Siêu tham số

Tốc độ học: Kiểm soát kích thước bước trong giảm dần gradient. Tốc độ học cao có thể dẫn đến dao động xung quanh mức tối thiểu, trong khi tốc độ thấp có thể dẫn đến hội tụ chậm.
Kích thước lô: Ảnh hưởng đến độ chi tiết của cập nhật gradient. Kích thước lô nhỏ hơn tạo ra nhiều nhiễu hơn trong các bản cập nhật, điều này có thể cải thiện khả năng khái quát hóa, trong khi các lô lớn hơn cung cấp các bản cập nhật ổn định hơn nhưng có thể dẫn đến quá khớp (overfitting).
Tham số điều chuẩn: - Dropout: Ngẫu nhiên loại bỏ các đơn vị trong GNN và MLP trong quá trình huấn luyện, giảm sự phụ thuộc vào các nút hoặc đường dẫn cụ thể và cải thiện khả năng khái quát hóa. - Suy giảm trọng số (Điều chuẩn L2): Thêm hình phạt vào độ lớn của trọng số, ngăn mô hình dựa quá nhiều vào các tham số cụ thể và khuyến khích các giải pháp đơn giản hơn.

4.7.0.4.3 C. Biến cấu trúc và đầu vào

Độ thưa thớt của đồ thị(Graph Sparsity): Đồ thị thưa thớt (với bậc nút trung bình thấp) có thể hạn chế lượng thông tin có sẵn cho mỗi nút, khiến mô hình khó học hỏi từ kết nối hạn chế.
Đặc trưng nút và cạnh(Node and Edge Features): Chất lượng và số lượng đặc trưng ảnh hưởng trực tiếp đến nhúng. Các đặc trưng phong phú hơn thường dẫn đến nhúng tốt hơn, làm giảm mất mát và cải thiện khả năng khái quát hóa.
Kích thước đồ thị và tính đồng nhất(Graph Size and Homophily): Các đồ thị lớn có tính đồng nhất cao (các nút được kết nối với các nút tương tự) có thể tạo ra các nhúng dễ phân loại hơn, trong khi các đồ thị có cấu trúc đa dạng và tính không đồng nhất (các nút được kết nối với các nút không giống nhau) có thể yêu cầu các mô hình phức tạp hơn và dẫn đến mất mát cao hơn nếu không được biểu diễn tốt.

4.7.0.5 Tóm tắt

Loss Function: Đo lường trực tiếp sự khác biệt giữa dự đoán và giá trị thực cho mỗi lô huấn luyện. Các lựa chọn phổ biến bao gồm chéo entropy (phân loại), MSE (hồi quy) và chéo entropy nhị phân hoặc mất mát tương phản (dự đoán liên kết và độ tương tự).
Hàm rủi ro(Risk Function): Biểu thị mất mát dự kiến trên toàn bộ phân phối dữ liệu, phản ánh hiệu suất khái quát hóa.
Training Variables: Tham số mô hình (ví dụ: lớp GNN, độ sâu MLP), siêu tham số (tốc độ học, điều chuẩn) và cấu trúc đồ thị (độ thưa thớt, độ phong phú đặc trưng) đều ảnh hưởng đáng kể đến hàm mất mát và hàm rủi ro trong quá trình huấn luyện.

Bằng cách tinh chỉnh các thành phần này, mô hình có thể đạt được sự hội tụ tốt hơn trên dữ liệu huấn luyện đồng thời đảm bảo khả năng khái quát hóa đối với dữ liệu chưa nhìn thấy, giảm thiểu hiệu quả cả hàm mất mát và hàm rủi ro.

4.8 IX. Đánh giá lỗi trong mạng nơ-ron đồ thị (GNN)

Đánh giá lỗi trong Mạng nơ-ron đồ thị (GNN) thường bao gồm việc hiểu và phân rã tổng lỗi của mô hình thành các thành phần riêng biệt, giúp chẩn đoán các vấn đề về hiệu suất và cải thiện khả năng khái quát hóa. Trong GNN, lỗi có thể bắt nguồn từ nhiều nguồn khác nhau, chẳng hạn như hạn chế xấp xỉ, quá khớp (overfitting), thiếu khớp (underfitting) và đặc thù cấu trúc đồ thị. Về mặt lý thuyết, chúng ta có thể biểu diễn lỗi bằng cách sử dụng phân rã lỗi và phân loại nó thành các loại mất mát riêng biệt, mỗi loại đóng góp vào hiệu suất tổng thể của mô hình.

4.8.0.1 1. Tổng lỗi trong GNN

Lỗi tổng thể trong GNN có thể được mô tả là sự khác biệt giữa dự đoán của mô hình và nhãn thực, và thường được biểu thị là rủi ro dự kiến hoặc lỗi khái quát hóa: \[ \text{Expected Risk} = \mathbb{E}_{(x, y) \sim P_{\text{data}}} \left[ L(f(x; \theta), y) \right] \] trong đó: - $f(x; \theta)$ là mô hình GNN được tham số hóa bởi $\theta$, - $L$ là hàm mất mát (ví dụ: chéo entropy hoặc MSE), - $(x, y)$ là các đặc trưng đầu vào và nhãn mục tiêu, - $P_{\text{data}}$ biểu thị phân phối dữ liệu.

Rủi ro dự kiến này có thể được phân rã thành các thành phần độ lệch (bias), phương sai (variance) và lỗi không thể giảm (irreducible error), tương tự như các mô hình học máy truyền thống. Trong bối cảnh của GNN, các thành phần lỗi này mang ý nghĩa đặc biệt do cấu trúc đồ thị và quá trình tổng hợp vùng lân cận.

4.8.0.2 2. Error Decomposition: Bias, Variance, and Irreducible Error

4.8.0.2.1 A. Lỗi độ lệch (Bias error)

Lỗi độ lệch biểu thị lỗi hệ thống do các giả định hoặc hạn chế của mô hình trong việc xấp xỉ mối quan hệ thực sự giữa đầu vào và đầu ra. Trong GNN, độ lệch bị ảnh hưởng bởi: - Kiến trúc mô hình: Việc lựa chọn hàm tổng hợp (trung bình, tổng, gộp tối đa) và độ sâu ảnh hưởng đến khả năng nắm bắt các sắc thái cấu trúc của GNN. GNN nông có thể có độ lệch cao vì chúng không thể nắm bắt các phụ thuộc phức tạp. - Giả định đơn giản hóa: Các mô hình có giả định mạnh (ví dụ: chỉ sử dụng các nút lân cận trực tiếp hoặc bỏ qua trọng số cạnh) có thể có độ lệch cao nếu các giả định này đơn giản hóa quá mức phân phối dữ liệu thực tế.

Thuật ngữ Bias độ lệch có thể được biểu diễn bằng toán học như sau: \[ \text{Bias} = \left( \mathbb{E}[f(x; \theta)] - y \right)^2 \] trong đó $y$ là nhãn thực và $\mathbb{E}[f(x; \theta)]$ là dự đoán dự kiến trên nhiều phiên bản mô hình hoặc mẫu dữ liệu.

4.8.0.2.2 B. Lỗi phương sai (Variance error)

Lỗi phương sai nắm bắt độ nhạy cảm của dự đoán của mô hình đối với những thay đổi trong dữ liệu huấn luyện. Trong GNN, phương sai có thể phát sinh do: - Độ biến thiên cấu trúc đồ thị: Các biến thể về bậc nút, cấu trúc cộng đồng và phân phối cạnh có thể dẫn đến biến động trong biểu diễn đã học. - Lấy mẫu vùng lân cận: GNN thường tổng hợp thông tin từ các vùng lân cận được lấy mẫu, tạo ra tính ngẫu nhiên. Nếu việc lấy mẫu vùng lân cận thay đổi đáng kể giữa các nút hoặc lô nhỏ, nó có thể dẫn đến phương sai cao. - Quá khớp (Overfitting): GNN sâu hơn dễ bị quá khớp bằng cách ghi nhớ cấu trúc của đồ thị huấn luyện, đặc biệt nếu chúng tận dụng các hàm tổng hợp phức tạp hoặc cơ chế chú ý.

Thuật ngữ Variance phương sai được biểu thị là: \[ \text{Variance} = \mathbb{E}\left[ (f(x; \theta) - \mathbb{E}[f(x; \theta)])^2 \right] \] trong đó $f(x; \theta)$ là dự đoán cho đầu vào$x$và kỳ vọng là trên các nhận thức khác nhau của mô hình được huấn luyện trên các mẫu khác nhau.

4.8.0.2.3 C. Lỗi không thể giảm (Irreducible error)

Lỗi không thể giảm, còn được gọi là lỗi nhiễu, biểu thị nhiễu cố hữu trong dữ liệu mà mô hình không thể giải thích được, bất kể độ phức tạp của nó. Trong trường hợp của GNN, lỗi không thể giảm có thể đến từ: - Nhiễu cố hữu trong nhãn: Dữ liệu đồ thị có thể chứa nhãn nhiễu hoặc không đầy đủ, chẳng hạn như nhãn được gán thông qua phương pháp heuristic hoặc phương pháp giám sát yếu. - Tính ngẫu nhiên của đồ thị: Đồ thị trong thế giới thực thường chứa tính ngẫu nhiên trong các kết nối, điều này có thể khiến việc dự đoán các mối quan hệ một cách chính xác trở nên khó khăn ngay cả với một mô hình hoàn hảo.

Lỗi không thể giảm được biểu diễn bằng toán học như sau: \[ \text{Irreducible Error} = \sigma^2 \] trong đó $\sigma^2$ biểu thị phương sai do nhiễu trong dữ liệu.

4.8.0.3 3. Phân rã cụ thể lỗi GNN thành các lớp mất mát

Lỗi trong GNN có thể được phân rã thêm thành các lớp mất mát khác nhau nắm bắt hành vi của mô hình ở các khía cạnh khác nhau. Chúng bao gồm mất mát phân loại/hồi quy, mất mát cấu trúc và mất mát điều chuẩn.

4.8.0.3.1 A. Mất mát cụ thể cho tác vụ (Mất mát phân loại/hồi quy)

Đây là hàm mất mát chính được sử dụng để tối ưu hóa hiệu suất tác vụ (ví dụ: phân loại hoặc hồi quy). Mất mát này thường biểu thị sự khác biệt giữa dự đoán và nhãn sự thật cơ bản trên một tác vụ có giám sát.

Mất mát phân loại: Mất mát chéo entropy cho các tác vụ phân loại nút hoặc đồ thị.
Mất mát hồi quy: Sai số bình phương trung bình (MSE) cho các tác vụ hồi quy cấp nút hoặc cấp cạnh.

Mất mát cụ thể cho tác vụ cung cấp thước đo lỗi liên quan trực tiếp đến khả năng khớp dữ liệu quan sát của mô hình.

4.8.0.3.2 B. Mất mát cấu trúc

Mất mát cấu trúc xử phạt mô hình dựa trên sự khác biệt về cấu trúc giữa các mối quan hệ dự đoán và thực tế trong đồ thị. Nó đặc biệt phù hợp trong các tác vụ mà độ chính xác quan hệ là rất quan trọng, chẳng hạn như dự đoán liên kết hoặc phát hiện cộng đồng.

Mất mát dự đoán liên kết: Đối với các tác vụ dự đoán cạnh, chéo entropy nhị phân hoặc mất mát tương phản có thể được sử dụng để khuyến khích dự đoán liên kết chính xác và không khuyến khích các liên kết không chính xác.
Điều chuẩn cấu trúc đồ thị: Các thuật ngữ điều chuẩn có thể khuyến khích mô hình duy trì các thuộc tính đồ thị, chẳng hạn như mẫu kết nối hoặc cấu trúc cộng đồng. Ví dụ: - Điều chuẩn Laplacian đồ thị: Khuyến khích các nút tương tự về cấu trúc đồ thị có nhúng tương tự. Thuật ngữ mất mát thường được biểu thị là: \[\text{Laplacian Loss} = \sum_{(i, j) \in E} \left\| \mathbf{z}_i - \mathbf{z}_j \right\|^2\] trong đó$\mathbf{z}_i$và$\mathbf{z}_j$là nhúng của các nút được kết nối$i$và$j$, và$E$là tập hợp cạnh. Mất mát này giảm thiểu sự khác biệt giữa các nhúng của các nút được kết nối, bảo toàn tính nhất quán cấu trúc.
Mất mát độ tương tự nút: Đối với đồ thị mà các nút có mối quan hệ hoặc độ tương tự đã biết, mất mát tương phản có thể khuyến khích các nút có đặc trưng hoặc vai trò cấu trúc tương tự có nhúng tương tự.

4.8.0.3.3 C. Mất mát điều chuẩn

Mất mát điều chuẩn rất cần thiết để kiểm soát độ phức tạp của mô hình và đảm bảo rằng nó khái quát hóa tốt với dữ liệu chưa nhìn thấy. Các kỹ thuật điều chuẩn phổ biến bao gồm:

Suy giảm trọng số (Điều chuẩn L2): Hình phạt đối với trọng số lớn trong các lớp GNN và MLP để ngăn mô hình khớp với nhiễu. Thuật ngữ mất mát là: \[\text{Regularization L2} = \lambda \sum_{k} \|\theta_k\|^2\] trong đó$\lambda$là hệ số điều chuẩn và$\theta_k$biểu thị các tham số mô hình.
Điều chuẩn Dropout: Được sử dụng trong cả lớp GNN và MLP, dropout ngẫu nhiên loại bỏ các nút hoặc cạnh trong quá trình huấn luyện để ngăn mô hình trở nên quá phụ thuộc vào các đường dẫn hoặc nút lân cận cụ thể, cải thiện khả năng khái quát hóa.
Điều chuẩn chú ý: Trong các mô hình sử dụng cơ chế chú ý (ví dụ: Mạng chú ý đồ thị), việc điều chuẩn trọng số chú ý có thể ngăn mô hình chú ý quá mức đến các nút lân cận cụ thể. Một thuật ngữ điều chuẩn khả thi là: \[\text{Attention Entropy Loss} = -\sum_{i} \sum_{j} a_{ij} \log(a_{ij})\] trong đó$a_{ij}$là trọng số chú ý cho các nút lân cận$j$của nút$i$. Thuật ngữ entropy này khuyến khích phân phối chú ý đồng đều hơn, tránh phụ thuộc quá nhiều vào một số ít nút.

4.8.0.4 4. Tóm tắt các thành phần lỗi trong GNN

Tóm lại, lỗi trong GNN có thể được phân rã thành các thành phần lý thuyết và thực tiễn khác nhau:

Độ lệch (Bias): Lỗi hệ thống do kiến trúc và giả định mô hình (ví dụ: GNN nông với tổng hợp vùng lân cận cục bộ).
Phương sai (Variance): Lỗi do độ nhạy của mô hình đối với các biến thể dữ liệu (ví dụ: độ nhạy với các cấu trúc đồ thị khác nhau, quá khớp (overfitting)).
Lỗi không thể giảm (Irreducible Error): Nhiễu trong dữ liệu mà mô hình không thể giải thích được, chẳng hạn như nhiễu nhãn hoặc tính ngẫu nhiên cố hữu trong các kết nối đồ thị.

Mất mát cụ thể cho tác vụ nắm bắt hiệu suất phân loại hoặc hồi quy chính, Mất mát cấu trúc thực thi các thuộc tính đồ thị và tính nhất quán cấu trúc, và Mất mát điều chuẩn kiểm soát độ phức tạp của mô hình, đảm bảo khả năng khái quát hóa và ngăn chặn quá khớp (overfitting).

Mỗi thành phần này đóng góp vào tổng lỗi trong mô hình GNN và cung cấp các khu vực riêng biệt để cải thiện hoặc điều chuẩn trong quá trình huấn luyện mô hình. Bằng cách điều chỉnh các thành phần mất mát này, chúng ta có thể đạt được khả năng khái quát hóa tốt hơn và giảm tổng lỗi, làm cho mô hình mạnh mẽ hơn cho các tác vụ dựa trên đồ thị.

4.9 X. Nguyên tắc cập nhật (học) trong mạng nơ-ron đồ thị (GNN)

Nguyên tắc cập nhật (học) được sử dụng trong Mạng nơ-ron đồ thị (GNN) thực sự dựa trên lan truyền ngược đầu cuối (end-to-end backpropagation), trong đó các tham số của mô hình được tối ưu hóa bằng cách lan truyền gradient lỗi từ lớp đầu ra qua từng lớp của mạng, bao gồm cả GNN và bất kỳ lớp MLP bổ sung nào. Quá trình đầu cuối này cho phép mô hình học các biểu diễn được tối ưu hóa trực tiếp cho mục tiêu nhiệm vụ (ví dụ: phân loại, hồi quy). Chúng ta hãy đi sâu hơn vào các khía cạnh chính, thuộc tính, độ phức tạp tính toán và phân tích lý thuyết về quá trình học này.

4.9.0.1 1. Lan truyền ngược đầu cuối trong GNN

Lan truyền ngược đầu cuối trong GNN bao gồm việc tính toán gradient của hàm mất mát đã chọn đối với các tham số mô hình và cập nhật chúng lặp đi lặp lại để giảm thiểu mất mát. Cụ thể, trong GNN: - Các lớp GNN tổng hợp thông tin từ các nút lân cận và truyền thông tin này qua các trọng số có thể học được. - Lan truyền ngược cho phép mô hình lan truyền tín hiệu lỗi từ lớp cuối cùng (ví dụ: đầu ra MLP) ngược trở lại qua từng lớp GNN, điều chỉnh trọng số trên tất cả các lớp để tối ưu hóa hiệu suất nhiệm vụ.

Quá trình học tập tổng thể có thể được tóm tắt như sau: 1. Chuyển tiếp: Tính toán nhúng nút bằng cách tổng hợp các đặc trưng thông qua các lớp GNN và tạo dự đoán cụ thể cho tác vụ (ví dụ: lớp nút hoặc giá trị hồi quy). 2. Tính toán mất mát: Tính toán mất mát cụ thể cho tác vụ (ví dụ: chéo entropy để phân loại). 3. Tính toán gradient: Tính toán gradient của mất mát đối với mỗi tham số trong các lớp GNN và MLP bằng cách sử dụng lan truyền ngược. 4. Cập nhật tham số: Cập nhật tham số bằng cách sử dụng bộ tối ưu hóa (ví dụ: giảm dần gradient ngẫu nhiên, Adam).

4.9.0.2 2. Thuộc tính của lan truyền ngược đầu cuối trong GNN

Một số thuộc tính xác định cách lan truyền ngược đầu cuối hoạt động trong GNN:

4.9.0.2.1 A. Tổng hợp thông tin theo lớp

Lan truyền ngược trong GNN vốn hỗ trợ học tập theo lớp. Mỗi lớp học cách tổng hợp thông tin vùng lân cận ở các bước nhảy lớn hơn dần, với các lớp đầu tập trung vào các nút lân cận gần và các lớp sâu hơn nắm bắt ngữ cảnh rộng hơn.

4.9.0.2.2 B. Gradient thông qua cấu trúc đồ thị

Lan truyền ngược đầu cuối yêu cầu gradient chạy qua cấu trúc đồ thị, nghĩa là cập nhật nhúng của mỗi nút phụ thuộc vào các nút lân cận của nó. Điều này dẫn đến chia sẻ tham số giữa các nút, cho phép GNN khái quát hóa tốt hơn trên toàn bộ đồ thị.

4.9.0.2.3 C. Chia sẻ tham số và bất biến đồ thị

GNN học các tham số bất biến với thứ tự nút và đồng dạng đồ thị, nghĩa là cùng một tham số đã học có thể áp dụng bất kể nhận dạng nút hoặc hướng đồ thị. Thuộc tính này cho phép GNN khái quát hóa cho các cấu trúc đồ thị khác nhau.

4.9.0.2.4 D. Khả năng diễn giải của trọng số

Học tập đầu cuối cung cấp các tham số có thể diễn giải trong mỗi lớp. Ví dụ: trong Mạng chú ý đồ thị, trọng số chú ý đã học cho biết nút lân cận nào đóng góp nhiều nhất vào biểu diễn của nút.

4.9.0.3 3. Khó khăn và thách thức của lan truyền ngược đầu cuối trong GNN

Mặc dù hiệu quả, lan truyền ngược đầu cuối trong GNN có một số thách thức và hạn chế:

4.9.0.3.1 A. Vấn đề làm mịn quá mức (Over-smoothing)

Với GNN sâu, học tập đầu cuối có thể dẫn đến vấn đề làm mịn quá mức: khi độ sâu mạng tăng lên, nhúng nút có thể hội tụ về các giá trị tương tự nhau trên toàn bộ đồ thị, làm mất đi sự phân biệt giữa các nút khác nhau. Điều này xảy ra do khi thông tin lan truyền qua nhiều lớp, các nút kết hợp nhiều nút lân cận ở xa hơn, có khả năng làm mất các đặc điểm riêng lẻ của nút.

4.9.0.3.2 B. Gradient biến mất hoặc bùng nổ

Trong GNN rất sâu, gradient có thể biến mất hoặc bùng nổ khi chúng lan truyền ngược qua nhiều lớp, đặc biệt là với một số hàm kích hoạt nhất định. Vấn đề này có thể cản trở sự hội tụ và dẫn đến kết quả học tập kém cho các mô hình sâu.

4.9.0.3.3 C. Chi phí bộ nhớ và tính toán cao

Lan truyền ngược đầu cuối trong GNN tốn nhiều bộ nhớ vì tất cả nhúng nút, kết quả trung gian và gradient cần được lưu trữ cho mỗi lớp trong quá trình chuyển ngược. Điều này có thể trở nên khó khăn đối với các đồ thị lớn, đặc biệt là khi thực hiện xử lý hàng loạt trên các cấu trúc vùng lân cận lớn.

4.9.0.4 4. Độ phức tạp tính toán và phân tích lý thuyết

Học tập đầu cuối trong GNN phức tạp về mặt tính toán do hai lý do chính: quá trình tổng hợp vùng lân cận và tính toán gradient.

4.9.0.4.1 A. Độ phức tạp của tổng hợp vùng lân cận

Mỗi lớp trong GNN tổng hợp thông tin từ các nút lân cận, dẫn đến sự mở rộng về lượng dữ liệu được xử lý trên mỗi nút. Đối với đồ thị có$N$nút, độ phức tạp tính toán của chuyển tiếp của mỗi lớp phụ thuộc vào: - Bậc nút trung bình ($d$): Xác định số lượng nút lân cận mà mỗi nút tổng hợp từ đó. - Độ sâu tổng hợp ($K$): Xác định khoảng cách mà mỗi nút thu thập thông tin (tức là số lớp GNN).

Chuyển tiếp trong lớp GNN thường có độ phức tạp thời gian là$O(N \times d)$. Tuy nhiên, đối với các đồ thị lớn, việc lưu trữ và tính toán trên tất cả các nút lân cận trong mỗi lớp trở nên khó khăn.

4.9.0.4.2 B. Độ phức tạp của lan truyền ngược

Chuyển ngược bao gồm việc tính toán và lưu trữ gradient cho các tham số của mỗi nút và cạnh, có độ phức tạp tương đương với chuyển tiếp trong mỗi lớp. Với$L$lớp, độ phức tạp tổng thể cho một lần chuyển (chuyển tiếp và chuyển ngược) là khoảng$O(L \times N \times d)$, tỷ lệ tuyến tính với độ sâu và kích thước của đồ thị. Tuy nhiên, sự tăng trưởng theo cấp số nhân của các nút lân cận (lên đến$d^K$nút lân cận) có thể dẫn đến tính toán quá mức trong GNN sâu.

4.9.0.4.3 C. Kỹ thuật để quản lý độ phức tạp

Phương pháp dựa trên lấy mẫu (ví dụ: GraphSAGE): Thay vì tổng hợp trên tất cả các nút lân cận, chỉ một tập hợp con của các nút lân cận được lấy mẫu. Điều này làm giảm kích thước vùng lân cận hiệu quả và chi phí tính toán.
Xử lý lô nhỏ: Đối với đồ thị lớn, việc huấn luyện có thể được thực hiện trên đồ thị con hoặc lô nhỏ để hạn chế mức sử dụng bộ nhớ.
Phương pháp tổng hợp lớp (ví dụ: kết nối bỏ qua): Chúng cho phép thông tin từ các lớp trước đó bỏ qua các bước nhất định, giảm làm mịn quá mức và độ sâu tính toán.

4.9.0.5 5. Tốc độ hội tụ và các khía cạnh quan trọng của quy tắc học

Tốc độ hội tụ của GNN phụ thuộc vào các yếu tố như tốc độ học, khởi tạo, cấu trúc đồ thị và điều chuẩn:

4.9.0.5.1 A. Tốc độ hội tụ

Tốc độ học: Tốc độ học cao hơn sẽ tăng tốc độ hội tụ nhưng có thể gây ra dao động hoặc mất ổn định, trong khi tốc độ học thấp hơn làm chậm tốc độ hội tụ nhưng cung cấp các bản cập nhật ổn định hơn.
Cấu trúc đồ thị: Đồ thị có kết nối cao hoặc dư thừa đôi khi có thể làm chậm tốc độ hội tụ vì mô hình phải học cách điều chỉnh cho thông tin lặp lại giữa các nút lân cận.
Điều chuẩn: Các kỹ thuật như dropout, suy giảm trọng số hoặc điều chuẩn chú ý có thể giúp giảm thiểu quá khớp (overfitting) và khuyến khích hội tụ mượt mà hơn.

4.9.0.5.2 B. Tầm quan trọng của quy tắc học

Quy tắc học trong GNN rất quan trọng vì nó đảm bảo rằng nhúng kết hợp biểu diễn nhận biết ngữ cảnh nắm bắt cả đặc trưng nút và cấu trúc vùng lân cận. Các khía cạnh chính cần xem xét trong quy tắc học bao gồm:

Cân bằng thông tin cục bộ và toàn cục: Quy tắc học cho phép GNN kết hợp thông tin cục bộ (nút lân cận trực tiếp) với thông tin toàn cục (nút ở xa hơn) một cách có kiểm soát.
Lựa chọn đặc trưng thông qua chú ý: Các cơ chế chú ý được nhúng trong quy tắc học giúp chọn nút lân cận nào cung cấp nhiều thông tin nhất, cho phép mô hình giảm nhiễu và tập trung vào các mối quan hệ thiết yếu.
Hiệu ứng lấy mẫu vùng lân cận: Sử dụng các phương pháp dựa trên lấy mẫu để giảm gánh nặng tính toán cũng đưa tính ngẫu nhiên vào quy tắc học, điều này có thể giúp cải thiện khả năng khái quát hóa bằng cách cho mô hình tiếp xúc với các cấu trúc vùng lân cận khác nhau.

4.9.0.6 Hình dung quá trình học

Hình dung bên về học tập đầu cuối trong GNN có thể minh họa:

Luồng thông tin theo từng lớp: Hiển thị cách mỗi lớp tổng hợp thông tin, với các nút lân cận kết nối với nút tiêu cự trong mỗi lớp để thể hiện các trường tiếp nhận ngày càng tăng.
Luồng gradient: Cho biết gradient chạy ngược trở lại qua các lớp GNN, hiển thị nơi lỗi tác động nhiều nhất trong quá trình huấn luyện.
Trọng số chú ý hoặc lựa chọn tổng hợp: Hình dung nút lân cận nào được tính trọng số nhiều nhất trong các mô hình dựa trên chú ý.

Hình dung như vậy giúp làm rõ cách thông tin lan truyền từ các nút lân cận đến các nút trung tâm và cách gradient được phân phối trên toàn bộ đồ thị, cho biết các nút hoặc lớp quan trọng trong quá trình học.

4.9.0.7 Tóm tắt

Lan truyền ngược đầu cuối cho phép GNN học nhúng bằng cách lan truyền lỗi ngược trở lại từ lớp đầu ra qua từng lớp, tối ưu hóa tham số để giảm thiểu mất mát.
Thuộc tính: Lan truyền ngược trong GNN được hưởng lợi từ tổng hợp theo lớp, chia sẻ tham số và khả năng diễn giải nhưng phải đối mặt với những thách thức với làm mịn quá mức, chi phí bộ nhớ và độ phức tạp tính toán.
Độ phức tạp tính toán: Lan truyền ngược trong GNN là$O(L \times N \times d)$, tỷ lệ với số lớp, số nút và bậc trung bình nhưng có thể tăng theo cấp số nhân trong đồ thị lớn.
Hội tụ và quy tắc học: Tốc độ hội tụ phụ thuộc vào tham số học, cấu trúc đồ thị và điều chuẩn. Các khía cạnh chính bao gồm khả năng cân bằng thông tin cục bộ/toàn cục, chọn các nút lân cận cung cấp nhiều thông tin và điều chỉnh các phương pháp lấy mẫu để đạt hiệu quả.

Hiểu và giải quyết các khía cạnh này là điều cần thiết để tối ưu hóa quá trình học của GNN, đạt được sự cân bằng giữa hiệu quả tính toán, sức mạnh biểu đạt và khả năng khái quát hóa.

4.10 Giải thích các ký hiệu toán học

Trong tài liệu này, chúng tôi đã sử dụng một số ký hiệu toán học để biểu diễn các khái niệm và công thức. Dưới đây là bảng giải thích ngắn gọn về các ký hiệu này:

Ký hiệu	Giải thích
$G(V, E)$	Đồ thị G với tập hợp các đỉnh V và tập hợp các cạnh E
$V$	Tập hợp các đỉnh trong đồ thị
$E$	Tập hợp các cạnh trong đồ thị
$(u, v)$	Một cạnh nối đỉnh u và đỉnh v
$A$	Ma trận kề của đồ thị
$A_{ij}$	Phần tử tại hàng i và cột j của ma trận kề, biểu thị sự tồn tại của cạnh giữa đỉnh i và đỉnh j
$\mathbb{R}^d$	Không gian vectơ d chiều
$d$	Số chiều của không gian nhúng
$\mathbf{z}_v$	Vectơ nhúng của đỉnh v
$\mathsf{ENC}(v)$	Mã hóa nút của đỉnh v
$X_v$	Vectơ đặc trưng của nút v
$w_{uv}$	Trọng số của cạnh (u, v)
$\deg(v)$	Bậc của nút v (số lượng cạnh kết nối với v)
$f(x; \theta)$	Mô hình GNN với tham số $\theta$
$L$	Hàm mất mát
$(x, y)$	Đặc trưng đầu vào x và nhãn mục tiêu y
$P_{\text{data}}$	Phân phối dữ liệu
$\mathbb{E}$	Giá trị kỳ vọng
$\sigma^2$	Phương sai
$\lambda$	Hệ số điều chuẩn

Tài Liệu Tham Khảo:

General Overview of GNNs and End-to-End Backpropagation
- Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations (ICLR). This paper introduces the Graph Convolutional Network (GCN) and discusses how backpropagation is applied to optimize GNNs for semi-supervised learning tasks. here
- Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., … & Weller, J. (2018). Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261. Provides a comprehensive overview of GNNs, relational inductive biases, and the role of end-to-end learning in various graph-based applications. here
Error Decomposition in GNNs: Bias, Variance, and Irreducible Error
- Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018). Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning (ICML). This paper addresses issues of over-smoothing and bias in GNNs and proposes techniques like skip connections to maintain node feature differentiation in deep layers. here
Common Loss Functions for GNNs and Structural Regularization
- Zhang, M., & Chen, Y. (2018). Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS). Discusses binary cross-entropy loss and contrastive loss for link prediction tasks, as well as various structural regularization techniques in GNNs.here
- Kipf, T. N., & Welling, M. (2016). Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. This paper introduces contrastive loss in the context of graph autoencoders and explains structural regularization techniques to preserve graph features during embedding. here
Computational Complexity in GNNs and Efficient Learning Techniques
- Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS). This paper introduces the GraphSAGE model, which uses neighborhood sampling to reduce computational complexity and improve scalability for large graphs. here
- Chen, J., Ma, T., & Xiao, C. (2018). FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations (ICLR). FastGCN presents sampling-based methods to manage the computational costs of neighborhood aggregation in large graphs. here
Over-Smoothing in Deep GNNs and Solutions to Improve Convergence
- Li, Q., Han, Z., & Wu, X.-M. (2018). Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence (AAAI). This paper discusses the over-smoothing phenomenon in GNNs and analyzes the limitations of deeper GNNs, providing insights into architectural adjustments to address these issues. here
- Rong, Y., Huang, W., Xu, T., & Huang, J. (2020). DropEdge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations (ICLR). DropEdge proposes a regularization technique to mitigate over-smoothing by randomly removing edges during training, thus preserving node distinction across layers. here
Learning Principles and Convergence in GNNs
- Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2018). Graph attention networks. In International Conference on Learning Representations (ICLR). This paper introduces attention-based GNNs, which help in learning relevant node dependencies and offer insights into convergence dynamics through attention weights.here
- Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. Adam optimizer is commonly used in training GNNs and aids in achieving stable convergence by adaptively adjusting the learning rate for each parameter. here
End-to-End Learning in Graph-Based Models: Visualizations and Interpretability
- Ying, Z., Bourgeois, D., You, J., Zitnik, M., & Leskovec, J. (2019). GNNExplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS). Provides methods for visualizing and interpreting the layers of GNNs to understand feature and neighbor importance in end-to-end learning.here
- Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018). Modeling relational data with graph convolutional networks. In European Semantic Web Conference. This paper explains relational modeling in GNNs, discussing interpretability of learned representations and visualizing how relationship types affect node embeddings.here

--- title: The GNN analysis --- This one is **untranslated from a collaborator**. Proceed with discretion on yourself. ___ Author: Lường Văn Tâm in accordance with the laboratory double descent research. ## I.Phân tích loại đồ thị $G(V, E)$ Để phân tích loại đồ thị $G(V, E)$ trong bối cảnh toán học và lý thuyết chặt chẽ, chúng ta hãy khám phá các loại đồ thị phổ biến liên quan đến các ứng dụng học máy, đặc biệt chú ý đến cách các loại này liên quan đến các mô hình và nhiệm vụ cụ thể. Trong lý thuyết đồ thị và học máy, loại đồ thị không chỉ ảnh hưởng đến các thuộc tính cấu trúc của nó mà còn ảnh hưởng đến thiết kế của các thuật toán học tập và các phương pháp nhúng áp dụng cho nó. Chúng ta hãy đi sâu vào từng phân loại tiềm năng cho $G(V, E)$: ### 1. Đồ thị song phương (Bilateral Graphs) Trong học máy, khái niệm đồ thị song phương "Bilateral" có thể không phải là tiêu chuẩn nhưng có thể được hiểu trong bối cảnh kết nối mạng nơ-ron. Trong mạng nơ-ron, các lớp được kết nối đầy đủ (hoặc dày đặc) kết nối mọi nút trong một lớp với mọi nút trong lớp tiếp theo, có thể được khái niệm hóa một cách lỏng lẻo là "Bilateral" vì kết nối là hai chiều. Tuy nhiên, thiết lập này không hoàn toàn phù hợp với định nghĩa cổ điển về đồ thị song phương trong lý thuyết đồ thị. Trong đồ thị song phương, chúng ta có thể mong đợi mỗi cạnh xuất hiện theo cả hai hướng giữa hai nút, tạo ra các kết nối không có hướng (đôi khi cho phép các kết nối có hướng qua lại theo cả hai hướng cho mỗi cạnh). Do đó, nếu chúng ta xem xét một đồ thị "song phương" theo nghĩa này, thì nó sẽ ngụ ý một **đồ thị vô hướng** $G(V, E)$ trong đó đối với mỗi cạnh $(u, v) \in E$, tồn tại một cạnh tương ứng $(v, u) \in E$. Nói một cách toán học, điều này ngụ ý rằng nếu $G$ là song phương, thì nó **đối xứng** trong ma trận kề $A$ của nó, trong đó $A_{ij} = A_{ji}$. Các cấu trúc như vậy phổ biến trong các ứng dụng như mạng xã hội, nơi các kết nối (ví dụ: tình bạn) thường là lẫn nhau. Tuy nhiên, nhiều tác vụ học máy, đặc biệt là các tác vụ trong **mô hình trình tự (sequence modeling)** hoặc **biểu diễn dựa trên luồng( flow - based representation )**, không yêu cầu các kết nối song phương như vậy và thường sử dụng đồ thị có hướng. ### 2. Đồ thị có hướng và đồ thị Digraph **Đồ thị có hướng** hoặc **digraph** là đồ thị mà các cạnh có hướng, được biểu diễn bằng các cặp đỉnh có thứ tự $(u, v)$. Trong bối cảnh học máy, đồ thị có hướng đặc biệt quan trọng khi biểu diễn các phụ thuộc hoặc luồng thông tin. Ví dụ: trong **mạng nơ-ron truyền thẳng** như perceptron nhiều lớp (MLP), mỗi lớp sẽ đưa vào lớp tiếp theo theo một hướng cụ thể mà không có chu kỳ hoặc kết nối ngược. Trong trường hợp này, đồ thị biểu diễn mạng sẽ có hướng, với các cạnh chỉ hướng về phía trước. Ví dụ: - Nếu mỗi đỉnh đại diện cho một lớp trong mạng, thì các cạnh chỉ được hướng từ các lớp trước đó sang các lớp sau, phù hợp với luồng dữ liệu. - Đồ thị có hướng cũng được sử dụng để biểu diễn các phụ thuộc chuỗi, như trong xử lý ngôn ngữ tự nhiên hoặc mạng nơ-ron hồi quy (RNN), trong đó thứ tự thời gian hoặc thứ tự tuần tự là quan trọng. Ở đây, các cạnh có thể đại diện cho sự chuyển đổi từ trạng thái này sang trạng thái tiếp theo trong một chuỗi. Về mặt hình thức, đồ thị có hướng $G = (V, E)$ có **ma trận kề không đối xứng** $A$, trong đó $A_{ij} \neq A_{ji}$ nói chung. Việc thiếu tính đối xứng trong $A$ thể hiện tính định hướng của các kết nối, điều cần thiết để mô hình hóa dữ liệu tuần tự hoặc dữ liệu có thứ tự nhân quả. ### 3. Đồ thị đa cạnh **Đồ thị đa cạnh** là đồ thị cho phép nhiều cạnh giữa các cặp đỉnh. Điều này có nghĩa là đối với các đỉnh $u$ và $v$, có thể tồn tại một số cạnh riêng biệt, mỗi cạnh có khả năng đại diện cho các loại quan hệ khác nhau hoặc nhiều tương tác. Trong các ứng dụng học máy: - Đồ thị đa cạnh có thể đại diện cho các mạng phức tạp với nhiều loại quan hệ. Ví dụ: trong mạng xã hội, các cạnh khác nhau có thể đại diện cho các loại quan hệ khác nhau: tình bạn, kết nối nghề nghiệp, gia đình, v.v. - Trong đồ thị tri thức hoặc hệ thống đề xuất, đồ thị đa cạnh có thể đại diện cho các loại tương tác khác nhau giữa người dùng và mặt hàng, chẳng hạn như mua hàng, lượt thích hoặc lượt xem. Trong biểu diễn ma trận, đồ thị đa cạnh thường sử dụng **biểu diễn tenxơ** thay vì một ma trận kề duy nhất để giải thích cho sự đa dạng của các cạnh. Ngoài ra, đồ thị đa cạnh có thể được biểu diễn bằng cách liên kết trọng số hoặc các thuộc tính bổ sung với các cạnh để phân biệt chúng. Bằng cách này, chúng ta có thể mã hóa các loại quan hệ đa dạng trong một cấu trúc duy nhất. ### 4. Đồ thị có trọng số **Đồ thị có trọng số** là đồ thị mà mỗi cạnh $(u, v) \in E$ được liên kết với trọng số $w_{uv}$, thường được biểu diễn bằng ma trận kề có trọng số $W$, trong đó mỗi mục nhập $W_{uv}$ đại diện cho trọng số của cạnh giữa$u$và$v$. Đồ thị có trọng số rất quan trọng trong các ứng dụng mà cường độ hoặc khả năng của các kết nối là quan trọng, chẳng hạn như: - **Mạng nơ-ron đồ thị (GNN)**: Nhiều GNN tận dụng đồ thị có trọng số, trong đó trọng số cạnh có thể đại diện cho cường độ tương tác hoặc sự giống nhau giữa các nút. - **Bài toán tối ưu hóa**: Trong các bài toán như người bán hàng đi du lịch hoặc đường đi ngắn nhất, trọng số cạnh đại diện cho khoảng cách hoặc chi phí. Trọng số thêm một lớp phức tạp cho đồ thị, vì các thuật toán phải tính đến những điều này khi tính toán các thuộc tính như đường dẫn, kết nối và cụm. Ma trận kề có trọng số thường đối xứng đối với đồ thị không có hướng và không đối xứng đối với đồ thị có hướng. ### 5. Đồ thị không có hướng Trong **đồ thị không có hướng**, các cạnh không có hướng, có nghĩa là nếu có một cạnh giữa $u$ và $v$, nó có thể được đi qua theo cả hai hướng. Loại đồ thị này phổ biến khi biểu diễn **các mối quan hệ lẫn nhau** hoặc **tương tác hai chiều** trong đó hướng của kết nối không quan trọng về mặt nội tại. Đồ thị không có hướng được biểu diễn bằng ma trận kề đối xứng, trong đó $A_{ij} = A_{ji}$. Các trường hợp sử dụng phổ biến bao gồm: - **Mạng xã hội**: Nếu chúng ta đang đại diện cho tình bạn lẫn nhau, thì đồ thị không có hướng là phù hợp. - **Lọc cộng tác trong hệ thống đề xuất**: Nếu cả người dùng và mặt hàng đều được coi là đối xứng, thì đồ thị không có hướng giúp nắm bắt bản chất có đi có lại của sở thích hoặc ái lực. Trong đồ thị không có hướng, các cạnh thường dễ xử lý hơn về mặt tính toán vì tính đối xứng có thể làm giảm số lượng phép tính cần thiết cho các phép toán nhất định (ví dụ: phân rã giá trị riêng). ### 6. Siêu đồ thị và đồ thị lưỡng phân Mặc dù không được đề cập trực tiếp trong bài báo, **siêu đồ thị** và **đồ thị lưỡng phân** là các cấu trúc khác đáng xem xét trong các ứng dụng học máy: - **Siêu đồ thị** cho phép các cạnh (siêu cạnh) kết nối nhiều hơn hai nút. Điều này có thể hữu ích trong các ứng dụng như nhóm người dùng dựa trên các hoạt động hoặc mặt hàng được chia sẻ, trong đó mỗi siêu cạnh có thể đại diện cho một nhóm. - **Đồ thị lưỡng phân** bao gồm hai tập hợp nút rời rạc, trong đó các cạnh chỉ kết nối các nút giữa các tập hợp (không nằm trong cùng một tập hợp). Các đồ thị này rất phù hợp trong các hệ thống đề xuất, trong đó một tập hợp các nút đại diện cho người dùng và tập hợp còn lại đại diện cho các mặt hàng. Tóm tắt các loại đồ thị và tính phù hợp của chúng đối với học máy Dựa trên loại dữ liệu và tác vụ học $G(V,E)$ có thể được phân loại thành bất kỳ loại nào sau đây: * **Song phương/Vô hướng(Bilateral/Undirected)** cho các mối quan hệ tương hỗ, trong đó hướng cạnh không quan trọng và các kết nối là có đi có lại. * **Có định hướng/Điểu đồ hướng(Directed/Digraph)** đối với dữ liệu có thứ tự cố hữu, chẳng hạn như kiến trúc dựa trên luồng (MLP hoặc RNN) hoặc cấu trúc nhân quả. * **Đa đồ thị(Multigraph)** khi tồn tại nhiều mối quan hệ riêng biệt giữa các nút. * **Đồ thị có trọng số(Weighted Graph)** nếu cường độ cạnh thay đổi và những biến thể này rất quan trọng đối với mô hình. * **Đồ thị vô hướng(Undirected Graph)** trong các ứng dụng mà các kết nối vốn có bản chất song phương và đối xứng. Mỗi loại áp đặt các ràng buộc và khả năng khác nhau về mặt biểu diễn tính toán, khả năng diễn giải và tiềm năng học tập trong các mô hình học máy dựa trên đồ thị. Việc lựa chọn loại cẩn thận là rất quan trọng vì nó ảnh hưởng đến các chiến lược nhúng, phương pháp tổng hợp lân cận và khả năng diễn giải các tính năng nút đã học trong các mô hình như GNN. ### 8Không gian nhúng của đồ thị $G(V, E)$ Không gian nhúng của đồ thị $G(V, E)$ là một không gian vectơ có cấu trúc, thường có số chiều thấp hơn, trong đó các đỉnh $v \in V$ được biểu diễn bằng các vectơ. Việc lựa chọn không gian này là rất quan trọng, vì nó xác định mức độ nắm bắt thông tin cấu trúc về đồ thị. Các đặc điểm của không gian nhúng như độ sâu, số chiều và độ phong phú có thể ảnh hưởng lớn đến khả năng khái quát hóa của mô hình, diễn giải các thuộc tính cấu trúc và cho phép tính toán hiệu quả cho các tác vụ tiếp theo. #### Xác định không gian nhúng cho đồ thị $G(V, E)$ 1. **Không gian nhúng là gì?** Trong bối cảnh đồ thị, không gian nhúng là một không gian vectơ $\mathbb{R}^d$ (trong đó $d \ll |V|$) trong đó mỗi đỉnh $v \in V$ được biểu diễn bằng một vectơ $\mathbf{z}_v \in \mathbb{R}^d$. Các nhúng này được học hoặc tính toán sao cho các mối quan hệ hình học (khoảng cách, góc hoặc thuộc tính topo) trong không gian vectơ phản ánh các mối quan hệ trong đồ thị $G$. Số chiều $d$ của không gian nhúng và hàm ánh xạ được thiết kế để nắm bắt càng nhiều càng tốt thông tin cấu trúc và quan hệ có liên quan trong $G$. Mục đích là để các nút "gần" trong đồ thị (dựa trên đường dẫn, kề nhau hoặc vai trò cấu trúc) có các nhúng gần nhau trong $\mathbb{R}^d$ theo một số số liệu khoảng cách. 2. **Ví dụ trong bài toán người bán hàng đi du lịch (TSP)** Đối với các tác vụ như TSP, không gian nhúng thường sử dụng **không gian Euclide 2D** trong đó các đỉnh được định vị dựa trên tọa độ trong thế giới thực (ví dụ: các thành phố trên bản đồ). Ở đây, ma trận kề hoặc khoảng cách biểu thị khoảng cách theo cặp giữa các đỉnh trong $\mathbb{R}^2$ , nắm bắt khoảng cách hình học là mối quan hệ chính giữa các đỉnh. Số chiều $d = 2$ là đủ vì bài toán vốn có tính chất không gian. 3. **Nhúng đồ thị trong học máy** Trong các bối cảnh học máy phức tạp hơn (chẳng hạn như đối với Mạng nơ-ron đồ thị hoặc phân loại nút), không gian nhúng có thể thay đổi đáng kể về số chiều và thường là **số chiều cao**. Số chiều $d$ được chọn dựa trên độ phức tạp của cấu trúc đồ thị, độ phong phú của thông tin mà mỗi nút cần nắm bắt và các yêu cầu của tác vụ học tập. ## II. Thuộc tính của không gian nhúng: Độ sâu, kích thước và độ phong phú Bây giờ, chúng ta hãy phân tích từng thuộc tính của không gian nhúng một cách chi tiết hơn. ##### 1. Độ sâu và kích thước của không gian nhúng - **Độ sâu(Depth):** có thể được xem như là mức độ mà một nhúng có thể nắm bắt các quan hệ đồ thị phức tạp hoặc bậc cao hơn thông qua nhiều lớp hoặc cấp độ tổng hợp. Nói một cách thực tế, điều này thường liên quan đến số lượng **lớp trong một mô hình**, chẳng hạn như trong Mạng nơ-ron đồ thị (GNN), trong đó độ sâu có thể đề cập đến số lượng lớp tổng hợp lân cận (bước nhảy) được sử dụng để tạo ra mỗi nhúng. - **Số chiều Dimensionality ($d$)**: Kích thước của không gian nhúng, tức là số chiều $d$, có thể dao động từ số chiều thấp (ví dụ: $d = 2$ hoặc $3$ cho nhúng trực quan hoặc không gian) đến số chiều cao (ví dụ: $d = 128$ hoặc $d = 512$ trong mạng xã hội phức tạp hoặc đồ thị tri thức). Số chiều cao hơn cho phép nhúng nắm bắt các mối quan hệ phức tạp hơn và các điểm tinh tế trong cấu trúc đồ thị. Ví dụ: - **Nhúng nông(Shallow embeddings)**: Các phương pháp như Laplacian Eigenmaps hoặc DeepWalk có thể sử dụng số chiều thấp hơn (ví dụ: $d \sim 10$ đến $100$), tập trung vào việc bảo toàn cấu trúc lân cận cục bộ. - **Nhúng sâu(Deep embeddings)**: GNN hiện đại thường tận dụng số chiều $d \sim 100$ đến $512$ hoặc thậm chí cao hơn, đặc biệt là trong đồ thị dày đặc hoặc cho các ứng dụng như phân loại nút và dự đoán liên kết, trong đó các chi tiết cấu trúc chi tiết là rất quan trọng. - **Kích thước nhúng so với độ phức tạp của đồ thị $G$**: Không gian nhúng cần đủ lớn để phản ánh **độ đa dạng cấu trúc** và **khả năng kết nối** trong đồ thị. Đối với các mạng có kết nối cao, phức tạp với các loại nút hoặc vai trò đa dạng (ví dụ: mạng xã hội hoặc mạng sinh học), kích thước nhúng lớn hơn cho phép biểu diễn đặc trưng phong phú hơn. Ngược lại, các đồ thị đơn giản hơn có thể không hưởng lợi đáng kể từ các nhúng có số chiều cao. ##### 2. Độ phong phú của không gian nhúng Để xác định **độ phong phú** của không gian nhúng, chúng ta xem xét mức độ hiệu quả của nó trong việc nắm bắt các sắc thái cấu trúc, mối quan hệ và sự đa dạng của các nút trong đồ thị. Độ phong phú có thể được đánh giá dựa trên: - **Bảo toàn lân cận(Neighborhood Preservation)**: Không gian nhúng phong phú nên nắm bắt **cấu trúc lân cận cục bộ(local neighborhood)** một cách chính xác, có nghĩa là các nút gần nhau trong đồ thị cũng nên gần nhau trong không gian nhúng. Ví dụ: - Các kỹ thuật như **node2vec** sử dụng bước đi ngẫu nhiên có thiên vị để tạo ra các nhúng nhấn mạnh sự giống nhau của lân cận. - GraphSAGE và các phương pháp dựa trên GNN tương tự tổng hợp thông tin từ nhiều bước nhảy, nắm bắt thông tin lân cận đa cấp, làm phong phú thêm không gian nhúng bằng cách mã hóa cả ngữ cảnh cục bộ và toàn cục. - **Vai trò cấu trúc và phát hiện cộng đồng**: Không gian nhúng phong phú nên phân biệt **vai trò cấu trúc** (ví dụ: nút trung tâm so với nút ngoại vi, nút cầu nối) và có khả năng tách các nút thành **cộng đồng** hoặc cụm. Các phương pháp nhúng đạt được điều này bằng cách sử dụng các thuộc tính như mẫu kết nối, hệ số phân cụm và mô-típ bậc cao hơn: - Các phương pháp như **struc2vec** hoặc **GraphWave** nhúng các nút dựa trên sự giống nhau về cấu trúc, giúp không gian nhúng nắm bắt các vai trò vượt ra ngoài khả năng kết nối đơn giản. - Kiến trúc GNN cũng có thể kết hợp thông tin cộng đồng bằng cách tổng hợp các đặc trưng lân cận trên một số lớp. - **Mã hóa các mối quan hệ bậc cao(Encoding Higher-Order Relationships)**: Không gian nhúng phong phú cũng có thể nắm bắt **mô-típ đồ thị bậc cao(higher-order graph motifs)** (ví dụ: hình tam giác, clique) hoặc cấu trúc đồ thị con. Điều này đặc biệt phù hợp trong các ứng dụng như hóa học hoặc sinh học, trong đó các mẫu nhất định trong mạng tương tác phân tử hoặc protein mang ý nghĩa ngữ nghĩa. Không gian nhúng nắm bắt các mô-típ như vậy thường được thiết kế bằng cách sử dụng: - Các phương pháp dựa trên bước đi ngẫu nhiên mã hóa gián tiếp các cấu trúc này bằng cách tổng hợp thống kê đồng xuất hiện. - **Phương pháp phổ(Spectral methods)** và **GNN tích chập(convolutional GNNs)** nắm bắt cấu trúc topo thông qua các bộ lọc phổ hoặc tổng hợp lân cận. - **Tích hợp thuộc tính và đặc trưng**: Trong đồ thị mà các nút có các đặc trưng liên quan (ví dụ: hồ sơ trong mạng xã hội, thuộc tính phân tử), độ phong phú cũng có thể đề cập đến mức độ không gian nhúng kết hợp các đặc trưng này cùng với thông tin cấu trúc. GNN, đặc biệt là những GNN sử dụng **cơ chế chú ý** hoặc **bộ mã hóa nhận biết thuộc tính**, đạt được độ phong phú cao hơn bằng cách nhúng thông tin đặc trưng cùng với cấu trúc đồ thị. #### Độ sâu, kích thước và độ phong phú: Một góc nhìn kết hợp Tóm tắt: - **Độ sâu** của không gian nhúng (được biểu thị bằng các lớp tổng hợp hoặc các lớp mô hình) xác định ngữ cảnh của mỗi nhúng nút trong đồ thị có phạm vi bao xa. - **Kích thước** (số chiều $d$) lý tưởng nên cân bằng giữa hiệu quả tính toán với nhu cầu biểu diễn độ phức tạp cấu trúc của đồ thị. - **Độ phong phú** đề cập đến khả năng của không gian nhúng trong việc mã hóa các mối quan hệ đa dạng, vai trò cấu trúc và các mẫu bậc cao, cùng với thông tin dựa trên thuộc tính khi có thể áp dụng. Độ phong phú có thể được đánh giá định lượng bằng cách đo lường **chất lượng phân cụm**, **độ chính xác phân loại** trong các tác vụ tiếp theo hoặc **tính nhất quán tôpô** (ví dụ: bảo toàn khoảng cách đường đi ngắn nhất hoặc cấu trúc cộng đồng). Đối với các mạng có số chiều cao, giàu thông tin (chẳng hạn như mạng xã hội hoặc mạng sinh học), không gian nhúng có độ sâu cao, số chiều lớn và các cơ chế tổng hợp lân cận và đặc trưng được điều chỉnh cẩn thận sẽ cung cấp các biểu diễn mạnh mẽ và "phong phú" nhất, cho phép phân tích phức tạp tiếp theo như phân loại nút, phát hiện cộng đồng và dự đoán liên kết. ## III. Mã hóa nút (Node encoding) $\mathsf{ENC}(V, E_{\text{neigh}})$ **Mã hóa nút** $\mathsf{ENC}(V, E_{\text{neigh}})$ là một biểu diễn nắm bắt thông tin về mỗi đỉnh $v \in V$ và các lân cận$E_{\text{neigh}}$ của nó, tức là tập hợp các cạnh kết nối $v$ với các nút lân cận. Mã hóa $\mathsf{ENC}(v)$ được định hình bằng cách tổng hợp các đặc trưng từ các nút và cạnh lân cận, tạo ra một biểu diễn vectơ tích hợp cấu trúc đồ thị cục bộ với các thuộc tính nút. Chúng ta hãy phân tích các thành phần chính của mã hóa này, hình dạng của nó và các xu hướng như độ thưa thớt. #### 1. Hình dạng của mã hóa nút $\mathsf{ENC}(V, E_{\text{neigh}})$ **Hình dạng** của $\mathsf{ENC}(v)$, biểu diễn vectơ được mã hóa của nút $v$, phụ thuộc vào một số yếu tố: - **Số chiều của không gian nhúng** ($d$): Thông thường, $\mathsf{ENC}(v) \in \mathbb{R}^d$, trong đó $d$ là số chiều nhúng được chọn cho mô hình. Ví dụ: - Trong các nhúng đơn giản hơn, số chiều thấp, $d$ có thể nhỏ tới 10–50. - Đối với các mô hình đồ thị sâu, đặc biệt là trong các mạng phức tạp, $d$ có thể dao động từ 128 đến 512 hoặc thậm chí cao hơn, vì số chiều lớn hơn giúp nắm bắt các cấu trúc phức tạp hơn. - **Tổng hợp phân lớp**: Trong các phương pháp như Mạng nơ-ron đồ thị (GNN), mã hóa nút thường được cập nhật lặp đi lặp lại trên nhiều lớp, trong đó mỗi lớp tổng hợp thông tin từ các nút ở khoảng cách ngày càng lớn hơn. Nếu GNN có $K$ lớp, thì mã hóa cuối cùng $\mathsf{ENC}(v)$ biểu thị thông tin được tổng hợp từ các nút cách xa tới $K$ - bước nhảy. Số chiều $d$ vẫn cố định trên các lớp, nhưng nội dung của $\mathsf{ENC}(v)$ trở nên phong phú hơn dần với mỗi lớp. Ví dụ: nếu sử dụng **Mạng tích chập đồ thị (GCN)**, mã hóa cho mỗi nút $v$ sau $K$ lớp có thể trông giống như sau: $$ \mathsf{ENC}(v) = f\left(\sigma\left(W^{(K)} \cdots \sigma\left(W^{(1)} X_v^{(1)} \right)\right)\right) $$ trong đó $W^{(k)}$ là trọng số đã học,$\sigma$là hàm kích hoạt và $X_v^{(1)}$ biểu thị các đặc trưng nút ban đầu. #### 2. Các thành phần của mã hóa **Mã hóa nút** $\mathsf{ENC}(v)$ thường nhận một số loại thông tin từ chính nút đó và các nút lân cận của nó. Các thành phần phổ biến bao gồm: - **Đặc trưng nút**: Mỗi nút$v$thường có các đặc trưng được liên kết, được biểu thị bằng vectơ đặc trưng $X_v$ (ví dụ: nhân khẩu học cho người dùng trong mạng xã hội, thuộc tính phân tử cho các nguyên tử trong phân tử). Vectơ đặc trưng này thường là đầu vào ban đầu cho quá trình mã hóa và được biến đổi qua các lớp để làm phong phú thêm biểu diễn. - **Tổng hợp lân cận**: Mã hóa kết hợp thông tin tổng hợp từ các nút lân cận. Tổng hợp này có thể được tính toán thông qua các chiến lược khác nhau: - **Trung bình**: Tính trung bình các đặc trưng của các nút lân cận, điều này cho biết cảm nhận chung về vùng lân cận đồng thời đơn giản và hiệu quả. - **Tổng hoặc gộp**: Cộng hoặc sử dụng gộp max/trung bình trên các đặc trưng lân cận, có thể nắm bắt thông tin biểu cảm hoặc đại diện hơn. - **Cơ chế chú ý**: Trong một số mô hình nâng cao (ví dụ: Mạng chú ý đồ thị, GAT), tổng hợp được tính trọng số bằng điểm chú ý, cho phép mã hóa ưu tiên các nút lân cận nhất định dựa trên mức độ liên quan của chúng. - **Đặc trưng cạnh**: Nếu các cạnh có các đặc trưng được liên kết (ví dụ: trọng số, loại hoặc mối quan hệ), thì những đặc trưng này cũng có thể được bao gồm trong mã hóa. Các mô hình như **GCN quan hệ** (R-GCN) và **Mạng chú ý đồ thị (GAT)** có thể sử dụng các đặc trưng cạnh này để sửa đổi cách tổng hợp các đặc trưng nút lân cận. #### 3. Thuộc tính của mã hóa: Độ thưa thớt và nội dung thông tin Mã hóa $\mathsf{ENC}(v)$ có một số thuộc tính đáng chú ý phụ thuộc vào cấu trúc và đặc điểm của đồ thị: - **Xu hướng thưa thớt**: Trong nhiều đồ thị trong thế giới thực, đặc biệt là các mạng quy mô lớn, các kết nối nút là **thưa thớt** (tức là mỗi nút kết nối với một tập hợp con nhỏ các nút khác so với tổng số). Độ thưa thớt này thường mở rộng đến mã hóa, đặc biệt là trong các mô hình sử dụng biểu diễn thưa thớt (ví dụ: ma trận kề thưa thớt). Trong những trường hợp như vậy: - **Tổng hợp thưa thớt**: Tổng hợp các đặc trưng từ vùng lân cận thưa thớt dẫn đến các vectơ mã hóa có thể chứa hầu hết các số 0 hoặc giá trị thấp cho các chiều không được kết nối. - **Độ thưa thớt đặc trưng**: Nếu bản thân các đặc trưng nút là thưa thớt (ví dụ: thuộc tính được mã hóa nhị phân hoặc một nóng), thì $\mathsf{ENC}(v)$ kết quả cũng có thể biểu hiện độ thưa thớt, đặc biệt là sau các lớp tổng hợp duy trì hoặc khuếch đại các đặc trưng thưa thớt này. - **Thông tin cục bộ**: Trong GNN nông (với số lượng lớp nhỏ), mã hóa $\mathsf{ENC}(v)$ chủ yếu phản ánh thông tin về vùng lân cận ngay lập tức của nút. Biểu diễn cục bộ này có hiệu quả đối với các tác vụ mà ngữ cảnh cục bộ (ví dụ: lân cận bậc nhất hoặc bậc hai) là phù hợp nhất. - **Lan truyền các thuộc tính cấu trúc**: Với các mạng sâu hơn (nhiều lớp hơn), mã hóa tích hợp thông tin từ một phần lớn hơn của đồ thị, nắm bắt không chỉ cấu trúc cục bộ mà còn nhiều vai trò toàn cục hoặc cấu trúc hơn (ví dụ: tính trung tâm, phân cụm trong một cộng đồng). Điều này quan trọng đối với các tác vụ yêu cầu hiểu các cấu trúc đồ thị rộng hơn. - **Độ phong phú đặc trưng so với giảm số chiều**: Trong khi số chiều $d$ của $\mathsf{ENC}(v)$ có thể vẫn cố định, **độ phong phú** của mã hóa tăng lên với mỗi lớp tổng hợp khi kết hợp nhiều thông tin lân cận đa dạng hơn. Tuy nhiên, để duy trì hiệu quả tính toán, một số GNN sử dụng các kỹ thuật giảm số chiều trong các lớp, giảm kích thước đặc trưng đồng thời bảo toàn các đặc điểm cấu trúc chính. #### Ví dụ về hình dạng và thuộc tính trong các mô hình đồ thị cụ thể Chúng ta hãy xem xét một số mô hình cụ thể và cách chúng định hình $\mathsf{ENC}(v)$: 1. **Mạng tích chập đồ thị (GCN)**: - GCN sử dụng trung bình hoặc tổng trọng số để tổng hợp các đặc trưng nút lân cận. Sau mỗi lớp, hình dạng của $\mathsf{ENC}(v)$ được kiểm soát bởi số chiều nhúng$d$đã chọn, với mỗi lớp thêm thông tin lân cận. - Các vectơ được mã hóa có xu hướng giữ lại các mẫu cấu trúc dày đặc, mặc dù độ thưa thớt có thể xuất hiện nếu các đặc trưng ban đầu hoặc cấu trúc kề là thưa thớt. 2. **Mạng chú ý đồ thị Graph Attention Networks (GAT)**: - Trong GAT, hình dạng mã hóa $\mathsf{ENC}(v)$ vẫn ở trong $\mathbb{R}^d$, nhưng mỗi phần tử trong vectơ được tính trọng số bằng điểm chú ý được áp dụng cho các đặc trưng lân cận. Điều này cho phép mã hóa phong phú hơn, thường thưa thớt hơn, vì các nút lân cận ít liên quan hơn bị giảm trọng số hoặc bỏ qua. - Mã hóa có thể thể hiện độ thưa thớt có chọn lọc dựa trên cơ chế chú ý, trong đó chỉ một tập hợp con thông tin lân cận đóng góp đáng kể vào $\mathsf{ENC}(v)$. - **Tính toán điểm chú ý:** GAT tính toán điểm chú ý giữa mỗi cặp nút dựa trên đặc trưng của chúng và đặc trưng của cạnh nối chúng. Điểm chú ý này phản ánh mức độ quan trọng của nút lân cận đối với nút hiện tại. - **Tổng hợp lân cận dựa trên chú ý:** GAT sử dụng điểm chú ý để tính trọng số cho đặc trưng của các nút lân cận trước khi tổng hợp chúng. - **Ví dụ:** Trong đồ thị tri thức, nếu một cạnh có trọng số cao hơn, GAT sẽ gán điểm chú ý cao hơn cho nút lân cận được kết nối bởi cạnh đó, cho phép mô hình tập trung vào các nút lân cận quan trọng hơn. Công thức tính điểm chú ý trong GAT có thể được viết như sau: $$ e_{ij} = \alpha \left( \mathbf{W} h_i , \mathbf{W} h_j, \mathbf{e}_{ij} \right) $$ Trong đó: - $e_{ij}$ là điểm chú ý giữa nút i và nút j. - $α$ là hàm tính điểm chú ý (ví dụ: một lớp perceptron một lớp). - $W$ là ma trận trọng số được chia sẻ. - $h_i$ và $h_j$ là mã hóa của nút i và nút j. - $e_{ij}$ là đặc trưng của cạnh nối nút i và nút j. Sau khi tính toán điểm chú ý, GAT chuẩn hóa chúng bằng hàm softmax và sử dụng chúng để tính trọng số cho đặc trưng của các nút lân cận: $$ \alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}_i} \exp(e_{ik})} $$ Cuối cùng, GAT tổng hợp thông tin từ các nút lân cận dựa trên trọng số chú ý: $$ h_i^{(l+1)} = \sigma \left( \sum_{j \in \mathcal{N}_i} \alpha_{ij} \mathbf{W} h_j^{(l)} \right) $$ Tóm lại, cả R-GCN và GAT đều cho phép tích hợp đặc trưng cạnh vào quá trình mã hóa nút. R-GCN sử dụng ma trận trọng số riêng biệt cho từng loại quan hệ, trong khi GAT sử dụng cơ chế chú ý để tính trọng số cho đặc trưng của các nút lân cận dựa trên đặc trưng cạnh. Bằng cách kết hợp đặc trưng cạnh, các mô hình này có thể học các biểu diễn phong phú hơn và nắm bắt các sắc thái quan trọng trong cấu trúc đồ thị. 3. **Mạng tích chập đồ thị quan hệ Relational Graph Convolutional Networks (R-GCN)**: R-GCN xử lý các đồ thị có nhiều loại quan hệ (tức là các loại cạnh khác nhau) bằng cách sử dụng các phép biến đổi cụ thể cho từng loại quan hệ trong quá trình tổng hợp lân cận. - **Ma trận trọng số riêng biệt:** Đối với mỗi loại quan hệ $r$, R-GCN sử dụng một ma trận trọng số riêng biệt $W_r$. Điều này cho phép mô hình học các mẫu khác nhau cho các loại quan hệ khác nhau. - **Tổng hợp lân cận dựa trên quan hệ:** Khi tổng hợp thông tin từ các nút lân cận, R-GCN áp dụng ma trận trọng số tương ứng với loại quan hệ của cạnh nối nút hiện tại với nút lân cận đó. - **Ví dụ:** Trong mạng xã hội, nếu có các loại quan hệ "bạn bè", "đồng nghiệp" và "gia đình", R-GCN sẽ sử dụng ba ma trận trọng số khác nhau để tổng hợp thông tin từ các nút lân cận thuộc mỗi loại quan hệ. Công thức cập nhật mã hóa nút trong R-GCN có thể được viết như sau: $$ h_i^{(l+1)} = \sigma \left( \sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_i^r} \frac{1}{c_{i,r}} W_r^{(l)} h_j^{(l)} + W_0^{(l)} h_i^{(l)} \right) $$ Trong đó: - $h_i(l)$ là mã hóa của nút i tại lớp l. - $R$ là tập hợp các loại quan hệ. - $N_i^r$ là tập hợp các nút lân cận của nút i thông qua quan hệ r. - $c{i,r}$ là hằng số chuẩn hóa (ví dụ: bậc của nút i đối với quan hệ r). - $W_r(l)$là ma trận trọng số cho quan hệ r tại lớp l. - W$_0(l)$là ma trận trọng số cho tự kết nối tại lớp l. - $σ$ là hàm kích hoạt phi tuyến. #### Tóm tắt - **Hình dạng** của $\mathsf{ENC}(v)$ chủ yếu được xác định bởi số chiều nhúng $d$, được chọn dựa trên nhiệm vụ và độ phức tạp của đồ thị. Hình dạng này nhất quán trên các nút trong một lớp nhất định nhưng có thể thay đổi trên các lớp trong các mô hình sâu. - **Các thành phần**: Đặc trưng nút, tổng hợp lân cận và đặc trưng cạnh đều góp phần vào $\mathsf{ENC}(v)$, với các hàm tổng hợp như trung bình, tổng và chú ý tinh chỉnh mã hóa. - **Thuộc tính**: - **Độ thưa thớt(Sparsity)** thường phát sinh trong đồ thị thưa thớt hoặc khi sử dụng các đặc trưng ban đầu thưa thớt. - **Cục bộ so với toàn cục(Local vs. Global)**: Mã hóa có thể dao động từ thông tin cục bộ đến nhận thức toàn cục tùy thuộc vào độ sâu của tổng hợp. - **Độ phong phú(Richness)** là một hàm của độ sâu lân cận và sự đa dạng đặc trưng, với mã hóa phong phú hơn nắm bắt nhiều vai trò cấu trúc và thông tin cấp cộng đồng hơn. Thông qua tổng hợp trên nhiều lớp, mã hóa$\mathsf{ENC}(v)$cuối cùng trở thành một biểu diễn nhỏ gọn nhưng biểu cảm của cả các thuộc tính nội tại của nút và ngữ cảnh cấu trúc của nó trong đồ thị. ## IV. Độ thưa thớt kết nối (Connectivity sparsity) trong đồ thị $G(V, E)$ Trong bối cảnh đồ thị $G(V, E)$, **độ thưa thớt kết nối** của các nút trung bình định lượng mức độ thưa thớt kết nối của đồ thị. Số liệu này giúp hiểu số lượng cạnh trung bình trên mỗi nút so với số lượng kết nối tối đa có thể có và cung cấp thông tin chi tiết về mật độ hoặc độ thưa thớt của cấu trúc đồ thị. Dưới đây là cách chúng tôi phân tích khái niệm này chính xác hơn: #### 1. Định nghĩa độ thưa thớt kết nối Độ thưa thớt kết nối có thể được định nghĩa chính thức là tỷ lệ giữa số lượng cạnh thực tế với số lượng cạnh tối đa có thể có, tập trung vào **bậc trung bình** hoặc **kết nối trung bình** trên mỗi nút. Đối với **đồ thị vô hướng** $G(V, E)$, số lượng cạnh tối đa có thể có là $\binom{|V|}{2} = \frac{|V|(|V|-1)}{2}$, trong khi đối với **đồ thị có hướng**, đó là $|V|(|V|-1)$ vì mỗi nút có thể có một cạnh có hướng đến mọi nút khác. Do đó, **độ thưa thớt (Connectivity Sparsity)** kết nối của $G$ có thể được tính bằng: $$ \text{Connectivity Sparsity} = 1 - \frac{2|E|}{|V|(|V|-1)} $$ cho đồ thị vô hướng. hoặc $$ \text{Connectivity Sparsity} = 1 - \frac{|E|}{|V|(|V|-1)} $$ cho đồ thị có hướng. Thước đo này cho giá trị từ 0 đến 1, trong đó giá trị gần bằng 1 cho biết độ thưa thớt cao (ít kết nối so với mức tối đa có thể có) và giá trị gần bằng 0 cho biết đồ thị dày đặc. #### 2. Bậc nút trung bình Một cách khác để đo lường độ thưa thớt là thông qua **bậc trung bình(Average Degree)** của các nút, là số lượng kết nối trung bình trên mỗi nút: $$ \text{Average Degree} = \frac{2|E|}{|V|} $$ cho đồ thị vô hướng, hoặc $$ \text{Average Degree} = \frac{|E|}{|V|} $$ cho đồ thị có hướng. **Bậc** của nút $v$, được ký hiệu là $\deg(v)$, là số lượng cạnh được kết nối với $v$. Đối với đồ thị thưa thớt, bậc trung bình thường thấp hơn nhiều so với$|V| - 1$, số lượng kết nối có thể có trên mỗi nút trong đồ thị đầy đủ. #### 3. Diễn giải độ thưa thớt kết nối Độ thưa thớt kết nối cho chúng ta biết **cụm cục bộ** hoặc **kết nối lỏng lẻo** của đồ thị trung bình như thế nào. Đồ thị thưa thớt có xu hướng thể hiện: - **Phân cụm cục bộ(Localized clustering)**: Các nút có ít kết nối, dẫn đến các cụm nhỏ, biệt lập thay vì cấu trúc được kết nối đầy đủ. - **Đường kính lớn và đường dẫn dài hơn(High diameter and longer paths)**: Với ít kết nối hơn, các đường dẫn giữa hai nút ngẫu nhiên có xu hướng dài hơn, làm tăng **độ dài đường dẫn ngắn nhất** trung bình. Trong các ứng dụng học máy, độ thưa thớt kết nối có thể ảnh hưởng đến: - **Truyền tin trong GNN**: Đồ thị thưa thớt có thể yêu cầu nhiều lớp hơn trong GNN để nắm bắt đủ thông tin trên các nút ở xa. - **Hiệu quả tính toán**: Đồ thị thưa thớt thường hiệu quả về mặt tính toán để xử lý do ít cạnh hơn, làm cho chúng phù hợp để lưu trữ và tính toán bằng cách sử dụng biểu diễn ma trận thưa thớt. #### 4. Ví dụ tính toán Để minh họa, hãy xem xét một đồ thị có nút $|V| = 1000$ và cạnh $|E| = 3000$ : - **Độ thưa thớt vô hướng**: Đối với đồ thị vô hướng, $$ \text{Connectivity Sparsity} = 1 - \frac{2 \cdot 3000}{1000 \times 999} = 1 - \frac{6000}{999000} \approx 0.994$$ Giá trị gần 1 này cho biết đồ thị rất thưa thớt. - **Bậc trung bình**: Bậc trung bình của mỗi nút trong đồ thị vô hướng này sẽ là: $$ \text{Average Degree} = \frac{2 \cdot 3000}{1000} =6$$ Với trung bình 6 kết nối trên mỗi nút trong số 999 kết nối có thể có, đồ thị này có mật độ kết nối rất thấp, điển hình của mạng thưa thớt. #### 5. Ứng dụng trong đồ thị thế giới thực Các đồ thị trong thế giới thực, như mạng xã hội hoặc mạng sinh học, thường thể hiện độ thưa thớt kết nối cao do **hiện tượng thế giới nhỏ** và **phân phối bậc theo luật lũy thừa**: - **Mạng thế giới nhỏ**: Các mạng này có phân cụm cục bộ cao nhưng tương đối ít cạnh kết nối các phần ở xa của đồ thị, dẫn đến các vùng lân cận cục bộ thưa thớt nhưng được kết nối với nhau cao. - **Mạng không có quy mô**: Trong các mạng này, một số nút (trung tâm) có bậc cao, nhưng hầu hết các nút có bậc thấp, góp phần vào độ thưa thớt chung. #### Tóm tắt - **Độ thưa thớt kết nối** đo lường mức độ thưa thớt kết nối của đồ thị, với giá trị gần bằng 1 cho biết đồ thị thưa thớt. - **Bậc trung bình** cung cấp góc nhìn cấp nút về độ thưa thớt. - Đồ thị thưa thớt phổ biến trong các mạng trong thế giới thực, thường dựa vào các biểu diễn thưa thớt hiệu quả để có lợi thế về tính toán. Hiểu biết về độ thưa thớt kết nối là rất quan trọng để thiết kế các mô hình học máy có thể thích ứng với cấu trúc độc đáo của đồ thị thưa thớt, đặc biệt là trong Mạng nơ-ron đồ thị, nơi sử dụng các thuật toán truyền tin. ## V. Quan hệ thứ tự và vị trí trong học máy dựa trên đồ thị Trong học máy dựa trên đồ thị, đặc biệt là trong các lĩnh vực như **Xử lý ngôn ngữ tự nhiên (NLP)**, các quan hệ như **thứ tự** và **quan hệ vị trí** đóng vai trò quan trọng trong việc định hình mã hóa đồ thị và giải quyết vấn đề. Các quan hệ này xác định kết nối và cấu trúc của các nút, có thể ảnh hưởng đến cách thông tin được tổng hợp, mã hóa và cuối cùng được mô hình diễn giải. Chúng ta hãy khám phá các loại quan hệ và tác động của chúng đối với mã hóa đồ thị và hiệu suất mô hình. #### 1. Các loại quan hệ trong mã hóa đồ thị ##### A. Quan hệ thứ tự (Order relation) **Quan hệ thứ tự** giữa các nút giới thiệu một cấu trúc tuần tự, cần thiết cho các ngữ cảnh mà chuỗi các phần tử mang ý nghĩa quan trọng (ví dụ: các từ trong câu). Quan hệ thứ tự đặc biệt phù hợp trong các tác vụ NLP, trong đó thứ tự xuất hiện của các từ ảnh hưởng đến ý nghĩa của câu. - **Định nghĩa**: Quan hệ thứ tự ngụ ý rằng có một **thứ tự ưu tiên** được xác định giữa các nút, trong đó$v_i$đứng trước $v_j$ (ví dụ: $v_i \rightarrow v_j$ biểu thị rằng $v_i$ đứng trước $v_j$). - **Ví dụ trong NLP**: Trong đồ thị câu, trong đó mỗi từ hoặc mã thông báo là một nút, quan hệ thứ tự sẽ phản ánh trình tự từ tự nhiên. Ví dụ: trong "Con mèo ngồi", "Con" sẽ được sắp xếp trước "mèo" và "mèo" trước "ngồi". ##### B. Quan hệ vị trí (Positional relation) **Quan hệ vị trí** biểu thị vị trí của nút trong một cấu trúc rộng hơn, độc lập với thứ tự tuần tự của nó. Khái niệm này phổ biến trong các cấu trúc giống như lưới (ví dụ: hình ảnh 2D) và ngày càng được sử dụng trong NLP để nắm bắt ngữ cảnh dựa trên vị trí từ hoặc khoảng cách từ một điểm tiêu cự. - **Định nghĩa**: Quan hệ vị trí chỉ định vị trí của nút so với các nút khác, thường dựa trên vị trí không gian hoặc cú pháp. Không giống như quan hệ thứ tự, quan hệ vị trí không ngụ ý hướng mà là ngữ cảnh không gian. - **Ví dụ trong NLP**: Trong các mô hình dựa trên biến đổi như BERT, **mã hóa vị trí** được thêm vào mỗi nhúng mã thông báo để kết hợp thông tin vị trí, cho phép mô hình phân biệt giữa các mã thông báo giống hệt nhau dựa trên vị trí của chúng trong câu. #### 2. Quan hệ thứ tự và vị trí ảnh hưởng đến mã hóa như thế nào Quan hệ thứ tự và vị trí ảnh hưởng đáng kể đến **mã hóa nút $\mathsf{ENC}(v)$** theo những cách sau: ##### A. Tác động của quan hệ thứ tự đối với mã hóa Khi mã hóa các nút có quan hệ thứ tự, các mô hình phải tôn trọng thông tin chuỗi, đảm bảo rằng mã hóa của mỗi nút kết hợp thông tin về vị trí của nó trong chuỗi. - **Tổng hợp tuần tự**: Trong Mạng nơ-ron đồ thị (GNN), thứ tự có thể quyết định **chuỗi truyền tin**. Ví dụ: trong **GNN hồi quy** hoặc **Mạng hồi quy đồ thị (GRN)**, các nút truyền tin nhắn đến các nút kế nhiệm của chúng theo một thứ tự cụ thể, bảo toàn cấu trúc chuỗi ban đầu. - **Mã hóa thời gian hoặc hướng**: Trong đồ thị có hướng với quan hệ thứ tự, nhúng nút có thể nhấn mạnh các phụ thuộc, cho phép các mô hình tiếp theo hiểu các phụ thuộc dựa trên thời gian hoặc tuần tự. Ví dụ: - Trong NLP, chuỗi có thứ tự giúp các mô hình hiểu cú pháp, trong đó các mẫu nhất định như "danh từ theo sau là động từ" mang ý nghĩa quan trọng. Mã hóa nắm bắt thứ tự này có thể biểu diễn tốt hơn các phụ thuộc ngôn ngữ. - **Ứng dụng**: Quan hệ thứ tự rất quan trọng trong các tác vụ như **dự đoán chuỗi**, **mô hình hóa ngôn ngữ** và **dịch máy**. Ví dụ: trong tác vụ dịch máy, việc nắm bắt thứ tự của các từ trong câu nguồn là rất quan trọng để tạo ra các bản dịch chính xác về mặt ngữ pháp và ngữ nghĩa. ##### B. Tác động của quan hệ vị trí đối với mã hóa Quan hệ vị trí thường nhấn mạnh ngữ cảnh không gian hoặc vị trí tương đối hơn là trình tự nghiêm ngặt. Điều này có thể rất quan trọng trong các tác vụ mà việc hiểu khoảng cách tương đối hoặc vị trí là quan trọng. - **Nhúng thông tin vị trí**: Trong biến đổi, mỗi mã thông báo được gán một **nhúng vị trí** được thêm vào nhúng ngữ nghĩa của nó, mã hóa vị trí của nó trong câu. Điều này giúp duy trì sự sắp xếp không gian mà không cần dựa vào một thứ tự nghiêm ngặt. - **Tổng hợp dựa trên sự chú ý**: Quan hệ vị trí cũng được mã hóa bằng cách sử dụng **cơ chế chú ý**, đặc biệt là trong các mô hình biến đổi. Ở đây, các lớp tự chú ý sử dụng mã hóa vị trí để xác định tầm quan trọng của mỗi mã thông báo so với các mã thông báo khác, cho phép mô hình nắm bắt các phụ thuộc tầm xa. - **Ứng dụng**: Quan hệ vị trí có lợi cho các tác vụ mà độ dài ngữ cảnh thay đổi (ví dụ: **phân loại tài liệu** hoặc **trả lời câu hỏi**), vì chúng cho phép mô hình giữ lại ngữ cảnh dựa trên sự gần gũi hơn là thứ tự cố định. Ví dụ: trong **trả lời câu hỏi**, việc biết vị trí của câu hỏi so với câu trả lời tiềm năng trong văn bản có thể cải thiện độ chính xác. #### 3. Ý nghĩa của quan hệ thứ tự và vị trí đối với học tập dựa trên đồ thị ##### A. Ảnh hưởng đến độ phức tạp và khả năng diễn giải của mô hình Quan hệ thứ tự và vị trí thường làm tăng độ phức tạp của mô hình nhưng cũng có thể tăng cường khả năng diễn giải: - **Độ phức tạp**: Mã hóa thứ tự và vị trí yêu cầu các tham số bổ sung, như đã thấy với mã hóa vị trí trong biến đổi hoặc các cạnh có hướng trong GNN dựa trên RNN. Điều này làm tăng độ phức tạp của mô hình nhưng có thể dẫn đến hiệu suất tốt hơn trên các tác vụ yêu cầu nhận thức về chuỗi hoặc vị trí. - **Khả năng diễn giải**: Quan hệ vị trí và thứ tự làm cho quá trình ra quyết định của mô hình dễ hiểu hơn, đặc biệt là trong NLP. Ví dụ: trong phân tích cú pháp phụ thuộc, mã hóa tôn trọng thứ tự có thể giúp xác định cấu trúc cú pháp rõ ràng hơn, hỗ trợ khả năng diễn giải. ##### B. Tăng tính biểu cảm trong mã hóa Các đồ thị nắm bắt quan hệ thứ tự và vị trí thường **biểu cảm hơn** và có khả năng biểu diễn các phụ thuộc phức tạp: - **Phụ thuộc tầm xa(Long-Range Dependencies)**: Quan hệ thứ tự trong các mô hình tuần tự nắm bắt **phụ thuộc tầm xa**, cho phép các nút cách xa nhau trong một chuỗi ảnh hưởng lẫn nhau trong mã hóa. Ví dụ: trong phân tích tình cảm, các từ ở xa nhau trong câu có thể sửa đổi ý nghĩa của nhau, điều mà mã hóa có thứ tự có thể nắm bắt được. - **Mối quan hệ ngữ cảnh**: Mã hóa vị trí cho phép các mô hình kết hợp ngữ cảnh rộng hơn mà không cần kết nối rõ ràng, điều cần thiết trong các tài liệu lớn hoặc các cuộc trò chuyện dài, nơi ngữ cảnh cục bộ cần được bảo toàn trong một cấu trúc lớn hơn. ##### C. Thích ứng thuật toán học tập Các thuật toán phải thích ứng để xử lý các yêu cầu cụ thể do quan hệ thứ tự và vị trí đưa ra. Ví dụ: - **Lan truyền ngược tuần tự**: Trong các mô hình có quan hệ thứ tự (ví dụ: GNN dựa trên RNN), lan truyền ngược xảy ra tuần tự để tôn trọng các phụ thuộc có thứ tự, yêu cầu mô hình tính toán gradient từng bước. - **Trọng số vị trí trong cơ chế chú ý**: Trong các mô hình như biến đổi, **các lớp tự chú ý** được sửa đổi để bao gồm mã hóa vị trí, cho phép các nút được tính trọng số dựa trên vị trí của chúng trong đầu vào thay vì độ kề của chúng trong đồ thị. #### 4. Thách thức và hạn chế Mặc dù quan hệ thứ tự và vị trí làm phong phú thêm mã hóa, chúng cũng đưa ra những thách thức: - **Khả năng mở rộng**: Mã hóa cả quan hệ thứ tự và vị trí làm tăng số chiều và yêu cầu tính toán, có thể dẫn đến sự kém hiệu quả trong đồ thị quy mô lớn hoặc các tác vụ NLP với chuỗi dài. - **Rủi ro Overfitting**: Với thông tin vị trí và thứ tự, mô hình có thể quá khớp với các mẫu cụ thể, đặc biệt nếu dữ liệu huấn luyện lặp lại hoặc sai lệch. Điều này có thể cản trở khả năng khái quát hóa, đặc biệt là trên các chuỗi chưa nhìn thấy hoặc cấu trúc đồ thị mới. - **Độ phức tạp trong mã hóa thông tin thời gian**: Đối với các tác vụ liên quan đến thứ tự thời gian (ví dụ: dự đoán sự kiện), việc nắm bắt thời gian của các sự kiện yêu cầu điều chỉnh bổ sung cho nhúng, làm cho mã hóa cả thứ tự và vị trí trở nên phức tạp hơn. #### Tóm tắt - **Quan hệ thứ tự** thêm một phụ thuộc có hướng hoặc tuần tự, cho phép mô hình mã hóa và tôn trọng luồng thông tin tự nhiên. Chúng rất quan trọng trong các tác vụ như mô hình hóa ngôn ngữ, phân tích tình cảm và dự đoán chuỗi, trong đó thứ tự từ ảnh hưởng đến ý nghĩa. - **Quan hệ vị trí** cung cấp thông tin không gian hoặc ngữ cảnh, thường hữu ích trong các tác vụ phi tuần tự hoặc nơi định vị tương đối là điều cần thiết để nắm bắt ngữ cảnh. Chúng được sử dụng nhiều trong các mô hình NLP dựa trên biến đổi, trong đó mã hóa vị trí giúp duy trì mức độ liên quan theo ngữ cảnh của các từ mà không cần phụ thuộc nghiêm ngặt vào thứ tự. - **Tác động đến mã hóa**: Cả hai quan hệ đều ảnh hưởng đến cách nhúng được tổng hợp, số chiều của chúng và độ phức tạp của các tác vụ tiếp theo. Các mô hình tính đến các quan hệ này có xu hướng biểu cảm hơn và có khả năng nắm bắt các phụ thuộc tinh tế. Các quan hệ này, khi được mã hóa chính xác, có thể cải thiện đáng kể khả năng hiểu cấu trúc dữ liệu của mô hình, làm cho nó mạnh mẽ hơn, nhận biết ngữ cảnh hơn và phù hợp để nắm bắt các thuộc tính độc đáo của đồ thị, đặc biệt là trong các tác vụ NLP phức tạp. ## VI. Đánh giá mô hình đồ thị dựa trên nguyên tắc truyền tin Để phân tích các mô hình dựa trên đồ thị, đặc biệt là **Mạng nơ-ron đồ thị (GNN)**, chúng ta có thể đánh giá hiệu suất bằng cách kiểm tra các thành phần chính ảnh hưởng trực tiếp đến cách thông tin được xử lý và học trong mô hình. Chúng ta hãy thảo luận về từng khía cạnh của việc đánh giá: #### 1. Sử dụng nguyên tắc truyền tin trong GNN Truyền tin là một phép toán cơ bản trong GNN cho phép mỗi nút tổng hợp thông tin từ các nút lân cận của nó một cách lặp đi lặp lại. Quá trình lặp đi lặp lại này cho phép các nút thu thập ngữ cảnh từ vùng lân cận cục bộ của chúng và cuối cùng nắm bắt các phụ thuộc bậc cao hơn trong cấu trúc đồ thị. Việc đánh giá một mô hình bằng cách sử dụng nguyên tắc truyền tin bao gồm ba câu hỏi chính: ___ ##### 1.1 Độ sâu của vùng lân cận xung quanh $v \in V$ là bao nhiêu? **Độ sâu của vùng lân cận** đề cập đến phạm vi tiếp nhận của một nút - về cơ bản, có bao nhiêu "bước nhảy" của các nút lân cận đóng góp thông tin cho biểu diễn cuối cùng của nút. - **Định nghĩa**: Trong GNN, độ sâu $K$ biểu thị số lớp hoặc số lần lặp của truyền tin, trong đó mỗi lớp tổng hợp thông tin từ các nút lân cận ở khoảng cách tương ứng. Ví dụ: - $K = 1$ nắm bắt thông tin từ các nút lân cận trực tiếp. - $K = 2$ nắm bắt thông tin từ các nút lân cận cách xa tối đa hai bước nhảy, kết hợp cả các nút lân cận trực tiếp và các nút lân cận của chúng. - **Tác động đến mã hóa**: - **Vùng lân cận nông** ( $K$ nhỏ): Nếu độ sâu bị giới hạn trong 1 hoặc 2 bước nhảy, mã hóa nút chủ yếu phản ánh thông tin cục bộ và tốt nhất để nắm bắt **cấu trúc vi mô** như cụm, cạnh hoặc mô-típ gần nút. - **Vùng lân cận sâu** ( $K$ lớn ): Độ sâu lớn hơn nắm bắt các cấu trúc **toàn cục** rộng hơn, hữu ích cho các tác vụ mà các phụ thuộc tầm xa quan trọng, chẳng hạn như phát hiện cộng đồng hoặc phân loại phân cấp. - **Đánh đổi**: Tăng độ sâu có thể dẫn đến **vấn đề làm mịn quá mức** - khi $K$ tăng, các nút có xu hướng có biểu diễn tương tự nhau, đặc biệt là trong đồ thị dày đặc, điều này có thể làm giảm khả năng phân biệt các nút ở các phần khác nhau của đồ thị của mô hình. - **Cân nhắc đánh giá**: Độ sâu được chọn phải phù hợp với yêu cầu nhiệm vụ: - Đối với các tác vụ cục bộ như dự đoán liên kết, vùng lân cận nông (ví dụ: $K = 1$ hoặc $2$ ) thường là đủ. - Đối với các tác vụ toàn cục, chẳng hạn như phân loại nút trên đồ thị có cấu trúc phân cấp, các lớp sâu hơn có thể cần thiết, nhưng chỉ khi chúng tránh được làm mịn quá mức. ___ ##### 1.2 Bối cảnh của người nhận dữ liệu là gì? **Bối cảnh(landscape)** của người nhận dữ liệu đề cập đến ngữ cảnh dựa trên cấu trúc và thuộc tính mà một nút hoặc đồ thị con nhận được thông tin trong quá trình truyền tin. Bối cảnh này bị ảnh hưởng bởi cả **tôpô đồ thị** và **thuộc tính nút**. - **Tôpô đồ thị**: - Cấu trúc xung quanh mỗi nút - chẳng hạn như nó nằm trong một cụm dày đặc hay trên một vùng ngoại vi thưa thớt - ảnh hưởng đến lượng thông tin mà nó nhận được từ các nút lân cận của nó. - Ví dụ: các nút trong các cụm được kết nối dày đặc nhận được một lượng lớn thông tin cục bộ, trong khi các nút ngoại vi có thể có tương tác hạn chế. - **Thuộc tính nút và cạnh**: - Các nút thường đi kèm với các đặc trưng, có thể bao gồm các đặc trưng số đơn giản, các danh mục được mã hóa một nóng hoặc các vectơ phức tạp hơn (như nhúng trong NLP). - Các thuộc tính cạnh cũng có thể xác định bản chất của các kết nối giữa các nút (ví dụ: trọng số hoặc loại quan hệ), tác động đến cách tin nhắn được truyền và tổng hợp. - **Mã hóa vị trí hoặc không gian**: - Đối với đồ thị có cấu trúc không gian hoặc phân cấp tự nhiên, mã hóa vị trí (như trong biến đổi) có thể làm phong phú thêm bối cảnh nút bằng cách mã hóa các vị trí tương đối trong đồ thị. - **Cân nhắc đánh giá**: Hiểu bối cảnh bao gồm kiểm tra cách cấu trúc và các đặc trưng kết hợp để định hình trường tiếp nhận của nút: - **Vùng dày đặc so với vùng thưa thớt**: Các nút trong vùng dày đặc hơn có thể hưởng lợi nhiều hơn từ truyền tin, vì chúng nhận được ngữ cảnh phong phú hơn, trong khi các nút trong vùng thưa thớt có thể yêu cầu mã hóa vị trí hoặc cấu trúc bổ sung để bù đắp. - **Độ biến thiên đặc trưng**: Độ biến thiên lớn hơn trong các đặc trưng nút hoặc cạnh có thể cải thiện sự đa dạng của thông tin được trao đổi, điều này có thể có lợi cho các tác vụ dựa vào việc phân biệt các nút dựa trên thông tin dựa trên đặc trưng hoặc dựa trên thuộc tính. ___ ##### 1.3 Phương pháp tổng hợp được sử dụng là gì? **Phương pháp tổng hợp** trong truyền tin là hàm được sử dụng để kết hợp thông tin từ các nút lân cận. Các phương pháp tổng hợp khác nhau có thể ảnh hưởng đáng kể đến chất lượng và loại thông tin mà một nút cuối cùng mã hóa. Các phương pháp tổng hợp phổ biến bao gồm: - **Tổng hợp trung bình**: - Tính trung bình các đặc trưng của các nút lân cận. - **Ưu điểm**: Đơn giản và hiệu quả về mặt tính toán, nắm bắt xu hướng trung bình trong vùng lân cận. - **Nhược điểm**: Có thể bỏ lỡ các biến thể quan trọng trong vùng lân cận, vì nó chỉ tóm tắt giá trị trung bình. - **Tổng hợp tổng**: - Cộng các đặc trưng từ các nút lân cận. - **Ưu điểm**: Bảo toàn tổng lượng thông tin đặc trưng, hữu ích cho các tác vụ dựa trên đếm hoặc tích lũy. - **Nhược điểm**: Có thể dẫn đến độ lớn đặc trưng lớn hơn, có thể yêu cầu chuẩn hóa. - **Gộp tối đa**: - Lấy giá trị tối đa trên các đặc trưng từ các nút lân cận. - **Ưu điểm**: Làm nổi bật các tín hiệu mạnh nhất trong vùng lân cận, thường tăng cường các đặc trưng quan trọng hoặc chiếm ưu thế. - **Nhược điểm**: Mất thông tin về các nút lân cận khác, có khả năng bỏ qua cấu trúc tổng thể của vùng lân cận. - **Cơ chế chú ý** (được sử dụng trong **Mạng chú ý đồ thị (GAT)**): - Gán trọng số cho mỗi nút lân cận dựa trên mức độ liên quan của nó, cho phép nút chọn lọc chú ý đến các nút lân cận cụ thể. - **Ưu điểm**: Thích ứng và nhạy cảm với ngữ cảnh, vì mô hình học được nút lân cận nào phù hợp nhất. - **Nhược điểm**: Phức tạp hơn về mặt tính toán và có khả năng yêu cầu tập dữ liệu lớn hơn để học điểm chú ý có ý nghĩa. - **Tổng hợp dựa trên LSTM hoặc GRU**: - Bộ tổng hợp tuần tự như LSTM có thể được sử dụng trong đồ thị có thứ tự để nắm bắt các phụ thuộc tuần tự trong vùng lân cận. - **Ưu điểm**: Hiệu quả đối với đồ thị có thứ tự hoặc phụ thuộc tự nhiên. - **Nhược điểm**: Tốn nhiều tài nguyên tính toán và có thể gây ra sai lệch thứ tự. ___ #### Tóm tắt các nguyên tắc đánh giá bằng cách sử dụng nguyên tắc truyền tin Để đánh giá GNN dựa trên truyền tin, các câu hỏi sau đây cung cấp một cách tiếp cận có cấu trúc: 1. **Độ sâu của vùng lân cận**: Xác định có bao nhiêu bước nhảy hoặc lớp là cần thiết để nắm bắt thông tin có ý nghĩa cho nhiệm vụ. - Chọn độ sâu nắm bắt cấu trúc liên quan mà không làm mịn quá mức. - Kiểm tra các độ sâu khác nhau trong quá trình thử nghiệm để tìm sự cân bằng tối ưu. 2. **Bối cảnh của người nhận dữ liệu**: Kiểm tra ngữ cảnh dựa trên cấu trúc và đặc trưng của mỗi nút, cụ thể là: - Các nút được kết nối dày đặc có thể hưởng lợi từ truyền tin trực tiếp hơn, trong khi các nút thưa thớt hoặc ngoại vi có thể cần mã hóa vị trí hoặc cấu trúc nâng cao. - Các nút có thông tin thuộc tính phong phú hoặc trọng số cạnh có ý nghĩa có thể cung cấp bối cảnh tinh tế hơn để tổng hợp. 3. **Phương pháp tổng hợp**: Chọn phương pháp tổng hợp phù hợp với nhiệm vụ và cấu trúc đồ thị. - **Tổng hợp trung bình và tổng** thường phù hợp với các tác vụ hoặc đồ thị đơn giản hơn với các vùng lân cận đồng nhất. - **Gộp tối đa(Max pooling)** và **cơ chế chú ý(attention mechanisms)** tốt hơn cho đồ thị phức tạp hoặc không đồng nhất, trong đó các nút hoặc cạnh nhất định có thể có ý nghĩa quan trọng hơn các nút hoặc cạnh khác. Việc đánh giá các khía cạnh này trong quá trình huấn luyện và thử nghiệm mô hình giúp tinh chỉnh kiến trúc của GNN để tối đa hóa hiệu suất trên các tác vụ cụ thể, chẳng hạn như phân loại nút, dự đoán liên kết hoặc phân loại đồ thị. Bằng cách điều chỉnh cẩn thận độ sâu vùng lân cận, xem xét bối cảnh và phương pháp tổng hợp, mô hình có thể được tối ưu hóa để truyền tin hiệu quả và dễ hiểu, cuối cùng dẫn đến biểu diễn đồ thị mạnh mẽ hơn. ## VII. Khả năng diễn giải và tính tương thích của lớp MLP trong cấu trúc GNN **Khả năng diễn giải** của **lớp MLP (Perceptron nhiều lớp)** trong cấu trúc GNN, cũng như **tính tương thích** giữa các thành phần GNN và MLP, là những yếu tố quan trọng để hiểu và phân tích mức độ mô hình nắm bắt và sử dụng thông tin dựa trên đồ thị cho các tác vụ tiếp theo. Chúng ta hãy xem xét kỹ từng thành phần này: #### 1. Khả năng diễn giải của lớp MLP sau cấu trúc GNN Khi GNN đưa đầu ra của nó vào lớp MLP, khả năng diễn giải của lớp cuối cùng này phụ thuộc vào mức độ MLP có thể xử lý **nhúng nút** do GNN tạo ra. Dưới đây là một số điểm chính cần xem xét: ##### A. Vai trò của MLP trong cấu trúc GNN Lớp MLP thường đóng vai trò là **bộ phân loại cuối cùng** hoặc **bộ hồi quy** trong kiến trúc GNN. Các chức năng chính của nó bao gồm: - **Tổng hợp các đặc trưng** được học thông qua nhiều lớp truyền tin GNN. - **Biến đổi nhúng** do GNN tạo ra thành định dạng đầu ra mong muốn cho các tác vụ cụ thể, chẳng hạn như phân loại nút, dự đoán liên kết hoặc dự đoán cấp độ đồ thị. Trong vai trò này, MLP: - **Xử lý các nhúng phong phú** do GNN tạo ra, kết hợp cả thông tin cấu trúc đồ thị cục bộ và toàn cục, thuộc tính nút và các mối quan hệ phức tạp, nhiều bước nhảy tiềm năng. - **Áp dụng các phép biến đổi phi tuyến** có thể tinh chỉnh hoặc lọc nhúng đồ thị, cung cấp thêm một mức độ trừu tượng hoặc ra quyết định. ##### B. Khả năng diễn giải của lớp MLP Khả năng diễn giải của lớp MLP trong GNN phụ thuộc vào nhiệm vụ, cũng như cách chúng ta diễn giải ranh giới quyết định cuối cùng hoặc đầu ra mà nó tạo ra: - **Trích xuất đặc trưng**: Vì MLP đang học trực tiếp từ các nhúng được GNN xử lý, nên nó có thể được xem như là **lớp trích xuất đặc trưng cuối cùng**. Mỗi đơn vị ẩn trong MLP nắm bắt một tổ hợp khác nhau của các đặc trưng được GNN học, giúp có thể phân tích cách các đặc trưng riêng lẻ hoặc nhóm đặc trưng ảnh hưởng đến dự đoán cuối cùng. - **Ranh giới quyết định**: Trong các tác vụ phân loại, lớp MLP tạo ra ranh giới quyết định phi tuyến trên không gian nhúng do GNN tạo ra. Điều này cung cấp thông tin chi tiết về **mẫu cấu trúc hoặc đặc trưng nào** (được GNN học) mang tính quyết định hơn cho việc phân loại cuối cùng. Ví dụ: hình dung các ranh giới quyết định này hoặc kiểm tra cách các lớp cụ thể phân cụm trong không gian nhúng có thể cung cấp khả năng diễn giải về cách các mối quan hệ dựa trên đồ thị ảnh hưởng đến dự đoán. - **Phân bổ và tầm quan trọng của đặc trưng**: Các phương pháp như **Lan truyền mức độ liên quan theo lớp (LRP)** hoặc **SHAP (SHapley Additive exPlanations)** có thể được áp dụng để phân tích đặc trưng nút hoặc cạnh nào từ đồ thị ban đầu có ảnh hưởng nhất trong việc xác định đầu ra của MLP. Các phương pháp này có thể phân bổ tầm quan trọng cho các đặc trưng đồ thị cụ thể, hỗ trợ khả năng diễn giải vai trò của lớp MLP. ##### C. Ví dụ thực tế về khả năng diễn giải của MLP Trong tác vụ **phân loại nút**, GNN có thể mã hóa mỗi nút bằng một vectơ nắm bắt cấu trúc vùng lân cận và thuộc tính đặc trưng. Khi mã hóa này được đưa vào MLP: - MLP gán trọng số khác nhau cho mỗi đặc trưng, tiết lộ khía cạnh nào của vùng lân cận của nút phù hợp nhất để phân loại. - Ví dụ: trong mạng trích dẫn, MLP có thể nhấn mạnh các đặc trưng nhất định (như "được kết nối với các bài báo được trích dẫn nhiều") là chỉ báo mạnh mẽ về lớp của nút. #### 2. Tính tương thích giữa các lớp GNN và MLP **Tính tương thích** giữa các cấu trúc GNN và MLP là rất quan trọng để học tập hiệu quả và phụ thuộc vào mức độ MLP có thể tận dụng nhúng đồ thị do GNN tạo ra. Các yếu tố tương thích bao gồm: ##### A. Tính tương thích đặc trưng Tính tương thích của hai thành phần bị ảnh hưởng rất nhiều bởi **mức độ nhúng của GNN phù hợp với yêu cầu của MLP** để đưa ra dự đoán chính xác. Các yếu tố bao gồm: - **Khớp số chiều**: Số chiều đầu ra của GNN phải tương thích với yêu cầu đầu vào của MLP. Nếu GNN tạo ra nhúng có số chiều$d$, thì MLP phải có khả năng xử lý các vectơ đầu vào của số chiều này mà không cần đệm hoặc cắt bớt quá mức. - **Tính biểu cảm**: GNN thường tạo ra các nhúng thông tin có số chiều cao, nắm bắt thông tin cấu trúc và thuộc tính tinh tế. MLP phải có khả năng trích xuất các mẫu có liên quan từ các nhúng này; nếu không, lợi ích của sức mạnh biểu đạt của GNN sẽ bị mất. Lớp MLP được thiết kế tốt với chiều rộng và độ sâu đủ có thể học các ánh xạ phức tạp từ các nhúng này sang các lớp đầu ra, nhãn hoặc dự đoán. ##### B. Luồng thông tin và tính đầy đủ Để có tính tương thích tối ưu, luồng thông tin giữa GNN và MLP phải **đầy đủ** - nghĩa là GNN lý tưởng nhất nên chuyển tất cả thông tin cần thiết đến MLP cho tác vụ tiếp theo. - **Tính đầy đủ** của nhúng GNN: Nhúng của GNN cần nắm bắt tất cả thông tin có liên quan (đặc trưng nút, mối quan hệ cấu trúc, thuộc tính cạnh) cần thiết cho tác vụ của MLP. Nếu thiếu các mối quan hệ quan trọng, MLP có thể không có đủ thông tin để đưa ra dự đoán chính xác. - **Dư thừa và quá khớp (Overfitting)**: Nhúng có số chiều cao cũng có thể gây ra dư thừa, đặc biệt nếu GNN sâu hoặc nắm bắt các đặc trưng quá chi tiết. MLP được điều chỉnh tốt có thể quản lý dư thừa bằng cách chọn lọc các đặc trưng trọng số, nhưng cấu hình kém có thể dẫn đến quá khớp (overfitting). ##### C. Tính tương thích thực nghiệm: Hiệp lực hiệu suất GNN + MLP Theo kinh nghiệm, tính tương thích giữa các lớp GNN và MLP được đánh giá dựa trên **mức độ chúng hoạt động cùng nhau để cải thiện các số liệu cụ thể cho tác vụ** (ví dụ: độ chính xác, điểm F1 hoặc sai số bình phương trung bình). - **Đánh giá thực nghiệm**: Các thí nghiệm thường chỉ ra rằng việc kết hợp GNN với MLP đạt được hiệu suất vượt trội trên các tác vụ phức tạp, chẳng hạn như phân loại nút và dự đoán cấp độ đồ thị. Điều này là do MLP tinh chỉnh các biểu diễn có cấu trúc do GNN tạo ra, cho phép mô hình tận dụng cả mẫu đồ thị cục bộ và toàn cục. - **Nghiên cứu cắt bỏ**: Nhiều nghiên cứu đánh giá tính tương thích của tổ hợp GNN-MLP bằng cách loại bỏ MLP hoặc sửa đổi GNN và quan sát những thay đổi về hiệu suất. Việc loại bỏ MLP thường dẫn đến giảm độ chính xác trong các tác vụ tiếp theo, vì MLP đóng một vai trò quan trọng trong việc biến đổi nhúng GNN thành đầu ra cụ thể cho tác vụ. ##### D. Ví dụ thực tế về tính tương thích Hãy xem xét **mạng xã hội** nơi chúng tôi muốn dự đoán sở thích của người dùng dựa trên các kết nối và thuộc tính hồ sơ: - **GNN** xử lý cấu trúc mạng, mã hóa từng người dùng dựa trên các kết nối và thuộc tính của những người hàng xóm. - Sau đó, **MLP** lấy các nhúng này và xác định ranh giới quyết định tốt nhất để phân loại sở thích của từng người dùng. Tính tương thích giữa GNN và MLP phụ thuộc vào khả năng của MLP trong việc tận dụng nhúng GNN để hình thành các cụm hoặc ranh giới riêng biệt cho các nhóm sở thích khác nhau. Trong trường hợp này: - Nếu nhúng GNN rõ ràng và khác biệt, MLP có thể phân loại sở thích một cách hiệu quả. - Nếu các nhúng quá giống nhau hoặc thiếu thông tin cần thiết, MLP có thể gặp khó khăn, cho thấy khả năng tương thích kém. #### Tóm tắt 1. **Khả năng diễn giải của lớp MLP**: MLP thêm một lớp tổng hợp đặc trưng và ra quyết định có thể diễn giải, tinh chỉnh các nhúng do GNN tạo ra. Nó cho phép chúng tôi hiểu cách các đặc trưng cụ thể hoặc tổ hợp các đặc trưng đóng góp vào dự đoán cuối cùng. 2. **Tính tương thích giữa GNN và MLP**: - **Tính tương thích đặc trưng**: Đảm bảo rằng MLP có thể xử lý hiệu quả số chiều và độ phức tạp của nhúng GNN. - **Luồng thông tin và tính đầy đủ**: Đảm bảo rằng nhúng GNN nắm bắt đủ thông tin để MLP đưa ra dự đoán chính xác. - **Tính tương thích thực nghiệm**: Được chứng minh thông qua kết quả thực nghiệm cho thấy hiệu suất tăng khi sử dụng GNN + MLP, thường được kiểm tra bằng các nghiên cứu cắt bỏ. Sự kết hợp GNN-MLP thường tương thích với các tác vụ dựa trên đồ thị, vì GNN cung cấp nhúng có cấu trúc, quan hệ và MLP chuyển đổi chúng thành đầu ra cụ thể cho tác vụ. Hiệu quả của sự kết hợp này thường được xác nhận bằng thực nghiệm, làm cho nó trở thành lựa chọn phổ biến trong các ứng dụng học máy đồ thị. ## VIII. Hàm mất mát và hàm rủi ro trong kiến trúc GNN+MLP **Hàm mất mát (loss function)** được sử dụng trong kiến trúc GNN+MLP thường phụ thuộc vào loại nhiệm vụ (ví dụ: phân loại, hồi quy hoặc dự đoán liên kết) và đóng một vai trò quan trọng trong việc tối ưu hóa mô hình trong quá trình huấn luyện. Ngoài hàm mất mát, **hàm rủi ro (risk function)** (thường được xem là giá trị kỳ vọng của mất mát trên tập dữ liệu) được sử dụng để đo lường khả năng khái quát hóa của mô hình trên dữ liệu chưa nhìn thấy. Chúng ta hãy đi sâu vào các hàm này, cách chúng hoạt động và các yếu tố ảnh hưởng đến chúng trong quá trình huấn luyện. #### 1. Các loại hàm mất mát và vai trò của chúng Hàm mất mát là số liệu đánh giá mức độ dự đoán của mô hình phù hợp với nhãn hoặc giá trị thực, hướng dẫn quá trình học bằng cách cung cấp thước đo định lượng về lỗi. ##### Các hàm mất mát phổ biến cho kiến trúc GNN+MLP 1. **Mất mát chéo entropy (Cross-Entropy Loss)** (cho các tác vụ phân loại): - **Định nghĩa**: Mất mát chéo entropy thường được sử dụng khi mô hình đang thực hiện tác vụ phân loại (ví dụ: phân loại nút). Nó đo lường sự phân kỳ giữa phân phối xác suất dự đoán (đầu ra của lớp softmax MLP) và phân phối nhãn thực. - **Công thức**: $$\text{Loss}_{\text{cross-entropy}}=-\sum_{i=1}^C y_i \log(\hat{y}_i)$$ trong đó $C$ là số lớp, $y_i$ là nhãn thực (thường được mã hóa một nóng) và $\hat{y}_i$ là xác suất dự đoán cho lớp $i$. - **Mục đích**: Mất mát chéo entropy khuyến khích mô hình tối đa hóa xác suất của lớp chính xác, giảm thiểu sự khác biệt giữa các lớp dự đoán và thực tế. Điều này được sử dụng rộng rãi trong các tác vụ **phân loại nút** và **phân loại cấp độ đồ thị**. 2. **Mất mát sai số bình phương trung bình (MSE - Mean Squared Error Loss)** (cho các tác vụ hồi quy): - **Định nghĩa**: LOSS MSE được sử dụng khi mô hình thực hiện tác vụ hồi quy (ví dụ: dự đoán giá trị liên tục cho mỗi nút hoặc cạnh). Nó tính toán chênh lệch bình phương trung bình giữa các giá trị dự đoán và thực tế. - **Công thức**: $$\text{Loss}_{\text{MSE}} = \frac{1}{N} \sum_{i=1}^N (\hat{y}_i - y_i)^2$$ trong đó $N$ là số lượng mẫu, $\hat{y}_i$ là giá trị dự đoán và$y_i$ là giá trị thực. - **Mục đích**: MSE xử phạt các lỗi lớn hơn nhiều hơn các lỗi nhỏ hơn, điều này có thể giúp mô hình học cách giảm thiểu các sai lệch đáng kể. Nó thường được sử dụng cho các tác vụ **hồi quy nút**, chẳng hạn như dự đoán các thuộc tính liên tục. 3. **Mất mát chéo entropy nhị phân (Binary Cross-Entropy Loss)** (cho các tác vụ phân loại nhị phân hoặc dự đoán liên kết): - **Định nghĩa**: Chéo entropy nhị phân được sử dụng để phân loại nhị phân, trong đó mỗi đầu ra được phân loại độc lập thành một trong hai lớp. Nó thường được áp dụng trong các tác vụ **dự đoán liên kết**, trong đó mục tiêu là xác định sự hiện diện hoặc vắng mặt của một cạnh giữa hai nút. - **Công thức**: $$\text{Loss}_{\text{binary}} = - \left( y \log(\hat{y}) + (1 - y) \log(1 - \hat{y}) \right)$$ trong đó $y$ là nhãn thực (0 hoặc 1) và $\hat{y}$ là xác suất dự đoán. - **Mục đích**: Chéo entropy nhị phân tối ưu hóa mô hình để dự đoán khả năng xảy ra mối quan hệ tích cực hoặc tiêu cực trong dự đoán liên kết và các tác vụ nhị phân khác. 4. **Mất mát tương phản (Contrastive Loss)** (cho các tác vụ nhúng và dựa trên sự giống nhau): - **Định nghĩa**: Mất mát tương phản được sử dụng khi mục tiêu là học các biểu diễn đưa các cặp nút tương tự lại gần nhau trong không gian nhúng đồng thời đẩy các cặp không giống nhau ra xa nhau. - **Công thức**: $$\text{Loss}_{\text{contrastive}} = \frac{1}{N} \sum_{i,j} y_{ij} d(\mathbf{z}_i, \mathbf{z}_j)^2 + (1 - y_{ij}) \max(0, m - d(\mathbf{z}_i, \mathbf{z}_j))^2$$ trong đó $y_{ij}$ là 1 nếu các nút$i$và$j$giống nhau và 0 nếu ngược lại, $d(\mathbf{z}_i, \mathbf{z}_j)$ là khoảng cách giữa các nhúng và $m$ là tham số lề. - **Mục đích**: Hàm mất mát này phổ biến trong **học biểu diễn** trên đồ thị, đặc biệt là trong các tác vụ học tập không giám sát, trong đó mục tiêu là nhúng các nút dựa trên sự giống nhau về cấu trúc. #### 2. Cách hàm mất mát lấy dữ liệu Hàm mất mát lấy: - **Đầu ra dự đoán**: Đây là đầu ra của MLP, xử lý nhúng do GNN tạo ra. Đối với phân loại, đây là xác suất; đối với hồi quy, giá trị liên tục; đối với mất mát tương phản, khoảng cách trong không gian nhúng. - **Nhãn hoặc giá trị thực**: Đối với các tác vụ có giám sát, nhãn thực (ví dụ: nhãn lớp, mục tiêu hồi quy) được so sánh với dự đoán để tính toán mất mát. Mất mát được tính **cho mỗi trường hợp** (nút, cạnh hoặc đồ thị) và được tính trung bình trên tập dữ liệu hoặc lô nhỏ trong mỗi lần lặp huấn luyện, cung cấp giá trị mất mát vô hướng đóng vai trò là mục tiêu để tối ưu hóa dựa trên gradient. #### 3. Đánh giá hàm mất mát và hàm rủi ro trên mô hình ##### A. Hàm mất mát **Hàm mất mát** đánh giá hiệu suất của mô hình trên lô dữ liệu hiện tại. Mất mát thấp cho biết dự đoán của mô hình khớp chặt chẽ với nhãn hoặc giá trị sự thật cơ bản, trong khi mất mát cao cho biết sự khác biệt đáng kể. ##### B. Hàm rủi ro (Khái quát hóa và mất mát dự kiến) **Hàm rủi ro** biểu thị **mất mát dự kiến** trên toàn bộ phân phối dữ liệu, bao gồm cả các ví dụ chưa nhìn thấy. Trong khi hàm mất mát cung cấp ảnh chụp nhanh về hiệu suất mô hình trên lô hiện tại, thì hàm rủi ro đánh giá khả năng **khái quát hóa** của mô hình. - **Giảm thiểu rủi ro**: Mục tiêu của đào tạo là giảm thiểu hàm rủi ro, điều này ngụ ý đạt được lỗi thấp trên cả dữ liệu huấn luyện và dữ liệu kiểm tra chưa nhìn thấy. - **Quá khớp (Overfitting) so với thiếu khớp (Underfitting)**: Giảm thiểu rủi ro bao gồm việc cân bằng giữa quá khớp (mất mát thấp khi huấn luyện nhưng cao trên dữ liệu kiểm tra) và thiếu khớp (mất mát cao trên cả dữ liệu huấn luyện và dữ liệu kiểm tra), thường được quản lý bằng cách điều chỉnh và điều chỉnh cẩn thận các tham số mô hình. #### 4. Các tham số và biến ảnh hưởng đến hàm mất mát trong quá trình huấn luyện Một số tham số và biến chính ảnh hưởng đến hành vi của hàm mất mát và do đó, hiệu suất của mô hình trong quá trình huấn luyện: ##### A. Tham số mô hình 1. **Tham số GNN**: Trọng số của GNN, chiến lược tổng hợp và số lớp xác định chất lượng của nhúng nút được đưa vào MLP. - **Số lượng lớp**: Tăng số lượng lớp cho phép thông tin chạy từ các nút lân cận ở xa hơn nhưng có thể dẫn đến làm mịn quá mức nếu quá nhiều. - **Hàm tổng hợp**: Các phương pháp tổng hợp khác nhau (ví dụ: trung bình, tối đa, chú ý) ảnh hưởng đến cách kết hợp các đặc trưng nút, tác động đến độ phong phú và tính biểu cảm của nhúng. 2. **Tham số MLP**: Trọng số MLP xác định cách nhúng được biến đổi và phân loại hoặc hồi quy. - **Độ sâu và chiều rộng**: Số lượng lớp và số lượng nơ-ron trên mỗi lớp trong MLP ảnh hưởng đến khả năng nắm bắt các mối quan hệ phi tuyến của mô hình. - **Hàm kích hoạt**: Các hàm như ReLU, tanh hoặc softmax ảnh hưởng đến phép biến đổi phi tuyến của nhúng, tác động đến tính biểu cảm và hội tụ của mô hình. ##### B. Siêu tham số 1. **Tốc độ học**: Kiểm soát kích thước bước trong giảm dần gradient. Tốc độ học cao có thể dẫn đến dao động xung quanh mức tối thiểu, trong khi tốc độ thấp có thể dẫn đến hội tụ chậm. 2. **Kích thước lô**: Ảnh hưởng đến độ chi tiết của cập nhật gradient. Kích thước lô nhỏ hơn tạo ra nhiều nhiễu hơn trong các bản cập nhật, điều này có thể cải thiện khả năng khái quát hóa, trong khi các lô lớn hơn cung cấp các bản cập nhật ổn định hơn nhưng có thể dẫn đến quá khớp (overfitting). 3. **Tham số điều chuẩn**: - **Dropout**: Ngẫu nhiên loại bỏ các đơn vị trong GNN và MLP trong quá trình huấn luyện, giảm sự phụ thuộc vào các nút hoặc đường dẫn cụ thể và cải thiện khả năng khái quát hóa. - **Suy giảm trọng số (Điều chuẩn L2)**: Thêm hình phạt vào độ lớn của trọng số, ngăn mô hình dựa quá nhiều vào các tham số cụ thể và khuyến khích các giải pháp đơn giản hơn. ##### C. Biến cấu trúc và đầu vào 1. **Độ thưa thớt của đồ thị(Graph Sparsity)**: Đồ thị thưa thớt (với bậc nút trung bình thấp) có thể hạn chế lượng thông tin có sẵn cho mỗi nút, khiến mô hình khó học hỏi từ kết nối hạn chế. 2. **Đặc trưng nút và cạnh(Node and Edge Features)**: Chất lượng và số lượng đặc trưng ảnh hưởng trực tiếp đến nhúng. Các đặc trưng phong phú hơn thường dẫn đến nhúng tốt hơn, làm giảm mất mát và cải thiện khả năng khái quát hóa. 3. **Kích thước đồ thị và tính đồng nhất(Graph Size and Homophily)**: Các đồ thị lớn có tính đồng nhất cao (các nút được kết nối với các nút tương tự) có thể tạo ra các nhúng dễ phân loại hơn, trong khi các đồ thị có cấu trúc đa dạng và tính không đồng nhất (các nút được kết nối với các nút không giống nhau) có thể yêu cầu các mô hình phức tạp hơn và dẫn đến mất mát cao hơn nếu không được biểu diễn tốt. #### Tóm tắt - **Loss Function**: Đo lường trực tiếp sự khác biệt giữa dự đoán và giá trị thực cho mỗi lô huấn luyện. Các lựa chọn phổ biến bao gồm chéo entropy (phân loại), MSE (hồi quy) và chéo entropy nhị phân hoặc mất mát tương phản (dự đoán liên kết và độ tương tự). - **Hàm rủi ro(Risk Function)**: Biểu thị mất mát dự kiến trên toàn bộ phân phối dữ liệu, phản ánh hiệu suất khái quát hóa. - **Training Variables**: Tham số mô hình (ví dụ: lớp GNN, độ sâu MLP), siêu tham số (tốc độ học, điều chuẩn) và cấu trúc đồ thị (độ thưa thớt, độ phong phú đặc trưng) đều ảnh hưởng đáng kể đến hàm mất mát và hàm rủi ro trong quá trình huấn luyện. Bằng cách tinh chỉnh các thành phần này, mô hình có thể đạt được sự hội tụ tốt hơn trên dữ liệu huấn luyện đồng thời đảm bảo khả năng khái quát hóa đối với dữ liệu chưa nhìn thấy, giảm thiểu hiệu quả cả hàm mất mát và hàm rủi ro. ## IX. Đánh giá lỗi trong mạng nơ-ron đồ thị (GNN) **Đánh giá lỗi** trong Mạng nơ-ron đồ thị (GNN) thường bao gồm việc hiểu và phân rã tổng lỗi của mô hình thành các thành phần riêng biệt, giúp chẩn đoán các vấn đề về hiệu suất và cải thiện khả năng khái quát hóa. Trong GNN, lỗi có thể bắt nguồn từ nhiều nguồn khác nhau, chẳng hạn như hạn chế xấp xỉ, quá khớp (overfitting), thiếu khớp (underfitting) và đặc thù cấu trúc đồ thị. Về mặt lý thuyết, chúng ta có thể biểu diễn lỗi bằng cách sử dụng **phân rã lỗi** và phân loại nó thành các loại mất mát riêng biệt, mỗi loại đóng góp vào hiệu suất tổng thể của mô hình. #### 1. Tổng lỗi trong GNN **Lỗi** tổng thể trong GNN có thể được mô tả là sự khác biệt giữa dự đoán của mô hình và nhãn thực, và thường được biểu thị là **rủi ro dự kiến** hoặc **lỗi khái quát hóa**: $$ \text{Expected Risk} = \mathbb{E}_{(x, y) \sim P_{\text{data}}} \left[ L(f(x; \theta), y) \right] $$ trong đó: - $f(x; \theta)$ là mô hình GNN được tham số hóa bởi $\theta$, - $L$ là hàm mất mát (ví dụ: chéo entropy hoặc MSE), - $(x, y)$ là các đặc trưng đầu vào và nhãn mục tiêu, - $P_{\text{data}}$ biểu thị phân phối dữ liệu. Rủi ro dự kiến này có thể được phân rã thành các thành phần **độ lệch (bias)**, **phương sai (variance)** và **lỗi không thể giảm (irreducible error)**, tương tự như các mô hình học máy truyền thống. Trong bối cảnh của GNN, các thành phần lỗi này mang ý nghĩa đặc biệt do cấu trúc đồ thị và quá trình tổng hợp vùng lân cận. #### 2. Error Decomposition: Bias, Variance, and Irreducible Error ##### A. Lỗi độ lệch (Bias error) Lỗi độ lệch biểu thị lỗi hệ thống do các giả định hoặc hạn chế của mô hình trong việc xấp xỉ mối quan hệ thực sự giữa đầu vào và đầu ra. Trong GNN, độ lệch bị ảnh hưởng bởi: - **Kiến trúc mô hình**: Việc lựa chọn hàm tổng hợp (trung bình, tổng, gộp tối đa) và độ sâu ảnh hưởng đến khả năng nắm bắt các sắc thái cấu trúc của GNN. GNN nông có thể có độ lệch cao vì chúng không thể nắm bắt các phụ thuộc phức tạp. - **Giả định đơn giản hóa**: Các mô hình có giả định mạnh (ví dụ: chỉ sử dụng các nút lân cận trực tiếp hoặc bỏ qua trọng số cạnh) có thể có độ lệch cao nếu các giả định này đơn giản hóa quá mức phân phối dữ liệu thực tế. **Thuật ngữ Bias độ lệch** có thể được biểu diễn bằng toán học như sau: $$ \text{Bias} = \left( \mathbb{E}[f(x; \theta)] - y \right)^2 $$ trong đó $y$ là nhãn thực và $\mathbb{E}[f(x; \theta)]$ là dự đoán dự kiến trên nhiều phiên bản mô hình hoặc mẫu dữ liệu. ##### B. Lỗi phương sai (Variance error) Lỗi phương sai nắm bắt độ nhạy cảm của dự đoán của mô hình đối với những thay đổi trong dữ liệu huấn luyện. Trong GNN, phương sai có thể phát sinh do: - **Độ biến thiên cấu trúc đồ thị**: Các biến thể về bậc nút, cấu trúc cộng đồng và phân phối cạnh có thể dẫn đến biến động trong biểu diễn đã học. - **Lấy mẫu vùng lân cận**: GNN thường tổng hợp thông tin từ các vùng lân cận được lấy mẫu, tạo ra tính ngẫu nhiên. Nếu việc lấy mẫu vùng lân cận thay đổi đáng kể giữa các nút hoặc lô nhỏ, nó có thể dẫn đến phương sai cao. - **Quá khớp (Overfitting)**: GNN sâu hơn dễ bị quá khớp bằng cách ghi nhớ cấu trúc của đồ thị huấn luyện, đặc biệt nếu chúng tận dụng các hàm tổng hợp phức tạp hoặc cơ chế chú ý. **Thuật ngữ Variance phương sai** được biểu thị là: $$ \text{Variance} = \mathbb{E}\left[ (f(x; \theta) - \mathbb{E}[f(x; \theta)])^2 \right] $$ trong đó $f(x; \theta)$ là dự đoán cho đầu vào$x$và kỳ vọng là trên các nhận thức khác nhau của mô hình được huấn luyện trên các mẫu khác nhau. ##### C. Lỗi không thể giảm (Irreducible error) Lỗi không thể giảm, còn được gọi là **lỗi nhiễu**, biểu thị nhiễu cố hữu trong dữ liệu mà mô hình không thể giải thích được, bất kể độ phức tạp của nó. Trong trường hợp của GNN, lỗi không thể giảm có thể đến từ: - **Nhiễu cố hữu trong nhãn**: Dữ liệu đồ thị có thể chứa nhãn nhiễu hoặc không đầy đủ, chẳng hạn như nhãn được gán thông qua phương pháp heuristic hoặc phương pháp giám sát yếu. - **Tính ngẫu nhiên của đồ thị**: Đồ thị trong thế giới thực thường chứa tính ngẫu nhiên trong các kết nối, điều này có thể khiến việc dự đoán các mối quan hệ một cách chính xác trở nên khó khăn ngay cả với một mô hình hoàn hảo. Lỗi không thể giảm được biểu diễn bằng toán học như sau: $$ \text{Irreducible Error} = \sigma^2 $$ trong đó $\sigma^2$ biểu thị phương sai do nhiễu trong dữ liệu. #### 3. Phân rã cụ thể lỗi GNN thành các lớp mất mát Lỗi trong GNN có thể được phân rã thêm thành các lớp **mất mát** khác nhau nắm bắt hành vi của mô hình ở các khía cạnh khác nhau. Chúng bao gồm **mất mát phân loại/hồi quy**, **mất mát cấu trúc** và **mất mát điều chuẩn**. ##### A. Mất mát cụ thể cho tác vụ (Mất mát phân loại/hồi quy) Đây là **hàm mất mát chính** được sử dụng để tối ưu hóa hiệu suất tác vụ (ví dụ: phân loại hoặc hồi quy). Mất mát này thường biểu thị sự khác biệt giữa dự đoán và nhãn sự thật cơ bản trên một tác vụ có giám sát. - **Mất mát phân loại**: Mất mát chéo entropy cho các tác vụ phân loại nút hoặc đồ thị. - **Mất mát hồi quy**: Sai số bình phương trung bình (MSE) cho các tác vụ hồi quy cấp nút hoặc cấp cạnh. Mất mát cụ thể cho tác vụ cung cấp thước đo lỗi liên quan trực tiếp đến khả năng khớp dữ liệu quan sát của mô hình. ##### B. Mất mát cấu trúc **Mất mát cấu trúc** xử phạt mô hình dựa trên sự khác biệt về cấu trúc giữa các mối quan hệ dự đoán và thực tế trong đồ thị. Nó đặc biệt phù hợp trong các tác vụ mà độ chính xác quan hệ là rất quan trọng, chẳng hạn như dự đoán liên kết hoặc phát hiện cộng đồng. 1. **Mất mát dự đoán liên kết**: Đối với các tác vụ dự đoán cạnh, chéo entropy nhị phân hoặc mất mát tương phản có thể được sử dụng để khuyến khích dự đoán liên kết chính xác và không khuyến khích các liên kết không chính xác. 2. **Điều chuẩn cấu trúc đồ thị**: Các thuật ngữ điều chuẩn có thể khuyến khích mô hình duy trì các thuộc tính đồ thị, chẳng hạn như mẫu kết nối hoặc cấu trúc cộng đồng. Ví dụ: - **Điều chuẩn Laplacian đồ thị**: Khuyến khích các nút tương tự về cấu trúc đồ thị có nhúng tương tự. Thuật ngữ mất mát thường được biểu thị là: $$\text{Laplacian Loss} = \sum_{(i, j) \in E} \left\| \mathbf{z}_i - \mathbf{z}_j \right\|^2$$ trong đó$\mathbf{z}_i$và$\mathbf{z}_j$là nhúng của các nút được kết nối$i$và$j$, và$E$là tập hợp cạnh. Mất mát này giảm thiểu sự khác biệt giữa các nhúng của các nút được kết nối, bảo toàn tính nhất quán cấu trúc. 3. **Mất mát độ tương tự nút**: Đối với đồ thị mà các nút có mối quan hệ hoặc độ tương tự đã biết, mất mát tương phản có thể khuyến khích các nút có đặc trưng hoặc vai trò cấu trúc tương tự có nhúng tương tự. ##### C. Mất mát điều chuẩn **Mất mát điều chuẩn** rất cần thiết để kiểm soát độ phức tạp của mô hình và đảm bảo rằng nó khái quát hóa tốt với dữ liệu chưa nhìn thấy. Các kỹ thuật điều chuẩn phổ biến bao gồm: 1. **Suy giảm trọng số (Điều chuẩn L2)**: Hình phạt đối với trọng số lớn trong các lớp GNN và MLP để ngăn mô hình khớp với nhiễu. Thuật ngữ mất mát là: $$\text{Regularization L2} = \lambda \sum_{k} \|\theta_k\|^2$$ trong đó$\lambda$là hệ số điều chuẩn và$\theta_k$biểu thị các tham số mô hình. 2. **Điều chuẩn Dropout**: Được sử dụng trong cả lớp GNN và MLP, dropout ngẫu nhiên loại bỏ các nút hoặc cạnh trong quá trình huấn luyện để ngăn mô hình trở nên quá phụ thuộc vào các đường dẫn hoặc nút lân cận cụ thể, cải thiện khả năng khái quát hóa. 3. **Điều chuẩn chú ý**: Trong các mô hình sử dụng cơ chế chú ý (ví dụ: Mạng chú ý đồ thị), việc điều chuẩn trọng số chú ý có thể ngăn mô hình chú ý quá mức đến các nút lân cận cụ thể. Một thuật ngữ điều chuẩn khả thi là: $$\text{Attention Entropy Loss} = -\sum_{i} \sum_{j} a_{ij} \log(a_{ij})$$ trong đó$a_{ij}$là trọng số chú ý cho các nút lân cận$j$của nút$i$. Thuật ngữ entropy này khuyến khích phân phối chú ý đồng đều hơn, tránh phụ thuộc quá nhiều vào một số ít nút. ___ #### 4. Tóm tắt các thành phần lỗi trong GNN Tóm lại, **lỗi trong GNN** có thể được phân rã thành các thành phần lý thuyết và thực tiễn khác nhau: 1. **Độ lệch (Bias)**: Lỗi hệ thống do kiến trúc và giả định mô hình (ví dụ: GNN nông với tổng hợp vùng lân cận cục bộ). 2. **Phương sai (Variance)**: Lỗi do độ nhạy của mô hình đối với các biến thể dữ liệu (ví dụ: độ nhạy với các cấu trúc đồ thị khác nhau, quá khớp (overfitting)). 3. **Lỗi không thể giảm (Irreducible Error)**: Nhiễu trong dữ liệu mà mô hình không thể giải thích được, chẳng hạn như nhiễu nhãn hoặc tính ngẫu nhiên cố hữu trong các kết nối đồ thị. **Mất mát cụ thể cho tác vụ** nắm bắt hiệu suất phân loại hoặc hồi quy chính, **Mất mát cấu trúc** thực thi các thuộc tính đồ thị và tính nhất quán cấu trúc, và **Mất mát điều chuẩn** kiểm soát độ phức tạp của mô hình, đảm bảo khả năng khái quát hóa và ngăn chặn quá khớp (overfitting). Mỗi thành phần này đóng góp vào tổng lỗi trong mô hình GNN và cung cấp các khu vực riêng biệt để cải thiện hoặc điều chuẩn trong quá trình huấn luyện mô hình. Bằng cách điều chỉnh các thành phần mất mát này, chúng ta có thể đạt được khả năng khái quát hóa tốt hơn và giảm tổng lỗi, làm cho mô hình mạnh mẽ hơn cho các tác vụ dựa trên đồ thị. ## X. Nguyên tắc cập nhật (học) trong mạng nơ-ron đồ thị (GNN) **Nguyên tắc cập nhật (học)** được sử dụng trong Mạng nơ-ron đồ thị (GNN) thực sự dựa trên **lan truyền ngược đầu cuối (end-to-end backpropagation)**, trong đó các tham số của mô hình được tối ưu hóa bằng cách lan truyền gradient lỗi từ lớp đầu ra qua từng lớp của mạng, bao gồm cả GNN và bất kỳ lớp MLP bổ sung nào. Quá trình đầu cuối này cho phép mô hình học các biểu diễn được tối ưu hóa trực tiếp cho mục tiêu nhiệm vụ (ví dụ: phân loại, hồi quy). Chúng ta hãy đi sâu hơn vào các khía cạnh chính, thuộc tính, độ phức tạp tính toán và phân tích lý thuyết về quá trình học này. #### 1. Lan truyền ngược đầu cuối trong GNN **Lan truyền ngược đầu cuối** trong GNN bao gồm việc tính toán gradient của hàm mất mát đã chọn đối với các tham số mô hình và cập nhật chúng lặp đi lặp lại để giảm thiểu mất mát. Cụ thể, trong GNN: - **Các lớp GNN** tổng hợp thông tin từ các nút lân cận và truyền thông tin này qua các trọng số có thể học được. - **Lan truyền ngược** cho phép mô hình lan truyền tín hiệu lỗi từ lớp cuối cùng (ví dụ: đầu ra MLP) ngược trở lại qua từng lớp GNN, điều chỉnh trọng số trên tất cả các lớp để tối ưu hóa hiệu suất nhiệm vụ. Quá trình học tập tổng thể có thể được tóm tắt như sau: 1. **Chuyển tiếp**: Tính toán nhúng nút bằng cách tổng hợp các đặc trưng thông qua các lớp GNN và tạo dự đoán cụ thể cho tác vụ (ví dụ: lớp nút hoặc giá trị hồi quy). 2. **Tính toán mất mát**: Tính toán mất mát cụ thể cho tác vụ (ví dụ: chéo entropy để phân loại). 3. **Tính toán gradient**: Tính toán gradient của mất mát đối với mỗi tham số trong các lớp GNN và MLP bằng cách sử dụng lan truyền ngược. 4. **Cập nhật tham số**: Cập nhật tham số bằng cách sử dụng bộ tối ưu hóa (ví dụ: giảm dần gradient ngẫu nhiên, Adam). #### 2. Thuộc tính của lan truyền ngược đầu cuối trong GNN Một số thuộc tính xác định cách lan truyền ngược đầu cuối hoạt động trong GNN: ##### A. Tổng hợp thông tin theo lớp Lan truyền ngược trong GNN vốn hỗ trợ **học tập theo lớp**. Mỗi lớp học cách tổng hợp thông tin vùng lân cận ở các bước nhảy lớn hơn dần, với các lớp đầu tập trung vào các nút lân cận gần và các lớp sâu hơn nắm bắt ngữ cảnh rộng hơn. ##### B. Gradient thông qua cấu trúc đồ thị Lan truyền ngược đầu cuối yêu cầu gradient chạy qua cấu trúc đồ thị, nghĩa là cập nhật nhúng của mỗi nút phụ thuộc vào các nút lân cận của nó. Điều này dẫn đến **chia sẻ tham số** giữa các nút, cho phép GNN khái quát hóa tốt hơn trên toàn bộ đồ thị. ##### C. Chia sẻ tham số và bất biến đồ thị GNN học các tham số **bất biến với thứ tự nút** và **đồng dạng đồ thị**, nghĩa là cùng một tham số đã học có thể áp dụng bất kể nhận dạng nút hoặc hướng đồ thị. Thuộc tính này cho phép GNN khái quát hóa cho các cấu trúc đồ thị khác nhau. ##### D. Khả năng diễn giải của trọng số Học tập đầu cuối cung cấp các tham số có thể diễn giải trong mỗi lớp. Ví dụ: trong Mạng chú ý đồ thị, trọng số chú ý đã học cho biết nút lân cận nào đóng góp nhiều nhất vào biểu diễn của nút. #### 3. Khó khăn và thách thức của lan truyền ngược đầu cuối trong GNN Mặc dù hiệu quả, lan truyền ngược đầu cuối trong GNN có một số thách thức và hạn chế: ##### A. Vấn đề làm mịn quá mức (Over-smoothing) Với GNN sâu, học tập đầu cuối có thể dẫn đến **vấn đề làm mịn quá mức**: khi độ sâu mạng tăng lên, nhúng nút có thể hội tụ về các giá trị tương tự nhau trên toàn bộ đồ thị, làm mất đi sự phân biệt giữa các nút khác nhau. Điều này xảy ra do khi thông tin lan truyền qua nhiều lớp, các nút kết hợp nhiều nút lân cận ở xa hơn, có khả năng làm mất các đặc điểm riêng lẻ của nút. ##### B. Gradient biến mất hoặc bùng nổ Trong GNN rất sâu, gradient có thể biến mất hoặc bùng nổ khi chúng lan truyền ngược qua nhiều lớp, đặc biệt là với một số hàm kích hoạt nhất định. Vấn đề này có thể cản trở sự hội tụ và dẫn đến kết quả học tập kém cho các mô hình sâu. ##### C. Chi phí bộ nhớ và tính toán cao Lan truyền ngược đầu cuối trong GNN **tốn nhiều bộ nhớ** vì tất cả nhúng nút, kết quả trung gian và gradient cần được lưu trữ cho mỗi lớp trong quá trình chuyển ngược. Điều này có thể trở nên khó khăn đối với các đồ thị lớn, đặc biệt là khi thực hiện xử lý hàng loạt trên các cấu trúc vùng lân cận lớn. #### 4. Độ phức tạp tính toán và phân tích lý thuyết Học tập đầu cuối trong GNN phức tạp về mặt tính toán do hai lý do chính: quá trình **tổng hợp vùng lân cận** và **tính toán gradient**. ##### A. Độ phức tạp của tổng hợp vùng lân cận Mỗi lớp trong GNN tổng hợp thông tin từ các nút lân cận, dẫn đến sự mở rộng về lượng dữ liệu được xử lý trên mỗi nút. Đối với đồ thị có$N$nút, độ phức tạp tính toán của chuyển tiếp của mỗi lớp phụ thuộc vào: - **Bậc nút trung bình ($d$)**: Xác định số lượng nút lân cận mà mỗi nút tổng hợp từ đó. - **Độ sâu tổng hợp ($K$)**: Xác định khoảng cách mà mỗi nút thu thập thông tin (tức là số lớp GNN). Chuyển tiếp trong lớp GNN thường có độ phức tạp thời gian là$O(N \times d)$. Tuy nhiên, đối với các đồ thị lớn, việc lưu trữ và tính toán trên tất cả các nút lân cận trong mỗi lớp trở nên khó khăn. ##### B. Độ phức tạp của lan truyền ngược Chuyển ngược bao gồm việc tính toán và lưu trữ gradient cho các tham số của mỗi nút và cạnh, có độ phức tạp tương đương với chuyển tiếp trong mỗi lớp. Với$L$lớp, độ phức tạp tổng thể cho một lần chuyển (chuyển tiếp và chuyển ngược) là khoảng$O(L \times N \times d)$, tỷ lệ tuyến tính với độ sâu và kích thước của đồ thị. Tuy nhiên, **sự tăng trưởng theo cấp số nhân của các nút lân cận** (lên đến$d^K$nút lân cận) có thể dẫn đến tính toán quá mức trong GNN sâu. ##### C. Kỹ thuật để quản lý độ phức tạp 1. **Phương pháp dựa trên lấy mẫu** (ví dụ: GraphSAGE): Thay vì tổng hợp trên tất cả các nút lân cận, chỉ một tập hợp con của các nút lân cận được lấy mẫu. Điều này làm giảm kích thước vùng lân cận hiệu quả và chi phí tính toán. 2. **Xử lý lô nhỏ**: Đối với đồ thị lớn, việc huấn luyện có thể được thực hiện trên đồ thị con hoặc lô nhỏ để hạn chế mức sử dụng bộ nhớ. 3. **Phương pháp tổng hợp lớp** (ví dụ: kết nối bỏ qua): Chúng cho phép thông tin từ các lớp trước đó bỏ qua các bước nhất định, giảm làm mịn quá mức và độ sâu tính toán. #### 5. Tốc độ hội tụ và các khía cạnh quan trọng của quy tắc học **Tốc độ hội tụ** của GNN phụ thuộc vào các yếu tố như tốc độ học, khởi tạo, cấu trúc đồ thị và điều chuẩn: ##### A. Tốc độ hội tụ 1. **Tốc độ học**: Tốc độ học cao hơn sẽ tăng tốc độ hội tụ nhưng có thể gây ra dao động hoặc mất ổn định, trong khi tốc độ học thấp hơn làm chậm tốc độ hội tụ nhưng cung cấp các bản cập nhật ổn định hơn. 2. **Cấu trúc đồ thị**: Đồ thị có kết nối cao hoặc dư thừa đôi khi có thể làm chậm tốc độ hội tụ vì mô hình phải học cách điều chỉnh cho thông tin lặp lại giữa các nút lân cận. 3. **Điều chuẩn**: Các kỹ thuật như dropout, suy giảm trọng số hoặc điều chuẩn chú ý có thể giúp giảm thiểu quá khớp (overfitting) và khuyến khích hội tụ mượt mà hơn. ##### B. Tầm quan trọng của quy tắc học Quy tắc học trong GNN rất quan trọng vì nó đảm bảo rằng nhúng kết hợp **biểu diễn nhận biết ngữ cảnh** nắm bắt cả đặc trưng nút và cấu trúc vùng lân cận. Các khía cạnh chính cần xem xét trong quy tắc học bao gồm: 1. **Cân bằng thông tin cục bộ và toàn cục**: Quy tắc học cho phép GNN kết hợp thông tin cục bộ (nút lân cận trực tiếp) với thông tin toàn cục (nút ở xa hơn) một cách có kiểm soát. 2. **Lựa chọn đặc trưng thông qua chú ý**: Các cơ chế chú ý được nhúng trong quy tắc học giúp chọn nút lân cận nào cung cấp nhiều thông tin nhất, cho phép mô hình giảm nhiễu và tập trung vào các mối quan hệ thiết yếu. 3. **Hiệu ứng lấy mẫu vùng lân cận**: Sử dụng các phương pháp dựa trên lấy mẫu để giảm gánh nặng tính toán cũng đưa tính ngẫu nhiên vào quy tắc học, điều này có thể giúp cải thiện khả năng khái quát hóa bằng cách cho mô hình tiếp xúc với các cấu trúc vùng lân cận khác nhau. #### Hình dung quá trình học **Hình dung bên** về học tập đầu cuối trong GNN có thể minh họa: 1. **Luồng thông tin theo từng lớp**: Hiển thị cách mỗi lớp tổng hợp thông tin, với các nút lân cận kết nối với nút tiêu cự trong mỗi lớp để thể hiện các trường tiếp nhận ngày càng tăng. 2. **Luồng gradient**: Cho biết gradient chạy ngược trở lại qua các lớp GNN, hiển thị nơi lỗi tác động nhiều nhất trong quá trình huấn luyện. 3. **Trọng số chú ý hoặc lựa chọn tổng hợp**: Hình dung nút lân cận nào được tính trọng số nhiều nhất trong các mô hình dựa trên chú ý. Hình dung như vậy giúp làm rõ cách thông tin lan truyền từ các nút lân cận đến các nút trung tâm và cách gradient được phân phối trên toàn bộ đồ thị, cho biết các nút hoặc lớp quan trọng trong quá trình học. #### Tóm tắt 1. **Lan truyền ngược đầu cuối** cho phép GNN học nhúng bằng cách lan truyền lỗi ngược trở lại từ lớp đầu ra qua từng lớp, tối ưu hóa tham số để giảm thiểu mất mát. 2. **Thuộc tính**: Lan truyền ngược trong GNN được hưởng lợi từ tổng hợp theo lớp, chia sẻ tham số và khả năng diễn giải nhưng phải đối mặt với những thách thức với làm mịn quá mức, chi phí bộ nhớ và độ phức tạp tính toán. 3. **Độ phức tạp tính toán**: Lan truyền ngược trong GNN là$O(L \times N \times d)$, tỷ lệ với số lớp, số nút và bậc trung bình nhưng có thể tăng theo cấp số nhân trong đồ thị lớn. 4. **Hội tụ và quy tắc học**: Tốc độ hội tụ phụ thuộc vào tham số học, cấu trúc đồ thị và điều chuẩn. Các khía cạnh chính bao gồm khả năng cân bằng thông tin cục bộ/toàn cục, chọn các nút lân cận cung cấp nhiều thông tin và điều chỉnh các phương pháp lấy mẫu để đạt hiệu quả. Hiểu và giải quyết các khía cạnh này là điều cần thiết để tối ưu hóa quá trình học của GNN, đạt được sự cân bằng giữa hiệu quả tính toán, sức mạnh biểu đạt và khả năng khái quát hóa. ## Giải thích các ký hiệu toán học Trong tài liệu này, chúng tôi đã sử dụng một số ký hiệu toán học để biểu diễn các khái niệm và công thức. Dưới đây là bảng giải thích ngắn gọn về các ký hiệu này: | Ký hiệu | Giải thích | | ----------------- | ---------------------------------------------------------------------------------------------- | | $G(V, E)$ | Đồ thị G với tập hợp các đỉnh V và tập hợp các cạnh E | | $V$ | Tập hợp các đỉnh trong đồ thị | | $E$ | Tập hợp các cạnh trong đồ thị | | $(u, v)$ | Một cạnh nối đỉnh u và đỉnh v | | $A$ | Ma trận kề của đồ thị | | $A_{ij}$ | Phần tử tại hàng i và cột j của ma trận kề, biểu thị sự tồn tại của cạnh giữa đỉnh i và đỉnh j | | $\mathbb{R}^d$ | Không gian vectơ d chiều | | $d$ | Số chiều của không gian nhúng | | $\mathbf{z}_v$ | Vectơ nhúng của đỉnh v | | $\mathsf{ENC}(v)$ | Mã hóa nút của đỉnh v | | $X_v$ | Vectơ đặc trưng của nút v | | $w_{uv}$ | Trọng số của cạnh (u, v) | | $\deg(v)$ | Bậc của nút v (số lượng cạnh kết nối với v) | | $f(x; \theta)$ | Mô hình GNN với tham số $\theta$ | | $L$ | Hàm mất mát | | $(x, y)$ | Đặc trưng đầu vào x và nhãn mục tiêu y | | $P_{\text{data}}$ | Phân phối dữ liệu | | $\mathbb{E}$ | Giá trị kỳ vọng | | $\sigma^2$ | Phương sai | | $\lambda$ | Hệ số điều chuẩn | ___ **Tài Liệu Tham Khảo**: 1. **General Overview of GNNs and End-to-End Backpropagation** - Kipf, T. N., & Welling, M. (2017). **Semi-supervised classification with graph convolutional networks**. In *Proceedings of the International Conference on Learning Representations (ICLR)*. This paper introduces the Graph Convolutional Network (GCN) and discusses how backpropagation is applied to optimize GNNs for semi-supervised learning tasks. [here](https://arxiv.org/pdf/1609.02907) - Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., ... & Weller, J. (2018). **Relational inductive biases, deep learning, and graph networks**. *arXiv preprint arXiv:1806.01261*. Provides a comprehensive overview of GNNs, relational inductive biases, and the role of end-to-end learning in various graph-based applications. [here](https://arxiv.org/pdf/1806.01261) 2. **Error Decomposition in GNNs: Bias, Variance, and Irreducible Error** - Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018). **Representation learning on graphs with jumping knowledge networks**. In *Proceedings of the 35th International Conference on Machine Learning (ICML)*. This paper addresses issues of over-smoothing and bias in GNNs and proposes techniques like skip connections to maintain node feature differentiation in deep layers. [here](https://arxiv.org/pdf/1806.03536) 3. **Common Loss Functions for GNNs and Structural Regularization** - Zhang, M., & Chen, Y. (2018). **Link prediction based on graph neural networks**. In *Advances in Neural Information Processing Systems (NeurIPS)*. Discusses binary cross-entropy loss and contrastive loss for link prediction tasks, as well as various structural regularization techniques in GNNs.[here](https://papers.nips.cc/paper_files/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf) - Kipf, T. N., & Welling, M. (2016). **Variational graph auto-encoders**. *arXiv preprint arXiv:1611.07308*. This paper introduces contrastive loss in the context of graph autoencoders and explains structural regularization techniques to preserve graph features during embedding. [here](https://arxiv.org/pdf/1611.07308) 4. **Computational Complexity in GNNs and Efficient Learning Techniques** - Hamilton, W. L., Ying, R., & Leskovec, J. (2017). **Inductive representation learning on large graphs**. In *Advances in Neural Information Processing Systems (NeurIPS)*. This paper introduces the GraphSAGE model, which uses neighborhood sampling to reduce computational complexity and improve scalability for large graphs. [here](https://papers.nips.cc/paper_files/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf) - Chen, J., Ma, T., & Xiao, C. (2018). **FastGCN: Fast learning with graph convolutional networks via importance sampling**. In *International Conference on Learning Representations (ICLR)*. FastGCN presents sampling-based methods to manage the computational costs of neighborhood aggregation in large graphs. [here](https://arxiv.org/pdf/1801.10247) 5. **Over-Smoothing in Deep GNNs and Solutions to Improve Convergence** - Li, Q., Han, Z., & Wu, X.-M. (2018). **Deeper insights into graph convolutional networks for semi-supervised learning**. In *Thirty-Second AAAI Conference on Artificial Intelligence (AAAI)*. This paper discusses the over-smoothing phenomenon in GNNs and analyzes the limitations of deeper GNNs, providing insights into architectural adjustments to address these issues. [here](https://cdn.aaai.org/ojs/11604/11604-13-15132-1-2-20201228.pdf) - Rong, Y., Huang, W., Xu, T., & Huang, J. (2020). **DropEdge: Towards deep graph convolutional networks on node classification**. In *International Conference on Learning Representations (ICLR)*. DropEdge proposes a regularization technique to mitigate over-smoothing by randomly removing edges during training, thus preserving node distinction across layers. [here](https://arxiv.org/pdf/1907.10903) 6. **Learning Principles and Convergence in GNNs** - Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2018). **Graph attention networks**. In *International Conference on Learning Representations (ICLR)*. This paper introduces attention-based GNNs, which help in learning relevant node dependencies and offer insights into convergence dynamics through attention weights.[here](https://arxiv.org/pdf/1710.10903) - Kingma, D. P., & Ba, J. (2014). **Adam: A method for stochastic optimization**. *arXiv preprint arXiv:1412.6980*. Adam optimizer is commonly used in training GNNs and aids in achieving stable convergence by adaptively adjusting the learning rate for each parameter. [here](https://arxiv.org/pdf/1412.6980) 7. **End-to-End Learning in Graph-Based Models: Visualizations and Interpretability** - Ying, Z., Bourgeois, D., You, J., Zitnik, M., & Leskovec, J. (2019). **GNNExplainer: Generating explanations for graph neural networks**. In *Advances in Neural Information Processing Systems (NeurIPS)*. Provides methods for visualizing and interpreting the layers of GNNs to understand feature and neighbor importance in end-to-end learning.[here](https://arxiv.org/pdf/1903.03894) - Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018). **Modeling relational data with graph convolutional networks**. In *European Semantic Web Conference*. This paper explains relational modeling in GNNs, discussing interpretability of learned representations and visualizing how relationship types affect node embeddings.[here](https://arxiv.org/pdf/1703.06103)

4.1 I.Phân tích loại đồ thị \(G(V, E)\)