大规模图数据管理与分析 课件 09-图表示学习与图嵌入

大规模图数据管理与分析图表示学习与嵌入第九章2本章概览3图表示学习概述基于矩阵分解的图嵌入方法基于随机游走的图嵌入方法图表示学习概述Part14图表示学习基本概念5

图上节点表示示意图传统方法处理图数据基本流程图表示学习基本概念6举例著名的空手道网络中的节点嵌入表示，源自DeepWalk属于同一社区的节点表示非常接近二维空间被分成了4个近似线性可分的区域，每个区域内的节点属于不同的社区。节点：会员边：朋友关系图表示学习基本概念7

输入示例图表示学习的输入示例：（左）邻接矩阵；（中）特征；（右）标签图表示学习的编码器-解码器视角8编码器-解码器框架编码器模型：将图中的每个节点映射到低维空间中的向量解码器模型：利用节点的低维嵌入向量，面向具体的图学习任务进行预测图表示学习的编码器-解码器视角9

浅嵌入（shallowembedding）方法10

图表示学习的应用111.节点分类（社交网络案例）设想一个有百万级用户的社交网络中，已知有部分账号是人为操纵的机器人账号。如果对每个账号都进行人工检测和审查，代价过于昂贵。因此，需要一个机器学习的模型，能够在人工标注少量样本的情况下，自动识别出机器人账户。（蛋白质网络上蛋白质的功能作用、引文网络上的论文领域预测）节点分类任务示意图形式化过程（半监督学习任务）

图表示学习的应用122.链接预测/图补全/关系推断（社交网络案例）在一个社交网络当中，我们通过边代表用户之间的朋友关系，对于没有边的两个用户，我们是否可以推断他们之间是否有朋友关系？（社交平台上的推荐系统、知识图谱中的未知关系推断、药物副作用推断）链接预测任务示意图形式化过程（无监督学习任务）

图表示学习的应用133.图分类（化学性质预测）用图来表示一个化学分子，其中每个节点代表一个原子，而原子间的化学键关系用边表示，预测该分子是否有某种性质（例如水溶性）。4.社区发现在节点嵌入的向量空间中使用聚类算法（如K-Means算法），可得到图上的社区划分。5.图重构从原始图信息学习得到节点表示，通过度量节点向量表示间的相似度建立一张新的图，而学习的节点表示需要保证建立的图与原图拓扑结构相近。这样，我们就可以认为节点表示充分涵盖了原图的拓扑结构信息。基于矩阵分解的图嵌入方法Part214基于矩阵分解的图嵌入方法15矩阵分解方法的一般形式优化目标

基于矩阵分解的图嵌入方法16代表性方法的目标函数代表性方法图分解方法GraRep方法HOPE方法模型优化目标IsoMapLLELEGFGraRepHOPE

基于矩阵分解的图嵌入方法17均方误差L2正则项基于矩阵分解的图嵌入方法18图分解方法（GraphFactorization,GF）。当图中节点数量较多，嵌入空间维度较大时，基于矩阵分解的算法很难将整张图存储在单个机器的内存中。利用图分割（GraphPartition）对图进行分布式训练，提高算法对大规模图数据的处理能力。基于矩阵分解的图嵌入方法19

基于矩阵分解的图嵌入方法20

基于矩阵分解的图嵌入方法21

基于矩阵分解的图嵌入方法22

基于矩阵分解的图嵌入方法23

基于矩阵分解的图嵌入方法24

基于矩阵分解的图嵌入方法25

基于随机游走的图嵌入方法Part326基本概念27给定图G:A表示图G的邻接矩阵通常，不考虑节点的特征.

uv

原始图嵌入式空间原始图嵌入空间

如何定义在原始图G上的两个点的相似性怎么定义Encoding函数基于随机游走的图嵌入方法28

基于随机游走的图嵌入方法29随机游走的概念编码器-解码器视角：将两个节点相似定义为它们之间存在边，只能捕捉到节点间的一跳关系基于随机游走（RandomWalk）的方法：提供了相似度度量的新思路。基于随机游走的图嵌入方法30随机游走的过程(1)首先，从图上随机选择一个节点作为起点，随机选择该节点的一个邻居节点并游走到邻居节点上;(2)接下来以邻居节点作为起点，再次随机选择邻居进行游走;(3)重复该过程直到达到预先设定的步数。通过随机游走，我们可以得到若干条节点的访问序列。以节点4为起点，通过5

步随机游走可以得到节点序列“4-5-8-9-8-11”。基于随机游走的图嵌入方法31

基于随机游走的图嵌入方法32

基于随机游走的图嵌入方法33

基于随机游走的图嵌入方法34

学习出节点嵌入式表示，以便在嵌入空间中相近的节点，在原始的图中也是相邻的。

从节点u开始的随机游走碰到节点v的概率。基于随机游走的图嵌入方法35

基于随机游走的图嵌入方法36

基于随机游走的图嵌入方法37

sigmoid示意图基于随机游走的图嵌入方法38

基于随机游走的图嵌入方法39

（softmax函数）所有节点节点的邻域节点集合

基于随机游走的图嵌入方法40DeepWalk算法-负采样优化损失函数，需要对图中的每个节点进行求和；每个节点计算邻居的预测概率时，需要计算目标节点与所有节点的内积和（softmax函数）。

为了降低训练的计算复杂度，采用负采样（NegativeSampling）。基于随机游走的图嵌入方法41

K个随机负样本

基于随机游走的图嵌入方法42DeepWalk算法的优势1

表达性方面：同时包含了节点的局部和高阶邻居信息，节点间相似的度量加多元；2

效率方面：不需要在训练时考虑所有的节点对，只需要考虑在随机游走序列中具有共现关系的节点对，使得训练更加高效。基于随机游走的图嵌入方法43node2vecDeepWalk：从图上的每个节点出发，进行无偏的长度固定的随机游走，游走到图上的某个节点时，对其邻居节点的选择都是等概率的。node2vec

算法：通过有偏的随机游走（Biasedrandomwalks）权衡节点的局部和全局信息。基于随机游走的图嵌入方法44node2vec广度优先搜索（BFS）：深入探索一个特定节点周围的节点：深度优先搜索（DFS）：更广泛地探索整个图的结构。node2vec

算法同时使用了这两种策略来进行随机游走。

基于随机游走的图嵌入方法45

基于随机游走的图嵌入方法46Node2vec的随机游走

基于随机游走的图嵌入方法47

基于随机游走的图嵌入方法48LINE显式随机游走：DeepWalk

和node2vec

算法这类需要先显式进行随机游走，近似随机游走：LINE不显式的在图上进行随机游走，而是利用近邻相似的假设，进行近似随机游走，直接优化1

跳和2

跳邻居的经验概率分布。LINE算法不仅可以适用于无权的无向图，也可以学习有权的有向图和无向图上的节点表达。基于随机游走的图嵌入方法49LINE一阶相似度（first-orderproximity）：用于表示节点的局部网络结构。

由于节点6和节点7间具有一条权重很高的边，因此这两个节点的表达应该更相似。二阶相似度（second-orderproximity）：一阶相似度不能够完全表达全局网络结构，使用二阶相似度作为补充。节点5和节点6也应该学到更加相似的表达，因为这两个节点的邻居非常相似，具有4个共同邻居。基于