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

节点之间不共享参数

每个节点嵌入不同

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

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

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

Basics of deep learning

优化参数

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

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

损失函数有几种

L2: $| | y - f (x) | |_{2}$

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

Softmax : $f (x)_{i} = \frac{e^{g (x)_{i}}}{\sum_{j = 1}^{C} 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

迭代算法：不用解释， $Θ \leftarrow Θ - η \nabla_{Θ} L$

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

LR：Learing Rate $η$

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

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

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

几个定义：

Batch size （样本集？）

Iteration 迭代（一步 SGD）

Epoch:训练次数

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

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

注意到以下三点：

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

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

反向传播

一些函数

Relu : x>0?x:0

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

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

softmax ： $\frac{e^{x_{i}}}{\sum_{i = 1}^{C} e^{x_{i}}}$

多层感知器

Multi-layer Perceptron (MLP)

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

以上的一些总结

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

图上机器学习

首先是基础概念 $V, A, X, v, 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

相似节点嵌入相似

$L = \sum_{z_{u}, z_{v}} CE (y_{u, v}, DEC (z_{u}, z_{v}))$

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

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

GNNs subsume CNNs and Transformers

比较 CNN 与 GNN

CNN : $h_{v}^{L + 1} = σ (\sum_{u \in N (v) \cup v} 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不满足置换等变