Graph Embedding là một nhánh các phương pháp biểu diễn đồ thị dưới dạng véc tơ. Đồ thị là một cách biểu diễn dữ liệu đặc biệt trong khoa học máy tính. Dựa trên cách biểu diễn này, chúng ta có thể sử dụng các tính chất trên đồ thị để khai phá dữ liệu, chứng minh và kiểm chứng các bài toán được đặt ra đối với dữ liệu đầu vào. Bên cạnh đó, những năm gần đây, machine learning (và đặc biệt là deep learning) chứng minh được sức mạnh của mình thông qua việc biểu diễn dữ liệu thông qua không gian véc tơ. Graph embedding là một nỗ lực kết hợp sức mạnh của biểu diễn đồ thị và các kỹ thuật machine learning.

Mục tiêu của Graph embedding

Mục tiêu của graph embedding là thay vì biểu diễn các nút trong đồ thị một cách riêng lẻ, phương pháp này tạo ra ánh xạ thể hiện được cả mối quan hệ của các nút trong đồ thị. Nói một cách khác, các véc tơ nhúng của nút sẽ được tính toán dựa trên vị trí tương đối của nó với các nút liên quan và lân cận trên đồ thị. Các nút tương tự trong đồ thị sẽ có khoảng cách gần nhau hơn trong không gian véc tơ.

Các nút tương tự trong graph embedding

Đối với một câu, chúng ta có thể sử dụng các từ xung quanh một từ để định nghĩa ngữ cảnh cho nó (ý tưởng của n-gram). Tương tự n-gram, chúng ta có thể định nghĩa ngữ cảnh của một nút trong đồ thị. Tuy nhiên, chúng ta sẽ có nhiều lựa chọn hơn vì các kết nối của đồ thị đa dạng hơn so với một chuỗi các từ.

Chúng ta có thể biểu diễn đồ thị dưới dạng một ma trận kề, và với mỗi nút, ta có nhiều phương án khác nhau để định nghĩa ngữ cảnh của nút đó.

Thông thường, có hai phương pháp độc lập để biểu diễn ngữ cảnh trong graph embedding

1. Theo chiều rộng (BF): Cách duyệt này ưu tiên các nút lân cận với nút đang xét trước và loang dần ra các nút xa hơn. Giả định của cách duyệt này là các nút tương tự trong đồ thị thì có mối quan hệ chặt chẽ hơn.
2. Theo chiều sâu (DF): Cách duyệt này duyệt qua hết một nhánh của nút đang xét trước khi tiếp tục với nhánh tiếp theo. Cách duyệt này quan tâm nhiều hơn đến đóng góp của một nút trong cấu trúc của đồ thị.

Chúng ta có thể sử dụng hai cách duyệt này, kết hợp chúng hoặc đề xuất cách duyệt phù hợp với dữ liệu của mình. Khi đã có được tập hợp các nút biểu diễn ngữ cảnh của mỗi nút, ta có thể so sánh được độ tương đồng ngữ cảnh giữa hai nút. Đơn giản nhất, ta có thể dùng độ đo Jaccard để xem hai tập hợp chồng lấn lên nhau với mức độ ra sao.

Lấy mẫu ngữ cảnh

Ý tưởng là như vậy, tuy nhiên, chúng ta không thể lấy mẫu toàn bộ ngữ cảnh của một nút vì như vậy sẽ dẫn tới việc phải xét đến toàn bộ đồ thị. Điều này là bất khả thi trên khía cạnh tính toán đối với dữ liệu lớn. Do đó chúng ta cần có một chiến lược lấy mẫu phù hợp. Ý tưởng đơn giản nhất là thực hiện một số bước đi ngẫu nhiên từ nút gốc để lấy ra một mẫu ngẫu nhiên.

Tiếp theo, thay vì sử dụng phép đo Jaccard đơn giản như đã đề cập phía trên, chúng ta có thể tính toán các giá trị véc tơ số cho mỗi nút và tối ưu hàm ánh xạ để gán các nút tương tự lại gần nhau. Đây cũng là ý tưởng của node2vec.

Trên đây là những ý tưởng cơ bản để bạn có thể hiểu được cách thức các phương pháp graph embedding hoạt động. Như đối với các nút, chúng ta có thể áp dụng chiến lược tương tự để ánh xạ các cạnh trong đồ thị vào không gian embedding. Mặc dù là một ý tưởng thú vị, độ phức tạp tính toán và các chiến lược lấy mẫu, chiến lược tìm kiếm trên đồ thị vẫn là các câu hỏi khó khi áp dụng graph embedding vào các bài toán thực tế.

Hi vọng thông qua bài viết này, các bạn đã hiểu thêm về graph embedding, phương pháp biểu diễn đồ thị dưới dạng véc tơ. Nếu bạn thấy bài viết hữu ích, hãy chia sẻ với những người quan tâm và truy cập Cộng đồng Trí tuệ nhân tạo để cùng thảo luận các vấn đề chuyên sâu về lĩnh vực này.