图的表达2

十七、PTE[2015]

1. 学习有意义且有效的文本（例如word、document）的 representation ，是许多机器学习任务（例如文本分类、文本聚类、文本检索）的关键前提条件。传统上，每个word都相互独立地表示，并且每个document都表示为 bag-of-words。然而，这两种representation 都存在数据稀疏、多义性polysemy 、同义性synonymy 等问题，因为在这两种representation 中不同word之间的语义相关性semantic relatedness 通常被忽略。

   word和document的分布式representation 通过在低维空间中表达word和document，从而有效地解决了这个问题。在这个低维空间中，相似的word/document彼此紧密地嵌入。这些方法的基本思想来自于分布式假设 distributional hypothesis ：一个单词的意义是由它的使用环境所形成的 （you shall know a word by the company it keeps ）。 《Distributed representations of words and phrases and their compositionality》 提出了一种简单而优雅的 word embedding 模型，称作 SkipGram。SkipGram 使用 target word 的 embedding 来预测局部窗口 local window 中每个单独的 context word 的 embedding 。《Distributed representations of sentences and documents》 进一步扩展了这一思想，并提出了 Paragraph Vector 从而嵌入任意的文本片段，例如sentence 和document。其基本思想是：使用 sentence/document 的embedding 来预测 sentence/document 中word的 embedding 。和也利用 word context 的分布式相似性distributional similarity 的其它经典方法（如布朗聚类 Brown clustering、最近邻法）相比，这些 text embedding 方法已被证明是非常有效的，可以在单台机器上扩展到数百万个 document 。

   由于采用无监督学习，通过这些 text embedding 模型学到的 representation 足够通用，可以应用于分类classification 、聚类clustering、以及排序ranking 等各种任务。然而，和端到端的复杂的深度学习方法（如卷积神经网络）相比时，text embedding 的性能通常在特定任务上达不到要求。这毫不奇怪，因为深度神经网络在学习数据 representation 时充分利用了可用于任务的 label 信息。大多数 text embedding 方法在学习 representation 时都无法考虑 label 信息。只有在使用训练好的 representation 作为特征来训练分类器时，label 才会被使用。换句话讲，无监督的 text embedding 对于不同的任务是可泛化generalizable 的，但是对于特定任务的预测能力较弱。

   尽管存在这一缺陷，但是和深度神经网络相比，text embedding 方法仍有相当大的优势。

   • 首先，深度神经网络（尤其是卷积神经网络）的训练是计算密集型的，在处理大量数据的时候通常需要多个 GPU 或 CPU 集群。
   • 其次，卷积神经网络通常假设大量的标记样本可用，这在许多任务中是不现实的。对于容易获取的未标记数据，卷积神经网络通常使用预训练的方式来间接利用。
   • 第三，卷积神经网络的训练需要多许多超参数进行详尽的调优，即使对于专家而言也是非常耗时的，而对于非专家而言是不可行的。

   另一方面，像 SkipGram 这样的 text embedding 方法效率更高、更容易调优、并且天然地适应于未标记数据。

   在论文 《PTE:Predictive Text Embedding through Large-scale Heterogeneous Text Networks》 中，作者通过提出 predictive text embedding: PTE 来填补这一空白。PTE 具有无监督 text embedding 的优点，但是在 representation learning 过程中自然地利用了标记信息。通过 PTE，我们可以从有限的标记样本和大量的未标记样本中联合学习有效的低维 representation 。与无监督 embedding 相比，这种 representation 针对特定任务进行了优化，就像卷积神经网络所作的那样。即，PTE 学到的 representation 对特定的分类任务具有很强的预测能力。

   PTE 自然地扩展了作者之前的无监督信息网络 embedding 工作（《Line: Large-scale information network embedding》），并首先提出通过异质文本网络heterogeneous text networt 学习word 的低维 embedding 。该网络对 word-word、word-document、word-label 之间不同 level 的共现信息co-occurrence information 进行编码。该网络被嵌入到一个低维向量空间中，该空间保留了网络中顶点之间的二阶邻近性second-order proximity 。任意一段文本（例如 sentence 或 document）的 representation 可以简单地推断为 word representation 的均值，结果证明这是非常有效的。整个优化过程仍然非常高效，在单台机器上可以扩展到数百万个 document 和数十亿个 token 。

   论文对现实世界的文本语料库进行了广泛的实验，包括 long document 和 short document 。实验结果表明：PTE 在各种文本分类任务中显著优于 state-of-the-art 的无监督 embedding。与用于文本分类的端到端卷积神经网络相比，PTE 在 long document 上表现更好、在 short document 上表现相当。与卷积神经网络相比，PTE 具有各种优势，因为它更高效、有效地利用大规模未标记数据，并且对模型超参数不太敏感。作者相信PTE 的探索指向了一个学习 text embedding 的方向，该方向可以在特定任务中与深度神经网络进行正面竞争。

   总而言之，论文的贡献如下：

   • 论文提出以半监督的方式学习 predictive text embedding。未标记数据和标记信息被集成到一个异质文本网络中，该网络包含不同 level 的文本共现信息。
   • 论文提出了一种高效的算法 PTE，它通过将异质文本网络嵌入到低维空间中来学习文本的分布式 representation 。该算法非常有效，几乎没有需要调优的超参数。
   • 论文使用各种真实世界的数据集进行了广泛的实验，并将 PTE 与无监督 text embedding、卷积神经网络进行了比较。

2. 相关工作：我们的工作主要涉及分布式文本 representation learning 和信息网络 embedding 。

   • Distributed Text Embedding：文本的分布式 representation 已被证明在许多自然语言处理任务中非常有效，例如单词类比 word analogy、词性标注 POS tagging、parsing、语言建模 language modeling 、以及情感分析sentiment analysis 。现有的方法通常可以分为两类：无监督方法、监督方法。

     • 最近提出的无监督方法通常通过在局部上下文 local context （例如 SkipGram）或者 document 级别（例如 Paragraph Vector ），利用 word co-occurrence 来学习 word/document 的 embedding 。这些方法非常有效，可以扩展到数百万个 document。
     • 监督方法通常基于深度神经网络架构，例如 recursive neural tensor network: RNTN、convolutional neural network: CNN。在 RNTN 中，每个 word 都嵌入到一个低维向量中，并且通过在 parse tree 中的子短语 sub-phrase 或者 word 上应用相同的、基于张量tensor-based 的组合函数composition function 来递归学习短语 phrase 的 embedding 。在 CNN 中，每个 word 也用一个向量来表示，并且在 sentence 的不同位置的上下文窗口上应用相同的卷积核，然后是一个最大池化层和一个全连接层。

     这两类方法之间的主要区别在于它们如何在 representation learning 阶段利用标记信息和未标记信息。无监督方法在 representation learning 时不包含标记信息，仅在将数据转换为学到的 representation 之后，才使用 label 来训练分类器。RNTN 和 CNN 将 label 直接结合到 representation learning 中，因此学到的 representation 特别针对分类任务进行了调优。然而，为了融合未标记的样本，这些神经网络通常必须使用间接方法，例如使用无监督方法预训练 word embedding 。和这两类方法相比，PTE 以半监督方式学习 text embedding，representation learning 算法直接利用标记信息和大量的未标记数据。

     与 predictive word embedding 类似的另一项工作是 《Learning word vectors for sentiment analysis》，该工作学习特别针对情感分析调优的 word embedding 。然而，他们的方法无法扩展到数百万个 document，也无法推广到其它分类任务。

   • Information Network Embedding：我们的工作还与 network/graph embedding 问题有关，因为 PTE 的 word representation 是通过异质文本网络 heterogeneous text network 学到的。

     将 network/graph 嵌入到低维空间，这在各种应用中非常有用，例如节点分类、链接预测。MDS、IsoMap、Laplacian eigenmap 等经典 graph embedding 算法不适用于嵌入包含数百万个顶点、数十亿条边的大型网络。

     最近有一些工作试图嵌入非常大的现实世界网络。《Deepwalk: Online learning of social representations》 提出了一种叫做 DeepWalk 的 network embedding 模型，该模型在网络上使用截断的随机游走，并且仅适用于具有二元边的网络。我们先前的工作提出了一种新的大规模网络嵌入模型，称作 LINE。LINE 适用于任意类型的信息网络，无向或有向、二元边或者带权边。LINE 模型优化了一个目标函数，该目标函数旨在保持局部网络结构 local network structure 和全局网络结构 global network structure 。DeepWalk 和 LINE 都是无监督的，只能处理同质网络homogeneous network 。PTE 使用的 network embedding 算法扩展了 LINE 从而处理异质网络（网络中存在多种类型的顶点和边）。

17.1 模型

17.1.1 基本概念

1. 让我们从正式定义 predictive text embedding 问题（通过异质文本网络）来开始。与学习文本的通用语义representation 的无监督 text embedding 方法（包括 SkipGram 和 Paragraph Vector ）相比，我们的目标是学习针对给定文本分类任务优化的文本 representation 。换句话讲，我们期待 text embedding 对给定任务的性能具有很强的预测能力。基本思想是：在学习 text embedding 时结合标记信息和未标记信息。为了实现这一点，首先需要有一个统一的 representation 对这两类信息（标记的和未标记的）进行编码。在本文中，我们提出了不同类型的网络来实现这一点，包括 word-word co-occurrence network、word-document network、word-label network 。

2. word-word co-occurrence network：word-word 共现网络表示为 $G_{w,w}=(\mathcal{V},{\mathcal{E}}_{w,w})$$G_{w,w} = (\mathcal V, \mathcal E_{w,w})$，它捕获了未标记数据的局部上下文local context 中的 word 共现信息。$\mathcal{V}$$\mathcal V$ 为 word 的词表 vocabulary，${\mathcal{E}}_{w,w}$$\mathcal E_{w,w}$为 word 之间的边的集合（共现关系）。word $v_i$$v_i$ 和 $v_j$$v_j$ 之间的边的权重 $w_{i,j}$$w_{i,j}$ 定义为：这两个word 在给定窗口大小的上下文窗口中同时出现的次数。

3. word-word 网络捕获局部上下文中的 word 共现，这是现有 word embedding 方法（如 SkipGram ）使用的基本信息。除了局部上下文之外，document level 的 word 共现也在经典的文本 representation 中被广泛探索，例如统计主题模型 statistical topic model（如 latent Dirichlet allocation: LDA）。为了捕获 document level 的 word 共现，我们引入了另一个网络，即 word-document 网络。

4. word-document network： word-document 网络表示为二部图 $G_{w,d}=(\mathcal{V}\cup \mathcal{D},{\mathcal{E}}_{w,d})$$G_{w,d} = ( \mathcal V\cup \mathcal D , \mathcal E_{w,d})$ ，其中 $\mathcal{D}$$\mathcal D$ 为 document 的集合，$\mathcal{V}$$\mathcal V$ 为 word 的集合，${\mathcal{E}}_{w,d}$$\mathcal E_{w,d}$ 为 word 到 document 的链接构成的边集合。word $v_i$$v_i$ 和 document $d_j$$d_j$ 之间的边的权重 $w_{i,j}$$w_{i,j}$ 定义为：word $v_i$$v_i$ 出现在 document $d_j$$d_j$ 中的频次。

5. word-word 网络和 word-document 网络对大规模语料库中的未标记信息进行编码，在局部上下文 level 和 document level 捕获 word 共现。为了对标记信息进行编码，我们引入了 word-label 网络，该网络在 category-level 捕获 word 共现。

6. word-label network：word-label 网络表示为二部图 $G_{w,l}=(\mathcal{V}\cup \mathcal{L},{\mathcal{E}}_{w,l})$$G_{w,l} = (\mathcal V\cup \mathcal L,\mathcal E_{w,l})$，其中 $\mathcal{L}$$\mathcal L$ 为 class 的集合，$\mathcal{V}$$\mathcal V$ 为 word 的集合，${\mathcal{E}}_{w,l}$$\mathcal E_{w,l}$ 为 word 到 class 的链接构成边的集合。$G_{w,l}$$G_{w,l}$ 捕获了 category-level 的 word 共现。word $v_i$$v_i$ 和 class $c_j$$c_j$ 之间的边的权重 $w_{i,j}$$w_{i,j}$ 定义为： $w_{i,j}=\sum _{(d:l_d=j)}{n}_{d,i}$$w_{i,j} = \sum_{(d:l_d = j)} n_{d,i}$ ，其中 $n_{d,i}$$n_{d,i}$ 为 document $d$$d$ 中 word $v_i$$v_i$ 出现的频次，$l_d$$l_d$ 为 document $d$$d$ 的 class label 。

7. 上述三种网络可以进一步融合为一个异质文本网络heterogeneous text network （如下图所示）。

   Heterogeneous Text Network：异质文本网络是由标记文本数据和未标记文本数据共同构建的 word-word 网络、word-document 网络、word-label 网络的组合。它捕获不同 level 的 word 共现，并同时包含标记信息和未标记信息。

   注意，异质文本网络的定义可以推广到融合其它类型的网络，例如 word-sentence 网络、word-paragraph 网络、document-label 网络等等。在这项工作中，我们使用三种类型的网络（word-word、word-document、word-label）作为说明性示例。我们特别关注 word 网络，以便首先将 word 表示为低维空间。然后可以通过聚合 word representation 来计算其它文本单元（如 stentence 或 paragraph）的 representation 。

   子网的构建需要结合具体任务，并且对任务性能产生重大影响。但是论文并未给出子网构建的原则。可以借鉴的是：这里的 word-word 捕获局部共现、word-document 捕获全局共现。

   

8. 最后，我们正式定义 predictive text embedding 问题如下：

   Predictive Text Embedding：给定具有标记信息和未标记信息的大量文本数据，predictive text embedding 问题旨在通过将由文本数据构建的异质文本网络嵌入到低维向量空间中从而学习 word 的低维 representation 。

9. 接下来我们将介绍通过异质文本网络学习 predictive text embedding 的方法。我们的方法首先将异质文本网络嵌入到低维空间来学习 word 的向量 representation ，然后根据学到的 word embedding 推断 text embedding 。由于异质文本网络由三个二部图组成，我们首先介绍一种嵌入单个二部图的方法。

17.1.2 二部图 Embedding

1. 在我们之前的工作中，我们引入了 LINE 模型来学习大规模信息网络的 embedding。LINE 主要是为同质网络而设计的，即具有相同类型节点的网络。LINE 无法直接应用于异质网络，因为不同类型边的权重不具有可比性。在这里，我们首先将 LINE 模型用于嵌入二部图。基本思想是：利用顶点之间的二阶邻近性，假设具有相似邻域的顶点彼此相似，因此应该在低维空间中紧密地表示。

   对于二部图，假设顶点 $A$$A$ 和顶点 $B$$B$ 具有相似的邻域，则暗示了 $A$$A$ 和 $B$$B$ 的顶点类型相同。

2. 给定一个二部图 $G=({\mathcal{V}}_A\cup {\mathcal{V}}_B,\mathcal{E})$$G=(\mathcal V_A\cup \mathcal V_B, \mathcal E)$，其中 ${\mathcal{V}}_A$$\mathcal V_A$ 和 ${\mathcal{V}}_B$$\mathcal V_B$ 是不同类型的、两个不相交的顶点集合，$\mathcal{E}$$\mathcal E$ 是它们之间的边的集合（相同类型顶点之间不存在边，只有不同类型顶点之间才存在边）。我们首先将集合 ${\mathcal{V}}_B$$\mathcal V_B$ 中顶点 $v_j$$v_j$ 生成集合 ${\mathcal{V}}_A$$\mathcal V_A$ 中顶点 $v_i$$v_i$ 的条件概率定义为：

   $$p(v_i\mid v_j)=\frac{\exp ({\overrightarrow{\mathbf{u}}}_i\cdot {\overrightarrow{\mathbf{u}}}_j)}{\sum _{v_i^{\prime }\in {\mathcal{V}}_A}\exp ({\overrightarrow{\mathbf{u}}}_{i^{\prime }}\cdot {\overrightarrow{\mathbf{u}}}_j)}$$

   其中：${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 为 ${\mathcal{V}}_A$$\mathcal V_A$ 中顶点 $v_i$$v_i$ 的 embedding 向量，${\overrightarrow{\mathbf{u}}}_j$$\mathbf{\vec u}_j$ 为 ${\mathcal{V}}_B$$\mathcal V_B$ 中顶点 $v_j$$v_j$ 的 embedding 向量。

   对于 ${\mathcal{V}}_B$$\mathcal V_B$ 中的每个顶点 $v_j$$v_j$ ，上式给出了一个定义在 ${\mathcal{V}}_A$$\mathcal V_A$ 中所有顶点上的条件分布 $p(\cdot \mid v_j)$$p(\cdot\mid v_j)$ 。对于 ${\mathcal{V}}_B$$\mathcal V_B$ 中的每对顶点 $v_j,v_{j^{\prime }}$$v_j,v_{j^\prime}$，它们的二阶邻近性second-order proximity 可以由它们的条件分布 $p(\cdot \mid v_j)$$p(\cdot\mid v_j)$ 、 $p(\cdot \mid v_{j^{\prime }})$$p(\cdot\mid v_{j^\prime})$ 来决定。为了保持二阶邻近性，我们可以使条件分布 $p(\cdot \mid v_j)$$p(\cdot\mid v_j)$ 接近其经验分布 $\hat{p}(\cdot \mid v_j)$$\hat p (\cdot\mid v_j)$ ，这可以通过最小化以下目标函数来实现：

   $$O=\sum _{v_j\in {\mathcal{V}}_B}{\lambda }_j\text{dist}(\hat{p}(\cdot \mid v_j),p(\cdot \mid v_j))$$

   其中：

   • $\text{dist}(\cdot ,\cdot )$$\text{dist}(\cdot,\cdot)$ 为两个分布之间的距离函数，这里采用 KL-divergence 函数。
   • ${\lambda }_j$$\lambda_j$ 为顶点 $v_j$$v_j$ 在网络中的重要性，我们设置为顶点的 degree ：${\text{deg}}_j=\sum _i{w}_{i,j}$$\text{deg}_j = \sum_i w_{i,j}$ 。
   • 经验分布 $\hat{p}(\cdot \mid v_j)$$\hat p (\cdot\mid v_j)$ 定义为 $\hat{p}(v_i\mid v_j)=\frac{w_{i,j}}{{\text{deg}}_j}$$\hat p (v_i\mid v_j) = \frac{w_{i,j}}{\text{deg}_j}$ 。

   忽略常数项，则上述目标函数重写为：

   $$O=-\sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}\log p(v_i\mid v_j)$$

   我们可以采用带边采样edge sampling 和负采样 nagative sampling 的随机梯度下降法来求解该最优化问题。在梯度下降的每一步：

   • 首先以正比于权重 $w_{i,j}$$w_{i,j}$ 的概率随机采样一条二元边 binary edge $e=(v_i,v_j)$$e=(v_i,v_j)$ ，即 edge sampling 。
   • 然后通过noise distribution $p_n(j)$$p_n(j)$ 来随机采样若干条负边，即 nagative sampling 。

   采样过程解决了学习 network embedding 中随机梯度下降的重大缺陷。详细的优化过程可以参考 LINE 的原始论文。

3. word-word 网络、word-document 网络、word-label 网络的 embedding 都可以通过上述模型来学习。注意，word-word 网络本质上是一个二部图，可以将每条无向边视为两条有向边，并且将 ${\mathcal{V}}_A$$\mathcal V_A$ 视为源顶点的集合、${\mathcal{V}}_B$$\mathcal V_B$ 视为目标顶点的集合。因此，我们可以定义条件概率 $p(v_i\mid v_j),p(v_i\mid d_j),p(v_i\mid l_j)$$p(v_i\mid v_j), p(v_i\mid d_j),p(v_i\mid l_j)$ ，然后通过优化目标函数来学习 embedding 。

17.1.2 异质文本网络 Embedding

1. 异质文本网络由三个二部图组成：word-word 网络、word-document 网络、word-label 网络，其中 word 顶点在三个网络之间共享。为了学习异质文本网络的 embedding，一种直观的方法是共同嵌入三个二部图，这可以通过最小化以下目标函数来实现：

   $$\begin{array}{c}{O}_{\text{pte}}=O_{w,w}+O_{w,d}+O_{w,l}\\ O_{w,w}=-\sum _{(v_i,v_j)\in {\mathcal{E}}_{w,w}}{w}_{i,j}\log p(v_i\mid v_j)\\ O_{w,d}=-\sum _{(v_i,v_j)\in {\mathcal{E}}_{w,d}}{w}_{i,j}\log p(v_i\mid d_j)\\ O_{w,l}=-\sum _{(v_i,v_j)\in {\mathcal{E}}_{w,l}}{w}_{i,j}\log p(v_i\mid l_j)\end{array}$$

   上述目标函数可以通过不同的方式进行优化，具体取决于如何使用标记信息（即 word-label 网络）。

   • 一种解决方案是同时使用未标记数据（word-word 网络和 word-document 网络）和标记数据训练模型。我们称这种方法为联合训练 joint training 。
   • 另一种解决方案是首先使用未标记数据来学习 embedding，然后使用 word-label 网络来微调 embedding 。这是受到深度学习文献中预训练和微调 pre-training and fine-tuning 思想的启发。

2. 在联合训练中，所有三种类型的网络一起使用。优化目标 $O_{\text{pte}}$$O_\text{pte}$ 的直接解决方案是合并三个集合 ${\mathcal{E}}_{w,w},{\mathcal{E}}_{w,d},{\mathcal{E}}_{w,l}$$\mathcal E_{w,w},\mathcal E_{w,d},\mathcal E_{w,l}$ 中的所有边，然后执行边采样 edge sampling （在每个 step 中对边进行采样从而进行模型更新，采样概率与边的权重成正比）。然而，当网络是异质的时候，不同类型顶点之间的边的权重是不可比的。更合理的解决方案是从三组边中交替采样。

3. PTE 联合训练算法：

   • 输入：

     • 异质文本网络的三个子网 $G_{w,w},G_{w,d},G_{w,l}$$G_{w,w},G_{w,d},G_{w,l}$
     • 采样数量 $T$$T$
     • 负采样比例 $K$$K$

   • 输出：所有单词的 embedding $\mathbf{U}$$\mathbf U$

   • 算法步骤：

     循环迭代，直到迭代了 $T$$T$ 个 step 。迭代过程为：

     • 从 ${\mathcal{E}}_{w,w}$$\mathcal E_{w,w}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 。
     • 从 ${\mathcal{E}}_{w,d}$$\mathcal E_{w,d}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 和 document embedding 。
     • 从 ${\mathcal{E}}_{w,l}$$\mathcal E_{w,l}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 和 label embedding 。

4. PTE 预训练和微调算法：

   • 输入：

     • 异质文本网络的三个子网 $G_{w,w},G_{w,d},G_{w,l}$$G_{w,w},G_{w,d},G_{w,l}$
     • 采样数量 $T$$T$
     • 负采样比例 $K$$K$

   • 输出：所有单词的 embedding $\mathbf{U}$$\mathbf U$

   • 算法步骤：

     预训练阶段：循环迭代，直到迭代了 $T$$T$ 个 step 。迭代过程为：

     • 从 ${\mathcal{E}}_{w,w}$$\mathcal E_{w,w}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 。
     • 从 ${\mathcal{E}}_{w,d}$$\mathcal E_{w,d}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 和 document embedding 。

     微调阶段：循环迭代，直到迭代了 $T$$T$ 个 step 。迭代过程为：

     • 从 ${\mathcal{E}}_{w,l}$$\mathcal E_{w,l}$ 采样一条正边和 $K$$K$ 个负边，更新 word embedding 和 label embedding 。

5. Text Embedding：异质文本网络对不同 level 的 word co-occurrence 进行编码，这些编码是从未标记数据和特定分类任务的标记信息中提取的。因此，通过嵌入异质文本网络学习的 word representation 不仅更加鲁棒，而且针对该特定任务进行了优化。一旦学到了 word vector，就可以通过简单地对这段文本中 word 的向量求均值来获得任意一段文本的 representation 。即，一段文本 $d=\{w_1,w_2,\cdots ,w_n\}$$d=\{w_1,w_2,\cdots,w_n\}$的向量 representation 可以计算为：

   $$\overrightarrow{\mathbf{d}}=\frac{1}{n}\sum _{i=1}^n{\overrightarrow{\mathbf{u}}}_i$$

   其中 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 为 word $w_i$$w_i$ 的 embedding 向量。

   事实上，word embedding 的均值是最小化以下目标函数的最优解：

   $$O=\sum _{i=1}^n\text{loss}({\overrightarrow{\mathbf{u}}}_i,\overrightarrow{\mathbf{d}})$$

   其中 $\text{loss}(\cdot ,\cdot )$$\text{loss}(\cdot,\cdot)$ 为 word embedding 和 text embedding 之间的、欧式距离的损失函数。

   与之相关的是 paragraph vector 的推断过程，它的目标函数相同但是具有不同的损失函数：

   $$\text{loss}({\overrightarrow{\mathbf{u}}}_i,\overrightarrow{\mathbf{d}})=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{u}}}_i\cdot \overrightarrow{\mathbf{d}})}$$

   然而这个损失函数对应的目标函数没有闭式解close form solution ，因此必须通过梯度下降算法来优化。

17.2 实验

1. 数据集：我们选择了长文document、短document两种类型的数据集：

   • 长document数据集：

     • 20newsgroup 数据集：广泛使用的文本分类数据集，包含 20 个类别。
     • wiki 数据集：2010年 4 月的维基百科数据集，包含大约 200 万篇英文文章。我们仅保留 2010 年维基百科中出现的常见词汇。我们选择了七种不同类别，包括 Art, History, Human, Mathematics, Nature, Technology, Sports 。每种类别我们随机选择 9000 篇文章作为标记的document 来训练。
     • Imdb 数据集：一个情感分类数据集。为避免训练数据和测试数据之间的分布偏差，我们随机混洗了训练数据和测试数据。
     • RCV1 数据集：一个大型文本分类基准语料库。我们从数据集中抽取了四个子集，包括 Corporate, Economics, Government, Market 。在 RCV1 数据集中，文档已经被处理为 bag-of-word: BOW 的格式，因此 word 的顺序已经被丢失。

   • 短document数据集：

     • DBLP 数据集：包含来自计算机科学领域论文的标题。我们选择了六个领域的论文，包括 database, articial intelligence, hardware, system, programming languages, theory 等。对于每个领域，我们选择该领域具有代表性的会议并收集该会议中发表的论文作为标记的 document 。

• MR 数据集：一个电影评论数据集，每条评论仅包含一个 sentence 。

  • Twitter 数据集：用于情感分类的 Tweet 语料库。我们从中随机抽取了 120 万 Tweets 然后拆分为训练集和测试集。

我们并没有在原始数据上执行进一步的文本归一化text normalization ，如删除停用词或者词干化。下表给出了数据集的详细统计信息。

2. baseline 方法：我们将 PTE 算法和其它的文本数据 representation learning 算法进行比较，包括经典的 BOW 算法、 state-of-the-art 的无监督 text embedding 、以及 state-of-the-art 的监督 text embedding 方法。

   • BOW：经典的 BOW 方法。每篇文档使用一个 $|\mathcal{V}|$$|\mathcal V|$ 维的向量来表达，向量第 $i$$i$ 个元素为word $v_i$$v_i$ 的 TFIDF 值。

   • SkipGram：根据 SkipGram 训练得到 word embedding，然后我们使用word embedding 的均值来作为 document embedding 。

   • PVDBOW：一种 paragraph embedding 模型，其中document内word 的顺序被忽略。

   • PVDM ：另一种paragraph embedding 模型，其中document内word 的顺序被考虑。

   • LINE：我们之前的工作提出的大规模信息网络 embedding 模型。我们使用 LINE 模型分别学习 word-word 网络和 word-dococument 网络，分别记作 $\text{LINE}(G_{w,w}),\text{LINE}(G_{w,d})$$\text{LINE}(G_{w,w}),\text{LINE}(G_{w,d})$。另外，我们也考虑联合学习 word-word 网络和 word-document 网络，记作 $\text{LINE}(G_{w,w},G_{w,d})$$\text{LINE}(G_{w,w},G_{w,d})$。

   • CNN：基于卷积神经网络 CNN 模型来监督学习 text embedding。尽管原始论文用于建模sentence，我们这里将其改编为适用于长文本在内的一般word 序列。尽管CNN 通常适用于完全标记的 documnet，但是它也可以通过无监督的 word embedding 从而对模型进行预训练来利用未标记数据，这被记作 CNN(pretrain)。

   • PTE：我们提出的、学习predictive text embedding 的方法。PTE 有多种变体，它们使用 word-word、word-document、word-label 的不同组合。

     • $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ 为仅使用 word-label 的版本。
     • $\text{PTE}(G_{w,w},G_{w,l})$$\text{PTE}(G_{w,w}, G_{w,l})$ 为使用 word-word 和 word-label 的版本。
     • $\text{PTE}(G_{w,d},G_{w,l})$$\text{PTE}(G_{w,d},G_{w,l})$ 为仅使用 word-document 和 word-label 的版本。
     • $\text{PTE(pretrain)}$$\text{PTE(pretrain)}$ 为使用 word-word 、word-document 进行无监督训练，然后使用 word-label 来微调的版本。
     • PTE(joint) 为联合训练异质文本网络的版本。

3. 实验配置：

   • SkipGram, PVDBOW, PVDM, PTE, PTE 模型：

     • 随机梯度下降的 mini-batch size 设为 1。
     • 学习率设为 ${\rho }_t={\rho }_0(1-t/T)$$\rho_t = \rho_0(1-t/T)$ ，其中 T 为总的迭代步数，${\rho }_0=0.025$$\rho_0 = 0.025$。
     • 负采样次数为 K=5。

   • SkipGram, PVDBOW, PVDM, PTE 模型：word-word 网络共现窗口大小为 5 。

   • CNN 模型：我们使用 《Convolutional neural networks for sentence classication》 中的 CNN 结构。该结构使用一个卷积层，然后是最大池化层和全连接层。卷积层的窗口大小设为 3，feature map 数量设为 100，随机选择训练集的 1% 作为验证集来执行早停。

   • 所有embedding 模型的词向量维度为 100 。

   注意：对于 PTE 模型，默认情况下在不同数据集上，超参数均按照上述设置。唯一需要调整的超参数的边采样中的样本数 $T$$T$ ，它可以较为安全地设为较大的值。

4. 评估方式：一旦构建或学习了 document 的向量representation，我们就会使用相同的训练数据集应用相同的分类过程。具体而言，训练集中的所有文档都用于 representation learning 阶段和classifier learning 阶段。

   • 如果使用无监督 embedding 方法，则在 representation learning 阶段不使用 document 的类别标签，仅在classifier learning 阶段使用类别标签。
   • 如果使用 predictive embedding 方法，则同时在这两个阶段都使用类别标签。

   对于测试数据集，我们在这两个阶段都留出 hold-out 标签数据和 document 文本。

   注意：在 representation learning阶段保留所有测试数据，即这一阶段模型看不到测试数据的标签、也看不到测试数据的文本。

   在分类阶段，我们使用 LibLinear package 中的 one-vs-rest 逻辑回归模型，并评估 micro-F 和 macro-F1 指标。每一种配置我们都执行十次，并报告指标的均值和方差。

5.  

17.2.1 实验结果

1. 我们在 20NG,Wiki,IMDB 数据集上的长文本效果对比如下。

   首先我们比较无监督 text embedding 方法，可以看到：

   • 具有 document-level 的 word 共现的 $\text{LINE}(G_{w,d})$$\text{LINE}(G_{w,d})$ 的效果，在无监督 embedding 中表现最好。
   • PVDM 性能不如 PVDBOW，这和原始论文中的结论不同。不幸的是我们始终无法得出他们的结论。

   然后我们比较 predictive embedding 方法，可以看到：

   • $\text{PTE}(G_{w,d},G_{w,l})$$\text{PTE}(G_{w,d},G_{w,l})$ 或者PTE(joint) 效果最好。
   • 所有带 word-label 网络PTE 方法都超越了对应的无监督方法（即 LINE 模型），这表明了在监督学习下 predictive text embedding 的强大能力。
   • PTE(joint) 超越了 $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ ，这表明了使用未标记数据可以显著改善监督学习的质量。
   • PTE(joint) 也超越了PTE(pretrain)，这表明联合训练未标记数据和标记数据，要比将它们分别独立训练并微调更有效。
   • 另外我们通过 $\text{LINE}(G_{w,l}+G_{w,d})$$\text{LINE}(G_{w,l} + G_{w,d})$ 学到的单词 embedding 来对 CNN进行预训练，然后使用 label 信息对其进行微调。出乎意料的是：预训练 CNN 在 20NG 和 IMDB 数据集上显著提高，并且在 Wiki 上几乎保持不变。这意味着训练良好的无监督 embedding 对 CNN 进行预训练非常有用。
   • 但是，即使是预训练的 CNN，其性能仍然不如 PTE(joint) 。这可能的因为 PTE 模型可以联合训练标记数据和未标记数据，而 CNN 只能通过预训练和微调两阶段来各自独立的使用标记数据和未标记数据。
   • PTE(joint) 也始终优于经典的 BOW 模型，尽管 PTE(joint) 的 embedding 向量维度远小于 BOW 的向量维度。

   

2. 我们在 RCV1 数据集上的长文本效果对比如下。由于word 之间的顺序丢失，因此要求保留word 顺序信息的 embedding 方法不适用。这里我们观察到了类似的结论：

   • predictive embedding 方法超越了无监督 embedding 。
   • PTE(joint) 方法比 PTE(pretrain) 方法更有效。

   

3. 我们比较了 CNN 和 PTE(joint) 在 IMDB 数据集上的训练实践。我们采用异步随机梯度下降算法，在 1T 内存、2.0G HZ的 40 核 CPU 上执行。平均而言 PTE(joint) 要比 CNN 快 10 倍以上。当使用 pretrain 时，CNN 虽然训练速度加快，但是仍然比 PTE(joint) 慢 5倍以上。

4. 我们在短文本上比较了模型性能如下。

   首先我们比较无监督 text embedding 方法，可以看到：

   • 结合了 document-level 和local-context level 的 word 共现的 $\text{LINE}(G_{w,w},G_{w,d})$$\text{LINE}(G_{w,w},G_{w,d})$ 效果最好。
   • 使用局部上下文级别 word 共现的 $\text{LINE}(G_{w,w})$$\text{LINE}(G_{w,w})$ 要优于使用document级别 word 共现的 $\text{LINE}(G_{w,d})$$\text{LINE}(G_{w,d})$ 。这和长文本实验中结论相反。这是因为在短文本中，document 级别的 word 共现非常稀疏。我们在主题模型中也观察到了类似的结果。
   • PVDM 性能仍然不如 PVDBOW 性能，这和长文本中结论一致。

   然后我们比较 predictive embedding 方法，可以看到：

   • PTE 在 DBLP,MR 数据集上性能最佳，CNN 在 Twitter 数据集上性能最好。

   • 融合了word-label 网络的 PTE 方法超越了对应的无监督embedding 方法(即 LINE 模型)，这和长文本中结论一致。

   • PTE(joint) 超越了 $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ ，这证明了融合未标记数据的有效性。

   • PTE(joint) 超越了 PTE(pretrain)，这证明了对标记数据和未标记数据联合训练的优势。

   • 我们观察到 PTE(joint) 并不能始终超越 CNN。原因可能是单词歧义 ambiguity 问题，这类问题在短文本中更为严重。

     CNN 通过在卷积核中使用局部上下文的word 顺序来减少单词歧义问题，而 PTE 抛弃了word 顺序。我们相信：如果利用了word 顺序，则 PTE 还有很大提升空间。

   

17.2.2 标记数据 & 未标记数据

1. 我们考察标记样本规模的变化对 CNN 和 PTE 的影响。我们考虑两种模式：

   • 监督学习：不包含未标记数据。如 $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$、CNN 。
   • 半监督学习：包含未标记数据。如 PTE(joint)、CNN 等。

   在半监督学习中，我们还比较了经典的半监督方法：带 EM 的朴素贝叶斯NB+EM、标签传播算法 label propagation:LP 。

   可以看到：

   • CNN 和 PTE 随着标记数据规模的增加，性能持续改善。
   • 在监督学习的 CNN 和 $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ 之间，$\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ 均优于CNN 或可与 CNN 媲美。
   • 在半监督学习的 CNN(pretrain) 和 PTE(joint) 之间，PTE(joint) 始终优于 CNN(pretrain)。
   • PTE(joint) 还始终优于经典的 NB+EM 和 LP 方法。

   另外我们还注意到：

   • 当标记数据规模不足时，使用无监督 embedding 的预训练 CNN非常有效，尤其是在短文本上。当训练样本太少时，它甚至优于所有的 PTE 。
   • 当标记数据规模增加时，预训练 CNN 并不总是能够改善其性能，如 DBLP 和 MR 数据集。
   • 对于 SkipGram 模型，增加标记数据规模几乎不会进一步改善其性能。
   • 在 DBLP 数据集上，当标记样本太少时 PTE 性能甚至不如 SkipGram 。原因是当标记数据太少时，word-label 网络的噪音太多。PTE 将 word-label 网络与噪音较少的 word-word, word-document 网络同等对待。一种解决办法是：在标签数据不足时，调整 word-label, word-word, word-document 网络的采样概率。

   

2. 我们考察未标记数据规模的变化对 CNN(pretrain) 和 PTE 的影响。由于篇幅有限，这里我们仅给出 20NG 和 DBLP 数据集的效果。对于 CNN，未标记数据可用于预训练。对于 PTE，未标记数据可用于预训练或联合训练。

   在 20NG 数据集上，我们使用 10% 文档作为标记数据，剩余文档作为未标记数据；在 DBLP 数据集上，我们随机抽取其它会议发表的 20 万篇论文的标题作为未标记数据。

   我们使用 $\text{LINE}(G_{w,w},G_{w,d})$$\text{LINE}(G_{w,w},G_{w,d})$ 作为 CNN 的预训练模型。可以看到：

   • 当未标记数据规模增加时，CNN 和 PTE 性能都有改善。
   • 对于 PTE 模型，未标记数据和标记数据联合训练的效果要优于“预训练和微调”的方式。

   

17.2.3 参数敏感性与可视化

1. PTE 模型除了训练步数 T 之外，大多数超参数对于不同训练集都是不敏感的（如学习率、batch size ），所以可以使用默认配置。

   我们在 20NG 和 DBLP 数据集上考察了 PTE(joint) 对于参数 T 的敏感性。可以看到：当 T 足够大时，PTE(joint) 性能会收敛。

   实际应用中，我们可以将 T 的数量设置称足够大。经验表明：T 的合理范围是异质文本网络中所有边的数量的几倍。

   

2. 我们给出了无监督 embedding （以 $\text{LINE}(G_{w,d})$$\text{LINE}(G_{w,d})$ 为代表）和 predictive embedding （以 $\text{PTE}(G_{w,l})$$\text{PTE}(G_{w,l})$ 为代表）在 20NG 数据集上采用 tSNE 可视化的结果。

   我们对训练集和测试集的文档均进行了可视化，其中 document embedding 为document 内所有word embedding的均值。可以看到：在训练集和测试集上，predictive embedding 均比无监督 embedding 更好地区分了不同的类别。这直观表明了 predictive embedding 在文本分类任务中的强大能力。

   

17.2.4 讨论

1. 无监督 embedding 使用的基本信息是局部上下文级别或者document级别的word 共现。

   • 在长文本中，我们可以看到document级别的word 共现比局部上下文级别的word 共现效果更好，并且二者的结合并不能进一步改善效果。
   • 在短文本中，局部上下文级别的word 共现比document级别的word 共现效果更好，并且二者的结合可以进一步改善效果。这是因为document级别的word 共现受到文本长度太短的困扰，即文本太稀疏。

2. predictive embedding 中：

   • 与 PTE 相比， CNN 模型可以更有效地处理标记信息，尤其是在短文本上。这是因为 CNN 的模型结构比 PTE 复杂得多，尤其时 CNN 可以在局部上下文中利用词序从而解决word 的歧义问题。因此，在标记数据非常稀疏的情况下，CNN 可以超越 PTE，尤其是在短文本上。但是这个优势是以大量的计算、详尽的超参数调优为代价的。

   • 与 CNN 相比，PTE 训练速度更快、超参数调整更容易（几乎没有需要调整的超参数）。当标记数据更为丰富时，PTE 的性能至少和 CNN 一样好并且通常更好。

     PTE 模型的一个明显优势是它可以联合训练标记数据和未标记数据。相比之下 CNN 只能通过预训练来间接利用未标记数据。当标记数据非常丰富时，这种预训练并不总是有帮助的。

3. 实践指南：基于上述讨论，我们提供以下实践指南。

   • 当没有标记数据时：

     • 在长文本上使用 $\text{LINE}(G_{w,d})$$\text{LINE}(G_{w,d})$ 来学习无监督 text embedding 。
     • 在短文本上使用 $\text{LINE}(G_{w,w},G_{w,d})$$\text{LINE}(G_{w,w},G_{w,d})$ 来学习无监督 text embedding 。

   • 当只有少量标记数据时：

     • 在长文本上使用 PTE 来学习text embedding 。
     • 在短文本上使用 CNN(pretrain) ，其中预训练采用 $\text{LINE}(G_{w,w},G_{w,d})$$\text{LINE}(G_{w,w},G_{w,d})$ 。

   • 当有大量标记数据时：

     • 在长文本上使用 PTE(joint) 来学习 text embedding 。
     • 在短文本上从 PTE(joint)、CNN 或者 CNN(pretrain) 三者之间选择，其中主要考虑训练效率和模型效果之间的平衡。

4. 未来方向：PTE 中考虑 word 的词序。

十八、HNE[2015]

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 将不同的异质对象映射到一个统一unified 的潜在空间中，以便可以直接比较来自不同空间的对象。

   与传统的线性 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 ，从而学习由网络结构指导 guide 的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 大规模视觉识别挑战赛上取得了 state-of-the-art 的性能。该挑战赛是计算机视觉中最具挑战性的任务之一。来自这个七层卷积神经网络的中间层的特征，后来被证明是其它计算机视觉任务（如对象检测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》 中，它使用条件conditional 的动态 temporary的 RBM 对网络链接的动态性进行建模，主要任务是使用历史数据预测未来的链接。与我们最相似的工作是 《Latent feature learning in social media network》，其中它在多媒体链接数据上训练一个 content RBM 。我们在几个方面与他们的工作不同：我们在无监督环境中使用监督学习的方案，我们的方法可以扩展到大规模数据集，我们执行多任务学习从而融合来自不同模态的形式。

18.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 算法直接扩展到多于两种对象类型的一般情况。

18.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)))$$

   这可以视为由网络链接引导 guided 的二元逻辑回归。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$。

18.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 的端到端监督学习深度神经网络。

18.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%。

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

   

18.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 模型并达到 state-of-the-art 的水平。

   

18.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 可以提升性能。

   

18.2.3 其它

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

   

十九、AANE[2017]

1. 网络分析已经成为许多实际应用中的有效工具，例如精准营销 targeted marketing 和基因分析。识别有效特征对于这些任务至关重要，但是这涉及大量的人力和大规模的工程实验。作为替代方案，network embedding 将每个节点的拓扑结构topological structure 映射为低维的向量represetnation ，从而可以很好地保留原始网络邻近性proximity 。已有工作表明，network embedding 可以使各种任务收益，例如节点分类、链接预测、网络聚类。

   虽然现有的 network embedding 算法专注于纯网络 pure network，但是现实世界网络中的节点通常关联一组丰富的特征或属性，这称作属性网络attributed network 。像同质性 homophily 和社交影响 social influence 等社会科学理论表明：节点属性与网络结构高度相关，即一方的形成取决于并影响了另一方。例如，微博中用户帖子和“关注” 关系之间的强关联，论文主题和引用关系的高度相关性。在各种应用中，已有工作表明联合利用这两个信息源（即节点拓扑结构和节点属性）可以提高学习性能。受到这些的启发，论文《Accelerated Attributed Network Embedding》提出研究节点特征是否可能有助于学到更好的 embedding representation 。

   此外，现实世界的网络通常是大规模的，具有大量节点和高维特征。例如，截至 2016 年，美国每月有超过 6500 万活跃的 Twitter 用户，每个用户可以发布数千条推文。这对 embedding 算法的可扩展性提出了更高的要求。属性网络 embedding 在以下三个方面具有挑战性：

   • 高的时间复杂度可能是限制算法在实践中应用的瓶颈。一些工作致力于利用网络结构和属性信息来寻找低秩low-rank 的潜在 representation 。它们要么在每次迭代中需要具有 $O(n^3)$$O(n^3)$ 时间复杂度的特征分解 eigen-decomposition（其中 $n$$n$ 为节点的总数），要么采用通常收敛速度较慢的梯度下降。
   • 由于异质信息heterogeneous information 的各种组合，在网络和属性的联合空间中评估节点邻近性node proximity 具有挑战性。另外，随着网络规模的扩大，节点属性邻近性node attribute proximity 矩阵往往太大，无法存储在单机上，更不用说对它的操作了。因此，如果 embedding 算法也是可扩展的，那么将很有吸引力。
   • 两个信息源都可能不完整incomplete 的且充满噪音noisy 的，这进一步加剧了 embedding representation learning 问题。

   因此，鉴于数据的独有特性，现有方法不能直接应用于可扩展的、属性网络的 embedding 。为了应对上述挑战，论文研究了在属性网络上有效地学习 embedding representation 的问题。论文旨在回答以下问题：

   • 如何在网络结构和节点属性组成的联合空间中有效地建模节点邻近性？
   • 如何使 vector representations learning 过程具有可扩展性scalable 和高效efficient ？

   通过调研这些问题，论文提出了一个称作 Accelerated Attributed Network Embedding: AANE 的新框架。总之，本文贡献如下：

   • 正式定义属性网络 embeding 问题。
   • 提出一个可扩展的、高效的框架 AANE 。AANE 通过将节点属性邻近性纳入 network embedding，从而学到有效的、统一的 embedding representation 。
   • 提出一种分布式优化算法。该算法将复杂的建模和优化问题分解为许多低复杂度的子问题，使得 AANE 能够高效地处理每个节点。
   • 在三个真实数据集上验证了 AANE 的效率和效果。

2. 相关工作：

   network embedding 已经成为处理大规模网络的有效工具。人们已经从各个方面进行了努力。

   • 《Scalable learning of collective behavior based on sparse social dimensions》 提出了一种 edge-centric 的聚类方案，从而提高学习效率并减轻内存需求。
   • 《Distributed large-scale natural graph factorization》 提出了一种基于随机梯度下降的分布式矩阵分解算法来分解大规模图。
   • 《LINE: Large scale Information Network Embedding》 通过将weighted edge 展开 unfolding 为多个binary edge 来提高随机梯度下降的效率。
   • 《Asymmetric transitivity preserving graph embedding》 设计了一种 Jacobi-Davidson 类型的算法来近似和加速 high-order proximity embedding 中的奇异值分解。
   • 《Structural deep network embedding》 涉及深度架构从而有效地嵌入节点的一阶邻近性和二阶邻近性。

   人们已经研究并分析了各个领域中的属性网络，并表明：通过联合利用几何结构和节点属性来提高学习性能变得越来越有希望。

   • 《What's in a hashtag? content based prediction of the spread of ideas in microblogging communities》 通过利用内容和拓扑特征改善了对思想ideas 传播的预测。
   • 《Exploring context and content links in social media: A latent space method》 基于 pairwise 相似性对内容信息进行建模，并通过学习语义概念semantic concept 之间的结构相关性structural correlation，从而将内容信息与上下文链接一起映射到语义潜在空间中。
   • 《Probabilistic latent document network embedding》 通过为网络链接和文本内容找到一个联合的低维 representation，从而为文档网络提出了一个基于概率的框架。
   • 《Heterogeneous network embedding via deep architectures》 设计了一种深度学习方法，将丰富的链接信息和内容信息映射到潜在空间，同时捕获跨模态数据之间的相关性。

   属性网络分析不同于多视图学习。属性网络的网络结构不止一个视图，其底层属性很复杂，包括连通性connectivity 、传递性transitivity 、一阶和更高阶的邻近性等等。

19.1 模型

19.1.1 基本概念

1. 设 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})$$\mathcal G=(\mathcal V,\mathcal E,\mathbf W)$ 为一个网络，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n \}$ 为节点集合，$n$$n$ 为节点数量，$\mathcal{E}$$\mathcal E$ 为边的集合，$\mathbf{W}=\{w_{i,j}\}\in {\mathbb{R}}^{n\times n}$$\mathbf W=\{w_{i,j}\}\in \mathbb R^{n\times n}$ 为边的权重矩阵。定义节点 $v_i$$v_i$ 的直接邻居节点为 $\mathcal{N}(v_i)$$\mathcal N(v_i)$ ，其大小为 $N_i$$N_i$ 。

   每条边 $(v_i,v_j)\in \mathcal{E}$$(v_i,v_j)\in \mathcal E$ 关联一个权重 $w_{i,j}\ge 0$$w_{i,j}\ge 0$ 。这里我们关注于无向图，因此有 $w_{i,j}=w_{j,i}$$w_{i,j} = w_{j,i}$ 。更大的 $w_{i,j}$$w_{i,j}$ 意味着节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间产生更强的关联，或者说更大的相似性。$w_{i,j}=0$$w_{i,j} = 0$ 意味着节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间不存在边。

   定义节点 $v_i$$v_i$ 的属性向量为 ${\overrightarrow{\mathbf{a}}}_i\in {\mathbb{R}}^m$$\mathbf{\vec a}_i\in \mathbb R^m$ ，其中 $m$$m$ 为属性的维度。定义属性矩阵为 $\mathbf{A}\in {\mathbb{R}}^{n\times m}$$\mathbf A\in \mathbb R^{n\times m}$ ，其中 ${\overrightarrow{\mathbf{a}}}_i$$\mathbf{\vec a}_i$ 为 $\mathbf{A}$$\mathbf A$ 的第 $i$$i$ 行。

   定义attributed network embedding 为：给定网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})$$\mathcal G=(\mathcal V,\mathcal E,\mathbf W)$ 以及属性矩阵 $\mathbf{A}$$\mathbf A$ ，任务的目的是给出每个节点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 一个低维embedding 向量 ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec h}_i\in \mathbb R^d$ ，使得embedding 向量能够同时保留节点的结构邻近关系、节点的属性邻近关系。所有节点的 embedding 向量构成 embedding 矩阵 $\mathbf{H}\in {\mathbb{R}}^{n\times d}$$\mathbf H\in \mathbb R^{n\times d}$ 。

19.1.2 AANE

1. 现实世界属性网络的理想 embedding 方法需要满足以下三个要求：

   • 首先，它需要能够处理任意类型的边（如，无向/有向边、无权/带权边）。
   • 其次，它需要同时在网络空间和属性空间中都很好地保持节点邻近性。
   • 最后，可扩展性很重要，因为节点的数量 $n$$n$ 和属性维度 $m$$m$ 可能很大。

   为此，我们开发了一个满足所有要求的、有效的、高效的框架 AANE。这里我们将描述 AANE 如何以有效的方式联合建模网络结构邻近性和属性邻近性。

2. 网络结构建模：为了保持 $\mathcal{G}$$\mathcal G$ 中的节点邻近性， AANE 提出两个假设：

   • 首先，假设基于图的映射graph-based mapping 在边上是平滑的，特别是对于节点密集的区域。这符合 “聚类假设” cluster hypothesis 。
   • 其次，具有更相似拓扑结构或由更高权重连接的一对节点更有可能具有相似的 embedding 。

   为了实现这些目标，我们提出以下损失函数来最小化相连节点之间的 embedding 差异：

   $${\mathcal{J}}_{\mathcal{G}}=\sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$

   其中 ${\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_i,\mathbf{\vec h}_j$ 分别为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的 embedding representation，$w_{i,j}$$w_{i,j}$ 是节点 $v_i,v_j$$v_i,v_j$ 之间边的权重。核心思想是：为最小化 ${\mathcal{J}}_{\mathcal{G}}$$\mathcal J_\mathcal G$ ，当 $w_{i,j}$$w_{i,j}$ 较大时（节点 $v_i$$v_i$ 和 $v_j$$v_j$ 相似性更大），模型将迫使 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 ${\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_j$ 的距离较小。

3. 属性邻近性建模：节点的属性信息与网络拓扑结构紧密相关。网络空间中的节点邻近性应该与节点属性空间中的节点邻近性一致。为此，我们研究如何使得 embedding representation $\mathbf{H}$$\mathbf H$ 也很好地保持节点属性的邻近性。

   受对称矩阵分解symmetric matrix factorization 的启发，我们提出使用 $\mathbf{H}$$\mathbf H$ 和 ${\mathbf{H}}^{\mathrm{\top }}$$\mathbf H^\top$ 的乘积来近似属性亲和矩阵attribute affinity matrix $\mathbf{S}\in {\mathbb{R}}^{n\times n}$$\mathbf S\in \mathbb R^{n\times n}$ 。基本思想是：强制 embedding representation ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 ${\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_j$ 的内积与对应的属性相似性 $s_{i,j}$$s_{i,j}$ 相同。在数学上，该损失函数定义为：

   $${\mathcal{J}}_A=\sum _{i=1}^n\sum _{j=1}^n{(s_{i,j}-{\overrightarrow{\mathbf{h}}}_i\cdot {\overrightarrow{\mathbf{h}}}_j)}^2={\Vert \mathbf{S}-\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}\Vert }_F^2$$

   其中亲和矩阵可以通过节点属性相似性来计算，具体而言这里我们采用余弦相似度。假设节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的属性相似性为 $s_{i,j}$$s_{i,j}$ ，即 $s_{i,j}={\overrightarrow{\mathbf{a}}}_i\cdot {\overrightarrow{\mathbf{a}}}_j$$s_{i,j} = \mathbf{\vec a}_i \cdot \mathbf{\vec a}_j$ 。

   计算亲和矩阵的时间复杂度为 $O(n^2)$$O(n^2)$，存储亲和矩阵的空间复杂度为 $O(n^2)$$O(n^2)$ 。我们可以对每个节点仅计算和存储最相似属性的 top k 个节点，从而将时间复杂度和空间复杂度降低到 $O(kn)$$O(kn)$ 。

4. Joint Embedding Representation Learning：现在我们有两个损失函数 ${\mathcal{J}}_G$$\mathcal J_G$ 和 ${\mathcal{J}}_A$$\mathcal J_A$，它们分别建模网络拓扑结构中的节点邻近性、节点属性中的节点邻近性。为了对这两种邻近性互补，形成一个统一的联合空间，我们在以下优化问题中对这两种类型的信息进行联合建模：

   $$J={\mathcal{J}}_A+\lambda {\mathcal{J}}_{\mathcal{G}}={\Vert \mathbf{S}-\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}\Vert }_F^2+\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$

   其中 $\lambda$$\lambda$ 用于平衡网络结构损失和属性损失：

   • 当 $\lambda \to 0$$\lambda \rightarrow 0$ 时，网络拓扑结构不影响最终的节点 embedding，。因此每个节点都可以是一个孤立的 cluster。
   • 当 $\lambda \to +\mathrm{\infty }$$\lambda\rightarrow +\infty$ 时，最优解倾向于使得所有节点的 embedding 相同（即 ${\overrightarrow{\mathbf{h}}}_i={\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_i = \mathbf{\vec h}_j$ ）， 此时所有节点在embedding 空间中形成单个 cluster 。

   因此我们可以通过调节 $\lambda$$\lambda$ 从而调整 embedding 空间中 cluster的数量。

   AANE 可以视为带正则化项的矩阵分解，其中将 $\mathbf{S}$$\mathbf S$ 分解为 $\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}$$\mathbf H \mathbf H^\top$ 。在分解过程中施加了基于网络结构的正则化 $\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$\lambda \sum_{(v_i,v_j)\in\mathcal E} w_{i,j}\left\|\mathbf{\vec h}_i - \mathbf{\vec h}_j\right\|_2$，该正则化迫使相连的节点在 embedding 空间中彼此靠近。

   AANE 仅考虑网络结构的一阶邻近性，无法捕获网络结构的高阶邻近性。

   AANE 仅捕获线性关系，未能捕获非线性关系。

   AANE 分别独立地建模网络结构邻近性和节点属性邻近性，并未建模二者之间的交互。