GNN 笔记：图上的傅里叶变换
1 圖拉普拉斯矩陣
圖拉普拉斯矩陣可以定義為： L=D-W。
其中，D 為度矩陣，W 為考慮權值的鄰接矩陣。
歸一化后的拉普拉斯矩陣：
1.1 散度
散度（Divergence）是向量分析的一個向量算子，將向量空間上的矢量場對應到一個標量場。
散度描述的是向量場里一個點是匯聚點還是發源點。
值為正時表示該點為發源點，值為負時表示該點為匯聚點，值為零時表示該點無源。
散度在物理上的含義可以理解為磁場、熱源等。
1.2?拉普拉斯算子
在數學中，拉普拉斯算子（Laplacian）是由歐幾里得空間中的一個函數的梯度的散度給出的微分算子。
對于任意函數 f?來說，其拉普拉斯算子的定義為：
拉普拉斯算子在 n 維空間笛卡爾坐標系中的數學定義（各個維度的二階偏導數之和）：
以一維空間為例：
拉普拉斯算子可以理解為當前點對其在所有自由度上微擾之后獲得的增益。這里自由度為 2，分別是 +1 和 -1 方向。
再以二維空間為例：
這里相當于是四個方向輕微擾動后得到的收益。
我們可以進行歸納：拉普拉斯算子是所有自由度上進行微小變化后所獲得的增益。
1.3?圖拉普拉斯算子的推導
我們將其推廣到網絡圖中，考慮有 N 個節點的網絡圖，其自由度最大為 N，那么函數 f?可以是 N 維的向量，即：
其中，?fi表示函數f在網絡圖中節點 i 處的函數值
上式對于任何i∈N都成立，所以我們有：
自此，我們便給出了圖拉普拉斯矩陣的推導過程.
這個公式的全稱為：圖拉普拉斯算子作用在由圖節點信息構成的向量上，得到的結果等于圖拉普拉斯矩陣和向量?的點積。
拉普拉斯矩陣反映了當前節點對周圍節點產生擾動時所產生的累積增益。直觀上也可以理解為某一節點的權值變為其相鄰節點權值的期望影響，形象一點就是拉普拉斯矩陣可以刻畫局部的平滑度。
1.4?拉普拉斯卷積核
剛才在介紹二維空間的拉普拉斯算子的時候，我們有：
把這個式子整理成二維矩陣的形式，就是圖像中的拉普拉斯卷積核了
| 0 | 1 | 0 |
| 1 | -4 | 1 |
| 0 | 1 | 0 |
2 拉普拉斯譜分解?
拉普拉斯矩陣的譜分解就是矩陣的特征分解：
對于無向圖來說，拉普拉斯矩陣是實對稱矩陣，而實對稱矩陣一定可以用正交矩陣進行正交相似對角化：
對拉普拉斯矩陣，我們左乘&右乘節點信號向量f，得到以下結果：
是圖信號的總變差（Total Variation），可以刻畫圖信號整體的平滑度。
2.1 拉普拉斯譜分解的性質
2.1.1
幾點說明：
1，拉普拉斯矩陣L=D-W，其中D是點i所有的邊的權重之和，也就是每一行（列）w之和。因此拉普拉斯矩陣每行（列）元素之和為0。
2，如果一個矩陣每一行（列）元素之和為0，那么一定有一個為0的特征值和一個全部值一樣的向量（如果是列向量，那么這個列向量右乘拉普拉斯矩陣，得到的向量每一個元素為拉普拉斯矩陣每行的和，即0）
2.1.2?拉普拉斯矩陣的特征值都大于等于零，歸一化的拉普拉斯矩陣的特征值區間為 [0, 2]
2.1.3?如果有 n 個特征值為 0，則表示圖有 n 個子圖相互無連接；
3 圖的傅里葉變換
一個結論：傅立葉分析是拉普拉斯譜分析的一個特例
3.1 傅里葉變化（回顧）
信號函數沿著基函數?各個分量進行分解
3.2 赫姆霍茲方程（Helmholtz Equation）
其實這個式子相當于對拉普拉斯矩陣的特征值分解
我們用基函數代替赫姆霍茲方程中的f（或者直接對基函數進行兩次微分也可以）
上面的推導可以說明是拉普拉斯算子的特征函數，同時也證明了離散傅立葉變換是拉普拉斯譜分析的一個特例。
3.3 網絡圖的傅里葉變換
我們把之前信號中的傅里葉變換看成：信號f和各個頻率ω對應的基函數相乘，然后求和。
類比一下，我們就有了網絡圖的傅里葉變換。此時的各個頻率就類比為各個特征值，各個頻率對應的基函數就類比為各個特征之對應的特征向量。
其中 ，u是圖的傅里葉矩陣（拉普拉斯矩陣）的特征向量。
3.3.1 網絡圖里面的傅里葉逆變換
總結
以上是生活随笔為你收集整理的GNN 笔记：图上的傅里叶变换的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python函数整理
- 下一篇： 文巾解题 679. 24 点游戏