[TOC]
Outline
- Introduction
- Roadmap
- Tasks, Dataset, and Benchmark
- Spatial-based GNN
- Graph Signal Processing and Spectral-based GNN
- Graph Generation
- GNN for NLP
Introduction
Graph
图在我们的日常学习生活中都无处不在：
如上图所示，Graph是由Nodes和Edges构成的。在每个不同的图中，每个Node有自己的性质，没有Edge也有自己的性质。
GNN = Graph + Neural Network
Why do we need GNN？
classification
input是graph~
Generation
Generator
output是一个graph~
例子：
Graph Signal Processing and Spectral-based GNN（vertex domain <-> spectral domain）
图信号处理和基于频谱的GNN
如上图，在CNN中，我们学习到一个Filter以便用于在矩阵中做convolution。那么如果我们要在Graph做到这样一种操作应该怎么做呢，怎么学习到这样一个Filter呢？下图中的流程是至关重要的~⭐⭐⭐⭐⭐
我们将Graph中vertex的feature值称作signal，然后对这些signal做Fourier Transform，将它们映射到Fourier domain之中，同理，将Filter也映射到Fourier domain之中，在Fourier domain之中做multiplication就可以实现convolution的效果了。最后再将Fourier domain里面的值inverse回来就好了。
这是一个很好的思想，但是问题是怎么实现呢？
我们先来看看一些信号和系统的知识。
![[~PX}1]HUOM`$J0C_$3Z0CR.png](http://ww1.sinaimg.cn/large/9b63ed6fgy1gkl99jrfmhj20dq0a2wf0.jpg)
一个信号可以看做是N维空间里面的一个vector，在《线性代数》中，我们学过一个vector可以由这个向量空间的basis线性组合得到（如上图所示），这个过程称为合成。
当我们想知道这个线性组合中每个component（即$\hat v_k$）的$a_k$的大小是多少的时候，我们要使用分析。
我们假设当前使用的basis是一组
orthonormal basis。合成和分析是一组互逆的操作，在下面的讲解中会经常用到这个概念。
在time domain里面，我们常用的一组basis就是cos和sin这样一组basis。
现在假设有一个周期性的信号，我们可以把它展开成一个Fourier Series。我们选用的一组basis就是$e^{jk\omega_0t}$，不同的component的大小就是由$a_k$来决定。我们有一些方式可以算出$ a_k$的大小是多少。
harmonic components：谐波分量
一个信号的表示可以体现在两个域上：时域（Time Domain）和频域（Frequency Domain）。
时域的表示就是用时域的basis线性组合。它的basis就是$\delta(t-\tau)$。上图中的积分其实也是求和的意思啦（想想积分的含义。。。）。
除了这组basis，我们还可以是用其他的basis，比如上图中的$e^{j\omega t}$。同一个信号可以用不同的basis来做合成。
![6[H}4ZF03]ng](http://ww1.sinaimg.cn/large/9b63ed6fgy1gkla6clysuj20m7097t9d.jpg)
Fourier transform的作用就在于找出$X(j\omega)$，上图中的式子其实也很简单，就是我们之前在Determination of $a_k$里面讲解的那种方法，只不过这里将和变成了积分~
下面是一些谱域图理论：
第5点中所说的
signal，其实可以简单的理解就是vertex的属性值。例如当vertex是城市时，signal可以表示城市的人口，面积啥的~当然，signal也可以是vector。
Laplacian: /lɑ:’plɑ:siən/ 拉普拉斯
半正定矩阵的概念：
而且eigen value都是大于等于0的
关于为何对称矩阵可以进行上述的矩阵分解，可以查阅之前上线性代数课的笔记——24_special matrix中的对称矩阵小节
我们将$\lambda_l$称为频率（frequency），$u_l$是对应的basis。
根据对称矩阵的分解，eigen vectors之间一定是orthogonal的，我们再让它们orthonormal！
我们将所有的basis作为signal绘制到graph上，得到下图：
至于为什么$u$可以作为signal，我就觉得很奇怪能够。。。
助教解释了为什么我们要将$\lambda_l$称为频率（frequency），$u_l$是对应的basis？
我们先来讲讲其他的东西，比如Discrete time Fourier basis：
上图中一个重要的定理就是：频率越大，相邻两点之间的信号变化量就越大。这个定理可以帮助理解spectral graph theory里面frequency的概念。
接下来就让我们来理解顶点frequency的概念吧~
接下来再看看平方的表示方法：
两个顶点之间的能量差。
也许上面的图中λ为0时很好理解，但是到3和4的时候比较难理解，那么我们举一个极端的例子帮助大家理解一下：
上面讲解的内容都是为我们找到Fourier Transform打基础的，我们先来看看在传统的信号与系统里面是怎么进行Fourier Transform的~（time domain – > frequency domain）
如果要转换回去，我们应该怎么转呢？也就是从spectral domain转换到vertex domain之上~
类比到我们的Spectra Graph上面就是：
接下来，我们来讲解一下filtering
区分L和L^2的不同
什么叫做localize呢？我们再次回顾我们在CNN中学到的那些东西~
receptive field：接受域
ChebNet
第一个Spectral-based GNN就是咱们的ChebNet啦~需要注意的是，我们的每一个模型都应该能够解决我们之前提到的两个图神经网络的问题：
- Learning Complexity
- Not Localize
通过让$g_{\theta}(L)$是$L$的多项式函数，我们就能让$g_{\theta}(L)$是一个$K-localized$的函数。同时，此时要学的参数也是$K$个了，复杂度为$O(K)$。
现在还存在一个问题就是在计算$U(\sum^K_{k=0}\theta_k\Lambda^k)$的时候，时间复杂度（time-complexity）为$O(N^2)$，同时，计算eigenvector本身就是一个计算量特别大的问题。
综合以上种种的问题，ChebNet使用了一个特殊的多项式来解决这个问题。
我们将Chebyshev Polynomial中的$x$替换成$\tilde \Lambda$，这样变形的原因就是为了满足在[-1,1]之间。
至于为什么要使用这个Chebyshev Polynomial代替呢？原因如下：
目的是为了使得$T_k(\tilde \Lambda)$是很好算的。至于为什么要这样代换呢？好像没讲清。
利用切比雪夫正交且递归的性质减少计算量。
就想CNN里面，你可以有不同的channel，
GCN
迷迷糊糊没有看懂
Comparison between the above GNNS——Tasks,Dataset,and Benchmark
benchmark test有下面这5个：
因为要做benchmark，那么dataset一定要大~
下面使用的是SuperPixel MNIST 和 CIFAR10
第二个是ZINC molecule graphs dataset，预测溶解度
第三个，任务是辨认graph里面的pattern，以及聚类。
第四个，旅行商问题
