Laplacian đồ thị

~4-5 giờ · cần xong bài 7 và bài 8 trước · bài bổ sung, đứng sau bài 9

Đích của bài này: hiểu vì sao một phép trừ trông tuỳ tiện — L = D − A — lại biến cấu trúc đồ thị thành một hàm năng lượng, và vì sao trị riêng thứ hai của nó chính là câu trả lời cho "cắt đồ thị này làm đôi ở đâu thì rẻ nhất?"

Bài 8 cho bạn cách đo "gần" thứ nhất trên đồ thị: lan truyền ngẫu nhiên (Markov, PageRank). Bài này cho cách thứ hai: phổ. Hai cách trả lời hai câu hỏi khác nhau, và biết cả hai thì bạn mới hỏi được câu đúng.

🧭 Làm theo thứ tự này

1. Không có video nào cho bài này.
2. Làm ô ⚡ bên dưới.
3. Đọc §1-4: L = D − A, trị riêng 0 đếm số mảnh, Fiedler λ₂, so sánh với PageRank ở bài 8.
4. Đọc §5 (ba chỗ Laplacian xuất hiện trong AI).
5. Làm bài tập §7: (a) đồ thị cầu và (b) đối chứng bằng đồ thị ngẫu nhiên là bắt buộc, (b) quan trọng nhất. (c) nối về bài 9, (d) là phần đọc thêm.
6. Tự kiểm §6. Nguồn đọc thêm ở §8.

Xong bài khi: nói được vì sao λ₂ lớn gấp 4-5 lần ở đồ thị ngẫu nhiên có nghĩa là phép cắt vô nghĩa.

⚡ 30 phút đầu — làm trước, đọc sau

import numpy as np
np.set_printoptions(precision=4, suppress=True)

# đồ thị hai cụm rõ rệt: {0,1,2} và {3,4,5}, nối bởi ĐÚNG MỘT cạnh 2—3
E = [(0,1),(0,2),(1,2), (3,4),(3,5),(4,5), (2,3)]
n = 6
A = np.zeros((n, n))
for i, j in E:
    A[i, j] = A[j, i] = 1

L = np.diag(A.sum(1)) - A          # <<< toàn bộ định nghĩa, một dòng
w, V = np.linalg.eigh(L)

print(w)                            # đích: [0. 0.4384 3. 3. 3. 4.5616]
print(V[:, 1])                      # đích: [-0.4647 -0.4647 -0.261 0.261 0.4647 0.4647]
print((V[:, 1] > 0).astype(int))    # đích: [0 0 0 1 1 1]

Ba đích: trị riêng nhỏ nhất bằng 0, trị riêng thứ hai là 0.4384, và dấu của eigenvector thứ hai là [0 0 0 1 1 1].

Dòng cuối là chỗ đáng dừng lại. Bạn không hề nói cho máy biết đồ thị có hai cụm. Bạn không đưa số cụm, không đưa hạt giống, không chạy thuật toán phân cụm nào. Bạn chỉ lấy eigenvector thứ hai của một ma trận — và dấu của nó chia đúng hai cụm.

Đó là toàn bộ bài này.

1. L = D − A không phải một định nghĩa — nó là một MÁY ĐO CHÊNH LỆCH

Nhìn công thức thì D − A trông như một phép trừ tuỳ tiện: lấy ma trận bậc (đường chéo, D[i][i] = số hàng xóm của nút i) trừ ma trận kề. Không có gì trong ký hiệu gợi ý nó dùng để làm gì.

Cách hiểu đúng: đừng nhìn ma trận, hãy cho nó ăn một vector.

Gán cho mỗi nút một con số — nhiệt độ, điểm số, ý kiến, gì cũng được. Thu về vector f. Khi đó:

(Lf)[i]  =  Σ        ( f[i] − f[j] )
          j là hàng xóm của i

Hàng thứ i của L trả về tổng độ lệch giữa nút i và các hàng xóm của nó.

Kiểm luôn:

f = np.array([3., 1., 4., 1., 5., 9.])

lhs = L @ f
rhs = np.array([sum(f[i] - f[j] for j in range(n) if A[i, j]) for i in range(n)])

assert np.allclose(lhs, rhs)
print(lhs)          # [  1.  -5.   7. -15.   0.  12.]

Đọc nút 4 cho cụ thể: f[4] = 5, hàng xóm là nút 3 (f=1) và nút 5 (f=9). Tổng độ lệch (5−1) + (5−9) = 4 − 4 = 0. Đúng bằng phần tử thứ 4 của kết quả. Nút 4 cân bằng với hàng xóm — nó cao hơn một bên đúng bằng mức nó thấp hơn bên kia.

L là toán tử khuếch tán. Nhân với A nghĩa là "mỗi nút thu gom giá trị của hàng xóm"; nhân với L nghĩa là "mỗi nút đo xem mình lệch bao nhiêu so với hàng xóm". Đây là phiên bản rời rạc của toán tử Laplace trong giải tích — và đó là lý do nó mang tên đó.

Bước thứ hai — chỗ đại số gặp hình học

Ép thêm một bước nữa: nhân f vào từ bên trái.

fᵀ L f  =  ½ · Σ      ( f[i] − f[j] )²
              i~j

(Tổng chạy qua mọi cặp có cạnh, và hệ số ½ vì mỗi cạnh được đếm hai lần trong tổng đôi.)

Kiểm bằng số:

q = f @ L @ f
s = sum((f[i] - f[j])**2 for i, j in E)     # tổng qua CẠNH, mỗi cạnh đúng 1 lần
print(q, s, np.isclose(q, s))               # 119.0  119.0  True

Đây là dòng đắt nhất của cả bài. L biến cấu trúc đồ thị thành một hàm năng lượng bậc hai đo mức độ gồ ghề của một tín hiệu trên đồ thị. fᵀLf nhỏ ⟺ các nút nối nhau có giá trị gần nhau ⟺ f trơn trên đồ thị.

Mọi thứ còn lại trong bài này — Fiedler, phân cụm phổ, vẽ đồ thị, over-smoothing trong mạng nơ-ron đồ thị — chỉ là cực tiểu hoá hoặc kiểm soát đúng một dạng toàn phương này. Không có ý tưởng thứ hai.

Hệ quả rơi ra ngay: vì fᵀLf là tổng các bình phương, nó luôn ≥ 0. Nói theo ngôn ngữ bài 7: L là ma trận nửa xác định dương — mọi trị riêng của nó không âm. Bạn vừa chứng minh xong điều đó mà không cần tính một trị riêng nào.

1b. Dựng L từ ma trận liên thuộc — fᵀLf = ‖Bᵀf‖², không cần hệ số ½ (bổ sung từ VMLS — 2026-10)

(nguồn: VMLS tr.132-135, §7.3; bài tập 7.6 tr.144 và 10.13 tr.192. VMLS gọi ma trận liên thuộc là A; ở đây gọi B vì A đã là ma trận kề.)

§1 đưa fᵀLf = ½Σ(fᵢ − fⱼ)² như công thức có sẵn, kèm hệ số ½ phải nhớ vì sao. Có cách dựng khác, trong đó hệ số ½ không xuất hiện và L = D − A tự rơi ra.

Ma trận liên thuộc B (incidence matrix) cỡ n × m (n nút, m cạnh): mỗi cột là một cạnh, có −1 ở nút đầu, +1 ở nút cuối, 0 ở mọi chỗ khác. Hướng cạnh chỉ để chọn dấu, và sẽ thấy nó không ảnh hưởng gì. Bᵀf là vector độ chênh trên từng cạnh: (Bᵀf)ₑ = f_cuối − f_đầu. Tính tay với f = (3,1,4,1,5,9) và bảy cạnh của ô ⚡:

cạnh        (0,1) (0,2) (1,2) (3,4) (3,5) (4,5) (2,3)
chênh         −2     1     3     4     8     4    −3        bình phương: 4+1+9+16+64+16+9 = 119

Đúng 119 của §1. Tổng bình phương độ chênh là ‖Bᵀf‖² (VMLS gọi là Dirichlet energy của f trên đồ thị), và ‖Bᵀf‖² = fᵀ(BBᵀ)f. Vậy chỉ còn phải chứng minh BBᵀ = L. Phần tử (BBᵀ)ᵢⱼ là tích vô hướng của hàng i với hàng j của B (bảng mọi tích vô hướng giữa các cặp hàng, cùng loại với QKᵀ ở bài 2 §3b):

• i = j: hàng i có một số ±1 cho mỗi cạnh chạm nút i, nên tích vô hướng với chính nó = bậc Dᵢᵢ.
• i ≠ j: chỉ cột của cạnh nối i—j có cả hai khác 0, và hai dấu ngược nhau, nên ra −1 nếu kề, 0 nếu không: −Aᵢⱼ.

Kiểm ở hai đầu cầu: hàng 2 của B là [0,1,1,0,0,0,−1], hàng 3 là [0,0,0,−1,−1,0,1]. Tích vô hướng = (−1)(1) = −1 = L[2,3]; hàng 2 với chính nó = 3 = bậc nút 2.

Bốn hệ quả: (1) fᵀLf = ‖Bᵀf‖² ≥ 0, nên L nửa xác định dương mà không cần đếm cạnh hai lần (câu 1-2 của §6). (2) Hướng cạnh vô can: lật hướng một cạnh là đổi dấu một cột b, mà BBᵀ = Σ b bᵀ (tổng các tích ngoài, bài 3) và b bᵀ = (−b)(−b)ᵀ. (3) L·1 = 0 theo cách thứ ba: mỗi cột của B tổng bằng 0 (một −1, một +1) nên Bᵀ1 = 0, suy ra L1 = B(Bᵀ1) = 0. (4) Đếm mảnh bằng hạng: fᵀLf = 0 ⟺ Bᵀf = 0, nên nhân của L là nhân của Bᵀ, số chiều = n − rank(B) (hạng–nullity, bài 3 §7). Đồ thị liên thông 6 nút có rank(B) = 5, nên đúng 1 trị riêng 0. Cắt cầu thì rank(B) = 4, ra 2, khớp [0 0 3 3 3 3] ở §2.

# dùng lại E, n, L ở ô ⚡ và f ở §1
B = np.zeros((n, len(E)))
for k, (i, j) in enumerate(E):
    B[i, k], B[j, k] = -1, +1                  # cạnh k đi từ i tới j

assert np.allclose(B @ B.T, L)                 # L = B Bᵀ, dựng từ cạnh
print(B.T @ f)                                 # [-2.  1.  3.  4.  8.  4. -3.]
assert np.isclose(np.sum((B.T @ f)**2), 119.0) and np.isclose(f @ L @ f, 119.0)

rng = np.random.default_rng(0)
B_lat = B * rng.choice([-1, 1], size=len(E))   # lật hướng ngẫu nhiên vài cạnh
assert np.allclose(B_lat @ B_lat.T, L)         # hướng cạnh vô can
assert np.allclose(np.ones(n) @ B, 0)          # mỗi cột tổng 0  ⇒  Bᵀ1 = 0  ⇒  L1 = 0
print(n - np.linalg.matrix_rank(B))            # 1  (liên thông)
B_cat = np.delete(B, E.index((2, 3)), axis=1)  # cắt cầu 2—3
print(n - np.linalg.matrix_rank(B_cat))        # 2  (hai mảnh)

# ví dụ của sách (VMLS hình 7.2): 4 nút, 5 cạnh. Năng lượng nhỏ = trơn, lớn = gồ ghề
B4 = np.array([[-1, -1, 0, 1, 0], [1, 0, -1, 0, 0], [0, 0, 1, -1, -1], [0, 1, 0, 0, 1]])
assert np.sum((B4.T @ [1, -1, 2, -1])**2) == 27 and np.sum((B4.T @ [1, 2, 2, 1])**2) == 3

2. Trị riêng 0 đếm số mảnh — bài toán ĐẾM có lời giải bằng ĐẠI SỐ

fᵀLf = 0 khi nào? Tổng các bình phương bằng 0 ⟺ mọi số hạng bằng 0 ⟺ f[i] = f[j] với mọi cạnh ⟺ f hằng số trên mỗi mảnh liên thông.

Nghĩa là nhân của L (không gian riêng ứng với λ = 0) có một cơ sở rất cụ thể: các vector chỉ báo của từng thành phần liên thông — vector bằng 1 trên mảnh đó, 0 ở ngoài.

Kiểm bằng cách cắt cạnh cầu 2—3 để đồ thị rời làm đôi:

A2 = A.copy(); A2[2, 3] = A2[3, 2] = 0
L2 = np.diag(A2.sum(1)) - A2
print(np.linalg.eigvalsh(L2))       # [0. 0. 3. 3. 3. 3.]

Hai trị riêng bằng 0 — đúng bằng hai thành phần liên thông.

Bội của trị riêng 0 = số thành phần liên thông. Một câu hỏi tổ hợp rời rạc ("đồ thị có mấy mảnh?") có câu trả lời liên tục ("số chiều của một không gian con").

Đây là chỗ chuyển pha nhận thức của cả bài. Người mới không kỳ vọng bài toán đếm lại giải được bằng đại số tuyến tính, và không thấy rằng vector chỉ báo cụm chính là một eigenvector.

Đối chiếu với thư viện chuẩn để chắc:

import networkx as nx
G2 = nx.from_numpy_array(A2)
print(nx.number_connected_components(G2))                       # 2
print(int(np.sum(np.abs(np.linalg.eigvalsh(L2)) < 1e-10)))      # 2

3. Fiedler λ₂ — vì sao trị riêng THỨ HAI lại là cách cắt đồ thị

Đây là mắt xích mà không sách nào nối hộ bạn, vì ba mảnh của nó nằm ở ba chương khác nhau. Ghép lại thì λ₂ hết bí ẩn hoàn toàn.

Bước 1 — trị riêng là nghiệm của một bài toán tối ưu. Với ma trận đối xứng, trị riêng chính là các giá trị cực tiểu/cực đại của thương Rayleigh:

                fᵀ L f
     R(f)  =  ─────────
                fᵀ f

Cực tiểu của R trên mọi f ≠ 0 là λ₁; cực tiểu trên các f trực giao với eigenvector đầu là λ₂; và cứ thế. (Đây là định lý Rayleigh–Ritz — bạn không cần chứng minh nó, cần biết nó nói gì.)

Bước 2 — với L, tử số đó CHÍNH LÀ chi phí cắt. Từ §1: fᵀLf = ½Σ(f_i − f_j)². Nếu f gán giá trị khác nhau cho hai bên một cạnh, cạnh đó đóng góp vào tổng. Cạnh nào bị "cắt qua" thì bị tính tiền. Tử số của Rayleigh là chi phí cắt mềm.

Bước 3 — vì sao phải ép trực giao với 1. Cực tiểu tuyệt đối của R là f hằng số, cho R = 0. Đó là nghiệm tầm thường: "không cắt gì cả, xếp mọi nút vào cùng một bên". Vô dụng.

Nên ta ép f ⟂ 1, tức tổng các giá trị bằng 0, tức bắt buộc phải có nút dương và nút âm, tức bắt buộc phải chia đôi đồ thị thật.

Ràng buộc trực giao với 1 không phải kỹ thuật cho đẹp. Nó chính là điều kiện "phải cắt thật".

Cực tiểu dưới ràng buộc đó là λ₂, và vector đạt cực tiểu u₂ là cách gán số cho các nút sao cho việc chia đôi cắt qua ít cạnh nhất. Vector đó có tên riêng: Fiedler vector.

Bước 4 — trực giác cuối, chỗ mọi thứ khớp vào nhau.

λ₂ nhỏ ⟺ "tồn tại một cách chia đôi chỉ tốn rất ít năng lượng" ⟺ đồ thị gần như đã đứt làm hai. λ₂ = 0 ⟺ nó đứt thật (quay về §2).

u₂ là phiên bản LÀM MỀM của vector chỉ báo cụm ở §2, và λ₂ đo "đồ thị gần đứt tới mức nào".

Đọc bằng số

w, V = np.linalg.eigh(L)
print(w[1])                          # 0.438447   ← lambda_2
print(V[:, 1])                       # [-0.4647 -0.4647 -0.261  0.261  0.4647  0.4647]
print((V[:, 1] > 0).astype(int))     # [0 0 0 1 1 1]

Ba điều đáng đọc kỹ trong u₂:

Cột thứ hai là thứ khiến phương pháp này hữu dụng hơn một thuật toán phân cụm thường: nó không chỉ nói nút nào thuộc cụm nào, nó còn nói nút nào nằm ở ranh giới.

Đối chiếu thư viện

G = nx.from_numpy_array(A)
assert np.allclose(L, nx.laplacian_matrix(G).toarray())
print(nx.algebraic_connectivity(G))        # 0.438447   ← khớp lambda_2

networkx gọi λ₂ là algebraic connectivity — "độ liên thông đại số". Cái tên đó nói đúng ý: nó đo đồ thị dính với nhau chặt cỡ nào, bằng một con số.

🪤 BẪY: λ₂ lớn KHÔNG có nghĩa là "phân cụm tốt"

Người mới hay đọc ngược. Chạy trên đồ thị đầy đủ K₆ (mọi nút nối mọi nút):

K = nx.complete_graph(6)
print(np.linalg.eigvalsh(nx.laplacian_matrix(K).toarray()))   # [0. 6. 6. 6. 6. 6.]

λ₂ = 6 — lớn gấp gần 14 lần đồ thị hai cụm của ta (0.4384). Nhưng K₆ không có cụm nào cả.

λ₂ lớn = đồ thị khó cắt = không có cấu trúc cụm. λ₂ nhỏ = đồ thị dễ cắt = có cụm rõ.

Và u₂ luôn luôn trả về một phép cắt, kể cả khi đồ thị không có cụm nào — nó buộc phải trả về gì đó. Phải nhìn λ₂ để biết phép cắt đó có ý nghĩa không. Chỉ nhìn u₂ là bạn sẽ tìm ra "cụm" trong nhiễu.

Đây đúng là cảnh báo của môn 6 về phân cụm nói chung, ở dạng cụ thể nhất: chạy phân cụm thì bao giờ cũng ra cụm — câu hỏi thật là cụm đó có thật không.

Còn một chế độ hỏng thứ hai ở đầu kia: nếu đồ thị gần đầy đủ thì mọi trị riêng phụ đều xấp xỉ bằng nhau, không có khe hở phổ, và phương pháp phổ không phát hiện được cụm nào — kể cả khi có cụm yếu. Nhìn K₆ ở trên: năm trị riêng phụ bằng nhau chằn chặn, không có λ₂ nào nổi bật.

4. Hai cách đo "gần" — bài 8 và bài 10 trả lời hai câu khác nhau

Đây là lý do mục này tồn tại sau bài 8 chứ không thay thế nó.

Và chúng nối với nhau chặt hơn bạn tưởng. Laplacian dạng random-walk là

L_rw  =  D⁻¹L  =  I − D⁻¹A  =  I − P

Vì L_rw = I − P, P và L_rw có chung hệt bộ eigenvector, chỉ đảo trật tự trị riêng: λ của P ↔ 1 − λ của L_rw. Trị riêng trội của P (λ=1) ứng với trị riêng đáy của L_rw (0).

"Phân phối dừng của bước ngẫu nhiên" và "eigenvector đáy của Laplacian" là MỘT VẬT nhìn từ hai phía.

Kiểm luôn cho chắc:

P = np.linalg.inv(np.diag(A.sum(1))) @ A
L_rw = np.eye(n) - P
wP = np.sort(np.linalg.eigvals(P).real)[::-1]
wR = np.sort(np.linalg.eigvals(L_rw).real)
print(np.allclose(wP, 1 - wR))      # True

🪤 BẪY thứ hai: P và L_rw KHÔNG đối xứng

Ba dòng code trên phải dùng np.linalg.eigvals (ma trận tổng quát), không dùng eigh (ma trận đối xứng). Vì D⁻¹A không đối xứng — nhân D⁻¹ vào bên trái phá vỡ tính đối xứng của A.

Hậu quả nghiêm trọng hơn một lỗi gọi hàm: không có định lý phổ thì không đảm bảo có cơ sở trực chuẩn eigenvector, không đảm bảo trị riêng thực. Đó chính là lý do tồn tại của phiên bản chuẩn hoá đối xứng:

L_sym  =  D^(−1/2) · L · D^(−1/2)

L_sym đồng dạng với L_rw (nên cùng phổ) nhưng đối xứng (nên có định lý phổ, có eigenvector trực chuẩn, có trị riêng thực).

Chuẩn hoá đối xứng thường bị dạy như một "thủ thuật ổn định số". Lý do thật: cần định lý phổ thì phải có ma trận đối xứng. Đó là một quyết định về công cụ toán được phép dùng, không phải về số học.

5. Nối vào AI — ba chỗ Laplacian xuất hiện mà bạn sẽ gặp

(a) Phân cụm phổ

Thuật toán đầy đủ, và nó ngắn đến bất ngờ:

1. dựng L (hoặc L_sym) từ đồ thị
2. lấy k eigenvector ứng với k trị riêng NHỎ NHẤT
3. mỗi nút i → một điểm trong R^k (hàng thứ i của ma trận eigenvector)
4. chạy k-means trên n điểm đó

Bước 3 là chỗ đáng chú ý: toạ độ của nút i chính là hàng thứ i của ma trận eigenvector. Bạn vừa nhúng một đồ thị vào không gian Euclid — và đó là dạng thuần khiết nhất của "graph embedding".

Chi tiết dạy được ngay: phải BỎ u₁. Nếu giữ vector hằng, mọi nút nhận cùng một toạ độ ở trục đó, và đồ thị bị dẹp vào một siêu phẳng — trục đó không mang thông tin nào. Đây đúng là lý do PCA trừ trung bình trước (môn 6): bỏ đi thành phần mà mọi mẫu đều giống nhau, vì nó không phân biệt được gì.

(b) Vẽ đồ thị đẹp = cùng một bài toán

Tưởng tượng mỗi cạnh là một lò xo; đặt các nút vào mặt phẳng sao cho tổng năng lượng lò xo nhỏ nhất. Năng lượng đó là Σ w_ij ‖ρ(v_i) − ρ(v_j)‖² — chính là dạng toàn phương ở §1, viết dưới dạng vết ma trận. Nghiệm tối ưu (với ràng buộc chuẩn hoá và cân bằng) là các eigenvector ứng với trị riêng nhỏ nhất khác 0.

Thuật toán vẽ đồ thị và thuật toán phân cụm phổ là CÙNG một thuật toán, chỉ khác cách dùng đầu ra: lấy u₂ liên tục để vẽ, lấy dấu của u₂ để cắt.

(c) Mạng nơ-ron đồ thị — và chỗ chính lý thuyết này cắn lại

Một bộ lọc phổ tổng quát trên đồ thị có hai bệnh: cần phân rã trị riêng (đắt), và ma trận kết quả dày đặc nên mỗi nút đầu ra phụ thuộc TOÀN BỘ đồ thị — không định xứ.

Cách sửa đẹp đến bất ngờ: ép bộ lọc là một đa thức bậc K của L. Khi đó nó rút gọn thành Σₖ θₖ Lᵏ — phân rã trị riêng biến mất hoàn toàn. Và vì Lᵏ[i,j] = 0 khi dist(i,j) > k, ta có:

"Đa thức bậc K của Laplacian" ≡ "chỉ nhìn hàng xóm trong K bước".

Hai thứ tưởng là hai trường phái đối lập — spectral (Fourier trên đồ thị) và spatial (lan truyền thông điệp) — hoá ra là một. Không ai tự nghĩ ra rằng hạn chế lớp hàm lại tạo ra tính định xứ; người mới nghĩ tính định xứ là thứ phải thiết kế vào kiến trúc, ở đây nó rơi ra miễn phí từ một ràng buộc đại số.

Và đây là chỗ bài 8 quay lại cắn: bỏ hàm phi tuyến đi, chồng L lớp mạng nơ-ron đồ thị chính là tính luỹ thừa bậc L của một ma trận lan truyền — đúng là power iteration của bài 8. Theo đúng lý thuyết đó, kết quả hội tụ về eigenvector trội, một vector chỉ chứa bậc của nút, mất sạch đặc trưng đầu vào. Hiện tượng này có tên: over-smoothing.

Cùng một định lý hội tụ làm PageRank hoạt động lại giết chết mạng đồ thị sâu. PageRank muốn quên điều kiện ban đầu — đó là mục đích của nó, và damping được thêm vào chính để ép nó quên nhanh hơn (bài 8 §7). Mạng nơ-ron đồ thị thì điều kiện ban đầu chính là dữ liệu. Quên nó đi là hỏng.

Cùng một phép toán. Ngược nhau về mục đích. Đây là ví dụ rõ nhất trong cả môn 2 rằng một kết quả toán không tự nó tốt hay xấu — nó tốt hay xấu tuỳ bạn muốn gì.

Điều kiện của định lý over-smoothing: đồ thị liên thông và KHÔNG hai phía. Đồ thị hai phía (người dùng–sản phẩm, tác giả–bài báo) là loại cực kỳ phổ biến trong AI, và ở đó tồn tại thành phần phổ dao động đổi dấu mãi mãi thay vì tắt dần — phá vỡ khe hở phổ. Ghi nhớ điều kiện, đừng chỉ ghi nhớ kết luận.

6. Tự kiểm "tận cùng"

1. Chứng minh fᵀLf = ½Σ_{i~j}(f_i − f_j)² bằng cách khai triển trực tiếp. (Vài dòng. Đây là dòng đắt nhất bài — tự tay làm một lần.)
2. Từ câu 1, chứng minh L nửa xác định dương mà không tính một trị riêng nào.
3. Vì sao L·1 = 0 luôn đúng với mọi đồ thị? Nêu bằng hai cách: bằng công thức (Lf)[i], và bằng cấu trúc D − A.
4. Đồ thị có 5 thành phần liên thông. Không tính gì, nói ngay: bội của trị riêng 0 là bao nhiêu, và một cơ sở của nhân L gồm những vector nào?
5. Vì sao phải ép f ⟂ 1 khi đi tìm λ₂? Bỏ ràng buộc đó đi thì cực tiểu là gì và nó nói lên điều gì?
6. λ₂ = 6 trên K₆ và λ₂ = 0.4384 trên đồ thị hai cụm. Đồ thị nào dễ cắt hơn, và điều đó nói gì về việc dùng u₂ để phân cụm trên K₆?
7. Trong u₂ = [−0.4647, −0.4647, −0.261, 0.261, 0.4647, 0.4647], vì sao nút 2 và 3 có giá trị tuyệt đối nhỏ nhất? Thông tin đó dùng được vào việc gì mà một nhãn cụm 0/1 không cho được?
8. L_rw = I − P nên P và L_rw chung eigenvector. Vậy vì sao vẫn cần L_sym? Trả lời bằng ngôn ngữ định lý phổ, không bằng "cho ổn định".
9. Nối bài 8 và bài 10: PageRank muốn hội tụ về eigenvector trội, mạng nơ-ron đồ thị thì sợ điều đó. Cùng một định lý. Giải thích vì sao cùng một kết quả toán lại vừa là tính năng vừa là lỗi.

Câu 1 và 9 là hai ranh giới. Làm được câu 1 thì cả bài này là hệ quả; hiểu được câu 9 thì bạn đã thấy được điều mà phần lớn người dùng thư viện đồ thị không bao giờ thấy.

7. Bài tập về nhà

(a) Đồ thị cầu — bắt buộc. Dựng đồ thị 20 nút gồm hai cụm 10 nút đầy đủ, nối bởi k cạnh cầu với k = 1, 2, 5, 10. Với mỗi k, tính λ₂ và in dấu của u₂.

Đây là số tôi đã chạy sẵn để bạn đối chiếu:

Đích: λ₂ tăng đơn điệu theo k — hai cụm càng dính chặt thì càng khó cắt. Nhưng chú ý cột thứ hai: phép cắt vẫn ĐÚNG ở cả bốn giá trị, kể cả k = 10. Câu hỏi thật: vì sao nó chưa hỏng? Muốn làm nó hỏng thì phải đổi cái gì — tăng k nữa, hay làm hai cụm thưa đi? Thử cả hai và nói xem cái nào phá được trước. (Tôi viết bản đầu của bài này với câu "tới khi k đủ lớn thì hỏng" mà chưa chạy. Chạy xong thì nó không hỏng. Đã sửa — và giữ lại vết sửa này vì nó là quy tắc 1 ở cỡ nhỏ nhất có thể: một khẳng định nghe hợp lý, không kiểm, và sai.)

(b) Nhiễu — đối chứng bắt buộc. Sinh đồ thị ngẫu nhiên Erdős–Rényi 20 nút, cùng mật độ cạnh với (a) ở k = 5. Tính λ₂ và u₂ cho 4 seed khác nhau.

Đích: u₂ vẫn trả về một phép chia ở cả bốn seed — nó buộc phải. Nhưng λ₂ lớn gấp 4-5 lần, và đó là dấu hiệu duy nhất cho biết phép chia đó vô nghĩa.

Đây là bài tập quan trọng nhất trong bốn bài: phương pháp luôn trả về đáp án, và bạn phải có một con số KHÁC để biết đáp án đó có nghĩa hay không. Không có đối chứng này thì bạn sẽ "phát hiện cấu trúc" trong nhiễu thuần tuý — và bảng kết quả sẽ trông y hệt một phát hiện thật.

(c) Nối về bài 9 — và một kết quả âm đáng giữ. Với đồ thị (a) k = 2, lấy 3 eigenvector đáy làm toạ độ cho mỗi nút rồi chạy sklearn.cluster.KMeans. So với chạy k-means thẳng trên hàng ma trận kề.

Kết quả tôi chạy: cả hai đều đạt 100%.

Đừng bỏ qua kết quả này vì nó "không thú vị". Nó nói đúng một điều: trên bài toán dễ, phương pháp phức tạp không hơn phương pháp tầm thường. Muốn thấy phổ thắng thật, bạn phải làm bài toán khó lên — cụm thưa hơn, nhiều cầu hơn, hoặc cụm lồng nhau mà ma trận kề không tách được tuyến tính. Việc của bạn là tìm cấu hình đó, và đó mới là bài tập thật. (Đây chính là quy tắc 2 ở dạng nhỏ nhất: nếu không có baseline tầm thường chạy song song, bạn sẽ tưởng 100% là công của phương pháp phổ.)

(d) Đọc. Nếu muốn thấy cùng những kết quả này ở dạng chứng minh chặt: Gallier & Quaintance, library/books/gallier-algebra-topology-calculus-optimization.pdf, ch.20 Graph Laplacians (~tr.701-721). Đọc §20.1-20.2, khoảng 6 trang. Còn phần nối sang mạng nơ-ron đồ thị: Ma & Tang, library/books/ma-tang-deep-learning-on-graphs.pdf, §2.4-2.5 (tr.26-32) — bảy trang đậm đặc nhất, và tr.27 là trang đắt nhất: chỗ L = D − A biến thành fᵀLf = ½Σ(f_i−f_j)².

8. Nguồn

⚠️ Cả ba cuốn trên đều KHÔNG có bất đẳng thức Cheeger — định lý chặn chất lượng phép cắt bằng λ₂, tức là định lý biện minh cho toàn bộ §3. Gallier nói thẳng "we do not have the space to present it here".

Sửa (2026-10): kho sách có nó — Zhao, Graph Theory and Additive Combinatorics (library/books/zhao-graph-theory-and-additive-combinatorics.pdf), Thm 3.2.13 tr.105, nhưng chỉ cho đồ thị d-đều:

κ/2  ≤  h(G)  ≤  √(2dκ)        κ = d − λ₂(A) = λ₂(L)  (bằng nhau vì G d-đều)
h(G) = min_{0<|S|≤n/2}  (số cạnh rời S) / |S|

Đồ thị	κ = λ₂(L)	h thật (đếm)	cận dưới κ/2	cận trên √(2dκ)
chu trình 20 đỉnh (d=2)	0.0979	0.2	0.0489	0.6257
khối lập phương Q₄ (d=4)	2.0	1.0	1.0 (chạm)	4.0

Đọc đúng chiều: chiều chặt là cận dưới — "λ₂ lớn ⇒ không có cổ chai" (chứng nhận phủ định). Chiều kia chỉ tới căn bậc hai: chu trình có h = Θ(1/n) nhưng κ = Θ(1/n²), nên "λ₂ nhỏ ⇒ có một cắt tốt" chỉ đúng định tính. Với đồ thị memory không đều (bậc lệch), dùng bản Laplacian chuẩn hoá — Zhao không dạy, chính Zhao trỏ sang Chung Spectral Graph Theory và Spielman SAGT (tr.128). Đừng tuyên bố mạnh hơn thứ định lý cho phép.

Bài trước: Bài 9 — SVD và xấp xỉ hạng thấp Quay lại: Môn 2 — tổng quan