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

Dear 丶 2022-11-21 14:43 169阅读 0赞

# 矩阵乘法的三种视角 #

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

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

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

举个例子来说：  
对于矩阵 ：  
 A = \[ 1 − 1 2 0 2 1 \] B = \[ 2 0 − 1 1 0 − 1 \] C = A × B = \[ 3 − 3 − 2 1 \] A= \\begin\{bmatrix\} 1 &-1 &2 \\\\ 0 & 2 &1 \\end\{bmatrix\} \\quad B=\\begin\{bmatrix\} 2 & 0 \\\\ -1 & 1\\\\ 0 & -1 \\end\{bmatrix\} \\quad C=A\\times B=\\begin\{bmatrix\} 3 &-3\\\\ -2&1 \\end\{bmatrix\} A=\[10−1221\]B=⎣⎡2−1001−1⎦⎤C=A×B=\[3−2−31\]

內积视角： c 0 , 0 = A 0 , ∗ × B ∗ , 0 = \[ 1 − 1 2 \] × \[ 2 − 1 0 \] = 3 c\_\{0,0\}=A\_\{0,\*\}\\times B\_\{\*,0\}=\\begin\{bmatrix\}1&-1&2\\end\{bmatrix\} \\times \\begin\{bmatrix\}2\\\\-1\\\\0\\end\{bmatrix\}=3 c0,0=A0,∗×B∗,0=\[1−12\]×⎣⎡2−10⎦⎤=3

行向量视角： C 0 , ∗ = A 0 , ∗ × B = \[ 1 − 1 2 \] × \[ 2 0 − 1 1 0 − 1 \] = 1 × ( 2 0 ) + − 1 × ( − 1 1 ) + 2 × ( 0 − 1 ) = ( 3 − 3 ) \\begin\{aligned\} C\_\{0,\*\}= A\_\{0,\*\} \\times B=\\begin\{bmatrix\}1&-1&2\\end\{bmatrix\} \\times \\begin\{bmatrix\} 2 & 0 \\\\ -1 & 1\\\\ 0 & -1 \\end\{bmatrix\}=1\\times \\begin\{pmatrix\}2&0\\end\{pmatrix\} + -1 \\times \\begin\{pmatrix\}-1&1\\end\{pmatrix\}+2 \\times \\begin\{pmatrix\}0&-1\\end\{pmatrix\}\\\\=\\begin\{pmatrix\}3&-3\\end\{pmatrix\} \\end\{aligned\} C0,∗=A0,∗×B=\[1−12\]×⎣⎡2−1001−1⎦⎤=1×(20)\+−1×(−11)\+2×(0−1)=(3−3)

列向量视角：  
 C ∗ , 1 = A × B ∗ , 1 = \[ 1 − 1 2 0 2 1 \] × \[ 0 1 − 1 \] = 0 × ( 1 0 ) + 1 × ( − 1 2 ) + − 1 × ( 2 1 ) = ( − 3 1 ) C\_\{\*,1\}=A \\times B\_\{\*,1\} = \\begin\{bmatrix\} 1 &-1 &2 \\\\ 0 & 2 &1 \\end\{bmatrix\} \\times \\begin\{bmatrix\} 0 \\\\ 1\\\\ -1 \\end\{bmatrix\}=0 \\times \\begin\{pmatrix\}1\\\\0\\end\{pmatrix\}+ 1 \\times \\begin\{pmatrix\}-1\\\\2\\end\{pmatrix\}+ -1 \\times \\begin\{pmatrix\}2\\\\1\\end\{pmatrix\}=\\begin\{pmatrix\}-3\\\\1\\end\{pmatrix\} C∗,1=A×B∗,1=\[10−1221\]×⎣⎡01−1⎦⎤=0×(10)\+1×(−12)\+−1×(21)=(−31)

# 图信号 #

给定图  G = ( V , E ) G=(V,E ) G=(V,E)，其中  V V V 表示节点集合，假设节点个数为  N N 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 m m维向量空间 R m R^m Rm的一个映射，即： V → R m V\\to R^m V→Rm，表示成向量的形式： x = \[ x 1 x 2 … x N \] \\bold\{x\}=\\begin\{bmatrix\}x\_1\\\\x\_2\\\\\\dots\\\\x\_N\\end\{bmatrix\} x=⎣⎢⎢⎡x1x2…xN⎦⎥⎥⎤，其中  x i x\_i xi 表示第 i i i 个节点的特征信号。

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

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

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

拉普拉斯矩阵的定义为： L = D − A L=D-A L=D−A ，其中 A A A 是图的邻接矩阵,如果 A i j = 1 A\_\{ij\}=1 Aij=1 说明存在  ( i , j ) ∈ E (i,j)\\in E (i,j)∈E，如果 A i j = 0 A\_\{ij\}=0 Aij=0 说明 ( i , j ) ∉ E (i,j)\\notin E (i,j)∈/E，而且规定 A i i = 0 A\_\{ii\}=0 Aii=0；而  D D D 是节点的出度矩阵，它是一个对角矩阵，其中 D i i = ∑ j = 1 N A i j D\_\{ii\}=\\sum^\{N\}\_\{j=1\}A\_\{ij\} Dii=∑j=1NAij。因此  L L L 的计算为：  
 D i j = \{ 0 , i f   ( i , j ) ∉ E − 1 , i f   ( i , j ) ∈ E , i ≠ j D i j , i f   i = j D\_\{ij\}=\\left\\\{ \\begin\{aligned\} 0 &,if \\space(i,j)\\notin E \\\\ -1&,if \\space (i,j) \\in E, i \\neq j \\\\ D\_\{ij\} &, if \\space i= j \\end\{aligned\} \\right. Dij=⎩⎪⎨⎪⎧0−1Dij,if (i,j)∈/E,if (i,j)∈E,i=j,if i=j

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

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

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

于是在 x ′ \\bold\{x'\} x′ 的基础上，我们左乘一个  x T \\bold\{x\}^T xT:  
 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∑Nxi\[j∈\{ j∣(i,j)∈E\}∑(xi−xj)\]=i=1∑Nj∈\{ j∣(i,j)∈E\}∑(xi2−xixj)=x12−x1x2\+x12−x1x3\+⋯\+x12−x1xj\+x22−x1x2\+x22−x2x3\+⋯\+x22−x2xj\+⋯\+xN2−x1xN\+xN2−xNx2\+⋯\+xN2−xNxj\+=(x12−2x1x2\+x22)\+(x12−2x1x3\+x32)\+⋯\+(x12−2x1xN\+xN2)\+(x22−2x2x3\+x32)\+⋯\+(x22−2x2xN\+xN2)\+…=\{ i,j∣(i,j)∈E\}∑(xi−xj)2  
我们把这个标量叫做图信号的总变差,记做  T V ( x ) = x T L x TV(\\bold\{x\})=\\bold\{x\}^TL\\bold\{x\} TV(x)=xTLx .  
 T V ( x ) TV(\\bold\{x\}) TV(x) 反映了图上各节点信号的平滑程度，而且总变差总是非负的。