我们已经学会了一种 $O(V)$ 的根据节点关系的 Embedding ，但是它的缺点也很显然:

节点之间不共享参数

每个节点嵌入不同

只能从样本中学习，不能处理其他的情况

有些节点自身的特性无法被利用

于是提出了 graph neural networks ，这样一个节点的嵌入 $\text{ENC}(v)$ 基于图的多层非线性转换（multiple layers of non-linear transformations based on graph structure）

Basics of deep learning

优化参数

处理一个监督式学习的时候，我们需要优化这个问题，我们要最小化这个公式

$\min_{\Theta}\limits \mathcal{L}(y,f(x))$ 其中 $\theta$ 为我们要优化的参数， $\mathcal{L}(y,f(x))$ 为目标函数（损失函数）

损失函数有几种

L2: $||y-f(x)||_2$

CE(Cross Entropy): $-\sum_{i=1}^{C}\limits(y_i \log f(x)_i)$

Softmax : $f(x)i=\frac{e^{g(x)_i}}{\sum{j=1}^{C}\limits e^{g(x)_j}}$

梯度向量

Direction and rate of fastest increase

$\nabla$ = \nabla

Gradient is the directional derivative in the direction of largest increase.

梯度下降 Gradient Descent

迭代算法：不用解释，$\Theta \leftarrow \Theta - \eta\nabla_{\Theta}\mathcal{L}$

训练：进行一次迭代（梯度下降）

LR：Learing Rate $\eta$

梯度下降的缺点：数据量太大，太慢了。

随机梯度算法 Stochastic gradient descent (SGD)

把每次的 $x$ 从全部样例变成部分样例

几个定义：

Batch size （样本集？）

Iteration 迭代（一步 SGD）

Epoch:训练次数

SGD是GD的无偏估计，但是无法保证收敛速度以及事实上需要优化lr，一般来说，它的优化器有,Adam, Adagrad, Adadelta, RMSprop…(我记得某篇博客说的很详细)

回到问题，我们需要最小化 loss 函数 $\min_{\Theta}\limits\mathcal{L}(y,f(x))$ 由于懒得打 latex 我们直接看图

注意到以下三点：

loss 函数提前就定义了
每个函数都有它的导数
模型可以自动在数据集上评估 $\Theta$ 下的 loss 函数梯度。

对于神经网络函数 $f(x)$ 我们已经处理了简单的情况，对于复杂的情况（例如是一个复合函数），我们可以用链式法则。

反向传播

一些函数

Relu : x>0?x:0

sigmoid : $\sigma(x)=\frac{1}{1+e^{-x}}$

tanh: $\frac{e^x-e^{-x}}{e^x+e^{-x}}$

softmax ：$\frac{e^{xi}}{\sum{i=1}^{C}\limits e^{x_i}}$

多层感知器

Multi-layer Perceptron (MLP)

每一层都是线性转换和非线性组合

以上的一些总结

我们的目标是最小化损失函数，并且神经网络函数 $f(x)$ 可以是一个 linear layer，也可以是 MLP 或者神经网络(比如 RNN , GNN )

图上机器学习

首先是基础概念 $V,A,X,v,\text{N}(v)$ 分别表示顶点集，邻接矩阵，以及一个$m \times |V|$ 的节点特征矩阵，顶点，邻域。

When there is no node feature in the graph dataset:

Indicator vectors (one-hot encoding of a node)

Vector of constant 1: [1, 1, …, 1]

有一个很 NAIVE 的想法是用到刚才的 $X$ 矩阵，然后跑神经网络。但是这个方法显然的：

1.参数太多，复杂度太高

2.每种图的神经网络不一样，也就是训练出来没啥意义？

3.对节点插入顺序很敏感

卷积神经网络 convolutional neural network

等下单独写一篇博客补充好了

置换不变 permutation invariant

参考

图的节点顺序没有规定（ Graph does not have a canonical order of the nodes!），我们可以用多种方式给节点标号

它们都代表了同一张图。于是我们想让函数满足 $f(A_1,X_1)=f(A_2,X_2)$ , 称 $f$ 是一个置换不变函数

Graph neural networks consist of multiple permutation equivariant （置换等变）/ invariant （置换不变）functions.

同时，多层感知器并不满足这个，因此 $f(A_1,X_1) \neq f(A_2,X_2)$

GCN Graph Convolutional Networks

这里就用 ppt 好了

用一个神经网络，聚合节点的邻居信息

灰色的东西就是一个神经网络，首先综合和领域传递的信息，第二步就是把这个信息放在神经网络上跑

$B_k$ weight matrix for transforming hidden vector of self

我们可以把这个嵌入提供给任何损失函数然后利用SGD来训练

Matrix Formulation

许多聚合可以通过（稀疏）矩阵运算有效地执行

训练GNN

相似节点嵌入相似

$\mathcal{L}=\sum{z_u,z_v}\limits \text{CE}(y{u,v},\text{DEC}(z_u,z_v))$

其中 $y_{u,v} =1$ 即为相似， $\text{DEC}$ 是解码器，节点相似度可以由随机游走，矩阵分解，节点近似度（Node proximity）得到

对于监督学习，我们利用类似交叉熵的函数，有

GNNs subsume CNNs and Transformers

比较 CNN 与 GNN

CNN : $hv^{L+1}=\sigma(\sum{u \in \text{N}(v)\cup{v}}\limits W{l}^{u}h{u}^{l}) \forall l \in { 0,…,L-1}$ 如果是一个 $3*3$ 的过滤器，那就需要相邻的八个像素点

CNN can be seen as a special GNN with fixed neighbor size and ordering ：

The size of the filter is pre-defined for a CNN

The advantage of GNN is it processes arbitrary graphs with different degrees for each node

CNN不满足置换等变

GNN VS Transformer

Transformer 是最流行的架构之一，在许多序列建模任务中都取得了出色的性能。

可以把它看成完全图的 GNN