丁香园 | 图表示学习 实践与思考

丁香园大数据 NLP

引言

结合了表示学习和深度学习的图模型已经成为近些年人气最高的研究方向之一，然而令其服务于应用场景并不简单，即便线上业务能产生大量数据，如何根据数据构建符合需求的图结构依然是强业务相关，难以总结通用经验的问题。在这方面，医疗信息行业有先天优势，首先从医学文献资料中就可以获取可靠的半结构化数据（就如众所周知的医疗知识图谱）此外医疗从业者的工作经验也能为我们构建图结构数据提供宝贵的先验知识。此前丁香园团队花费了大量时间精力构建图谱，同时也与医疗工作者配合，积累经验整合医疗知识，现在希望能通过图表示学习，充分发挥结构化半结构化医疗数据的潜力。

此前的文章中，笔者也介绍过以 DeepWalk 为代表的 skip-gram 模型，以及清华唐杰老师团队发表的 ProNE，不过受当时认知所限，并未发觉两类方法之间的关系，本文将通过唐杰老师团队的其他工作来展示 skip-gram 模型和**矩阵分解(matrix factorization)**的关联，并讨论实践过程中与图构建和重构图表示向量有关的问题。

skip-gram 模型其实也是矩阵分解

以 DeepWalk 为代表的基于 skip-gram 的表示模型，包括 Line 和 node2vec，基本都能归纳为上下文采样后套用 word2vec 的学习模式；这类方法操作简单，大规模图数据也有对应分布式实现，且经过工业界多年验证，属于性价比极高的应用落地基线方法（如果某种追求指标的新方法不能明显超越它们，那么对应的改进思路可能就需要重新考量）。而基于矩阵分解的表示模型算是另一大类，不同于 skip-gram 可以逐步采样训练，矩阵分解需要加载整个邻接图，分布式也相对复杂，现今常见的优化思路主要是寻找可表达或近似邻接图的稀疏矩阵，并匹配基于稀疏矩阵的分解算法，例如之前介绍过的 ProNE。

虽然 skip-gram 和 matrix factorization 普遍被视为两类方法，但清华唐杰老师团队通过数学分析，告诉我们基于 skip-gram 的表示模型本质上也是在做矩阵分解，并尝试用矩阵分解来近似和提升 skip-gram 模型。

《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec 》

本篇的论述过程非常精彩，在第二节中分别将 LINE, PTE, DeepWalk, node2vec 这四个常见的 skip-gram 模型转换为下图中的矩阵分解形式，笔者能力有限，这里仅通过简要展示 LINE 和 DeepWalk 的推导来展示 skip-gram 模型到矩阵分解的跨越，PTE 可视为 LINE 的特例，node2vec 沿用了 DeepWalk 的思路，感兴趣的读者可自行翻阅原文学习。

1. LINE

我们知道，LINE(二阶)可以视作替换了滑动窗口的 word2vec，因此二者的损失函数形式相同，从 skip-gram 到 matrix factorization 的变换就从损失函数开始

根据 LINE 中作者的建议，对节点 j 的负采样可正比于节点度数 d 的 0.75 次方，下面的公式里简化为正比于 d，可以将损失函数改写为

注意上式负采样中的均值部分，显然 log 函数的概率可以用邻接图中对应节点的度表示，即

根据(1)和(2)，损失函数的每一项 loss(i, j)可写为

训练 LINE 就是最大化损失函数，所以用 zi,j 表示向量 xy 内积，对上式求导取导数为 0 可得

上式只存在一个基本可由图表示有效解

显然，将上面的解写为矩阵形式后，LINE 要学习的两个 Embedding 参数 X 和 Y 就表现为 matrix factorization 的形式

2. DeepWalk

将 skip-gram 转换为 matrix factorization 基本都是由损失函数出发，LINE 非常贴近 word2vec 因此过程也相对容易，DeepWalk 还有随机游走采样步骤，所以对应的推导也需要涵盖这一过程，下面的 Skip-gram with Negative Sampling(SGNS)引用了《Neural Word Embedding as Implicit Matrix Factorization》（讨论 word embedding 与 matrix factorization 的关系）中给出的损失函数形式，下面对 DeepWalk 的推导基于该形式，其中矩阵 D 为特定采样产生的图，(w)表示出现频率

要基于上式表达 DeepWalk，明显需要用邻接图 D 和词频率表示随机游走过程，这里作者将 D 划分为多个子图，每个子图代表窗口大小为 r 时的采样结果，由于是无向图，(w, c)共现需要考虑前向和后向两部分

现在，基于上述表示，以及三条 Theorem（证明过程请阅读原文），结合 DeepWalk 随机游走的 SGNG 损失函数可以转换为矩阵分解形式

• Theorem 2.1：用图的形式来表述子图 Dr 下#(w, c)的共现频率（L 为游走步长）

• Theorem 2.2：说明当步长 L 趋于无穷时，基于完整图 D 的共现频率可用子图共现频率的和表示（T 为最大窗口）
  
• Theorem 2.3：基于 Theorem2.1 和 2.2，SGNS 损失函数很容易用矩阵求和的形式表达

最终，将 Theorem2.3 改写为矩阵形式即可得（不难看出，LINE 就是当 T=1 时的 DeepWalk）

3. 矩阵分解框架 NetMF

• 本文地址：丁香园 | 图表示学习 实践与思考
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

文章 3.1 小节对矩阵分解形式的 DeepWalk 做谱分析，揭示了 DeepWalk 与 Graph Laplacian 的关系，并给出有关特征值的性质和界，这里不再赘述，直接来到作者提出的框架（基于公式(3)右式），将待分解矩阵记为 M，即：

• 小窗口 T

较小的窗口 T 对应较低的运算量，此时应用 NetMF 不必考虑对 M 近似，对应原文的算法 3，先计算每个窗口下的 P，代入计算出 M，最后应用奇异值分解；此处第 3 步的 M'=max(M, 1) 是为了消除 log(0) 的情况，同时 log(1) = 0 也能让矩阵稠密程度降低

• 大窗口 T

窗口尺寸 T 上升会令计算复杂度显著提高，因此作者提出先用特征分解，取 top-h 的特征对作为 M 的近似，提升 M 的稀疏程度

至此便是本篇的主体内容，将应用多年的 skip-gram 模型统一为矩阵分解，意味着我们有机会应用更多图算法去改进 skip-gram，同一个团队在第二年就展示了应用图稀疏化方法提升框架性能的工作 NetSMF。

《NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization》

NetMF 慢主要还是因为输入矩阵 M 不够稀疏，本文利用图谱稀疏化技术（graph sparsification technique）构造 M 的稀疏近似矩阵，并用随机奇异值分解（RSVD）生成稀疏图的对应 Embedding，为了与本文的符号一致，这里重新给出 DeepWalk 的矩阵分解形式以及 M 在本文里的表示

显然图谱稀疏化是本文的核心，思路是基于原图的连接关系，重新采样生成新的边和边权重，下面的算法 1 是 NetSMF 的整体流程（这里跳过了图谱相似的定义以及随机游走多项式的谱稀疏性定理，他们共同说明了在特定复杂度内构造的图与原图的谱相似程度，感兴趣的读者可参阅原文 3.1 节）

其中第 5 步对应边采样算法（算法 2）：根据真实挑选的边 e=(u, v)，在 u 和 v 的特定范围邻居中采样新的节点(u0, ur)作为新边，并通过新边间通路长度算得新边权重

第 10 步的 RSVD 分解会将原输入矩阵映射到低维空间，这将进一步提升整体框架运算效率；此外，作者还分析了 NetSMF 的并行化能力，并描述了边采样，稀疏矩阵构造，RSVD 三个关键部分的并行实现思路；文中的效率实验表明 NetSMF 对比 DeepWalk 和 NetMF 有大幅提升。

不过这还不够，如今工业界应用图表示的场景恐怕都是千万节点起步，ProNE 继续沿着 NetMF 的思路，在 matrix factorization 的框架上找到了更快更巧妙的技术，特别是第二部分，对分解产生的 Embedding 做谱传播，图傅立叶变换会将输入投影到谱空间，投影过程中拉普拉斯矩阵的特征值会缩放输入矩阵，并且该特征值与输入图矩阵本身的内聚程度有关，因此在谱传播过程中，第一部分对图表示向量将依特征值大小被传播到更局部或全局部分。

应用图表示学习时的障碍

笔者之前对医疗文本中的实体词和内部医学知识词库做原子词表示时用了 ProNE，结果都很不错，然而将相似的思路应用到其他文本数据时结果很糟糕，举个例子：麻疹和荨麻疹其实是两种病，但多数人其实分不清它们，医学科普文章又经常将二者放在一起比较，所以滑动窗口采样出的上下文非常接近，笔者考虑把 word2vec 的滑动窗口视为边采样，再结合原子词表示的实体边采样方式，由二者共同构成词表的邻接矩阵，希望这样学习到的词向量表示有更强的实体倾向性（例如二者的传染源不同，临床症状不同）。

我们猜测，如果词表构成内聚程度强，或数据本身就存在结构化/半结构化结构，对应图的表意就会相对明确，自然用简单的构图策略就可以产生符合期望的图，而对更泛的语料，大量平凡用语产生的上下文会淡化重点词汇间的关系，这样简单的构图策略就无法表达我们的目标意图；所以，应该设计更复杂的构图策略，并为图结构赋予更复杂的信息，GNN 在推荐系统等场景中发展出的异质网络就是很好的学习对象，来自阿里和唐杰老师团队的 GATNE 就融合了不同类型的边，以求学习复杂场景下的表示向量。

《Representation Learning for Attributed Multiplex Heterogeneous Network》

虽说是更复杂的图结构，但 GATNE 的思路非常直观，如下图所示，除了常规通过节点邻接关系学习到的 Base Embedding，节点间的边可能蕴含不同的属性，因此完整的图结构是由不同类别的边连接而成的子图之和，这里需要学习各类边的 Edge Embedding，每个节点最终的向量表示就是对应 Edge 和 Base 表示的组合，因为线性组合无法体现节点之间及不同类边的影响，因而在 concat 操作后还会用注意力机制为不同表示加权

本文还分别讨论了 Transductive 和 Inductive 两种情况（对应 GATNE-T 和 GATNE-I）；无疑 Transductive 更简单，重点放在 Edge 表示学习即可，对应操作就是以特定类别的边产生的邻居的聚合作为该节点对应此类边的表示向量；而 GATNE-I 需要考虑新数据加入，Base 向量就借用 GraphSAGE 的邻居聚合思想，Edge 表示由于新节点加入会改变整体结构，因此不能通过 GATNE-T 的邻居聚合实现，这里通过训练由 Base 到 Edge 的转换函数实现。

增强节点的内聚性

设计足够复杂的图结构以及符合业务需求的图学习任务是困难的，所以任务初期纠结于如何实施图表示向量预训练，此时或许可以从增强节点内聚性入手，因为通常业务场景都包含产品逻辑下的类别特征，所以可以根据特定业务特征设计距离度量函数构图，再通过聚类任务学习不同类别下的节点表示向量。

《Attributed Graph Clustering: A Deep Attentional Embedding Approach》

深度学习背景下常见的图聚类方法基于自编码器，本篇提出的 DAEGC 模型也类似，如下图所示，模型上半部分通过自编码器重构网络表示，下半部分让网络表示对应的分布 Q 拟合代表聚类信息的分布 P；除此之外，本篇的特点大概就是在生成表示向量 Z 处加入注意力机制，将更复杂的聚合函数应用于本框架并无障碍，下面的 SDCN 模型就从图结构信息考虑从而将 GCN 加入聚合函数

《Structural Deep Clustering Network》

本文认为在 DNN 的基础上加入 GCN 可以更好的捕捉图结构信息，如图所示；其中下半部分可以简单视为 DAEGC 框架，即通过 DNN 重构图输入 X，同时表示向量 H 对应的分布区拟合聚类分布 P；区别则在于 KL 散度需要分别应用于 DNN 生成的分布 Q 和 GCN 生成的分布 Z，简单说就是先通过 Q 构造代表聚类信息的分布 P，然后一方面最小化 Q 和 P 间的 KL 散度，另一方面也用 P 约束 GCN 学习到的 Z，最终的损失函数由图中三部分组成；文章在 6 个数据集上的实验表示多数情况用 GCN 生成的表示向量效果更好，并且最高的第四层表示总是优于前三层；此外，本篇还提到对非结构化数据通过 K 近邻算法构建邻接图，作者选用了 Heat Kernel 和 Dot-product 两种距离函数

总结

本文主要介绍了将 skip-gram 模型统一为矩阵分解形式，并应用图谱稀疏化等技术提升算法的工作。从矩阵分解的视角出发，我们有机会通过引入更多图理论中的工具发展图向量表示的性能，并且在处理超大规模图数据上走得更远。不过，业务相关的图构建仍然是难以算法化/理论化的障碍，简单的构建策略无法迁移到不同数据集上，图表示方向也应该学习 GNN 中异质网络的思路，同时，在困扰于结合业务需求设计学习任务时，考虑通过业务属性特征来增强表示向量的任务相关性和复杂性或许也是值得考虑方向。

参考文献

[1] 《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec》

[2]《Neural Word Embedding as Implicit Matrix Factorization》

[3]《NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization》

[4]《ProNE: Fast and Scalable Network Representation Learning》

[5]《Representation Learning for Attributed Multiplex Heterogeneous Network》

[6]《Arrtributed Graph Clustering: A Deep Attenetional Embedding Approach》

[7]《Structural Deep Clustering Network》