CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記5.1：Spectral Clustering - 譜聚類基礎(chǔ)知識(shí)點(diǎn)
本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會(huì)參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
[toc]
1 引言
本節(jié)從矩陣計(jì)算和線性代數(shù)角度來分析圖。而相關(guān)矩陣包括：鄰接矩陣和圖拉普拉斯矩陣。在進(jìn)入具體譜聚類算法介紹前，有必要先熟悉下相關(guān)矩陣、特征值和特征向量等相關(guān)知識(shí)。
1.1 線性代數(shù)矩陣知識(shí)
1.2 圖的矩陣表示
先復(fù)習(xí)下圖的矩陣表示形式。對(duì)于無向圖 ，與之相關(guān)的矩陣表示有如下三種：
- 鄰接矩陣A
- 度矩陣D
- 拉普拉斯矩陣L=D-A
其中拉普拉斯矩陣的性質(zhì)，是由其實(shí)對(duì)稱舉證性質(zhì)決定的。其中有一點(diǎn)，關(guān)于特征值大于等于0（半正定）的證明如下：
來源：
http://www.sofasofa.io/forum_main_post.php?postid=1004484
2 一些概念
下面，補(bǔ)充些關(guān)于譜圖相關(guān)的概念。
2.1 什么是譜（Spectral）
譜的定義：譜就是指矩陣特征值的集合。該名稱來自光譜，指一些純事物的集合，就像將矩陣分解成為特征值與特征向量。定義譜半徑為該方陣最大的特征值。
在譜圖里面實(shí)際上矩陣指拉普拉斯矩陣 ，對(duì)它的特征值和特征向量的分解稱為譜分解.（特征分解，對(duì)角化，譜分解是一個(gè)概念）
譜圖理論（Spectral graph partitioning）
圖譜論是指分析圖G的矩陣表示的“頻譜”。頻譜是指由其對(duì)應(yīng)的特征值的大小升序排序的一組圖的特征向量：
2.2 圖拉普拉斯矩陣的由來
整個(gè)譜圖理論都是圍繞著圖的拉普拉斯矩陣為核心進(jìn)行展開的，那么為什么將其定義為D-W呢？它其實(shí)是拉普拉斯算子在圖上的推廣，它是離散的拉普拉斯算子。
其第 i 行其實(shí)是第 i 個(gè)節(jié)點(diǎn)在產(chǎn)生擾動(dòng)時(shí)對(duì)其他節(jié)點(diǎn)產(chǎn)生的收益累積。
具體可以看下面的鏈接里的公式推導(dǎo)：
2.3 拉普拉斯矩陣和拉普拉斯算子之間關(guān)系？
拉普拉斯矩陣是離散的拉普拉斯算子。具體分析參考下文
2.4 拉普拉斯算子的物理含義？
根據(jù)定義，函數(shù)的拉普拉斯算子又可以寫成
，其被定義為函數(shù) 梯度的
散度。
拉普拉斯算子實(shí)際上衡量了在空間中的每一點(diǎn)處，該函數(shù)梯度（向量場）是傾向于增加還是減少.
3 圖劃分
3.1 圖劃分與社區(qū)發(fā)現(xiàn)之間聯(lián)系與區(qū)別
聯(lián)系
圖劃分（graph partitioning）與社區(qū)發(fā)現(xiàn)（community detection):二者都是根據(jù)網(wǎng)絡(luò)中的邊的連接模式，把網(wǎng)絡(luò)中的頂點(diǎn)劃分成群組、簇或者社區(qū)。使得同一群組間節(jié)點(diǎn)緊密連接，而不同群組間只有少數(shù)的邊。
區(qū)別
- 圖劃分得到的
群組的數(shù)量基本是確定的，而社區(qū)發(fā)現(xiàn)是不確定的。 - 另外，從
目的角度看，前者的目的通常是將網(wǎng)絡(luò)劃分為更多更小的塊，為了劃分而劃分。沒有好的劃分，也要盡量在不好的劃分中選擇一種。而社區(qū)發(fā)現(xiàn)則是為了了解網(wǎng)絡(luò)結(jié)構(gòu)，沒有符合條件的劃分可以不劃分。
這小節(jié)，算是鋪墊。具體圖劃分以及譜聚類放到下一小結(jié)，再做討論。
4 參考文章
- GNN教程：第六篇Spectral算法細(xì)節(jié)詳解！
- https://zhuanlan.zhihu.com/p/85287578
- https://zhuanlan.zhihu.com/p/84649941
- https://zhuanlan.zhihu.com/p/81502804
- 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
