图傅里叶变换和图卷积

我这篇博客,目的是为了打下理解 GCN 的基础,介绍图傅里叶变换和图卷积。图傅里叶变换主要参考 [0] 这个讲义的前半部分。

先说一下 [0] 这篇讲义吧。这是一篇关于图的信号处理方法的讲义,我觉得对于 GCN 的理解非常有用,一眼看上去也还挺硬核,于是决定先看它。这篇讲义介绍了 ① 图信号处理的挑战 ② 各类定义图的谱域的方法 ③ 对于图信号的各种操作 ④ 高维图的局部多尺度变换方法。本博客只介绍 ①②,③④ 以后再说。

这个讲义我看的比较吃力(跳步真的太多了喂!),查阅了比较多的文章,都有写引用。建议阅读我所有引用的文章,对理解很有帮助。后面的图卷积相对还没有那么难理解,直接看我写的就好啦。

1 简介

在图结构中,边权可以被看做是点之间的相似度,连接与否取决于实际问题的物理意义或从数据中推断;图中的数据可以被视为有限的样本集合,也就是把每个顶点的数据当做一次采样。我们就把顶点上的这些“采样”叫做图信号(graph signal),下图就是一个 peterson 图上信号的例子,高度代表顶点上的值:

在图信号上的数据处理任务包括滤波(filtering)、降噪(denoising)、修复(inpainting)和压缩(compressing)。

1.1 图信号处理的主要挑战

有 $N$ 个顶点的图上的信号,可以像 $N$ 次采样的离散时间信号一样,用长为 $N$ 的向量表示。但是,如果用传统的信号处理方法来处理图信号,就会忽略了图的不规则结构的信息依赖。另外,很多传统信号处理中的基本概念在图信号处理问题上也存在问题:

  1. 模拟信号 $f(t)$ 的平移,$f(t-3)$ 即可。但是,图信号的 $f(t-3)$ 操作代表什么呢?倒是可以把所有顶点从 $1$ 到 $N$ 标号,然后令 $f(t-3):=f(mod(t-3,N))$,但这似乎没啥意义。这种图的结构是不规则的,因此不具有平移不变性。(所以怎么卷积?怎么参数共享?)
  2. 谱域信号的平移,乘个 $e^{jw}$ 即可。但是,图信号是离散的,且不均匀的,因此并不太能“在谱域平移”
  3. 离散信号的下采样,每 x 个取一个即可。但是,不规则结构的图信号怎么下采样?

除此之外,当图中数据很多时,信号处理要求只采用 localized 的操作(就比如 CNN,就是只在卷积核里有 localized 的卷积,只跟邻居发生关系),但是图结构怎么定义邻居呢?

综上所述,图上的信号处理存在的挑战主要就是 localize。

2 谱图理论

在图的信号处理领域,谱图理论被用来定义图傅里叶变换的频谱和坐标变换(basis expansion)(我搜了一下,就是把线性不可分的数据转换到另一个空间,使之线性可分,这个新的空间的基就叫做 expansion basis,详见 [2])

2.1 有权图和图信号

我们定义一个无向、连通、有权图 $G = \{\mathcal{V},\mathcal{E},W\}$,其中顶点集 $\mathcal{v}$ 的大小 $|\mathcal{V}|= N$,边集 $\mathcal{E}$,邻接矩阵 $W$。如果一个图有多个连通分量,就拆成多个上述的图。

邻接矩阵的一项 $W_{ij}$ 通常代表边的权重。如果没有显式地定义,通常按照如下式子定义:

$$W_{ij}= \begin{cases} exp(-\dfrac{[dist(i,j)]^2}{2\theta^2})& \text{if } dist(i,j)\le \mathcal{k} \\ 0& \text{otherwise} \end{cases} $$

当然,也可以把顶点连接到 $k$ 个最近的邻居。

定义图的顶点的一个函数 $f:\mathcal{V}\rightarrow \mathbb{R}$,可以表示成一个向量 $f\in \mathbb{R}^N$,向量的第 $i$ 个分量表示第 $i$ 个顶点的函数值。

2.2 图拉普拉斯矩阵

图拉普拉斯矩阵 $L:=D-W$ 是一个差分算子(difference operator,可见百度百科)。对于任何信号 $f\in\mathbb{R}N$,都满足:

$$(Lf)(i) = \sum_{j\in\mathcal{N}_i}W_{ij}[f(i) – f(j)]$$

其中,$\mathcal{N}_i$ 是和顶点 $i$ 有直接相邻边的点集。更普遍地,用 $\mathcal{N}(i,k)$ 表示跟顶点 $i$ 的距离 $\le k$ 的点集。

要理解上面这个式子,首先要知道,函数的拉普拉斯算子为:

$$\triangledown^2f=\dfrac{\partial^2f}{\partial x^2} + \dfrac{\partial^2f}{\partial y^2}$$

即梯度的散度。再看下 [4] 的“图(Graph)上热传播模型的推广”部分即可理解。

由于 $L$ 是实对称矩阵,所以有 $N$ 个非负特征值,这组特征值 $\sigma(L) = \{\lambda_0,\lambda_1,…,\lambda_{N-1}\}$ 就叫做谱。

如果想深入了解拉普拉斯矩阵,建议阅读 [9](虽然我也还没有认真读)

2.3 图傅里叶变换

经典的傅里叶变换:

$$\hat{f}(\xi):=\langle f,e^{2\pi i\xi t}\rangle = \int_\mathbb{R}f(t)e^{-2\pi i \xi t}dt$$

其中 $\xi$ 是频域的变量。不了解傅里叶变换的可以先看一下 [7]。这里我们可以把傅里叶变换看做将函数 $f(t)$ 向基函数 $e^{-2\pi i \xi t}$ 投影,傅里叶变换的结果 $\hat{f}(\xi)$ 就是在 $\xi$ 对应的基上的坐标(详见[6])。

从上面第一个等号看出,傅里叶变换本质上是函数和一个复指数的内积。而这个复指数就是上文说的基,也正是拉普拉斯算子的特征向量:

$$-\triangle(e^{2\pi i\xi t}) = -\frac{\partial^2}{\partial t^2}e^{2\pi i\xi t} = (2\pi\xi)^2e^{2\pi i\xi t}$$

看了 [4] 才知道,$\triangle$ 这个符号代表对各个坐标二阶导数的加和,其实就是拉普拉斯算子 $\triangledown^2$!又看了 [5],终于理解:原来上面等式中,第一个等号是带入拉普拉斯算子的定义 $\triangledown^2f=\partial^2f/\partial x^2 + \partial^2f/\partial y^2$,第二个等号是求出二阶导。对比第一项和最后一项发现,$e^{2\pi i\xi t}$ 就是 $\triangledown^2$ 的特征向量。

我们知道了傅里叶变换的本质,是求函数与正交基($e^{2\pi i\xi t}$)的内积。那么类似地,推广到图,图上的拉普拉斯矩阵就是离散化的拉普拉斯算子,图上的正交基就是拉普拉斯矩阵的特征向量。因此我们可以定义,图的函数 $f\in\mathbb{R}^N$(上文说过,用 $N$ 维向量表示)的傅里叶变换 $\hat{f}$ 为:

$$\hat{f}(\lambda_l):=\langle f,u_l\rangle = \sum_{i=1}^Nf(i)u_l^*(i)$$

其中,$u_l(i)$ 表示第 $l$ 个特征值的第 $i$ 个分量。那么在特征值(或者说频率) $\lambda_l$ 处对应的坐标,就是函数与 $\lambda_l$ 对应的特征向量 $u_l$ 进行内积运算。看了 [8] 才明白,由于上述的内积运算是在复数空间定义的,因此用的是 $u_l$ 的共轭。

图傅里叶反变换:

$$f(i) = \sum_{l=0}^{N-1}\hat{f}(\lambda_l)u_l(i)$$

这里再插一句我的理解:用机器学习的话说,图傅里叶变换,就是一个空间变换的过程,将原始数据转换到高维特征空间。这个空间的基就是拉普拉斯矩阵的特征值,求傅里叶变换的目的就是求原函数在这组基下的坐标。

对了,读到这里你可能会有这样的疑问:“为什么图拉普拉斯矩阵就是离散拉普拉斯算子呢?这俩形式差那么多,为啥名字差不多呢?” 这是因为,在某点处计算离散拉普拉斯算子,表示进行微小扰动后的总增益,即

$$\triangle f = \triangledown^2f=\sum_{i=1}^n\dfrac{\partial^2f}{\partial x_i^2}=\sum_{i=1}^n f”(x_i)$$

而对于图来说,顶点 $i$ 处的微小扰动,到达各点会有一个 $w_{ij}$ 的权重,权重为零则是无相邻的边,无法直接到达。因此计算图上的总增益,为:

$$\triangle f_i = \sum_{j=1}^nw_{ij}(f_i-f_j) = d_if_i -\sum_{j=1}^nw_{ij}f_j$$ $$\triangle f = \left( \begin{array}{c} \triangle f_1\\ \vdots\\ \triangle f_n \end{array} \right) = (D-W)f = Lf$$

因此计算这俩,都是同一个目的。故图拉普拉斯矩阵就是离散拉普拉斯算子(详见 [6])。

在传统傅里叶变换中,频率低($\xi$ 小)的正弦分量,波动慢;频率大的波动快。在连通图中也是同理,图拉普拉斯矩阵零特征值对应的特征向量 $u_0$ 是常量(直流分量),且在每个顶点都是 $\frac{1}{\sqrt{N}}$(我在网上查的说是 $(1,1,…,1)^T$,差不多,不计较了)。小特征值对应的特征向量,在图上传播的“很慢”。我这里还是用谱聚类的切图理解的,小特征值的特征向量就是更 bottleneck 的地方,传播的也就更“慢”。

作者举了个🌰,说如果两个顶点之间的边权较大,那么这俩点处,在谱域的这个小特征值对应的特征向量(就是一个基)上的坐标,会非常可能相似。这个乍一看很难理解,但是可以把它类比到传统信号的傅里叶变换上:“图上两点边权大”就是距离近([3] 推导里看到的),“特征向量上坐标相似”就是在频域的分量差不多。整句话转换过来就是,在时域相隔很近的两处对信号采样,这两个值在频域上,低频分量可能非常接近。这是因为相距很近,低频分量“波动慢”,变化就小。

那与之相反,图拉普拉斯矩阵的大特征值对应的特征向量,在图上“波动”的就更剧烈;大边权的两点,在大特征值对应的特征向量上,可能相去甚远(因为高频信号变得快)。

这张图的横坐标是在不同大小的特征值对应的分量,纵坐标对应的是图上的过零边(zero crossing),即连接的两个顶点,一个信号是正数,一个信号是负数。这张图表明,频率越高,过零边越多。这是因为相邻两点在高频分量的变化可能更大,与上面说的结论一致。

以上就是 [0] 的前半部分,不过为了后面学习 GCN,还要在图傅里叶变换的理解上更加深入。

2.4 矩阵形式的图傅里叶变换

上文说过,傅里叶变换是将函数向基投影。那怎么找这组基呢?拉普拉斯矩阵可以进行如下的特征分解:

$$L=U\Lambda U^T$$

其中 $U$ 的每一列都是 $L$ 的特征向量,构成一组基,$\Lambda$ 是对角矩阵,对角线上是 $L$ 的特征值。

上文说过,图傅里叶变换的表达式:

$$F(\lambda_l) = \hat{f}(\lambda_l)= \sum_{i=1}^Nf(i)u_l^*(i)$$

那么把每个分量都写出来,就得到矩阵形式:

$$ \left( \begin{array}{c} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2)\\ \vdots\\ \hat{f}(\lambda_N) \end{array} \right) = \left( \begin{array}{cccc} u_1(1) & u_1(2) & \cdots & u_1(N)\\ u_2(1) & u_2(2) & \cdots & u_2(N)\\ \vdots & \vdots & \ddots & \vdots\\ u_N(1) & u_N(2) & \cdots & u_N(N)\\ \end{array} \right) \left( \begin{array}{c} f(1)\\ f(2)\\ \vdots\\ f(N) \end{array} \right) $$

$$\hat{f} = U^Tf$$

图傅里叶逆变换为:

$$f = U\hat{f}$$

推理的过程同上,或见 [10]。

这里小结一下。图的傅里叶变换感觉并不是非常严谨的把傅里叶变换扩展到图上,而只是经过很多类比,定义成的样子。

3 图卷积

图卷积也是用卷积定理来类比,推广到图上的。

卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即对于函数 $f(t),h(t)$,满足:

$$f*h = \mathcal{F}^{-1}[\hat{f}(\omega)\hat{h}(\omega)] = \frac{1}{2\pi}\int \hat{f}(\omega)\hat{h}(\omega)e^{i\omega t}d\omega$$

类推到图上,我们把图傅里叶变换的定义 $\hat{f} = U^Tf$ 代入,就可以直接得到函数 $f$ 与卷积核 $h$ 在图上的卷积:

$$(f*h)_G = U((U^Th)\odot(U^Tf))$$

中间的 Hadamard product 是同形矩阵,同位置相乘。为啥是 $\odot$?详见 [10]。

另外,图卷积实际上并不是卷积了,只是“频域相乘再回来”的过程,和数学里的卷积定义不同!具体详见 [6]。

ok,有了上面这些基础,就可以开始看 GCN 啦!下篇文章见!

4 引用和拓展阅读

[0] Shuman, David I., et al. "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains." IEEE Signal Processing Magazine 30.3 (2013): 83-98.

[1] 如何通俗地讲解傅立叶分析和小波分析间的关系? – 咚懂咚懂咚的回答 – 知乎 很好理解,必看

[2] Lecture 4. Logistic Regression & Basis Expansion 大致知道 Basis Expansion 的概念就好

[3] 【其实贼简单】拉普拉斯算子和拉普拉斯矩阵 – Clyce的文章 – 知乎 深度好文!必看!讲解了图拉普拉斯矩阵、图拉普拉斯算子的具体理解!必看!!!

[4] 如何理解 Graph Convolutional Network(GCN)? – Johnny Richards的回答 – 知乎 必看!也是很好的讲解了拉普拉斯算子

[5] 图卷积神经网络(Graph Convolutional Network, GCN) 从零开始,推出 GCN。必看!#TODO

[6] 图傅里叶变换 – Dwzb的文章 – 知乎 必读!很好懂!

[7] 傅里叶级数与傅里叶变换(一) 傅里叶级数与傅里叶变换(二) 傅里叶变换的基础知识

[8] 图(Graph)上的傅里叶变换 其实大部分都是从 [10] 抄的

[9] EIGENVALUES OF THE LAPLACIAN AND THEIR RELATIONSHIP TO THE CONNECTEDNESS OF A GRAPH #TODO

[10] 如何理解 Graph Convolutional Network(GCN)? – superbrother的回答 – 知乎 # TODO,以及后面的引用文章都要读

[11] 论文笔记:The Emerging Field of Signal Processing on Graphs

5 TODO

[0] [5] [9] [10] 看完

[mathjax]

Leave a Comment

电子邮件地址不会被公开。