图网络初步

1. 基础知识

1.1. 图的表示

给定一张图（Graph），记为$G = (V, E)$

结点$v$的度（degree），记为$\operatorname{d} (v)$或$\operatorname{deg} (v)$，表示一个结点的邻居结点的数量

1.2. 几种矩阵

• 邻接矩阵（Adjacency matrix）：$G = (V, E)$有$n$个结点，邻接矩阵$A \in \mathbb{R}^{n \times n}$表示为：

  $$A_{i j}=\left\{\begin{array}{ll} 1 & \text { if }\left\{v_{i}, v_{j}\right\} \in E \text { and } i \neq j \\ 0 & \text { otherwise } \end{array}\right.$$

  邻接矩阵是实对称矩阵

• 度矩阵（Degree matrix）：$G = (V, E)$有$n$个结点，度矩阵$D \in \mathbb{R}^{n \times n}$表示为：

  $$D_{ii} = \operatorname{d}(v_i)$$

  $D$是对角矩阵

• 拉普拉斯矩阵（Laplacian matrix）：对于一个无向图$G = (V, E)$有$n$个结点，$L \in \mathbb{R}^{n \times n}$定义为：

  $$L = D - A$$

  细化到每个元素：

  $$L_{i j}=\left\{\begin{array}{ll} d\left(v_{i}\right) & \text { if } i=j \\ -1 & \text { if }\left\{v_{i}, v_{j}\right\} \in E \text { and } i \neq j \\ 0 & \text { otherwise } \end{array}\right.$$

  显然，拉普拉斯矩阵也是实对称矩阵

• 对称归一化拉普拉斯矩阵（Symmetric normalized Laplacian matrix）：对Laplacian matrix做归一化：

  $$\begin{aligned} L^{s y m} &=D^{-\frac{1}{2}} L D^{-\frac{1}{2}} \\ &=I-D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \end{aligned}$$

  其中的元素为：

  $$L_{i j}^{s y m}=\left\{\begin{array}{ll} 1 & \text { if } i=j \text { and } d\left(v_{i}\right) \neq 0, \\ -\frac{1}{\sqrt{d\left(v_{i}\right) d\left(v_{j}\right)}} & \text { if }\left\{v_{i}, v_{j}\right\} \in E \text { and } i \neq j, \\ 0 \quad & \text { otherwise. } \end{array}\right.$$

---

举个例子🌰

对于上面一张有5个结点的无向图，可以得到其邻接矩阵与度矩阵为：

$$A = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{bmatrix}, \quad D = \begin{bmatrix} 4 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & 2 & \\ & & & & 2 \end{bmatrix}$$

相应的Laplacian矩阵为：

$$L = D - A = \begin{bmatrix} 4 & -1 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 2 & -1 \\ -1 & 0 & 0 & -1 & 2 \end{bmatrix}$$

计算Symmetric Normalized Laplacian matrix：

$$\begin{aligned} L^{s y m} &= D^{-\frac{1}{2}} L D^{-\frac{1}{2}} \\ &= \begin{bmatrix} 1/2 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & 1/\sqrt{2} & \\ & & & & 1/\sqrt{2} \end{bmatrix} \begin{bmatrix} 4 & -1 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 2 & -1 \\ -1 & 0 & 0 & -1 & 2 \end{bmatrix} \begin{bmatrix} 1/2 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & 1/\sqrt{2} & \\ & & & & 1/\sqrt{2} \end{bmatrix} \\ &= \begin{bmatrix} 1 & -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2\sqrt{2}} & -\frac{1}{2\sqrt{2}} \\ -\frac{1}{2} & 1 & 0 & 0 & 0 \\ -\frac{1}{2} & 0 & 1 & 0 & 0 \\ -\frac{1}{2\sqrt{2}} & 0 & 0 & 1 & -\frac{1}{2} \\ -\frac{1}{2\sqrt{2}} & 0 & 0 & -\frac{1}{2} & 1 \end{bmatrix} \end{aligned}$$

---

2. 图卷积的谱方法（Spectral Method）

2.1. 傅里叶变换

卷积和傅里叶变换有着密不可分的关系。在数学上，两个函数的卷积等于各自求傅里叶变换转成频域后乘积的逆傅里叶变换。傅里叶变换又可以通过谱图理论推广到Graph上进行变换。因此可以形成以下路线：

Convolution —— Fourier —— Spectral Graph

信号领域的傅里叶变换，简而言之就是构造频域内的一组正交基，一个函数在频域内可以由这组正交基线性表示。每个基都有自己的频率，同时表示一个函数时会有相应的傅里叶系数（即正交函数的振幅），这个傅里叶系数就是线性组合时的系数。可以表示如下：

$$f(x)=\sum_{k} F(k) e^{i k x}=\sum_{k} \underbrace{\frac{1}{2 \pi} \int_{-\infty}^{\infty} f\left(x^{\prime}\right) e^{-i k x^{\prime}} d x^{\prime}}_{\text {Fourier Coefficient }} e^{i k x}$$

其中$F(k)$是傅里叶系数，$e^{ikx}$是基函数，$k$是频率。

2.2. 图拉普拉斯算子

为了将信息领域的傅里叶变换引申到图，即在图上做傅里叶变换，需要有对应的三种量：频率、正交基、傅里叶系数，如果在图处理时也能找到对应的这三个表示，就能把图信号转换到频域。为此，需要引入图拉普拉斯算子，即前面所说的拉普拉斯矩阵。将拉普拉斯矩阵做谱分解，得到特征值和相应的特征向量，特征值就对应于傅里叶变换中的频率，而特征向量就对应于这个频率下的基函数。

现假设一张图$G$的结点数目为$n$，则其拉普拉斯矩阵为$L \in \mathbb{R}^{n \times n}$，则$L$是一个半正定实对称矩阵。

---

对于任意给定的向量$\boldsymbol{x}$，拉普拉斯矩阵的二次型为：$\boldsymbol{x}^TL\boldsymbol{x} = \sum_{e_{ij} \in E}(x_i - x_j)^2 \geq 0$，所以拉普拉斯矩阵是一个半正定矩阵，其所有特征值都大于0。

---

半正定实对称矩阵有如下的性质：

• 对称矩阵一定有$n$个线性无关的特征向量（$n$是Graph节点数）
• 半正定矩阵的特征值一定非负
• 对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵

对$L$矩阵做谱分解，可以得到：

$$L = U \Lambda U^T = \begin{bmatrix} \boldsymbol{\alpha}_1 & \boldsymbol{\alpha}_2 & \cdots & \boldsymbol{\alpha}_n \end{bmatrix} \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \\ \end{bmatrix} \begin{bmatrix} \boldsymbol{\alpha}_1^T \\ \boldsymbol{\alpha}_2^T \\ \vdots \\ \boldsymbol{\alpha}_n^T \end{bmatrix}$$

其中，$U \in \mathbb{R}^{n \times n}$是一个正交矩阵，满足$UU^T=I$。$U = \begin{bmatrix}
\boldsymbol{\alpha}_1 & \boldsymbol{\alpha}_2 & \cdots & \boldsymbol{\alpha}_n
\end{bmatrix}$表示$L$的$n$个特征向量，并且这些向量是线性无关的单位向量，$\boldsymbol{\alpha}_i \in \mathbb{R}^{n \times 1}$是列向量。$\lambda_k$是第$k$个特征向量对应的特征值，我们对特征值进行升序排列，即$\lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$。

现在可以对比一下传统信号的傅里叶变换与图上的傅里叶变换：

传统傅里叶变换	图傅里叶变换
频率	特征值
基函数	特征向量
傅里叶系数	傅里叶系数

现在只需要知道傅里叶系数如何计算，就可以得到完整的图傅里叶变换了。

假设一个有$n$个结点的图，其图上的信号用$\boldsymbol{x} = [x_1, x_2, \cdots, x_n]^T$来表示，其中$x_i$表示第$i$个结点上的信号强度，即图上每个结点的特征暂时都用一个标量来表示。定义图傅里叶变换为：

$$\boldsymbol{\tilde{x}} = U^T \boldsymbol{x}$$

$\boldsymbol{\tilde{x}} = [\tilde{x}_1, \tilde{x}_2, \cdots, \tilde{x}_n]$是信号$\boldsymbol{x}$经傅里叶变换后的表示，$\tilde{x}_i$是$\boldsymbol{x}$在第$i$个特征向量上的傅里叶系数，$\tilde{x}_i = <\boldsymbol{\alpha}_i, \boldsymbol{x}> = \boldsymbol{\alpha}_i^T \boldsymbol{x}$。这样就把图傅里叶变换与传统信号的傅里叶变换对应起来了。

同样可以定义图逆傅里叶变换：

由于$U$是一个正交矩阵，对$\boldsymbol{\tilde{x}} = U^T \boldsymbol{x}$左乘$U$，得$U\boldsymbol{\tilde{x}} = UU^T \boldsymbol{x} = \boldsymbol{x}$，即

$$\boldsymbol{x} = U \boldsymbol{\tilde{x}}$$

将上式展开成向量形式，如下：

$$\begin{align} \boldsymbol{x} &= U \boldsymbol{\tilde{x}} = \begin{bmatrix} \boldsymbol{\alpha}_1 & \boldsymbol{\alpha}_2 & \cdots & \boldsymbol{\alpha}_n \end{bmatrix} \begin{bmatrix} \tilde{x}_1 \\ \tilde{x}_2 \\ \vdots \\ \tilde{x}_n \end{bmatrix} \\ &= \tilde{x}_1 \boldsymbol{\alpha}_1 + \tilde{x}_2 \boldsymbol{\alpha}_2 + \cdots + \tilde{x}_n \boldsymbol{\alpha}_n \\ &= \sum_{i=1}^{n}\tilde{x}_i \boldsymbol{\alpha}_i \end{align}$$

由此可以看出，图信号可以表示为拉普拉斯矩阵的特征向量的线性组合，这一点与传统傅里叶变换的思想也是一致的。

2.3. 番外：图拉普拉斯算子是如何定义的

一个很自然的想法是为什么定义拉普拉斯算子的人是怎么想到这个定义，以及这个定义和拉普拉斯有什么关系呢？首先需要看一下标准的拉普拉斯算子定义：

$$\Delta f=\sum_{i} \frac{\partial f}{\partial x^{2}}$$

即非混合二阶偏导数的和。$f$是拉普拉斯算子作用的「函数」，求函数各向二阶导数再求和，定义为$f$上的拉普拉斯算子。

图像作为一种离散数据（可以看做坐标的离散函数），拉普拉斯算子应该离散化。离散函数的一阶导数可以近似为一阶差分：

$$f^{\prime}(x)=\frac{\partial f(x)}{\partial x} \approx f(x+1)-f(x)$$

二阶导数近似于二阶差分：

$$\begin{aligned} f^{\prime \prime}(x)=\frac{\partial^{2} f(x)}{\partial x^{2}} &=f^{\prime}(x)-f^{\prime}(x-1) \\ &=(f(x+1)-f(x))-(f(x)-f(x-1)) \\ &=f(x+1)+f(x-1)-2 f(x) \\ &=[f(x+1)-f(x)]+[f(x-1)-f(x)] \end{aligned}$$

某个二阶导数等于其在所有自由度上微扰之后获得的增益。一维函数其自由度可以理解为2，分别是+1方向和-1方向，增益分别为$f(x+1)-f(x)$和$f(x-1)-f(x)$，总增益为所有方向增益的和。

对于二维图像而言，

$$\begin{aligned} (\Delta f)_{x, y} &=\frac{\partial f(x, y)}{\partial x^{2}}+\frac{\partial f(x, y)}{\partial y^{2}} \\ & \approx f(x+1, y)+f(x-1, y)-2 f(x, y) + f(x, y+1)+f(x, y-1)-2 f(x, y) \\ & = [f(x+1, y)-f(x, y)]+[f(x-1, y)-f(x, y)] + [f(x, y+1)-f(x, y)]+[f(x, y-1)-f(x, y)] \end{aligned}$$

上下左右共4个自由度$(1,0),(-1,0),(0,1),(0,-1)$，当然还可以任意的定义自由度，比如对角线也算的话，就是8个自由度。这样上式可以理解为：在图像上某一点，其拉普拉斯算子的值，即为对其进行扰动，使其变化到相邻像素后得到的增益。

这给我们一种形象的结论：拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益。

那么推广到Graph，对于有$n$个节点的Graph，其邻接矩阵为$W$（这里把邻接矩阵记作$W$是考虑到加权图，对于无权图来说，$W=A$），这个Graph的自由度为$n$。因为如果该图是一个完全图，即任意两个节点之间都有一条边，那么对一个节点进行微扰，它可能变成任意一个节点。

那么对于图来说，上面的函数$f$就理所当然是一个$n$维的向量，即

$$\boldsymbol{f}=\left(f_{1}, \ldots, f_{N}\right)$$

其中，$\boldsymbol{f}_i$表示函数在结点$i$的值（这里的$\boldsymbol{f}$就是上一节中用来表示图的向量$\boldsymbol{x}$）。

对于任意结点$i$，对结点$i$进行微扰，它可能变为任意一个与之相邻的结点$j \in N_{i}$。

前面提到，拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益。对于图而言，从结点$i$变化到结点$j$增益是$f_j - f_i$，不过通常这里经常写作写作取负数的形式（无非就是$L=D-W$还是$W-D$的问题），即$f_i - f_j$。再考虑边的权重，可以认为增益是$W_{ij}(f_i - f_j)$，那么对于结点$i$，总的增益即为拉普拉斯算子在结点$i$处的值：

$$\begin{aligned} (\Delta \boldsymbol{f})_{i} &=\sum_{j} \frac{\partial f_{i}}{\partial j^{2}} \\ & \approx \sum_{j \in N_{i}} W_{i j}\left(f_{i}-f_{j}\right) \\ &=\sum_{j} W_{i j}\left(f_{i}-f_{j}\right) \\ &=\sum_{j} W_{i j} f_{i}-\sum_{j} W_{i j} f_{j} \\ &=(\boldsymbol{D} \boldsymbol{f})_{i}-(\boldsymbol{W} \boldsymbol{f})_{i} \\ &=[(\boldsymbol{D}-\boldsymbol{W}) \boldsymbol{f}]_{i} \end{aligned}$$

上式中$j \in N_i$去掉是因为对于非邻接点$W_{ij} = 0$。

对于任意结点$i$， 都有上述的结论。故

$$\Delta \boldsymbol{f}=(\boldsymbol{D}-\boldsymbol{W}) \boldsymbol{f}$$

注意上式中$\Delta \boldsymbol{f}$要看作一个整体，表示图拉普拉斯算子作用在由图结点信息构成的向量上得到的结果。

对于无权图，$W$可以换成$A$，则拉普拉斯算子变为：

$$L = D - A$$

也就是拉普拉斯矩阵。

2.4. 图卷积

传统信号的卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数$f$与$h$，两者的卷积是其函数傅立叶变换乘积的逆变换，用公式表示即：

$$\boldsymbol{f} * \boldsymbol{h}=\mathcal{F}^{-1}[\hat{\boldsymbol{f}} \circ \hat{\boldsymbol{h}}]$$

类比到图信号上，$\boldsymbol{x} = [x_1, x_2, \cdots, x_n]^T$是图信号的表示，$\boldsymbol{h} = [h_1, h_2, \cdots, h_n]^T$是卷积核，我们可以将这两者都视为函数，则$\boldsymbol{x}$和$\boldsymbol{h}$的卷积可以按照以下步骤解出：

1. 计算$\boldsymbol{x}$的傅里叶变换$\boldsymbol{\tilde{x}} = U^T \boldsymbol{x}$
2. 计算卷积核$\boldsymbol{h}$的傅里叶变换$\boldsymbol{\tilde{h}} = U^T \boldsymbol{h}$
3. 求解$\boldsymbol{\tilde{x}}$和$\boldsymbol{\tilde{h}}$的element-wise乘积$\boldsymbol{\tilde{x}} \circ \boldsymbol{\tilde{h}}$，也等价与将$\boldsymbol{\tilde{h}}$组织为对角矩阵的形式$\operatorname{diag}(\boldsymbol{\tilde{h}})$，再计算其与$\boldsymbol{\tilde{x}}$的矩阵乘法，即$\operatorname{diag}(\boldsymbol{\tilde{h}}) \boldsymbol{\tilde{x}}$
4. 求上述结果的逆傅里叶变换，即左乘$U$

总结一下，图上的卷积定义为：

$$(\boldsymbol{x} * \boldsymbol{h})_{\mathcal{G}}= U \operatorname{diag}(\boldsymbol{\tilde{h}}) U^{T} \boldsymbol{x}$$

2.5. 参考

入门必读 | 图卷积神经网络理论基础：从傅里叶变换到图卷积

图拉普拉斯算子为何定义为D-W

3. 深度学习中的图卷积

深度学习中的Convolution就是要设计含有trainable共享参数的kernel，上面公式中的卷积核$\boldsymbol{h}$（及其傅里叶变换$\boldsymbol{\tilde{h}}$）是事先已经设定好的，如果将卷积核的傅里叶变换直接设为$\operatorname{diag}\left[\theta_{1}, \ldots, \theta_{n}\right]$作为参数进行学习，就可以得到初步的GCN¹：

$$\boldsymbol{y}_{\text {output }}=\sigma\left(U \boldsymbol{g}_{\theta} U^{T} \boldsymbol{x}\right)=\sigma\left(U \operatorname{diag}\left[\theta_{1}, \ldots, \theta_{n}\right] U^{T} \boldsymbol{x}\right)$$

上式中，$\boldsymbol{x}$就是graph上对应于每个结点的feature构成的向量$\boldsymbol{x} = [x_1, x_2, \cdots, x_n]^T$，目前仍然是每个结点信息是标量（即单通道），后续推广到向量很方便（多通道）。$\boldsymbol{y}_{\text {output }}$是该图卷积后的输出，所有的结点都要经过该操作，得到各自的输出。再$\sigma$激活后，传入下一层。$\boldsymbol{g}_{\boldsymbol{\theta}}=\operatorname{diag}\left[\theta_{1}, \ldots, \theta_{n}\right]$相当于拿这个卷积核每个节点卷一遍。

¹. Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013. ↩

4. 最初的图卷积网络（Graph Convolution Network）

GraphConv可以说是图卷积网络的开山之作。作者从谱卷积推导，给出的图卷积网络层的定义如下：

$$H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$$

其中，$\tilde{A} = A + I$是加了自连接的无向图的邻接矩阵，相应地，$\tilde{D}_{ii} = \sum_{j}\tilde{A}_{ij}$，即$\tilde{D} = D + I$；$H^{(l)} \in \mathbb{R}^{N \times D}$是第$l$层的输出，$N$是图中结点的数量，$D$是结点的特征向量的长度，$H^{(0)} = X$；$W^{(l)} \in \mathbb{R}^{D \times F}$的第$l$层的权重，是网络中的可训练值；$\sigma(\cdot)$为激活函数。