前言

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

1. 适用性广：LINE能够处理各种类型的网络，无论是有向图、无向图还是带权图。
2. 信息全面：目标函数同时考虑了网络的局部特征和全局特征。
3. 高效性：提出了一种高效的边采样算法，解决了随机梯度下降（SGD）的效率问题。
4. 速度快：提供了一种快速的网络表示方法，在单个计算节点上可以在数小时内完成百万级别顶点的网络表示学习。

接下来让我们详细了解LINE算法的核心概念。

重要定义

在深入了解LINE算法之前，我们需要先掌握论文中的一些关键概念。

信息网络

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

一阶相似性

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

二阶相似性

二阶相似性指的是两个顶点之间的间接相似性，通过它们各自的邻域结构来衡量。数学上，设N(u)表示顶点u的所有邻居，那么u和v之间的二阶相似性取决于pu和pv之间的相似性。如果没有一个顶点同时与u和v相连，则u和v之间的二阶相似性为零。

大规模信息网络嵌入

给定一个大网络G=(V, E)，大规模信息网络嵌入的任务是将每个顶点v表示为低维空间中的向量。学习的目标是找到一个函数f，使得对于任意顶点v，都有一个对应的向量fv，该向量尽可能准确地反映了顶点v在网络中的位置和特性。

希望以上内容对你有所帮助。