Neural network là 1 khái niệm vô cùng quen thuộc trong học máy, và graph (đồ thị) là 1 dạng cấu trúc dữ liệu vô cùng cơ bản để lưu trữ thông tin. Trong những năm gần đây, việc sử dụng các giải thuật học máy đang rất phát triển, và trong bài viết này chúng ta sẽ đề cập đến việc áp dụng neural network cho graph.
Trong bài viết đầu tiên này, chúng ta sẽ quay trở lại các khái niệm graph, neural network và sự khác biệt khi sử dụng graph như 1 đầu vào với viêc sử dụng các kiểu input truyền thống ( ảnh, văn bản hay các dạng structured data khác ). Ở bài viết thứ 2, chúng ta sẽ cùng nhau implement 1 giải thuật neural network dành cho graph.
Bài viết này sẽ gồm 3 phần:
1. Nhắc lại kiến thức cơ bản về graph - đồ thị
2. Các loại bài toán machine learning dành cho graph
3. Ý tưởng cơ bản của graph neural network - sư khác nhau với các mô hình neural network thông thường
1.Nhắc lại kiến thức cơ bản về graph - đồ thị
a. Đồ thị
1 đồ thị là 1 tập hợp các điểm (vertex), trong đó mỗi cặp điểm có thể không được kết nối hoặc được nối bởi một hoặc nhiều cạnh (edge).
Đồ thị xuất hiện khắp nơi trong cuộc sống. Mạng lưới bạn bè trong facebook chính là 1 đồ thị khổng lồ, trong đó chúng ta có thể xem mỗi cá nhân là 1 điểm, và mối quan hệ giữa các cá nhân trong đồ thị được biểu diễn là thông qua các cạnh nối các điểm với nhau. Chúng ta có thể viết mã giả như sau:
If A and B is friend, then connect(A,B) = 1, else0 b. Đồ thị có trọng số - không có trọng số:
đồ thị mà mỗi cạnh đều được gán một giá trị riêng biệt khác nhau. Với đồ thị không có trọng số, tất cả các cạnh đều có trọng số giống nhau, thông thường tất cả các cạnh sẽ có trọng số = 1.
Ví dụ: Nếu A và B là bạn trên facebooks, vậy thì trọng số của cạnh giữa 2 điểm A và B trong đồ thị có thể định nghĩa là số post có tags chung cả 2 người.
c. Đồ thị có hướng- vô hướng:
Trong đồ thị vô hướng, nếu tồn tại cạnh giữa 2 điểm (u, v)ta có thể suy ra đồ thị cũng có cạnh (v,u) và ngược lại. Nói một cách khác, đồ thị vô hướng là đồ thị mà trong đó, mọi cạnh (u,v) là 2 chiều; ta có thể đi từ u đến v và từ v đến u Với đồ thị có hướng, ta không thể làm phép suy như trên.
2. Các bài toán Machine Learning cho Graph:
Nhìn vào cấu trúc dữ liệu như trên, chúng ta có thể thấy kha khá các bài toán cho đồ thị cần sự có mặt của Machine Learning:
a. Node classification:
Giả sử chúng ta có 1 đồ thị trong đó mỗi điểm có thể là sinh viên hoặc giảng viên của nhà trường, 1 cạnh giữa 2 điểm tồn tại nếu 2 người đó từng cùng xuất hiện trong 1 lớp học. Chúng ta chỉ biết giá trị nhãn ( sinh viên-giảng viên ) của 1 vài điểm trong đồ thị, liệu chúng ta có thể dựa vào đó để dự báo nhãn ( sinh viên-giảng viên ) của những node chưa biết không?
Trong hình bên dưới, các bạn có thể hình dung các điểm màu tím là sinh viên, màu vàng là giảng viên, các điểm màu xám là điểm cần dự báo
b. Link prediction:
Chúng ta có 1 đồ thị giữa các thành viên trong 1 lớp học tiếng Anh - các thành viên này thường được ghép đôi thành 1 nhóm để thực hiện bài tập. Cạnh của đồ thị được quy ước như sau:
- nếu 2 người từng chung 1 nhóm và nhóm đó đạt điểm cao, chúng ta sẽ quy định cạnh của 2 điểm đó là +1 ( positive ).
- nếu 2 người từng chung 1 nhóm và nhóm đó đạt điểm thấp, chúng ta quy định cạnh của 2 điểm đó là -1 ( negative ).
- Bây giờ nếu chúng ta thực hiện việc ghép nhóm giữa 2 người chưa từng chung nhóm với nhau bao giờ, liệu chúng ta có thể dự báo là nhóm đó sẽ đạt điểm cao hay thấp ko ? Nói cách khác, chúng ta đang muốn dự báo cạnh giữa 2 điểm trong đồ thị sẽ là positive hay negative
Ngoài ra chúng ta còn có 1 số bài toán khác như là Community detection, Network similarity, .... các bạn có thể tự tìm hiểu thêm
3.Ý tưởng cơ bản của graph neural network - sư khác nhau với các mô hình neural network thông thường
Giả sử chúng ta có 1 bài toán node classification như sau: chúng ta có 1 đồ thị mạng xã hội của các cử tri gồm 1000 người, với mỗi node là 1 người, 1 node có thể có các thuộc tính như là tuổi, giới tính, thu nhập, quê quán, ....Tồn tại 1 cạnh giữa 2 người nếu như 2 người đó là bạn bè trên mạng xã hội. Trong đó chúng ta, biết chắc chắn 100 người sẽ vote cho đại biểu nào- họ đã vote từ trước, còn 900 người khác chúng ta chưa biết sự lựa chọn của họ, vậy thì liệu chúng ta có thể dự báo được họ sẽ vote cho đại biểu nào ko ?
Chúng ta có thể mô hình hóa đầu vào bài toán như sau:
* 1 đồ thị có n điểm, mỗi điểm trong đồ thị có m features, vậy là chúng ta sẽ có 1 ma trận (n, m) để biểu diễn các điểm trong đồ thị. Chúng ta gọi ma trận này là X
* Các cạnh trong đồ thị được biểu diễn bằng 1 ma trận vuông (n,n) trong đó giá trị của 1 ô vuông có tọa độ (i, j) trong ma trận được đánh nhãn là 1 nếu điểm j và j có kết nối qua cạnh với nhau, còn lại bằng 0. Chúng ta gọi ma trận này là Y.
a.Nhược điểm của các mô hình neural network truyền thống với dạng bài toán đồ thị
Nếu như chúng ta dự báo bài toán này với 1 classification neural network thông thường, cách làm chúng ta nghĩ đến sẽ là encode mỗi người với các thông tin của họ như là tuổi tác, giới tính, thu nhập tạo thành 1 bộ traning data, sau đó chúng ta dùng 100 người đã vote làm training data để tạo ra 1 model. Sau đó chúng ta dùng model đó để dự báo cho 900 người còn lại. Như vậy, thực chất là chúng ta đang cố gằng tìm 1 hàm dự báo dựa trên các thông tin cá nhân của 1 người, và chúng ta bỏ qua các thông tin về mối quan hệ của người đó với những người khác. Nói cách khác, chúng ta đang chỉ sử dụng ma trận X chúng ta đã định nghĩa ở phía trên, nhưng lại bỏ qua ma trận Y. Tuy nhiên, thông tin về mối quan hệ có thể là thông tin quan trọng hơn rất nhiều, ví dụ như khi tất cả bạn bè của tôi đều vote cho đại biểu A, thì nhiều khả năng tôi cũng sẽ là người vote cho đại biểu A.
Vậy với bài toán node classification, 1 mô hình neural network truyền thống sẽ có 1 nhược điểm rất lớn khi chúng ta sử dụng để dự báo đồ thị: nó bỏ qua tất cả các kết nối giữa các điểm trong đồ thị đó. Nói cách khác, sự dự báo của chúng ta chỉ đơn thuần dựa vào các features của chính bản thân node đó, mà không xét đến mối quan hệ với các node xung quanh
b. Cách khắc phục bằng graph neural network
Đầu tiên, , sự khác biệt lớn nhất chúng ta cần phải thấy, đó là input của mô hình graph neural network không chỉ có duy nhất các features của node dùng để dự báo như các mô hình truyền thống, nó yêu cầu chúng ta phải có thêm cả sự mô tả các kết nối các điểm với nhau nữa. 1 mô hình graph network đòi hỏi phải có 2 ma trận đầu vào, 1 ma trận biểu diễn encoding của các điểm trong đồ thị( ma trận X chúng ta định nghĩa phía trên), và thêm 1 ma trận khác để biểu diễn kết nối các điểm ( chính là ma trận Y chúng ta định nghĩa phía trên )
Vậy ma trận Y biểu diễn kết nối giữa các node được sử dụng như thế nào ?Chúng ta có thể tóm tắt trong 1 câu ngắn gọn: enbedding của 1 node không chỉ dựa vào các features của chính bản thân node đó, nó còn đồng thời dựa vào các features của các node xung quanh nữa Hãy cùng nhìn vào đồ thị sau để thấy rõ hơn, khi chúng ta dự báo giá trị của 1 node với mô hình graph neural network với 3 layers:
Nhìn vào đồ thị trên, chúng ta có thể thấy node A là node đang cần được predict, nó có kết nối với các node B, C, D. XA, XB, XC, ... chính là các features của từng node. qua từng lớp layers, node embedding được tạo ra từ các features của các node xung quanh. Bởi vậy nó khắc phục được nhược điểm của các mô hình truyền thống khi không hề sử dụng thông tin của các node xung quanh mình để phục vụ cho việc predict
Vậy là các bạn đã có thể hiểu qua được ý tưởng của graph neural network. Trong bài thứ 2, chúng ta sẽ cùng nhau thực hiện implement bằng python
