LINE

作者: 山的那边是什么_ | 来源:发表于2018-09-09 16:59 被阅读182次

LINE:Large-scale Information Network Embedding

1.背景

LINE 这个模型就是把一个大型网络中的节点根据其关系的疏密程度映射到向量空间中去，使联系紧密的节点被投射到相似的位置中去，而在网络中衡量两个节点联系紧密程度一个重要的指标就是这两个节点之间边的权值。在这篇文章中作者在建模的时候不仅仅只考虑了一阶的关系，即两个点之间直接有较大权值的边相连就认为它们比较相似；同时考虑了二阶关系，即两个点也许不直接相连，但是如果它们的一阶公共节点比较多，那么它们也被认为是比较相似的。基于这两个角度的思考，作者提出了两个模型。

2.原理

2.1 相关定义

$Information Network$ （信息网络）：一个信息网络被定义为 $G =（V，E）$ ，其中 $V$ 是顶点集合，每个代表一个数据对象， $E$ 是顶点之间的边集，代表两个数据对象之间的关系。每个边 $e∈E$ 是一个有序对 $e =（u，v）$ ，并且与权重 $w_{uv}> 0$ 相关联，表示关系的强度。如果 $G$ 是无向的，则有 $（u，v）≡（v，u）$ 和 $w_{uv}≡w_{vu}$ ; 如果 $G$ 是有向的，我们有 $（u，v)!≡（v，u）$ 和 $w_{uv}!≡w_{vu}$ 。
负权重是有可能的，本实验中不考虑

$First-order Proximity$ （一阶相似度）：网络中的一阶相似度是两个顶点之间的自身相似（不考虑其他顶点）。对于由边 $（u，v）$ 连接的每一对顶点，边上的权重 $w_{uv}$ 表示 $u$ 和 $v$ 之间的相似度，如果在 $u$ 和 $v$ 之间没有边连接，则它们的一阶相似度为0。
一阶邻近通常意味着现实世界网络中两个节点的相似性。例如，在社交网络中相互交友的人往往有着相似的兴趣;在万维网上相互链接的页面倾向于谈论类似的话题。

$Second-order Proximity$ （二阶相似度）：网络中一对顶点 $（u，v）$ 之间的二阶相似度是它们邻近网络结构之间的相似性。在数学上，设 $p_u=（w_{u,1}，...，w_{u，| V |}）$ 表示 $u$ 与所有其他顶点的一阶相似度，则 $u$ 和 $v$ 之间的二阶相似度由 $p_u$ 和 $p_v$ 决定。如果没有顶点与 $u$ 和 $v$ 都连接，则 $u$ 和 $v$ 之间的二阶相似度为0。
因为有些边观察不到等原因，一阶相似度不足以保存网络结构。因此提出共享相似邻居的顶点倾向于彼此相似，即二阶相似度。例如，在社交网络中，分享相似朋友的人倾向于有相似的兴趣，从而成为朋友; 在词语共现网络中，总是与同一组词语共同出现的词往往具有相似的含义。

$Large-scale Information Network Embedding$ （大规模网络信息嵌入）：给定一个大的网络 $G =（V，E）$ ，大规模信息网络嵌入问题的目的是将每个顶点 $v∈V$ 表示成一个低维空间 $R^d$ 中的向量，即学习一个函数 $f_G：V→R^d$ ，其中 $d<<| V |$ 。在 $R^d$ 空间中，顶点之间的一阶相似度和二阶相似度都被保留下来。

2.2 LINE with First-order Proximity

对于每个无向边 $（i，j）$ ，定义顶点 $v_i$ 和 $v_j$ 的联合概率:

$u_i$ 是一个低位向量，代表顶点 $v_i$ ;
$p(.,.)$ 是一个 $VxV$ 的向量；
对于每个无向边 $（i，j）$ ，定义顶点 $v_i$ 和 $v_j$ 的经验概率分布：

其中：
起到归一化的作用；
为了保持一阶相似性，一个简单的办法是最小化联合概率分布和经验概率分布：

使用KL散度作为最小化目标，省略常量：

一阶相似度仅适用于无向图，而不适用于有向图。通过一阶相似度可以表示d维空间中的每个顶点。

2.3 LINE with Second-order Proximity

二阶相似度可以用于有向图和无向图，每个顶点需要表示顶点自身和附近顶点的邻居；为每个节点引入两个向量表示 $u_i$ 和 $u^{'}_i$ ： $u_i$ 是 $v_i$ 作为顶点时的向量表示， $u^{'}_i$ 是 $v_i$ 作为附近定点的邻居时的向量表示。
定义 $v_j$ 是 $v_i$ 的邻居的概率为: