机器学习|Graph Neural Network学习笔记-Day2 机器学习|卷积|人工智能

参考清单如下：
B站视频
知乎Johnny Richards
知乎Taylor Wu
接上一篇blog：Graph Neural Network学习笔记-Day1

文章目录

**Spectral-Based Convolution**
基础知识?Spectral Graph Theory
- 基本概念
- 拉普拉斯算子
- 怎么理解特征值是频率
- 关于拉普拉斯啰嗦点别的
- - 从热传播模型到图上的信号传播模型
  - - 热传播模型
    - 图的热传播模型（也可以是各种别的信号）
  - L的特征函数
- 傅里叶变换和拉普拉斯算子的关系
- 怎样把Graph傅里叶变换到频域做卷积
- 卷积函数的讨论
ChebNet
GCN

Spectral-Based Convolution 和Spatial-based convolution不同，Spectral-Based Convolution就是根据“时域卷积<==>频域乘积”的性质，通过傅里叶变换，把时域需要卷积的feature和卷积核，变换到频域，相乘之后再傅里叶反变换过去，从而完成卷积。

文章图片

基础知识?Spectral Graph Theory 主要是理解graph如何变换到谱域，如何进行傅里叶变换
基本概念

文章图片

什么是graph（包括节点，边，节点个数是N）
ajacency matrix（节点与节点之间有边则对应位置的矩阵元素为1，否则为0。是对称矩阵）
只考虑无向图
degree matrix（是对角矩阵，对角线元素就是节点的度
信号（节点上的一个函数）
如下图所示，一个demo graph和它上面的信号（如每个节点表示城市，那么信号可以是该城市的气温、人口增长数，等）

文章图片

拉普拉斯算子

文章图片

graph的拉普拉斯矩阵L=D-A
L是对称的
L进行谱分解L = U Λ U T L = U\Lambda U^T L=UΛUT
Λ = d i a g [ λ 0 , ? ? , λ N ? 1 ] \Lambda = diag[\lambda_0,\cdots,\lambda_{N-1}] Λ=diag[λ0?,?,λN?1?]对角矩阵，元素是L的特征值
U 酉矩阵， U = [ u 0 , ? ? , u N ? 1 ] U = [u_0,\cdots,u_{N-1}] U=[u0?,?,uN?1?]，列向量是L的特征值对应的特征向量。是一组标准正交基（自己和自己的内积是1，两两之间内积为0）。
λ l \lambda_l λl?就是谱域的频率，基向量 u l u_l ul?就是频率 λ l \lambda_l λl?对应的基向量。

对于demo graph，给出上面的信号 f f f。根据graph的样子，可以得到D，A，L，以及L谱分解之后的 Λ \Lambda Λ, U U U。

文章图片

怎么理解特征值是频率

文章图片

λ = 0 \lambda=0 λ=0就是直流分量，特征向量 u 0 u_0 u0?这四个节点上的信号强度相同， λ i \lambda_i λi?越大，特征向量在节点上变化的就越快。
还是以上面的demo graph为例子，考察拉普拉斯算子究竟干了什么~~

文章图片

如上图所示，L算子作用到graph的信号 f f f上面 L f = ( D ? A ) f = D f ? A f Lf = (D-A)f = Df - Af Lf=(D?A)f=Df?Af，只考察第一个节点 v 0 v_0 v0?, 第一个节点变换后的值$a = D(1,:) f - A(1,:)f，其中，其中，其中D(1,:) , , ,A(1,:)$ 分别表示这两个矩阵的第一行。那么就是 v 0 v_0 v0?上的signal f ( 1 ) f(1) f(1)乘以节点的度，然后减去与 v 0 v_0 v0?相邻的节点的信号。如上图，整理成v 0 v_0 v0?上的信号和它的邻居节点的信号之差，再求和。所以这就是信号强度的变化。如果考虑功率的话，就用 f T L f f^TLf fTLf，如下图所示，整理成了相邻node之间信号功率的变化，或者是graph上信号平滑程度。平滑程度就是频率，频率越高，相邻信号之间能量差就越大，频率越低，相邻信号之间的能量差就越小。

文章图片

【机器学习|Graph Neural Network学习笔记-Day2】把信号用特征向量替代，有

文章图片

所以特征值就是特征向量的频率大小。
例如下图中的demo graph，是一个具有20个node的 line graph。根据这个graph的L进行谱分解，得到的 λ \lambda λ和对应的 u u u如下面六张图，其中 λ \lambda λ越大，节点之间信号变化就越快。

文章图片

自己随便画了一下

文章图片

关于拉普拉斯啰嗦点别的参考知乎上一篇回答，感觉挺有趣。
从热传播模型到图上的信号传播模型
热传播模型顾名思义就是热量是怎么传播的咯。
牛顿冷却定律（Newton’s Law of Cooling)说，当物体表面与周围存在温度差时，单位时间从单位面积散失的热量与温度差成正比，比例系数称为热传递系数（摘自：百度百科）。假设这个比例系数为 k k k，在一维、离散假设下，位于 i i i处的一个点的温度为 ? i \phi_i ?i?,那么 ? i \phi_i ?i?变化快慢 d ? i d t \frac{d\phi_i}{dt} dtd?i??就是其周围相邻的两个点 i ? 1 i-1 i?1和 i + 1 i+1 i+1的温度 ? i ? 1 \phi_{i-1} ?i?1?和 ? i + 1 \phi_{i+1} ?i+1?分别与 ? i \phi_i ?i?的差乘以比例系数 k k k。即
d ? i d t = k ( ? i + 1 ? ? i ) ? k ( ? i ? ? i ? 1 ) \frac{d\phi_i}{dt} = k(\phi_{i+1} - \phi_i) - k(\phi_i - \phi_{i-1}) dtd?i??=k(?i+1???i?)?k(?i???i?1?)
这里假设点 i i i从 i + 1 i+1 i+1处接收热量，向 i ? 1 i-1 i?1处传播热量。这么表示是为了后面写成二阶导数的形式。。。其他情况也可以转化成该形式。
不难看出，等式右边其实是温度对空间位置的二阶偏导数，即
d ? i d t = k [ ( ? i + 1 ? ? i ) ? ( ? i ? ? i ? 1 ) ] = k ? 2 ? i ? x 2 \frac{d\phi_i}{dt} = k [(\phi_{i+1} - \phi_i) - (\phi_i - \phi_{i-1})] = k \frac{\partial^2 \phi_i}{\partial x^2} dtd?i??=k[(?i+1???i?)?(?i???i?1?)]=k?x2?2?i??
因此，一维连续空间的热传导方程就可以写为：
d ? d t ? k ? 2 ? ? x 2 = 0. \frac{d\phi}{dt} - k \frac{\partial^2 \phi}{\partial x^2} = 0. dtd???k?x2?2??=0.
上面是一维的情况，对于高维情况下，等式右边的二阶偏导数就变成了拉普拉斯算子 ▽ 2 \bigtriangledown^2 ▽2。
d ? d t ? k ▽ 2 ? = 0. \frac{d\phi}{dt} - k\bigtriangledown^2 \phi = 0. dtd???k▽2?=0.
拉普拉斯算子就是梯度的散度，是一个二阶微分算子，是笛卡尔坐标系 x i x_i xi?中的所有非混合二阶偏导数： ∑ i = 1 n ? 2 ? x i 2 \sum_{i=1}^{n}\frac{\partial^2}{\partial x_i^2} ∑i=1n??xi2??2?
图的热传播模型（也可以是各种别的信号）一个Graph可以表示为节点V和边E的集合。用邻接矩阵A（Ajacency Matrix）来表示各个节点之间的连接关系。 a i j = 1 a_{ij} = 1 aij?=1表示 v i v_i vi?和 v j v_j vj?之间是相连的； a i j = 0 a_{ij} = 0 aij?=0则表示 v i v_i vi?和 v j v_j vj?之间没有边。假设热量在图的节点与节点之间传播，那么只有在相邻的节点之间才有传播，因此
d ? v i d t = k ∑ j = 1 N a i j ( ? v i ? ? v j ) \frac{d \phi_{v_i}}{dt} = k \sum_{j=1}^N a_{ij} (\phi_{v_i} -\phi_{v_j}) dtd?vi???=k∑j=1N?aij?(?vi????vj??)
其中 N N N表示Graph中的节点总数。上式中，对于A中的第 i i i行，只把其中为1（与 v i v_i vi?相连接）对应的节点与节点 v i v_i vi?的温度差取出，乘以热传递的比例系数k。
把上面式子稍作整理：
d ? v i d t = k ( ? v i ∑ j = 1 N a i j ? ∑ j = 1 N a i j ? v j ) = k ( ? v i d i ? ∑ j = 1 N a i j ? v j ) \frac{d \phi_{v_i}}{dt} = k( \phi_{v_i} \sum_{j=1}^N a_{ij} - \sum_{j=1}^N a_{ij}\phi_{v_j}) = k (\phi_{v_i} d_i - \sum_{j=1}^N a_{ij}\phi_{v_j}) dtd?vi???=k(?vi??∑j=1N?aij??∑j=1N?aij??vj??)=k(?vi??di??∑j=1N?aij??vj??)
其中 d i d_i di?表示节点 v i v_i vi?的度。
把所有节点都考虑进来表示成列矩阵 ? = [ d ? v 1 d t , … , d ? v N d t ] T \phi = [\frac{d\phi_{v_1}}{dt},\dots,\frac{d\phi_{v_N}}{dt}]^T ?=[dtd?v1???,…,dtd?vN???]T，令D为对角矩阵，对角线元素就是节点的度，则
d ? d t = k ( D ? ? A ? ) = k ( D ? A ) ? \frac{d\phi}{dt} = k(D\phi - A\phi) = k(D-A)\phi dtd??=k(D??A?)=k(D?A)?
其中 D ? A D-A D?A就是拉普拉斯矩阵 L L L，所以有
d ? d t ? k L ? = 0 \frac{d\phi}{dt} - k L \phi =0 dtd???kL?=0
是不是和上面的红色公式一毛一样？？—区别只是一个是欧式空间、一个是拓扑空间哟。
d ? d t = k L ? \frac{d\phi}{dt} = k L \phi dtd??=kL? 这个公式可以这样解释哦，对一个graph上用L算子作用到每个节点的温度上是有什么意义呢？忽略这个常数k的话，L作用到 ? \phi ?得到的就是节点的温度变换率。
L的特征函数
欧式空间上，L的特征函数是 e ? j ω t e^{-j\omega t} e?jωt，因为易知
L e ? j ω t = ? ω 2 e ? j ω t L e^{-j\omega t} = -\omega^2 e^{-j\omega t} Le?jωt=?ω2e?jωt
欧式空间中，基函数（特征函数）有无穷多个
在graph里面，L是N维的，N是graph的节点数。所以特征空间是有限维的。
上面也很容易看出，特征向量对应的是和频率相关的。
傅里叶变换和拉普拉斯算子的关系一开始我们就说，spectral-based GNN是把graph和卷积核都进行傅里叶变换，在谱域相乘之后，反变换回来。那么为什么讲了半天L还没出现傅里叶变换呢？下面就是傅里叶变换了。

文章图片

傅里叶变换就是信号在一组基函数上的展开，这组基函数就是拉普拉斯算子的特征函数。
相应的，推广到graph上，就是把graph的信号在一组基向量上展开，用的就graph的拉普拉斯算子的特征向量 U U U。
所以graph的傅里叶变换就是
F = U T f F = U^Tf F=UTf 这里积分变成了向量的内积。意义都是一样的，都是原来的信号f在基函数 e ? j ω t e^{-j\omega t} e?jωt 或者基向量 u i u_i ui?是上面的投影。
下图解释的就是上面的graph的傅里叶变换。其中，内积的值对应的就是不同频率 λ 0 \lambda_0 λ0?, λ 1 \lambda_1 λ1?, λ 2 \lambda_2 λ2?, λ 3 \lambda_3 λ3?上面的信号分量的大小。

文章图片

这样我们就有了graph Fourier Transform的方法。
逆傅里叶变换更简单，就是

文章图片

因为 U U T = I UU^T = I UUT=I 所以就变回了原来的 x x x。当然也可以对应传统的逆傅里叶变换，从物理意义上去解释。
怎样把Graph傅里叶变换到频域做卷积卷积就相当于信号经过了一些线性系统，或者叫做滤波器。时域上是卷积，频域就是滤波器的频率响应和信号的频率相乘。把某一些频率的信号放大了，某一些频率的信号抑制了。如下图所示。

文章图片

graph的滤波
如下图，也是graph的信号的spectral domainx ^ \hat{x} x^，和一个滤波器 g θ ( Λ ) g_\theta(\Lambda) gθ?(Λ)相乘。滤波器的参数 θ \theta θ是待训练的参数，滤波器的自变量 Λ \Lambda Λ就是L的特征值，因为滤波器是在不同的特征值（频率）上的响应。比如 θ \theta θ可以定义为就是每个频率 λ i \lambda_i λi?上面的滤波器响应值 θ i \theta_i θi?。

文章图片

这样就在频域完成了滤波。最后反变换回去就可以了。也就是下图所示。

文章图片

整理一下，整个傅里叶变换，滤波，反变换过程，就是下图所示。其中把关于特征值的函数 g θ g_\theta gθ?提到外面，就变成了 y = g θ ( L ) x y=g_\theta(L)x y=gθ?(L)x

文章图片

对一个graph进行卷积，就是定义一个 g θ ( L ) g_\theta(L) gθ?(L)。
终于，卷积完成啦！！！
卷积函数的讨论如果按照下面的定义来构造graph convolution，很显然卷积核大小和graph的大小有关，是个问题。

文章图片

另外，L的几次方其实代表着对graph的卷积感受野的大小，L就是只考虑和node一步相邻的node， L k L^k Lk就表示k步相邻的node都考虑进去， L N L^N LN就是整个graph的全局特征了。对于某些数据集来讲，可能需要局部特征更好一些。

文章图片

也就是这里面说的第一代卷积核以及存在的问题

文章图片

ChebNet 选用的 g θ ( L ) g_\theta(L) gθ?(L)是L的多项式加权和，权重是要学习的参数 θ \theta θ，只考虑L的前K次方。但是因为还是要计算U矩阵的乘法，所以时间复杂度依然很高。

文章图片

为了解决上述问题，采用下面的Chebyshev多项式函数。可以递归计算~~

文章图片

根据Chebyshev多项式函数，把本来定义的关于 Λ \Lambda Λ的多项式函数替换成了Chebyshev多项式函数

文章图片

文章图片

可以用递归的方式来把 x ˉ 0 . . . x ˉ K \bar{x}_0...\bar{x}_K xˉ0?...xˉK?求好，然后和待学习的参数 θ ′ \theta' θ′相乘就得到了卷积输出。从而解决了要求N阶矩阵乘法的问题。
详细的过程点这个知乎
对应其中的第二代GCN
GCN ChebNet取K=1就是下面的了。