前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 

知其然 知其所以然！

 
本文仅记录自己感兴趣的内容

ABSTRACT

本文研究了将非常大的信息网络嵌入到低维向量空间的问题（大规模网络嵌入）

我们提出了一种新的网络嵌入方法，称为“LINE”，它适用于任意类型的信息网络:无向、有向和/或加权

• 该方法优化了一个精心设计的目标函数，同时保留了局部和全局网络结构
• 针对经典随机梯度下降算法的局限性，提出了一种边缘采样算法，提高了推理的有效性和效率。

实验证明LINE在语言网络、社交网络、引文网络等多种现实信息网络中具有有效性

该算法非常高效，能够在一台典型的单机机器上在几个小时内学习包含数百万个顶点和数十亿条边的网络的嵌入 （适于大型网络高效进行网络嵌入）

1. INTRODUCTION

LINE在保留局部和全局网络结构的前提下对目标进行优化

自然地，局部结构由网络中观察到的连接表示，反映了顶点之间的一阶邻近

在真实的网络中，许多(如果不是大多数的话)合法的连接实际上是没有被观察到的。所以在真实世界数据中观测到的一阶接近度不足以保留全局网络结构

作为补充，我们探索顶点之间的二阶邻近性，这不是通过观察节点之间的连接强度，而是通过顶点的共享邻域结构来确定的

---

二阶邻近的一般概念可以解释为共享邻居的节点可能是相似的

这种直觉可以在社会学和语言学的理论中找到。

以下图为例

• 由于顶点6和7之间的边的权值较大，即6和7具有较高的一阶接近度，因此在嵌入空间中应该紧密地表示它们。
• 顶点5和顶点6之间虽然没有联系，但它们有很多共同的邻居，即它们有很高的二阶接近度，因此它们之间也应该紧密地表示

我们期望 二阶邻近性的考虑 有效地补充了一阶邻近性的稀疏性，并更好地保留了网络的全局结构。

---

即使找到了一个合理的目标优化函数，针对一个非常大的网络进行优化也是一项挑战

随机梯度下降法（SGD）是近年来备受关注的一种优化方法。然而，直接部署随机梯度下降对于真实世界的信息网络是有问题的

• 因为在许多网络中，边缘都是加权的
• 而且权重通常呈现出很高的方差
• 比如考虑一个单词共现网络，其中单词对的权重(共现)从1到数十万不等。
• 这些边的权值将被乘到梯度中，导致梯度爆发，从而影响性能。

为了解决这个问题，我们提出了一种新的边缘采样方法，它提高了推断的有效性和效率

• 我们以与其权重成正比的概率对边进行采样，然后将采样的边作为二值边进行模型更新。
• 在这个采样过程中，目标函数保持不变，边缘的权重不再影响梯度

---

本文贡献

• 我们提出了一种新的网络嵌入模型，称为“LINE”，它适用于任意类型的信息网络，并容易扩展到数百万个节点。它有一个精心设计的目标函数，同时保持一阶和二阶邻近性。
• 我们提出了一种边缘采样算法来优化目标。该算法解决了经典随机梯度算法的局限性，提高了推理的有效性和效率。
• 我们在真实世界的信息网络上进行广泛的实验。实验结果证明了LINE模型的有效性和高效性。

2. RELATED WORK

一般的图嵌入或降维的经典方法，如MDS[4]、IsoMap[20]、LLE[18]和Laplacian Eigenmap[2]

• 通常首先使用数据点的特征向量构造亲和性图，例如数据的k近邻图
• 然后将亲和性图[22]嵌入到低维空间中

然而，这些算法通常依赖于求解亲和矩阵的主导特征向量，其复杂度至少是节点数量的二次方，这使得它们在处理大规模网络时效率低下

---

图分解[1]技术

• 通过矩阵分解找到大图的低维嵌入
• 并使用随机梯度下降法进行优化

然而，矩阵分解的目标并不是针对网络设计的，因此不一定能保持网络的全局结构

直观上，图分解要求一阶接近度较高的节点被紧密表示。

图分解方法只适用于无向图

---

DeepWalk[16]，它为社交网络嵌入部署了一个截断的随机游走。

尽管在经验上是有效的，但DeepWalk并没有提供一个明确的目标，说明哪些网络属性被保留。

• 直观上，DeepWalk期望具有较高二阶接近度的节点产生类似的低维表示
• 而LINE同时保持一阶和二阶接近度

区别：

• DeepWalk使用随机漫步来扩展顶点的邻域，这类似于深度优先搜索，而LINE采用宽度优先搜索策略，这是一种比较合理的二阶逼近方法。
• DeepWalk只适用于未加权的网络，而LINE适用于既有加权边又有非加权边的网络。

3. PROBLEM DEFINITION

Definition 1. (Information Network)

• $G=(V,E)$

• $e=(u,v),e\in E,u,v\in V$

• $w_{u,v}$：节点u、v之间边的权重

现实中，信息网络可以是定向的(如引用网络)，也可以是非定向的(如Facebook中用户的社交网络)。这些边的权值可以是二值的，也可以取任何实数

• 例如，在引文网络和社交网络中，$w_{uv}$取二值（0或1）;
• 在不同对象间的共现网络中，$w_{uv}$可以取任意非负值。

注意，虽然负权边是可能的，但在本研究中我们只考虑非负权边。

在某些网络中，当一些对象多次共出现而另一些对象可能只共出现几次时，边缘的权值可能会发生分歧。（没懂）

---

Definition 2. (First-order Proximity)

网络中的一阶邻近性是两个顶点之间的局部两两邻近性。

• 对于每一对由边$(u,v)$连接的顶点，该边的权值$w_{uv}$表示$u$和$v$之间的一阶接近度。
• 如果$u$和$v$之间没有边，则它们的一阶接近度为0。

一阶邻近度通常意味着网络中两个节点的相似性。

例如，在社交网络中彼此是朋友的人往往拥有相似的兴趣；在万维网中相互链接的页面往往谈论相似的话题。

由于这种重要性，许多现有的图嵌入算法，如ISOMAP、LLE、拉普拉斯特征映射和图因式分解，都以保持一阶邻近性为目标。

然而，在现实世界的信息网络中，观察到的连接只占一小部分，还有许多其他链接缺失[10]。

缺失链路上的一对节点具有零一阶邻近度（缺失边，一阶邻近性为0），即使它们本质上彼此非常相似。

因此，仅有一阶邻近性不足以保存网络结构，重要的是寻求另一种邻近性概念来解决稀疏性问题。

一种自然的直觉是，共享相似邻居的顶点往往彼此相似。

例如

• 在社交网络中，拥有相似朋友的人往往有相似的兴趣，从而成为朋友；
• 在单词共现网络中，总是与同一组单词共现的单词往往具有相似的含义。

因此，我们定义了二阶邻近度，它补充了一阶邻近度，并保持了网络结构。

---

Definition 3. (Second-order Proximity)

网络中一对顶点$(u,v)$之间的二阶邻近性是其邻域网络结构之间的相似性。

设$p_u=(w_{u,1}，\dots ，w_{u，|V|})$表示$u$与所有其他顶点的一阶邻近性

则$u$与$v$的二阶接近度由$p_u$与$p_v$的相似度决定

如果没有一个顶点同时连接到u和v，那么u和v之间的二阶邻近性为0。

---

Definition 4. (Large-scale Information Network Embedding)

给定一个大网络$G=(V,E)$，大规模信息网络嵌入问题的目标是将每个顶点$v\in V$表示到一个低维空间$R^d$中

即学习函数$f_G:V\to R^d$，其中 $d<<|V|$。

在空间$R^d$中，顶点之间的一阶邻近性和二阶邻近性都保持不变。

4. LINE: LARGE-SCALE INFORMATION NETWORK EMBEDDING

一个理想的真实世界信息网络嵌入模型必须满足以下几个条件:

• 第一，它必须能够同时保持顶点之间的一阶和二阶邻近性
• 其次，它必须适用于非常大的网络，比如数百万个顶点和数十亿条边;
• 第三，它可以处理具有任意类型边的网络:有向边、无向边和/或加权边

4.1 Model Description

我们描述了LINE模型，分别保持一阶邻近性和二阶邻近性，然后介绍了一种简单的结合两阶邻近性的方法。

4.1.1 LINE with First-order Proximity

一阶接近是指网络中顶点之间的局部两两接近。

为了模拟一阶接近，对于每个无向边(i, j)，我们定义顶点$v_i$和$v_j$之间的联合概率如下

其中${\vec{u}}_i\in R^d$，表示顶点$v_i$的向量表示

等式(1)定义了$V\times V$空间上的一个分布$p(\cdot ,\cdot )$，其经验概率可以定义为$\widehat{p_1}(i,j)=\frac{w_{ij}}{W}$，其中$W={\sum }_{(i,j)\in E}{w}_{ij}$

---

为了保持一阶接近，一个直接的方法是最小化以下目标函数

$d(\cdot ,\cdot )$为两个分布之间的距离

我们选择最小化两个概率分布的KL散度（KL-divergence）

KL-divergence：https://zhuanlan.zhihu.com/p/425693597

用$KL-散度$替换$d(\cdot ,\cdot )$，并去掉一些常数，我们有

注意，一阶接近只适用于无向图，而不适用于有向图。

通过找到$\{{\hat{u}}_i{\}}_{i=1...|V|}$ 最小化等式（3）

4.1.2 LINE with Second-order Proximity

二阶邻近既适用于有向图，也适用于无向图

给定一个网络，不失一般性的情况下，我们假设它是有向的

一条无向边可以被认为是两个方向相反、权值相等的有向边

---

二阶接近假设顶点之间有很多连接，它们彼此相似。在这种情况下，每个顶点也被视为一个特定的“上下文”，在“上下文”上具有类似分布的顶点被认为相似。

个人理解：若顶点的上下文分布类似，那么这些节点很可能也是相似的

因此，每个顶点都扮演两个角色：顶点本身和其他顶点的特定“上下文”。

我们引入两个向量${\vec{u}}_i$和${\vec{u}}_i^{{}^{\prime }}$

• 其中${\vec{u}}_i$是将$v_i$视为顶点时的表示
• ${\vec{u}}_i^{{}^{\prime }}$是将$v_i$视为特定“上下文”时的表示

---

对于每条有向边(i, j)，我们首先定义顶点$v_i$生成“上下文”$v_j$的概率为:

• 其中$|V|$是顶点或“上下文”的数量
• 此时$v_i$角色为“节点本身”，$v_j$角色为其他节点的上下文

对于每个顶点$v_i$, 等式(4)实际上定义了一个基于上下文的条件分布$p_2(\cdot |v_i)$

如上所述，二阶接近假设在上下文中具有相似分布的顶点彼此相似

为了保持二阶接近，我们应该使低维表示所指定的上下文$p_2(\cdot |v_i)$的条件分布接近经验分布${\hat{p}}_2(\cdot |v_i)$

因此，我们最小化以下目标函数:

• $d(\cdot ,\cdot )$为两个分布之间的距离，也是采用KL散度
• ${\lambda }_i$来表示网络中顶点i的声望，${\lambda }_i=d_i$，$d_i$为顶点i的出度

经验分布${\hat{p}}_2(\cdot |v_i)$定义为$p_2(v_j|v_i)=\frac{w_{ij}}{d_i}$

• $w_{ij}$为边(i, j)的权值，
• $d_i$为顶点i的出度，即$d_i={\sum }_{k\in N(i)}{w}_{ik}$，其中$N(i)$为$v_i$的出邻居集合

得到最终目标优化函数：

通过学习${\vec{u}}_i$和${\vec{u}}_i^{{}^{\prime }}$来最小化等式（6）

4.1.3 Combining first-order and second-order proximities

为了同时保持一阶和二阶邻近性嵌入网络，我们在实践中发现了一种简单有效的方法，即

• 分别训练保持一阶邻近性和二阶邻近性的LINE模型
• 然后对每个顶点将两种方法训练的嵌入连接起来

4.2 Model Optimization

优化目标(6)的计算成本很高，在计算条件概率$p_2(\cdot |v_i)$时需要对整个顶点集求和。

为了解决这一问题，我们采用[13]中提出的负采样方法，对每条边(i, j)按照一定的噪声分布对多个负边进行采样。

具体来说，它为每条边(i, j)指定了以下目标函数:

其中$\sigma (x)=\frac{1}{1+e^{-x}}$

第一项对观察到的边进行建模，第二项对从噪声分布中提取的负边缘进行建模，k是负边缘的数量。

我们设$P_n(v)\propto d_v^{3/4}$，$d_v$为顶点$v$的出度

---

对于目标函数(3)，存在一个平凡解:$u_{ik}=\infty$，对于$i=1，\dots ，|V|$， $k=1，\dots ，d$。

为了避免平凡解，我们仍然可以利用负采样方法(7)，只需将${\vec{u}}_j^{{}^{\prime }T}$改为${\vec{u}}_j^T$

---

我们采用异步随机梯度算法(ASGD)[17]对等式（7）进行优化

在每一步中，ASGD算法都会对一小批边缘进行采样，然后更新模型参数。

如果采样了一条边(i, j)，则梯度w.r.t计算顶点i的嵌入向量${\vec{u}}_i$为：

注意，梯度将乘上边缘的权值

当边的权值方差很大时，这就会出现问题

例如，在一个单词共现网络中，有些单词共现多次(例如，数万次)，而有些单词只共现几次。在这样的网络中，梯度的尺度是发散的，很难找到一个好的学习率。

如果我们根据权重小的边选择一个大的学习率，那么权重大的边上的梯度就会爆炸，而如果我们根据权重大的边选择学习率，梯度就会太小。

4.2.1 Optimization via Edge Sampling

解决上述问题的直觉是，如果所有边的权值相等(例如，具有二值边的网络)，那么选择合适的学习率就没有问题

因此，一种简单的处理方法是将一条加权边展开为多个二值边

例如，一条权值为$w$的边展开为$w$条二值边

这将解决问题，但将显著增加内存需求，特别是当边缘的权值非常大的时候。

---

为了解决这个问题，我们可以从原始边采样，并将采样的边视为二值边，采样概率与原始边的权值成比例。

通过这种边缘采样处理，总体目标函数保持不变。

---

这个问题归结为如何根据它们的权重对边缘进行采样

设$W=(w1,w2，\dots ，w|E|)$表示边权值的序列。我们可以简单地计算权值的总和$w_{sum}={\sum }_{i=1}^{|E|}$，然后在$[0,w_{sum}]$范围内采样一个随机值，看看该随机值属于哪个区间$[{\sum }_{j=0}^{i-1}{w}_j,{\sum }_{j=0}^i{w}_j)$

这种方法需要$O(|E|)$的时间来绘制一个样本，当边缘$|E|$的数量很大时，这种方法的开销很大。

我们使用别名表方法[9]根据边缘的权值来绘制样本，当从相同的离散分布反复绘制样本时，只需要O(1)时间。

从别名表中采样一条边需要常数时间$O(1)$，负采样优化需要$O(d(K+1))$时间，其中$K$是负采样的数量。

因此，总的来说，每一步耗时$O(dK)$。

在实践中，我们发现用于优化的步数通常与边的数量$O(|E|)$成正比。因此，LINE的整体时间复杂度为$O(dK|E|)$，与边数$|E|$线性，与顶点数$|V|$无关。

边采样处理在不影响效率的前提下提高了随机梯度下降算法的有效性。

4.3 Discussion

Low degree vertices

一个实际的问题是如何精确地嵌入度非常小的顶点。由于这样一个节点的邻居数量非常少，所以很难准确地推断出它的表示，尤其是使用严重依赖于“上下文”数量的二阶邻近性方法。

一个直观的解决方案是通过添加更高阶的邻居来扩展这些顶点的邻居，比如邻居的邻居。

在本文中，我们只考虑在每个顶点上添加二阶邻域，即邻域的邻域。

顶点$i$与其二阶邻居$j$之间的权值的度量为

在实践中，我们只能添加一个顶点$j$的子集，该子集与顶点$i$的$w_{ij}$最大

---

New vertices

另一个实际问题是如何找到新到达的顶点的表示。

对于一个新的顶点i，如果已知它与现有顶点的关系，我们就可以得到现有顶点上的经验分布${\hat{p}}_1(\cdot ,v_i)$和${\hat{p}}_2(\cdot |v_i)$。

根据目标函数等式（3）或（6）得到新顶点的嵌入

一种直接的方法是最小化以下任一目标函数

通过更新新顶点的嵌入，保持现有顶点的嵌入。

如果没有观察到新顶点和现有顶点之间的连接，我们必须求助于其他信息，比如顶点的文本信息，我们把它留给未来的工作

5. EXPERIMENTS

我们对LINE的有效性和效率进行了实证评估。我们将该方法应用于多个不同类型的大型真实世界网络，包括一个语言网络、两个社会网络和两个引文网络。

5.1 Experiment Setup

数据集

基线方法

• GF
• Deep Walk
• Skip Gram
• LINE-SDD(1st)
• LINE-SDD(2nd)
• LINE(1st)
• LINE(2nd)

5.2 Quantitative Results

5.2.1 Language Network

Word Analogy.

Document Classification

使用一阶和二阶接近比较大多数相似的单词。

5.2.2 Social Network

Flickr网络上的多标签分类结果

Youtube网络上的多标签分类结果

5.2.3 Citation Network

基于DBLP(AuthorCitation)网络的多标签分类结果

基于DBLP(PaperCitation)网络的多标签分类结果。

5.3 Network Layouts

可视化的合著者网络。作者被映射到二维空间使用t-SNE包学习嵌入作为输入。

节点的颜色表示作者所在的社区

• 红色:“数据挖掘”
• 蓝色:“机器学习”
• 绿色:“计算机视觉”。

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/125311404