Ma Trận Laplacian Và Ma Trận Kề Chuẩn Hóa Đối Xứng Cho Đồ Thị (Spectral Graph Theory)

Mục tiêu kiến thức

• Cho đồ thị vô hướng G = (V, E) với N đỉnh và ma trận kề A ∈ R^{N × N} (A_ij = 1 nếu có cạnh, 0 nếu không).
• Ma trận bậc D ∈ R^{N × N} là ma trận đường chéo: D_ii = ∑_j A_ij.
• Ma trận Laplacian chuẩn hóa đối xứng (Normalized Graph Laplacian):

L_sym = I - D^-1/2 A D^-1/2

• Mẹo tái chuẩn hóa GCN (Renormalization Trick - Kipf & Welling 2017):

Để tránh hiện tượng bùng nổ/triệt tiêu phổ giá trị riêng khi xếp chồng nhiều tầng GNN, ta thêm vòng tự khuyên (self-loop) vào mỗi đỉnh: A = A + I_N, D_ii = ∑_j A_ij A = D^-1/2 A D^-1/2 Ma trận A có bán kính phổ bị chặn bởi 1.0, là toán tử lan truyền thông điệp cốt lõi của Graph Convolutional Networks.

Yêu cầu

Viết hàm:

def compute_normalized_adjacency_and_laplacian(
    adjacency_matrix: np.ndarray
) -> tuple[np.ndarray, np.ndarray]:
    pass

• adjacency_matrix: Mảng 2D đối xứng (N, N) chứa các giá trị 0 hoặc 1.
• Trả về tuple (gcn_hat_A, L_sym):
• gcn_hat_A: A = D^-1/2 (A + I) D^-1/2.
• L_sym: I - D^-1/2 A D^-1/2 (đối với đỉnh cô lập có degree=0, quy ước D_ii^-1/2 = 0).

Ràng buộc

• Thời gian chạy tối đa: 2000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.