深度图模型

陈一帅

yschen@bjtu.edu.cn

北京交通大学电子信息工程学院网络智能实验室

北京交通大学《深度图模型》课程，源自斯坦福大学 CS224W，讲解深度图模型的基本原理和算法，一路下来，带大家在动手中，走上算法研发的职业道路。详细课程信息请访问：https://yishuai.github.io/bigalgo/graph.html

目录

1. Shallow 节点表征
2. 标签传播和节点分类
3. GNN
4. 训练技巧
5. KG 知识图表征和推理
6. GNN 推荐
7. 实验

1、Shallow 节点表征

本节介绍Shallow 节点表征，它仅利用节点的拓扑关系，学习节点表征

内容

1. 利用节点拓扑关系定义节点相似（如：相连的两个节点应该相似），以此训练节点表征（如：两个相似节点的表征的Cos相似应该较大）
2. Encoder 是 简单查表，用 nn.Embedding 实现
3. 随机游走
• Negative sampling
• 无偏游走：DeepWalk
• 有偏游走：node2vec，平衡 BFS 和 DFS
4. 图表征方法
• 节点平均
• 超级节点
• 基于Walk

材料

• 斯坦福 CS224W 节点表征，PDF

实验

• 节点表征和链路预测，采用Loss函数：相邻节点表征的 Cos 相似： 腾讯文档

2、标签传播和节点分类

已知少数节点的类别，利用“连接的节点相似”这一点，进行“标签传播”，得到其它节点类别

方法

• 邻居类别概率加权求和
• 训练分类器，利用节点属性和邻居节点标签，进行分类
• 先用节点属性，得到 base 分类
• 计算 邻居节点 标签的 summary，迭代分类
• Correct & Smooth (更正和平滑)：用 ground truth节点的模型误差和标签，进行校正

材料

• 斯坦福 CS224W 标签传播和节点分类，PDF
• Correct & Smooth 论文，ICLR 2021，Combining Label Propagation and Simple Models Out-performs Graph Neural Networks，论文， Github， PyG 实现

3、GNN

Shallow 节点表征模型没有利用节点feature，不能扩展到没见过的节点。GNN模型利用节点特征，表达能力更强

方法

• 输入：节点特征 X
• 方法
• Message Propagation
• Aggregation
• 模型
• GCN：sigmoid(w*h)
• GraphSAGE: sigmoid(w, h, agg(h))
• agg 可以是 mean, pool, LSTM
• l2 normalization
• GAT：多头 attention 机制
• 实用方法: Batch Normalization， Dropout， Skip connection

材料

• 斯坦福 CS224W GNN模型，PDF 1，PDF 2

实验

• 图分析和节点分类，三层 GCNConv，腾讯文档
• 深度图神经元网络，自己实现 GNN layer，包括 GCNConv， Batch Normalization， Dropout， 腾讯文档
• 实现 GraphSAG 和 GAT 图注意力机制，腾讯文档

4、训练技巧

GNN训练起来不容易。本节介绍各种实用技巧

• 加节点特征
• GNN 不能识别一些图特征，所以，手工 加 图特征，如 cycle 数
• 加边
• 两跳连边，改善稀疏
• 加节点
• 改善消息传播
• 邻居采样
• 降低计算量
• 数据 Split
• 根据问题的特点，采用特定的训练集、验证集、测试集的划分方法
• Debug 技巧
• 初始化，激活函数等

材料

• 斯坦福 CS224W 模型训练技巧，PDF
• 常用高级模型库，支持常见GNN模型
• PyG：PyTorch Geometric（网站）
• DGL：Deep Graph Library（网站)，各种模型，如 NGCF（Github）

5、KG 知识图表征和推理

学习 KG，根据 Head 实体 + 关系，预测 Tail 实体

方法

• KG 是一种Heterogeneous 异质 图
• 多种节点
• 多种关系
• entity， relation 都 用 shallow embedding
• 通过 字典学习，降低 关系 W 的参数数目
• 应用：KG 完成
• 根据 head, relation 补上 tail
• 如：根据 “J.K. Rowling”, “genre” 补上 “Science Fiction”)
• 方法
• TransE：head + relation -> tail
• TransR：M * head + relation -> M * tail
• DistMult：head * relation * tail
• ComplEx：复向量空间
• 如果没有很多 对称关系的话，一般用 TransE，然后试试 ComplEx
• 应用：基于 Embedding 的 KG 推理
• Path query
• 如：A导致的症状，和哪些 protein 蛋白质 有关？
• 扩展 TransE，变成 embedding 的向量运算
• head + relation1 + relation2 -> tail
• Conjunctive query 连接查询
• 如：能治疗A，但会导致B的药有哪些？
• 即：要求 “导致 B 的” 和 “治疗A的” 的交集
• Query2Box
• Projection 投影 操作符
• Box intersection 操作符

材料

• 斯坦福 CS224W， KG 表征（PDF），推理（PDF)
• 常用高级模型库，支持常见GNN-KG模型
• Amazon DGL-KG，提供 TransE, TransR, RESCAL, DistMult, ComplEx, RotatE，Github
• Facebook PyTorch-BigGraph，适合10万以上节点的图，不适合小规模图，Github
• Google SMORE，支持 BetaE, Query2box, GQE, RotatE, ComplEx, DistMult 在千万节点图上训练，Github

6、GNN 推荐

用户-Item图的推荐

方法

• NGCF
• Shallow 用户/Item 表征
• 计算 用户 - Item 表征 Cos 相似，进行匹配
• LightGCN
• 节点数很大时，GCN的参数信息量不大，用户/Item 表征 已经非常 expressive 了
• 去掉 非线性，直接 矩阵 Diffusion
• 类似 更正 和 平滑
• PinSAGE：图片，为了适应大数据，可扩展，进行了特别设计
• Curriculum learning：先送容易的样本，再送难的

材料

• 斯坦福 CS224W GNN 推荐，PDF
• LightGCN 推荐 PyTorch 实现，Github

7、实验

1、王一行，《Python基础指南》，Docx, 1.6MB

2、张璇，《Python机器学习快速上手入门指南》，Docx, 237KB，PDF, 342KB，Iris实验代码和数据，Zip，1.5MB