【paper】LINE：Large-scale Information Network Embedding

日期：20200726

chapter1：简介

• 提出目前graph embedding的局限性，无法处理大型复杂网络，无法处理有向图
• 针对以上缺点，涉及有效目标函数，以及函数优化方法，能够处理大型、有向、带权网络，构建node embedding，用于后续任务
• 有效目标函数：提出图中节点的一阶关系、二阶关系，一阶关系描述局部网络结构，但是一阶网络不足以描述图的全部网络结构，作为补充，提出二阶关系【具有相似邻接网络结构的节点越相似】，见图1，节点5和6的邻接网络结构相似，节点5和节点6存在二阶相似关系
• 优化方法：采用随机梯度下降，不适用于大型网络

chapter3：问题定义

• 图网络 $G=(V,E)$，图中节点的边$e=(u,v)，w_{uv}  > 0$，
• 一阶近似关系：描述的是两个连通节点之间的局部成对关系，如果两个节点之间不是直接连通的，则两个节点之间的一阶近似关系为0，只能描述网络中的显性关系，
• 二阶近似关系：认为两个节点之间即使没有连通关系，但是两个节点的邻接网络结构具有一定的相似性，则认为两个节点之间具有二级相似性，即二阶相似性描述两个节点之间网络结构的相似性
• 大规模复杂网络embedding：目的是将节点的向量表示进行降维，降维后的向量能够描述两个节点之间的相似性

chapter4.1：Line方法详解

1.  一阶近似关系描述
   1. 一阶函数定义：$p_1(v_i,v_j) =  \frac{1}{ 1 + exp(  \vec{-u_i^T}  \cdot  {u_j})  }$
   2.  $\vec{u_i^T}$ 是 节点 $u_i$ 的低维度向量，维度从|V|降低到d， $p(\cdot,\cdot)$是节点空间|V| * |V|的分布，可以使用 $\frac{w_{ij}}{W}$进行表示，W为网络中所有节点对的权重之和
   3. 一阶近似关系优化定义： $O_1 = d(\hat{p_i}(\cdot,\cdot), p_i(\cdot,\cdot) ) $
   4. 目标函数优化方法： $ d(\cdot,\cdot)$表示两个分布之间的差异性，可以使用KL距离进行刻画，$O_1= - \sum_{(i,j) \in E} w_{ij} \cdot log(p_1(v_i,v_j)) $
2. 二阶近似关系描述
   1. 假设：具有相似的邻接网络结构的节点具有一定的相似性，共享邻居节点的结构，二阶相似度指的是一对顶点之间的接近程度，即$(u,v)$在网络中是其邻域网络结构之间的相似性
   2. 定义为：一阶相似度向量之间的相似，一阶近似关系得到的向量代表节点u与其邻接节点的信息
   3. j是变量，对于固定的i来说同样类似一阶相似，二阶相似的分布之间的差异性进行优化  

chapter4.2 目标函数优化问题

• 由于网络中节点之间度的方差非常大，会造成梯度爆炸，所以要对目标函数进行优化处理
• 二阶中计算每个节点的分布都需要计算所有边，计算代价大，使用了负采样方法，只取部分负样本进行处理
• 

   

   

• 上述函数可以采用异步随机梯度下降算法（ASGD）优化，每一步中，ASGD算法对小批量边缘进行抽样，然后更新模型参数。但是这也带来一个问题，如果我们根据小权重的边缘选择较大的学习率，那么大权重的边上的梯度就会爆炸式的过大，如果我们根据具有较大权重的边选择学习小的速率，那么小权重上的边的梯度将变得太小。因此边缘采样同样要优化。从起始边缘采样并将采样的边缘作为二进制边缘，其中采样概率与原始边缘的权重成比例

原文：https://www.cnblogs.com/zhangleleuestc/p/13370711.html