LINE的一阶与二阶邻近，大规模图的负采样优化？
一阶邻近：直接相连的节点对，边 $(u,v)$ 存在则 $u,v$ 应接近。二阶邻近：不直接相连但共享很多邻居的节点对，即「邻居的邻居」相似，如两个用户买了大量相同商品。LINE 用两个目标分别刻画这两种关系，再联合训练或拼接嵌入。
对边 $(u,v)$ 与边权 $w_{uv}$，定义联合概率与经验概率，用 KL 散度或交叉熵最小化。一阶目标使直接相连节点嵌入内积大（或距离小）： \(\mathcal{L}_1 = -\sum_{(u,v)} w_{uv} \ln \sigma(\boldsymbol{u}^\top \boldsymbol{v}),\) 其中 $\boldsymbol{u},\boldsymbol{v}$ 为节点嵌入，$\sigma$ 为 sigmoid。即最大化边两端节点向量的相似度，权重大则损失权重大。
二阶：节点 $u$ 的「上下文」为其邻居分布。设 $u$ 的邻居分布为经验分布 $\hat{p}(\cdot \mid u)$，模型用 softmax 拟合 $p(v \mid u) \propto \exp(\boldsymbol{u}^\top \boldsymbol{v}’)$（$\boldsymbol{v}’$ 为上下文嵌入）。目标为最小化 $\hat{p}$ 与 $p$ 的 KL 或交叉熵，使「邻居分布」相似的节点嵌入相似。形式上与 Skip-gram 一致，即 \(\mathcal{L}_2 = -\sum_{(u,v)} w_{uv} \ln \frac{\exp(\boldsymbol{u}^\top \boldsymbol{v}')}{\sum_{v'} \exp(\boldsymbol{u}^\top \boldsymbol{v}')}.\)
$\mathcal{L}2$ 中 softmax 分母对大规模图不可算。负采样：对每条边 $(u,v)$，采样 $K$ 个负节点 $v^-$，用 \(-\ln \sigma(\boldsymbol{u}^\top \boldsymbol{v}') - \sum_{v^-} \ln \sigma(-\boldsymbol{u}^\top \boldsymbol{v}^{'-})\) 近似，将 $O(|V|)$ 的归一化变为 $O(K)$。负样本常按度或均匀采样；边采样：按边权 $w{uv}$ 采样边做 mini-batch，避免权重大边主导梯度，同时控制每轮计算量。二者结合可在大规模图上高效训练 LINE。
| 返回模块 | 返回总览 |