十八、HNE

1. 社交网络中包含Graph 以及相关的数据，如何学到数据的representation 具有挑战：

   • 首先，社交网络上的数据规模呈指数型增长

   • 其次，社交网络上的数据类型多种多样，不仅包含文本，还有图像、视频。

   • 最后，社交网络上的数据并不是孤立的，而是相互产生关联。这些关联可以通过数据之间的链接来显式或隐式的构成：

     • 显式关联：如果文本和图像出现在同一个网页中，则该文本和图像之间构成显式关联；如果两个网页之间存在超链接，则这两个网页之间存在显式关联。
     • 隐式关联：用户的活动可以视为隐式反馈，它提供了数据之间的隐式关联。例如，如果用户使用相似的 tag 描述了多张图片，那么这些图片之间存在隐式的语义关联。

   因此，如此大规模的数据导致异常复杂的异质网络heterogeneous network，这对学习数据的统一表达提出了巨大挑战。

   为解决该问题，论文 《Heterogeneous Network Embedding via Deep Architectures》 提出了一种被称作异质网络嵌入 Heterogeneous Network Embedding:HNE 的新的方法来学习学习网络的representatioin 。

   • HNE 方法同时考虑顶点的内容信息和顶点之间的链接信息。
   • HNE 将不同的异质顶点映射到一个统一的潜在空间中，以便可以直接比较不同类型的顶点。

18.1 模型

1. 定义异质网络 heterogeneous network 为 ，其中： 为顶点集合、 为边集合。

   定义顶点的类型映射函数为： ，其中 为顶点类型集合。定义顶点的链接映射函数为： ，其中 为链接类型集合。

   • 对于同质网络 homogeneous network，我们有
   • 对于异质网络，我们有

   为便于讨论，假设网络中存在两种类型的顶点：文本类型顶点 、图像类型类型顶点 。假设网络中存在三种类型的边：text-text 类型的边 、text-image 类型的边 、image-image 类型的边 。并且它们满足：

   

   对于每个顶点，我们抽取其内容作为特征：

   • 对于文本顶点 ，我们选择该文本的 TF-IDF 向量（或者 BOW 向量）作为顶点的特征，记作 。其中 为文本顶点特征向量的维度。
   • 对于图像顶点 ，我们选择该图像的张量（如RGB 空间中的原始像素）作为顶点的特征，记作 。其中 为图像顶点张量的尺寸。

   我们采用简单的对称邻接矩阵 来表示链接关系：

   

   .

18.1.1 线性 HNE

1. 假设图像顶点 的内容 映射到一个 维的空间，映射后的向量为 。最简单的映射方式是：将 按照矩阵的列进行拼接。

   我们使用两个线性变换将图像顶点、文本顶点映射到统一的低维空间：

   • 图像顶点：
   • 文本顶点：

   其中 为统一的低维空间的维度。

   顶点的相似性可以通过顶点在低维空间中的内积来实现：

   

   其中：

   

2. 异质顶点之间存在显式或隐式的交互，这些交互具体表现为异质网络中的链接。如果两个顶点之间产生链接，则它们之间的相似性要比未链接的两个顶点的相似性更大。

   考虑一对图像顶点 ，我们定义一个pariwise 函数来编码顶点之间的链接信息：

   

   我们选择 ，其中 为一个偏移量。

   则定义损失函数为：

   

   • 当 存在链接时 ，此时 越大则损失越小
   • 当 不存在链接时 ，此时 越大则损失越大

   text-text 顶点pair 对、image-text 顶点 pair 对之间的损失函数也类似，只需要替代 函数为对应值即可。类似的偏移项替代为 。

   最终我们的损失函数为：

   

   其中：

   • 表示image-image 链接的数量，即 ； 表示text-text 链接的数量，即 ； 表示 image-text 链接的数量，即 。
   • 为平衡系数，用于平衡不同类型损失以及正则化项。
   • 等偏置项既可以从数据中学习得到，也可以设为固定值。为简单考虑，我们都设置为固定值。

3. 上述最优化问题可以通过坐标下降法coordinate descent 得到有效解决，每次固定一个变量从而求解另一个变量：

   • 首先固定参数 从而求解参数 ：

     

   • 然后固定参数 从而求解参数 ：

     

     .

18.1.2 深度 HNE

1. 在前面的介绍中，我们将不同的异质顶点映射到统一的低维潜在空间。但是，这类 embedding 函数是线性的，缺乏对复杂网络进行建模的能力。这里我们引入深度学习框架。

   前面部分我们的解决方案可以分为两个步骤：

   • 手动构造顶点的特征表示：对于文本顶点，使用其 TF-IDF 向量；对于图像顶点，使用其原始 RGB 像素点拼接而成的向量。
   • 将不同的特征表示嵌入到公共的低维空间中。

   这里我们通过深度学习将特征表示的学习、公共空间的嵌入合并为一步。

2. 特征表示的学习：

   • 定义图像特征抽取的非线性函数为 ，其参数为 。通常我们使用 CNN 来抽取图像特征。下图为一个图像特征抽取模型，它由五个卷积层、两个全连接层组成。所有层都采用 ReLU 非线性激活函数。

     该模块称作 deep image 模块。

     

   • 定义文本特征抽取的非线性函数为 ，其参数为 。由于文本是非结构化的，不包含空间信息，因此通常使用全连接层FC 对文本的 TF-IDF 输入来抽取特征。

     该模块称作 deep text 模块。

   则我们的损失函数变为：

   

3. 公共空间的嵌入：我们可以通过一个额外的线性嵌入层来级联deep image 模块和 deep text 模块。

   定义 ，其中 ；定义 ，其中 。

   则目标函数变为：

   

   其中：

   • 我们使用 dropout 代替了 正则化项，因此上式没有 对应的项

   • 我们使用新的损失函数：

     

     与前面的 相比，这里的损失函数移除了偏置项。

   该目标函数可以通过随机梯度下降SGD 来求解。

4. 为进行端到端的 HNE 学习，我们将deep image 模块和 deep image 模块连接起来。我们以 text-text 链接为例，另外两种类型的链接也是类似的。下图包含两个deep text 模块，它们构成了pairwise text-text 模块。

   • deep text 模块包含两个FC 全连接层，然后是一个线性 embedding 层。
   • 线性 embedding 层的输出是公共潜在空间中的低维向量，该低维向量进一步送到预测层 prediction layer 来计算损失函数。
   • text-text 模块是对称的，下图中相同颜色的神经元共享相同的权重和偏差，箭头表示前向传播的方向。

   

5. HNE 的整体架构如下图所示，图中展示了三个模块，从左到右依次为 image-image 模块、image-text 模块、text-text 模块。这些模块分别连接到prediction layer 来计算损失函数。

   下图中，相同的颜色代表共享权重。箭头表示前向传播和反向传播的方向。

   

6. 目前为止我们仅展示了两种类型顶点的异质网络embedding 方法。事实上，我们的框架也支持多种类型顶点的异质网络 embedding 。

   另外，我们提出的方法是无监督学习方法，因此可以作为下游fine-tuning 微调阶段的预训练pretraining 步骤来使用。

   也可以将prediction layer 替换为 softmax 层，从而将整个深度网络转换为 task-specific 的端到端有监督训练模型。

18.2 实验

1. 数据集：我们使用来自现实世界社交网络的两个公开数据集：

   • BlogCatalog：一个博客社交网络，用户可以在预定义的类别下对该用户的博客进行分类。

     我们根据“关注”行为来构建用户之间的链接，并使用每个用户的所有博客内容的 TF-IDF 向量作为用户的内容特征。最终我们得到一个无向、同质图，每个顶点代表一个用户，顶点的特征为TF-IDF 向量。

     最终该图包含 5196 个顶点、171743 条边、类别数量 6、内容向量维度 8189，并且该数据集各类别是平衡的。

   • NUS-WIDE：Flickr 上的图片和文本数据，包含 269648 张关联有 tag 的图像，其中 tag 集合大小为 5018 。每一组image-tag 标记有一个 label ，一共 81 个类别。

     • 由于原始数据中包含很多不属于任何类别的噪音样本，因此这些样本被删除。
     • 另外，我们将频次最高的 1000 个 tag 作为文本并抽取其 TF-IDF 向量作为特征。
     • 我们进一步删除了不包含任何这 1000 个 tag 的样本。

     最终我们分别随机抽样了 53844 和 36352 个样本进行训练和测试。我们将图像和文本分别视为独立的顶点来构建异质网络，训练网络包含 107688 个顶点、测试网络包含 72704 个顶点。如果两个顶点共享至少一个概念 concept，则构建它们之间的语义链接。我们对每个顶点最多随机采样 30 个链接，从而构建稀疏的邻接矩阵 。

     我们以 out-of-sample 方式来评估不同的算法，即：训练样本绝对不会出现在测试数据集中。

2. 对于所有配置我们随机重复执行五次，并取结果的平均值。

3. 我们从 BlogCatalog 数据集中随机选择 500 个顶点，然后可视化其链接，其中每个顶点的颜色代表其类别。

   可以看到：

   • 相对而言，“关注” 关系倾向于将具有相似属性的用户聚合在一起
   • 绝对而言，这种聚合之中存在大量噪音。统计表明：59.89% 的链接连接到了不同类别的顶点。

   

4. 我们考察 HNE 算法训练过程中重建链接的准确性。我们评估了算法学习 embedding 过程中，训练集每个 mini-batch 的链接重建准确性 accuracy ：预估正确的 pair 对的数量， 除以所有的 pair 对的数量。其中 mini-batch = 128 。

   横轴表示 epoch ，每个 epoch 包含 500 个 step 。红线表示每个 epoch 重建准确性的均值。

   可以看到：随着学习的推进，算法能够正确地重建 80% 以上的链接。

   

5. 我们在 BlogCatalog 数据集上比较了以下模型来无监督抽取特征：

   • Content：基于原始空间的内容特征，即用户所有博客的 TF-IDF 特征向量
   • Links：基于原始空间的链接特征，即用户的邻接关系作为特征
   • Link-Content：将内容和邻接关系都视为特征
   • LUFS：针对内容和链接的无监督特征抽取框架
   • LCMF：基于链接和内容的矩阵分解方法
   • HNE：我们提出的异质网络特征抽取方法

   对于这些抽取出来的特征，我们使用标准的 kNN 分类器来评估特征的分类效果。为确保公平比较，所有方法的 embedding 维度固定为 100 。对于 Content/Links/Link-Content 方法抽取的特征，我们使用 PCA 算法投影到 100 维的空间。

   这些模型的分类准确率如下所示。可以看到：

   • 在不同规模的训练集中，HNE 始终优于其它的 baseline 方法。这是因为网络链接可以编码很多有用的信息。

   • 如果将 embedding 视为预训练步骤，并通过将多类 softmax 替换掉 predict layer 来微调整个模型，则我们的效果会进一步提升。

     这表明了无监督的 embedding 学习对于有监督分类任务提供了很好的初始化，并能进一步提升性能。

   

6. 我们还比较了BlogCatalog 数据集上不同方法得到的 embedding 的聚类表现。与分类任务相比，聚类任务是完全无监督的，并很大程度上依赖于相似性度量函数。这里我们采用最常见的余弦相似度。

   我们根据聚类后的结果以及label 信息，同时给出了准确率和互信息 normalized mutual information :NMI 作为评估指标。

   结果表明：

   • 类似分类任务，仅使用链接会带来最差的结果。这可能是因为：在没有全局内容信息指导的条件下，相似性往往是局部的，并且对噪音非常敏感。
   • 仅内容相似性不足以捕获关系信息。
   • 通过链接和内容的简单组合，这可以提供与其它 baseline 相当的性能。
   • 我们的 HNE 模型优于所有其它 baseline 模型。

   

7. 与 BlogCatalog 相比，NUS-WIDE 数据集构成了一个包含图像、文本的异质网络。该数据集上的对比模型包括：

   • Canonical Correlation Analysis: CCA：根据输入的多个数据源的关系将它们嵌入到共同的潜在空间。
   • DT：一种迁移学习方法，通过潜在 embedding 来减少图像和文本之间的语义距离。
   • LHNE：HNE 的线性版本。

   我们为所有其它baseline 方法抽取了 4096 维的特征，但是由于我们的HNE 方法是端到端的，因此不需要为图像手动抽取特征。

   由于 NUS-WIDE 数据集是类别不平衡的，因此我们用平均精度 average precsision:AP 来评估每种可能的标签结果的分类性能。

   为了方便比较，所有方法的公共嵌入空间的维度为 400 维，并且使用线性支持向量机 SVM 来作为所有方法产出的 embedding 的通用分类器。之所以用 SVM 是因为计算 AP 需要预估一个概率值，而这不方便从深度神经网络分类器中取得。

   我们比较了三种配置：

   • image only：仅在图像顶点上学习 embedding，然后训练 SVM、执行分类测试。
   • text only：仅在文本顶点上学习 embedding，然后训练 SVM、执行分类测试。
   • image + text：同时使用图像顶点和文本顶点学习 embedding，然后后训练 SVM、执行分类测试。

   可以看到：

   • 在所有配置中，仅使用文本数据进行分类效果最差。这可能是由于：和图像输入相比，文本输入非常稀疏。
   • 仅使用线性的 HNE ，我们就可以获得与 DT 相当的结果。
   • 非线性HNE 在所有三种配置中进一步提高性能，这表明使用非线性函数同时优化特征学习和潜在 embedding 的优势。

   

8. 为进一步验证 HNE 的能力，我们在 cross-modal 检索任务中将我们的方法和 baseline 进行比较。

   我们的目标是希望通过文本 query 来召回对应的图片。在所有 81 个 label 中，有 75 个出现在 TF-IDF 文本向量中。因此我们基于这 75 个label 单词来构建 query 向量：

   

   其中query 向量长度为 1000， 除了第 个 label 对应的位置为 1，其它所有位置为零。query 向量一共有 75 个。

   根据学到的 embedding 函数，我们将这些 query 向量都映射到公共潜在空间中，并通过欧式距离来检索测试集中的所有图像。我们报告了 average precision at rank k:p@k （top k 结果中的平均precision 值） 的结果。 可以看到：HNE 明显优于其它 baseline 。

   

   然后我们给出一些检索的案例。可以看到：

   • Mountain 的第三个检索结果不正确，这可能是由于其它Mountain 图像和带有牛的Mountain图像之间存在极大的视觉相似性。

   • Cow 的检索结果中包含三只鹿，这是因为这些图像具有多个tag，并通过“动物” 概念进行链接。

     由于我们的方法以及 ranking 函数完全是无监督的，因此 cow 和 deer 等对象之间的联系会混淆我们的 embedding 学习。我们预期使用监督 ranking 可以提升性能。

   

9. 我们展示了HNE 在 BlogCatalog 数据集上目标函数的变化，从而验证模型的收敛性。其中 x 轴代表 epoch 。

   可以看到：目标函数经过 60 个 epoch 的持续性降低之后趋向于平稳，这表明算法可以收敛到稳定结果。

   

10. AP 就是P-R 曲线下的面积，mAP 就是所有类别的 AP 的均值。

    事实上，AP 就是把 recall 的取值根据 一共 11 个水平，然后取对应的 Precision 的平均值。在 P-R 曲线上这等价于曲线的线下面积。