Bài này chúng ta tiếp tục tìm hiểu khái niệm thương Rayleigh (Rayleigh quotient) và bất đẳng thức Cheeger. Thương Rayleigh cho chúng ta một cách nhìn về trị riêng và vector riêng thông qua bài toán tối ưu, qua đó cho chúng ta một phương pháp tìm trị riêng và vector riêng một cách khá hiệu quả. Bất đẳng thức Cheeger cho chúng ta một cách nhìn về đồ thị thông qua trị riêng nhỏ thứ 2, cũng như gợi mở ra sự quan hệ giữa bài toán phát hiện cộng đồng trong mạng và bài toán phân tích phổ. Ta sẽ chứng minh bất đẳng thưc này sử dụng thương Reyleigh.

Thương Rayleigh

Trong phần này, ta sẽ giả sử ma trận đầu vào $M$ là thực,đối xứng và có kích thước $n \times n$. Định lí phân tích phổ (xem lại bài trước) cho chúng ta biết $M$ có $n$ trị riêng $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$ và $n$ vector riêng tương ứng $\mathbf{v}_1,\mathbf{v}_2, \ldots, \mathbf{v}_n$.

Chứng minh: Trong bài tập 1 của bài trước, ta đã chứng minh rằng nếu hai trị riêng khác nhau thì hai vector riêng vuông góc với nhau. Điều này có thể mở rộng ra cho trường hợp mọi trị riêng của $M$: Ta có thể chọn bộ vector riêng $\mathbf{v}_1,\mathbf{v}_2, \ldots, \mathbf{v}_n$ sao cho bộ này trực giao (orthorgonal), i.e, các vector đôi một vuông góc với nhau.

Ngoài ra, định nghĩa của vector riêng cho chúng ta biết nếu một vector là một vector riêng thì sau khi ta co/giãn (scale) vector này với một hệ số thực $a$ bất kì thì vector đó cũng là một vector riêng với cùng trị riêng. Do đó, ta có thể chuẩn hóa các vector riêng sao cho mọi vector riêng đều có độ dài là $1$. Qua đó, ta thu được bộ vector riêng $\mathbf{v}_1,\mathbf{v}_2, \ldots, \mathbf{v}_n$ trực chuẩn (orthonormal).

Chúng ta nhắc lại 2 tính chất của bộ vector trực chuẩn (mà ta sẽ dùng trong bài này):

1. $\mathbf{v}_i^T\mathbf{v}_j = 0 \quad \forall i \not= j $ và $\mathbf{v}_i^T\mathbf{v}_i = 1 \quad \forall i$.
2. Gọi $\mathbf{x} \in \mathbb{R}^V$ là một vector tùy ý, ta có:

   $\sum_{1 \leq i \leq n} (\mathbf{v_i}^T\mathbf{x})^2 = ||x||_2 \qquad (1)$

Nhìn vào $(2)$ ta thấy, thương Rayleigh có vẻ là một đại lượng "không đẹp" tí nào cả vì nó liên quan đến phép chia. Các phép chia chỉ làm các bài toán tính toán trở nên phức tạp hơn mà thôi. Tuy nhiên, nhìn kĩ một lúc ta sẽ thấy:

Thương Rayleigh thì có liên quan gì đến trị riêng và vector riêng? Thử tìm Thương Rayleigh của vector riêng $\mathbf{v}_n$ của $M$? Ta có:

$\frac{\mathbf{v}_n^TM\mathbf{v}_n}{\mathbf{v}_n^T\mathbf{v}_n} = \frac{\mathbf{v}_n^T \lambda_n \mathbf{v}_n}{\mathbf{v}_n^T\mathbf{v}_n} = \lambda_n \frac{\mathbf{v}_n^T\mathbf{v}_n}{\mathbf{v}_n^T\mathbf{v}_n} = \lambda_n\qquad (2)$

À, té ra Thương Rayleigh của vector riêng chính là trị riêng của nó. Tuy nhiên, cái đẹp của thương Rayleigh không chỉ có vậy. Xét định lý sau:

Ta khoan hãy chứng minh định lý này mà hãy xem xét một số hệ quả của nó trước. Nhìn vào $(3)$ và $(1)$ các bạn có thấy cái gì đó giống nhau? (Chú ý ở đây $||\mathbf{x}||_2 = 1$ vì $\mathbf{x}$ là một vector đơn vị). Từ $(3)$ (và kết hợp với $(1)$) ta dễ dàng suy ra:

$\frac{\mathbf{x}^TM\mathbf{x}}{\mathbf{x}^T\mathbf{x}} \leq \sum_{1 \leq i \leq n} \lambda_n(\mathbf{v_i}^T\mathbf{x})^2 = \lambda_n \sum_{1 \leq i \leq n} (\mathbf{v_i}^T\mathbf{x})^2 = \lambda_n \qquad (4)$

và

$\frac{\mathbf{x}^TM\mathbf{x}}{\mathbf{x}^T\mathbf{x}} \geq \sum_{1 \leq i \leq n} \lambda_1(\mathbf{v_i}^T\mathbf{x})^2 = \lambda_1 \sum_{1 \leq i \leq n} (\mathbf{v_i}^T\mathbf{x})^2 = \lambda_1 \qquad (5)$

và nếu ta chọn $\mathbf{x}$ là một vector vuông góc với vector riêng đầu tiên $\mathbf{v_1}$, thì ta có $\mathbf{v_i}^T\mathbf{x} = 0$. Do đó, từ $(3)$ ta suy ra:

$\frac{\mathbf{x}^TM\mathbf{x}}{\mathbf{x}^T\mathbf{x}} = \sum_{2 \leq i \leq n} \lambda_1(\mathbf{v_i}^T\mathbf{x})^2 \geq \lambda_2 \sum_{2 \leq i \leq n} (\mathbf{v_i}^T\mathbf{x})^2 = \lambda_2 \qquad (6)$

Mở rộng ra một chút nữa (coi như bài tập cho các bạn), ta có định lý sau:

Theorem 1 chính là cái đẹp của thương Rayleigh. Nó cho chúng ta thấy quan hệ của vector riêng, trị riêng và bài toán tối ưu thương Rayleigh. Theorem 1 cũng ngay lập tức cho ta một cách để tính trị riêng và vector riêng. Ta có thể bắt đầu từ tính $\lambda_1, \mathbf{v_1}$. $\lambda_1$ chính là (theo $(7)$):

$\lambda_1 = \min{x \in \mathbb{R}^V} \frac{\mathbf{x}^TM\mathbf{x}}{\mathbf{x}^T\mathbf{x}} = \min_{x \in \mathbb{R}^V} \mathbf{x}^TM\mathbf{x} \quad \mbox{subject to } \mathbf{x}^T\mathbf{x} = 1\qquad (9)$

Ta có thể dùng phương pháp nhân tử Lagrange để giải bài toán tối ưu $(9)$ trong thời gian cỡ $O(n^2)$. Sau khi đã tìm được $\lambda_1, \mathbf{v_1}$ ta tiếp tục tìm $\lambda_2, \mathbf{v_2}$ cũng bằng cách giải bài toán tối ưu, và cứ như vậy. Tổng thời gian để tìm là $O(n^3)$. Độ phức tạp này tuy hơi lớn, nhưng nó cho chúng ta một giải pháp đơn giản, thay vì sử dụng định nghĩa, tính det và giải phương trình bận $n$.

Bây giờ ta quay trở lại chứng minh Lemma 1.

Chứng minh Lemma 1: Để chứng minh định lý này, ta cần một cách để liên hệ $\mathbf{x}$ và bộ trị riêng. Do bộ trị riêng là trực chuẩn, ta có:

$\mathbf{x} = \sum_{1 \leq i \leq n} (\mathbf{v}_i^T\mathbf{x})\mathbf{v}_i$

Do đó (chú ý $\mathbf{x}$ đơn vị):

$\begin{array} {l} \frac{\mathbf{x}^TM\mathbf{x}}{\mathbf{x}^T\mathbf{x}} & = \mathbf{x}^TM\mathbf{x} \\ & = \sum_{1 \leq i \leq n} (\mathbf{v}_i^T\mathbf{x})\mathbf{v}^T_i M \sum_{1 \leq j \leq n} (\mathbf{v}_j^T\mathbf{x})\mathbf{v}_j \\ &= \sum_{1 \leq i,j \leq n} (\mathbf{v}_i^T\mathbf{x})(\mathbf{v}_j^T\mathbf{x}) \mathbf{v}^T_i M \mathbf{v}_j \\ &= \sum_{1 \leq i,j \leq n} (\mathbf{v}_i^T\mathbf{x})(\mathbf{v}_j^T\mathbf{x})\mathbf{v}^T_i (\lambda_j \mathbf{v}_j) \\ &= \sum_{1 \leq i,j \leq n} (\mathbf{v}_i^T\mathbf{x})(\mathbf{v}_j^T\mathbf{x})\lambda_j \mathbf{v}^T_i \mathbf{v}_j \\ &= \sum_{1 \leq i \leq n}(\mathbf{v}_i^T\mathbf{x})^2 \lambda_i\end{array}$

Từ phương trình 5 xuống phương trình 6, ta áp dụng $\mathbf{v}_i \bot \mathbf{v}_j \quad \forall i \not = j$ và $\mathbf{v}^T_i \mathbf{v}_i = 1 \quad \forall i$.

Bất đẳng thức Cheeger

Bất đẳng thức Cheeger cho chúng ta một cách nhìn về đồ thị thông qua trị riêng $\lambda_2$ của ma trận Laplace. Tại sao không phải là $\lambda_1$? Hẳn bạn còn nhớ trong tính chất 3 của ma trận Laplace trong bài 1, ma trận Laplace có $\lambda_1 = 0$ ứng với vector riêng $\mathbf{1}$. Do đó, $\lambda_1$ là một trị riêng tâm thường. Để phát biểu bất đẳng thức này, ta cần thêm một số khái niệm.

Gọi $S \subset V$ là một tập đỉnh. Ta kí hiệu $\partial S$ là tập các cạnh có đúng một đầu mút trong $S$ (và đầu mút còn lại trong $V\setminus S$). Ta định nghĩa độ mở (expansion) của $S$ là tỉ lê:

$\Phi(S) = \frac{|\partial S|}{|S|} \qquad (10)$

và định nghĩa độ mở của đồ thị $G(V,E)$:

$\Phi(G) = \min_{1 \leq |S| \leq n/2}\frac{|\partial S|}{|S|} \qquad (11)$

Xem ví dụ về độ mở của đồ thị trong hình dưới đây:

Theo nghĩa nào đó, độ mở cho chúng ta biết mức độ liên thông của đồ thị. Độ mở bằng $0$ khi và chỉ khi đồ thị không liên thông. Độ mở càng nhỏ thì "mức độ liên thông" càng thấp. Tính chất này rất có ý nghĩa trong bài toán phân cụm mạng xã hội, mà nổi bất là phát hiện cộng đồng. Trong hình vẽ ở ví dụ trên, nếu ta phát hiện được tập $S$ như trong hình bên phải thì coi như ta đã phân được mạng thành 2 thành 2 cụm thực sự. Ta sẽ nghiên cứu kĩ hơn một chút nữa tính chất này trong phần bài tập và các phần sau của lý thuyết này.

Gọi $\Delta(G)$ là bậc của đồ thị, i.e, là bậc lớn nhất trong số bậc của các đỉnh. Ví dụ với hình trên thì $\Delta(G) = 5 = d[6]$. Bất đẳng thức Cheeger cho chúng ta biết phổ của đồ thị có liên quan chặt chẽ đến độ mở:

Trước khi chứng minh ta hãy xem xem điều thú vị ở bất đẳng thức Cheeger là gì? Nếu $\lambda_2 = 0$, từ $(12)$ ta dễ dàng suy ra $\Phi(G) = 0$. Điều đó có nghĩa là đồ thị $G$ không liên thông (tại sao?). Hay nói cách khác đồ thị $G$ có ít nhất 2 thành phần liên thông (có thể có nhiều hơn). Điều này có thể mở rộng ra trường hợp $\lambda_k = 0$ (xem bài tập 2). Điều này có ý nghĩa lớn với bài toán phân cụm đồ thị. Nếu ta muốn phân đồ thị thành $k$ cụm, ta có thể nhìn vào $k$ vector riêng đầu tiên. Ví dụ paper [2] là một ví dụ áp dụng ý tưởng này và tutorial [3] thảo luận kĩ hơn về ý tưởng này.

Giờ ta sẽ xem cách chứng minh bất đẳng thức đầu tiên, (bất đẳng thức thứ 2 chứng minh khó hơn và ta sẽ xem xét ở phần sau). Để chứng minh $\frac{\lambda_2}{2} \leq \Phi(G)$, ta sẽ chứng minh:

 
Từ bất đẳng thức $(13)$, ta dễ dàng suy ra $\frac{\lambda_2}{2} \leq \Phi(G)$ đựa vào định nghĩa của $\Phi(G)$.

Chứng minh $(13)$: Ta có $\lambda_1 = 0$ và $\mathbf{v}_1 = \mathbf{1}$. Theo Theorem 1, ta có:

$\lambda_2 = \min_{\mathbf{x} \bot \mathbf{1}} \frac{\mathbf{x}^TL\mathbf{x}}{\mathbf{x}^T\mathbf{x}} $

Do đó, ta suy ra:

$\lambda_2 \leq \frac{\mathbf{x}^TL\mathbf{x}}{\mathbf{x}^T\mathbf{x}} \quad \forall \mathbf{x} \in \mathbb{R}^V, \mathbf{x} \bot \mathbf{1} \qquad (14)$

Giờ ta sẽ tìm cách liên hệ vector $\mathbf{x}$ với $S$. Thử chọn $\mathbf{x} $ là vector đặc trưng $\mathbf{\chi}_S$ của $S$. Vector đặc trưng được định nghĩa như sau:

$ \mathbf{\chi}_S [i]= \begin{cases} 1 & \mbox{if } i \in S\\ 0, & \mbox{otherwise } \end{cases}$

Với cách chọn như vây, dễ dàng suy ra:

1. $\mathbf{x}^T\mathbf{x} = |S|$
2. Áp dụng dạng toàn phương của ma trận Laplace, $\mathbf{x}^TL\mathbf{x} = \sum_{(i,j)\in E}(x[i] - x[j])^2 = \sum_{(i,j)\in \partial S}(x[i] - x[j])^2 = | \partial S|$

Như vậy, $\frac{\mathbf{x}^TL\mathbf{x}}{\mathbf{x}^T\mathbf{x}} = \frac{|\partial S|}{|S|} = \Phi(S)$.

Không may, vì ta cần phải chọn $\mathbf{x}$ thỏa mãn $\mathbf{x}^T \mathbf{1} \not= 0$. Với cách chọn hiện tại, $\mathbf{x}^T \mathbf{1} = |S|$ (bạn tự kiểm tra). Thay vào đó, ta sửa đổi cách chọn $\mathbf{x} = \mathbf{\chi}_S - s\mathbf{1}$, hay nói cách khác:

$ \mathbf{x} [i]= \begin{cases} 1 - s & \mbox{if } i \in S\\ -s, & \mbox{otherwise } \end{cases}$

Khi đó, $\mathbf{x}^T\mathbf{1} = 0, \mathbf{x}^T\mathbf{x} = |S|(1-s)^2 + (n-|S|)s^2 = |S|(1-s), \mathbf{x}^TL\mathbf{x} = |\partial S|$.

Thay vào $(14)$, ta có:

$ \lambda_2 \leq \frac{|\partial S|}{|S|(1-s)}$

Từ đó ta suy ra dpcm.

Bài tập

Bài tập 1: Không sử dụng bất đẳng thức Cheeger, chứng minh rằng $\lambda_2 = 0$ khi và chỉ khi đồ thị có ít nhất 2 thành phần liên thông. Hints: sử dụng dạng toàn phương của ma trận Laplace.

Bài tập 2: Mở rộng bài tập 1, chứng minh rằng $\lambda_k = 0$ khi và chỉ khi đồ thị có ít nhất k thành phần liên thông.

Hướng dẫn giải bài tập SGT01

Phần này mình đưa ra một số hướng dẫn giải bài tập trong bài trước.

Bài 1: Ta có: $M\mathbf{u} = \lambda \mathbf{u}$, suy ra $\mathbf{u}^TM^T = \lambda \mathbf{u}^T$. Do $M$ đối xứng, ta suy ra: $\mathbf{u}^TM = \lambda \mathbf{u}^T$. Nhân cả 2 vế với $\mathbf{u}$ và sử dụng tính chất $M\mathbf{v} = \lambda v$, ta sẽ suy ra dpcm.

Bài 2: Trước hết bạn chỉ cần chứng minh $\Pi^T\Pi = I$. Để chứng minh điều này, bạn có thể thử kiểm tra với hoán vị:
$\pi = \bigl(\begin{smallmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{smallmatrix}\bigr)$
và sau đó rút ra quy luật. Sau khi đã chứng minh được rồi, sử dụng tính kết hợp (associative property) của phép nhân ma trận ta suy ra:
$(\Pi A \Pi^T)(\Pi \mathbf{v}) = \Pi A (\Pi^T \Pi)\mathbf{v} = \Pi A \mathbf{v} = \Pi \lambda \mathbf{v} = \lambda \Pi \mathbf{v} $

Bài 3: Xem bài 2

Bài 4: Gọi $\lambda$ và $v$ tương ứng là trị riêng và vector riêng của $B$. Từ định nghĩa ma trận tương tự, ta suy ra:

$AM = MB \Rightarrow AM\mathrm{v} = MB \mathrm{v} \Rightarrow AM\mathrm{v} = \lambda M\mathrm{v} $
do đó, $M\mathrm{v}$ là vector riêng của $A$ ứng với trị riêng $\lambda$

Bài 5: Bài này muốn các bạn xem lại cách thao tác ma trận với dạng khối. Ta có thể viết $\Phi = \bigl(\mathbf{v}_1 \Phi_1\bigr)$ trong đó $\Phi_{1}$ là ma trận $(n-1)\times (n-1)$ và mỗi cột là một vector tương ứng trong $\{\mathbf{v}_2,\ldots, \mathbf{v}_n\}$. Khi đó, ta viết:

$\Phi^T M \Phi = \bigl(\begin{smallmatrix} \mathbf{v}_1^T \\ \Phi_1\end{smallmatrix}\bigr)M \bigl(\begin{smallmatrix} \mathbf{v}_1^T & \Phi_1\end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} \mathbf{v}_1^TM \mathbf{v}_1 & \mathbf{v}_1^TM\Phi_1 \\ \Phi_1^TM \mathbf{v}_1 & \Phi_1^TM\Phi_1 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} \lambda_1 & 0 \\ 0 & \Phi_1^TM\Phi_1 \end{smallmatrix}\bigr)$
Sau đó áp dụng quy nạp cho $\Phi_1^TM\Phi_1$, ta sẽ suy ra điều phải chứng minh.

Đối với vế thứ 2 của bài này, chỉ cần chú ý $\Phi\Phi^T = I$.

Bài 6: Phương trình $(10)$ chỉ cần viết rõ ràng kết quả của $\mathrm{Tr}$ của 2 vế. Với phương trình $(11)$, áp dụng bài tập 5 và phương trình $(10)$. Cụ thể:

$\mathrm{Tr}(M) = \mathrm{Tr}(\Phi \Lambda \Phi^T) = \mathrm{Tr}(\Phi^T\Phi\Lambda ) = \mathrm{Tr}(\Lambda ) = \sum_{i=1}^n \lambda_i$.

Tham khảo
[1] Daniel Speilman. Spectral Graph Theory Notes, Fall 2015, Lecture 01 and 02.
[2] Dhillon, Inderjit S. Co-clustering Documents and Words using Bipartite Spectral Graph Partitioning. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2001.
[3] Von Luxburg, Ulrike. A Tutorial on Spectral Clustering."= Statistics and Computing 17.4 (2007): 395-416.