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

节点之间不共享参数

每个节点嵌入不同

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

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

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

pSVCcQg.png

pSVCzY6.png

Basics of deep learning

优化参数

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

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

损失函数有几种

L2: yf(x)2||y-f(x)||_2

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

Softmax : f(x)i=eg(x)ij=1Ceg(x)jf(x)_i=\frac{e^{g(x)_i}}{\sum_{j=1}^{C}\limits e^{g(x)_j}}

梯度向量

Direction and rate of fastest increase

\nabla = \nabla

pSe3d7n.png

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

梯度下降 Gradient Descent

迭代算法:不用解释,ΘΘηΘL\Theta \leftarrow \Theta - \eta\nabla_{\Theta}\mathcal{L}

训练:进行一次迭代(梯度下降)

LR:Learing Rate η\eta

梯度下降的缺点:数据量太大,太慢了。

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

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

几个定义:

Batch size (样本集?)

Iteration 迭代(一步 SGD)

Epoch:训练次数

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

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

pSeBWHf.png

注意到以下三点:

  1. loss 函数提前就定义了

  2. 每个函数都有它的导数

  3. 模型可以自动在数据集上评估 Θ\Theta 下的 loss 函数梯度。

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

反向传播

pSeD8Vf.png

pSeDGa8.png

一些函数

Relu : x>0?x:0

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

tanh: exexex+ex\frac{e^x-e^{-x}}{e^x+e^{-x}}

softmax :exii=1Cexi\frac{e^{x_i}}{\sum_{i=1}^{C}\limits e^{x_i}}

多层感知器

Multi-layer Perceptron (MLP)

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

pSeDBq0.png

以上的一些总结

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

图上机器学习

首先是基础概念 V,A,X,v,N(v)V,A,X,v,\text{N}(v) 分别表示顶点集,邻接矩阵,以及一个m×Vm \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 的想法是用到刚才的 XX 矩阵,然后跑神经网络。但是这个方法显然的:

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

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

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

卷积神经网络 convolutional neural network

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

置换不变 permutation invariant

参考

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

pSmnjgJ.png

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

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

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

GCN Graph Convolutional Networks

这里就用 ppt 好了

pSmKmz4.png

pSmKGFK.png

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

pSmKBwt.png

pSmKsFf.png

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

pSmKgSg.png

BkB_k weight matrix for transforming hidden vector of self

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

Matrix Formulation

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

pSmMoDA.png

pSmMq4f.png

训练GNN

相似节点嵌入相似

L=zu,zvCE(yu,v,DEC(zu,zv))\mathcal{L}=\sum_{z_u,z_v}\limits \text{CE}(y_{u,v},\text{DEC}(z_u,z_v))

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

对于监督学习,我们利用类似交叉熵的函数,有
pSmQCEq.png

GNNs subsume CNNs and Transformers

比较 CNN 与 GNN

CNN : hvL+1=σ(uN(v)vWluhul)l{0,...,L1}h_v^{L+1}=\sigma(\sum_{u \in \text{N}(v)\cup{v}}\limits W_{l}^{u}h_{u}^{l}) \forall l \in \{ 0,...,L-1\} 如果是一个 333*3 的过滤器,那就需要相邻的八个像素点

pSmQYKH.png

pSmQNqA.png

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 是最流行的架构之一,在许多序列建模任务中都取得了出色的性能。

pSmlGF0.png

可以把它看成完全图的 GNN