Thực chiến Siêu đồ thị: Triển khai Phân cụm phổ và Nhúng nút bằng Python (kèm mã nguồn đầy đủ)

Gần đây, khi phân tích dữ liệu của một nhóm xã hội, tôi đã gặp một vấn đề điển hình: các mô hình đồ thị truyền thống dường như "bất lực". Chúng ta quen thuộc với việc mô hình hóa mạng xã hội bằng các mối quan hệ cặp đôi như "ai là bạn của ai", nhưng các tương tác nhóm trong thực tế thường phức tạp hơn nhiều. Ví dụ, một nhóm đọc sách trực tuyến có thể bao gồm mười mấy thành viên, và một sự kiện hội thảo ngoại tuyến có thể kết nối nhiều người tham gia từ các công ty khác nhau. Loại mối quan hệ "một-nhiều" hoặc "nhiều-nhiều" này, nếu được mô tả bằng các cạnh (chỉ có thể kết nối hai nút), sẽ làm mất đi một lượng lớn thông tin cấu trúc quan trọng. Điều này giống như cố gắng sử dụng một kịch bản chỉ mô tả cuộc trò chuyện giữa hai người để tái hiện toàn bộ động lực của một cuộc thảo luận bàn tròn nhiều người, chắc chắn sẽ gặp khó khăn.

Lúc này, **siêu đồ thị (Hypergraph)** đã xuất hiện trong tầm nhìn của tôi. Nó cho phép một "siêu cạnh" (hyperedge) kết nối một số lượng tùy ý các đỉnh, phù hợp hoàn hảo với nhu cầu mô tả các mối quan hệ nhóm. Từ mạng hợp tác nghiên cứu, hệ thống người dùng-thẻ hàng hóa trong thương mại điện tử, đến các tương tác phức hợp protein trong sinh vật, siêu đồ thị cung cấp một cách mô hình hóa tự nhiên hơn, mất mát thông tin ít hơn. Tuy nhiên, vẻ đẹp lý thuyết như thế nào để có thể thực thi thành mã nguồn có thể chạy được? Đặc biệt là làm thế nào để mở rộng thuật toán **phân cụm phổ (Spectral Clustering)** kinh điển từ đồ thị thông thường sang siêu đồ thị, và sau đó tạo ra **nhúng (Embedding)** chiều thấp của nút, để sử dụng cho các tác vụ **phân cụm (Clustering)** hoặc **phân loại (Classification)** ở hạ lưu? Đây chính là vấn đề cốt lõi mà bài viết này sẽ giải quyết.

Bài viết này sẽ hoàn toàn bỏ qua việc chồng chất các công thức phức tạp, bắt đầu từ góc nhìn của một nhà khoa học dữ liệu, và hướng dẫn bạn từng bước triển khai siêu đồ thị bằng Python, bao gồm việc xây dựng siêu đồ thị, tính toán toán tử Laplace của siêu đồ thị, giải quyết phân cụm phổ và tạo nhúng nút. Chúng ta sẽ sử dụng một tập dữ liệu mạng xã hội thực tế và đính kèm mã nguồn hoàn chỉnh, có thể tái tạo cho mỗi đoạn. Dù bạn muốn khám phá mô hình hóa các mối quan hệ phức tạp hay cần áp dụng các công cụ phân cụm mạnh mẽ hơn trong dự án, bài viết này sẽ cung cấp một con đường thực hành rõ ràng.

1. Hiểu về Siêu đồ thị: Công cụ mô hình hóa vượt qua mối quan hệ cặp đôi

Trước khi đi vào mã nguồn, chúng ta cần củng cố nền tảng khái niệm. Đồ thị thông thường (Graph) là một trường hợp đặc biệt của siêu đồ thị, trong đó mỗi cạnh chỉ có thể liên kết hai đỉnh. Điểm đột phá cốt lõi của siêu đồ thị nằm ở chỗ, các cạnh của nó (gọi là siêu cạnh, Hyperedge) là một tập con bất kỳ của các đỉnh. Điều này có nghĩa là một siêu cạnh có thể liên kết hai, ba, thậm chí hàng trăm đỉnh.

Hãy tưởng tượng một ví dụ đơn giản: có ba bài báo A, B, C, được hai tác giả甲 và 乙 hoàn thành. Tác giả甲 viết A và B, tác giả乙 viết B và C. Nếu dùng đồ thị thông thường để mô hình hóa:

• Đỉnh: Bài báo A, B, C.
• Cạnh: Nếu hai bài báo có cùng tác giả, thì nối cạnh.
• Kết quả: A-B được nối (cùng tác giả甲), B-C được nối (cùng tác giả乙), A và C không có cạnh trực tiếp. Điều này đã làm mất thông tin về mối quan hệ nhóm rõ ràng "tác giả甲 cùng liên kết A và B".

Nếu dùng siêu đồ thị để mô hình hóa:

• Đỉnh: Bài báo A, B, C.
• Siêu cạnh: Hai siêu cạnh. Siêu cạnh e1 = {A, B} (đại diện cho tác giả甲), siêu cạnh e2 = {B, C} (đại diện cho tác giả乙).
• Kết quả: Mối quan hệ nhóm được giữ nguyên vẹn. Chúng ta có thể gán trọng số cho siêu cạnh, ví dụ, dựa trên tầm quan trọng của tác giả hoặc độ chuyên môn trong lĩnh vực để đặt `w(e1)` và `w(e2)`.

Siêu đồ thị thường được biểu diễn toán học bằng **ma trận liên kết H**. Giả sử có `|V|` đỉnh và `|E|` siêu cạnh, **H** là một ma trận `|V| x |E|`, trong đó `H[v, e] = 1` khi và chỉ khi đỉnh `v` thuộc siêu cạnh `e`, ngược lại là 0.

import numpy as np

# Ví dụ: 3 đỉnh (V0, V1, V2), 2 siêu cạnh (E0, E1)
# E0 chứa V0, V1
# E1 chứa V1, V2
vertices = ['V0', 'V1', 'V2']
hyperedges = ['E0', 'E1']
incidence_matrix = np.array([
    [1, 0],  # V0 thuộc E0, không thuộc E1
    [1, 1],  # V1 thuộc E0 và E1
    [0, 1]   # V2 không thuộc E0, thuộc E1
])
print("Ma trận liên kết H:")
print(incidence_matrix)
# Kết quả:
# [[1 0]
#  [1 1]
#  [0 1]]

Với ma trận liên kết H và vector trọng số siêu cạnh w (thường tạo thành ma trận đường chéo **W**), chúng ta có thể định nghĩa hai ma trận đối góc quan trọng trong siêu đồ thị:

• Ma trận độ đỉnh D_v: Phần tử đường chéo `D_v[i,i]` là bậc của đỉnh i, bằng tổng trọng số của tất cả các siêu cạnh chứa đỉnh i. Công thức tính: `D_v = diag(H * W * 1)`, trong đó 1 là vector toàn 1.
• Ma trận độ siêu cạnh D_e: Phần tử đường chéo `D_e[j,j]` là bậc của siêu cạnh j, bằng số lượng đỉnh mà siêu cạnh đó chứa. Công thức tính: `D_e = diag(1^T * H)`.

# Giả sử trọng số của hai siêu cạnh lần lượt là 0.8 và 1.2
hyperedge_weights = np.diag([0.8, 1.2])
print("Ma trận trọng số siêu cạnh đường chéo W:")
print(hyperedge_weights)

# Tính ma trận độ đỉnh D_v
# H shape: (3,2), W shape: (2,2), 1 shape: (2,)
ones_vector_hyperedges = np.ones((incidence_matrix.shape[1], 1)) # Vector cột
D_v_diag = incidence_matrix @ hyperedge_weights @ ones_vector_hyperedges # Lấy độ của mỗi đỉnh (vector cột)
vertex_degree_matrix = np.diagflat(D_v_diag)
print("
Ma trận độ đỉnh D_v:")
print(vertex_degree_matrix)
# Kết quả: diag([0.8, 2.0, 1.2])^T
# Độ của V0=0.8, V1=0.8+1.2=2.0, V2=1.2

# Tính ma trận độ siêu cạnh D_e
ones_vector_vertices = np.ones((incidence_matrix.shape[0], 1))
D_e_diag = ones_vector_vertices.T @ incidence_matrix # Lấy độ của mỗi siêu cạnh (vector hàng)
hyperedge_degree_matrix = np.diagflat(D_e_diag.flatten())
print("
Ma trận độ siêu cạnh D_e:")
print(hyperedge_degree_matrix)
# Kết quả: diag([2, 2])^T
# E0 chứa 2 đỉnh, E1 chứa 2 đỉnh

Các ma trận này là nền tảng để xây dựng toán tử Laplace của siêu đồ thị. Hiểu chúng, bạn đã nắm được cách mô tả định lượng cấu trúc của siêu đồ thị.

2. Từ Đồ thị đến Siêu đồ thị: Di chuyển ý tưởng cốt lõi của Phân cụm phổ

Sự thành công của phân cụm phổ trên đồ thị thông thường đến từ nguyên lý toán học tinh tế của nó: nó cố gắng tìm một cách phân chia đồ thị, sao cho sự kết nối giữa các đồ thị con khác nhau là "yếu" nhất có thể, trong khi sự kết nối bên trong các đồ thị con là "mạnh" nhất có thể. Mục tiêu này được thực hiện thông qua phân rã đặc trưng của ma trận Laplace của đồ thị. Đối với siêu đồ thị, chúng ta cần một "toán tử Laplace của siêu đồ thị" tương tự.

Trên đồ thị thông thường, hàm mục tiêu Cắt chuẩn hóa (Normalized Cut, Ncut) có thể được nới lỏng thành việc giải ma trận Laplace chuẩn hóa **L_sym = I - D^{-1/2} A D^{-1/2}**.