SIGIR18 《BiNE:Bipartite Network Embedding》 Reading Notes
论文地址：BiNE Introduction Bipartite Network(二分网络):如下图所示： 二分网络将节点分为两种类型，其中 边存在于两种类型之间，例如users-items组成的推荐网络，相同类型节点间不会产生边。传统的Network Embedding将bipartite network视为同质网络（homogeneous network)， 也就是仅考虑直接联系的边。这样就存在一个问题，即在同一个类型中的节点，虽然没有直接的连接，但是也可能有间接的关系。比如两个用户同时连接到同一个商品，则这两个用户可能有有相同的购买偏好。 另一个问题， 如上两图所示， 图一可以看出，节点被访问的词数和考虑到的节点数呈现斜率为-1.582的幂律分布，但是基于随机游走的生成器相对于真实分布有所偏差， 文中分析原因在于基于随机游走的模型DeepWalk为每个节点生成相同长度的节点序列（walk_length）并且每个节点所需要的随机游走次数（walk per vertex)也是完全相同的，这样无法反应网络的特征以及异构性。 另外，对于Heterogeneous Network Embedding方法metapath2vec++, 此方法是次优的因为它将直接连接的节点与间接有关系的节点视为等价。 针对以上问题，BiNE为直接连接和间接关系分别设计了专用的目标函数，并且联合优化。 并且，所及游走的长度由该节点的重要程度决定，节点的重要程度通过HITS来衡量。 Model 如figure中的二分网络， 可以这样定义：$G=(U,V,E)$,和一个$|U| \times |V|$的$W=[w_{ij}]$为权重矩阵。输出d维embedding向量$U=[\overrightarrow{u_i}]$, $V=[\overrightarrow{v_i}]$，结构如下图所示： （取自作者的讲解ppt) Explicit Relations 同LINE一样， 基于直接连接的目标函数表示为： $$\mathrm{minimize} \quad O_1=-\sum_{e_{ij} \in E}w_{ij}\log \hat{P}(i,j)$$ Implicit Relations 构造随机游走序列 这是本文的创新点，分别为$U$和$U$构建语料库，即随机游走序列$D^U$和$D^V$。 首先给出两个同type节点相似度的定义： $$w^U_{ij}=\sum_{k \in V}w_{ik}w_{jk}$$ $$w^V_{ij}=\sum_{k \in U}w_{ki}w_{kj}$$ 其中$i$和$j$是为$U$或$V$中的同类节点，也就是说两个同类节点如果有共同目标顶点，那么他们的2介相似度不为0。 则$U$中的二阶权重矩阵$|U|\times|U|$维矩阵$W^U=[w^U_{ij}]$。$V$中同理。 其中$l=\max(H(v_i)\times \max T,\min T)$, $H(v_i)$为节点$v_i$的中心性，中心性由HITS衡量。$l$为节点$v$的random walk次数（the number of random walks）,有这个节点的重要程度（centrality/importance）决定。 $$D_{v_i}=\mathrm{BiasedRandomWalk}(W^R,v_i,p)$$ 表示其中一次随机游走的节点集合$p$表示停止概率。 通过上面的推导，可以对分别对$U$,$V$中的节点构早随机游走序列，以$U$为例，若$S\in D^U$表示 那么$S$就是$U$中的一个随机游走序列。 ...