Chương 1 cũng đã nêu bật những khía cạnh quan trọng khi nghiên cứu về đồ thị học sâu và phát hiện cộng đồng trong chúng, bao gồm đa dạng về lớp, sự kết nối giữa các lớp, và ứng dụng thực tế trong nhiều lĩnh vực. Chương tiếp theo sẽ tập trung vào việc xem xét các phương pháp và ứng dụng cụ thể liên quan đến các khái niệm này, giúp chúng ta hiểu sâu hơn về cách nghiên cứu và áp dụng chúng trong thực tế. 8 Chương 2 Ứng dụng học sâu trên đồ thị trong phát hiện cộng đồng Chương 2 tập trung vào khía cạnh lý thuyết và định nghĩa vấn đề, đồng thời đánh giá giới hạn của mạng tích chập đồ thị GCN và các phương pháp truyền thống khác. Chương này cũng so sánh sự khác biệt giữa phân vùng ngẫu nhiên và phân vùng phân cụm, bao gồm cả sự hình thành của thuật toán Cluster-GCN , cũng như những thách thức khi đào tạo mạng tích chập đồ thị học sâu.
Dựa trên những kiến thức này, chương 2 xây dựng nền tảng quan trọng cho việc thực hiện các thực nghiệm trong Chương 3. Định nghĩa bài toán Cho một đồ thị có thuộc tính vô hướng G = (V, E, X), trong đó V = {v1 , v2 , ., vn } là tập hợp gồm n đỉnh và E là tập hợp các cạnh với eij = (vi , vj ) ∈ E nếu có một cạnh nối giữa các đỉnh vi và vj , và X = {x1 , x2 , ., xn } ∈ Rn×F là ma trận thuộc tính, trong đó mỗi đỉnh vi được kết nối với một vector thuộc tính xi có kích thước F. Mục tiêu là gán mỗi đỉnh vào một tập hợp riêng biệt và không chồng chéo C dựa trên cả cấu trúc của đỉnh và thuộc tính của chúng. Mạng tích chập đồ thị GCN đã chứng tỏ được sự thành công đáng kể trong nhiều lĩnh vực, đặc biệt là trong các nhiệm vụ như phân loại đỉnh và dự đoán liên kết.
GCN tận dụng cấu trúc đồ thị cơ bản để học các biểu diễn ý nghĩa cho các đỉnh, từ đó giúp phân loại chính xác các đỉnh và dự đoán các liên kết trong đồ thị. Hơn nữa, GCN gần đây cũng đã được ứng dụng để phân cụm các đỉnh trong các đồ thị có thuộc tính. Các biểu diễn được học bởi GCN có thể được sử dụng như một phần của quá trình phân cụm dữ liệu, sau khi dữ liệu đã được phân cụm ban đầu bằng một phương pháp như METIS (sẽ được giải thích trong phần Cluster-GCN ). Trong bối cảnh này, các biểu diễn được học bởi GCN có thể được sử dụng 9 làm đầu vào cho các nhiệm vụ phân cụm dữ liệu, giúp khám phá cấu trúc cộng đồng trong đồ thị.
Mạng nơ-ron đồ thị (GNN), trong đó GCN là một phần, bao gồm một gia đình rộng hơn của các mô hình mạng nơ-ron được thiết kế cho dữ liệu dựa trên đồ thị. GNNs, nói chung, đã mở ra cách tiếp cận đầy sáng tạo để tận dụng dữ liệu đồ thị cho các nhiệm vụ khác nhau, bao gồm các hệ thống gợi ý, phát hiện bất thường và phân tích mạng xã hội. Đề án này đề cập một số phương pháp tận dụng GCN và khả năng của chúng trong phân loại, phân cụm và các kỹ thuật GNN liên quan để giải quyết các vấn đề phức tạp dựa trên đồ thị. Xây dựng đồ thị 2.
Định nghĩa mạng (a) (b) Hình 2.1: được trích dẫn từ [11] (a) hình minh họa đồ thị trong đó các nút biểu thị người dùng trong mạng xã hội. (b) Hình minh họa về hai cộng đồng (C1 và C2 ) dựa trên dự đoán nghề nghiệp của người dùng. Việc phát hiện sử dụng sự tương đồng của người dùng trong các hoạt động trực tuyến (cấu trúc liên kết) và hồ sơ tài khoản (thuộc tính). • Cho một mạng cơ bản G = (V, E), trong đó V = v1 ,.
, vn là tập nút với E = {eij }nn j=1 đại 2 diện cho tập cạnh giữa các nút. N(W] = {U ∈ V |(W , u) ∈ E⟩ xác định vùng lân cận của một nút vi. A = [aij ] biểu thị ma trận kề n × n chiều, trong đó aij = 1 nếu ϵij ∈ E, ngược lại aij = 0. Nếu aij ̸= aji , G là mạng có hướng, nếu không thì đó là mạng vô hướng.
Nếu aij là có trọng số bởi wij ∈ W, G = (V, E, W ) là mạng có trọng số, mặt khác, nó là một mạng không có trọng số. Nếu giá trị của aij khác nhau trong +1 (dương) và −1 (âm), G là mạng đã được định nghĩa. Nếu nút vi ∈ V được gán bởi xi ∈ X ⊆ Rn×d , G = (V, E, X) là mạng được phân bổ, nếu không thì đó là mạng không được phân bổ. Biểu diễn đồ thị • Trước khi bắt đầu thảo luận về các hoạt động mạng thần kinh cụ thể trên đồ thị, chúng ta nên xem xét cách biểu diễn đồ thị.
Về mặt toán học, một đồ thị G được định nghĩa là một bộ gồm một tập các nút/đỉnh V và một tập các cạnh/đường liên kết E:G = (V, E). Mỗi cạnh là một cặp gồm hai đỉnh và biểu thị một kết nối giữa chúng. Chẳng hạn, hãy xem đồ thị sau: Các đỉnh là V = {1, 2, 3, 4}, và các cạnh E = {(1, 2), (2, 3), (2, 4), (3, 4)}. Lưu ý rằng để đơn giản, chúng ta giả sử đồ thị là vô hướng và do đó không thêm các cặp đối xứng.
Trong ứng dụng, các 10 Hình 2. đỉnh và cạnh thường có thể có các thuộc tính cụ thể và các cạnh thậm chí có thể được định hướng. Câu hỏi đặt ra là làm thế nào chúng ta có thể biểu diễn sự đa dạng này một cách hiệu quả cho các phép toán ma trận. Thông thường, đối với các cạnh, chúng ta quyết định giữa hai biến thể: ma trận kề hoặc danh sách các chỉ số đỉnh được ghép nối.
Ma trận kề A là một ma trận vuông có các phần tử cho biết các cặp đỉnh có kề nhau hay không, tức là có liên thông hay không. Trong trường hợp đơn giản nhất, Aij là 1 nếu có kết nối từ nút i đến j và ngược lại là 0. 1 nếu có kết nối từ nút i đến j Aij = (2.1) 0 ngược lại Nếu chúng ta có các thuộc tính cạnh hoặc các loại cạnh khác nhau trong đồ thị, thông tin này cũng có thể được thêm vào ma trận. Đối với đồ thị vô hướng, hãy nhớ rằng A là ma trận đối xứng (Aij = Aji ).
Đối với đồ thị ví dụ trên, chúng ta có ma trận kề sau: 0 1 0 0 1 0 1 1 A= 0 1 0 1 0 1 1 0 Trong khi biểu diễn một đồ thị dưới dạng một danh sách các cạnh sẽ hiệu quả hơn về mặt bộ nhớ 11 và (có thể) tính toán, thì việc sử dụng ma trận kề sẽ trực quan hơn và đơn giản hơn để thực hiện. Định nghĩa cộng đồng Cho một tập hợp các cộng đồng C = {C1 , C2 , · · · , CK}, mỗi cộng đồng Ck là một phân hoạch của G trong đó giữ cấu trúc khu vực và tính chất cụm. một nút vi tập hợp thành quần xã vk nên thỏa mãn điều kiện mức độ nút nội bộ bên trong cộng đồng vượt quá mức của nó bằng cấp bên ngoài. Giả sử Ck ∩ Ck′ = ∅, (∀k.
k ′ ), C ký hiệu cộng đồng rời rạc; các cộng đồng chồng chéo khác. Đầu vào phát hiện cộng đồng Các mô hình học học sâu có đầu vào như cấu trúc liên kết mạng và thuộc tính mạng. Các cấu trúc liên kết được hình thành bởi các nút và các cạnh có thể được biểu diễn bằng các ma trận như ma trận kề ki kj A, ma trận kề có dấu A(+, -) và các ma trận đo lường như tính mô đun ma trận B (bij = aij − 2m ). Thuộc tính mạng biểu thị thông tin bổ sung trên các thực thể mạng chẳng hạn như thuộc tính nút X.
Kết quả phát hiện cộng đồng Phương pháp phát hiện cộng đồng nhằm mục đích tạo ra một tập hợp các cộng đồng có thể là rời rạc hoặc chồng chéo. Đầu ra khác nhau bằng cách sử dụng các phương pháp phát hiện cộng đồng khác nhau. Cộng đồng rời rạc, ví dụ: câu lạc bộ sinh viên cho phép một sinh viên chỉ tham gia một câu lạc bộ. Cộng đồng chồng chéo, ví dụ: người dùng tham gia trong một số vòng kết nối trong mạng xã hội.
Các phương pháp cho các cộng đồng chồng chéo có thể phát hiện các cộng đồng rời rạc. Mạng tích chập đồ thị GCN tổng hợp thông tin nút của vùng lân cận trong các lớp tích chập của đồ thị học học sâu để nắm bắt toàn cục các đặc trưng phức tạp để phát hiện cộng đồng (hình 2. có hai phương pháp phát hiện cộng đồng dựa trên GCN: (1) phân loại cộng đồng được giám sát/bán giám sát và (2) phân cụm cộng đồng với đại diện mạng không giám sát. Phương pháp phân loại cộng đồng bị hạn chế do thiếu nhãn trong thực tế.
Để so sánh, các biểu diễn mạng linh hoạt hơn đối với các nhóm cộng đồng thông qua các kỹ thuật như tái tạo ma trận và tối ưu hóa khách quan. GCN sử dụng một số phương pháp phát hiện cộng đồng truyền thống như toán tử đồ thị học sâu (deep graph operators), chẳng hạn như SBM để suy luận thống kê, ma trận Laplacian để phân tích phổ và các mô hình đồ họa xác suất truyền bá thông tin. Ví dụ, Mạng nơ-ron đồ thị đường kẻ (LGNN) là một mô hình mạng giám sát phát hiện cộng đồng, giúp cải thiện SBM với hiệu suất phát hiện cộng đồng tốt hơn và giảm chi phí tính toán. Tích hợp toán tử không quay lui với quy tắc truyền thông điệp của lan truyền tới, LGNN học các đặc trưng của nút được đại diện trong các mạng có hướng.
Hàm kích hoạt (softmax) xác định xác suất có điều kiện mà một nút 12 vi thuộc về với cộng đồng Ck (oi,k = p(yi = ck |Θ, G), và cực tiểu hóa loss (cross-entropy loss) trên tất cả các hoán vị có thể có SC của nhãn cộng đồng: X L(Θ) = min − log oi,π (yi )· (2.2) π∈SC i Vì GCN ban đầu không được thiết kế cho nhiệm vụ phát hiện cộng đồng, cấu trúc cộng đồng không phải là trọng tâm trong cách học nhúng nút.