一、HNE [2015]

《Heterogeneous Network Embedding via Deep Architectures》

1. 向量化的 data representation 经常出现在许多数据挖掘 application 中。向量化的 data representation 更容易处理，因为每个数据都可以被视为驻留在欧式空间中的一个 point 。因此，可以通过一个合适的指标来直接衡量不同 data point 之间的相似性，从而解决分类、聚类、检索等传统任务。如 《Data Classification: Algorithms and Applications》 所示，学习良好的 representation 是数据挖掘和 web 搜索中的基本问题之一。与设计更复杂的模型相比，学习良好的 representation 对任务效果的影响通常更大。

   不幸的是，许多network数据源（如 Facebook, YouTube, Flickr, Twitter）无法自然地表示为向量化的输入。这些社交网络和社交媒体数据通常以图数据 （graph data） 和关系数据 （relational data） 二者组合的形式来表示。当前的研究集中在预定义（pre-defined ）的特征向量、或者复杂的 graph-based 的算法来解决底层任务。人们在各种主题上完成了大量的研究，例如协同分类（ collective classification）、社区检测（community detection） 、链接预测（link prediction ）、社交推荐（social recommendation） 、定向广告（targeted advertising）等等。对于内容和链接而言，网络数据（network data） 以 embedding 形式开发的 unified representation 非常重要。 unified representation 的基本假设是：一旦获得向量化的 representation，网络挖掘任务就可以很容易地通过现有的机器学习算法来解决。

   然而，网络数据的 feature learning 并不是一项简单的任务，因为网络数据具有许多特有的特性，例如网络的规模、动态性、噪声、以及异质性（heterogeneity ）。首先，社交网站上的多媒体数据量呈指数级增长。到 2011 年年中，Facebook 上的照片估计数量已达 1000 亿张，并且每天上传的新照片数量高达 3.5 亿张。其次，鉴于用户的不同背景（background） ，社交媒体往往噪音很大。而且研究人员注意到，垃圾邮件发送者产生的数据比合法用户更多，这使得网络挖掘更加困难。最后，社交媒体数据包含多样（diverse） 的、异质的信息。例如，当事件发生时，不同类型的媒体数据都会进行报道。如下图所示，当在谷歌中搜索 “马航 MH17” 时，相关结果中不仅包含文本文档，还包含图像和视频。

   

   此外，社交媒体数据不是孤立存在的，而是由各种类型的数据组合而成的。这些交互可以通过它们之间的链接显式或隐式地形成。例如，在同一网页中同时出现的图像和文本提供了它们之间的显式链接，而文本到文本的链接是通过不同 web document 之间的超链接显式形成的。另一方面，用户的交互活动可以被视为隐式反馈，它链接了不同的社交媒体部分（social media component） 。如果用户以相似的标签（tag ）描述多张图像，那么一个合理的假设是：这些图像之间存在语义关系。很明显，如此庞大的数据量导致了复杂的异质网络，这给学习 uniform representation 带来了巨大的挑战。

   为了应对上述挑战，论文 《Heterogeneous Network Embedding via Deep Architectures》 提出了一种关于 network representation learning 的新思想，称作 Heterogeneous Network Embedding: HNE 。HNE 同时考虑了内容信息（ content information ）和关系信息（relational information） 。HNE 将不同的异质对象映射到一个统一的潜在空间中，以便可以直接比较来自不同空间的对象。

   与传统的线性 embedding 模型不同，HNE 将 feature learning 过程分解为深层的多个非线性层。HNE 通过迭代求解关于 feature learning 和 objective minimization 的问题，从而协调并相互加强这两个部分。HNE 同时建模了底层网络的全局链接结构（global linkage structure ）和局部链接结构（local linkage structure），这使得它在捕获网络链接方面比浅层 embedding 方案更强大，特别是当链接信息在揭示不同对象之间的语义相关性方面起关键作用时。沿着这个研究方向，论文利用网络链接来设计一个损失函数，从而迫使网络中存在链接的不同对象在 embedding 空间是相似的。network-preserved embedding 的思想如下图所示。

   事实上根据 HNE 的模型公式，HNE 仅建模了局部链接结构（即，保留一阶邻域），并未建模全局链接结构。

   

   HNE 框架的主要优点如下：

   • 鲁棒性：HNE 探索不同异质对象之间的全局一致性（ global consistency ），从而学习由网络结构指导的unified feature representation 。

   • 无监督：HNE 是无监督并且独立于任务的，这使其适用于许多面向网络的数据挖掘 application 。

   • out-of-sample：HNE 能够处理 out-of-sample 问题（即 unseen 顶点）。这解决了动态网络相关的挑战，其中随着时间的推移可能会在网络中添加新顶点。

2. 相关工作：

   • Network Embedding：feature embedding 的一个分支是由网络中的协同过滤和链接预测等 application 所推动的。这些 application 根据潜在属性对实体之间的关系进行建模。这些模型通常将问题迁移 （transfer） 为学习实体的 embedding，这在数学上对应于对观察到的关系矩阵的矩阵分解问题。

     • 《Combining content and link for classification using matrix factorization》 提出了一种在链接邻接矩阵（linkage adjacency matrix ）和 document-term frequency 矩阵上联合分解的方法，从而用于网页分类。

     • 此外，《Structure preserving embedding》 提出了一种 structure preserving 的 embedding 框架，该框架将图嵌入到低维欧式空间中，并保持了全局拓扑属性。

     • 此外，DeepWalk 从截断的随机游走中学习网络中顶点的潜在 representation。

     然而，这些模型仅关注单一关系（single relation），这无法应用于异质网络。而且这些模型中的大多数很难泛化到 unseen sample （即训练期间未见过的顶点）。

     这些方法对异质网络的自然扩展是将多个关系矩阵堆叠在一起，然后应用传统的张量分解。这种 multi-relational embedding 的缺点是不同 term 之间共享参数，这无法扩展到大型网络。《Latent feature learning in social media network》 提出的非线性 embedding 模型使用 Restricted Boltzmann Machine: RBM 进行跨模型链接分析（ crossmodel link analysis ）。但是，它没有利用原始数据中的所有社交信息，这导致了次优的解决方案。此外，计算机视觉和语音方面的工作表明，与 DNN 和 CNN 相比，layer-wise 的 RBM 训练对于大规模数据而言效率低下。

   • 深度学习：近年来，机器学习研究已经从基于人工制作的特征显著转向为基于原始数据学到的特征，这主要归功于深度学习的成功。深度学习模型在语音识别、图像识别/检测、以及最近的自然语言处理中变得越来越重要。深度学习技术是通用函数的逼近器（approximator）。然而，从历史上来看，训练具有两层以上隐层的深度神经网络很难成功。困难在于高维的参数空间、以及高度非凸的目标函数，这使得基于梯度的方法受到局部极小值的困扰。

     深度学习的最新进展得益于多种因素的推动，例如大规模数据集的使用、算力的增长、以及无监督和监督训练算法的进步。

     • 无监督深度学习（通常被称为预训练 pre-training），借助大量可用的未标记数据来提供鲁棒的初始化和正则化。例如，《Reducing the dimensionality of data with neural networks》 首次使用 RBM 对深度神经网络进行 layer-wise 初始化。《Greedy layer-wise training of deep network》 也提出了类似的方法，采用自编码器来进行权重初始化。

     • 最近，多层神经网络的监督学习已经成为可能。dropout 的方法已经展示出特别的前景。《Imagenet classification with deep convolutional neural networks》 提出的七层卷积神经网络在 ImageNet 大规模视觉识别挑战赛上取得了 SOTA 的性能。该挑战赛是计算机视觉中最具挑战性的任务之一。来自这个七层卷积神经网络的中间层的特征，后来被证明是其它计算机视觉任务（如对象检测object detection ）的良好的 feature representation 。

     在深度学习架构的背景下，人们对利用来自多模态（multiple modalities ）的数据越来越感兴趣。自编码器和 RBM 等无监督深度学习方法被部署并联合重建（部分共享的网络partially shared network）音频和视频来执行 feature learning，从而成功应用于多模态任务（multimodal task） 。另一种方案，也有人努力学习具有多个任务的联合 representation 。对于图像和文本，一种特别有用的场景是通过将语义上有意义的 embedding 空间与图像 label 相结合，从而实现对 unseen 的 label 进行图像分类的 zero-shot learning 。

     据我们所知，之前很少有人尝试利用网络中的链接结构进行 representation learning 。在《A deep learning approach to link prediction in dynamic network》 中，它使用条件的动态的 RBM 对网络链接的动态性进行建模，主要任务是使用历史数据预测未来的链接。与我们最相似的工作是 《Latent feature learning in social media network》，其中它在多媒体链接数据上训练一个 content RBM 。我们在几个方面与他们的工作不同：我们在无监督环境中使用监督学习的方案，我们的方法可以扩展到大规模数据集，我们执行多任务学习从而融合来自不同模态的形式。

1.1 模型

1. 异质网络（ heterogeneous network ）指的是具有不同类型对象、和/或具有不同类型链接的网络。从数学上讲，我们定义一个无向图 $G=(\mathcal{V},\mathcal{E})$$G =(\mathcal V,\mathcal E)$，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V = \{v_1,\cdots,v_n\}$ 为顶点集合，$\mathcal{E}$$\mathcal E$ 为边集合。一条边 $e_{i,j}\in \mathcal{E}$$e_{i,j}\in \mathcal E$ 当且仅当顶点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间存在无向链接。

   此外，图 $G$$G$ 还关联了对象类型映射函数 $f_v:\mathcal{V}\to \mathcal{O}$$f_v:\mathcal V\rightarrow \mathcal O$、以及链接类型映射函数 $f_e:\mathcal{E}\to \mathcal{R}$$f_e:\mathcal E\rightarrow \mathcal R$，其中 $\mathcal{O}$$\mathcal O$ 代表对象类型集合、$\mathcal{R}$$\mathcal R$ 代表关系类型集合。每个顶点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 属于一个特定的对象类型 $f_v(v_i)\in \mathcal{O}$$f_v(v_i)\in \mathcal O$。类似地，每个链接 $e_{i,j}\in \mathcal{E}$$e_{i,j}\in \mathcal E$ 属于一个特定的关系类型 $f_e(e_{i,j})\in \mathcal{R}$$f_e(e_{i,j})\in \mathcal R$ 。值得一提的是，边的链接类型自动地定义了其端点的顶点类型。

   网络的异质性分别由集合 $\mathcal{O}$$\mathcal O$ 和 $\mathcal{R}$$\mathcal R$ 的大小所反映。当 $|\mathcal{O}|=|\mathcal{R}|=1$$|\mathcal O|=|\mathcal R| = 1$ 的情况下，网络是同质（heterogeneous） 的。否则网络是异质 （heterogeneous） 的。下图说明了一个异质网络的示例，其中包含两种对象类型和三种链接类型。为了进一步便于理解，我们将假设对象类型为 image: I、text: T 。链接关系 $\mathcal{R}$$\mathcal R$ 包含 image-to-image（红色点虚线）、text-to-text （绿色短虚线）、image-to-text（蓝色实线），分别用 RII, RTT, RIT 表示。因此，在这种情况下，我们有 $|\mathcal{O}|=2,|\mathcal{R}|=3$$|\mathcal O| = 2, |\mathcal R| = 3$ 。虽然在文本域和图像域的这种简单抽象仅仅是为了便于在本文中进一步讨论，但是这个假设并未失去一般性，因为这些思想很容易推广到任意数量的类型。

   因此，任何顶点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 都可以被划分到两个不相交的子集 ${\mathcal{V}}_I$$\mathcal V_I$ 或 ${\mathcal{V}}_T$$\mathcal V_T$ ，分别对应于文本域和图像域。因此，我们有：${\mathcal{V}}_I\cup {\mathcal{V}}_T=\mathcal{V}$$\mathcal V_I\cup \mathcal V_T = \mathcal V$ ，以及 ${\mathcal{V}}_I\cap {\mathcal{V}}_T=\varphi$$\mathcal V_I\cap \mathcal V_T = \phi$ 。 类似地，边集 $\mathcal{E}$$\mathcal E$ 可以划分为三个不相交的子集，分别记作 ${\mathcal{E}}_{I,I},{\mathcal{E}}_{T,T},{\mathcal{E}}_{I,T}$$\mathcal E_{I,I},\mathcal E_{T,T},\mathcal E_{I,T}$ 。此外，每个顶点都聚合了 unique 的内容信息。具体而言：

   • 对于每个图像顶点 $v_i\in {\mathcal{V}}_I$$v_i\in \mathcal V_I$，我们给出图像张量的内容 ${\mathbf{X}}_i\in {\mathbb{R}}^{d_I\times d_I\times 3}$$\mathbf X_i\in \mathbb R^{d_I\times d_I\times 3}$，其中 $d_I$$d_I$ 为图像的尺寸。

   • 对于每个文本顶点 $v_i\in {\mathcal{V}}_T$$v_i\in \mathcal V_T$，我们给出文本向量的内容 ${\overrightarrow{\mathbf{z}}}_j\in {\mathbb{R}}^{d_T}$$\mathbf{\vec z}_j\in \mathbb R^{d_T}$，其中 $d_T$$d_T$ 为文本的长度。

   例如，图像的内容是 RGB 颜色空间中的原始像素格式，文本的内容是文档的 Term Frequency - Inverse Document Frequency: TF-IDF 得分。我们将链接关系表示为一个对称的邻接矩阵 $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$，如果 $e_{i,j}\in \mathcal{E}$$e_{i,j}\in \mathcal E$ 则 $A_{i,j}=1$$A_{i,j} = 1$，否则 $A_{i,j}=-1$$A_{i,j}=-1$ （为了模型简单）。

   注意，这里的邻接矩阵元素取值为 {+1, -1}，这和经典的 {+1, 0} 不同。这是为了后面的损失函数服务，给 “负边”（即，未链接的顶点对）一个非零值可以在损失函数中引入 “负边” 的信息。虽然这种邻接矩阵是完全稠密的矩阵，但是我们可以仅存储“正边”，从而仍然存储一个稀疏版本的邻接矩阵。

   

2. 接下来，我们首先引入一种新的损失函数来衡量跨网络的相关性，并以数学方式展示我们的 HNE 框架。本质上，embedding 过程为每个对象同时将异质内容和异质链接编码到一个 representation 中。

   然后我们提出了一种 linkage-guided 的深度学习框架，从而同时对潜在空间 embedding 和 feature learning 进行联合建模。这可以通过使用反向传播技术有效地求解。

   最后，我们讨论了将 HNE 算法直接扩展到多于两种对象类型的一般情况。

1.1.1 线性 HNE

1. 异质 embedding 任务的主要目标是学习映射函数，从而将不同模态的数据映射到公共空间，以便直接衡量对象之间的相似性。假设与图像顶点相关联的原始内容 ${\mathbf{X}}_i\in {\mathbb{R}}^{d_I\times d_I\times 3}$$\mathbf X_i\in \mathbb R^{d_I\times d_I\times 3}$ 可以转换为向量representation ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_I^{\prime }}$$\mathbf{\vec x}_i\in \mathbb R^{d_I^\prime}$ 。原始输入数据到 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 的转换将在下一节内容中描述。一种朴素的方法是将图像的每一列拼接起来，或者通过feature machine 。值得一提的是，$d_I^{\prime }$$d_I^\prime$ 和 $d_T$$d_T$ 不必相同，因为图像和文本是完全不同领域的特征。

   我们使用两个线性变换矩阵 $\mathbf{U}\in {\mathbb{R}}^{d_I^{\prime }\times r}$$\mathbf U\in \mathbb R^{d_I^\prime \times r}$ 和 $\mathbf{V}\in {\mathbb{R}}^{d_T\times r}$$\mathbf V\in \mathbb R^{d_T\times r}$ 将两种类型的样本变换到一个均匀的潜在空间，其中 $\mathbf{U}$$\mathbf U$ 用于图像域、$\mathbf{V}$$\mathbf V$ 用于文本域。对于图像和文本，变换后的represetnation 分别为 $\widetilde{\overrightarrow{\mathbf{x}}}\in {\mathbb{R}}^r,\widetilde{\overrightarrow{\mathbf{z}}}\in {\mathbb{R}}^r$$\tilde{\mathbf{\vec x}}\in \mathbb R^r,\tilde{\mathbf{\vec z}}\in \mathbb R^r$。因此我们有：

   $$\widetilde{\overrightarrow{\mathbf{x}}}={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}},\widetilde{\overrightarrow{\mathbf{z}}}={\mathbf{V}}^{\mathrm{\top }}\overrightarrow{\mathbf{z}}$$

   尽管图像和文本可能在不同维度的空间中表示，但是变换矩阵 $\mathbf{U}$$\mathbf U$ 和 $\mathbf{V}$$\mathbf V$ 将它们映射到一个共同的 $r$$r$ 维空间。相同类型的两个 data point 之间的相似性可以表示为投影空间中的内积，即：

   $$\begin{array}{c}s({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)={\widetilde{\overrightarrow{\mathbf{x}}}}_i^{\mathrm{\top }}{\widetilde{\overrightarrow{\mathbf{x}}}}_j={\left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i\right)}^{\mathrm{\top }}{\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_j={\overrightarrow{\mathbf{x}}}_i^{\mathrm{\top }}{\mathbf{M}}_{I,I}{\overrightarrow{\mathbf{x}}}_j\\ s({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)={\widetilde{\overrightarrow{\mathbf{z}}}}_i^{\mathrm{\top }}{\widetilde{\overrightarrow{\mathbf{z}}}}_j={\left({\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_i\right)}^{\mathrm{\top }}{\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j={\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\mathbf{M}}_{T,T}{\overrightarrow{\mathbf{z}}}_j\end{array}$$

   注意，由于嵌入到公共空间，不同类型对象（如文本和图像）之间也可以进行相似度计算，即：

   $$\begin{array}{c}s({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{z}}}_j)={\widetilde{\overrightarrow{\mathbf{x}}}}_i^{\mathrm{\top }}{\widetilde{\overrightarrow{\mathbf{z}}}}_j={\left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i\right)}^{\mathrm{\top }}{\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j={\overrightarrow{\mathbf{x}}}_i^{\mathrm{\top }}{\mathbf{M}}_{I,T}{\overrightarrow{\mathbf{z}}}_j\\ ={\widetilde{\overrightarrow{\mathbf{z}}}}_j^{\mathrm{\top }}{\widetilde{\overrightarrow{\mathbf{x}}}}_i={\left({\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j\right)}^{\mathrm{\top }}{\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i={\overrightarrow{\mathbf{z}}}_j^{\mathrm{\top }}{\mathbf{M}}_{I,T}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i\end{array}$$

   这里 ${\mathbf{M}}_{I,I}=\mathbf{U}{\mathbf{U}}^{\mathrm{\top }}\in {\mathbb{R}}^{d_I^{\prime }\times d_I^{\prime }}$$\mathbf M_{I,I}=\mathbf U\mathbf U^\top\in \mathbb R^{d_I^\prime \times d_I^\prime}$ 和 ${\mathbf{M}}_{T,T}=\mathbf{V}{\mathbf{V}}^{\mathrm{\top }}\in {\mathbb{R}}^{d_T\times d_T}$$\mathbf M_{T,T}=\mathbf V\mathbf V^\top\in \mathbb R^{d_T\times d_T}$ 为半正定矩阵，而 ${\mathbf{M}}_{I,T}=\mathbf{U}{\mathbf{V}}^{\mathrm{\top }}\in {\mathbb{R}}^{d_I^{\prime }\times d_T}$$\mathbf M_{I,T}=\mathbf U\mathbf V^\top\in \mathbb R^{d_I^\prime \times d_T}$ 。

   潜在 embedding 与文献 《Learning locally-adaptive decision functions for person verification》 中已被广泛研究的相似性学习（ similarity learning）和度量学习（ metric learning ）密切相关。即，两个顶点之间的相关性（correlation ）可以通过投影矩阵 $\mathbf{U}$$\mathbf U$ 和 $\mathbf{V}$$\mathbf V$ 进行参数化，也可以通过矩阵 ${\mathbf{M}}_{I,I},{\mathbf{M}}_{T,T},{\mathbf{M}}_{I,T}$$\mathbf M_{I,I},\mathbf M_{T,T},\mathbf M_{I,T}$ 定义的双线性函数进行参数化。 这提供了 application-specific 的方式来建模异质关系的灵活性。

2. 对象之间的交互被表示为网络中的异质链接。我们假设：如果两个对象是连接的，则它们之间的相似性应该比孤立对象之间的相似性更大，从而反映这一事实（即，对象是连接的）。

   注意，这里仅考虑一阶邻近性，即直接连接关系。

   考虑两个图像 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 和 ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$。为了对链接信息进行编码，我们设计了一个 pairwise 决策函数 $d({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)$$d\left(\mathbf{\vec x}_i ,\mathbf{\vec x}_j\right)$ ：

   $$\begin{array}{c}d({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)\{\begin{array}{ll}>0,& \text{if }{A}_{i,j}=1\\ <0,& \text{else}\end{array}\end{array}$$

   注意，要推断 $d(\cdot ,\cdot )$$d(\cdot,\cdot)$，我们不需要知道 $\mathbf{A}$$\mathbf A$ 的相应元素值，也不要求异质顶点为 in-sample 。这意味着该方法具有泛化能力从而嵌入 unseen 顶点。

   这句话的意思是，$d(\cdot ,\cdot )$$d(\cdot,\cdot)$ 的计算仅与 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 和 ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ 本身有关，与链接权重无关、也与是否存在链接无关。对于 unseen 的顶点，我们也可以计算 $d(\cdot ,\cdot )$$d(\cdot,\cdot)$ ，从而预测它与其它顶点之间是否存在链接。

   对于所有顶点 $v_i,v_j\in {\mathcal{V}}_I$$v_i,v_j\in \mathcal V_I$，考虑 $d({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=s({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)-t_{I,I}$$d\left(\mathbf{\vec x}_i ,\mathbf{\vec x}_j\right) = s\left(\mathbf{\vec x}_i ,\mathbf{\vec x}_j\right) - t_{I,I}$ ，其中 $t_{I,I}$$t_{I,I}$ 为基于关系的 bias 值。则损失函数可以定义为：

   $$L({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\log (1+\exp (-A_{i,j}\times d({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)))$$

   这可以视为由网络链接引导的二元逻辑回归。text-text 损失函数和 image-text 损失函数也是类似的，只需要将 $s(\cdot )$$s(\cdot)$ 替换为相应模态的损失函数即可。类似地，$t_{T,T}$$t_{T,T}$ 和 $t_{I,T}$$t_{I,T}$ 表示相应的、基于关系的 bias 值。

   该损失函数仅捕获一阶邻近性（即局部网络结构），没有捕获高阶邻近性（既全局网络结构）。

   该损失函数迫使相连的顶点之间的 embedding 是相似的、不相连的顶点之间的 embedding 是不相似的。这就是为什么 $A_{i,j}$$A_{i,j}$ 取值为 $\{+1,-1\}$$\{+1,-1\}$，和传统邻接矩阵不同的原因。

   最终我们的目标函数如下：

   $$\begin{array}{c}\underset{\mathbf{U},\mathbf{V}}{min}\frac{1}{N_{I,I}}\sum _{v_i,v_j\in {\mathcal{V}}_I}L({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)+\frac{{\lambda }_1}{N_{T,T}}\sum _{v_i,v_j\in {\mathcal{V}}_T}L({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)+\frac{{\lambda }_2}{N_{I,T}}\sum _{v_i\in {\mathcal{V}}_I,v_j\in {\mathcal{V}}_T}L({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{z}}}_j)\\ +{\lambda }_3(||\mathbf{U}|{|}_F^2+||\mathbf{V}|{|}_F^2)\end{array}$$

   其中：

   • $N_{I,I}$$N_{I,I}$ 表示image-image 链接的数量，即 $|{\mathcal{E}}_{I,I}|$$|\mathcal E_{I,I}|$ ；$N_{T,T}$$N_{T,T }$ 表示text-text 链接的数量，即 $|{\mathcal{E}}_{T,T}|$$|\mathcal E_{T,T}|$ ；$N_{I,T}$$N_{I,T}$ 表示 image-text 链接的数量，即 $|{\mathcal{E}}_{I,T}|$$|\mathcal E_{I,T}|$ 。

   • ${\lambda }_1,{\lambda }_2,{\lambda }_3$$\lambda_1,\lambda_2,\lambda_3$ 为平衡系数，用于平衡不同类型损失以及正则化项。$||\cdot |{|}_F^2$$||\cdot||_F^2$ 为矩阵的 F 范数。

   • $t_{I,I},t_{T,T},t_{I,T}$$t_{I,I},t_{T,T},t_{I,T}$ 等bias 值既可以从数据中学习得到，也可以设为固定值。为简单考虑，我们都设置为固定值。

   该最优化问题可以通过坐标下降法（coordinate descent ）得到有效解决，每次固定一个变量从而求解另一个变量：首先固定参数 $\mathbf{V}$$\mathbf V$ 从而求解参数 $\mathbf{U}$$\mathbf U$，然后固定参数 $\mathbf{U}$$\mathbf U$ 从而求解参数 $\mathbf{V}$$\mathbf V$。

1.1.2 深度 HNE

1. 目前为止，我们已经证明了我们的损失函数融合了网络结构，从而将不同异质成分（heterogeneous component ）映射到统一的潜在空间。然而，这种 embedding 函数仍然是线性的，可能缺乏建模复杂网络链接的能力。接下来我们引入深度学习框架。

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

   • 手动构造顶点的feature representation ：对于文本顶点使用其 TF-IDF 向量，对于图像顶点使用其原始 RGB 像素点拼接而成的向量。

   • 将不同的feature representation 嵌入到公共的低维空间中。

   这里我们通过深度学习将 feature representation 的 learning 和 embedding 合并在一起。

2. feature representation learning：

   • 定义图像特征抽取的非线性函数为 $p_{{\mathcal{D}}_I}(\cdot )$$p_{\mathcal D_I}(\cdot)$，其参数为 ${\mathcal{D}}_I$$\mathcal D_I$ 。通常我们使用 CNN 来抽取图像特征。下图为一个图像特征抽取模型，它由五个卷积层、两个全连接层组成。所有层都采用 ReLU 非线性激活函数。该模块称作 deep image 模块。

     

   • 定义文本特征抽取的非线性函数为 $q_{{\mathcal{D}}_T}(\cdot )$$q_{\mathcal D_T}(\cdot)$ ，其参数为 ${\mathcal{D}}_T$$\mathcal D_T$ 。由于文本是非结构化的，不包含空间信息，因此通常使用全连接层FC 对文本的 TF-IDF 输入来抽取特征。该模块称作 deep text 模块。

   则我们的损失函数变为：

   $$\begin{array}{c}\underset{\mathbf{U},\mathbf{V},{\mathcal{D}}_I,{\mathcal{D}}_T}{min}\frac{1}{N_{I,I}}\sum _{v_i,v_j\in {\mathcal{V}}_I}L(p_{{\mathcal{D}}_I}({\mathbf{X}}_i),p_{{\mathcal{D}}_I}({\mathbf{X}}_j))+\frac{{\lambda }_1}{N_{T,T}}\sum _{v_i,v_j\in {\mathcal{V}}_T}L(q_{{\mathcal{D}}_T}({\overrightarrow{\mathbf{z}}}_i),q_{{\mathcal{D}}_T}({\overrightarrow{\mathbf{z}}}_j))\\ +\frac{{\lambda }_2}{N_{I,T}}\sum _{v_i\in {\mathcal{V}}_I,v_j\in {\mathcal{V}}_T}L(p_{{\mathcal{D}}_I}({\mathbf{X}}_i),q_{{\mathcal{D}}_T}({\overrightarrow{\mathbf{z}}}_j))+{\lambda }_3(||\mathbf{U}|{|}_F^2+||\mathbf{V}|{|}_F^2)\end{array}$$

3. feature representation embedding：我们可以通过一个额外的线性embedding layer 来级联deep image 模块和 deep text 模块。

   定义 ${\tilde{p}}_{{\mathcal{D}}_I^{\prime }}(\mathbf{X})={\mathbf{U}}^{\mathrm{\top }}{p}_{{\mathcal{D}}_I}(\mathbf{X})$$\tilde p_{\mathcal D^\prime_I}(\mathbf X) = \mathbf U^\top p_{\mathcal D_I }(\mathbf X)$ ，其中 ${\mathcal{D}}_I^{\prime }={\mathcal{D}}_I\cup \{\mathbf{U}\}$$\mathcal D_I^\prime = \mathcal D_I\cup \{\mathbf U\}$ 。定义 ${\tilde{q}}_{{\mathcal{D}}_T^{\prime }}(\overrightarrow{\mathbf{z}})={\mathbf{V}}^{\mathrm{\top }}{q}_{{\mathcal{D}}_T}(\overrightarrow{\mathbf{z}})$$\tilde q_{\mathcal D^\prime_T}(\mathbf{\vec z}) = \mathbf V^\top q_{\mathcal D _T}(\mathbf {\vec z})$ ，其中 ${\mathcal{D}}_T^{\prime }={\mathcal{D}}_T\cup \{\mathbf{V}\}$$\mathcal D_T^\prime = \mathcal D_T\cup \{\mathbf V\}$ 。则目标函数变为：

   $$\begin{array}{c}\underset{{\mathcal{D}}_I^{\prime },{\mathcal{D}}_T^{\prime }}{min}\frac{1}{N_{I,I}}\sum _{v_i,v_j\in {\mathcal{V}}_I}{L}^{\prime }({\tilde{p}}_{{\mathcal{D}}_I^{\prime }}({\mathbf{X}}_i),{\tilde{p}}_{{\mathcal{D}}_I^{\prime }}({\mathbf{X}}_j))+\frac{{\lambda }_1}{N_{T,T}}\sum _{v_i,v_j\in {\mathcal{V}}_T}{L}^{\prime }({\tilde{q}}_{{\mathcal{D}}_T^{\prime }}({\overrightarrow{\mathbf{z}}}_i),{\tilde{q}}_{{\mathcal{D}}_T^{\prime }}({\overrightarrow{\mathbf{z}}}_j))\\ +\frac{{\lambda }_2}{N_{I,T}}\sum _{v_i\in {\mathcal{V}}_I,v_j\in {\mathcal{V}}_T}{L}^{\prime }({\tilde{p}}_{{\mathcal{D}}_I^{\prime }}({\mathbf{X}}_i),{\tilde{q}}_{{\mathcal{D}}_T^{\prime }}({\overrightarrow{\mathbf{z}}}_j))\end{array}$$

   其中：

   • 我们使用 dropout 代替了 $L_2$$L_2$ 正则化项，因此上式没有 ${\lambda }_3$$\lambda_3$ 对应的项

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

     $$L^{\prime }(\overrightarrow{\mathbf{a}},\overrightarrow{\mathbf{b}})=\log (1+\exp (-A_{i,j}\overrightarrow{\mathbf{a}}\cdot \overrightarrow{\mathbf{b}}))$$

     与前面的 $L(\cdot ,\cdot )$$L(\cdot,\cdot)$ 相比，这里的损失函数移除了bias 项。

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

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

   • deep text 模块包含两个FC 全连接层，然后是一个线性 embedding 层。

     这里有些违反直觉。主流的 DNN 模型都是先通过一个 embedding 层，然后再通过 FC 层。

   • 线性 embedding 层的输出是公共潜在空间中的低维向量，该低维向量进一步送到预测层 prediction layer 来计算损失函数。

   • text-text 模块是对称的，下图中相同颜色的神经元共享相同的权重和偏差，箭头表示前向传播的方向。

   

5. HNE 的整体架构如下图所示，图中展示了三个模块，从左到右依次为 image-image 模块、image-text 模块、text-text 模块。这些模块分别连接到prediction layer 来计算损失函数。下图中，相同的颜色代表共享权重。箭头表示前向传播和反向传播的方向。

   

6. 讨论：

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

   • 由于深度学习是高度非线性和非凸的，因为无法保证全局最优解。参数的初始化对模型性能至关重要。文献表明，即使最终任务与 pre-training 任务不同，精心设计的 pre-training 也可以显著提高最终任务的表现。

   • 值得一提的是，我们提出的方法是无监督学习方法，因此可以作为下游fine-tuning 微调阶段的预训练（pretraining ）步骤来使用。换句话讲，如果我们想对网络顶点进行分类，那么我们可以从 embedding layer 获得最终特征并应用相应的机器学习算法。或者我们也可以将prediction layer 替换为 softmax 层，然后进行微调为 task-specific 的端到端监督学习深度神经网络。

1.2 实验

1. 数据集：我们使用来自现实世界社交网络的两个公开数据集。所有实验结果均在五次不同的运行中取均值。

   • BlogCatalog：一个社交博客网络，博主可以在预定义的类别下对其博客进行分类。这样的分类用于定义类标签，而 following（即，关注）行为用于构建博主之间的链接。我们使用每个博主的所有博客内容的 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 个链接，从而构建稀疏的邻接矩阵 $\mathbf{A}$$\mathbf A$ 。

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

2. 网络重建（Network Reconstruction）：在分类、聚类或检索任务之前，我们首先对网络链接重建的质量进行基本的、直观的评估，从而验证我们的假设。我们从 BlogCatalog 数据集中随机选择 500 个顶点，然后可视化其链接，其中每个顶点的颜色代表其类别。可以看到：

   • 相对而言，社交“关注” 关系倾向于将具有相似属性的用户聚合在一起。

   • 绝对而言，这种聚合之中存在大量噪音，其中59.89% 的链接连接到了不同类别的顶点。

     这是可以理解的，因为即使 HNE 百分之百地重建了网络，但是原始网络本身就存在大量的、不同类别的顶点链接在一起的情况。

   

   我们评估了算法学习 embedding 过程中，训练集每个 mini-batch 的链接重建准确率 ：预估正确的 pair 对的数量， 除以所有的 pair 对的数量。其中 mini-batch = 128 。结果如下图所示，其中横轴表示 epoch ，每个 epoch 包含 500 个 step 。红线表示每个 epoch 重建准确率的均值。可以看到：随着学习的推进，算法能够正确地重建 80% 以上的链接，而一开始的准确率只有 55%。

   注意，这里是训练集的重建准确率，而不是测试集的。

   

1.2.1 BlogCatalog 数据集

1. 分类任务：在 BlogCatalog 数据集上，我们将我们的 feature learning 方法和以下 feature learning 方法进行比较：

   • 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 学习对于有监督分类任务提供了很好的初始化，并能进一步提升性能。

    

   

2. 聚类任务：我们还比较了BlogCatalog 数据集上不同方法得到的 embedding 的聚类表现。与分类任务相比，聚类任务是完全无监督的，并很大程度上依赖于相似性度量函数。这里我们采用最常见的余弦相似度。我们根据聚类后的结果以及label 信息，同时给出了准确率和归一化互信息 （ normalized mutual information :NMI ）作为评估指标。

   结果表明：

   • 类似分类任务，仅使用链接会带来最差的结果。这可能是因为：在没有全局内容信息指导的条件下，相似性往往是局部的，并且对噪音非常敏感。

   • 仅内容相似性不足以捕获关系信息。

   • 通过链接和内容的简单组合，这可以提供与其它 baseline 相当的性能。

   • 我们的 HNE 模型优于所有其它 baseline 模型并达到 SOTA 的水平。

   

1.2.2 NUS-WIDE 数据集

1. 与 BlogCatalog 相比，NUS-WIDE 数据集构成了一个包含图像、文本的异质网络。我们将在分类任务、跨模态检索（cross-modal retrieval） 任务中评估 HNE 的性能。注意，跨模态检索任务在前一个数据集的同质场景中是不可行的。

2. 分类任务：鉴于 BlogCatalog 的异质场景，我们将我们的方法和以下无监督的、能够处理多模态输入的 baseline 进行比较：

   • Canonical Correlation Analysis: CCA：根据输入的多个数据源的关系将它们嵌入到共同的潜在空间。

   • DT：一种迁移学习方法，通过潜在 embedding 来减少图像和文本之间的语义距离。

   • LHNE：HNE 的线性版本。

   我们为所有其它baseline 方法抽取了 4096 维的特征，但是由于我们的HNE 方法是端到端的，因此不需要为图像手动抽取特征。由于 NUS-WIDE 数据集是类别不平衡的，因此我们用平均精度（ average precsision:AP ）来评估每种可能的标签结果的分类性能。

   AP 就是P-R 曲线下的面积，mAP 就是所有类别的 AP 的均值。事实上，AP 就是把 recall 的取值根据 $\{0,0.1,\cdots ,0.9,1.0\}$$\{0,0.1,\cdots,0.9,1.0\}$ 一共 11 个水平（也可以划分更小的单位），然后取对应的 Precision 的平均值。在 P-R 曲线上这等价于曲线的线下面积。

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

   我们比较了三种配置：

   • image only：仅在图像顶点上学习 embedding，然后训练 SVM、执行分类测试。

   • text only：仅在文本顶点上学习 embedding，然后训练 SVM、执行分类测试。

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

   可以看到：

   • 对于所有方法，仅使用文本数据进行分类效果最差。这可能是由于：和图像输入相比，文本输入非常稀疏。

   • 仅使用线性的 HNE ，我们就可以获得与 DT 相当的结果，并且优于 CCA。

   • 非线性HNE 在所有三种配置中进一步提高性能，这表明使用非线性函数同时优化feature learning 和潜在 embedding 的优势。

   

3. 跨模态检索：为进一步验证 HNE 的能力，我们在跨模态检索任务中将我们的方法和 baseline 进行比较。我们的目标是希望通过文本 query 来召回对应的图片。在所有 81 个 label 中，有 75 个出现在 TF-IDF 文本向量中。因此我们基于这 75 个label word 来构建 query 向量：

   $${\text{query}}_i=(0,0,\cdots ,0,1,0,\cdots ,0{)}^{\mathrm{\top }}$$

   其中query 向量长度为 1000， 除了第 $i$$i$ 个 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 可以提升性能。

   

1.2.3 其它

1. 训练收敛性：我们展示了HNE 在 BlogCatalog 数据集上目标函数的变化，从而验证模型的收敛性。其中 x 轴代表 epoch 。可以看到：目标函数经过 60 个 epoch 的持续性降低之后趋向于平稳，这表明算法可以收敛到稳定结果。