Question

1. 传统的网络挖掘、网络学习的范式通常从对网络结构属性structural property 的显式探索而开始。但是许多这类的属性（如中介中心度 betweenness centrality、三角计数 triangle count、模度 modularity）由人工制作，并且需要广泛的领域知识和昂贵的计算代价。鉴于这些问题，以及最近出现的 representation learning 所提供的机会，人们广泛研究了学习网络的潜在 representation（也就是 network embedding ），以便自动发现网络的结构属性并将其映射到一个潜在的空间。

   形式上，network embedding 的问题通常形式化如下：给定一个无向带权图 $ G=(V,E,\mathbf A) $ ，其中 $ V $ 为顶点集合、 $ E $ 为边集合、 $ \mathbf A $ 为邻接矩阵，任务的目标是学习一个映射 $ V\rightarrow \mathbb R^d $ ，该映射将每个顶点映射到一个能够捕获该顶点结构属性的 $ d $ 维向量。输出的 representation 可以用于各种网络科学任务、网络 learning algorithm 的输入，例如标签分类、社区检测。

   解决这个问题的尝试可以追溯到谱图理论 spectral graph theory 和社交维度学习 social dimension learning 。该问题最近的进展很大程度上受到 SkipGram 模型的影响。SkipGram 模型最初是为 word embedding 所提出的，其输入是由自然语言中的句子组成的文本语料库，输出是语料库中每个单词的 latent vector representation 。值得注意的是，受到该 setting 的启发，DeepWalk 通过将网络上随机游走所遍历的顶点路径视为句子，并利用 SkipGram 来学习潜在的节点 representation，从而开创了 network embedding 的先河。随着 DeepWalk 的出现，人们后续已经开发了很多 network embedding 模型，例如 LINE、PTE、node2vec 。

   到目前为止，上述模型已经被证明非常有效。然而，它们背后的理论机制却鲜为人知。人们注意到，用于 word embedding 的、带负采样的 SkipGram 模型已经被证明是某个 word-context 矩阵的隐式分解，并且最近有人努力从几何角度从理论上解释 word embedding 模型。但是，目前尚不清楚 word-context 矩阵与网络结构之间的关系。此外，早期人们尝试从理论上分析 DeepWalk 的行为，然而他们的主要理论结果和原始 DeepWalk 论文的 setting 并不完全一致。此外，尽管 DeepWalk, LINE, PTE, node2vec 之间存在表面上的相似性，但是对它们的底层联系缺乏更深入的了解。

   在论文 《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec》中，作者提供了关于几种基于 SkipGram 的 network embedding 方法的理论结果。具体而言：

   • 论文首先表明这里提到的模型（即 DeepWalk, LINE, PTE, node2vec ）在理论上执行隐式矩阵分解。论文为每个模型推导出矩阵的封闭形式 closed form 。例如，DeepWalk （图上的随机游走加上 SkipGram）本质上是对一个随机矩阵进行因子分解，并且随着随机游走的长度趋于无穷大，该矩阵在概率上收敛到这个的闭式矩阵。
   • 其次，从它们矩阵的闭式形式观察，作者发现有意思的是，LINE 可以视为 DeepWalk 的一个特例：当 SkipGram 中的上下文窗口大小 $ T = 1 $ 时。此外，作者证明了 PTE 作为 LINE 的扩展，实际上是多网络的联合矩阵joint matrix 的隐式分解。
   • 第三，作者发现了 DeepWalk 的隐式矩阵implicit matrix 和图拉普拉斯矩阵graph Laplacian 之间的理论联系。基于这种联系，作者提出了一种新算法 NetMF 来逼近 DeepWalk 隐式矩阵的封闭形式。通过使用 SVD 显式分解该矩阵，论文在四个网络（在 DeepWalk 和 node2vec 论文中所采用的）中的广泛实验证明了 NetMF 相比于 DeepWalk 和 LINE 的出色性能（相对提升高达 50%）。

   论文的理论价值高于 NetMF 实用的价值，实际上 NetMF 很难应用到工业环境中，因为 NetMF 的时间复杂度和空间复杂度都太高。

2. 论文展示了所有上述带负采样的模型都可以统一到具有封闭形式closed form 的矩阵分解框架中。论文的分析和证明表明：

   • DeepWalk 经验性empirically 地产生了网络归一化拉普拉斯矩阵的低秩变换low-rank transformation 。
   • LINE 理论上是 DeepWalk 的一个特例：当顶点的上下文 size 为 1 时。
   • 作为 LINE 的扩展，PTE 可以视为多个网络的拉普拉斯矩阵的联合分解。
   • node2vec 正在分解与二阶随机游走的平稳分布、转移概率张量等相关的矩阵。

   这项工作为基于 SkipGram 的 network embedding 方法奠定了理论基础，从而更好地理解了潜在的 network representation learning 。

3. 相关工作：network embedding 的故事来源于谱聚类 Spectral Clustering。谱聚类是一种数据聚类技术，它选择数据的亲和矩阵 affinity matrix 的特征值eigenvalue /特征向量 eigenvector 从而获得representation ，从而进一步用于聚类或嵌入到低维空间。谱聚类已广泛应用于社区检测和图像分割等领域。

   近年来，人们对 network embedding 越来越感兴趣。继 SocDim 和 DeepWalk 等一些开创性工作之后，越来越多的文献试图从不同的角度解决这个问题，例如 heterogeneous network embedding 、半监督 network embedding、具有丰富顶点属性的 network embedding、具有高阶结构的 network embedding、有符号的 network embedding 、有向的network embedding、通过神经网络的 network embedding 等等。在上述研究中，一种常用的技术是为每个顶点定义 context，然后训练一个预测模型来进行上下文预测。例如，DeepWalk, node2vec, metapath2vec 分别通过基于一阶的随机游走、基于二阶的随机游走、基于 metapath 的随机游走来定义顶点的上下文。

   利用上下文信息的思想很大程度上是由带负采样的 SkipGram 模型skip-gram model with negative sampling: SGNS所推动的。最近，人们一直在努力理解这个模型。例如：

   • 《NeuralWord Embedding as Implicit Matrix Factorization》 证明了 SGNS 实际上是进行隐式矩阵分解，这为我们提供了分析上述 network embedding 模型的工具。
   • 《A latent variable model approach to pmi-based word embeddings》 提出生成模型 RAND-WALK 来解释 word embedding 模型。
   • 《Word embeddings as metric recovery in semantic spaces》 将 word embedding 框架作为度量学习问题。

   基于隐式矩阵分解的工作，我们从理论上分析了流行的、基于 SkipGram 的 network embedding 模型，并将它们与谱图理论联系起来。

15.1 模型

1. 这里我们首先介绍四种流行的 network embedding 方法（LINE, PTE, DeepWalk, node2vec）的详细理论分析和证明，然后提出我们的 NetMF 方法。

15.1.1 LINE

1. 给定一个带权无向图 $ G=(V,E,\mathbf A) $ ，二阶邻近性的LINE（即 LINE(2nd) ）的任务是学到两个representation 矩阵 ：

   • vertex represetation 矩阵 $ \mathbf X \in \mathbb R^{|V|\times d} $ ：第 $ i $ 行 $ \mathbf{\vec x}_i $ 为顶点 $ v_i $ 作为vertex 时的 embedding 向量。
   • context representation 矩阵 $ \mathbf Y \in \mathbb R^{|V|\times d} $ ：第 $ i $ 行 $ \mathbf{\vec y}_i $ 为顶点 $ v_i $ 作为contex 时的 embedding 向量。

   LINE(2nd) 的目标函数为：

   $ \mathcal L = \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A_{i,j} \left(\log \sigma(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j) + b \mathbb E_{j^\prime \sim P_N}[\log \sigma(-\mathbf{\vec x}_i\cdot \mathbf{\vec y}_{j^\prime})]\right) $

   其中： $ \sigma(\cdot) $ 为 sigmoid 函数， $ b $ 为负采样系数， $ P_N $ 为用于产生负样本的 noise 分布。在 LINE 原始论文中使用经验分布 $ P_N(j)\propto d_j^{3/4} $ ，其中 $ d_j $ 为顶点 $ j $ 的加权 degree $ d_j = \sum_{k=1}^{|V|}A_{j,k} $ 。

   LINE(2nd) 的目标函数为 $ -\sum_{(i,j)\in E} A_{i,j}\times \log \frac{\exp(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j)}{\sum_{k=1}^{|V|}\exp(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_k)} $ （即 $ -\sum_{(i,j)\in E} A_{i,j}\times \log p_2(v_j\mid v_i) $ ），考虑到 $ (i,j)\notin E $ 时 $ A_{i,j} = 0 $ 以及负采样，则得到上述目标函数。这也是为什么 $ \mathcal L $ 中 $ A_{i,j} $ 不仅作用在“正边”、也作用在 “负边” 上的原因。

2. 本文我们选择 $ P_N(j)\propto d_j $ ，因为这种形式的经验分布将得到一个闭式解closed form solution 。定义 $ \text{vol}_G = \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A_{i,j}=\sum_{j=1}^{|V|}d_j $ 为所有顶点的加权 degree 之和，则有 $ P_N(j) = \frac{d_j}{\text{vol}_G} $ 。我们重写目标函数为：

   $ \mathcal L = \left(\sum_{i=1}^{|V|}\sum_{j=1}^{|V|} A_{i,j}\log \sigma(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j)\right) + \left(b\sum_{i=1}^{|V|} d_i \mathbb E_{j^\prime \sim P_N}[\log \sigma(-\mathbf{\vec x}_i\cdot \mathbf{\vec y}_{j^\prime})]\right) $

   我们在图 $ G $ 的所有顶点上计算，从而得到期望为：

   $ \mathbb E_{j^\prime \sim P_N}[\log \sigma(-\mathbf{\vec x}_i\cdot \mathbf{\vec y}_{j^\prime})] = \sum_{j=1 }^{|V|} \frac{d_{j }}{\text{vol}_G} \log \sigma(-\mathbf{\vec x}_i\cdot \mathbf{\vec y}_{j }) $

   因此有：

   $ \mathcal L = \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}\left(A_{i,j}\log\sigma(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j) + b \frac{d_id_j}{\text{vol}_G}\log \sigma(\mathbf{-\vec x}_i\cdot \mathbf{\vec y}_j)\right) $

   则对于每一对顶点 (i,j)，其局部目标函数local objective function 为：

   $ \mathcal L(i,j) = A_{i,j}\log \sigma(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j) + b \frac{d_id_j}{\text{vol}_G}\log \sigma(\mathbf{-\vec x}_i\cdot \mathbf{\vec y}_j) $

   定义 $ z_{i,j} = \mathbf{\vec x}_i \cdot \mathbf{\vec y}_j $ ，根据 《NeuralWord Embedding as Implicit Matrix Factorization》 的结论：对于一个足够大的 embedding 维度， 每个 $ z_{i,j} $ 之间可以认为是相对独立的。因此我们有：

   $ \frac{\partial \mathcal L}{\partial z_{i,j}} = \frac{\partial \mathcal L(i,j)}{\partial z_{i,j}} = A_{i,j} \sigma(-z_{i,j}) - b \frac{d_id_j}{\text{vol}_G}\sigma(z_{i,j}) $

   为求解目标函数极大值，我们令偏导数为零，则有：

   $ \exp(2z_{i,j}) - \left(\frac{\text{vol}_GA_{i,j}}{bd_id_j} -1\right)\exp(z_{i,j}) - \frac{\text{vol}_GA_{i,j}}{bd_id_j} = 0 $

   这个方程有两个闭式解：

   • $ \exp(z_{i,j}) = -1 $ ：其解为虚数，不予考虑。
   • $ \exp(z_{i,j}) = \frac{\text{vol}_G A_{i,j}}{bd_id_j} $ ：有效解。

   因此有：

   $ \mathbf{\vec x}_i\cdot \mathbf{\vec y}_j = z_{i,j} = \log \left(\frac{\text{vol}_G A_{i,j}}{bd_id_j}\right) $

   则 LINE(2nd) 对应于矩阵分解：

   $ \mathbf X\mathbf Y^\top = \log(\text{vol}_G \mathbf D^{-1}\mathbf A \mathbf D^{-1}) - (\log b)\mathbf I $

   其中对角矩阵 $ \mathbf D = \text{diag}(d_1,\cdots,d_{|V|}) $ 。

15.1.2 PTE

1. PTE 是 LINE(2nd) 在异质文本网络heterogeneous text network 中的扩展。我们首先将我们对 LINE(2nd) 的分析调整到二部图网络。考虑一个二部图网络 $ G=(V_1\cup V_2, E, \mathbf A) $ ，其中 $ V_1 $ 和 $ V_2 $ 是两个不相交的顶点集合， $ E\sube V_1\times V_2 $ 是边集合， $ \mathbf A\in \mathbb R^{|V_1|\times |V_2|} $ 为二部图网络的邻接矩阵。定义图 $ G $ 的 volume 为 $ \text{vol}_G = \sum_{i=1}^{|V_1|}\sum_{j=1}^{|V_2|} A_{i,j} $ 。则 PTE 的目标是学习每个节点 $ v_i\in V_1 $ 的节点 representation $ \mathbf{\vec x}_i $ 、以及学习每个节点 $ v_j\in V_2 $ 的节点 representation $ \mathbf{\vec y}_j $ 。则 LINE(2nd) 的目标函数为：

   $ \mathcal L = \sum_{i=1}^{|V_1|}\sum_{j=1}^{|V_2|} A_{i,j} \left(\log \sigma(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j) + b \mathbb E_{j^\prime \sim P_N}[\log \sigma(-\mathbf{\vec x}_i\cdot \mathbf{\vec y}_{j^\prime})]\right) $

   这里 $ V_1 $ 内节点和 $ V_2 $ 内节点互为上下文，因此没必要引入 $ V_1 $ 上下文的 embedding 变量、 $ V_2 $ 上下文的 embedding 变量。

   与 LINE 相同的分析过程，我们可以发现最大化 $ \mathcal L $ 等价于因子分解：

   $ \mathbf X\mathbf Y^\top = \log(\text{vol}_G \mathbf D_\text{row}^{-1}\mathbf A \mathbf D^{-1}_\text{col}) - (\log b)\mathbf I $

   其中 $ \mathbf D_\text{row} = \text{diag}(\mathbf A\mathbf{\vec e}) $ 为 $ \mathbf A $ 各行之和构成的对角矩阵， $ \mathbf D_\text{col} = \text{diag}(\mathbf A^\top\mathbf{\vec e}) $ 为 $ \mathbf A $ 各列之和构成的对角矩阵， $ \mathbf{\vec e} $ 为全 1 的向量。

   当二部图是无向图时， $ \mathbf A = \mathbf A^\top $ （无向图的出边就是入边），则 $ \mathbf D_\text{row} = \mathbf D_\text{col} $ 。

2. 基于上述分析，接下来我们考虑 PTE 中的异质文本网络。假设单词集合为 $ \mathbb V $ ，文档集合为 $ \mathbb D $ ，标签集合为 $ \mathbb L $ ，我们将文本网络分为三个子网络：

   • word-word 子网 $ G^{w,w} $ ：每个 word 是一个顶点，边的权重为两个 word 在大小为 T 的窗口内共现的次数。假设其邻接矩阵为 $ \mathbf A^{w,w} $ ，定义 $ d_{i\cdot,}^{w,w} = \sum_j A_{i,j}^{w,w} $ 为 $ \mathbf A^{w,w} $ 第 $ i $ 行的元素之和， 定义 $ d_{\cdot,j}^{w,w} = \sum_i A_{i,j}^{w,w} $ 为 $ \mathbf A^{w,w} $ 第 $ j $ 列的元素之和。定义对角矩阵 $ \mathbf D_\text{row}^{w,w} = \text{diag}(d^{w,w}_{1,\cdot},\cdots,d^{w,w}_{|\mathbb V|,\cdot}) $ ， $ \mathbf D_\text{col}^{w,w} = \text{diag}(d^{w,w}_{\cdot,1},\cdots,d^{w,w}_{\cdot,|\mathbb V|}) $ ，它们分别由 $ \mathbf A^{w,w} $ 的各行之和、各列之和组成。
   • word-document 子网 $ G^{d,w} $ ：每个 word 和 document 都是一个顶点，边的权重是word 出现在文档中的次数。同样地我们定义对角矩阵 $ \mathbf D_\text{row}^{w,d} = \text{diag}(d^{w,d}_{1,\cdot},\cdots,d^{w,d}_{|\mathbb V|,\cdot}) $ ， $ \mathbf D_\text{col}^{w,d} = \text{diag}(d^{w,d}_{\cdot,1},\cdots,d^{w,d}_{\cdot,|\mathbb D|}) $ ，它们分别由 $ \mathbf A^{w,d} $ 的各行之和、各列之和组成。
   • word-label 子网 $ G^{w,l} $ ：每个 word 和 label 都是一个顶点，边的权重为 word 出现在属于这个 label 的文档的篇数。同样的我们定义对角矩阵 $ \mathbf D_\text{row}^{w,l} = \text{diag}(d^{w,l}_{1,\cdot},\cdots,d^{w,l}_{|\mathbb V|,\cdot}) $ ， $ \mathbf D_\text{col}^{w,l} = \text{diag}(d^{w,l}_{\cdot,1},\cdots,d^{w,l}_{\cdot,|\mathbb L|}) $ ，它们分别由 $ \mathbf A^{w,d} $ 的各行之和、各列之和组成。

   PTE 的损失函数为：

   $ \mathcal L = \alpha \mathcal L_{w,w} + \beta \mathcal L_{w,d} + \gamma\mathcal L_{w,l} = \\ \alpha \sum_{i=1}^{|\mathbb V|}\sum_{j=1}^{|\mathbb V|}\left(A_{i,j}^{w,w}\log\sigma\left(\mathbf{\vec x}_i^{w,w}\cdot \mathbf{\vec y}_j^{w,w}\right) + b \frac{d_{i,\cdot}^{w,w}d_{i,\cdot}^{w,w}}{\text{vol}_G^{w,w}}\log \sigma\left(\mathbf{-\vec x}_i^{w,w}\cdot \mathbf{\vec y}_j^{w,w}\right)\right)\\ + \beta \sum_{i=1}^{|\mathbb V|}\sum_{j=1}^{|\mathbb D|}\left(A_{i,j}^{w,d}\log\left(\sigma(\mathbf{\vec x}_i^{w,d}\cdot \mathbf{\vec y}_j^{w,d}\right) + b \frac{d_i^{w,d}d_j^{w,d}}{\text{vol}_G^{w,d}}\log \sigma\left(\mathbf{-\vec x}_i^{w,d}\cdot \mathbf{\vec y}_j^{w,d}\right)\right)\\ + \gamma \sum_{i=1}^{|\mathbb V|}\sum_{j=1}^{|\mathbb L|}\left(A_{i,j}^{w,l}\log\sigma\left(\mathbf{\vec x}_i^{w,l}\cdot \mathbf{\vec y}_j^{w,l}\right) + b \frac{d_i^{w,l}d_j^{w,l}}{\text{vol}_G^{w,l}}\log \sigma\left(\mathbf{-\vec x}_i^{w,l}\cdot \mathbf{\vec y}_j^{w,l}\right)\right) $

   其中 $ (\cdot)^{w,w},(\cdot)^{w,d},(\cdot)^{w,l} $ 分别为三个子网中的量， $ \alpha,\beta,\gamma $ 为三个超参数来平衡不同子网的损失， $ b $ 为负采样系数。根据 PTE 论文， $ \alpha,\beta,\gamma $ 需要满足： $ \alpha \text{vol}_{G_{w,w}} = \beta \text{vol}_{G_{w,d}} = \gamma \text{vol}_{G_{w,l}} $ ，这是因为PTE 在训练期间执行边采样，其中边是从三个子网中交替采样得到。

   根据前面的结论有：

   $ \mathbf{\vec x}_i^{w,w}\cdot \mathbf{\vec y}_j ^{w,w}= \log \left(\frac{\text{vol}_G^{w,w} A_{i,j}^{w,w}}{bd_i^{w,w}d_j^{w,w}}\right)\\ \mathbf{\vec x}_i^{w,d}\cdot \mathbf{\vec y}_j^{w,d} = \log \left(\frac{\text{vol}_G^{w,d} A_{i,j}^{w,d}}{bd_i^{w,d}d_j^{w,d}}\right)\\ \mathbf{\vec x}_i^{w,l}\cdot \mathbf{\vec y}_j ^{w,l} = \log \left(\frac{\text{vol}_G^{w,l} A_{i,j}^{w,l}}{bd_i^{w,l}d_j^{w,l}}\right) $

   令：

   $ \mathbf X = \begin{bmatrix} (\mathbf{\vec x}_1^{w,w})^\top& \mathbf 0&\mathbf 0\\ \vdots&\vdots&\vdots\\ (\mathbf{\vec x}_{|\mathbb V|}^{w,w})^\top& \mathbf 0&\mathbf 0\\ \mathbf 0&(\mathbf{\vec x}_1^{w,d})^\top&\mathbf 0\\ \vdots&\vdots&\vdots\\ \mathbf 0&(\mathbf{\vec x}_{|\mathbb V|}^{w,d})^\top&\mathbf 0\\ \mathbf 0&\mathbf 0&(\mathbf{\vec x}_1^{w,l})^\top\\ \vdots&\vdots&\vdots\\ \mathbf 0&\mathbf 0&(\mathbf{\vec x}_{|\mathbb V|}^{w,l})^\top \end{bmatrix}\quad \mathbf Y = \begin{bmatrix} (\mathbf{\vec y}_1^{w,w})^\top& \mathbf 0&\mathbf 0\\ \vdots&\vdots&\vdots\\ (\mathbf{\vec y}_{|\mathbb V|}^{w,w})^\top& \mathbf 0&\mathbf 0\\ \mathbf 0&(\mathbf{\vec y}_1^{w,d})^\top&\mathbf 0\\ \vdots&\vdots&\vdots\\ \mathbf 0&(\mathbf{\vec y}_{|\mathbb D|}^{w,d})^\top&\mathbf 0\\ \mathbf 0&\mathbf 0&(\mathbf{\vec y}_1^{w,l})^\top\\ \vdots&\vdots&\vdots\\ \mathbf 0&\mathbf 0&(\mathbf{\vec y}_{|\mathbb L|}^{w,l})^\top \end{bmatrix} $

   则有 $ \mathbf X \in \mathbb R^{3|\mathbb V|\times 3d},\mathbf Y \in \mathbb R^{(|\mathbb V|+|\mathbb D| +|\mathbb L|)\times 3d} $ ，且有：

   $ \mathbf M_1 = \alpha \text{vol}_{G_{w,w}}\mathbf (\mathbf D_{row}^{w,w})^{-1}\mathbf A^{w,w} (\mathbf D_{col}^{w,w})^{-1}\\ \mathbf M_2 = \beta\text{vol}_{G_{d,w}}\mathbf (\mathbf D_{row}^{d,w})^{-1}\mathbf A^{d,w} (\mathbf D_{col}^{d,w})^{-1}\\ \mathbf M_3 = \gamma \text{vol}_{G_{l,w}}\mathbf (\mathbf D_{row}^{l,w})^{-1}\mathbf A^{l,w} (\mathbf D_{col}^{l,w})^{-1}\\ \mathbf X\mathbf Y^\top = \log \left( \begin{bmatrix} \mathbf M_1&\mathbf 0 &\mathbf 0\\ \mathbf 0 & \mathbf M_2 &\mathbf 0\\ \mathbf 0&\mathbf 0&\mathbf M_3 \end{bmatrix} \right) - (\log b)\mathbf I $

   .

15.1.3 DeepWalk

1. DeepWalk 首先通过在图上执行随机游走来产生一个 corpus $ \mathcal D $ ，然后在 $ \mathcal D $ 上训练 SkipGram 模型。这里我们重点讨论带负采样的 SkipGram 模型skipgram with negative sampling:SGNS 。整体算法如下所示：

   • 输入：

     • 图 $ G(V,E,\mathbf A) $
     • 窗口大小 $ T $
     • 随机游走序列长度 $ L $
     • 总的随机游走序列数量 $ N $

   • 输出：顶点的 embedding 矩阵 $ \mathbf X $

   • 算法步骤：

     • 迭代： $ \text{for}\; s = 1,2,\cdots,N $ ，迭代过程为：

       • 根据先验概率分布 $ P(w) $ 随机选择一个初始顶点 $ w^{}_1 $ 。

       • 在图 $ G $ 上从初始顶点 $ w^{}_1 $ 开始随机游走，采样得到一条长度为 $ L $ 的顶点序列 $ (w_1^{},\cdots,w_L^{}) $ 。

       • 统计顶点共现关系。对于窗口位置 $ j=1,2,\cdots,L-T $ ：

         • 考虑窗口内第 $ r $ 个顶点 $ r=1,2,\cdots,T $ ：

           • 添加 vertex-context 顶点对 $ (w_j^{},w_{j+r}^{}) $ 到 $ \mathcal D $ 中。
           • 添加 vertex-context 顶点对 $ (w_{j+r} ^{},w_{j}^{}) $ 到 $ \mathcal D $ 中。

     • 然后在 $ \mathcal D $ 上执行负采样系数为 $ b $ 的 SGNS 。

2. 根据论文 《NeuralWord Embedding as Implicit Matrix Factorization》 ， SGNS 等价于隐式的矩阵分解：

   $ \mathbf X \mathbf Y^\top = \mathbf M\\ M_{w,c} = \log\left(\frac{n(w,c)\times |\mathcal D|}{n(w)\times n(c)}\right)-\log b $

   其中： $ |\mathcal D| $ 为语料库大小； $ n(w,c) $ 为语料库 $ \mathcal D $ 中vertex-context $ (w,c) $ 共现的次数； $ n(w) $ 为语料库中 vertex $ w $ 出现的总次数； $ n(c) $ 为语料库中 context $ c $ 出现的总次数； $ b $ 为负采样系数。

   这个矩阵 $ \mathbf M $ 刻画了图结构的什么属性？目前并没有相关的分析工作。此外，这里是否可以去掉 log、是否可以去掉 log b ，也没有理论的解释。

3. 接下来的分析依赖于一些关键的假设：

   • 假设图 $ G $ 为无向的undirected、连接的connected、non-bipartite 的，这使得 $ P(w) = d_w/\text{vol}_G $ 为一个平稳分布。
   • 假设每个随机游走序列的第一个顶点从这个平稳分布 $ P(w) $ 中随机选取。

   对于 $ r=1,2,\cdots,T $ ，定义：

   • $ \mathcal D_{r\rightarrow} = \{(w,c)\mid (w,c)\in \mathcal D, w = w_j^{},c = w_{j+r}^{}\} $ ，即 $ \mathcal D_{r\rightarrow} $ 为 $ \mathcal D $ 的子集，它的每个 context 顶点 $ c $ 都在每个 vertex 顶点 $ w $ 的右侧 $ r $ 步。另外定义 $ n(w,c)_{r\rightarrow} $ 为 $ \mathcal D_{r\rightarrow} $ 中vertex-context $ (w,c) $ 共现的次数。

   • $ \mathcal D_{r\leftarrow} = \{(w,c)\mid (w,c)\in \mathcal D, w = w_{j+r}^{},c = w_{j}^{}\} $ ， 即 $ \mathcal D_{r\rightarrow} $ 为 $ \mathcal D $ 的子集，它的每个 context 顶点 $ c $ 都在每个 vertex 顶点 $ w $ 的左侧 $ r $ 步。另外定义 $ n(w,c)_{r\leftarrow} $ 为 $ \mathcal D_{r\leftarrow} $ 中vertex-context $ (w,c) $ 共现的次数。

   • 定义 $ \mathbf P = \mathbf D^{-1}\mathbf A $ ， $ \mathbf P^r = \underbrace {\mathbf P\times \cdots \times \mathbf P}_r $ （ $ r $ 个 $ \mathbf P $ 相乘），其中对角矩阵 $ \mathbf D = \text{diag}(d_1,\cdots,d_{|V|}) $ ， $ d_w = \sum_{c}A_{w,c} $ ， $ \text{vol}_G=\sum_{w}\sum_{c}A_{w,c} $ 。定义 $ P^r_{w,c} $ 为 $ \mathbf P^r $ 的第 $ w $ 行、第 $ c $ 列。

     事实上 $ \mathbf P $ 定义了一个概率转移矩阵， $ P_{w,c} $ 定义了从顶点 $ w $ 经过一步转移到 $ c $ 的概率； $ P^r_{w,c} $ 定义了从顶点 $ w $ 经过 $ r $ 步转移到 $ c $ 的概率。

   另外考虑到对称性，我们有 $ \mathbf A= \mathbf A^{\top} $ 。

4. 定理一：定义，则当 $ L\rightarrow \infty $ 时有：

   $ \frac{n(w,c)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|}\stackrel{p}{\rightarrow } \frac{d_w}{\text{vol}_G}P^r_{w,c}\\ \frac{n(w,c)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|}\stackrel{p}{\rightarrow } \frac{d_c}{\text{vol}_G}P^r_{c,w} $

   其中： $ \stackrel{p}{\rightarrow} $ 表述依概率收敛。

   证明：

   首先介绍 S.N. Bernstein 大数定律：设 $ Y_1,Y_2,\cdots $ 为一个随机变量的序列，其中每个随机变量具有有限的期望 $ \mathbb E[Y_j]\lt K $ 和有限的方差 $ \text{Var} (Y_j) \lt K $ ，并且协方差满足：当 $ |i-j|\rightarrow \infty $ 时， $ \text{Cov}(Y_i,Y_j)\rightarrow 0 $ 。则大数定律 law of large numbers:LLN 成立。

   考虑只有一条随机游走序列（即 $ N=1 $ ）： $ (w_1,\cdots,w_L) $ 。给定一个 vertex-context $ (w,c) $ ，定义随机变量 $ Y_j,j=1,2,\cdots,L-T $ 为事件 $ w_j=w,w_{j+r} = c $ 发生的指示器 indicator 。

   我们观察到：

   • $ |\mathcal D_{r\rightarrow}| = L-T $ ， $ \sum_{j=1}^{L-T} Y_j = n(w,c)_{r\rightarrow} $ 。因此有：

     $ \frac{n(w,c)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|} = \frac{1}{L-T} \sum_{j=1}^{L-T} Y_j $

   • 基于我们对图的假设和随机游走的假设，则有： $ Y_j $ 发生的概率等于 $ w_j=w $ 的概率乘以 $ w $ 经过 $ r $ 步转移到 $ c $ 的概率。即：

     $ \mathbb E[Y_j] = P(Y_j) = \frac{d_w}{\text{vol}_G}\times P^r_{w, c} $

   • 基于我们对图的假设和随机游走的假设，则有：当 $ j\gt i+r $ 时有：

     $ \mathbb E[Y_iY_j] = P(w_i=w,w_{i+r}=c, w_j=w,w_{j+r} = c)\\ = \frac{d_w}{\text{vol}_G}P^r_{w,c}\times P^{j-i-r}_{c,w}\times P^r_{w,c} $

     其中：第一项为 $ w_i $ 采样到 $ w $ 的概率；第二项为从 $ w $ 经过 $ r $ 步转移到 $ c $ 的概率；第三项为从 $ c $ 经过 $ j-(r+i) $ 步转移到 $ w $ 得概率；第四项为从 $ w $ 经过 $ r $ 步转移到 $ c $ 的概率。

   则有：

   $ \text{Cov}(Y_i,Y_j) = \mathbb E[Y_iY_j] - \mathbb E[Y_i]\mathbb E[Y_j] = \frac{d_w}{\text{vol}_G}P^r_{w,c}\left[P^{j-i-r}_{c,w} -\frac{d_w}{\text{vol}_G}\right]P^{r}_{w,c} $

   当 $ |j-i|\rightarrow \infty $ 时，从 $ c $ 经过 $ \infty $ 步转移到 $ w $ 的概率收敛到它的平稳分布，即 $ p(w_j=w) $ 。即：

   $ \lim_{|j-i|\rightarrow\infty}P^{j-i-r}_{c,w} = \frac{d_w}{\text{vol}_G} $

   因此有 $ \lim_{|j- i|\rightarrow \infty} \text{Cov}(Y_i,Y_j) = 0 $ 。因此随机游走序列收敛到它的平稳分布。

   应用大数定律，则有：

   $ \frac{n(w,c)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|} = \frac{1}{L-T} \sum_{j=1}^{L-T} Y_j \stackrel{p}{\rightarrow} \frac{1}{L-T}\sum_{j=1}^{L-T} \mathbb E[Y_j] = \frac{d_w}{\text{vol}_G}P^r_{w,c} $

   类似地，我们有：

   $ \frac{n(w,c)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|} = \frac{d_c}{\text{vol}_G}P^r_{c,w} $

   当 $ N\gt 1 $ 时，我们定义 $ Y_j^{},s=1,2,\cdots,N,j=1,2,\cdots,L-T $ 为事件 $ w_j^{} = w, w_{j+r}^{(s)} = c $ 的指示器，同样可以证明相同的结论。

5. 事实上如果随机游走序列的初始顶点分布使用其它分布（如均匀分布），则可以证明：当 $ j\rightarrow \infty $ 时，有：

   $ \lim_{j\rightarrow\infty} P(w_j=w, w_{j+r} = c) = \frac{d_w}{\text{vol}_G}P^r_{w,c} $

   因此定理一仍然成立。

6. 定理二：当 $ L\rightarrow\infty $ 时，有：

   $ \frac{n(w,c)}{|\mathcal D|}\stackrel{p}{\rightarrow}\frac{1}{2T}\sum_{r=1}^T\left(\frac{d_w}{\text{vol}_G}P^r_{w,c} + \frac{d_c}{\text{vol}_G}P^r_{c,w}\right) $

   证明：

   注意到 $ \frac{|\mathcal D_{r\rightarrow}|}{|\mathcal D|}=\frac{|\mathcal D_{r\leftarrow}|}{|\mathcal D|} = \frac{1}{2T} $ ，应用定理一有：

   $ \frac{n(w,c)}{|\mathcal D|} = \frac{\sum_{r=1}^T(n(w,c)_{r\rightarrow} + n(w,c)_{r\leftarrow})}{\sum_{r=1}^T(|\mathcal D_{r\rightarrow}|+|\mathcal D_{r\leftarrow}|)} = \frac{1}{2T}\sum_{r=1}^T\left(\frac{n(w,c)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|} + \frac{n(w,c)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|} \right)\\ \stackrel{p}{\rightarrow}\frac{1}{2T}\sum_{r=1}^T\left(\frac{d_w}{\text{vol}_G}P^r_{w,c} + \frac{d_c}{\text{vol}_G}P^r_{c,w}\right) $

   进一步的，考察 $ w $ 的边际分布和 $ c $ 的边际分布，当 $ L\rightarrow \infty $ 时，我们有：

   $ \frac{n(w)}{|\mathcal D|} \stackrel{p}{\rightarrow} \frac{d_w}{\text{vol}_G},\quad \frac{n(c)}{|\mathcal D|} \stackrel{p}{\rightarrow} \frac{d_c}{\text{vol}_G} $

   当 $ r $ 不大时，单边的、间隔 $ r $ 的 vertex-context 数量是固定的，为全体 vertex-context 数量的 $ 1/(2T) $ 。

7. 定理三：在 DeepWalk 中，当 $ L\rightarrow \infty $ 时有：

   $ \frac{n(w,c)|\mathcal D|}{n(w)n(c)}\stackrel{p}{\rightarrow} \frac{\text{vol}_G}{2T}\left(\frac{1}{d_c}\sum_{i=1}^TP^r_{w,c} +\frac{1}{d_w}\sum_{i=1}^TP^r_{c,w} \right) $

   因此DeepWalk 等价于因子分解：

   $ \mathbf X \mathbf Y^{\top} = \log\left(\frac{\text{vol}_G}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1}\right)- (\log b)\mathbf I $

   证明：

   利用定理二和continous mapping theorem，有：

   $ \frac{n(w,c)|\mathcal D|}{n(w)n(c)} = \frac{\frac{n(w,c)}{|\mathcal D|}}{\frac{n(w)}{|\mathcal D|}\frac{n(c)}{|\mathcal D|}}\stackrel{p}{\rightarrow}\frac{\frac{1}{2T}\sum_{r=1}^T\left(\frac{d_w}{\text{vol}_G}P^r_{w,c} + \frac{d_c}{\text{vol}_G}P^r_{c,w}\right)}{\frac{d_w}{\text{vol}_G}\times \frac{d_c}{\text{vol}_G}}\\ = \frac{\text{vol}_G}{2T}\left(\frac{1}{d_c}\sum_{r=1}^T P^r_{w,c} +\frac{1}{d_w}\sum_{r=1}^T P^r_{c,w} \right) $

   写成矩阵的形式为：

   $ \frac{\text{vol}_G}{2T}\left(\sum_{r=1}^T\mathbf P^r\mathbf D^{-1}+\sum_{r=1}^T\mathbf D^{-1}(\mathbf P^r)^{\top}\right)\\ = \frac{\text{vol}_G}{2T}\left(\sum_{r=1}^T(\underbrace{\mathbf D^{-1}\mathbf A\times\cdots\times \mathbf D^{-1}\mathbf A}_r)\mathbf D^{-1}+\sum_{r=1}^T\mathbf D^{-1}(\underbrace{\mathbf A\mathbf D^{-1}\times \cdots\times \mathbf A\mathbf D^{-1}}_r) \right)\\ = \frac{\text{vol}_G}{T}\left(\sum_{r=1}^T(\underbrace{\mathbf D^{-1}\mathbf A\times\cdots\times \mathbf D^{-1}\mathbf A}_r)\mathbf D^{-1} \right) = \frac{\text{vol}_G}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $

8. 事实上我们发现，当 $ T=1 $ 时，DeepWalk 就成为了 LINE(2nd)， 因此 LINE(2nd) 是 DeepWalk 的一个特例。

15.1.4 node2vec

1. node2vec 是最近提出的 graph embedding 方法，其算法如下：

   • 输入：

     • 图 $ G(V,E,\mathbf A) $
     • 窗口大小 $ T $
     • 随机游走序列长度 $ L $
     • 总的随机游走序列数量 $ N $

   • 输出：顶点

   • 算法步骤：

     • 构建转移概率张量 $ \mathbf P\in \mathbb R^{|V| \times |V|\times |V|} $

     • 迭代： $ \text{for}\; s = 1,2,\cdots,N $ ，迭代过程为：

       • 根据先验概率分布 $ Q(w_1,w_2) $ 随机选择初始的两个顶点 $ (w^{}_1,w_2^{}) $ 。

       • 在图 $ G $ 上从初始顶点 $ w^{}_1,w^{}_2 $ 开始二阶随机游走，采样得到一条长度为 $ L $ 的顶点序列 $ (w_1^{},\cdots,w_L^{}) $ 。

       • 统计顶点共现关系。对于窗口位置 $ j=2,\cdots,L-T $ ：

         • 考虑窗口内第 $ r $ 个顶点 $ r=1,2,\cdots,T $ ：

           • 添加三元组 $ (w_j^{},w_{j+r}^{},w_{j-1}^{}) $ 到 $ \mathcal D $ 中。
           • 添加三元组 $ (w_{j+r} ^{},w_{j}^{},w_{j-1}^{}) $ 到 $ \mathcal D $ 中。

     • 然后在 $ \mathcal D^\prime=\{(w,c)\mid (w,c,u)\in \mathcal D \} $ 上执行负采样系数为 $ b $ 的 SGNS 。

     注意：这里为了方便分析，我们使用三元组 $ (w_j,w_{j+r},w_{j-1}) $ ，而不是vertex-context 二元组。

2. node2vec 的转移概率张量 $ \mathbf P $ 采取如下的方式定义：

   • 首先定义未归一化的概率：

     $ \hat P_{w,v,u} = \begin{cases} \frac 1p,& (u,v) \in E, (v,w) \in E, u=w\\ 1,&(u,v) \in E, (v,w) \in E, u\ne w,(w,u) \in E\\ \frac 1q,&(u,v)\in E, (v,w) \in E, u\ne w, (w,u)\notin E\\ 0,&\text{else} \end{cases} $

     其中 $ \hat P_{w,v,u} $ 表示在 $ w_{j-1}=u,w_j = v $ 的条件下， $ w_{j+1} = w $ 的概率。

   • 然后得到归一化的概率：

     $ P_{w,v,u} = P(w_{j+1}=w\mid w_j=v, w_{j-1} = u) = \frac{\hat P_{w,v,u}}{\sum_{u^\prime}\hat P_{w,v,u^\prime}} $

3. 类似 DeepWalk ，我们定义：

   $ \mathcal D_{r\rightarrow} = \{(w,c,u)\mid (w,c,u)\in \mathcal D, w_j^n = w, w_{j+r}^n = c, w_{j-1}^n = u\}\\ \mathcal D_{r\leftarrow} = \{(w,c,u)\mid (w,c,u)\in \mathcal D, w_{j+r}^n = w, w_{j}^n = c, w_{j-1}^n = u\} $

   这里 $ u $ 为previous 顶点。

   定义 $ n(w,c,u)_{\rightarrow} $ 为 $ (w,c,u) $ 出现在 $ \mathcal D_{r\rightarrow} $ 中出现的次数；定义 $ n(w,c,u)_{\leftarrow} $ 为 $ (w,c,u) $ 出现在 $ \mathcal D_{r\leftarrow} $ 中出现的次数。

   定义二阶随机游走序列的平稳分布为 $ \mathbf Q $ ，它满足： $ \sum_{u} P_{w,v,u}Q_{v,u} = Q_{w,v} $ 。根据 Perron-Frobenius 定理，这个平稳分布一定存在。为了便于讨论，我们定义每个随机游走序列的初始两个顶点服从平稳分布 $ \mathbf Q $ 。

   定义高阶转移概率矩阵 $ P^r_{w,v,u} = P(w_{j+r}=w\mid w_j=v,w_{j-1}=u) $ 。

   由于篇幅有限，这里给出 node2vec 的主要结论，其证明过程类似 DeepWalk ：

   $ \frac{n(w,c,u)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|}\stackrel{p}{\rightarrow } Q_{w,u}P^r_{c,w,u},\quad \frac{n(w,c,u)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|}\stackrel{p}{\rightarrow } Q_{c,u}P^r_{w,c,u}\\ \frac{n(w,c)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|}=\frac{\sum_u n(w,c,u)_{r\rightarrow}}{|\mathcal D_{r\rightarrow}|}\stackrel{p}{\rightarrow } \sum_{u} Q_{w,u}P^r_{c,w,u}\\ \frac{n(w,c)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|}=\frac{\sum_u n(w,c,u)_{r\leftarrow}}{|\mathcal D_{r\leftarrow}|}\stackrel{p}{\rightarrow } \sum_u Q_{c,u}P^r_{w,c,u}\\ \frac{n(w,c)}{|\mathcal D|}\stackrel{p}{\rightarrow } \frac{1}{2T}\sum_{r=1}^T \left(\sum_u Q_{w,u}P^r_{c,w,u} + \sum_u Q_{c,u}P^r_{w,c,u}\right)\\ \frac{n(w)}{|\mathcal D|} \stackrel{p}{\rightarrow } \sum_u Q_{w,u},\quad \frac{n(c)}{|\mathcal D|} \stackrel{p}{\rightarrow } \sum_u Q_{c,u} $

   因此 node2vec 有：

   $ \frac{n(w,c)\times |\mathcal D|}{n(w)\times n(c)}\stackrel{p}{\rightarrow } \frac{\frac{1}{2T}\sum_{r=1}^T \left(\sum_u Q_{w,u}P^r_{c,w,u} + \sum_u Q_{c,u}P^r_{w,c,u}\right)}{ \left(\sum_u Q_{w,u}\right)\times \left(\sum_u Q_{c,u}\right)} $

   尽管实现了 node2vec 的封闭形式，我们将其矩阵形式的公式留待以后研究。

4. 注意：存储和计算转移概率张量 $ \mathbf P^r $ 以及对应的平稳分布代价非常高，使得我们难以对完整的二阶随机游走动力学过程建模。但是最近的一些研究试图通过对 $ \mathbf Q $ 进行低秩分解来降低时间复杂度和空间复杂度：

   $ Q_{u,v} = \mathbf{\vec q}_u\cdot \mathbf{\vec q}_v $

   由于篇幅限制，我们这里主要集中在一阶随机游走框架DeepWalk 上。

15.1.5 NetMF

1. 根据前面的分析我们将 LINE,PTE,DeepWalk,node2vec 都统一到矩阵分解框架中。这里我们主要研究 DeepWalk 矩阵分解，因为它比 LINE 更通用、比 node2vec 计算效率更高。

2. 首先我们引用了四个额外的定理：

   • 定理四：定义归一化的图拉普拉斯矩阵为 $ \mathbf L = \mathbf I - \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2} $ ，则它的特征值都是实数。

     而且，假设它的特征值从大到小排列 ，则有：

     $ 2\ge\lambda_1\ge\lambda_2\ge \cdots\ge\lambda_n = 0 $

     进一步的，假设该图是连通图 （connected），并且顶点数量 $ n\gt 1 $ ，则有： $ \lambda_1\ge \frac{n}{n-1} $ 。

     证明参考：《Spectral graph theory》。

   • 定理五：实对称矩阵的奇异值就是该矩阵特征值的绝对值。

     证明参考：《Numerical linear algebra》。

   • 定理六：假设 $ \mathbf B\in \mathbb R^{n\times n} ,\mathbf C \in \mathbb R^{n\times n} $ 为两个对称矩阵，假设将 $ \mathbf B,\mathbf C,\mathbf {BC} $ 的奇异值按照降序排列，则对于任意 $ 1\le i,j\le n,i+j\le n+1 $ ，以下不等式成立：

     $ \sigma_{i+j-1}(\mathbf B\mathbf C) \le \sigma_i(\mathbf B)\times \sigma_j(\mathbf C) $

     其中 $ \sigma_i(\cdot) $ 为对应矩阵的奇异值根据降序排列之后的第 $ i $ 个奇异值。

     证明参考：《Topics in Matrix Analysis》。

   • 定理七：给定一个实对称矩阵 $ \mathbf A $ ，定义它的瑞利商为：

     $ R(\mathbf A,\mathbf{\vec x}) = \frac{\mathbf{\vec x}^\top \mathbf A \mathbf{\vec x} }{\mathbf{\vec x}^\top \mathbf{\vec x}} $

     假设 $ \mathbf A $ 的特征值从大到小排列为 $ \lambda_1\ge\cdots\ge\lambda_n $ ，则有：

     $ \lambda_n = \min_{\mathbf{\vec x}\ne \mathbf{\vec 0}} R(\mathbf A,\mathbf{\vec x}),\quad \lambda_1 = \max_{\mathbf{\vec x}\ne \mathbf{\vec 0}} R(\mathbf A,\mathbf{\vec x}) $

     证明参考：《Numerical linear algebra》。

3. 考察 DeepWalk 的矩阵分解：

   $ \mathbf X \mathbf Y^{\top} = \log\left(\frac{\text{vol}_G}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1}\right)- (\log b)\mathbf I $

   忽略常量以及 element-wise 的 log 函数，我们关注于矩阵： $ \frac{1}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $ 。

   实对称矩阵 $ \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} = \mathbf I - \mathbf L $ 存在特征值分解 $ \mathbf U\mathbf\Lambda \mathbf U^\top $ ，其中 $ \mathbf U $ 为正交矩阵、 $ \mathbf\Lambda=\text{diag}(\lambda_1,\cdots,\lambda_n) $ 为特征值从大到小构成的对角矩阵。根据定理四可知， $ 1=\lambda_1\ge \lambda_2\cdots\ge\lambda_n\ge -1 $ ，并且 $ \lambda_n\lt -\frac{1}{n-1}\lt0 $ 。

   考虑到 $ \mathbf P = \mathbf D^{-1}\mathbf A= \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ ，因此有：

   $ \frac{1}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} = \left(\mathbf D^{-1/2}\right)\left(\mathbf U\left(\frac{1}{T}\sum_{r=1}^T \mathbf\Lambda^r\right) \mathbf U^\top\right)\left(\mathbf D^{-1/2}\right) $

   • 我们首先分析 $ \mathbf U\left(\frac{1}{T}\sum_{r=1}^T \mathbf\Lambda^r\right) \mathbf U^\top $ 的谱。显然，它具有特征值：

     $ \left\{\frac 1T \sum_{r=1}^T \lambda_1^r,\; \frac 1T \sum_{r=1}^T \lambda_2^r,\;\cdots,\;\frac 1T \sum_{r=1}^T \lambda_i^r,\;\cdots\;\frac 1T \sum_{r=1}^T \lambda_n^r\right\} $

     这可以视为对 $ \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 的特征值 $ \lambda_i $ 进行一个映射 $ f(x) = \frac 1T\sum_{r=1}^T x^r $ 。这个映射可以视为一个滤波器，滤波器的效果如下图所示。可以看到：

     • 滤波器倾向于保留正的、大的特征值。
     • 随着窗口大小 $ T $ 的增加，这种偏好变得更加明显。

     即：随着 $ T $ 的增加，滤波器尝试通过保留较大的、正的特征值来近似低阶半正定矩阵。

     

   • 然后我们分析 $ \frac{1}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $ 的谱。

     根据定理五，矩阵 $ \mathbf U\left(\frac{1}{T}\sum_{r=1}^T \mathbf\Lambda^r\right) \mathbf U^\top $ 的奇异值可以根据其特征值的绝对值得到。我们将 $ |\frac 1T \sum_{r=1}^T \lambda_i^r|,i=1,2,\cdots,n $ 进行降序排列，假设排列的顺序为 $ \{p_1,p_2,\cdots,p_n\} $ ，则有：

     $ \left|\frac 1T \sum_{r=1}^T \lambda_{p_1}^r\right|\ge \left|\frac 1T \sum_{r=1}^T \lambda_{p_2}^r\right|\ge\cdots\ge \left|\frac 1T \sum_{r=1}^T \lambda_{p_n}^r\right| $

     考虑到每个 $ d_i $ 都是正数，因此我们可以将 $ \mathbf D^{-1/2} $ 的奇异值根据特征值 $ \frac{1}{\sqrt d_i} $ 降序排列。假设排列的顺序为 $ \{q_1,q_2,\cdots,q_n\} $ ，则有：

     $ \frac{1}{\sqrt{d_{q_1}}}\ge \frac{1}{\sqrt{d_{q_2}}}\ge\cdots\ge\frac{1}{\sqrt{d_{q_n}}} $

     特别的， $ d_{q_1} = d_{\min} $ 为最小的 degree 。

     通过应用两次定理六，我们可以发现第 $ s $ 个奇异值满足：

     $ \sigma_s\left(\left(\frac{1}{T}\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1}\right)\le \sigma_1(\mathbf D^{-1/2})\sigma_s\left(\mathbf U\left(\frac 1T\sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top\right)\sigma_1(\mathbf D^{-1/2})\\ = \frac{1}{\sqrt{d_{q_1}}}\left|\frac 1T \sum_{r=1}^T\lambda_{p_s}^r\right| \frac{1}{\sqrt{d_{q_1}}} = \frac{1}{d_{\min}}\left|\frac 1T \sum_{r=1}^T\lambda_{p_s}^r\right| $

     因此 $ \frac{1}{T}\left(\sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $ 的第 $ s $ 个奇异值的上界为 $ \frac{1}{d_{\min}}\left|\frac 1T \sum_{r=1}^T\lambda_{p_s}^r\right| $ 。

     另外，根据瑞利商，我们有：

     $ R\left(\left(\frac 1T\sum_{r=1}^T\mathbf P^r\right)\mathbf D^{-1},\mathbf{\vec x}\right) = R\left(\mathbf U\left(\frac 1T\sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top, \mathbf D^{-1/2} \mathbf{\vec x}\right) R(\mathbf D^{-1},\mathbf{\vec x})\\ \ge \lambda_{\min}\left(\mathbf U\left(\frac 1T \sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top\right)\lambda_{\min}(\mathbf D^{-1})\\ = \frac {1}{d_\min}\lambda_{\min}\left(\mathbf U \left(\frac 1T\sum_{r=1}^T\mathbf\Lambda^r\right)\mathbf U^\top\right) $

     应用定理七，我们有：

     $ \lambda_{\min}\left(\left(\frac 1T \sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1}\right) \ge \frac{1}{d_\min}\lambda_\min \left(\mathbf U\left(\frac 1T\sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top\right) $

4. 为了说明滤波器 $ f(x) = \frac 1T\sum_{r=1}^T x^r $ 的效果，我们分析了 Cora 数据集对应的引文网络。我们将引文链接视为无向边，并选择最大连通分量 largest connected component 。我们分别给出了 $ \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2} $ 、 $ \mathbf U\left(\frac {1}{T} \sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top $ 以及 $ \left(\frac 1T \sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $ 按照降序排列的特征值，其中 $ T=10 $ 。

   • 对于 $ \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2} $ ，最大的特征值为 $ \lambda_1= 1 $ ，最小特征值为 $ \lambda_n = -0.971 $ 。

   • 对于 $ \mathbf U\left(\frac {1}{T} \sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top $ ，我们发现：它的所有负特征值以及一些小的正特征值都被过滤掉了 filtered out 。

   • 对于 $ \left(\frac 1T \sum_{r=1}^T \mathbf P^r\right)\mathbf D^{-1} $ ，我们发现：

     • 它的奇异值（即特征值的绝对值）被 $ \mathbf U\left(\frac {1}{T} \sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top $ 的奇异值所限制 bounded 。
     • 它的最小特征值的被 $ \mathbf U\left(\frac {1}{T} \sum_{r=1}^T \mathbf\Lambda^r\right)\mathbf U^\top $ 的特征值所限制 bounded 。

   

5. 基于前面的理论分析，我们提出了一个矩阵分解框架 NetMF ，它是对 DeepWalk 和 LINE 的改进。

   为表述方便，我们定义：

   $ \mathbf M = \frac{\text{vol}_G}{bT}\left(\sum_{r=1}^T\mathbf P^r\right) \mathbf D^{-1} $

   因此 $ \mathbf X \mathbf Y^\top = \log \mathbf M $ 对应于 DeepWalk 的矩阵分解。

   • 对于很小的 $ T $ ，我们直接计算 $ \mathbf M $ 并对 $ \log \mathbf M $ 进行矩阵分解。考虑到直接对 $ \log \mathbf M $ 进行矩阵分分解难度很大，有两个原因：当 $ M_{i,j} = 0 $ 时 $ \log M_{i,j} $ 的行为未定义； $ \log \mathbf M $ 是一个巨大的稠密矩阵，计算复杂度太高。

     受到 Shifted PPMI 启发，我们定义 $ \mathbf M^\prime = \max(\mathbf M,1) $ 。这使得 $ \log \mathbf M^\prime $ 中每个元素都是有效的，并且 $ \log \mathbf M^\prime $ 是稀疏矩阵。然后我们对 $ \log \mathbf M^\prime $ 进行奇异值分解，并使用它的 top $ d $ 奇异值和奇异向量来构造embedding 向量。

   • 对于很大的 $ T $ ，直接计算 $ \mathbf M $ 的代价太高。我们提出一个近似算法，主要思路是：根据 $ \mathbf M $ 和归一化拉普拉斯矩阵之间的关系来近似 $ \mathbf M $ 。

     • 首先我们对 $ \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 进行特征值分解，通过它的 top $ h $ 个特征值和特征向量 $ \mathbf U_h\mathbf\Lambda_h\mathbf U_h^{\top} $ 来逼近 $ \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 。由于只有 top $ h $ 个特征值被使用，并且涉及的矩阵是稀疏的，因此我们可以使用 Arnoldi 方法来大大减少时间。

       大型稠密矩阵的特征值分解的代价太高，实际是不可行的。

     • 然后我们通过 $ \hat {\mathbf M} = \frac{\text{vol}_G}{b }\mathbf D ^{-1/2}\mathbf U_h\left(\frac 1T\sum_{r=1}^T\mathbf \Lambda_h^r\right) \mathbf U_h^\top\mathbf D^{-1/2} $ 来逼近 $ \mathbf M $ 。

6. NetMF 算法：

   • 输入：

     • 图 $ G(V,E,\mathbf A) $
     • 窗口大小 $ T $

   • 输出：顶点的 embedding 矩阵 $ \mathbf X $

   • 算法步骤：

     • 如果 $ T $ 较小，则计算：

       $ \mathbf P^1,\cdots,\mathbf P^T\\ \mathbf M = \frac{\text{vol}_G}{bT}\left(\sum_{r=1}^T\mathbf P^r\right) \mathbf D^{-1}\\ \mathbf M^\prime = \max (\mathbf M,1) $

       如果 $ T $ 较大，则执行特征值分解： $ \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2} \simeq \mathbf U_h\mathbf\Lambda_h\mathbf U_h^\top $ 。然后计算：

       $ \hat {\mathbf M} = \frac{\text{vol}_G}{b }\mathbf D ^{-1/2}\mathbf U_h\left(\frac 1T\sum_{r=1}^T\mathbf \Lambda_h^r\right) \mathbf U_h^\top\mathbf D^{-1/2}\\ \hat{\mathbf M}^\prime = \max (\hat{\mathbf M},1) $

     • 执行 $ d $ 维的 SVD 分解： $ \log \mathbf M^\prime = \mathbf U_d \Sigma_d \mathbf V_d^\top $ 或者 $ \log \hat{\mathbf M}^\prime = \mathbf U_d \Sigma_d \mathbf V_d^\top $ 。

     • 返回 $ \mathbf U_d\sqrt\Sigma_d $ 作为网络 embedding。

7. 对于较大的 $ T $ ，可以证明 $ \hat{\mathbf M} $ 逼近 $ \mathbf M $ 的误差上界，也可以证明 $ \log \hat{\mathbf M}^\prime $ 逼近 $ \log \mathbf M^\prime $ 的误差上界。

   定理八：令 $ ||\cdot||_F $ 为矩阵的 Frobenius 范数，则有：

   $ \left\|\mathbf M - \hat{\mathbf M}\right\|_F \le \frac{\text{vol}_G}{bd_\min}\sqrt{\sum_{j=k+1}^n \left|\frac 1T\sum_{r=1}^T \lambda_j^r\right|}\\ \left\|\log \mathbf M^\prime - \log \hat{\mathbf M}^\prime\right\|_F \le \left\|\mathbf M^\prime - \hat{\mathbf M}^\prime\right\|_F \le \left\|\mathbf M - \hat{\mathbf M}\right\|_F $

   证明：

   • 第一个不等式：可以通过 F 范数的定义和前面的定理七来证明。

   • 第二个不等式：不失一般性我们假设 $ M^\prime_{i,j}\le \hat M_{i,j}^\prime $ ，则有：

     $ \left|\log M_{i,j}^\prime -\log \hat M_{i,j}^\prime \right| = \log \left(1+ \frac{\hat M^\prime_{i,j} - M^\prime_{i,j}}{M^\prime_{i,j}}\right)\\ \le \frac{\hat M^\prime_{i,j} - M^\prime_{i,j}}{M^\prime_{i,j}} \le \hat M^\prime_{i,j} - M^\prime_{i,j} = \left|\hat M^\prime_{i,j} - M^\prime_{i,j}\right| $

     第一步成立是因为： 对于 $ x\ge 0 $ 有 $ \log (1+x)\le x $ ；第二步成立是因为： $ M_{i,j}^\prime = \max(M_{i,j},1) \ge 1 $ 。因此有 $ \left\|\log \mathbf M^\prime - \log \hat{\mathbf M}^\prime\right\|_F \le \left\|\mathbf M^\prime - \hat{\mathbf M}^\prime\right\|_F $ 。

     另外，根据 $ \mathbf M^\prime $ 和 $ \hat{\mathbf M}^\prime $ 的定义有：

     $ \left|M_{i,j}^\prime - \hat M_{i,j}^\prime\right| = \left|\max(M_{i,j},1) - \max(\hat M_{i,j},1)\right|\le \left|M_{i,j} - \hat M_{i,j}\right| $

     因此有： $ \left\|\mathbf M^\prime - \hat{\mathbf M}^\prime\right\|_F \le \left\|\mathbf M - \hat{\mathbf M}\right\|_F $ 。

15.2 实验

1. 这里我们在在多标签顶点分类任务中评估 NetMF 的性能，该任务也被 DeepWalk, LINE, node2vec 等工作所采用。

2. 数据集：

   • BlogCatalog 数据集：在线博主的社交关系网络，标签代表博主的兴趣。
   • Flickr 数据集：Flickr网站用户之间的关系网络，标签代表用户的兴趣组，如“黑白照片”。
   • Protein-Protein Interactions:PPI：智人 PPI 网络的子集，标签代表标志基因组和代表的生物状态。
   • Wikipedia 数据集：来自维基百科，包含了英文维基百科 dump 文件的前一百万个字节中的单词共现网络。顶点的标签表示通过Stanford POS-Tagger推断出来的单词词性Part-of-Speech:POS 。

   这些数据集的统计信息如下表所示。

   

3. Baseline 模型和配置：我们将 NetMF(T=1)、NetMF(T=10) 和 LINE(2nd), DeepWalk 进行比较。

   • 所有模型的 embedding 维度都是 128 维。
   • 对于 NetMF(T=10) ，我们在 Flickr 数据集上选择 $ h=16384 $ ，在其它数据集上选择 $ h=256 $ 。
   • 对于 DeepWalk ，我们选择窗口大小为 10、随机游走序列长度 40、每个顶点开始的随机游走序列数量为 80 。

   我们重点将 NetMF(T=1) 和 LINE(2nd) 进行比较，因为二者窗口大小都为 1 ；重点将 NetMF(T=10) 和 DeepWalk 进行比较，因为二者窗口大小都为 10 。

4. 和 DeepWalk 相同的实验步骤，我们首先训练整个网络的 embedding，然后随机采样一部分标记样本来训练一个one-vs-rest 逻辑回归分类模型，剩余的顶点作为测试集。在测试阶段，one-vs-rest 模型给出 label 的排名，而不是最终的 label 分配。为了避免阈值效应，我们假设测试集的 label 数量是给定的。

   对于 BlogCatalog,PPI,Wikipedia 数据集，我们考察分类训练集占比 10%~90% 的情况下，各模型的性能；对于 Flickr 数据集，我们考察分类训练集占比 1%~10% 的情况下，各模型的性能。我们评估测试集的 Micro-F1 指标和 Macro-F1 指标。为了确保实验结果可靠，每个配置我们都重复实验 10 次，并报告测试集指标的均值。

   完成的实验结果如下图所示。可以看到：NetMF(T=1) 相对于 LINE(2nd) 取得了性能的提升（它们的上下文窗口 T=1 ），NetMF(T=10) 相对于 DeepWalk 也取得了性能提升（它们的上下文窗口 T=10 ）。

   • 在 BlogCatalog,PPI,Flickr 数据集中，我们提出的 NetMF(T=10) 比 Baseline 性能更好。这证明了我们提出的理论基础在 network embedding 的有效性。

   • 在 Wikipedia 数据集中，窗口更小的 NetMF(T=1) 和 LINE(2nd) 效果更好。这表明：短期依赖足以建模 Wikipedia 网络结构。这是因为 Wikipedia 网络是一个平均 degree 为 77.11 的稠密的单词共现网络，大量单词之间存在共现关系。

   • 如下表所示，大多数情况下当标记数据稀疏时，NetMF 方法远远优于 DeepWalk 和 LINE 。

   • DeepWalk 尝试通过随机游走采样，从而用经验分布来逼近真实的 vertex-context 分布。尽管大数定律可以保证这种方式的收敛性，但是实际上由于真实世界网络规模较大，而且实际随机游走的规模有限（随机游走序列的长度、随机游走序列的数量），因此经验分布和真实分布之间存在gap ，从而对 DeepWalk 的性能产生不利影响。

     NetMF 通过直接建模真实的 vertex-context 分布，从而得到比DeepWalk更好的效果。