前言

在上一篇文章中，我们介绍了Graph Embedding技术中的代表算法——Deepwalk。今天，我们将为大家介绍另一种重要的算法：LINE（Large-scale Information Network Embedding）。LINE致力于将大规模的信息网络嵌入到低维度的向量空间中，适用于各种类型的网络（包括有向图、无向图以及带权图）。此外，LINE还提出了一种改进的经典随机梯度下降算法的边缘采样方法，从而提升了算法的效率和实用性。总结起来，LINE具有以下几个显著的特点：

1. 广泛适用：LINE能够应用于任意类型的网络，无论是有向图、无向图还是带权图。
2. 全面覆盖：目标函数同时考虑了网络的局部特征和全局特征。
3. 高效执行：通过引入边采样算法，有效解决了随机梯度下降的效率问题。
4. 快速计算：LINE提出了一种高效的网络表示方法，能够在短时间内学习到大规模网络的表示。

重要定义

在深入了解LINE算法之前，我们需要先了解一些关键概念。

信息网络

信息网络可以表示为G=(V,E)，其中V是顶点集合，代表数据对象，E是顶点之间的边的集合，每条边表示两个数据对象之间的关系。每条边e可以表示为有序对e=(u,v)，并与权重Wuv（Wuv>0）相关联，表示关系的强度。如果G是无向图，则(u,v)=(v,u)，且Wuv=Wvu；如果G是有向图，则(u,v)≠(v,u)，且Wuv≠Wvu。通常情况下，我们假定权重是非负的。

一阶相似性

在网络中，一阶相似性是指两个顶点之间的局部邻近度。对于每对通过边(u,v)相连的顶点，该边的权重Wuv表示u和v之间的一阶相似性。如果u和v之间没有边连接，则它们的一阶相似性为0。

二阶相似性

二阶相似性指的是两个顶点之间的间接相似性，即它们在网络中的邻域结构之间的相似性。具体来说，如果pu和pv分别表示u和v的邻域结构，那么u和v之间的二阶相似性取决于pu和pv的相似性。如果没有一个顶点同时与u和v相连，则u和v的二阶相似性为0。

大规模信息网络嵌入

给定一个大规模网络G=(V,E)，大规模信息网络嵌入的目标是将每个顶点v表示为低维度空间中的向量。通过学习一个映射函数，我们可以将每个顶点映射到一个低维度的向量空间中，从而实现网络的高效表示。