·序言
段小宇讯号与系统+通信根本原理的教师应该对传递函数、低通滤波、振幅、傅立叶转换那些术语有基盘的感情吧。。。前一两年听了图神经收集研讨会的陈述后，想简单介绍下GCN 中传递函数、低通滤波等根本概念的认知，再者比来看了台大的相关课程觉得讲的十分好，也节录一些分享给各人。
本文脉络
传递函数、低通滤波、振幅的简单认知如前所述"基"的讯号造备与降解图收集的即非图传递函数有什么问题ChebNet 与 GCN
01
—
传递函数、低通滤波、振幅的简单认知
传递函数阿谁根本概念可能有些人从 CNN 那里才领会的，但其实传递函数做为一种运算在诸多工程范畴有着很长远的应用汗青。传递函数操做体例有时候也会被称为低通滤波操做体例，望文生义就是过滤器掉讯号中的那类成分 (那类振幅的波)。下面那句话隐含了3个意思：1）频域/低空讯号能转化成频域讯号；2）讯号在频域能复原成多个振幅的波；3）传递函数能对某一振幅的波做处置。
以相片处置为例，争取不消公式让各人简单认知下面3句话。
下面4那哥是随手跑的matlab 的成果。图1是原初 lena，是他们裸眼能认知的低空讯号。图2是将图1展开二维傅立叶转换后的频带图，是他们裸眼无法简单认知的振幅域讯号的可视化成果。越靠近频带图办事中心边线讯号振幅越低，即办事中心边线的讯号是高频讯号，关于低空图1中的像素变革很"慢"的扁平部分好比说外阴部和肩部。远离办事中心边线的讯号是高频讯号，相联系关系图1中的头发、帽檐等变革"很快"的部分。
他们接纳两个频域低通低通滤波器把图2中高频部分都过滤器掉获得图4的频带图（除了办事中心高频被保留，其余高频全数过滤器），阿谁频域操做体例同构于在图1阿谁低空讯号上，用相联系关系的传递函数函数展开传递函数操做体例。振幅过滤器获得图4后，再接纳傅立叶逆转换回到内部空间域图3，他们发现图3中高频着色细节都没有了，剩下的高频扁平的内容。不异振幅相联系关系着不异强弱的热量。
从下面的例子他们发现，内部空间域的讯号即不断相片，能复原成频域不异振幅的讯号（不异振幅的波）共振，他们在频域对那类振幅的讯号展开处置，会反响到低空上相相联系关系的原初讯号上，同构于间接在内部空间域展开传递函数操做体例。（一不小心，传递函数定理都讲完了）
有影像布景的教师必定晓得，在CNN火起来之前都是接纳一些专门的低通滤波器去传递函数相片获得报酬定义的特点，好比说用 Gabor 低通滤波器获得着色特点。还有更简单的，sobel 算子去传递函数两张相片获得边缘信息，如下右图转位图后再和 sobel 低通滤波器传递函数一下就抽取出右边的图。
因而，传递函数给他们的觉得是，能抽取一类某一的特点讯号，好比说边缘特点、高频着色特点等等。但是 CNN 是良多层的，抽取了一层特点后的 feature map 上再来一次传递函数获得的是什么特点呢？还有 GCN 那类非影像数据，又该若何认知阿谁抽取的特点讯号的？
02
—
如前所述"基"的讯号造备与降解
世界是稀少的。好比说任何两张影像都能用几组一般来说的小影像块共振而成。那里其实是在频域找到几组基（几组一般来说的小影像块）来降解讯号（相片）。
更有趣的是，那组基其实不独一。示企图所示，能是右边如许的几组 DCT（离散余弦转换） 基；也能是用 dictionary learning 进修出来的中间如许的几组基；不异组基矢量的大小纷歧也是能不异的，如右边小影像块的大小纷歧能不异。
下面的那组基是频域的，而他们要讲的 GNN 即非从频域来降解的，不外根本原理都是类似的。下图是频域的两个正弦波讯号，那么相联系关系到频域就能复原成各个不异振幅和波数的正弦波。（若是你用过示波器，阿谁过程就很好认知）
两个频域的讯号，被他们复原成不异振幅（不异热量）的讯号共振，有DC曲流部分、有热量很高的波、有热量很弱的波。
上图展现了两个讯号，别离从频域降解和频域降解的2种情况。此中 和 别离暗示几组基矢量，一般他们单项选择几组单元正交韦尔恩造备讯号。
选定了米洛韦，若是他们想要晓得在某一基（某一振幅）上的讯号大小纷歧，则操纵上图的阐发过程来求的，两个内积即可。
最常用的就是傅立叶那套了，如下图所示，此中 就是基。
有了下面那些常识，就能正式起头阐发 GCN了。。。
03
—
图收集的即非
在介绍图传递函数之前，还得从通俗传递函数讲起，起首介绍一维持续传递函数的定义，f 和 g 的传递函数定义如下，附上几乎每个教师上课都用过的动图：
现实应用中，他们更多的是处置二维离散讯号，二维离散传递函数定义如下：
简单归纳综合传递函数过程就是：扭转、平移、相乘、乞降。能看出传递函数运算是很复杂的，所以有没有法子不去间接求传递函数呢？
那里就要介绍两个前面提过的定理，传递函数定理：函数传递函数的傅立叶转换等于函数傅立叶转换的乘积。可见对函数傅立叶转换后的乘积在展开傅立叶逆转换就能获得原初函数的传递函数。
上式中 F 代表傅立叶转换 F^{-1} 暗示傅立叶逆转换。
回到图收集上，频域的传递函数不只计算难，连定义两个传递函数核都难。因而也是依靠传递函数定理，在频域来做些骚操做体例，下图所示：
如今他们目的就是定义好图傅立叶转换和逆转换即可！
类比通俗的傅立叶转换就是求讯号在 e^{-jwt} 上的投影，那么图傅立叶转换也是求讯号 x 在几组正交基 上的投影。 图傅立叶转换如下：
上表来自知乎网友文章截图
那么上图中的那组基 u 从哪里来呢？阐发获得的特点值 \lambda 又是什么意思呢?
关于\lambda ，特点值/特点矢量听名字就晓得很有用是不是，都叫特点了，必定是能代表讯号的属性的。段小宇线性代数的都很熟悉，就不烦琐了。间接来说那组傅立叶基 u 怎么求。
先约定下关于图收集的符号暗示。关于两个 graph 收集 G，那么能用节点 V （N 个），和边 E 来暗示。关于肆意两个收集，能获得2个矩阵A和D。邻接矩阵 A 的定义是暗示若是2个节点有边联系关系则未1，不然未0. 度矩阵 D 的定义是该节点的度数（对角阵）。
有了 A 和 D，就能计算出收集 G 的拉普拉斯矩阵：L = D-A。
收集的拉普拉斯矩阵 L 是两个对称的半正定矩阵，能复原成 L=U\Lambda U^T 的形式。而且那里的 u 就是他们想要的傅立叶转换的基，\lambda 就是讯号的特点振幅。
到此，他们就能用操纵传递函数定理和图傅立叶转换获得图传递函数的解法了：
图讯号 f 和 g 的图传递函数，类比通俗讯号f 和 g 的通俗传递函数，形式是一样的。
参考第一末节的相片低通滤波，那么关于两个图讯号 x，也是先做傅立叶转换到频域 U^Tx ，然后在频域展开低通滤波即和同样傅立叶转换后的低通滤波器 g_{\theta}=U^Ty 展开乘积获得 g_{\theta}U^Tx ；最初再傅立叶逆转换归去即获得频域得成果 y= Ug_{\theta}U^Tx 。
画成矩阵的形式就是下面如许：
为了愈加简单一点，他们进一步转换一下，把前面介绍的拉普拉斯矩阵 L 再引入回来：
所以图传递函数计算，相当于就是拿拉普拉斯矩阵 L 的函数来对讯号展开两个处置！阿谁函数的参数也就是他们的传递函数核参数，模子需要进修的参数。阿谁处置会做些啥呢，和低通低通滤波器又有什么关系呢？
04
—
图传递函数有什么问题
复用两个台大课程上详细的例子来申明下拉普拉斯矩阵 L 的函数在图 graph 上操做体例的过程。
下面定义了两个简单的图收集讯号 f，共有4个节点，每个节点就一维数值。那么阿谁graph f 的度矩阵 D和邻接矩阵A，以及拉普拉斯矩阵 L 和相联系关系的降解成果如上所示（上图矩阵 A 写错了）。
用最简单的拉普拉斯 L 的函数 g_{\theta}(L)=L 来感化到阿谁图 f 上，获得成果 Lf 是如下：
认真看下面的计算过程，当计算 Lf 的第两个值 a 时， a=(4-2) + (4-4); 能从参与计算的数值（黄色框、红色框、军绿色框中数值）看出，第一项(4-2) 中的4代表 v0节点的讯号大小纷歧4，此中的2代表 v1的讯号大小纷歧；第二项（4-4）中的第两个4代表 v0节点讯号大小纷歧，第二个4代表 v2节点讯号大小纷歧。之所以是有2项是因为 v0节点的度=2，即有2个邻人（v1和 v2）。
有没有总结出规律！当用 L 感化到图 f 上时，某种水平上能看做是计算节点讯号与本身邻边节点讯号的差值。阿谁差值的大小纷歧变革水平是不是就类似于第一末节说的相片像素的差距，差距变革越快就是高频，反之则代表高频。
再思虑两个问题，下面计算过程发现，当他们计算第两个节点 v0时，只用到了邻人 v1和 v2的值，没有用到 v3，因为 v0和 v3间接没有边。下图矩阵简单的看出当 g_{\theta}(L)=L 时，阿谁函数感化的 f 上，求 y第一行 的2时，因为 L[0][3]=0,代表和 v3节点没有邻边，所以用不到 v3节点的信息。
如许必定是有信息丧失的，相当于他们每次更新两个节点时，只用了1阶邻人节点的信息。若是他们的函数再复杂点呢，好比说取2次方 g_{\theta}(L)=L^2 。
此时能看出L 的函数包罗其2次方项后，矩阵中都长短0项，则更新节点 v0时，v3节点的信息也会被用到。因为 v3和 v0固然不是间接邻人，但是他们存在着2阶邻边，所以当 g_{\theta}(L)=L^2 时，更新某两个节点时会用到其所有2阶邻人的信息。
讲到那里就引出当前 graph 传递函数的几个问题。
1）传递函数函数 g_{\theta} 中包罗 L 的M次方，更新节点时就会用到它的 M 阶邻人。好比说 g_{\theta}=cos(\theta) 时，此中就包罗了 N 次方，那么更新任何两个节点时，都需要用到所有节点信息，阿谁显然是不合理也不现实的，N 很大时没法算了，那种性量称为非localize，Nonlocal 的。比照影像传递函数，每个值就只和传递函数核大小纷歧内的像素有关。所以graph 传递函数如许不具备 localize 特征。
2）前面提到进修图传递函数的参数就是 g_{\theta} ，阿谁参数个数是 N，即和图的节点个数有关，每增加两个节点，阿谁参数就要变革。
3）需要对 L 展开矩阵降解，大矩阵的矩阵降解计算量长短常庞大的。
05
—
ChebNet 与 GCN
讨论下面几个问题，就必需要提 ChebNet 阿谁里程碑工做了。
ChebNet 简单解释就是用切比雪夫多项式拟合 L 的 K 次多项式做为传递函数函数。示企图公式所示，如许设想后，每个节点更新就最多和 K 阶邻人有关，实现了 localize。 同时参数个数也定死是 K 个，不会跟着 graph 的变革而变革。拟合的过程如下：
最末获得的传递函数公式就是上式y的计算过程，如许处置后，计算量就下来了，从 O(N*N) 酿成 O(KE)：
根本原理有点类似下面的函数求问题(2)时用转换后的多项式降解来求解会简化计算。（阿谁转换我也没深切推导过）
用了 ChebNet 后，上一末节的3个问题就都处理了。接纳普遍的 GCN 就是 ChebNet K= 1时的一阶近似。
下面推导依赖几个思绪：1）更大的特点值 \lambda_{max} 比2略小，约等于2. 2） 那里的拉普拉斯矩阵 L 能正则化为：
3）参数 \theta 的关系是报酬设定的，不是理论。renormalization trick 也是做者那么定义的两个计算办法。此中
， A相当于加了一次本身。
同时能看到下面的特点值范畴是[-1,1],那么在振幅展开低通滤波时，即振幅响应函数的范畴也是在那范畴内，属于高频段，所以 GCN 能看做是两个低通低通滤波器。
颠末上图转换后获得了最末收集下一层的输出 H^{(l+1)} 的计算办法。若是觉得阿谁式子欠好认知，能换成下面的形式：
就是讲输入特点 x 颠末一次变革 W 后，再将所有邻人（包罗本身）的那些值乞降相加，再求均值，最初颠末一次"激活"函数 f，获得输出。阿谁式子认知起来就很传统了。
GCN 的效果若何，存在什么问题？关于阿谁，网上有良多材料，我就不介绍了，简单说便是颠末多层后，有 over-smoothing 问题。效果的话，一般般吧，至少在良多相片使命上，效果十分差。在现实工做中，很少会间接用那么单纯的 GCN 的，应用较广的仍是graphsage、gat 那些。
