cs224w-6-GNN1
我们已经学会了一种 的根据节点关系的 Embedding ,但是它的缺点也很显然:
节点之间不共享参数
每个节点嵌入不同
只能从样本中学习,不能处理其他的情况
有些节点自身的特性无法被利用
于是提出了 graph neural networks ,这样一个节点的嵌入 基于图的多层非线性转换(multiple layers of non-linear transformations based on graph structure)
Basics of deep learning
优化参数
处理一个监督式学习的时候,我们需要优化这个问题,我们要最小化这个公式
其中 为我们要优化的参数, 为目标函数(损失函数)
损失函数有几种
L2:
CE(Cross Entropy):
Softmax :
梯度向量
Direction and rate of fastest increase
= \nabla
Gradient is the directional derivative in the direction of largest increase.
梯度下降 Gradient Descent
迭代算法:不用解释,
训练:进行一次迭代(梯度下降)
LR:Learing Rate
梯度下降的缺点:数据量太大,太慢了。
随机梯度算法 Stochastic gradient descent (SGD)
把每次的 从全部样例变成部分样例
几个定义:
Batch size (样本集?)
Iteration 迭代(一步 SGD)
Epoch:训练次数
SGD是GD的无偏估计,但是无法保证收敛速度以及事实上需要优化lr,一般来说,它的优化器有,Adam, Adagrad, Adadelta, RMSprop…(我记得某篇博客说的很详细)
回到问题,我们需要最小化 loss 函数 由于懒得打 latex 我们直接看图
注意到以下三点:
-
loss 函数提前就定义了
-
每个函数都有它的导数
-
模型可以自动在数据集上评估 下的 loss 函数梯度。
对于神经网络函数 我们已经处理了简单的情况,对于复杂的情况(例如是一个复合函数),我们可以用链式法则。
反向传播
一些函数
Relu : x>0?x:0
sigmoid :
tanh:
softmax :
多层感知器
Multi-layer Perceptron (MLP)
每一层都是线性转换和非线性组合
以上的一些总结
我们的目标是最小化损失函数,并且神经网络函数 可以是一个 linear layer,也可以是 MLP 或者神经网络(比如 RNN , GNN )
图上机器学习
首先是基础概念 分别表示顶点集,邻接矩阵,以及一个 的节点特征矩阵,顶点,邻域。
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 的想法是用到刚才的 矩阵,然后跑神经网络。但是这个方法显然的:
1.参数太多,复杂度太高
2.每种图的神经网络不一样,也就是训练出来没啥意义?
3.对节点插入顺序很敏感
卷积神经网络 convolutional neural network
等下单独写一篇博客补充好了
置换不变 permutation invariant
图的节点顺序没有规定( Graph does not have a canonical order of the nodes!),我们可以用多种方式给节点标号
它们都代表了同一张图。于是我们想让函数满足 , 称 是一个置换不变函数
Graph neural networks consist of multiple permutation equivariant (置换等变)/ invariant (置换不变)functions.
同时,多层感知器并不满足这个,因此
GCN Graph Convolutional Networks
这里就用 ppt 好了
用一个神经网络,聚合节点的邻居信息
灰色的东西就是一个神经网络,首先综合和领域传递的信息,第二步就是把这个信息放在神经网络上跑
weight matrix for transforming hidden vector of self
我们可以把这个嵌入提供给任何损失函数然后利用SGD来训练
Matrix Formulation
许多聚合可以通过(稀疏)矩阵运算有效地执行
训练GNN
相似节点嵌入相似
其中 即为相似, 是解码器 ,节点相似度可以由随机游走,矩阵分解,节点近似度(Node proximity)得到
GNNs subsume CNNs and Transformers
比较 CNN 与 GNN
CNN : 如果是一个 的过滤器,那就需要相邻的八个像素点
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