四、TADW

1. 大多数网络表示学习方法仅仅研究网络结构。事实上，网络顶点包含了丰富的信息（如文本内容和其它元数据），而这些方法都无法利用到这些信息。

   利用顶点的文本信息的一个直接方法是：分别独立学习文本特征representation 和网络顶点representation，然后将二者拼接在一起。这种方法没有考虑网络结构和文本信息之间的复杂交互，因此通常效果一般。

   论文《Network Representation Learning with Rich Text Information》 提出了 text-associated DeepWalk:TADW 模型，该模型在矩阵分解的框架下将顶点的文本信息纳入网络表示学习中。

4.1 模型

1. 给定网络 ，NRL 的目标是对每个顶点 得到一个低维表达 ，其中 。

2. 根据论文 《NeuralWord Embedding as Implicit Matrix Factorization》 以及 GraRep 的结论，基于 SGNS 的 DeepWalk 等价于矩阵分解：

   

   其中：

   • 为转移概率矩阵， 为邻接矩阵， 为度矩阵。

     定义了从顶点 经过一步转移到顶点 的概率，因此也称为一阶转移概率矩阵。

   • 为 阶转移矩阵， 定义了顶点 经过 步转移到顶点 的概率。

   • ， 。

   • 。

   进一步的，基于该思路类似可以证明：基于softmax 的 SkipGram 模型等价于矩阵分解：

   

   定义矩阵 ，则可以对 进行低秩分解： ，其中 ， 。

   这个问题是 NP 难的，因此研究者将这个问题转化为一个带约束的最优化问题：

   

   其中 是 观察到的部分， 为 Frobenius 范数， 为正则化系数。

3. 假设我们还有额外的特征，则可以使用 inductive matrix completion 技术来利用这些额外特征。

   假设每个顶点还有额外的特征 ，则可以进行矩阵分解：

   

   其中 。

   目标函数为：

   

   优于目标函数是 或 的凸函数，因此可以通过交替最小化 和 来求解该问题。实验中经过10 轮迭代即可收敛。

   • 尽管优化算法最终收敛到局部极小值而不是全局极小值，但是经验表明 TADW 效果较好。
   • 这里的 就是每个顶点的文本representation 矩阵，它是预训练好的。
   • 最终我们拼接 和 作为每个顶点的 维 representation 。

4. 考虑到计算 的计算复杂度为 ，因此TADW 采用近似计算在速度和准确性之间折衷：

   

   有两个好处：

   • 计算复杂度降低到
   • 是稀疏矩阵，其非零项远远少于 。

5. 算法复杂度：

   • 计算 的复杂度为 。

   • 在最优化求解迭代过程中：

     • 最小化一次 的复杂度为
     • 最小化一次 的复杂度为 。

   总的算法复杂度为 。其中 为 中非零元素的数量。

4.2 实验

1. 数据集：

   • Cora 数据集：包含来自七个类别的 2708 篇机器学习论文。

     • 论文之间的链接代表引用关系，共有 5429个链接。

     • 从标题、摘要中生成短文本作为文档，并经过停用词处理、低频词处理（过滤文档词频低于 10个的单词），并将每个单词转化为 one-hot 向量。

       最终每篇文档映射为一个 1433 维的binary 向量，每一位为0/1 表示对应的单词是否存在。

   • Citeseer数据集：包含来自六个类别的 3312 篇公开发表出版物。

     • 文档之间的链接代表引用关系，共4732个链接。

     • 从标题、摘要中生成短文本作为文档，并经过停用词处理、低频词处理（过滤文档词频低于 10个的单词），并将每个单词转化为 one-hot 向量。

       最终每篇文档映射为一个 3703 维的binary 向量，每一位为0/1 表示对应的单词是否存在。

   • Wiki 数据集：包含来自十九个类别的 2405篇维基百科文章。

     • 文章之间的链接代表超链接，共 17981 个链接。我们移除了没有任何超链接的文档。
     • 每篇文章都用内容单词的 TFIDF 向量来表示，向量维度为 4973 维。

   其中Cora、Citeseer 数据集平均每篇文档包含 18~32 个单词，数据集被认为是有向图；Wiki 数据集平均每篇文档包含 640 个单词，数据集被认为是无向图。

2. 对比模型及其配置：

   • TADW ：通过SVD 分解 TFIDF 矩阵到 200 维的文本特征矩阵 ，这是为了降低矩阵 的规模。

     对于 Cora,Citeseer 数据集 ；对于维基百科数据集 。

     注意：最终每个顶点的representation 向量的维度为 2k 。

   • DeepWalk：窗口尺寸 ，每个顶点的游走序列数量 。对于 Cora,Citeseer 数据集维度 ，对于维基百科数据集维度 。

   • pLSA：利用文档的主题分布作为文档的 representation 。

   • Text Features：使用文本特征矩阵 作为每篇文档的 200 维 representation，这代表了仅使用文本特征的效果。

   • Naive Combination：直接拼接 DeepWalk 的embedding 向量和文本特征向量。对于 Cora,Citeseer 数据集这将得到一个300 维向量；低于维基百科数据集这将得到一个 400 维向量。

   • NetPLSA ：引入文档之间的连接作为正则化项的主题模型。

     对于 Cora,Citeseer 数据集主题数量为 160；对于维基百科数据集主题数量为 200 。

3. 评估方式：我们对抽取的 Graph Embedding 分别采用线性 SVM 和 TSVM 来评估其监督学习和半监督学习的性能。评估方法是基于 one-vs-rest 来进行多分类任务。对于线性 SVM 我们分别随机选择 10%~50% 的样本作为训练集，剩下样本作为测试集；对于TSVM 我们分别随机选择 1%~10% 的样本作为训练集，剩下样本作为测试集。

   我们评估测试集的分类 accuracy 。每种拆分方式随机重复10次取均值作为结果。

4. 评估结果如下所示：

   • - 表示 TSVM 训练12个小时都未收敛。

   • 我们并未在维基百科上给出半监督学习的结果。因为在该数据集上TADW 在监督学习的小数据集上已经证明其优越性，无需继续验证。

   • 结论：

     • TADW 在所有三个数据集上始终优于其它所有模型。

       在 Cora,Citeseer 数据集上，即使 TADW 模型的训练数据减少一半，其效果然仍然超过其它所有模型。这证明了 TADW 是有效的。

     • TADW 在半监督学习方面显著提升。在 Cora 数据集的半监督学习任务中，TADW 超越了剩余的最佳模型 4%；在 Citeseer 数据集的半监督学习任务中，TADW 超越了剩余的最佳模型 16%。

       这是因为 Citeseer 数据集的噪声更大，而 TADW 对学习的噪声鲁棒性更好。

     • 当训练集较小时，TADW 效果更为明显。

       大多数模型的效果随着训练集比例的下降而迅速下降，因为这些模型的顶点representation 训练不充分，噪声较多。而TADW 从网络和文本中共同学习的 representation 噪音更少。

   

   

   

5. 固定训练集比例为 10% ，我们评估超参数 （维度）和 （正则化系数）的影响。

   对于 Cora,Citeseer 数据集 ；对于维基百科数据集 。

   可以看到：

   • 当固定维度 时，TADW 预测结果随着 的增加基本保持不变。
   • 对于不同的数据集，最佳的维度 有所不同。

   如下图所示，原始论文用 表示维度，用 表示正则化项。这里为了表达方便采用了不同的符号。