谱图理论入门：图傅里叶变换与谱卷积知识详解

前言

之前做可解释 模型  的时候，看了图卷积相关的资料及论文，对谱图理论及空域图理论有一些理解。这个博文包含了自己先前总结及思考的知识点，是一个 from scratch 的学习路线图。后续会逐步更新业界常见及最新的谱图及空域图相关论文。

重点需要理解的地方

• 傅立叶变换中的基的理解，即basis
• 图卷积的定义是为了迎合卷积定理?
• 图卷积  f ∗ h = U ( U T f ⊙ U T h ) f*h=U(U^Tf\odot U^Th) f∗h=U(UTf⊙UTh) 中的  h h h 是卷积核，既可以作为顶点的函数，也可以作为特征向量的函数。

(Spectral Graph Theory)

谱图理论是研究图的性质与特征多项式，特征值和与图相关的矩阵特征向量的关系，例如图的  和 Laplacian矩阵。¹

• Laplacian允许在离散表示（如graphs）和连续表示（如vector space和manifolds）之间建立自然链接。
• Laplacian最重要的应用是谱聚类(spectral clustering)，它对应于图的划分问题(graph partitioning problem)的计算上易于处理的解决方案。
• Laplacian另一个应用是谱匹配(spectral matching)，它解决了图匹配(graph matching)。

谱图理论应用：²

• 谱划分（Spectral partitioning）：Image Segmentation。我看了一些基于谱划分的paper，效果不是很好，远低于基于深度学习的paper。
• 文档分类、协同推荐等
• 流形分析（Manifold analysis）：流形嵌入（Manifold embedding）、流形学习（manifold learning）、网格分割（mesh segmentation）等。

Laplacian矩阵

Laplacian矩阵简介

Laplacian矩阵是图的矩阵表示，可以看作是  得到的逼近负连续拉普拉斯的图上负离散拉普拉斯 运算符  的矩阵形式。 基于图的信号处理是基于  ，它扩展了传统的  ，将  替换为对应于信号的  的特征向量。³

Laplacian矩阵在  的应用中更为常见， 将图的属性与谱(spectrum)相关联，即与图相关的矩阵的特征值和特征向量，例如其邻接矩阵或Laplacian矩阵。不平衡的权重可能会对矩阵谱产生不利影响，导致需要归一化——矩阵条目(entries)的列/行缩放——导致归一化的邻接和Laplacian矩阵。

• 无向图Laplacian矩阵： L = D − A L=D-A L=D−A
• ： L s y m = ( D + ) 1 2 L ( D + ) 1 2 = I − ( D + ) 1 2 A ( D + ) 1 2 L^{sym}=(D^+)^{\frac 1 2}L(D^+)^{\frac 1 2}=I-(D^+)^{\frac 1 2}A(D^+)^{\frac 1 2} Lsym=(D+)21​L(D+)21​=I−(D+)21​A(D+)21​
• 左()和右归一化Laplacians： L r w = D + L = I − D + A L^{rw}=D^+L=I-D^+A Lrw=D+L=I−D+A
• 右归一化Laplacian矩阵： L D + = I − A D + LD^+=I-AD^+ LD+=I−AD+

为什么谱图卷积使用到了拉普拉斯矩阵?（待更新）

Laplacian矩阵特征分解

Laplacian矩阵分解(Laplacian Matrix Eigendecomposition)也称为谱分解(spectral decomposition)。

   因为Laplacian矩阵是实对称矩阵，所以可以被正交对角化：
L = U Λ U T =   U [ λ 1 λ 2 ⋱ λ n ] U T

𝐿=𝑈Λ𝑈𝑇= 𝑈𝜆1𝜆2⋱𝜆𝑛𝑈𝑇     L = U Λ UT =   U  [     λ 1           λ 2          ⋱          λ n     ]  UT    L=UΛUT= U   ​λ1​​λ2​​⋱​λn​​   ​UT​​
U U U是列向量为单位特征向量的矩阵， λ l \lambda_l λl​为特征值。
 

从傅里叶变换到

经典傅里叶变换

傅里叶级数 知识参见：
\quad 矩形波的傅里叶级数及代码

   FT参考链接：
\quad 傅里叶级数和傅里叶变换是什么关系？ - 马同学的回答 - 知乎
\quad 傅里叶系列（二）傅里叶变换的推导 - 知乎
\quad 傅里叶变换 – 从 Hilbert Space 到傅里叶变换基
\quad 傅里叶变换基的疑问

傅里叶级数是针对周期函数的，为了可以处理非周期函数，需要傅里叶变换(FT)。FT有助于将傅里叶级数扩展到非周期函数，这允许将任何函数视为简单正弦曲线的总和。

• FT将波形分解为正弦曲线，因此提供了另一种表示波形的方法。
• FT将作为时间函数的波形分解为构成它的频率。

传统的傅里叶变换公式为：
F ( ω ) = F [ f ( t ) ] = ∫ − ∞ + ∞ f ( t ) e − i ω t d t F(\omega)=\mathcal{F}[f(t)]=\int_{-\infin}^{+\infin}f(t)e^{-i\omega t}dt F(ω)=F[f(t)]=∫−∞+∞​f(t)e−iωtdt

离散傅里叶变换及逆变换

参考wiki百科-Discrete Fourier transform
F ( k ) = X k = ∑ n = 0 N − 1 x n ⋅ e − i 2 π N k n = ∑ n = 0 N − 1 x n ⋅ [ cos ⁡ ( 2 π N k n ) − i ⋅ sin ⁡ ( 2 π N k n ) ] ,

(𝑘)=𝑋𝑘=∑𝑛=0𝑁−1𝑥𝑛⋅𝑒−𝑖2𝜋𝑁𝑘𝑛=∑𝑛=0𝑁−1𝑥𝑛⋅[cos(2𝜋𝑁𝑘𝑛)−𝑖⋅sin(2𝜋𝑁𝑘𝑛)],      F  ( k ) =  X k     =  ∑  n = 0   N − 1    x n  ⋅ e −   i 2 π  N  k n        =  ∑  n = 0   N − 1    x n  ⋅  [ cos ⁡  (   2 π  N  k n )  − i ⋅ sin ⁡  (   2 π  N  k n )  ]  ,    F(k)=Xk​​=n=0∑N−1​xn​⋅e−Ni2π​kn=n=0∑N−1​xn​⋅[cos(N2π​kn)−i⋅sin(N2π​kn)],​

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删