Graph Embedding算法背景引入

先回顾下图的概念

图(graph)由节点(vertex)和点之间连线(edge)所组成其中点通常被成为“顶点(vertex)”,而点与点之间的连线则被成为“边”(edge)。通常记为,G=(V,E)。常见分为无向图和有向图。

示例如下

无向图

有向图

在互联网场景下数据对象之间更多呈现的是图结构。示例如下

用户行为数据生成的和物品全局关系图

由属性、实体、各类知识组成的知识图谱

在Graph 图中相关概念有BFS和DFS示例如下

广度优先搜索算法Breadth-First-Search BFS利用队列实现。类似“湖面丢进一块石头激起层层涟漪如下

深度优先搜索算法Depth-First-SearchDFS利用递归实现。类似“不撞南墙不回头” 。

接着再回顾下Embedding的概念

数学定义Embedding: 数学上表示一个映射关系 F: X -> Y即一个函数。

深度学习Embedding: 用一个低维度向量表示一个实体或者一个词Word2Vec,或者一个物品Item2Vec亦或者网络关系中的节点Graph Embedding)。

Graph Embedding: 用低维、稠密、实值的向量表示网络中的节点。

那如何生成Graph Embedding 呢?

GraphEmbedding最开始参考的就是 NLP 领域中的Word2vec 模型

再来回忆下Word2Vec模型。比如下段落

苹果是蔷薇科苹果亚科苹果属植物其树为落叶乔木。

苹果营养价值很高富含矿物质和维生素。

苹果是一种低热量的食物每100克产生大约60千卡左右的热量。

苹果中营养成分可溶性大容易被人体吸收。

所有的水果里我最爱吃苹果了。

词的语义由其上下文决定。

“A word is characterized by the company itkeeps” —— J. R. Firth

如果想要识别苹果语义Word2vec中有如下两种方式

Word2vec Skip Gram: 根据中心词预测上下文

Word2vec: Negative Sampling

Word2vec整体架构

Graph Embedding 介绍

由以上回忆可知序列sequence是一种一维的关系而图graph是一种二维的关系那如何类比呢

先看下Graph Embedding图游走示例

以及Graph Embedding示例

所以Word2vec -->图嵌入领域的问题可类比生成

通常图中的节点会受其邻居的影响。如下所示

此外Graph Embedding 能够生成一些“不存在”的序列。如图中

B->E->F;

D->E->C。

Graph Embedding算法之Deep Walk

将 NLP 领域的思想运用到图(网络)嵌入领域。

Deep Walk 游走方式RandomWalk

Deep Walk 整体架构

节点示意图

流程示意图

Deep Walk 应用扩展之EGES算法

Deep Walk 可以生成Item 的 Embedding 向量从而从用户行为中捕捉高阶相似性。然而这只能针对已有的Item 而无法应对新的 Item即无法解决冷启动问题。

对于新加入的物品或者长尾物品无法在行为图中找到。那如何解决呢

可以引入Side Information(补充信息)比如商品的类别、店铺、价格等。

Eg:优衣库同店的两件卫衣同品类可能会非常相似喜欢尼康镜头的人可能也会对佳能相机感兴趣。

所以EGES的架构思想如下

1、通过用户行为序列生成行为关系图。

2、通过”相同属性”“相同类别”等信息建立物品之间的边生成基于内容的知识图谱图。

其中item 和 sideinformation例category, brand)的Embedding 是通过 Word2vec 算法一起训练得到的。

其中的item表示为item Embedding category Embeddingbrand Embedding等 Embedding信息求均值。即

整体架构图如下

下节预告

Graph Embedding算法之Node2vec和相关案例二