CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記5.3：Spectral Clustering - 譜圖聚類的具體操作步驟
本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進行總結(jié)以求內(nèi)容完整
[toc]
引言
通過前一篇文章介紹，我們知道如何評價圖劃分的好壞；和為什么能根據(jù)圖拉普拉斯矩陣的第二小特征值對應(yīng)的特征向量對圖進行近似分割。前面算是理論部分，下面進入實踐部分。
1 譜聚類流程
1.1 譜聚類步驟
譜聚類過程分為三個步驟。
第三步劃分組，對倒數(shù)第二小特征向量進行升序排列后，如何確定分割的點呢？
基礎(chǔ)操作
- 取
0點作為分割點，（正負號） - 取
中位數(shù)作為分割點
- 取
其他 （相對復(fù)雜方法）
- 逐步計算，選擇使得Normalied cut 最小的分割點。（Sweep procedure）
1.2 如何實現(xiàn) K 分類呢？
上面介紹的都是二分的情況，如何推廣到多（K）分的情況呢？
具體，有2個基本的方法：
以分層劃分的方式遞歸地調(diào)用二分類算法
- 缺點是效率低，不穩(wěn)定（每一次都是近似，誤差會放大）。
采用多個特征向量的譜聚類
- 按照
的值（排除最小的 λ）從小到大依次取 m 個特征向量，將節(jié)點嵌入到低維空間中，每個節(jié)點通過 m 維數(shù)據(jù)表示，之后通過 K-means 算法進行聚類。通常也不需要取很大的值。多個特征向量，減少信息丟失，并已被證明能夠近似地逼近最優(yōu)劃分。
1.3 如何選擇社區(qū)的數(shù)量 K？
1.3.1 特征間距
可將特征值從大到小排序后，兩個連續(xù)的特征值之間的差被稱為特征間距（Eigengap）。
通常來說，通過選取最大化特征差距的 K 大概率能獲得穩(wěn)定的劃分結(jié)果。如下圖對應(yīng)的K=2是特征間距最大。
2 基于motif 的圖劃分
第三節(jié)中有介紹到motif，將圖拆解為一個個子圖來重新看待網(wǎng)絡(luò)，motif給了網(wǎng)絡(luò)一個新的定義方式，可以考慮從motif的角度（而不是上述邊的角度）出發(fā)來進行譜圖聚類。
具體操作過程與基于邊分割類似，不同的是需要對于劃分標準，拉普拉斯矩陣進行轉(zhuǎn)換。
2.1 Motif Conductance
對于最優(yōu)劃分標準類比edge cut和conductance，針對motif思想也是同樣，就是要組內(nèi)motif盡可能多，組間motif盡可能少。具體對比定義如下
所以問題就變成了，給定motif M和圖G，如何劃分節(jié)點，使motif conductance最小。但找到最小motif conductance也為np問題，也需要采用算法近似估算
2.2 Motif Spectral Clustering
類比一般譜圖聚類，基于motif的譜聚類也分為三步：
1. 數(shù)據(jù)預(yù)處理：基于motif對圖邊權(quán)重進行重新定義，每個邊權(quán)重為出現(xiàn)過的motif次數(shù).得到權(quán)重矩陣和拉普拉斯矩陣。
2. 分解：類似于標準的譜圖聚類方法，計算拉普拉斯矩陣和對應(yīng)的特征值特征向量
3. 分組：利用Sweep procedure方法，對第二小的特征值對應(yīng)的特征向量x的元素從小到達排列，計算每一種劃分下的motif conductance，選擇使motif conductance最小的劃分。
如下圖左下角所示，當r=5時，motif conductance最小。
此外，最小 motif conductance 也可以根據(jù)cheeger 不等式。
基于motif 的譜聚類算法的價值：
- 它提供了從更高維度去觀察網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的新角度。
- 算法簡單、快速和靈活，便于應(yīng)用。
2.3 基于motif的譜聚類案例
課上老師給了一個食物鏈網(wǎng)絡(luò)中基于motif的譜圖聚類結(jié)果。可以看出，基于motif的聚類在每一類結(jié)果中捕捉了特定的motif的結(jié)構(gòu)，在每一類內(nèi)部有較多的給定motif，而類與類之間這種motif較少。
參考文章
- https://blog.csdn.net/klcola/article/details/104800804
- 圖網(wǎng)絡(luò)機器學習 | 社區(qū)發(fā)現(xiàn) — 譜聚類算法
- 斯坦福CS224W 圖與機器學習5】Spectral Clustering
- 譜聚類方法推導和對拉普拉斯矩陣的理解
- 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
