Question

1. 数据点之间的各种显式交互 explicit interaction 和隐式交互implicit interaction （例如 friendship, co-authorship, co-concurrence）使得 network 无处不在。因此，network representation 在许多数据挖掘 application 中是难以避免的。一方面，许多数据挖掘 application 都是为网络而设计的，例如社区检测 community detection 、链接预测 link prediction 。另一方面，其它数据挖掘 application 也可以从网络分析中受益，例如 collective classification 和降维 dimension reduction 。

   以上所有 application 都依赖于对网络交互 network interaction 或者 edge 的分析。如今，network embedding 越来越多地用于辅助网络分析，因为它可以有效地学习潜在特征 latent feature 从而编码链接信息。network embedding 的基本思想是通过在潜在空间中保持相连顶点pair 对，从而保持网络结构 network structure 。潜在特征是有益的，因为它比 edge 具有更强的表达能力，并且可以直接被现有的机器学习技术所使用。尽管之前人们已经提出了各种 network embedding 方法，但是这些方法仅设计用于在单网络 single network 上学习 representation 。

   此外，在大数据时代，不同类型的相关信息往往是可用的，并且可以融合在一起形成耦合异质网络 coupled heterogeneous network ，其中每种类型的信息都可以表示为一个独立的同质网络 homogeneous network 。我们将耦合异质网络定义为由两个不同的、但是相关的子网 sub-network 构成的网络。这些子网通过跨网链接 inter-network link 来连接，例如：

   • author and word network ：author可以通过他们之间的交互而联系起来，例如 co-authorship 。单词可以通过共现 co-concurrence 关系联系起来。author可以和他们在paper中使用的单词联系起来。
   • social network user and word network：用户可以通过他们之间的好友关系而联系起来。单词可以通过共现 co-concurrence 关系联系起来。用户可以和他们使用的单词联系起来。
   • customer and movie network：消费者可以通过他们之间的好友关系而联系起来。电影可以通过共同演员或者共同导演关系而联系起来。消费者可以和他们看过的电影联系起来。
   • gene and chemical compound network：基因可以通过 gene-gene 相互作用而联系起来。化合物可以通过具有相同本体 ontology 的方式联系起来。基因可以通过 binding 关系从而和化合物联系起来。

   为了直观地说明这个概念，下图给出了 author and word network 的一个例子，其中author通过 co-authorship 联系起来，并且在同一个标题中的同时出现被定义为单词之间的 co-concurrence 关系。我们从 DBLP 数据集中对网络进行采样。被采样的 co-authorship 网络由 2000 年到 2003 年期间在两个数据挖掘会议 KDD 和 ICDM 、以及两个数据库会议 SIGMOD 和 VLDB 上发表paper的author组成。结果表明，author构成了两个簇 cluster，单词也构成了两个簇，这些簇可以通过社区检测算法来生成。而且，数据挖掘专家对数据挖掘领域的单词相比数据库领域的单词有更多的链接，而数据库专家对数据库领域的单词相比数据挖掘领域的单词有更多的链接。

   

   为了学习author的潜在特征，同一个领域的author应该在潜在空间中彼此靠近。可以看出，author和单词之间的 edge 可以在已经存在 author edge 的情况下作为补充信息 complementary information 。这是因为同一个领域的 author 更有可能在其领域的单词上存在 edge ，这可以用来使得仅从 author edge 学习的潜在特征更加全面和准确。当 author edge 不存在时，补充信息更为重要，这可以称之为冷启动问题 cold-start problem 。学习单词潜在特征的情况也是类似的。

   author network 和 word network 都有可用的 embedding 方法。然而，将现有的、用于 single network 的 embedding 方法扩展到耦合异质网络并不简单。主要挑战来自于两个不同网络的异质特性 heterogeneous characteristics ，这将导致两个异质潜在空间 heterogeneous latent space 。因此，不同网络的潜在特征无法直接匹配。为了应对这一挑战，论文 《Embedding of Embedding (EOE) : Joint Embedding for Coupled Heterogeneous Networks》提出了一种叫做 embedding of embedding: EOE 的方法，该方法通过引入一个调和 harmonious 的 embedding 矩阵，从而进一步将 embedding 从一个潜在空间嵌入到另一个潜在空间。在 EOE 中，潜在特征不仅编码网内边 intra-network edge ，还编码跨网边 inter-network edge。具体而言，论文提出的 EOE 可以通过乘以适当设计的调和 embedding 矩阵，将潜在特征从一个空间转换到另一个空间。有了这个调和 embedding 矩阵，不同网络的潜在特征之间的计算就没有障碍了。作为一种 embedding 方法，论文提出的 EOE 还使得那些被 edge 链接的顶点能够在潜在空间中紧密靠近。

   EOE 与现有 single network 的 embedding 方法的主要区别在于：两个网络对应着三种类型的边、以及两种类型的潜在空间。此外，必须同时学习两个网络的潜在特征，因为任何一方都可以通过跨网边 inter-network edge 向另一方提供补充信息。

   很容易得出 EOE 的学习目标 learning objective 中需要优化的变量有三类：两个网络对应的两类潜在特征、以及调和 embedding 矩阵。因此，论文提出了一种交替优化算法alternating optimization algorithm ，其中学习目标单次仅针对一种类型的变量进行优化，直到算法收敛。这种交替优化算法可以用一系列更容易的优化来代替对三个变量的、困难的联合优化。EOE 模型和优化算法将在正文部分详细介绍。

   本文主要贡献如下：

   • 据作者所知，该论文是第一个研究耦合网络联合 embedding 问题的人。论文提出了一个联合 embedding 模型 EOE，该模型结合了一个调和 embedding 矩阵，从而进一步嵌入仅编码网内边 intra-network edge 的 embedding 。
   • 论文提出了一种交替优化算法来解决 EOE 的学习目标，其中学习目标单次仅针对一种类型的变量进行优化，直到算法收敛。
   • 论文对各种现实世界的耦合异质网络进行了全面的实验评估，从而展示联合学习在耦合网络上的优势。所提出的 EOE 在包括可视化visualization 、链接预测prediction 、多类别分类multi-class classification 、多标签分类 multi-label classification 在内的四个 application 中优于 baseline 。
   • 这项工作表明将耦合异质网络作为来自不同信息源的、融合信息的有效 representation，其中每个信息源都表示为单独的同质网络，并且inter-network link 捕获了异质网络顶点之间的关系。

2. 相关工作：我们提出的 EOE 模型与常规的 graph embedding 或 network embedding 方法密切相关，这些方法用于学习 graph 或者 network 顶点的潜在 representation 。

   人们之前已经提出了一些 graph embedding 方法或 network embedding 方法，但是它们最初是为已有特征的降维而设计的。具体而言，他们的目标是学习已有特征的低维潜在 representation，从而显著降低特征维度带来的学习复杂度 learning complexity 。在我们的场景中，不存在网络顶点的特征，而是网络的 edge 信息。

   另一种称作 graph factorization （《Distributed large-scale natural graph factorization》）的 graph embedding 方法通常利用网络 edge 来学习潜在特征。它将graph 表示为矩阵，其中矩阵元素对应于顶点之间的边，然后通过矩阵分解来学习潜在特征。但是 graph factorization 方法仅在潜在空间中表示具有交互interaction 的顶点 pair 对。我们提出的 EOE 模型不仅将存在edge 的顶点紧密靠近，而且还将不存在 edge 的顶点彼此远离。后一种规则很重要，因为它将保留某些顶点不太可能交互的信息，这也是网络结构信息的一部分。

   最近一种叫做 DeepWalk 的 network embedding 模型嵌入了从随机游走获得的局部链接信息 local link information 。它的动机是网络的 degree 分布和自然语言词频word frequency 分布之间的联系。基于这一观察，自然语言模型被重用于对网络社区结构进行建模。然而，随机游走可能会跨越多个社区，这对于保持网络结构的目标而言是不希望看到的。此外，DeepWalk 仅能处理无权网络unweighted network，而我们提出的 EOE 模型同时适用于加权网络 weighted network 和无权网络。

   state-of-the-art 的、相关的模型是用于大规模信息网络 embedding 的 LINE 。LINE 保留了交互信息和非交互信息，这与我们提出的 EOE 类似。但是我们提出的 EOE 模型在代价函数的公式上与 LINE 不同。此外，我们提出的 EOE 是为嵌入耦合异质网络而设计的。包括 LINE 在内的现有方法都无法处理耦合异质网络。而耦合异质网络在现实世界中很常见，并且 EOE 有利于耦合异质网络中每个子网的 embedding 。

10.1 模型

10.1.1 基本概念

1. 耦合异质网络coupled heterogeneous network 的定义：耦合异质网络由两个不同的、但是相关的子网络 sub-network 组成，这些子网络通过 inter-network edge 相连。术语 “不同” 指的是两个子网络的顶点属于不同的类型。术语 “相关” 意味着两个子网络的顶点具有特定类型的交互或关系。

   给定两个子网络 $ \mathcal G_u(\mathcal U,\mathcal E_u,\mathcal W_u) $ 、 $ \mathcal G_v(\mathcal V,\mathcal E_v,\mathcal W_v) $ ，耦合异质网络表示为 $ \mathcal G_{u,v}(\mathcal G_u,\mathcal E_{u,v},\mathcal W_{u,v},\mathcal G_v) $ ，其中：

   • $ \mathcal U $ 为第一个子网络的顶点集合， $ \mathcal V $ 为第二个子网络的顶点集合。
   • $ \mathcal E_u $ 为第一个子网络的边集合， $ \mathcal E_v $ 为第二个子网络的边集合， $ \mathcal E_{u,v} $ 为连接 $ \mathcal G_u $ 和 $ \mathcal G_v $ 的 inter-network edge 集合。 $ \mathcal W_u,\mathcal W_v,\mathcal W_{u,v} $ 分别代表这些边的权重。所有这些边都可以是加权的/无权的、有向的/无向的。

2. 为了学习 $ \mathcal U $ 和 $ \mathcal V $ 的潜在特征，EOE 利用网络 edge 从而作为 embedding 方法。具体而言，具有edge 的顶点 pair 对在潜在空间中紧密靠近。

   如果一对顶点之间存在边的概率相当高（理想情况下为 100%），则它们在潜在空间中是紧密靠近的。这个概率由以下公式来定义：

   $ p(\mathbf{\vec u}_i,\mathbf{\vec u}_j) = \frac{1}{1+\exp\left(-\mathbf{\vec u}_i^\top \mathbf{\vec u}_j\right)} $

   其中 $ \mathbf{\vec u}_i,\mathbf{\vec u}_j $ 分别是子网络 $ \mathcal G_u $ 中顶点 $ i $ 和顶点 $ j $ 的 embedding 向量。

3. 上述方程是 $ \mathcal G_u $ 在潜在空间中度量的，对于 $ \mathcal G_v $ 其概率公式也是类似的。但是，上述方程无法计算来自 $ \mathcal G_u $ 的顶点和来自 $ \mathcal G_v $ 的顶点之间存在边的概率，因为这个概率涉及到两个不同的潜在空间。为了调和两个潜在空间的异质性，我们引入了一个调和 embedding 矩阵，从而进一步将 embedding 从一个潜在空间嵌入到另一个潜在空间。

   调和 embedding 矩阵 harmonious embedding matrix 是一个实值矩阵 $ \mathbf M\in \mathbb R^{d_u\times d_v} $ ，其中 $ d_u $ 为 $ \mathcal U $ 的潜在特征维度、 $ d_v $ 为 $ \mathcal V $ 的潜在特征维度。使用调和 embedding 矩阵之后，衡量来自不同网络的顶点之间紧密程度的概率如下所示：

   $ p(\mathbf{\vec u}_i,\mathbf{\vec v}_j) = \frac{1}{1+\exp\left(-\mathbf{\vec u}_i^\top \mathbf M\mathbf{\vec v}_j\right)} $

   其中 $ \mathbf{\vec u}_i $ 是子网络 $ \mathcal G_u $ 中顶点 $ i $ 的 embedding 向量， $ \mathbf{\vec v}_j $ 是子网络 $ \mathcal G_v $ 中顶点 $ j $ 的 embedding 向量。

10.1.2 EOE

1. 基于前述的定义，我们现在提出 EOE 模型。EOE 模型不仅将存在edge 的顶点紧密靠近，还将不存在 edge 的顶点彼此远离。后一种规则很重要，因为它将保留某些顶点不太可能交互的信息，这也是网络结构信息的一部分。

   要将这两个规则都转换为优化问题，则应该惩罚存在 edge 的顶点 pair 对的小概率、以及不存在 edge 的顶点 pair 对的大概率。惩罚前者的损失函数如下所示：

   $ \mathcal L(\mathbf U) = \sum_{(i,j)\in \mathcal E_u} (\mathbf W_u)_{i,j}\times f\left(p(\mathbf{\vec u}_i,\mathbf{\vec u}_j)\right) $

   其中：

   • $ (\mathbf W_u)_{i,j} $ 表示顶点 $ \mathbf{\vec u}_i $ 和 $ \mathbf{\vec u}_j $ 之间存在边的权重。

     $ \mathbf U\in \mathbb R^{|\mathcal U|\times d_u} $ 为 $ \mathcal U $ 中所有顶点的 embedding 向量构成的 embedding 矩阵， $ |\mathcal U| $ 为 $ \mathcal U $ 中所有顶点数量， $ d_u $ 为 $ \mathcal U $ embedding 向量的维度。

   • $ f(x) $ 为待定义的惩罚函数。乘以 $ (\mathbf W_u)_{i,j} $ 是反映权重所表示的关系强度。如果网络是无权的，则 $ (\mathbf W_u)_{i,j} $ 是一个常数，例如 1。

   作为一个合适的惩罚函数， $ f(x) $ 必须是单调递减的，并且当概率接近 1.0 时递减到 0.0。单调递减保证对较大概率的链接给予较小的惩罚。这个属性是必要的，因为我们只希望惩罚存在链接但是预估概率却很小的 case 。此外，为了便于优化， $ f(x) $ 应该是凸函数并且是连续可微的。该属性使得上述损失函数可以通过常用的梯度下降算法求解，并确保全局最优解。具有这两个属性的简单函数是负的对数似然，因此上式改写为：

   $ \mathcal L(\mathbf U) = - \sum_{(i,j)\in \mathcal E_u} (\mathbf W_u)_{i,j}\times \log\left(p(\mathbf{\vec u}_i,\mathbf{\vec u}_j)\right) $

   类似地，对于不存在 edge 的顶点 pair 对的惩罚函数 $ f(x) $ 也是以这种方式定义的，只是必要的属性被调整为单调递增，并且在概率接近零时惩罚函数接近零。因此，惩罚预估概率很大但是却不存在链接的损失函数定义为：

   $ \mathcal L(\mathbf U) = - \sum_{(h,k)\notin \mathcal E_u} \log\left(1-p(\mathbf{\vec u}_h,\mathbf{\vec u}_k)\right) $

   其中 $ u_h,u_k $ 是不存在 edge 的一对顶点， $ u_i,u_j $ 是存在 edge 的一对顶点。在本文的剩余部分，我们以这种方式来表示存在 edge 的顶点pair 对、以及不存在 edge 的顶点 pair 对。

   在处理大规模网络时，在所有不存在edge 的顶点pair 对上计算该损失函数是不切实际的。从计算规模上考虑，我们对不存在 edge 的顶点 pair 对进行采样，使得其规模仅比存在 edge 的顶点 pair 对的数量大几倍。

2. $ \mathcal G_v $ 的损失函数和来自不同子网络的顶点 pair 对都以这种方式进行衡量。所有这些损失函数都应该联合优化，因为每个子网络都可以通过 inter-network edge 向另一个子网络提供补充信息。组合所有这些损失函数的一种直接方法是将它们直接相加。我们将更复杂的组合方式留待未来的工作。

   在添加 L2 正则化项和 L1 正则化项从而避免过拟合之后，嵌入了耦合异质网络 $ \mathcal G_{u,v}(\mathcal G_u,\mathcal E_{u,v},\mathcal W_{u,v},\mathcal G_v) $ 的整体损失函数为：

   $ \mathcal L(\mathbf U,\mathbf M,\mathbf V) = \\ -\left[\sum_{(i,j)\in \mathcal E_u} (\mathbf W_u)_{i,j}\log p(\mathbf{\vec u}_i,\mathbf{\vec u}_j) + \sum_{(i,j)\in \mathcal E_{u,v} } (\mathbf W_{u,v})_{i,j}\log p(\mathbf{\vec u}_i,\mathbf{\vec v}_j) + \sum_{(i,j)\in \mathcal E_v}(\mathbf W_v)_{i,j}\log p(\mathbf{\vec v}_i,\mathbf{\vec v}_j)\right]\\ -\left[\sum_{(h,k)\not\in \mathcal E_u} \log(1- p(\mathbf{\vec u}_u,\mathbf{\vec u}_k)) + \sum_{(h,k)\not\in \mathcal E_{u,v} } \log (1-p(\mathbf{\vec u}_h,\mathbf{\vec v}_k)) + \sum_{(h,k)\not\in \mathcal E_v} \log (1-p(\mathbf{\vec v}_h,\mathbf{\vec v}_k))\right]\\ + \lambda \sum_{i=1}^{|\mathcal U|} ||\mathbf{\vec u}_i||_2 + \beta ||\mathbf M||_1+ \eta \sum_{i=1}^{|\mathcal V|}||\mathbf{\vec v}_i||_2 $

   其中：

   • $ p(\mathbf{\vec u}_i,\mathbf{\vec u}_j) = \frac{1}{1+\exp\left(-\mathbf{\vec u}_i^\top \mathbf{\vec u}_j\right)} $ ， $ p(\mathbf{\vec v}_i,\mathbf{\vec v}_j) = \frac{1}{1+\exp\left(-\mathbf{\vec v}_i^\top \mathbf{\vec v}_j\right)} $ ， $ p(\mathbf{\vec u}_i,\mathbf{\vec v}_j) = \frac{1}{1+\exp\left(-\mathbf{\vec u}_i^\top \mathbf M\mathbf{\vec v}_j\right)} $ 。
   • $ \lambda,\beta,\eta \in \mathbb R $ 为正则化系数。

   调和embedding 矩阵的 L1 正则化用于执行特征选择来协调两个潜在空间，因为这会引入稀疏性。

10.1.3 优化算法

1. 最小化损失函数 $ \mathcal L(\mathbf U,\mathbf M,\mathbf V) $ 是一个凸优化问题，因此我们可以使用基于梯度的算法来执行优化。 $ \mathbf{\vec u}_i $ 的梯度为 $ \nabla_{\mathbf{\vec u}_i} \mathcal L(\mathbf U,\mathbf M,\mathbf V) $ ， $ \mathbf{\vec v}_i $ 的梯度为 $ \nabla_{\mathbf{\vec v}_i} \mathcal L(\mathbf U,\mathbf M,\mathbf V) $ 。但是，损失函数 $ \mathcal L(\mathbf U,\mathbf M,\mathbf V) $ 对于 $ \mathbf M $ 的零元素是不可微的，因此我们对 $ \mathbf M $ 采用 sub-gradient 梯度，这可以通过以下公式获得：

   $ \frac{\partial \mathcal L(\mathbf U,\mathbf M,\mathbf V)}{\partial \mathbf M} = -\sum\left[\frac{(\mathbf W_{u,v})_{i,j}\exp\left(-\mathbf{\vec u}_i^\top \mathbf M \mathbf{\vec v}_j\right)}{1+\exp\left(-\mathbf{\vec u}_i^\top \mathbf M \mathbf{\vec v}_j\right)}\mathbf{\vec u}_i\mathbf{\vec v}_j^\top\right] \\ +\sum\left[\frac{\exp\left(-\mathbf{\vec u}_h^\top\mathbf M \mathbf{\vec v}_k\right)}{p(\mathbf{\vec u}_h,\mathbf{\vec v}_k) - 1}\times p^2(\mathbf{\vec u}_h,\mathbf{\vec v}_k)\mathbf{\vec u}_i\mathbf{\vec v}_j^\top\right]+\beta\sum_{i=1}^{|\mathcal U|}\sum_{j=1}^{|\mathcal V|}\text{sign}(m_{i,j}) $

   其中 $ m_{i,j} $ 为 $ \mathbf M $ 为第 $ i $ 行第 $ j $ 列， $ \text{sign}(x) $ 定义为：

   $ \text{sign}(x) = \begin{cases} 1,&\text{if}\; x \gt 0\\ -1,&\text{if}\; x \lt 0\\ 0,&\text{else} \end{cases} $

   $ \mathcal L(\mathbf U,\mathbf M,\mathbf V) $ 对于 $ m_{i,j} = 0 $ 不可微的，但是考虑到 $ m_{i,j} $ 在实际中很少会刚好为 0，因此如果 $ m_{i,j} $ 在梯度下降过程中穿越零点，则我们将其设置为零。这称作 lazy update，因此将鼓励 $ \mathbf M $ 成为稀疏矩阵。

2. 有了这些梯度，我们提出了一种基于梯度的交替优化算法 gradient-based alternating optimization algorithm 。在该优化算法中，损失函数每次针对一种类型的变量最小化，直到收敛。这种交替优化算法可以用一系列更容易的优化来代替对三个变量的、困难的联合优化。

   关于变量的交替时机，直到特定于当前变量的最小化收敛时才执行。这是因为每种类型的变量都会影响其它两种类型的变量，如果当前变量没有很好地优化，则它可能会传播负面影响 negative influence 。一个直观的例子是，如果存在边的两个相似单词在交替 author 之前在潜在空间中不接近，则由于 co-author 而应该接近的两个 author 可能会彼此远离，远离的原因仅仅是因为这两个 author 分别与前述单词存在边。

3. EOE 交替优化算法：

   • 输入：

     • 耦合异质网络 $ \mathcal G_{u,v}(\mathcal G_u,\mathcal E_{u,v},\mathcal W_{u,v},\mathcal G_v) $ ，embedding 维度 $ d_u,d_v $
     • 正则化系数 $ \lambda,\beta,\eta $

   • 输出： $ \mathcal U,\mathcal V $ 的 embedding ，调和embedding 矩阵 $ \mathbf M $

   • 算法步骤：

     • 全零初始化 $ \mathcal U,\mathcal V $ 的 embedding 参数，以及矩阵 $ \mathbf M $

     • 预训练顶点集合 $ \mathcal U $ ，循环迭代直到算法收敛。迭代步骤为：

       • 对 $ \mathcal U $ 里的所有顶点计算梯度 $ \frac{\partial \mathcal L(\mathbf U)}{\partial \mathbf{\vec u}_i} $ ，其中 $ \mathcal L(\mathbf U) $ 为仅仅考虑子图 $ \mathcal G_u $ 的损失函数
       • 线性搜索找到学习率 $ \eta_u $
       • 更新参数： $ \mathbf{\vec u}_i^{} = \mathbf{\vec u}_i^{} - \eta_u \frac{\partial \mathcal L(\mathbf U)}{\partial \mathbf{\vec u}_i} $ ，其中 $ t $ 为迭代次数

     • 预训练顶点 $ \mathcal V $ ，循环迭代直到算法收敛。迭代步骤为：

       • 对 $ \mathcal V $ 里的所有顶点计算梯度 $ \frac{\partial \mathcal L(\mathbf V)}{\partial \mathbf{\vec v}_i} $ ，其中 $ \mathcal L(\mathbf V) $ 为仅仅考虑子图 $ \mathcal G_v $ 的损失函数
       • 线性搜索找到学习率 $ \eta_v $
       • 更新参数： $ \mathbf{\vec v}_i^{} = \mathbf{\vec v}_i^{} - \eta_v \frac{\partial \mathcal L(\mathbf V)}{\partial \mathbf{\vec v}_i} $ ，其中 $ t $ 为迭代次数

     • 循环直到收敛，迭代步骤为：

       • 固定 $ \mathcal U $ 和 $ \mathcal V $ 的 embedding 参数，利用梯度下降算法优化 $ \mathbf M $
       • 固定 $ \mathcal V $ 的 embedding 参数和 $ \mathbf M $ ，利用梯度下降算法优化 $ \mathcal U $ 的 embedding 参数
       • 固定 $ \mathcal U $ 的 embedding 参数和 $ \mathbf M $ ， 利用梯度下降算法优化 $ \mathcal V $ 的 embedding 参数

     • 最终返回顶点 $ \mathcal U,\mathcal V $ 的 embedding 向量以及调和embedding 矩阵 $ \mathbf M $

4. 在 EOE 交替优化算法中，我们分别对 $ \mathcal G_u $ 和 $ \mathcal G_v $ 进行预训练从而学习 $ \mathcal U $ 和 $ \mathcal V $ 的潜在特征，这也是为了不将负面影响传播到其它变量。损失函数 $ \mathcal L(\mathbf U) $ 之前未给出，它是仅包含 $ \mathcal G_u $ 的损失。

   我们使用回溯线性搜索 backtracking line search 来为每次迭代学习一个合适的学习率。判断是否整体收敛的条件：当前迭代和上一轮迭代之间的相对损失小于一个相当小的值，如 0.001 。

5. EOE 交替优化算法的复杂度和顶点embedding 梯度、调和 embedding 梯度的复杂度成正比。这些梯度的复杂度处于同一个水平，即 $ O(nd_u\times d_v) $ ，其中 $ n $ 是存在边的顶点 pair 对的数量， $ d_u $ 是 $ \mathcal U $ 的顶点 embedding 维度， $ d_v $ 是 $ \mathcal V $ 的顶点 embedding 维度。因此，上述算法的复杂度为 $ O(nd_u\times d_v I) $ ，其中 $ I $ 为迭代次数。因此，我们提出的 EOE 交替优化算法可以在多项式时间内求解。

6. 未来工作：将EOE 模型扩展到两个以上的网络，从而融合多个信息源。

10.2 实验

1. 我们在可视化、链接预测、多分类、多标签分类等常见的数据挖掘任务上，评估 EOE 模型学到的潜在特征的有效性。

2. baseline 方法：

   • 谱聚类spectral clustering: SC：该方法使用谱聚类来学习顶点的潜在特征。具体而言，它使用归一化的拉普拉斯矩阵的 top d 个特征向量作为 embedding 向量。

   • DeepWalk：通过截断的随机游走和 SGNS 来学习顶点的 embedding 向量。

     由于 DeepWalk 仅适用于未加权的边，因此所有边的权重设置为 1 。

   • LINE：它是为了嵌入大规模信息网络而提出的，适用于有向/无向图、加权/无权图。我们提出的 EOE 也适用于大规模网络，因为它可以在多项式时间内求解。此外，EOE 也适用于所有类型的网络（有向/无向、加权/无权）。

     LINE 分别定义损失函数来保留一阶邻近性和二阶邻近性来求解一阶邻近representation 和二阶邻近 representation，然后将二者拼接一起作为 representation 。LINE 有两个变体：LINE-1st 仅保留一阶邻近性，LINE-2nd 仅保留二阶邻近性。而我们提出的 EOE 模型仅保留一阶邻近性。

     由于如何合理的结合 LINE-1st 和 LINE-2nd 尚不清楚，因此我们不与LINE(1st+2nd) 进行比较。

   注：这些方法都是同质图的 embedding 方法，仅能捕获单个图的信息。而 EOE 可以同时捕获多个图的信息，因此这种比较不太公平（EOE 有额外的输入信息，因此理论上效果更好）。

3. EOE 的实验配置：

   • 设置 embedding size 为 128 （DeepWalk 和 LINE 的 embedding size 也是 128 ）。
   • 无边的顶点 pair 数量相对有边的顶点pair 的比例为 5 。
   • backtracking line search 采用常用设置。
   • 正则化项的所有系数为 1 。
   • 采用 0.001 作为相对损失的阈值，从而判断梯度下降算法是否收敛。

10.2.1 可视化

1. embedding 在二维空间上的可视化是 network embedding 的一个重要应用。如果学到的 embedding 很好地保留了网络结构，则可视化提供了一种生成网络布局 network layout 的简单方法。我们用 author and word network 来说明这一点。

2. 数据集：我们从 DBLP 数据集中采样了一个较大的网络。具体而言，我们选择了来自四个研究领域的热门会议，即：数据库领域的 SIGMOD,VLDB,ICDE,EDBT,PODS，数据挖掘领域的 KDD,ICDM,SDM,PAKDD， 机器学习领域的 ICML,NIPS,AAAI,IJCAI,ECML ，信息检索领域的 SIGIR,WSDM,WWW,CIKM,ECIR 。

   我们选择了 2000 到 2009 年发表的论文，过滤掉论文数量少于 3 篇的 author ，并过滤掉停用词（如where,how ）。过滤后的 author network 包含 4941位 author 、17372 条链接（即 co-authorship）。过滤后的 word network 有6615个单词、78217条链接（即co-concurrence）。过滤后的 author 到 word 的链接有 92899 条。

3. 所有 baseline 都分别独立学习 author embedding 和 word embedding 。EOE 通过联合推断来学习这些 embedding 。所有方法生成的 embedding 维度为 128 。我们使用 t-SNE 工具将它们映射到二维空间中，如下图所示。其中：绿色为数据库领域、浅蓝色为信息检索领域、深蓝色为数据挖掘领域、红色为机器学习领域。

   下图的第二排第一图应该为 SpectralClustering Word Network，这个是作者原图的标示错误。

   author 子网络和 word 子网络应该显示四个聚类的混合，因为所选的四个研究领域密切相关。

   • 谱聚类的结果不符合预期，因为谱聚类的学习目标不是保留网络结构。

   • 尽管 DeepWalk 和 LINE 在某种程度上表现更好，但是它们无法同时展示四个不同的聚类。

     • DeepWalk 的问题可能在于：随机游走跨越了多个研究领域，结果导致来自不同领域的数据点被分布在一起。
     • LINE 也有类似的问题，因为author可能具有来自不同领域的其它author的链接。

   • EOE 的结果最符合预期，因为 EOE 可以通过补充的文本信息来克服上述问题。具体而言，即使某些author 和很多不同领域的其它author存在链接，author的论文中的单词也能够提供该author研究领域的补充信息。

     单词网络的情况也类似。

   

10.2.2 链接预测

1. 链接预测问题是指通过测量顶点之间的相似性来推断网络顶点之间新的交互。我们部署了两种链接预测场景来评估潜在特征：未来链接预测future link prediction 、缺失链接预测 missing link prediction 。

2. 未来链接预测问题是推断未来会发生的交互。在未来链接预测中，我们采用 DBLP 的 2000 到 2009 年发表的论文作为训练集，然后预测 2010 年、2010~2011年、2011~2012年、2010~2012 年这四个时期的链接。在这四个时期，我们除了直接得到正样本( 存在co-authorship 关系的author) 之外，我们还通过计算来间接得到负样本：通过随机生成数量与正样本相同、没有co-authorship 关系的author pair 对。通过负样本来评估模型检测负样本的能力。

   我们通过以下概率来预测新的co-authoreship 相似性：

   $ p(\mathbf{\vec u}_i,\mathbf{\vec u}_j) = \frac{1}{1+\exp(-\mathbf{\vec u}_i\cdot\mathbf{\vec u}_j)} $

   其中 $ \mathbf{\vec u}_i,\mathbf{\vec u}_j $ 为两个顶点的 embedding 向量。

   我们使用 AUC 来评估二类分类器的预测能力，结果如下。结果表明：

   • 所有的神经网络模型都优于谱聚类，这表明神经网络embedding 对于学习顶点潜在特征的有效性。
   • EOE 方法在四个时间都优于其它模型，这表明 EOE 方法捕捉的信息更全面、准确。

   

   为了从实验的角度研究 EOE 性能优异的原因，我们研究这些方法如何针对测试样本进行预测。我们给出两个具有代表性的测试样本。这两个测试样本是发生在 CVPR'10 和 SIGIR'10 会议的两个co-authorship 关系。

   • 所有的 baseline 方法都低估这两个未来链接发生的概率。
   • EOE 通过 author 之间共享相似的研究方向的信息（通过common word 给出）给出了最佳的预测。
   • LINE(2nd) 给出的预测结果被忽略，因为它对所有测试样本（包括不存在 co-authorship 的 author pair 对）预测的概率都接近 100% 。我们不知道原因，并且其背后的原因也不在本文讨论范围之内。但是我们知道 LINE(2nd) 的学习目标是保留二阶邻近度，而推断新的链接是预测一阶邻近度，二者不匹配。

   

3. 缺失链接预测问题是推断未观察到的现有交互。对于缺失链接预测，我们部署了其它三个任务，即论文引用预测、社交网络的 friendship 预测、基因交互预测。

   • 对于论文引用预测，我们采用 Embedding 可视化任务相同的数据集，但是这里考虑的是论文引用 paper citation关系，而不是 co-authorship 关系。我们采用 2000~2009 年的论文，过滤掉该时间段内未发表的参考文献，并且过滤掉词频小于5 的单词。最终论文引文子网络包含 6904 篇论文、19801 个引用关系（链接），单词子网络包含 8992 个单词、118518 条链接，论文和单词之间有 59471 条链接。
   • 对于基因交互预测，我们从 SLAP 数据集构建 gene and chemical compound network ，该数据集包含基因以及化合物之间的关系。基因子网络包含基因和基因之间的相互作用，化合物子网络包含化合物之间是否具有相同的本体，两个子网络之间包含基因和化合物之间的作用。最终化合物子网络有 883 个顶点、70746 个链接，基因子网络有 2472 个基因、4396 条链接，基因和化合物之间存在 1134 条链接。
   • 对于社交网络 friendship 预测，我们从 BlogCatalog 构建 user and word network 。我们选择四种热门类型（艺术、计算机、音乐、摄影）的用户，这包含 5009 个用户，用户之间存在 28406 条链接。我们基于这些用户的博客来构建单词子网络，词频小于 8 的单词被过滤掉。我们采用窗口大小为 5 的滑动窗口来生成单词共现关系。最终得到的单词子网络包含 9247 个单词、915655 条链接。用户和单词之间存在 350434 条链接。

   我们开展了10次实验，分别对训练集中的链接保留比例从 0%~90% 。其中， 0% 的保留比例即丢弃所有链接，这将导致冷启动问题。

   • 目前任何 baseline 模型都无法解决冷启动问题，因为所有 baseline 模型都依赖于已有的链接来学习潜在特征，而 EOE 可以通过补充信息来解决冷启动问题。
   • 在所有比例的情况下，EOE 仍然优于基准方法，这说明了EOE 针对耦合异质网络联合学习 embedding 的优势。

   

10.2.3 多分类

1. 多分类任务需要预测每个样本的类别，其中类别取值有多个，每个样本仅属于其中的某一个类别。这里使用论文引用预测任务（Paper citation）中使用的 paper and word network 。具体而言，分类任务是预测每篇论文的研究领域，可以是数据库、数据挖掘、及其学习、信息检索四个领域之一。

   我们开展了 10次实验，分别对训练集中的链接保留比例从 10%~100% 。一旦学到潜在特征，我们使用具有线性核的 SVM 来执行分类任务。我们采用 10-fold 交叉验证的平均准确率作为评估指标，结果如下：

   • EOE 在所有比例的情况下，始终优于其它 baseline 模型。
   • 当链接比例越少（如 10%~20%），EOE 相比于 baseline 模型的提升越明显。这是因为论文的摘要中包含了大量的关于论文研究领域的信息，EOE 可以很好的利用这些信息。

   

10.2.4 多标签分类

1. 多类分类任务需要预测每个样本的类别，其中每个样本可以属于多个类别。

   我们使用可视化中的 author and word network 来预测 author 的领域，一些 author 可能是多个领域的专家，因为他们在多个领域的会议上发表论文。此外，链接预测任务中使用的 BlogCatalog user and word network 也用于该实验，因为用户注册的博客可以属于多个类别。

   我们开展了5次实验，分别对训练集中的链接保留比例从 20%~100% 。一旦学到潜在特征，我们对学到的 author representation 执行二元 SVM 从而进行多领域预测任务。我们采用 10-fold 交叉验证的Micro-F1 和 Macro-F1 作为评估指标，结果如下：

   • EOE 在所有任务中都超越了 baseline 模型。
   • 当链接比例越少（如 20%），EOE 相比于 baseline 模型的提升越明显。

   

2. 结合可视化任务、链接预测任务、多分类任务、多标签分类人任务的实验结果，这表明 inter-networks edge 提供的互补信息是有益的，因为这些互补信息可以使得从 intra-network edge 学到的潜在特征更加全面和准确，并且在遇到冷启动问题时更为重要。

3. 从可视化任务、链接预测任务、多类分类任务、多标签分类任务可以看到：多个子网络之间的链接提供的额外补充信息是有益的，因为它可以使得学到的潜在特征更加准确、全面，这在解决冷启动问题时尤为重要。

10.2.5 参数探索

1. EOE 模型有两种主要的超参数：正则项的系数、潜在特征维度。在所有之前的实验中，这两个超参数都固定为常数，正则化系数设置为 1.0，潜在特征维度为 128 。这里我们将正则化系数分别设置为 0.1,0.5,1.0,2.0,5.0,10.0 、将潜在特征维度分别设置为 32,64,128,256,512，然后观察这些超参数的影响。

   注意：研究潜在特征维度时，正则化系数固定为 1.0；研究正则化系数时，潜在特征维度固定为 128 。我们的训练数据集为 DBLP co-authorship 数据集。

   • 潜在特征维度：可以看到 EOE 对于潜在特征维度不是特别敏感，只要该值不是太小。最佳性能出现在潜在特征维度为 128 时。

     

   • 正则化系数：可以看到 EOE 对于正则化系数更为敏感，当正则化系数为 1.0 时模型效果最好。