深蓝学院-GNN课程笔记01-图论基础

这个系列是深蓝学院图深度学习理论与实践的同步课程笔记。课程内容涉及图深度学习的基础理论与应用，本节主要介绍图论的基础知识。

图的表示

一个图(Graph)可以表示为 $G = {V, E}$ ，其中 $V = {v_{1}, . . ., v_{N}}$ 是节点的集合, $E = {e_{1}, . . ., e_{M}}$ 是边的集合。

一个图可以用邻接矩阵(adjacency matrix)来存储。给定一个图 $G = {V, E}$ ，对应的邻接矩阵可以表示为 $A = {0, 1}^{N \times N}$ ，如果 $v_{i}$ 和 $v_{j}$ 相邻则 $A_{i j} = 1$ 否则 $A_{i j} = 0$ 。显然无向图的邻接矩阵一定是对称的，上图对应的邻接矩阵为：

A = [\begin{matrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{matrix}]

图的性质

度

图的性质有很多，其中最基本的性质是节点的度(degree)，它表示与该节点相邻的其他节点的数目：

d (v_{i}) = \sum_{v_{i} \in V} 1_{E} ({v_{i}, v_{j}}) = \sum_{j = 1}^{N} A_{i j}

1_{E} ({v_{i}, v_{j}}) = {\begin{aligned} 1, & (v_{i}, v_{j}) \in E \\ 0, & otherwise \end{aligned}

同时，图上所有节点度的和(邻接矩阵中非零元素的个数)等于图上边数量的2倍：

\sum_{v_{i} \in V} d (v_{i}) = 2 | E |

在度的基础上我们可以定义邻域(neighborhood) $N (v_{i})$ ，它表示所有与节点 $v_{i}$ 相邻的节点构成的集合。显然邻域 $N (v_{i})$ 中元素的个数等于节点的度：

d (v_{i}) = | N (v_{i}) |

连通度

我们定义途径(walk)是节点与边的交替序列，从一个节点开始，以一个节点结束，其中每条边与紧邻的节点相连。途径的长度定义为途径中包含的边的数量。

在途径的基础上可以定义迹(trail)和路径(path)，其中迹是边各不相同的途径，而路径是节点各不相同的途径。换句话说，迹中不能有相同的边儿路径中不能有相同的节点。以下图为例， $(v_{1}, e_{4}, v_{4}, e_{5}, v_{5}, e_{6}, v_{1}, e_{1}, v_{2})$ 是一条迹但不是路径，而 $(v_{1}, e_{4}, v_{4}, e_{5}, v_{5}, e_{3}, v_{3})$ 则是一条路径。

给定一个图，如果图中的任意两个节点之间都至少存在一条路径，则称这个图是一个连通图(connected graph)。对于下图所表示的图，如果只考虑左半部分则它是一个连通图，如果把整个图放在一起考虑则不是一个连通图。

给定连通图中的任意两点，连接这两点的长度最小的路径被称为这两点之间的最短路径(shortest path)，最短路径的长度被称为两点间的距离。需要注意的是一对节点之间可能存在不止一条最短路径，如下图中 $v_{5}$ 和 $v_{2}$ 之间就存在2条最短路径。

通过最短路径我们可以定义图的直径(diameter)为图上最远的两点间的距离，即所有最短路径中的最长路径的长度。

中心性

节点的中心性(centrality)用来衡量节点在图上的重要程度，其中最基础的是度中心性(degree centrality)，它基于节点的度来测量中心性：

c_{d} (v_{i}) = d (v_{i}) = \sum_{j = 1}^{N} A_{i j}

度中心性背后的思想在于与节点 $v_{i}$ 相邻的节点越多， $v_{i}$ 在图上就越重要。

度中心性认为与节点 $v_{i}$ 相邻的节点都具有相同的重要性，然而在实际中不同节点的重要性往往是不同的。在此基础上我们可以定义节点的特征向量中心性(eigenvector centrality)来考虑相邻节点的中心性对中心节点的贡献：

c_{e} (v_{i}) = \frac{1}{λ} \sum_{j = 1}^{N} A_{i j} c_{e} (v_{j})

其中 $λ$ 为归一化系数。将上面的公式写成矩阵的形式不难发现特征向量中心性 $c_{e}$ 实际上对应了连接矩阵 $A$ 的特征向量，而 $λ$ 为对应的特征值：

λ c_{e} = A c_{e}

显然对于给定的图可能存在多个不同的特征向量，实际中一般可取最大特征值的作为特征向量中心性。

类似地，可以定义Katz中心性(Katz centrality)为：

c_{k} (v_{i}) = α \sum_{j = 1}^{N} A_{i j} c_{k} (v_{j}) + β

其中常数 $β$ 表示中心节点自身天然具有的重要性，而常数 $α$ 表示其他节点贡献的中心性相对于 $β$ 的权重。将上面的公式写成矩阵的形式得到：

c_{k} = α A c_{k} + β

(I - α A) c_{k} = β

显然常数 $α$ 和 $β$ 控制了Katz中心性的值，当 $α = \frac{1}{λ_{max}}$ 且 $β = 0$ 时Katz中心性即为特征向量中心性。同时需要注意 $α$ 的选取：比较大的 $α$ 容易导致矩阵 $I - α A$ 出现病态的情况，在实践中一般令 $α < \frac{1}{λ_{max}}$ ；而较小的 $α$ 会导致不同节点都具有相似的中心性，此时计算得到的中心性是没有意义的。

谱图论与图信号处理

拉普拉斯矩阵

拉普拉斯矩阵(Laplacian matrix)在图论中具有非常重要的应用，其定义为节点度矩阵与邻接矩阵的差：

L = D - A

由于度矩阵 $D$ 和邻接矩阵 $A$ 都是对称矩阵，显然拉普拉斯矩阵 $L$ 也是对称矩阵。

通过拉普拉斯矩阵可以度量每个节点与和它相邻节点的差异。假设节点 $v_{i}$ 具有的特征为 $f_{i}$ ，将拉普拉斯矩阵与节点特征向量相乘得到：

\begin{aligned} h & = L f \\ = (D - A) f \\ = D f - A f \end{aligned}

$h$ 中的每一项表示节点与每个相邻节点差的和：

\begin{aligned} h_{i} & = d (v_{i}) f_{i} - \sum_{j = 1}^{N} A_{i j} f_{j} \\ = \sum_{v_{j} \in N (v_{i})} (f_{i} - f_{j}) \end{aligned}

类似地， $f$ 关于拉普拉斯矩阵的二次型为：

\begin{aligned} f^{T} L f & = \sum_{v_{i} \in V} f_{i} \sum_{v_{j} \in N (v_{i})} (f_{i} - f_{j}) \\ = \sum_{v_{i} \in V} \sum_{v_{j} \in N (v_{i})} (f_{i} f_{i} - f_{i} f_{j}) \\ = \sum_{v_{i} \in V} \sum_{v_{j} \in N (v_{i})} (\frac{1}{2} f_{i} f_{i} - f_{i} f_{j} + \frac{1}{2} f_{j} f_{j}) \\ = \frac{1}{2} \sum_{v_{i} \in V} \sum_{v_{j} \in N (v_{i})} (f_{i} - f_{j})^{2} \end{aligned}

因此 $f^{T} L f$ 是相邻节点差的平方和，它表示相邻节点之间的差异。同时 $f^{T} L f \geq 0$ ，这说明拉普拉斯矩阵是半正定的。更进一步可以证明拉普拉斯矩阵0特征值的个数(特征值0的重数)等于图上连通分量的数目。

图信号处理

我们可以为图上的每一个节点赋予一个特征，这样的图数据结构称为图信号。图信号由图 $G = {V, E}$ 和节点域上定义的将节点映射为特征的映射 $f : V \to R^{d}$ 构成。

前面已经证明了拉普拉斯矩阵的二次型 $f^{T} L f$ 度量了图信号的光滑程度， $f^{T} L f$ 越小表示图上不同节点间的差异越小，图信号变化越平滑。因此， $f^{T} L f$ 也称为信号的平滑度(频率)。

在一维信号处理中同一个信号可以在时域和频域两个域上进行表示，它们之间的转换由傅里叶变换给出：

F (ξ) = ⟨ f (t), \exp {- 2 π i t ξ} ⟩ = \int_{- \infty}^{\infty} f (t) \exp {- 2 π i t ξ} d t

上式可以理解为将时域信号 $f (t)$ 投影到不同频率的基函数 $\exp {- 2 π i t ξ}$ 上。结合拉普拉斯算子不难发现基函数 $\exp {- 2 π i t ξ}$ 是拉普拉斯算子的特征函数：

\begin{aligned} Δ \exp {- 2 π i t ξ} & = \frac{\partial^{2}}{\partial t^{2}} \exp {- 2 π i t ξ} \\ = - (2 π ξ)^{2} \exp {- 2 π i t ξ} \end{aligned}

因此类似于一维信号处理，图上的傅里叶变换只需要将图信号投影到拉普拉斯矩阵的特征向量上即可：

F (l) = ⟨ f, u_{l} ⟩ = u_{l}^{T} f = \sum_{i = 1}^{N} f_{i} u_{l} [i]

其中 $u_{l}$ 是拉普拉斯矩阵的第 $l$ 个特征向量，对应的特征值 $λ_{l}$ 为 $u_{l}$ 的频率。

拉普拉斯矩阵的特征向量构成了图 $G$ 的傅里叶基，频域信号 $F$ 由图信号 $f$ 在这些傅里叶基上的系数组成。因此图傅里叶变换(graph Fourier transform, GFT)的矩阵形式为：

F = U^{T} f

其中 $U$ 的每一列均为拉普拉斯矩阵的特征向量。相应地，图傅里叶逆变换(inverse graph Fourier transform, IGFT)为：

f = U F

复杂图

到目前位置我们只考虑了无向图，但在实际应用中的图要复杂得多。本节最后介绍其它常见但更复杂的图类型。

异质图(heterogeneous graph)包含多种不同类型的节点和边来表示不同对象之间的关系。

二分图(bipartite graph)中可以将节点划分为两组互不相交的子集，每条边都连接着这两个子集中的节点。日常生活中电商平台的用户和商品就是典型的二分图。

多维图(multi-dimensional graph)中同一对节点之间允许存在多种不同的关系，其中每一种关系都可以单独建模成一张图。比如说视频网站中用户间的订阅、观看和评论就可以建模成具有3个维度的多维图。

符号图(signed graph)在社交网络中有着非常广泛的应用，用户间的「关注」行为可以看做是正关系，而「屏蔽」行为则是负关系。

超图(hypergraph)中允许多个节点通过同一条边连接起来。比如说论文构成的超图上同一个作者作为一条超边将他发表的所有文章连接起来。

前面介绍的图类型都是静态的，而动态图(dynamic graph)则允许图上的节点和边随时间不断演化。