Deep Walk
DeepWalk: Online Learning of Social Representations（2014，Bryan Perozzi）
算法做什么的？
- 输入：一个 graph
- 输出：每个节点对应的向量
算法优点
- 信息缺失下表现良好
- 数据稀疏的情况下表现良好
- 可用于大规模计算（算法可以并行化）
social representations
我们想让 social representations 有这样的特点
- Adaptability：真实世界中，社交网络是不断演化的
- Community aware：向量距离，应当能代表网络成员的距离
- Low dimensional：向量应当是低纬的
- Continuous：值应当是连续的，如果这样，在此基础上的模型会更 robust。（例如分类模型会有一个稳定的分类平面）
1. Random Walks
在以往，Random walks，已经在对剑算法和社区检验中得到应用。
而且还有其它优点：
- 并行性。可以做多个 random walkers，在不同的线程、进程甚至机器上去跑。(in different threads, processes, or machines)
- 如果网络的少数节点改变，不需要全局重跑。
2. Connection: Power laws
如果度的分布服从 power law (is scale-free)，那么random walk 得到的节点，也服从 power law
然后下面这个图，说明社交网络和自然语言的相似性：The power-law distribution of vertices appearingin short random walks (a) follows a power-law, much like the distribution of words in natural language (b).
3. Language Modeling
算法就是类似 word2vec 的算法
\(\min -\log Pr(\{ v_{i-w},...,v_{i-1},v_{i+1},...,v_{i+w}\}\mid \Phi(v_i))\)
- 其中，$\Phi$是节点到向量的映射
- 顺序不重要。原文给出两个原因：有助于获取“距离近”的概念，增加速度。
文章在下文还写了一些细节，都是word2vec中的概念，不多讲。
- SkipGram
- Hierarchical Softmax
模型的变体
- decay learning rate 不再可能，不过有时候设置小一点儿还是值得的。
- 二叉树可以使 Huffman 树
实验
- BlogCatalog：label是topic categories
- Flickr：这是个用户和照片分享网络，label是用户点了“喜欢”还是“不喜欢”
- YouTube：label是用户喜欢的流派
然后实验结果当然是很好啊（用labeled data验证，仅用20%数据，达到别的模型90%效果）
node2vec
node2vec: Scalable Feature Learning for Networks
本文贡献
- 提出了 node2vec 模型
- 展示了 node2vec 模型，符合以往的网络科学（network science）中建立起来的原则
- 拓展了 node2vec 算法，以及其他基于邻居的算法，来做基于边的预测任务
- 在真实数据上，建立 标签分类 （multi-label classification） 和 连接预测 ( link prediction) 这两种任务，目的是经验性地评估 node2vec （为啥是经验性地评估呢？个人觉得是因为这用两个任务评估算法有一定的说服力，但并不充分，但也没有更好的评估方法了）
前人成果
我们想要寻找一种无须任何人工工程（hand-engineered）的方法
无监督特征抽取，往往需要各种矩阵，例如拉普拉斯矩阵和近邻矩阵（Laplacian and the adjacency matrice），一代数视角看来，这些方法是一些降维技术，例如PCA和IsoMap，他们的缺点来自两个：计算量、统计表现。
- 特征分解就很耗费计算量。所以这些方法很难用到大规模网络上
- 对于各种网络特征，并不鲁棒。例如谱聚类（spectral clustering）的前提假设就很强（也就是很严，不过好多中文也喜欢用强这个词）。
然后论文介绍了NLP中的 word2vec 方法，然后说可以把节点序列类比为文字序列。这一块不多说。
但是，有很多种采样策略，论文的研究展示，没有哪个采样策略显著胜出。
node2vec 就克服了这一缺陷，靠的是设计了一个灵活的、不依赖特定采样策略的目标，以及提供了可以调整的参数。
node2vec框架
摘录一个原文上的公式：
$\max\limits_f \sum\limits_{u\in V} Pr(N_S(u)\mid f(u))$
其中，
- V是节点，图 $G=(V,E)$ 的节点。
- $N_S$ 是一种采样方法，$N_S(u)$ 是用这种采样方法得到的邻居。（后面好几段都在强调这个采样方法是创新点）
NLP 中的 skip-gram，因为语言是线性的，所以直接去截取就行了。但图上的不能这样做。
传统的采样方法
有两个极端：
- Breadth-first Sampling (BFS)
- Depth-first Sampling (DFS)
这个不多说，看下面这个图
通常说，图上的点的预测问题，往往是两种相似性的折中：同质性和结构等价性。
（原文：prediction tasks on nodes in networks often shuttle between two kinds of similarities: homophily and structural equivalence）
- homophily:如果两个节点连接紧密，那么就应当归为一类。例如图中的s1和u就在homophily概念上算同一社区。
- structural equivalence：有相似的结构上的角色（e similar structural roles in networks），例如u和s6在结构上就很相似。现实中，两个节点可以相距很远，但有相同的结构。
一般来说，
- BFS取样更多的提取 structural equivalence 特征。直观理解：structural equivalence 更加依赖相邻的邻居，BFS会更多提取相邻邻居的信息。再者，BFS采样会把相邻邻居采样后的数量增多。
- DFS采样更多地提取邻居的更宏观的视角，更接近 homophily
node2vec模型
random walk
以概率随机游走，deep walk 那篇论文笔记里也写了，不多说。
$P(v\to x)=\dfrac{\pi_{v\to x}}{\sum ?}$
其中
- $\pi$用来控制转移概率，最简单的模型可以取权重
- $\sum ?$是为了让概率总和归一化
search bias
这是本论文的一个特点，
看上面的图，假设已经从t游走到v，那么：
- v到t是回退
- v到x1是BFS
- v到x2，v到x3是DFS
与v相连的节点，都按照下面的原则赋值
- 对于回退，赋值为1/p
- 对于BFS，赋值1
- 对于DFS，赋值1/q
所以这就使用超参数p, q控制了BFS和DFS
实验
case study
结果与预期一致：
- 上面那个是 p=1, q=0.5 的结果，更多地提取了 homophily 特征
- 下面那个是 p=1, q=2 的结果，更多地提取了 structural equivalence 特征
experiment
模型应用于 multi-label classification
- BlogCatalog：label是blogger 的兴趣
- Protein-Protein Interactions (PPI)，蛋白质之间的相互作用，也是一个 graph：label 是特征基因集（我也不懂）
- Wikipedia：网络是 cooccurrence network of words，label是词性
然后，实验就是用 one-vs-rest logistic regreesion ，计算其 F1-score，实验效果当然是挺好。
模型稳定性
然后，文章又做了稳定性实验。
- 随机去除某些边。
- 随机增加一些边
发现模型表现下降，但不很剧烈（下面的右边两个图）
数据规模
实验并记录了数据规模和计算耗时，线性关系。
而且采样时间花费占比很大。
Link prediction
为了做这件事：
- 随机去除50%的边，并且保证剩下的图是联通的
- 负例：随机选取不相邻的节点对
Alibaba Embedding
论文名：《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba(kdd 2018)》
模型是做什么的？
模型输入是用户点击流+物品属性
模型输出是每个item对应的低维向量
abstract&introduction
Taobao是国内最大的C2C平台，推荐系统面临3个问题:
- scalability
- sparsity
- cold start
本论文解决这个问题，基于 graph embedding 方法。
two-stage recommending framework
2 stage 分别是
- matching ：生成candidate
- ranking ：用DNN做个排序
本文专注 matching 问题，核心问题是基于用户行为计算出物品的两两相似度（ pairwise similarities between all items based on users’ behaviors）
以前的方法是 CF 方法（collaborative filtering），但CF的缺点是只考虑物品在用户行为中同时出现这种情况。CF based methods only consider the co-occurrence of items in users’ behavior history
本文的方法规避了这种不足。
但仍然存在 冷启动 的问题，为了解决这个问题，使用 side information 去增强 embedding 过程。
例如，同一品牌、品类的商品，应该更近一点。
但是，Taobao 的 side information 有几百种，而且直觉能想到，不同的 side information 权重肯定不同
Alibaba graph-embedding
构造图的策略
CF 策略只考虑了 co-occurrence，没考虑 sequential information
- 将每个用户浏览序列sequence，做session分隔，1个sequence->n个sessions，每个session 构成一个sequence
- 将所有sequence构成有向有权图，
- 权重是次数之和
- 该步骤需要过滤掉：
- 少于1秒的点击：可能不是用户有意点的
- 点击量太多，或购买量太多的用户，可能是 spam user
- 同样的ID，可能实际商品变了，这也要移除。
DeepWalk
在 graph 上做随机游走。
Graph Embedding with Side Information
为了解决 “cold-start” 问题
side information 指的是品类、店铺、价格等。
例如，同一个店铺的两个羊毛衫，应当较近。Nikon lens和Canon Camera应该很近（品类和品牌接近）
模型做法是把 side information 作为特征，然后求均值（GES模型）
现实中，特征的权重肯定是不一样的。例如，买iPhone的人，更可能买mac，这里品牌权重大。买衣服的，可能买同一家店铺的另一个品牌的衣服，为了优惠，这里店铺特征权重大。所以引入EGES模型。
这个模型给每个item的每个side information 特征，加一个权重。
- 权重值形如 $e^x$，而不是x，这是为了保证权重为正）
- 引入item对field weights: 建立一个MxN的大权重矩阵，学习每个item在各个标签field上的权重
- 新item的表示: item将由其本身的id特征、其他标签特征、特征权重共同表达，如果新item没有id特征，则只用标签特征做加权平均模拟，加到向量模型
算法流程
实验
离线
在亚马逊和阿里的数据上进行了实验。
- 随机选择1/3的边，作为test set，并且移除，剩下的作为训练集
- test set 中，相同数量的 node paris（不相互连接的），作为test set 的负例。
Taobao 数据，按经验选了12个比较重要的 side information
在线AB test
使用CTR指标
模型部署
离线+在线的形式，不多写了。
Airbnb word2vec
另有一片 airbnb 的文章，大体类似，细节不同
- reference《Real-time Personalization using Embeddings for Search Ranking at Airbnb(kdd 2018)》
- 提出了自己的冷启动策略
- 通过修改采样模式来优化word2vec的策略
采样策略
global context：
- 如果用户点击了 like/share，那么这个session内，这个条目与每个浏览都形成点击对（窗口无限大）
-
另一个做法（美图秀秀）做了借鉴。他们有dislike这个行为，那么条目作为负例。
- 用session分割点击序列：将用户点击序列过滤再分段成n个sessions，一个session指的是相邻item时间间隔≤30mins的”有效”行为序列
- 局部负例采样：提出要额外从同属一个cluster的其他item里抽负样本
- 付费行为强化：点击序列中若有付费行为，则将这个 item 强制纳入该序列每个item的上下文窗口
冷启动策略
- airbnb并没有做end2end的学习属性的embedding，而是直接把new item按主要属性检索到最相似的top3个已知的item，取3个item向量的平均值初始化new item embedding
