CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記5.2：Spectral Clustering - 譜聚類主要思想及關(guān)鍵結(jié)論的證明
本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
[toc]
引言
本節(jié)除了介紹圖劃分（二分）的基本思路外，主要回答一個(gè)問題：為什么能根據(jù)圖拉普拉斯矩陣的第二小特征值對應(yīng)的特征向量對圖進(jìn)行分割？
1 圖劃分
圖劃分也要回答兩個(gè)問題：
- 怎么定義圖的一個(gè)好的劃分？（
標(biāo)準(zhǔn)） - 如何高效得到劃分結(jié)果？（
效率）
1.1 圖劃分標(biāo)準(zhǔn)
先以最簡單的圖對分（bi-partition）為例，（對于多分情況可以在二分的基礎(chǔ)上推廣）。評價(jià)指標(biāo)有：
1. 割集規(guī)模（Graph Cuts）
Cut是將被分割的邊的數(shù)量最少為圖分割的標(biāo)準(zhǔn)，這一標(biāo)準(zhǔn)存在一定問題
2. 傳導(dǎo)性（Conductance）
傳導(dǎo)性不光追求被分割邊數(shù)量最少，還兼顧組內(nèi)的連接。衡量了組間連通性相對于每個(gè)組的組內(nèi)連通性的程度。是個(gè)更好的圖分割標(biāo)準(zhǔn)。
雖然依據(jù)conductance可以獲得較為平衡的圖劃分，但是計(jì)算conductance 是NP-hard問題。
除了這兩個(gè)劃分標(biāo)準(zhǔn)外，還有如在圖像分割領(lǐng)域中用的比較多的Normalized cut（N-cut）等。
2 如何近似求解
要理解譜聚類算法需要掌握三個(gè)關(guān)鍵結(jié)論的證明。
2.1 一個(gè)不等式
這是一個(gè)關(guān)于對稱矩陣瑞利商性質(zhì)的證明。
瑞利定理（Rayleigh theorem）相關(guān)介紹課參考下面引用文章1
2.2 近似優(yōu)化方法
回到尋找最優(yōu)劃分解的問題，1973年 Fiedler 提出將二劃分的集合 A 和 B 的元素標(biāo)簽限制在 1 和 -1，且限制 2 個(gè)集合的元素個(gè)數(shù)相同（等價(jià)于與向量（1, 1, …, 1）垂直）可以實(shí)現(xiàn)最優(yōu)圖分割的目的。
由于無法在求解的過程中嚴(yán)格滿足上述條件(約束條件過分嚴(yán)格)，故對向量取值弱化約束的松弛法(relaxation)，允許它們?nèi)∪我鈱?shí)數(shù)。根據(jù)上面證明的瑞利定理（Rayleigh Theorem）提出最小化 Fiedler 提及的公式，就是求解拉普拉斯矩陣L的第二小的特征值 所對應(yīng)的特征向量x .x是最優(yōu)分割向量的近似?？梢酝ㄟ^x各維度的值的正負(fù)符號來決定相應(yīng)節(jié)點(diǎn)所屬的社區(qū)。
ps：為什么不是最小特征值對應(yīng)的特征向量呢？
因?yàn)?，圖拉普拉斯矩陣對應(yīng)的最小特征值為0，其特征向量取值全為1 的向量。
2.3 conductance 有下界
對于最優(yōu)分割標(biāo)準(zhǔn) 傳導(dǎo)性 conductance 是有下界的。第二小特征值小于等于兩倍的最優(yōu)傳導(dǎo)，也就是說將為最優(yōu)conductance的下界。
3 其他定義
- 拉普拉斯矩陣的第二小特征值也叫圖的
代數(shù)連通度. 因?yàn)楫?dāng)且僅當(dāng)網(wǎng)絡(luò)連通時(shí)，非零。如果網(wǎng)絡(luò)不連通，此時(shí)，通常分別將網(wǎng)絡(luò)的連通分支拿出來，分別應(yīng)用算法。
- 拉普拉斯矩陣的最大特征值也叫圖的
譜半徑.
總結(jié)
至此，算是介紹完對于圖分割的思想以及關(guān)鍵結(jié)論的介紹。解釋了為什么能根據(jù)圖拉普拉斯矩陣的第二小特征值對應(yīng)的特征向量對圖進(jìn)行分割。下面就是具體的分割算法，以及如何將二分推廣到多分情況。敬請期待！
參考文章
- https://blog.csdn.net/klcola/article/details/104800804
- 圖網(wǎng)絡(luò)機(jī)器學(xué)習(xí) | 社區(qū)發(fā)現(xiàn) — 譜聚類算法
- 斯坦福CS224W 圖與機(jī)器學(xué)習(xí)5】Spectral Clustering
- 譜聚類方法推導(dǎo)和對拉普拉斯矩陣的理解
- https://linalg.apachecn.org/#/docs/chapter21
- https://www.cnblogs.com/xingshansi/p/6702188.html?utm_source=itdadao&utm_medium=referral
- http://www.cs.yale.edu/homes/spielman/sgta/SpectTut.pdf
- http://www.math.ucsd.edu/~fan/wp/cheeger.pdf
