图卷积网络原理（二）【图信号与图的拉普拉斯矩阵】

矩阵乘法的三种视角

后续图卷积网络的原理讲解主要以矩阵乘法的显示展开，这里介绍矩阵乘法的几种不同的视角，这些视角有助于我们理解图卷积网络的逻辑过程。

对于矩阵 $A\in R^{m\times n}$ 和 矩阵 $B\in R^{n\times p}$，它们的乘积 $C\in R^{m\times p}$，可以由如下三种视角计算得到。

• 內积视角：这是我们本科阶段就接触到的视角。矩阵$C$ 的第i 行第 j 列是由矩阵 $A$ 的第$i$ 和矩阵$B$ 的第j列做內积运算得到。
  即：$c_{i,j}=A_{i,\ast }\times B_{\ast ,j}={\sum }_{k=1}^n{a}_{i,k}\ast b_{k,j}$。$A_{i,\ast }$表示A的第i行，$B_{\ast ,j}$表示B的第j列。
• 行向量视角：矩阵 $C$的第 $i$ 行可以看做矩阵$B$ 的所有行向量以矩阵$A$ 的第i行为系数，线性组合而得到。这里的逻辑是：矩阵 $C$ 的第 $i$ 行的形状是 $1\times p$,该形状与矩阵$B$ 的每一行的形状($1\times p$)是一致的。因此我们看可以把 $C$的第$i$ 行，看成是矩阵 $B$ 的所有行的线性组合。那么组合过程的系数是谁呢？因为每次组合，需要对矩阵$B$ 的 $m$ 个行向量进行组合，那么势必需要 $m$ 个系数，每个系数负责去乘以一个行向量，很自然地 矩阵$A$ 的第$i$ 列 恰好是有$m$ 个元素的，可以充当系数。
  于是我们有：$C_{i,\ast }=A_{\ast ,i}\times B$ 。
• 列向量视角： 矩阵 $C$的第$i$ 列，可以看做是矩阵 $A$的所有列向量，以矩阵$B$ 的第$i$ 行 为系数，线性组合而成。
  我们有：$C_{\ast ,i}=A\times B_{i,\ast }$ 。

举个例子来说：
对于矩阵 ：
$$A=\left[\begin{array}{ccc}1& -1& 2\\ 0& 2& 1\end{array}\right]B=\left[\begin{array}{cc}2& 0\\ -1& 1\\ 0& -1\end{array}\right]C=A\times B=\left[\begin{array}{cc}3& -3\\ -2& 1\end{array}\right]$$

內积视角：$c_{0,0}=A_{0,\ast }\times B_{\ast ,0}=\left[\begin{array}{ccc}1& -1& 2\end{array}\right]\times \left[\begin{array}{c}2\\ -1\\ 0\end{array}\right]=3$

行向量视角：$$\begin{array}{r}{C}_{0,\ast }=A_{0,\ast }\times B=\left[\begin{array}{ccc}1& -1& 2\end{array}\right]\times \left[\begin{array}{cc}2& 0\\ -1& 1\\ 0& -1\end{array}\right]=1\times \left(\begin{array}{cc}2& 0\end{array}\right)+-1\times \left(\begin{array}{cc}-1& 1\end{array}\right)+2\times \left(\begin{array}{cc}0& -1\end{array}\right)\\ =\left(\begin{array}{cc}3& -3\end{array}\right)\end{array}$$

列向量视角：
$$C_{\ast ,1}=A\times B_{\ast ,1}=\left[\begin{array}{ccc}1& -1& 2\\ 0& 2& 1\end{array}\right]\times \left[\begin{array}{c}0\\ 1\\ -1\end{array}\right]=0\times \left(\begin{array}{c}1\\ 0\end{array}\right)+1\times \left(\begin{array}{c}-1\\ 2\end{array}\right)+-1\times \left(\begin{array}{c}2\\ 1\end{array}\right)=\left(\begin{array}{c}-3\\ 1\end{array}\right)$$

图信号

给定图 $G=(V,E)$，其中 $V$ 表示节点集合，假设节点个数为 $N$ , E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\{(u,v)|u\in V,v \in V\} E={(u,v)∣u∈V,v∈V} 表示边集合。
所谓的图信号，是图节点到$m$维向量空间$R^m$的一个映射，即：$V\to R^m$，表示成向量的形式：$\mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ \dots \\ x_N\end{array}\right]$，其中 $x_i$ 表示第$i$ 个节点的特征信号。

为了方便后续的讲解，我们先把$m$ 限制为1。

在研究图上面节点特征信号的时候，除了要自然而然的考虑图信号本身以外，还需要考虑图里面节点之间的连接关系，不同图上同一特征信号具有不同的性质。

拉普拉斯矩阵是用来研究图结构性质的核心对象，它负责将图中节点之间的连接关系以矩阵的方式引入到模型之中，它充当了一个离散图信号与图拓扑关系之间的桥梁的角色。

拉普拉斯矩阵的定义为：$L=D-A$ ，其中$A$ 是图的邻接矩阵,如果$A_{ij}=1$ 说明存在 $(i,j)\in E$，如果$A_{ij}=0$ 说明$(i,j)\notin E$，而且规定$A_{ii}=0$；而 $D$ 是节点的出度矩阵，它是一个对角矩阵，其中$D_{ii}={\sum }_{j=1}^N{A}_{ij}$。因此 $L$ 的计算为：
$$D_{ij}=\{\begin{array}{rl}0& ,if(i,j)\notin E\\ -1& ,if(i,j)\in E,i\ne j\\ D_{ij}& ,ifi=j\end{array}$$

为啥说拉普拉斯矩阵是个桥梁呢 ？
我们可以看到特性信号向量 $\mathbf{x}$ 里面的每个元素是独立的，如果我们往$\mathbf{x}$ 左乘它所在图的拉普拉斯矩阵 $L$，
即：${\mathbf{x}}^{\prime }=L\mathbf{x}$ 。我们看可以得到什么：
$$\begin{array}{r}{\mathbf{x}}^{\prime }=L\mathbf{x}=(D-A)\mathbf{x}\end{array}$$
因为$L$ 的形状是$N\times N$，而$\mathbf{x}$的形状为$N\times 1$，于是它们乘积的结果${\mathbf{x}}^{\prime }$ 的形状是$N\times 1$ 。
如果我们从行向量视角来看${\mathbf{x}}^{\prime }$的计算的话，那么${\mathbf{x}}^{\prime }$的第$i$ 行可以看做是 $\mathbf{x}$的所有行的线性组合，而组合的系数是 $L$的第$i$ 行 ，即有：
$${\mathbf{x}}_{\mathbf{i}}^{\prime }=L_{i\ast }\mathbf{x}$$
而 $L$的第$i$ 里面，$L_{ii}$ 是节点$i$ 的出度，$L_{ij}=0$ 如果不存在节点$i$ 到节点 $j$的边，否则$L_{i,j}=-1$。因此
x i ′ = L i ∗ x = ∑ j ∈ { j ∣ ( i , j ) ∈ E } A i j x i − ∑ j ∈ { j ∣ ( i , j ) ∈ E } A i j x j = ∑ j ∈ { j ∣ ( i , j ) ∈ E } A i j x i − A i j x j = ∑ j ∈ { j ∣ ( i , j ) ∈ E } ( x i − x j ) \begin{aligned} \bold{x'_i}=L_{i*}\bold{x}=\sum_{j\in\{j|(i,j)\in E\}}A_{ij}x_i-\sum_{j\in \{j|(i,j)\in E\}}A_{ij}x_{j}\\=\sum_{j\in\{j|(i,j)\in E\}}A_{ij}x_i-A_{ij}x_{j}=\sum_{j\in\{j|(i,j)\in E\}}(x_i-x_{j}) \end{aligned} xi′​=Li∗​x=j∈{j∣(i,j)∈E}∑​Aij​xi​−j∈{j∣(i,j)∈E}∑​Aij​xj​=j∈{j∣(i,j)∈E}∑​Aij​xi​−Aij​xj​=j∈{j∣(i,j)∈E}∑​(xi​−xj​)​
也就是：${\mathbf{x}}^{\prime }$的第$i$ 个元素表示用节点$i$ 与其他所有从它出去的节点的特征信号差的和。

这反映了$i$ 节点的信号值与其他相邻节点信号值之间的差异程度。

当然了，这个差值的和是带符号的，如果出现一正一负的数据，他们进行求和后数值本身的绝对值会下降。
如果能够使用差的平方和就好了！

于是在${\mathbf{x}}^{\prime }$ 的基础上，我们左乘一个 ${\mathbf{x}}^T$:
p = x T x ′ = x T L x ′ = ∑ i = 1 N x i [ ∑ j ∈ { j ∣ ( i , j ) ∈ E } ( x i − x j ) ] = ∑ i = 1 N ∑ j ∈ { j ∣ ( i , j ) ∈ E } ( x i 2 − x i x j ) = x 1 2 − x 1 x 2 + x 1 2 − x 1 x 3 + ⋯ + x 1 2 − x 1 x j + x 2 2 − x 1 x 2 + x 2 2 − x 2 x 3 + ⋯ + x 2 2 − x 2 x j + ⋯ + x N 2 − x 1 x N + x N 2 − x N x 2 + ⋯ + x N 2 − x N x j + = ( x 1 2 − 2 x 1 x 2 + x 2 2 ) + ( x 1 2 − 2 x 1 x 3 + x 3 2 ) + ⋯ + ( x 1 2 − 2 x 1 x N + x N 2 ) + ( x 2 2 − 2 x 2 x 3 + x 3 2 ) + ⋯ + ( x 2 2 − 2 x 2 x N + x N 2 ) + … = ∑ { i , j ∣ ( i , j ) ∈ E } ( x i − x j ) 2 \begin{aligned} p=\bold{x}^T\bold{x'}=\bold{x}^TL\bold{x'}=\sum_{i=1}^{N}x_{i}[\sum_{j\in\{j|(i,j)\in E\}}(x_{i}-x_{j})]\\ =\sum_{i=1}^{N}\sum_{j\in\{j|(i,j)\in E\}}(x_{i}^2-x_{i}x_{j})\\ =x_{1}^{2}-x_1x_2+x_1^2-x_1x_3+\dots+x^2_1-x_1x_j+\\ x_{2}^{2}-x_1x_2+x_2^2-x_2x_3+\dots+x^2_2-x_2x_j+\\ \dots +\\ x_{N}^{2}-x_1x_N+x_N^2-x_Nx_2+\dots+x^2_N-x_Nx_j+\\ =(x_1^2-2x_1x_2+x^2_2)+(x^2_1-2x_1x_3+x^2_3)+\dots+(x^2_1-2x_1x_N+x^2_N)+\\ (x^2_2-2x_2x_3+x^2_3)+\dots+(x^2_2-2x_2x_N+x^2_N)+\dots\\ =\sum_{\{i,j|(i,j)\in E\}}(x_i-x_j)^2 \end{aligned} p=xTx′=xTLx′=i=1∑N​xi​[j∈{j∣(i,j)∈E}∑​(xi​−xj​)]=i=1∑N​j∈{j∣(i,j)∈E}∑​(xi2​−xi​xj​)=x12​−x1​x2​+x12​−x1​x3​+⋯+x12​−x1​xj​+x22​−x1​x2​+x22​−x2​x3​+⋯+x22​−x2​xj​+⋯+xN2​−x1​xN​+xN2​−xN​x2​+⋯+xN2​−xN​xj​+=(x12​−2x1​x2​+x22​)+(x12​−2x1​x3​+x32​)+⋯+(x12​−2x1​xN​+xN2​)+(x22​−2x2​x3​+x32​)+⋯+(x22​−2x2​xN​+xN2​)+…={i,j∣(i,j)∈E}∑​(xi​−xj​)2​
我们把这个标量叫做图信号的总变差,记做 $TV(\mathbf{x})={\mathbf{x}}^{T}L\mathbf{x}$ .
$TV(\mathbf{x})$ 反映了图上各节点信号的平滑程度，而且总变差总是非负的。