二十一、MVE [2017]

发布于 2023-07-17 23:38:24 字数 111907 浏览 0 评论 0 收藏 0

由于在现实世界中的广泛应用，挖掘和分析大规模信息网络（如社交网络、引文网络、航空网络）最近引起了很多关注。为了有效地、高效地挖掘此类网络，首要条件是找到有意义的 network representation 。传统上，网络被表示为节点的邻接矩阵，这个矩阵既是高维的、又是稀疏的。最近，人们越来越关注将网络表示为低维空间（也称作 network embedding），其中每个节点都用一个低维向量来表示。这样的向量能够保持节点之间的邻近性proximity ，因此可被视为节点特征并有助于各种下游应用（如节点分类、链接预测、节点可视化）。
尽管这些工作在许多网络中经验性地有效和高效，但是它们都假设网络中的节点之间仅存在一种类型的邻近性，而实际上网络中存在多种类型的邻近性。以科技文献中作者之间的网络为例，可以通过 co-authorship 关系来得到邻近性，即两位作者是否曾经共同撰写过同一篇论文；也可以通过引用关系来得到邻近性，即一位作者是否引用另一位作者的论文。另一个例子是社交网站中用户之间的网络，其中存在多种类型的邻近性，例如由关注（following-followee）、回复、转发、引用等关系所产生的邻近性。每种邻近性定义了一个网络视图，多个邻近性产生了一个具有多视图multiple views 的网络。每个单独的视图通常是稀疏sparse 的、有偏biased 的，因此现有方法学到的node representation 可能不是那么全面。为了学到更鲁棒的 node representation，一个自然的解决方案可能是利用来自多个视图的信息。
这促使我们研究一个新的问题：学习多视图网络的 node representation ，旨在通过考虑网络的多个视图来学习节点的 robust representation。在文献中，人们已经提出了各种方法来从多个视图中学习数据 representation，例如多视图聚类 multi-view clustering 方法、多视图矩阵分解multi-view matrix factorization 方法。这些方法在许多application 上表现良好，例如聚类任务、推荐任务。但是，当应用于我们的问题时，它们具有以下局限性：
- 视图协同collaboration 不足。由于网络的每个单独的视图通常都是有偏biased 的，因此学习节点的 robust representation 需要多个视图的协同。然而，大多数现有的多视图学习方法旨在找到跨不同视图的 compatible representation，而不是促进不同视图的协同从而找到节点的 robust representation 。
- 缺乏权重学习 weight learning 。为了学习节点的 robust representation，需要整合来自多个视图的信息。在集成过程中，由于不同视图的重要性可能存在差异，因此需要仔细确定它们的权重。现有方法通常为所有视图分配相同的权重。换句话讲，不同的视图被同等对待，这对于大多数多视图网络而言是不合理的。
为了克服这些限制，我们正在寻求一种能够促进不同视图协同，并在集成过程中自动推断视图权重的方法。
在论文《An Attention-based Collaboration Framework for Multi-View Network Representation Learning》中，作者提出了这种方法。作者首先引入一组 view-specific 的node representation ，从而保持不同视图中节点的邻近性。然后作者组合 view-specific 的node representation 从而用于投票出节点的 robust representation 。由于不同视图的信息量可能不同，因此理想的情况下，在投票过程中需要以不同的方式对待每个视图。换句话讲，每个视图的权重应该不同。受到最近神经机器翻译neural machine translation 中注意力机制attention mechanism 进展的启发，在论文中作者提出了一种基于注意力的方法来推断不同节点的各个视图权重。该方法利用一些标记数据。整个模型可以通过反向传播算法进行有效地训练，在优化 view-specific node representation 、以及投票出节点的 robust representation （通过学习不同视图的权重）之间交替进行。
作者对各种现实世界的多视图网络进行了广泛的实验。多标签节点分类任务、链接预测任务的实验结果表明：论文提出的方法优于用于学习单视图 node representation 的最新方法、以及多视图的其它竞争性方法。
总之，论文贡献如下：
- 论文建议研究 multi-view network representation learning，旨在通过利用来自多个视图的信息来学习 node representation。
- 论文提出了一个新颖的协同框架，该框架促进了不同视图的协同collaboration ，以投票的方式得到节点的 robust representation。论文引入了一种注意力机制，用于在投票期间学习不同视图的权重。
- 论文在几个多视图网络上进行了实验。两项任务的实验结果证明了所提出的方法在许多竞争性的 baseline 上的效率和效果。
相关工作：我们的工作与现有的、用于学习 network representation 的 scalable 方法有关，包括 DeepWalk, LINE, node2vec。这些方法使用不同的搜索策略来探索网络结构：深度优先搜索 depth-first search: DFS、广度优先搜索 breadth-first search: BFS、以及这两种搜索策略的组合。然而，所有这些方法都侧重于学习单视图网络single-view network 的 node representation，而我们研究多视图网络multiple-view network 。
另一类相关工作是多视图学习multi-view learning ，旨在利用来自多个视图的信息，并在分类、聚类、ranking、主题模型topic modeling 等任务中显示出有效性。与我们最相似的工作是多视图聚类、以及多视图矩阵分解方法。例如：
- 《Co-regularized multi-view spectral clustering》 提出了一个谱聚类spectral clustering 框架来正则化regularize不同视图的聚类假设clustering hypotheses 。
- 《Multiview spectral embedding》 提出了一种多视图非负矩阵分解模型，旨在最小化每个视图的相关系数矩阵 coefficient matrix 和共性矩阵 consensus matrix 之间的距离。
我们的多视图 network representation 方法与这些工作具有相似的直觉，旨在找到跨多个视图的、鲁棒的 data representation 。然而，主要区别在于现有方法为所有视图分配相同的权重，而我们的方法采用基于注意力的方法，从而为不同节点学习不同的视图投票权重。
此外，我们的工作还与基于注意力的模型 attention based model有关。基于注意力的模型旨在推断训练数据不同部分的重要性，并让 learning 算法专注于信息量最大的部分。基于注意力的模型已经应用于各种任务，包括图像分类、机器翻译、语音识别。据我们所知，这是在 multi-view network representation learning 问题中首次尝试使用基于注意力的方法。

21.1 模型

21.1.1 基本概念

信息网络Information Network定义：信息网络 $G = (V, E)$ $ G=(\mathcal V,\mathcal E) $ 编码不同对象之间的关系，其中 $V$ $ \mathcal V $ 为节点集合（每个节点代表一个对象）， $E$ $ \mathcal E $ 为边的集合。每条边 $e = (u, v)$ $ e = (u,v) $ 关联一个权重 $w_{u, v} > 0$ $ w_{u,v}\gt 0 $ ，表示节点 $u$ $ u $ 和节点 $v$ $ v $ 之间关系的强度。
一个网络视图来自于节点之间的、单一类型的关系或邻近性proximity，可以用一个边集合 $E$ $ \mathcal E $ 来刻画。
传统上，网络被表示为稀疏的、高维的邻接矩阵。最近，人们越来越关注学习网络的低维向量 representation （也称作 network embedding ）。
Network Embedding 定义：给定一个信息网络 $G = (V, E)$ $ G=(\mathcal V,\mathcal E) $ ，network embedding 问题旨在为每个节点 $v \in V$ $ v\in \mathcal V $ 学习一个低维向量 representation ${\vec{x}}_{v} \in R^{d}$ $ \mathbf{\vec x}_v\in \mathbb R^d $ （其中 $d ≪ | V |$ $ d\ll |\mathcal V| $ ），该representation 保留节点之间的邻近性。
最近人们已经提出了各种 network embedding 方法。尽管它们已被证明在各种场景中有效果、高效率，但是它们都专注于具有单一类型关系的网络。然而，在现实中，我们经常观察到节点之间多种类型的关系。例如，对于社交网站（如 Twitter）的用户，除了 following（关注）关系之外，还存在其它关系，如转发retweet 、引用mention 等关系。每种类型的关系定义了节点之间的一个网络视图，而多种类型的关系产生了具有多个视图的网络。网络的不同视图之间通常互补，因此考虑多个视图可能有助于学习节点的 robust representation。这促使我们研究学习多视图网络的 node representation 问题。
Multi-view Network Embedding 定义：给定带 $K$ $ K $ 个视图的信息网络 $G = (V, E_{1}, E_{2}, \dots, E_{K})$ $ G=(\mathcal V, \mathcal E_1,\mathcal E_2,\cdots,\mathcal E_K) $ ，多视图network embedding 旨在为每个节点 $v \in V$ $ v\in \mathcal V $ 学到低维的 robust representation ${\vec{x}}_{v} \in R^{d}$ $ \mathbf{\vec x}_v\in \mathbb R^d $ （其中 $d ≪ | V |$ $ d\ll |\mathcal V| $ ），该 representation 在不同的视图中是一致 consistent 的。
为了学习跨不同视图的、节点的 robust representation，我们需要设计一种方法来促进不同视图的协同、并投票来产生节点的 robust representation。由于视图的质量不同，该方法还应该能够在投票期间对不同的视图进行不同的加权。
这里我们介绍我们提出的、用于嵌入多视图网络的方法。大多数现有的多视图 network embedding 方法，例如多视图聚类和多视图矩阵分解算法，都未能取得令人满意的结果。这是因为它们在训练过程中不能有效地促进不同视图的协同。此外，在组合多视图信息时，这些方法也无法为不同的视图分配合适的权重。
为了解决这些挑战：
- 我们的方法首先挖掘了编码单个视图的邻近性的node representation。在编码期间，我们提出了一个协同框架 collaboration framework 来促进不同视图的协同。
- 然后，我们通过投票vote 来进一步集成不同的视图，从而得到节点的 robust representation。在投票过程中，我们通过基于注意力的机制来自动学习每个视图的投票权重。
我们的目标函数总结为：
$O = O_{collab} + O_{attn}$
其中：
- $O_{collab}$ $ \mathcal O_\text{collab} $ 为协同框架的目标函数，其目标是学习单个视图的节点邻近性，同时通过投票来产生节点的 robust representation 。
- $O_{attn}$ $ \mathcal O_\text{attn} $ 是学习投票权重的目标函数。
注意：这里并没有引入超参数来平衡这两个目标函数。理论上可以引入超参数，比如 $λ$ $ \lambda $ ，使得 $O = O_{collab} + λ O_{attn}$ $ \mathcal O = \mathcal O_\text{collab} + \lambda \mathcal O_\text{attn} $ 。
我们的方法如下所示，其中：黄色部分为协同框架，蓝色部分为基于注意力的权重学习，不同颜色的边代表不同的视图（共有三个视图），红色的节点为待分类的节点。

12.1.2 协同框架

collaboration framework 协同框架的目标是学习编码了单个视图节点邻近性的node representation ，同时将它们集成起来通过投票产生节点的 robust representation 。对于每个节点 $v_{i} \in V$ $ v_i\in \mathcal V $ ，我们引入 view-specific representation ${{\vec{x}}_{i}^{k}}_{k = 1}^{K}$ $ \left\{\mathbf{\vec x}_i^k\right\}_{k=1}^K $ 来编码单个视图中的结构信息。我们还引入了节点的 robust representation ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ 来集成所有视图中的信息。
考虑视图 $k$ $ k $ ，为保持视图 $k$ $ k $ 中的结构信息，对视图 $k$ $ k $ 中的每条有向边 $(v_{i}, v_{j})$ $ (v_i,v_j) $ ，定义它们之间存在链接的概率为条件概率 $p_{k} (v_{j} ∣ v_{i})$ $ p_k(v_j\mid v_i) $ 为：
$p_{k} (v_{j} ∣ v_{i}) \propto \exp ({\vec{x}}_{j}^{k} \cdot {\vec{c}}_{i})$
这意味着 $p_{k} (v_{j} ∣ v_{i}) = \frac{\exp ({\vec{x}}_{j}^{k} \cdot {\vec{c}}_{i})}{\sum_{j^{'}} \exp ({\vec{x}}_{j^{'}}^{k} \cdot {\vec{c}}_{i})}$ $ p_k(v_j\mid v_i) = \frac{\exp\left(\mathbf{\vec x}_j^k\cdot \mathbf{\vec c}_i\right)}{\sum_{j^\prime} \exp\left(\mathbf{\vec x}_{j^\prime}^k\cdot \mathbf{\vec c}_i\right)} $ 。
其中 ${\vec{c}}_{i}$ $ \mathbf{\vec c}_i $ 为节点 $v_{i}$ $ v_i $ 的 context representation 。在我们的方法中，节点 $v_{i}$ $ v_i $ 的context representation在所有视图之间共享，这使得不同的view-specific representation 将位于相同的语义空间中。我们还尝试了对不同视图采用不同的 context representation ，这作为我们方法的一个变种，并在试验中进行比较。
context representation在所有视图之间共享，这使得节点的 view-specific representation 位于相同的语义空间中，这就是 “协同” 的含义。
根据定义，概率分布 $p_{k} (\cdot ∣ v_{i})$ $ p_k(\cdot\mid v_i) $ 定义了视图 $k$ $ k $ 中节点 $v_{i}$ $ v_i $ 的邻居分布 neighbor distribution 。定义视图 $k$ $ k $ 中节点 $v_{i}$ $ v_i $ 的经验邻居分布为 ${\hat{p}}_{k} (\cdot ∣ v_{i})$ $ \hat p_k(\cdot\mid v_i) $ ，则 view-specific representation 的目标是最小化邻居分布 $p_{k} (\cdot ∣ v_{i})$ $ p_k(\cdot\mid v_i) $ 和经验领居分布 ${\hat{p}}_{k} (\cdot ∣ v_{i})$ $ \hat p_k(\cdot\mid v_i) $ 的距离。这里我们采用 KL 散度作为概率分布之间的距离的度量。
我们将经验邻居分布定义为 ${\hat{p}}_{k} (v_{j} ∣ v_{i}) = w_{i, j}^{(k)} / d_{i}^{(k)}$ $ \hat p_k(v_j\mid v_i) = w_{i,j}^{(k)} / d_i^{(k)} $ ，其中： $w_{i, j}^{(k)}$ $ w_{i,j}^{(k)} $ 为视图 $k$ $ k $ 中边 $(v_{i}, v_{j})$ $ (v_i,v_j) $ 的权重； $d_{i}^{(k)}$ $ d_i^{(k)} $ 为视图 $k$ $ k $ 中节点 $v_{i}$ $ v_i $ 的出度 out degree，即 $d_{i}^{(k)} = \sum_{j} w_{i, j}^{(k)}$ $ d_i^{(k)} = \sum_j w_{i,j}^{(k)} $ 。
经过简化之后，视图 $k$ $ k $ 的 view-specific representation 的目标函数为：
$O_{k} = - \sum_{(i, j) \in E_{k}} w_{i, j}^{(k)} \log p_{k} (v_{j} ∣ v_{i})$
该目标函数优化一阶邻近性（即直接邻域）。
直接优化视图 $k$ $ k $ 的目标函数代价太大，因为在计算条件概率 $p_{k} (v_{j} ∣ v_{i})$ $ p_k(v_j\mid v_i) $ 时需要遍历所有的节点。这里我们采用负采样negative sampling 技术，从而简化了条件概率的计算：
$p_{k} (v_{j} ∣ v_{i}) = \log σ ({\vec{x}}_{j}^{k} \cdot {\vec{c}}_{i}) + \sum_{n = 1}^{N} E_{v_{n} \propto P_{neg}^{k} (v)} [\log σ (- {\vec{x}}_{n}^{k} \cdot {\vec{c}}_{i})]$
其中 $σ (x) = \frac{1}{1 + \exp (- x)}$ $ \sigma(x) = \frac{1}{1+\exp(-x)} $ 为 sigmoid 函数， $N$ $ N $ 为负采样比例。
- 第一项用于最大化“正边”，即观察到的边 observed edge 。
- 第二项用于最小化“负边”，即不存在的噪音边noisy edge。其中 $v_{n}$ $ v_n $ 是从噪音分布 $P_{neg}^{k} (v) \propto {(d_{v}^{(k)})}^{3 / 4}$ $ P^k_\text{neg}(v)\propto \left(d_v^{(k)}\right)^{3/4} $ 采样到的噪音节点， $d_{v}^{(k)}$ $ d_v^{(k)} $ 为视图 $k$ $ k $ 中节点 $v$ $ v $ 的出度。
通过最小化 view-specific representation 的目标函数， ${{\vec{x}}_{i}^{k}}_{k = 1}^{K}$ $ \left\{\mathbf{\vec x}_i^k\right\}_{k=1}^K $ 可以保留不同视图中的结构信息。然后我们通过投票来促进不同视图的协同，从而得到节点的robust representation。在投票过程中由于各个视图的重要性可能不同，因此我们需要为每个视图分配不同的权重。
考虑所有这些因素，我们引入正则化项：
$R = \sum_{i = 1}^{| V |} \sum_{k = 1}^{K} λ_{i}^{k} {‖ {\vec{x}}_{i}^{k} - {\vec{x}}_{i} ‖}_{2}^{2}$
其中： $| | \cdot | |_{2}$ $ ||\cdot||_2 $ 为 $L_{2}$ $ L_2 $ 正则化； $λ_{i}^{k}$ $ \lambda_i^k $ 为节点 $v_{i}$ $ v_i $ 在视图 $k$ $ k $ 中的正则化系数，它也是表示视图 $k$ $ k $ 的重要性。
该正则化使得最终的robust representation 与各view-specific representation 保持一致。其物理意义为：
- 一方面，要求节点的 robust representatioin ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ 尽可能保留不同视图中的结构信息，即尽可能逼近 ${{\vec{x}}_{i}^{k}}_{k = 1}^{K}$ $ \left\{ \mathbf{\vec x}_i^k\right\}_{k=1}^K $ 。这也是view-specific representation 的一致性consistency 。
- 另一方面，如果节点的 robust representation 无法保留所有视图中的结构信息，则它保留较重要的那些视图的结构信息。即尽可能逼近 $λ_{i}^{k}$ $ \lambda_i^k $ 较大的那些 ${\vec{x}}_{i}^{k}$ $ \mathbf{\vec x}_i^k $ 。
  如果采用相等的权重，那么 $R$ $ \mathcal R $ 最优化的解就是各 view-specific representation 的均值。
直观而言，通过为每个节点 $v_{i}$ $ v_i $ 学习适当的权重 ${λ_{i}^{k}}_{k = 1}^{K}$ $ \left\{\lambda_i^k\right\}_{k=1}^K $ ，我们的方法可以让每个节点专注于信息量最大的视图。我们将在下一节介绍如何自动学习这些权重。
最终，不同的view-specific representation 基于以下方式投票从而产生 robust representation：
${\vec{x}}_{i} = \sum_{k = 1}^{K} λ_{i}^{k} {\vec{x}}_{i}^{k}$
视图的权重作用在两个地方：投票产生 robust representation、不同视图的正则化系数。
根据 $R = \sum_{i = 1}^{| V |} \sum_{k = 1}^{K} λ_{i}^{k} {‖ {\vec{x}}_{i}^{k} - \sum_{s = 1}^{K} λ_{i}^{s} {\vec{x}}_{i}^{s} ‖}_{2}^{2}$ $ \mathcal R = \sum_{i=1}^{|\mathcal V|}\sum_{k=1}^K \lambda_i^k \left\|\mathbf{\vec x}_i^k - \sum_{s=1}^K\lambda_i^s \mathbf{\vec x}_i^s\right\|_2^2 $ 可以看到，权重在 $R$ $ \mathcal R $ 是三次多项式的关系，这更加强化了信息量大的视图。
很自然地， robust representation 被计算为 view-specific representation 的加权组合，加权系数为视图的投票权重，这非常直观。
通过整合view-specific representation 学习阶段的目标、投票阶段的目标（即正则化项），则协同框架的最终目标为：
$O_{collab} = \sum_{k = 1}^{K} O_{k} + η R$
其中 $η$ $ \eta $ 为平衡正则化项的系数。
当 $η = 0$ $ \eta = 0 $ 时，不考虑 view-specific representation 之间的一致性。

12.1.3 attention 机制

上述框架提出了一种灵活的方式让不同的视图相互协同。这里我们介绍一种基于 attention 机制，用于在投票期间学习不同视图的权重。我们提出的方法非常通用，只需要提供少量标记数据就可以为 specific-task 学习不同节点的视图权重。
基于attention 机制，我们使用 softmax 单元来定义节点 $v_{i}$ $ v_i $ 的视图 $k$ $ k $ 的权重为：
$λ_{i}^{k} = \frac{\exp ({\vec{z}}_{k} \cdot {\vec{x}}_{i}^{C})}{\sum_{k^{'} = 1}^{K} \exp ({\vec{z}}_{k^{'}} \cdot {\vec{x}}_{i}^{C})}$
其中：
- ${\vec{x}}_{i}^{C} = {(x_{i, 1}^{1}, \dots, x_{i, d}^{1}, \dots, x_{i, d}^{K})}^{⊤} \in R^{K d}$ $ \mathbf{\vec x}_i^C = \left(x^1_{i,1},\cdots,x^1_{i,d},\cdots,x^K_{i,d}\right)^\top\in \mathbb R^{Kd} $ 为所有的 view-specific representation 的拼接向量
- ${\vec{z}}_{k} \in R^{K d}$ $ \mathbf{\vec z}_k\in \mathbb R^{Kd} $ 为视图 $k$ $ k $ 的特征向量 feature vector，用于描述哪些特征的节点认为视图 $k$ $ k $ 是信息质量较高的（informative）。
  这里 ${\vec{z}}_{k}$ $ \mathbf{\vec z}_k $ 是与节点无关、仅与视图相关，因此它是跨所有节点共享的。另外，这里的 $λ_{i}^{k}$ $ \lambda_i^k $ 是权重归一化的，即使所有视图对于 $v_{i}$ $ v_i $ 都是没有信息量的，权重也是非零的。
  这里使用拼接后的向量作为 query，而没有使用每个视图的 representation 向量作为 query。后者使用局部的、单个视图的 representation，前者使用全局的、所有视图的 representation。
当 ${\vec{x}}_{i}^{C} \cdot {\vec{z}}_{k}$ $ \mathbf{\vec x}_i^C \cdot \mathbf{\vec z}_k $ 较大时，则意味着节点 $v_{i}$ $ v_i $ 认为视图 $k$ $ k $ 是信息量较高的，因此节点 $v_{i}$ $ v_i $ 的视图 $k$ $ k $ 将分配较大的权重。
另外，每个节点的视图权重将由其view-specific representation 的拼接向量 ${\vec{x}}_{i}^{C}$ $ \mathbf{\vec x}_i^C $ 来决定，因此，邻近性较大的两个节点可能学到相似的 view-specific representation，因此视图权重也相似。这种性质是合理的，这使得我们能够利用 view-specific representation 中保留的邻近性更好地推断不同节点的注意力，即相似的representation 有相似的attention 。
一旦学到视图的权重，则可以通过 ${\vec{x}}_{i} = \sum_{k = 1}^{K} λ_{i}^{k} {\vec{x}}_{i}^{k}$ $ \mathbf{\vec x}_i = \sum_{k=1}^K\lambda_i^k \mathbf{\vec x}_i^k $ 来得到节点的 robust representation 。然后我们可以将该representation 应用于不同的预测任务，并基于部分标记数据来使用反向传播算法来自动学习投票权重。
以节点分类任务为例，我们基于视图的特征向量 ${{\vec{z}}_{k}}_{k = 1}^{K}$ $ \{\mathbf{\vec z}_k\}_{k=1}^{K} $ 来最小化以下目标函数：
$O_{attn} = \sum_{v_{i} \in S} L ({\vec{x}}_{i}, y_{i})$
其中： $S$ $ \mathcal S $ 为带标签的节点集合； ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ 为节点 $v_{i}$ $ v_i $ 的 robust representation； $y_{i}$ $ y_i $ 为节点 $v_{i}$ $ v_i $ 的标签； $L (\cdot, \cdot)$ $ \mathcal L(\cdot,\cdot) $ 为task-specific 损失函数。
我们根据梯度下降法来求解该最优化问题，其梯度为：
$\nabla_{{\vec{z}}_{k}} O_{attn} = \sum_{v_{i} \in S} [\sum_{l = 1}^{K} (\frac{\partial O_{attn}}{\partial λ_{i}^{k}} - \frac{\partial O_{attn}}{\partial λ_{i}^{l}}) λ_{i}^{k} λ_{i}^{l}] {\vec{x}}_{i}$
一旦求解出参数 ${{\vec{z}}_{k}}_{k = 1}^{K}$ $ \{\mathbf{\vec z}_k\}_{k=1}^{K} $ 之后，所有节点（无论有标签还是无标签）的各个视图的权重 $λ_{i}^{k}$ $ \lambda_i^k $ 就可以直接计算出来。在实验中我们证明了权重学习仅需要少量标记数据即可收敛，并还将证明该方法非常有效。
总的目标函数为： $O = \sum_{k = 1}^{K} O_{k} + η R + \sum_{v_{i} \in S} L ({\vec{x}}_{i}, y_{i})$ $ \mathcal O = \sum_{k=1}^K \mathcal O_k + \eta \mathcal R + \sum_{v_i\in \mathcal S} \mathcal L(\mathbf{\vec x}_i,y_i) $ ，其中第一、二项为 $O_{collab}$ $ \mathcal O_\text{collab} $ ，第三项为 $O_{attn}$ $ \mathcal O_\text{attn } $ 。注意， $O_{attn}$ $ \mathcal O_\text{attn} $ 可以乘以超参数 $γ$ $ \gamma $ 从而平衡注意力损失函数的重要性，但是论文未使用这种方式从而直接用原始的注意力损失。
在本文中，我们研究两类预测任务：节点分类、链接预测。
- 在节点分类任务中，目标函数定义为：
  $O_{attn}^{class} = \sum_{v_{i} \in S} | | \vec{w} \cdot {\vec{x}}_{i} - {\vec{y}}_{i} | |_{2}^{2}$
  其中： ${\vec{y}}_{i}$ $ \mathbf{\vec y}_i $ 为标签 $y_{i}$ $ y_i $ 的 one-hot 向量； $\vec{w}$ $ \mathbf{\vec w} $ 为分类器的参数。
- 在链接预测任务中，目标函数定义为：
  $O_{attn}^{link} = - \sum_{(v_{i}, v_{j}) \in S} \cos ({\vec{x}}_{i}, {\vec{x}}_{j})$
  其中： $(v_{i}, v_{j})$ $ (v_i,v_j) $ 为存在链接的节点pair 对； $\cos (\cdot, \cdot)$ $ \cos(\cdot,\cdot) $ 为向量的 cos 相似度。

12.1.4 优化

我们使用梯度下降法和反向传播算法来优化模型。具体地说，在每轮迭代中：
- 我们首先从网络中采样一组边，并优化节点的 view-specific representation ${{\vec{x}}_{i}^{k}}_{k = 1}^{K}$ $ \left\{\mathbf{\vec x}_i^k\right\}_{k=1}^K $ 。
- 然后我们使用标记数据来训练视图的参数向量 ${{\vec{z}}_{k}}_{k = 1}^{K}$ $ \{\mathbf{\vec z}_k\}_{k=1}^{K} $ ，并更新不同节点的视图投票权重 ${λ_{i}^{k}}_{k = 1}^{K}$ $ \{\lambda_i^k\}_{k=1}^{K} $ 。
- 最后，基于学到的视图投票权重，我们集成节点的view-specific representation 来得到节点的 robust representation 。
算法本质上是一个半监督学习，以多任务的形式进行学习：无监督地优化节点邻近性损失、监督地优化节点分类损失。训练是以交替优化无监督损失、监督损失的方式进行。
MVE 算法：
- 输入：
  - 多视图网络 $G = (V, E_{1}, E_{2}, \dots, E_{K})$ $ G=(\mathcal V,\mathcal E_1,\mathcal E_2,\cdots,\mathcal E_K) $
  - 标记数据 $S$ $ \mathcal S $
  - 更新 view-specific representation 中采样的样本数 $T$ $ T $
  - 负采样比例 $N$ $ N $
- 输出：节点的 robust representation ${{\vec{x}}_{i}}_{i = 1}^{| V |}$ $ \{\mathbf{\vec x}_i\}_{i=1}^{|\mathcal V|} $
- 算法步骤：
  迭代直到算法收敛，迭代步骤为：
  - 更新节点的 view-specific representation。更新方式为：迭代直到本轮采样的“正边”数量大于 $T$ $ T $ 。迭代过程为：
    - 随机选择一个视图，记作视图 $k$ $ k $
    - 从 $E_{k}$ $ \mathcal E_k $ 中随机采样一条“正边”、以及 $N$ $ N $ 条“负边”
    - 求解 $\nabla_{{\vec{x}}_{i}^{k}} (O_{collab} + O_{attn})$ $ \nabla_{\mathbf{\vec x}_i^k} (\mathcal O_\text{collab} + \mathcal O_\text{attn}) $ ，根据该梯度来更新节点的 view-specific representation
    - 求解 $\nabla_{{\vec{c}}_{i}} O_{collab}$ $ \nabla_{\mathbf{\vec c}_i} \mathcal O_\text{collab} $ ，根据该梯度来更新节点的 context representation
  - 更新顶点的投票权重。更新方式为：
    - 求解 $\nabla_{{\vec{z}}_{k}} O_{attn}$ $ \nabla_{\mathbf{\vec z}_k} \mathcal O_\text{attn} $ ，根据该梯度来更新视图的特征向量 ${\vec{z}}_{k}$ $ \mathbf{\vec z}_k $

通过 ${\vec{z}}_{k}$ $ \mathbf{\vec z}_k $ 来更新每个视图的权重 ${λ_{i}^{k}}_{k = 1}^{K}$ $ \{\lambda_i^k\}_{k=1}^K $
- 更新节点的 robust representation

MVE 算法由三个过程组成：
- view-specific representation 学习过程：该过程根据未标记数据、标记数据分别来学习节点的 view-specific representation 。根据之前的研究，这部分的计算复杂度为 $O (| E | \times d \times N)$ $ O(|\mathcal E|\times d\times N) $ ，其中 $| E |$ $ |\mathcal E| $ 为所有视图的边的总数， $d$ $ d $ 为节点representation 的维度， $N$ $ N $ 为负采样比例。
- robust representation 学习过程：该过程根据每个节点的view-specific representation 投票得到最终的 robust representation。这部分的计算复杂度为 $O (| V | \times d \times K)$ $ O(|\mathcal V|\times d\times K) $ ，其中 $K$ $ K $ 为视图总数。
- 投票权重学习过程：这部分通过注意力机制来学习每个视图的投票权重。这部分的计算复杂度为 $O (| S | \times d \times K)$ $ O(|\mathcal S|\times d\times K) $ ，其中 $| S |$ $ |\mathcal S| $ 为标记样本数量。实际应用中，我们通常采样非常少的标记样本，即 $| S | ≪ | V |$ $ |\mathcal S|\ll |\mathcal V| $ 。
考虑到大多数网络有 $| V | ≪ | E |$ $ |\mathcal V|\ll |\mathcal E| $ ，因此总的算法复杂度为 $O (| E | \times d \times N)$ $ O(|\mathcal E|\times d\times N) $ ，它和图中边的总数成正比。对于大多数真实世界的网络，由于边的数量通常是稀疏的，因此大多数情况下我们的方法计算效率较高。

21.2 实验

数据集：一共包含 5 个数据集，其中前三个数据集用于节点分类任务，后两个数据集用于链接预测任务。
- DBLP：包含来自计算机科学领域论文的作者author。网络包含三种类型的视图：
  - co-authorship 视图：边的类型定义为作者之间共同发表论文的关系，边的权重为共同发表文章的数量。
  - author-citation 视图：边的类型定义为作者之间的论文引用关系，边的权重为作者 $i$ $ i $ 的论文引用作者 $j$ $ j $ 的论文的数量。
  - text-similariry 视图：边的类型定义为作者论文之间的相似度，边的权重为每个作者发表论文的标题、摘要计算得到的 TF-IDF 的 cos 相似度，每个顶点仅保留最相似的 5 个邻居顶点的链接及其权重。
  我们选择8 个不同的研究领域作为label，包括 machine learning, computational linguistics, programming language, data mining, database, system technology, hardware, theory 。对于每个 label 我们选择该领域若干个具有代表性的会议，并且只有在这些会议中发表的论文才用于构建这三个视图。
- Flickr 数据集：一个在线图片共享社区，用户彼此关注从而构成一个网络。用户可以为图片指定 tag ，我们将这些 tag 作为节点（用户）的属性。用于可以加入不同的组，我们将这些组作为用户的 label 。
  该网络包含两个视图：
  - friendship 视图：边的类型定义为用户之间的关注，边的权重为 0 （没有关注）或 1 关注。
  - tag-similarity 视图：边的类型定义为用户所有图片 tag 之间的相似性，边的权重就是 tag 之间的相似度。每个节点仅保留最相似的 100 个邻居节点的链接及其权重。
- PPI 数据集：一个 protein-protein interaction network ，只考虑人类基因作为节点。我们根据 coexpression, cooccurrance, database, experiments, fusion, neighborhood information 构建了六个视图。Hallmark 基因组提供的基因分组视为节点的类别。
  考虑到原始的网络非常稀疏，因此我们对每个视图通过添加邻居的邻居来扩展 degree 小于 1000 的节点的邻居集合，直到扩展的邻居集合的规模达到 1000 。
- Youtube 数据集：根据 Youtube 网络的用户社交数据构建的用户社交网络。我们构建了五个视图：
  - common friends 视图：边的类型定义为用户之间的共同好友，边的权重共同好友数量。
  - common subscription 视图：边的类型定义为共同订阅用户（站在subscriber的角度) ，边的权重为共同订阅用户数量。
  - common subscriber 视图：边的类型定义为共同订阅者（站在订阅用户的角度），边的权重为共同订阅者的数量。
  - common favorite video 视图：边的类型定义为共同喜爱的视频，边的权重为共同喜爱视频的数量。
  - friendship 视图：边的类型定义为是否好友关系，边的权重为 0 或 1 。
  我们认为 friendship 视图可以更好地反映用户之间的邻近性，因此我们使用前四个视图来训练，并预测第五个视图中的链接。
- Twitter 数据集：根据 Twitter 网络的用户社交数据构建的用户社交网络。由于原始网络的稀疏性，我们将其视为无向图。我们根据回复reply、转发 retweet、提及 mention、好友 friendship 等关系定义了四个视图，其中前三个视图用于训练（以 PPI 数据集相同的形式重建），预测第四个视图中的链接。
Baseline 模型：我们比较了两类方法：基于单视图single-view 的方法、基于多视图 multi-view 的方法。
- LINE：一种用于单视图、可扩展的embedding 方法。我们给出了它在所有单个视图的结果中，效果最好的那一个。
- node2vec：另一种用于单视图、可扩展的embedding 方法。我们给出了它在所有单个视图的结果中，效果最好的那一个。
- node2vec-merge：node2vec 的一个变种。为了融合多视图，我们合并了所有视图的边从而得到一个大的视图，然后通过 node2vec 来学习该视图的 embedding 。
- node2vec-concat：node2vec 的另一个变种。为了融合多视图，我们首先从每个视图学到 node embedding，然后将节点在每个视图的 embedding 拼接起来。
- CMSC：一个 co-regularized 多视图谱聚类模型。它可以应用于我们的任务，但是无法扩展到大规模的图。
  我们使用基于质心的变体，因为其效率更高并且质心的特征向量 eigen-vector 可以视作节点的 representation。
- MultiNMF：一个多视图的非负矩阵分解模型。它可以应用于我们的任务，但是无法扩展到大规模的图。
- MultiSPPMI：一个词向量模型，它通过分解单词的共现矩阵从而得到单词的 embedding 。这里我们通过联合分解不同视图的邻接矩阵，并在不同视图之间共享node representation ，从而利用该模型来学习node representation 。
- MVE：我们提出的方法，其中使用了协同框架和注意力机制。
- MVE-NoCollab：MVE 的一个变体。我们针对不同的视图引入了不同的 context node representation，因此节点的 view-specific representation 将位于不同的语义空间中。因此在训练期间，节点的 view-specific representation 无法协同。
- MVE-NoAttn：MVE 的另一个变体。我们在投票期间为每个视图赋予相同的权重，因此没有采用注意力机制。
注意，我们并没有比较 DeepWalk 模型，因为 DeepWalk 可以视为参数 $p = 1, q = 1$ $ p=1,q=1 $ 的 node2vec 模型的特例。
实验配置：
- 对于除了 node2vec-concat 以外的其它所有方法，node representation 维度设置为 $d = 100$ $ d=100 $ ；对于 node2vec-concat 方法，每个视图的representation 维度为 100，最终的维度为 $100 \times K$ $ 100\times K $ ， $K$ $ K $ 为视图的数量。
- 对于 LINE 和 MVE，负采样系数为 $N = 5$ $ N=5 $ ，初始学习率为 0.025 。
- 对于 node2vec ，窗口大小设为 10、随机游走序列长度为 40，超参数 $p, q$ $ p,q $ 根据标记数据来择优。
- 对于 MVE，每轮迭代中的“正边”数量 $T$ $ T $ 为 1000 万，参数 $η$ $ \eta $ 默认为 0.05 。
节点分类任务：我们将不同算法学到的node reprsentation 作为特征，并使用 Lib-Linear 软件包来训练 one-vs-rest 线性分类器。在分类器的训练过程中：
- 对于 DBLP 和 PPI 数据集，我们随机抽取 10% 的节点作为训练集，剩余 90% 作为测试集。
- 对于Flickr 数据集，我们随机选择 100 个节点作为训练集，以及 10000 个节点作为测试集。
为了学习视图权重，我们随机选择少量的标记样本来训练MVE 模型，这些标记样本不包含在测试集中，标记节点的数量参考数据集部分提供的图表。
我们给出在测试集上的分类 Micro-F1/Macro-F1 值，每种配置随机执行10 次并报告平均结果。由于 CMSC 无法扩展到非常大的网络，因此仅报告它在 PPI 网络上的结果。
结论：
- 基于单视图的方法（LINE 和 node2vec ）分类效果都比较一般。
- node2vec-merge 通过合并不同视图的边来利用多视图信息。但是，不同视图的邻近性是无法直接比较的，简单地将它们融合在一起会破坏每个视图的网络结构。在 Flickr 数据集上，node2vec-merge 方法的效果甚至还不如基于单视图的方法。
- node2vec-concat 通过将学到的多个视图的view-specific representatioin 进行拼接来利用多视图信息。但是，来自某些稀疏视图的representation 可能会有严重有偏 biased，这可能会破坏最终的 representation。因此，即使该方法使用了更高的维度，node2vec-concat 也不会显著优于其它的、基于单视图的方法。
- 多视图聚类CMSC 和多视图矩阵分解（MultiNMF 和 MultiSPPMI）的效果都较差，因为它们无法有效地实现不同视图的协同，也无法学习不同视图的权重。
- 我们提出的 MVE 在不使用标签信息来学习视图权重的情况下，MVE-NoAttn 超越了所有 baseline 方法。当使用注意力机制之后，MVE 可以进一步提升效果。
- 如果 MVE 去掉了不同视图的协同（即 MVE-NoCollab ），则会观察到较差的结果。这表明我们的协同框架确实可以通过促进视图的协同来提升性能。
链接预测任务：链接预测任务旨在预测网络中最有可能形成的链接。由于节点规模巨大，因此预测全网的所有可能的链接是不现实的。因此我们为每个数据集构造一个核心节点集合，并且仅预测核心节点集合中的节点链接。
- 对于 Youtube 数据集，核心节点集包含同时出现在所有四个视图中的所有节点，一共 7654 个节点。
- 对于 Twitter 数据集，由于节点数量太多，我们随机采样了出现在所有三个视图中的 5000 个节点。
对核心节点集中的每对节点，我们用它们robust representation 向量的余弦相似度来作为形成链接的概率。另外，为了获得 MVE 模型中视图的投票权重，我们从每个数据集中随机抽取 500 条边作为标记数据，这些标记数据不包含在评估数据集中。
我们通过核心数据集的AUC 来评估不同模型的链接预测能力。由于 CMSC/MultiNMF 无法扩展到非常大的网络，因此我们仅报告 Youtube 数据集上的结果。
结论：
- 基于单视图的方法（node2vec/LINE ）效果都比较一般。
- node2vec-merge 通过合并不同视图的边来利用多视图信息。由于这两个数据集的不同视图具有可比性和互补性，因此 node2vec-merge 的效果得到改善。
- node2vec-concat 通过将学到的多个视图的view-specific representatioin 进行拼接来利用多视图信息。但是某些稀疏的视图（如Twitter 数据集上的 reply 视图）可能会有严重的bias ，这可能会破坏最终的 representation。
- 多视图聚类CMSC 和多视图矩阵分解（MultiNMF 和 MultiSPPMI）的效果仍然都较差，因为它们无法有效地实现不同视图的协同，也无法学习不同视图的权重。
- 我们提出的 MVE 方法让然优于所有的 baseline 方法。如果移除视图协同（MVE-NoCollab ）或者移除注意力机制（MVE-NoAttn），则效果将下降。这表明我们协同框架的有效性和注意力机制的重要性。
数据稀疏性：这里我们检查 MVE 是否对稀疏数据也是鲁棒的。具体而言，我们研究MVE 在不同degree 节点上的性能，这对应于不同级别的数据稀疏性。每个节点的 degree 是所有视图的 degree 的总和。根据节点的 degree，我们将 DBLP 数据集的所有节点划分为 10 个不同的分组、将 Youtube 数据集中所有节点划分为 5 个不同的分组。
我们比较了 MVE, node2vec-merge 和 MVE-NoCollab 在不同分组上的性能，效果如下图所示。图中组id 越小则节点 degree 越大，组 id 越大则节点 degree 越小。因此越靠近右侧，数据越稀疏。
结论如下：
- 对于 BDLP 数据集，这三个模型在左侧的分组上效果均不理想。这是因为很多 degree 非常高的节点属于多个研究领域，因此难以正确分类。
  在右侧的分组中，node2vec-merge 和 MVE-NoCollab 的性能仍然很差，但是 MVE 明显优于它们。
- 对于 Youtube 数据集，也观察到类似的结果。这三个模型在左侧的分组上效果均不理想，但是在右侧的分组中 MVE 的效果优于 node2vec-merge 和 MVE-NoCollab 。
总之，MVE 在更稀疏的节点上取得了更好的效果，并且始终优于 MVE-NoCollab 和 node2vec-merge 。这表明我们的方法可以有效解决数据稀疏性问题，并帮助学到更鲁棒的node representation。
参数 $η$ $ \eta $ 的敏感性：在我们的协同框架中，参数 $η$ $ \eta $ 将控制正则项项的系数。该系数平衡了 view-specific representation 保留的邻近性与 view-specific representation 的一致性。我们在节点分类任务和链接预测任务上比较了 MVE 随着不同 $η$ $ \eta $ 上的性能。
结论：
- 当 $η = 0$ $ \eta = 0 $ 时，MVE 效果较差，因为不同视图无法通过正则化来彼此交流信息。
- 当 $η > 0$ $ \eta\gt0 $ 并逐渐提高时，MVE 效果持续改善。
- 当 $η \in (0.025, 0.1)$ $ \eta \in (0.025,0.1) $ 时，MVE 的效果比较稳定。
- 当 $η > 0.1$ $ \eta \gt 0.1 $ 并逐渐增加时，MVE 效果持续下降。这是因为更大的 $η$ $ \eta $ 倾向于使得不同的 view-specific representation 趋同，从而忽略了视图之间的差异。
标记数据规模的敏感性：为了学习不同节点的视图投票权重，我们的框架需要一些标记数据。这里我们考察不同规模的标记数据对于效果的影响。我们观察随着标记数据规模的变化， MVE 和 MVE-NoAttn 的性能。
结论：
- 通过利用标记数据来学习视图的投票权重，MVE 始终超越了其变体 MVE-NoAttn
- 在这两个数据集上，MVE 只需要很少的标记数据就可以使得预测性能收敛，这证明了我们基于注意力机制来学习投票权重的有效性。
效率：我们在 DBLP 和 Twitter 数据集上对比 MVE 和 node2vec/LINE/MVE-NoAttn 的训练时间。
结论：
- MVE 和 LINE/node2vec 的运行时间都很接近。
- 在拥有超过 30 万顶点、1 亿边的 Twitter 数据集上，MVE 训练过程不超过 15 分钟，非常高效。
- 对比 MVE 和 MVE-NoAttn 的训练时间，我们观察到 MVE 的权重学习过程在这两个数据集上花费的时间不到总训练时间的 15%。这证明了我们基于注意力的权重学习方法具有很高的效率。
注意力权重分析：我们考察MVE 学到的注意力，以及这些注意力为什么能够改善性能。
首先我们研究哪些视图会得到更高的注意力。我们以 DBLP 和 Youtube 数据集为例。对每个视图，我们报告单独使用view-specific representation 进行分类/链接预测的结果，以及每个视图所有节点的平均注意力得分。
结论：单个视图的性能和它们分配的平均注意力正相关。即：我们的方法使每个节点关注于效果最好的视图。
然后，我们比较不同label 中节点的注意力，从而在更细粒度进一步研究学到的注意力。我们以 DBLP 数据集为例，并研究四种label 中的节点，包括 hardware (HW), programming language (PL), data mining (DM) and machine learning (ML) 。对每种 label，我们计算属于该label 的节点各视图平均分配的权重，并报告与其它label 的节点各视图平均分配的权重的比值，以便了解哪些视图对于各label 而言效果最好。
结论：
- 对 HW/PL 领域的节点而言，它们对 citation 视图的关注相对更多。
- 对 DM/ML 邻域的节点而言，它们对 co-author 视图的关注相对更多。
这是因为我们的节点分类任务旨在预测不同作者的研究领域。为了提高预测的准确性，我们的注意力机制需要让节点关注于最能够与其它领域作者区分开的视图。
- 对于 HW 和 PL 领域作者而言，与其它领域节点（每个节点就是一位作者）相比，这两个领域的作者可能会引用非常不同的论文，因此论文引用视图对它们的区分度最大。因此，HW/PL 领域的节点对 citation 视图的注意力更大。
- 对于 DM/ML 领域作者而言，他们更可能使用相似的术语并引用相似的论文，因此文本相似度视图、引文视图都无法将这些领域区分开来。因此，这些领域的节点很少关注文本相似性视图和引文视图，而更多地关注 co-author 视图。
总之，通过注意力机制学到的视图权重非常直观：迫使每个节点专注于信息量最高的视图。
case 研究：最后我们提供一些case 来展示 view-specific representation 和 robust representation 之间的差异。我们以 DBLP 数据集为例。给定一个作者作为 query，我们根据不同的 embedding 找出最相似的作者，相似度通过embedding 向量的余弦相似度来衡量。
结论：view-specific representation 可以很好地保留各个视图的结构邻近性，而 robust representation 则利用了来自所有不同视图的信息。