CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記5.1：Spectral Clustering - 譜聚類基礎(chǔ)知識點(diǎn)

本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整

課程主頁：CS224W: Machine Learning with Graphs

視頻鏈接：【斯坦福】CS224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)

文章目錄

• CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記5.1：Spectral Clustering - 譜聚類基礎(chǔ)知識點(diǎn)
• • 1 引言
  • • 1.1 線性代數(shù)矩陣知識
    • 1.2 圖的矩陣表示
  • 2 一些概念
  • • 2.1 什么是譜（Spectral）
    • • • 譜圖理論（Spectral graph partitioning）
    • 2.2 圖拉普拉斯矩陣的由來
    • 2.3 拉普拉斯矩陣和拉普拉斯算子之間關(guān)系？
    • 2.4 拉普拉斯算子的物理含義？
  • 3 圖劃分
  • • 3.1 圖劃分與社區(qū)發(fā)現(xiàn)之間聯(lián)系與區(qū)別
    • • • 聯(lián)系
        • 區(qū)別
  • 4 參考文章

1 引言

**本節(jié)從矩陣計(jì)算和線性代數(shù)角度來分析圖。**而相關(guān)矩陣包括：鄰接矩陣和圖拉普拉斯矩陣。在進(jìn)入具體譜聚類算法介紹前，有必要先熟悉下相關(guān)矩陣、特征值和特征向量等相關(guān)知識。

1.1 線性代數(shù)矩陣知識

1.2 圖的矩陣表示

先復(fù)習(xí)下圖的矩陣表示形式。對于無向圖 $G=(V,E)$，與之相關(guān)的矩陣表示有如下三種：

鄰接矩陣A

度矩陣D

拉普拉斯矩陣L=D-A

其中拉普拉斯矩陣的性質(zhì)，是由其實(shí)對稱舉證性質(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í)際上矩陣指拉普拉斯矩陣 ，對它的特征值和特征向量的分解稱為譜分解.（特征分解，對角化，譜分解是一個概念）

譜圖理論（Spectral graph partitioning）

圖譜論是指分析圖G的矩陣表示的“頻譜”。頻譜是指由其對應(yīng)的特征值的大小升序排序的一組圖的特征向量：

• https://zhuanlan.zhihu.com/p/81502804

2.2 圖拉普拉斯矩陣的由來

整個譜圖理論都是圍繞著圖的拉普拉斯矩陣為核心進(jìn)行展開的，那么為什么將其定義為D-W呢？它其實(shí)是拉普拉斯算子在圖上的推廣，它是離散的拉普拉斯算子。

其第 i 行其實(shí)是第 i 個節(jié)點(diǎn)在產(chǎn)生擾動時對其他節(jié)點(diǎn)產(chǎn)生的收益累積。

具體可以看下面的鏈接里的公式推導(dǎo)：

• https://zhuanlan.zhihu.com/p/84649941

2.3 拉普拉斯矩陣和拉普拉斯算子之間關(guān)系？

拉普拉斯矩陣是離散的拉普拉斯算子。具體分析參考下文

• https://zhuanlan.zhihu.com/p/85287578

2.4 拉普拉斯算子的物理含義？

根據(jù)定義，函數(shù)的拉普拉斯算子${?}^{2}f$又可以寫成$???f$ ，其被定義為函數(shù) 梯度的散度。

拉普拉斯算子實(shí)際上衡量了在空間中的每一點(diǎn)處，該函數(shù)梯度（向量場）是傾向于增加還是減少.

• https://zhuanlan.zhihu.com/p/67336297

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

總結(jié)

以上是生活随笔為你收集整理的CS224W-图神经网络 笔记5.1：Spectral Clustering - 谱聚类基础知识点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。