这节课主要是从频域的角度出发介绍GNN，带大家入门GNN。
首先讲解graph filters；
然后通过【graph filter+pointwise nonlinearity】的构造graph perceptron，多个graph perceptron的叠加就是
the most simplest GNN了。
最后，在最基本的GNN的基础上，我们引入filter banks和multiple-input-multiple-output graph filters，得到MIMO GNNs。而MIMO GNNs就是我们常见的GNN了。
Graph Convolutional Filter
Graph Convolutional Filter的输入
从频域的角度出发，Graph Convolutional Filter的输入和输出是Graph Signals。
Graph Convolutional Filter的优化目标
Empirical Risk Minimization通常包含3个组成成分：
而机器学习的目标就是在function class里面找到损失最小的那个function：
那么，对于GNN来说，它的function class是什么呢？就是graph convolutional filters！
注意啦，在课程中graph convolutional filters和graph filters指的都是同一种东西。
给定GSO（Graph Shift Operator）$S$，其感受野为$K$的graph convolutional filters可以统一表示成下方的形式：
在这个function class里面，$S$和$h$都应该是超参数，但是由于往往$S$都是给定的，所以超参数只剩下h了。所以，GNN的优化目标就是：
Graph Convolutional Filter的输出
从频域的角度出发，Graph Neural Networks的输入和输出是Graph Signals。
但是当我们训练集上的$y$不是graph signal的时候，可以在GNN输出上加一层Readout Layer（其Transformation Matrix为$A$），将GNN输出的graph signal变成和$y$相同的维度，具体的流程图如下：
相应的，优化目标变成了：
那么这个$A$如何定义呢？可能我们的第一想法是将其设置为超参数，但是老师说这是不可取的，$A$最好根据实际情况，自己进行定义，例如可以定义为：
其实在使用PyG的Cora数据集时，里面有使用
train_mask和test_mask，它们就可以看做是read out specific nodes的操作~
Graph Neural Networks（GNNs）
Graph Perceptron
Simplest GNN是由很多graph perceptron构成的，一个graph perceptron只是在Graph Convolutional Filter之后添加了一些东西，其结构如下：
这种Pointwise非线性函数通过下面的操作图就能理解它是什么运作的了：
我们常见的Pointwise Nonlinearities有：
那么Why呢？
老师给出的答案：
- Pointwise nonlinearities decrease variability. => They function as demodulators.
- Graph lters have limited expressive power because they can only learn linear maps。所以需要引入nonlinearity。
我没有理解。。。Graph Perceptron的优化目标
正是引入了Pointwise Nonlinearities的概念，所以Graph Perceptron的优化目标和Graph Convolutional Filter有点点不同：
其中：
GNN的结构
Simplest GNN是由很多graph perceptron构成的，对于一个拥有3层graph perceptron的GNN来说，其结构为：
GNN的优化目标
通过上面的结构我们可以总结出GNN的function class为：
那么它的优化目标，就是找到一组最合适的$\mathcal{H}$使得loss最小：
其实想想参数的数量是$K \times L$个。
GNN vs. Graph Filters
| 比较方面 | 结果 |
|---|---|
| 结构 | GNN是在Graph Filter的基础上增加了pointwise nonlinearities和layer compositions； |
| 效果 | GNN表现更加优秀 |
| 迁移性 | 两者都具有迁移性，我们可以将$x$和$S$都看作模型的input，那么就可以在多个图之间共享$\mathcal{H}$了。 |
GNN v.s. CNN
GNNs are proper generalizations of CNNs
GNN vs. FCNN
首先，回顾一下，我们常见的FCNN（Fully Connected Neural Network）的执行流程：
由于GNN可以看作是FCNN的子类，GNN只是对FCNN里面的$\mathcal{H}$增加了限制，因此FCNN的效果一定是不会弱于GNN的：
那为什么我们还要使用GNN呢？
这就回到我们机器学习课上面讲的过拟合和模型泛化性了，GNN在这两个方面表现得更好。
Because it exploits internal symmetries of graph signals codified in the graph shift operator，涉及到了Permutation Equivariance of Graph Neural Network的知识，这里就不多讲了。
Graph Filter Banks
A Graph Filter Bank = A Set of Filters
我们用$h^f$表示第$f$个filter，将$x$分别输入多个filter之后可以得到：
上图的结果就是将我们的feature matrix从$N \times 1$变成了$N \times F$大小，扩充了feature matrix的维度。
Output Energy of a Graph Filter in the GFT Domain
接下来介绍一个关于Graph Filter的output energy的定理：
定理的证明如下：
Multiple Feature GNNs
至此，我们所讲的graph signal都是$N \times 1$大小的，也就是每个结点只有一个特征，但是实际生活中的图上，结点的特征通常是多维度的，那么怎么处理多维特征的情况呢？
前面我们介绍了filter bank，引入它的作用就在于实现处理多维特征。
对于输入的特征矩阵$\mathbf{X} \in \mathbb{R}^{N \times F}$，我们的处理思想就是对每一维的feature都进行filter bank操作。
Multiple-Input-Multiple-Output (MIMO) Graph Filters
假设现在有一个Feature Matrix $\mathbf{X} = [\mathbf{x}^1,…,\mathbf{x}^f,…,\mathbf{x}^F]$，对于其中的每一个$\mathbf{x}^f$都使用一个大小为$G$的filter bank。
下面是对某一个$\mathbf{x}^f$使用一个大小为$G$的filter bank的示例：
下面是所有的$\mathbf{x}^f$使用一个大小为$G$的filter bank的结果：
可以想象，如果不做任何的处理，最终将会产生$F \times G$个特征维度，随着网络越来越深，这样的增长会限制我们的运行速度。因此，在这里，我们采用了上图中相加的方式。其公式表示为：
最后的矩阵计算公式也非常的漂亮，只不过要多思考一下为什么是这样的矩阵计算公式：
Tips：上面的矩阵乘法是从列向量线性组合的角度看待的。
MIMO GNN
跟graph perceptron类比，我们将MIMO Graph Filters后面再加一个pointwise nonlinearity，就组成了MIMO perceptron。
再进行类比，叠加MIMO perceptron就构成了MIMO GNN（也就是我们最常用的GNN）了。
对于拥有三个MIMO perceptron的MIMO GNN，它的执行流程图如下所示：
再次总结一下，GNN每一层的操作如下：
