论文传送门

作者

华东师范大学：

• 高明
• 周傲英
• Leihui Chen
  中国科学技术大学：
• 何向南

摘要

传统的学习图数据的节点表示的方法大都聚焦于一般的同构网络，忽略了二部图的特殊性质。因此这些方法对于二部图嵌入来说可能是次优的。
本文提出了BiNE（Bipartite Network Embedding）来学习二部图的顶点表示。通过有目的地采用“biased random walk”，生成可以较好保持长尾分布的顶点序列。接着提出了一个优化框架，在学习过程中既考虑了显式关系（observed links），也考虑了隐式关系（transitive links）。本文在真实数据集上完成了多种任务，包括边预测、推荐和可视化。定量的结果和定性的分析都验证了BiNE的有效性和合理性。

引言

二部图是一直常见的数据结构，被广泛应用于各种场景，如推荐系统、搜索引擎、问答系统等。
常见的图嵌入的方法 DeepWalk 通常分为两步：

1. 随机游走得到顶点序列
2. 使用词嵌入方法（如word2vec）进行计算

传统的嵌入方法在二部图上是次优的，原因有以下两点：

1. 未考虑节点的类型信息，虽然边只存在于不同类型的点之间，但是同类型的点存在着隐含的关系（如用户-物品中，用户有相同的偏好）。随机游走能在一定程度上捕获高层次的隐含信息，但我们提出了一个更加有效和显式的方法来编码这种隐式的关系。
2. 随机游走生成的 corpus 不能很好的保持二部图的特征。二部图的分布通常遵循幂律，但是deepwalk 等的随机游走的generator的设计存在不足，难以反映二部图的这种分布情况。

BiNE 有两个优点：

• 提出了一个联合优化框架，既考虑了显式的关系也考虑了隐式的关系。
• 为了尽可能多地保持二部图的属性，提出了一个有偏的自适应的随机游走生成器。

相关工作

图表示学习可以分为两类：

• 基于矩阵分解的
• 基于神经网络的

BINE

对显式的边建模

最小化 KL 散度

对隐式的边建模

对于同一类的点，连接它们的路径数量和长度表征了它们之间的关系。
但是计算路径数量是指数级的复杂度。
为此，我们考虑在两个包含相同类型的节点的二阶邻近关系的同质网络上进行随机游走。
定义 2nd-order proximity:

随机游走的步数与节点的 centrality 正相关。
设置停止随机游走的概率。
遵循了“rich gets richer”的准则。

centrality 可以用很多标准来衡量，比如 degree centrality，PageRank、HITS 等等。本文是用来 HITS。

接着对两个 corpora 采用 Skip-gram 模型。

优化目标：

由于这个优化是非平凡的，所以本文采用了 negative sampling。
首先采用了 locality sensitive hashing（LSH），然后随机选择负样本。

联合优化

采用了随机梯度下降（SGA）来优化模型。

由于优化目标是非凸的，所以初始化很重要。

实验

边预测任务数据集：

• 维基百科数据：http://konect.uni-koblenz.de/networks/wikipedia_link_en
• QQlive 数据

推荐任务数据集：

• DBLP
• MovieLens
• VisualizeUs

边预测评价指标：

• AUC-ROC
• AUC-PR

推荐任务评价指标：

• F1
• Normalized Discounted Cumulative Gain
• Mean Average Precision
• Mean Reciprocal Rank

案例分析时采用 DBLP 的一个子集，对 Embedding 进行 TSNE 降维，同时与不对隐式关系建模的 BiNE 的效果进行了比较，其他参考的方法有：

• DeepWalk
• Node2Vec
• LINE
• Metapath2vec++

实验验证了 BiNE 的有效性。