graph-embedding

Word Embedding

Item2vec

Barkan et. al. 在 ICML16 Workshop 提出,区别于 item2item (ALS ItemCF)方法,用 word2vec (负采样 Skip-gram) 学习物品隐式表达。

以用户浏览商品作为句子。假设同句子中的词是无顺序关系的,忽略了浏览顺序的 spartial information。其他情况可能不符合该假设,比如丛书《哈利波特1-5》。

Music 领域分类,用音乐人流派进行聚类, item2vec 方法与 SVD 对比,有效分类:

img

Airbnb Embedding

KDD 18 Real-time Personalization using Embeddings for Search Ranking at Airbnb (Airbnb 2018)

对用户和房源计算 word2vec,embedding everything,提升搜索推荐系统的性能。

Graph Embedding

目标是用低维稠密向量表示图中的点。解决传统方法问题:

  1. 矩阵分解 — 计算量大
  2. 构造人工特征 — 需要领域知识、工作量大

可用于推荐、节点分类、链接预测、可视化等场景。

DeepWalk

构造无向无环图,以特定点作为起点,做随机游走得到点的序列作为句子,用 w2v skip gram 学习。

例如给定 KV 对(用户,APPID),计算 APPID 的 embedding 时,以 APPID 作为节点,两个 APPID 之间共同的用户占比作为权重。

img

img

LINE

MSRA 15,LINE (large-scale Information Network Embedding) 利用图中已存在的边构造目标函数,该目标函数显式描绘了一阶(6 和 7)和二阶(5 和 6)的邻近关系。然后通过优化方法去学习点的表达向量,其本质上是一种关于边的平滑,即很多很可能存在的边实际上不存在,需要模型去学习和预测出来。这点类似于推荐,任何推荐的算法本质上是对于user-item关系矩阵的平滑。

img

对于 用户ID-游戏ID 序列能够较好的建模。

Node2Vec

Standford16,在DeepWalk的基础上更进一步,通过调整随机游走权重的方法使graph embedding的结果在网络的同质性(homophily)和结构性(structural equivalence)中进行权衡。

为了使Graph Embedding的结果能够表达网络的同质性,在随机游走的过程中 BFS 产生结构性,DFS 产生同质性。为了获取二者的特性,通过 p q 参数控制随机游走过程往远处跳、跳回的概率。

从实验结果看,同质性相同的物品很可能是同品类、同属性、或者经常被一同购买的物品,而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的物品。

EGES

KDD18 Enhanced Graph Embedding with Side Information。

为了使“冷启动”的商品获得“合理”的初始Embedding,阿里团队通过引入了更多补充信息 (side info) 来丰富Embedding信息的来源,从而使没有历史行为记录的商品获得Embedding,从 DeepWalk 改进得到 EGES。

Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

SDNE

THU16 本文认为,DeepWalk的缺点是缺乏明确的优化目标,即objective function,而LINE是把网络的局部信息和全局信息分开学习,最后简单地把两个表达向量连接起来,显然不是最优做法,文章利用深度学习去做graph embedding,好处自然是非线性表达能力更强了,然后设计了一个同时描述局部和全局网络信息的目标函数,利用半监督的方式去拟合优化。

SimRank

MIT 02 Jeh & Widom 提出,给定 user-item 二部图 G(V,E)G(V,E),考虑如果用户相似,那么他们关联的物品也相似。其中 V 是节点,E 是边。

定义两个节点的相似度

s(a,b)=CI(a)I(b)i=1I(a)j=1I(b)s(Ii(a),Ii(b))s(a,b)=\frac{C}{|I(a)||I(b)|}\sum_{i=1}^{|I(a)|} \sum_{j=1}^{|I(b)|} s(I_i(a), I_i(b))

如果 a = b 则 s(a,b)=1s(a,b)=1 ;如果 ab,I(a)null,I(b)nulla\ne b,I(a)\ne null,I(b)\ne null 则结果如上式;其他情况 s(a,b)=0s(a,b)=0

其中 I(a)I(a) 表示和 a 相连的二部图另一个子节点的集合。

img

User2vec LSTM

Reference

[0] https://zhuanlan.zhihu.com/p/33732033

[1] DeepWalk: Online Learning of Social Representations

[2] LINE: Large-scale Information Network Embedding

[3] node2vec: Scalable Feature Learning for Networks

[4] Structural Deep Network Embedding

[5] 深度学习中不得不学的Graph Embedding方法 https://zhuanlan.zhihu.com/p/64200072

[7] Item2Vec: Neural Item Embedding for Collaborative Filtering https://arxiv.org/abs/1603.04259

本文有帮助?