CS224W-圖神經(jīng)網(wǎng)絡 筆記5.1：Spectral Clustering - 譜聚類基礎知識點
本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)钞速，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進行總結(jié)以求內(nèi)容完整
[toc]
1 引言
本節(jié)從矩陣計算和線性代數(shù)角度來分析圖隘蝎。而相關(guān)矩陣包括：鄰接矩陣和圖拉普拉斯矩陣当编。在進入具體譜聚類算法介紹前掂器，有必要先熟悉下相關(guān)矩陣格嘁、特征值和特征向量等相關(guān)知識这橙。
1.1 線性代數(shù)矩陣知識
1.2 圖的矩陣表示
先復習下圖的矩陣表示形式欢摄。對于無向圖 熬丧，與之相關(guān)的矩陣表示有如下三種：
- 鄰接矩陣A
- 度矩陣D
- 拉普拉斯矩陣L=D-A
其中拉普拉斯矩陣的性質(zhì)，是由其實對稱舉證性質(zhì)決定的怀挠。其中有一點析蝴，關(guān)于特征值大于等于0（半正定）的證明如下：
來源：
http://www.sofasofa.io/forum_main_post.php?postid=1004484
2 一些概念
下面害捕，補充些關(guān)于譜圖相關(guān)的概念。
2.1 什么是譜（Spectral）
譜的定義：譜就是指矩陣特征值的集合闷畸。該名稱來自光譜尝盼，指一些純事物的集合，就像將矩陣分解成為特征值與特征向量腾啥。定義譜半徑為該方陣最大的特征值东涡。
在譜圖里面實際上矩陣指拉普拉斯矩陣 ，對它的特征值和特征向量的分解稱為譜分解.（特征分解倘待，對角化疮跑，譜分解是一個概念）
譜圖理論（Spectral graph partitioning）
圖譜論是指分析圖G的矩陣表示的“頻譜”。頻譜是指由其對應的特征值的大小升序排序的一組圖的特征向量：
2.2 圖拉普拉斯矩陣的由來
整個譜圖理論都是圍繞著圖的拉普拉斯矩陣為核心進行展開的凸舵，那么為什么將其定義為D-W呢剪芍？它其實是拉普拉斯算子在圖上的推廣油啤，它是離散的拉普拉斯算子。
其第 i 行其實是第 i 個節(jié)點在產(chǎn)生擾動時對其他節(jié)點產(chǎn)生的收益累積。
具體可以看下面的鏈接里的公式推導：
2.3 拉普拉斯矩陣和拉普拉斯算子之間關(guān)系童太？
拉普拉斯矩陣是離散的拉普拉斯算子移盆。具體分析參考下文
2.4 拉普拉斯算子的物理含義惰拱？
根據(jù)定義判没，函數(shù)的拉普拉斯算子又可以寫成
，其被定義為函數(shù) 梯度的
散度庄新。
拉普拉斯算子實際上衡量了在空間中的每一點處鞠眉，該函數(shù)梯度（向量場）是傾向于增加還是減少.
3 圖劃分
3.1 圖劃分與社區(qū)發(fā)現(xiàn)之間聯(lián)系與區(qū)別
聯(lián)系
圖劃分（graph partitioning）與社區(qū)發(fā)現(xiàn)（community detection):二者都是根據(jù)網(wǎng)絡中的邊的連接模式，把網(wǎng)絡中的頂點劃分成群組择诈、簇或者社區(qū)械蹋。使得同一群組間節(jié)點緊密連接，而不同群組間只有少數(shù)的邊羞芍。
區(qū)別
- 圖劃分得到的
群組的數(shù)量基本是確定的哗戈，而社區(qū)發(fā)現(xiàn)是不確定的。 - 另外荷科，從
目的角度看唯咬，前者的目的通常是將網(wǎng)絡劃分為更多更小的塊，為了劃分而劃分畏浆。沒有好的劃分副渴，也要盡量在不好的劃分中選擇一種。而社區(qū)發(fā)現(xiàn)則是為了了解網(wǎng)絡結(jié)構(gòu)全度，沒有符合條件的劃分可以不劃分。
這小節(jié)斥滤，算是鋪墊将鸵。具體圖劃分以及譜聚類放到下一小結(jié)勉盅，再做討論。
4 參考文章
- GNN教程：第六篇Spectral算法細節(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
