图计算

发表于 | | 本文总阅读量

综述和必读论文

https://zhuanlan.zhihu.com/p/89503068
https://mp.weixin.qq.com/s/3CYkXj2dnehyJSPLBTVSDg

框架实现

  • Deep Graph Library (DGL)
  • PyTorch Geometric
  • TensorFlow primitives for “gather” and “math.unsorted_segment” ops

应用

生成每个节点的向量表达式

得到每个节点的嵌入向量表达
这个应用和Word2Vec（https://zhuanlan.zhihu.com/p/27234078）很像，每个单词的低维稠密嵌入向量

算法

DeepWalk

这还是图嵌入算法，主要用于生成每个节点的低维稠密向量表达，提供给后续算法去使用

https://zhuanlan.zhihu.com/p/56380812
以当前节点为起始节点，随机游走(随机选择一个邻近节点)，直到选择到的节点数量满足条件，然后利用skip-gram进行训练(和Word2Vec)相似，得到节点的低维稠密向量表达

官方实现：

https://sites.google.com/site/bryanperozzi/projects/deepwalk
https://github.com/phanein/deepwalk

举一个例子：

有512个节点的图，节点之间具有一定的连接关系

  1. 对每个节点编号，(然后就可以对每个节点进行one-hot编码, 如果使用gensim的Word2Vec函数，不需要进行显示的one-hot编码)
  2. 生成一个字典，字典的key为每个节点的编号，value为一个list，这个list里面的值就是和当前节点相连的节点的编号
  3. 确定每个节点需要随机游走的次数，比如这里我们设置10，这样一共需要进行512*10=5120次随机游走
  4. 确定随机游走的深度，比如是40，所以每一次随机游走都会生成一个长度为40的list，表示这次随机游走经过的节点的编号。这样会生成一个5120*40的矩阵，作为输入矩阵
  5. 调用gensim的Word2vec的API，输入这个512040的矩阵，设置特征嵌入的矩阵维度。比如为1024. 最后的权重矩阵是一个512 \1024的，每一行就对应了一个节点的特征向量

tips:

  • 在第四步随机游走的过程中，存在可能性回到原始节点重新游走
  • 第五步调用了gensim的Word2vec API，如果矩阵过大，无法一次性放在内存中，需要写入硬盘分块载入处理，参考官方代码的实现
  • 上面提到的=5120次随机游走，每一次都是独立的，所以可以多线程并行来做

GCN(Graph Convolution Network)

利用嵌入后的向量进行计算的后续算法，关键的需要解决的问题是如何去设计卷积核

资料

图卷积步骤

  1. 首先计算图的度矩阵D，和邻接矩阵A，从而可以计算得到图的Laplace矩阵
  2. 对Laplace矩阵进行矩阵分解，得到N个特征向量和N个特征值 (N为图的顶点的个数)
  3. 对图进行离散傅里叶变换，平时说的傅里叶变换是从时域向频域的转换，这里说的是从顶点的编号组成的域 向 图特征值组成的域的变换
  4. 将第三步说的对N个特征值分别进行的离散傅里叶变换，写成矩阵的形式(N个离散傅里叶变换拼在一起)
  5. 同理，可以推导傅里叶逆变换，得到从特征值到顶点编号的变换矩阵
  6. 定理：两个函数的卷积的傅里叶变换，等于，两个函数的傅里叶变换的乘积
    所以两个函数的卷积，等于，两个函数的傅里叶变换的乘积的逆变换

图卷积神经网络的计算步骤

参考这个实现的源代码，有很多变种的实现，可以看论文综述的文章
Numpy实现：https://mp.weixin.qq.com/s/sg9O761F0KHAmCPOfMW_kQ
Pytorch-Geometric实现：https://pytorch-geometric.readthedocs.io/en/latest/notes/installation.html

GraphSAGE

背景

GCN的问题: GCN是直推式(transductive)训练，基于当前的图信息去做训练，范化性不好，无法解决训练过程出现新节点的问题。所以每次出现新的节点，都需要对模型进行重新训练。每一个隐藏层的权重矩阵是对所有节点计算的，所以每个节点对应的隐藏层的权重矩阵的值是不一样。
GraphSage 采用了归纳式(inductive)训练, 学习生成节点特征向量的方法，而不是学习最终生成的特征向量，原始论文(Inductive Representation Learning on Large Graphs)。每一个节点都对应了同样的隐藏层权重矩阵的值。GraphSage通过训练确认了聚类函数参数和采样函数参数，这样当新的节点出现的时候，只需要利用新的图+之前训练得到的函数做前向传播，得到所有节点的嵌入信息，而不需要重新训练，大大节省了计算量。

算法细节

GraphSage框架中包含两个很重要的操作：Sample采样和Aggregate聚合

  • 聚类：算法迭代的每一层都会进行一次聚合，把上一层学习学习到的各个节点的特征进行一次聚合生成新的一层的各个节点的特征
  • 采样：当前层的节点进行聚合的时候，需要用到上一层的哪些节点？这里原始算法就只用直接相接的节点输入到聚合函数，这里可以进行采样操作，只使用一部分邻接节点，降低计算的复杂度。

GraphSage关键问题：

  • 每一层(一共K层，原始论文说2层的效果就很好了)用什么聚合函数？ 最后的训练结果包含了学习到的聚合函数的各个参数值
  • 聚合用到上一层节点的哪些邻居节点
  • 利用mini-batch进行训练或者前向推理，第一步需要把每一层用于计算的节点都找出来：确定要计算嵌入向量的一个batch的节点(这个是最后一层)，一层一层往前去，把为了聚类计算最后一层节点而在当前层要用到的节点都找出来存下来。第二步就是从第一层开始向最后一层去采样(这里是和非mini-batch的概念里面的采样降低计算的复杂度)，聚合，得到这个mini-batch的节点的嵌入向量。
  • 训练时的ground-truth如何确认？有无监督学习和监督学习的方法：无监督学习的方法认为相邻的节点应该有相似的嵌入向量，有监督的学习在GraphSage后面接一个分类神经网络直接用分类的标签和预测进行学习。

应用

GraphSage训练得到可以生成节点的特征向量算法(主要是泛化，对新节点也可以生成特征向量)，提供给下游任务(比如全连接去预测节点的分类)
每个新节点，只要和已经训练好的老节点聚类，就可以生成这个心节点的特征向量

参考大佬的实现

PinSage

PinSage 是第一个GCN在工业推荐系统的落地，原始论文(Graph Convolutional Neural Networks for Web-Scale Recommender Systems)

评估指标

使用Micro-F1 以及 Macro-F1作为指标去评估

https://zhuanlan.zhihu.com/p/64315175
其中：

  • 精度presicion：预测为正的样本里面，真实为正的比例
  • 召回率recall：真实为正的样本里面，有多少个被预测为正找出来了
    https://www.zhihu.com/question/19645541

多元分类器，可以把自己这个类看成正类，其它类都是负类

例子

Zachary 空手道俱乐部