返回介绍

数学基础

统计学习

深度学习

工具

Scala

二十八、MVN2VEC [2018]

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

  1. 在实际 application 中,对象可以通过不同类型的关系来连接。这些对象及其关系可以自然地由多视图网络 multi-view network 来表达,即多重网络multiplex networkmulti-view graph。下图给出了一个示例性的多视图网络,其中每个视图对应于一种类型的边,并且所有视图共享同一组节点。作为一个更具体的例子,关于用户节点的四视图网络可用于描述社交网络服务,其中包括好友friendship、关注 following、互发信息message exchange、帖子查看 post viewing 等关系。随着多视图网络的广泛应用,挖掘多视图网络是有意义的。

    与此同时,network embedding 已成为一种用于网络数据的、可扩展的representation learning 方法。具体而言,network embedding 将网络的节点投影到 embedding 空间中。通过编码每个节点的语义信息,学到的 embedding 可以直接作为各种下游应用的特征。受到 network embedding 在同质网络中的成功的激励,论文 《MVN2VEC: Preservation and Collaboration in Multi-View Network Embedding》 认为更好地理解多视图网络embedding 很重要。

    要设计多视图网络的 embedding 方法,主要挑战在于如何使用来自不同视图的边的类型信息。因此,我们的兴趣集中在以下两个问题:

    • 当有多种类型的边可用时,对于多视图网络 embedding 而言,特定specific 的、重要important 的目标是什么?

      即,多视图网络 embedding 要优化的是什么目标?

    • 我们可以通过联合建模这些目标来实现更好的 embedding 质量吗?

    为了回答第一个问题,我们从嵌入真实世界多视图网络的实践中确定了两个这样的目标:保持preservation 和协同 collaboration

    • collaboration:在某些数据集中,由于共享的潜在原因,可能观察到同一对节点pair 对之间在不同视图中都存在边。例如,在社交网络中,如果我们在 message exchangepost viewing 视图中观察到用户 pair 对之间存在边,那么这两个用户很可能乐意彼此成为好友。在这种情况下,这些视图可能会互补,并且联合嵌入它们可能会比单独嵌入它们产生更好的结果。在联合嵌入多视图过程中,我们将这种协同效应synergetic effect 称作 collaborationcollaboration 也是大多数现有多视图网络算法背后的主要直觉。

    • preservation:另一方面,不同的网络视图可能具有不同的语义。也可能一部分节点在不同视图中具有完全不一致的边,因为不同视图中的边是由不相关的潜在原因unrelated latent reason 而形成的。

      例如,职场关系professional relationship 可能并不总是与好友关系 friendship 保持一致。如果我们将图 (b) 中的职场关系视图和友谊关系视图嵌入到同一个 embedding 空间中,那么 Garyembedding 将靠近 TildeElton 。因此,由于传递性,Tildeembedding 也不会离 Elton 太远。然而,这并不是一个理想的结果,因为根据原始的多视图网络,TildeElton 在职场关系或好友关系方面都没有密切关联。换句话讲,以这种方式的 embedding 无法保持不同网络视图所携带的、独有 unique 的信息。我们将保持不同视图所携带的 unique 信息的这种需求need 称作保持 preservation 。在论文中,我们将详细讨论 preservationcollaboration 的有效性和重要性。

    此外,preservationcollaboration 的需求可能在同一个多视图网络中共存。有两种场景会导致这种情况:

    • 一对视图是由非常相似的潜在原因产生的,而另一对视图是由完全不同的潜在原因产生的。。
    • 在同一对视图中,一部分节点在不同视图中具有一致的边,而另一部分节点在不同视图中具有完全不一致的边。例如,在某些国家,职场关系和好友关系并不一致;而在另一些国家,同事之间经常成为好友。

    因此,我们也有兴趣通过同时建模 preservationcollaboration 来探索实现更好 embedding 质量的可行性。我们将在论文中详细介绍这一点。

    我们注意到,与其提出一个超越很多 baseline 方法的、复杂的模型,不如将重点放在多视图网络 embeddingcollaborationpreservation 目标上。在实验中,我们在不同场景中比较了侧重于不同目标的方法。出于同样的原因,本文排除了可以使用监督信息的场景,而从无监督场景学到的经验教训也可以应用于有监督的多视图网络 embedding 算法。此外,通过无监督方法学到的 node embedding 可以直接应用于不同的下游任务,而监督算法产生的 embedding 专有地适合监督信息所在的任务。

    总而言之,我们的贡献如下:

    • 我们研究了对多视图网络 embedding 而言特定 specific 的、重要 important 的目标,并且从嵌入现实世界的多视图网络的实践中,确定了 preservationcollaboration 这两个目标。
    • 我们探索通过同时建模 preservationcollaboration 来获得更好 embedding 的可行性,并提出了两种多视图网络 embedding 方法:MVN2VEC-CONMVN2VEC-REG
    • 我们在四个数据集上对各种下游 application 进行了实验。这些实验证实了 preservationcollaboration 的有效性和重要性,并证明了所提出方法的有效性。
  2. 相关工作:

    • network embeddingnetwork embedding 已成为学习分布式 node representation 的一种高效的、有效的方法。传统的无监督 feature learning 方法利用了常见的、网络的谱属性 spectral property。与传统方法相反,大多数 network embedding 方法都是根据网络的局部属性local property 来设计的,这些局部属性涉及节点之间的链接和邻近性。这种聚焦于局部属性的方法已被证明更具有可扩展性。

      许多最近的 network embedding 算法的设计都是基于网络的局部属性,并且可以追溯到 SkipGram 模型,其中 SkipGram 模型被证明具有可扩展性和广泛的适用性。为了利用 SkipGram 模型,人们已经提出了各种策略来定义网络场景中的节点上下文。除了 SkipGram 模型之外,在文献中还可以找到保持某些其它网络属性的 embedding 方法。

    • 多视图网络:大多数现有的多视图网络方法旨在提高传统任务的性能,如聚类clustering 、分类classification 、稠密子图挖掘dense subgraph mining 等任务。

      另一个研究方向侧重于衡量和分析多视图网络中的交叉视图交互关系 cross-view interrelation 。但是他们没有讨论嵌入多视图网络的目标,也没有研究他们所提出的度量和分析如何与多视图网络的 embedding learning 相关联。

    • 多视图网络 embedding:最近,《An attention-based collaboration framework for multi-view network representation learning》 提出了一种基于注意力的协同框架,从而用于多视图网络 embedding。这项工作的 setting 与我们不同,因为该工作需要监督信号从而用于注意力机制。此外,该方法并不直接建模 preservation(该方法重点关注协同),而我们认为 preservation 是对多视图网络 embedding 很重要的目标之一。在该框架中, final embedding 通过线性组合得到,因此是所有视图的 representation 之间的权衡 trade-off

      《Co-regularized deep multi-network embedding》 还提出了一种用于嵌入multi-network 的深度学习架构,其中 multi-network 是比多视图网络更通用的概念,并且允许跨网络进行多对多的对应 correspondence 。虽然所提出的模型可以应用于更具体的多视图网络,但是它并不聚焦于多视图网络 embedding 目标的研究。

      另一组相关工作研究了使用潜在空间模型联合建模多个网络视图的问题。这些工作再次没有建模 preservation。还有一些研究涉及多视图网络 embedding ,但是它们即不建模 preservationcollaboration,也不旨在提供对这些目标的深入研究。

      此外,多视图矩阵分解问题也与多视图网络 embedding 有关。《Multi-view clustering via joint nonnegative matrix factorization》 提出了一种多视图非负矩阵分解模型,旨在最小化每个视图的邻接矩阵与共识矩阵 consensus matrix 之间的距离。虽然这些方法可以为每个节点生成一个向量,但是这些向量被建模以适应某些具体任务(如矩阵补全或聚类任务),而不是可用于不同下游 application 的、节点的分布式 representation

    • 其它类型网络的 embedding 技术:在更大的范围内,人们最近在嵌入更通用的网络方面进行了一些研究,如异质信息网络 heterogeneous information network: HIN 。有些工作在 metapath 之上构建算法,但是相比于多视图网络, metapath 对于具有多种类型节点的 HIN 而言更有意义。另一些工作是为具有额外辅助信息或特定结构的网络而设计的,这些网络不适用于多视图网络。最重要的是,这些方法是为它们想要嵌入的网络而设计的,因此并不专注于研究多视图网络 embedding 的特定需求和目标。

    • 多关系multi-relational 网络 embedding (或知识图谱 embedding):多关系网络 embedding 体现了与多视图网络 embedding 相关的另一个研究方向。这个方向的研究重点与多视图网络 embedding 有所不同,并不直接适用于我们的场景,因为这些网络中涉及的关系通常是有向的。此类方法中的一族流行方法是基于翻译的,其中有向边的 head entityh$ \mathbf{\vec h} $ 、有向边的 tail entityt$ \mathbf{\vec t} $ 、有向边上的关系r$ \mathbf{\vec r} $ ,这三个 embedding 满足:(t+r)$ (\mathbf{\vec t} + \mathbf{\vec r}) $ 和h$ \mathbf{\vec h} $ 相似。 这种假设对于具有无向子网络视图的多视图网络而言是无效的。

28.1 模型

28.1.1 基本概念

  1. 多视图网络定义:多视图网络G=(V,E)$ \mathcal G=(\mathcal V, \mathcal E) $ ,其中V={v1,v2,,vn}$ \mathcal V=\{v_1,v_2,\cdots,v_n\} $ 。假设网络有M$ M $ 个不同的视图,对应的边集合为E1,E2,,EM$ \mathcal E_1,\mathcal E_2,\cdots,\mathcal E_M $ ,其中EmE,m=1MEm=E$ \mathcal E_m\sub \mathcal E,\quad \bigcup_{m=1}^M \mathcal E_m = \mathcal E $ 。定义类型为m$ m $ 的子网为Gm(V,Em)$ \mathcal G_m(\mathcal V,\mathcal E_m) $ 。
  2. 多视图网络embedding 的目标是为每个节点viV$ v_i\in \mathcal V $ 学到一个 center embedding 向量viRd$ \mathbf{\vec v}_i\in \mathbb R^d $ 从而保持多视图网络的原始结构信息,其中dn$ d\ll n $ 。除了 center embedding 向量之外,一系列流行的算法还为每个节点viV$ v_i\in \mathcal V $ 学到一个 context embeddingciRd$ \mathbf{\vec c}_i\in\mathbb R^d $ 。此外,当需要把学到的 embedding 用作下游任务的特征向量时,我们遵从常见的做法,将 center embedding 作为特征。

28.1.2 朴素方法

  1. 可以通过把简单网络 embedding 方法推广到多视图,从而得到多视图网络 embedding 的两种简单直接的方法:独立模型independent model 、单空间模型 one-space model

    定义节点vi$ v_i $ 在视图m$ m $ 上的 embeddingvi(m)Rdm$ \mathbf{\vec v}_i^{(m)}\in \mathbb R^{d_m} $ ,其中dm$ d_m $ 为视图Gm$ \mathcal G_m $ 的 embedding 维度。

    • 独立模型分别独立嵌入每个视图,然后将所有视图的 embedding 拼接从而得到 final embedding

      vi=mMvi(m)Rd

      其中d=mdm$ d = \sum_m d_m $ ,$ \bigoplus $ 表示向量拼接。

      这种方法得到的 node embedding 保持了每个视图的信息,但是无法跨不同视图进行协同collaboration

    • 单空间模型:单空间模型假设每个视图共享相同的参数,final embedding 为:

      vi=vi(m)Rd

      其中d=dm$ d= d_m $ 。

      在单空间模型中所有视图的 embedding 都相同,它们就是final embedding。因此final embedding和所有视图有关。

      这种方法得到的 node embedding 鼓励不同视图进行协同,但是没有保持每个视图独有的信息。

  2. 我们通过 YouTube, Twitter 这两个多视图网络来评估独立模型、单空间模型的效果。

    在这两个网络中,每个节点代表一个用户。YouTube 网络有三个视图,分别代表共同观看视频 cmn-vid、共同订阅者 cmnsub、共同好友 cmn-fndTwitter 有两个视图,分别表示回复 reply、提及 mention 。下游任务是评估两个用户是否好友关系。

    评估结果如下表所示。可以看到并没有哪个模型的效果始终比另外一个更好。

    • YouTube 数据集上,独立模型的效果优于单空间模型。
    • Twitter 数据集上,单空间模型的效果优于独立模型。

  3. 我们认为:不同网络的network embedding 对建模 preservation 和建模collaboration 的需求不同,这使得采用独立模型、单空间模型的效果不同。具体而言:独立模型仅捕获 perservation,单空间模型仅捕获 collaboration。因此:

    • 如果某个数据集更需要建模 preservation,那么独立模型的效果将优于单空间模型。
    • 如果某个数据集更需要建模 collaboration,那么单空间模型的效果将优于独立模型。

    为证明我们的观点,我们检查了数据集中不同网络视图之间信息的一致性。给定两个集合,我们通过 Jaccard 系数来衡量两个集合之间的相似性:

    J(S1,S2)=|S1S2||S1S2|[0,1]

    给定多视图网络中的一对视图Gm1,Gm2$ \mathcal G_{m_1},\mathcal G_{m_2} $ ,节点vi$ v_i $ 可以在这两个视图中分别连接到不同的邻居节点。假设在Gm1$ \mathcal G_{m_1} $ 中节点vi$ v_i $ 的邻居节点集合为Nvi(m1)$ \mathcal N_{v_i}^{(m_1)} $ ,在Gm2$ \mathcal G_{m_2} $ 中节点vi$ v_i $ 的邻居节点集合为Nvi(m2)$ \mathcal N_{v_i}^{(m_2)} $ ,则节点vi$ v_i $ 在这对视图中的一致性为:

    Jvi(m1,m2)=J(Nvi(m1),Nvi(m2))

    对于每对视图,我们检查所有节点在它们之间的一致性,并给出一致性大于 0.5 的节点占所有节点的比例。该比例定义为视图之间信息的一致性,即:

    rate(Gm1,Gm2)=viVI(Jvi(m1,m2)>0.5)|V|

    其中I()$ \mathbb I(\cdot) $ 为示性函数。

    YouTube, Twitter 数据集上不同视图的信息一致性结果如下图所示:

    • YouTube 数据集中每对视图之间几乎没有一致性。因此,该数据集最需要的是建模 perservation,而不是collaboration 。因此在该数据集上独立模型优于单空间模型。
    • Twitter 数据集中每对视图之间一致性较高,因此对该数据集建模 collaboration 可以带来效果的提升。因此该数据集上单空间模型优于独立模型。

28.1.3 MVN2VEC 模型

  1. 我们将 preservationcollaboration 定义为多视图网络 embedding 中的重要目标。

    • 一种极端情况是,每个视图都具有独特的语义。此时仅需要建模 preservation,因此独立模型就可以产生比较好的结果。
    • 另一种极端情况是,每个视图都具有相同的语义。此时仅需要建模 collaboration,因此单空间模型就能得到令人满意的结果。

    但是,通常多视图网络介于两者之间,因此需要同时建模 preservationcollaboration。为此,我们提出两种方法 MVN2VEC-CONMVN2VEC-REG,它们都可以同时捕获这两个目标。其中 MVN2VEC 表示 multi-view network to vectorCON 表示constrainedREG 表示 regularized

  2. 根据之前的定义,节点vi$ v_i $ 在视图m$ m $ 上的 embeddingvi(m)Rdm$ \mathbf{\vec v}_i^{(m)}\in \mathbb R^{d_m} $ 。定义节点vi$ v_i $ 在视图m$ m $ 中作为上下文时的 context embeddingci(m)Rdm$ \mathbf{\vec c}_i^{(m)}\in \mathbb R^{d_m} $ 。为方便模型设计,我们选择dm=d/M$ d_m = d/M $ 。

    给定视图Gm$ \mathcal G_m $ ,我们定义视图内损失函数 intra-view loss 来衡量当前 embedding 来表达视图Gm$ \mathcal G_m $ 的效果:

    l({vi(m),ci(m)}Gm)

    我们这里先不给出损失函数l()$ l(\cdot) $ 的具体定义,其定义在后续给出。

  3. MVN2VEC-CONMVN2VEC-CON 方法同时建模 collaborationpreservation

    首先,该方法不对vi(m)$ \mathbf{\vec v}_i^{(m)} $ 进行进一步处理,从而希望保持每个视图的语义,即建模 preservation。然后,该方法对 context embedding 施加约束:要求不同视图中的 context embedding 共享。具体做法为:

    ci(m)=(1θ)×gi(m)+θ×1Mm=1Mgi(m)

    其中giRdm$ \mathbf{\vec g}_i\in \mathbb R^{d_m} $ 。θ[0,1]$ \theta\in [0,1] $ 是控制参数parameter 共享比例的超参数,取值越大则参数共享比例越高,从而更多地建模 collaboration

    θ$ \theta $ 也可以利用模型从数据中自动学习。

    最终,MVN2VEC-CON 模型需要求解以下最优化问题:

    min{vi(m),gi(m)}l({vi(m),gi(m)}Gm;θ)

    当模型完成训练之后,每个节点vi$ v_i $ 的 final embedding 为:

    vi=mMvi(m)Rd

    其中$ \bigoplus $ 表示向量拼接。注意:当θ=0$ \theta=0 $ 时,MVN2VEC-CON 模型退化为独立模型。

    注意,这里用向量拼接而没有用均值聚合或 sum 聚合。拼接操作能够保持每个视图的语义,即 preservation

    进一步地,为区分不同视图我们将θ$ \theta $ 替换为 view-specific 参数θm$ \theta_m $ ,即每个视图都有一个共享比例超参数,我们将该研究作为未来工作。

  4. MVN2VEC-REGMVN2VEC-REG 方法也同时建模 collaborationpreservation 。该方法并未要求不同视图之间的参数共享,而是对不同视图的 embedding 施加正则化。

    MVN2VEC-REG 的目标函数为:

    min{vi(m),ci(m)}l({vi(m),ci(m)}Gm)+γ×(Ri(m)+R~i(m))

    其中γ$ \gamma $ 为超参数,表示正则化系数。Ri(m)$ \mathcal R_i^{(m)} $ 和R~i(m)$ \tilde{\mathcal R}_i^{(m)} $ 为正则化项:

    Ri(m)=vi(m)1Mmvi(m)2R~i(m)=ci(m)1Mmci(m)2

    ||||2$ ||\cdot||_2 $ 表示l2$ l_2 $ 正则化。

    • 一方面,MVN2VEC-REG 通过让{vi(m)}$ \left\{\mathbf{\vec v}_i^{(m)}\right\} $ 和{ci(m)}$ \left\{\mathbf{\vec c}_i^{(m)}\right\} $ 位于view-specificembedding 子空间中,从而建模 preservation
    • 另一方面,MVN2VEC-REG 通过跨视图的正则化来建模 collaboration

    类似于 MVN2VEC-CON 模型,在 MVN2VEC-REG 模型中超参数γ$ \gamma $ 越大,则模型越倾向于建模 collaboration 。当γ=0$ \gamma= 0 $ 时MVN2VEC-REG 模型退化为独立模型。

    进一步地,为区分不同视图我们将Ri(m)$ \mathcal R_i^{(m)} $ 和R~i(m)$ \tilde {\mathcal R}_i^{(m)} $ 替换为:

    Ri(m)=vi(m)mλm×vi(m)mλm2R~i(m)=ci(m)mλm×ci(m)mλm2

    其中超参数λm$ \lambda_m $ 刻画了视图Gm$ \mathcal G_m $ 的的重要性。我们将该研究作为未来工作。

  5. 视图内损失函数 intra-view loss:视图内损失函数l()$ l(\cdot) $ 有多种形式,这里我们采用基于随机游走的 SkipGram 模型。具体而言,对于每个视图Gm$ \mathcal G_m $ ,我们首先通过随机游走来采样节点序列。对于每个节点vi$ v_i $ ,我们选择所有序列中该节点位于窗口大小为B$ B $ 的上下文节点集合Cvi(m)$ \mathcal C^{(m)}_{v_i} $ 。则视图内损失函数定义为:

    l({vi(m),ci(m)}Gm)=viVcjCvi(m)logp(m)(cjvi)

    其中:

    p(m)(cjvi)=exp(vi(m)cj(m))jexp(vi(m)cj(m))

    这个损失函数旨在保持视图内的一阶邻近性。

  6. 模型推断:为了优化 MVN2VEC-CONMVN2VEC-REG 的目标函数,我们选择异步随机梯度下降 asynchronous stochastic gradient descent: ASGD 。此外,我们也采用负采样技术来近似p(m)(cjvi)$ p^{(m)}(c_j\mid v_i) $ ,即:

    p(m)(cjvi)logσ(vi(m)cj(m))+k=1KEjP(m)logσ(vi(m)cj(m))

    其中:σ()$ \sigma(\cdot) $ 为 sigmoid 函数,K$ K $ 为负采样比例,P(m)(v)(dv(m))3/4$ P^{(m)}(v)\propto \left(d_v^{(m)}\right)^{3/4} $ 为噪音分布。dv(m)$ d_v^{(m)} $ 为节点v$ v $ 在视图Gm$ G_m $ 中的度 degree ,或者也可以选择dv(m)$ d_v^{(m)} $ 为节点v$ v $ 在Gm$ G_m $ 的所有随机游走序列中出现的次数。

    当使用负采样之后:

    • MVN2VEC-CON 的目标函数为:

      ci(m)=(1θ)×gi(m)+θ×1Mm=1Mgi(m)LCON=viVcjCvi(m)[logσ(vi(m)cj(m))+k=1KEjP(m)logσ(vi(m)cj(m))]
    • MVN2VEC-REG 的目标函数为:

      Ri(m)=vi(m)1Mmvi(m)2,R~i(m)=ci(m)1Mmci(m)2LREG=viVcjCvi(m)[logσ(vi(m)cj(m))+γ×(Ri(m)+R~j(m))+k=1KEjP(m)[logσ(vi(m)cj(m))+γ×(Ri(m)+R~j(m))]]

    .

  7. 随机游走 pair 生成:在缺乏额外监督信息的情况下,我们假设不同网络视图的重要性相同,并从每个视图中采样相同数量的N$ N $ 个随机游走序列。定义视图Gm$ \mathcal G_m $ 中非孤立节点的数量为n(m)$ n^{(m)} $ ,定义nmax=maxmn(m)$ n_{\max} = \max_{m} n^{(m)} $ 。假设每个节点开始的随机游走序列数量为S$ S $ (S$ S $ 为超参数),则我们选择N=S×nmax$ N=S \times n_\max $ 。

    给定网络视图Gm$ \mathcal G_m $ ,我们根据现有研究来生成随机游走 pair 对,其中节点的转移概率与所有 outgoing edge 的权重成正比。

  8. 复杂度分析:对于每个网络视图,随机游走都是根据现有方法独立生成的。《node2vec: Scalable feature learning for networks》 的分析表明,整体复杂度为O(MLB(LB))$ O(\frac{ML}{B(L-B)}) $ ,其中L$ L $ 为每条随机游走序列的长度(L$ L $ 为超参数),B$ B $ 为上下文窗口大小,M$ M $ 为视图个数。因此随机游走的计算复杂度是M$ M $ 的一次关系。

    对于模型推断,ASGD 的迭代步数和 (node, context) pair 对的数量成线性关系,而这个数量正比于L$ L $ 、B$ B $ 、S$ S $ 、M$ M $ 。此外, ASGD 每步迭代的梯度计算正比于M$ M $ 。因此 ASGD 的计算复杂度是M$ M $ 的二次关系。

  9. MVN2VEC 训练算法:

    • 输入:

      • 多视图网络G=(V,E)$ \mathcal G=(\mathcal V,\mathcal E) $ ,其中每个视图Gm=(V,Em)$ \mathcal G_m = (\mathcal V,\mathcal E_m) $ ,EmE$ \mathcal E_m\sub \mathcal E $
      • 每个节点开始的随机游走序列数量S$ S $
      • 随机游走序列长度L$ L $
      • 上下文窗口大小B$ B $
      • 负采样比例K$ K $
      • 超参数θ$ \theta $ 或者γ$ \gamma $
    • 输出:每个节点的 embedding{vi}$ \{\mathbf{\vec v}_i\} $

    • 算法步骤:

      • 从每个视图Gm$ \mathcal G_m $ 中均采样N=S×nmax$ N=S \times n_\max $ 条长度为L$ L $ 的随机游走序列。

      • 对每个节点vi$ v_i $ ,生成视图Gm$ \mathcal G_m $ 中的、窗口大小为B$ B $ 的上下文Cvi(m)$ \mathcal C^{(m)}_{v_i} $ 。

      • 对每个节点vi$ v_i $ ,混洗所有视图的上下文,得到总的上下文Cvi$ \mathcal C_{v_i} $ 。

      • 迭代(下面的迭代步骤可以并行进行):

        • for(viV,cjCvi):$ \text{for }(v_i \in \mathcal V,c_j\in \mathcal C_{v_i}): $ 基于梯度更新参数。
      • 对于每个节点viV$ v_i\in \mathcal V $ ,返回vi=mvim$ \mathbf{\vec v}_i = \bigoplus_m \mathbf{\vec v}_i^m $ 。

28.2 实验

28.2.1 人工合成数据集

  1. 为直接研究不同模型在具有不同程度的 preservationcollaboration 网络上的性能,我们设计了一组人工合成网络,并执行多类分类任务。这些人工合成网络记作G(p)$ \mathcal G(p) $ ,其中p[0,0.5]$ p\in [0,0.5] $ 表示冲突概率intrusion probability 。我们首先描述如何生成G(0)$ G(0) $ :

    • 在带有标签 AB 的所有节点上生成一个随机网络,并在带有标签 CD 的所有节点上生成另一个随机网络。将这两个随机网络的所有边放入视图G1$ \mathcal G_1 $ 。
  • 在带有标签 AC 的所有节点上生成一个随机网络,并在带有标签 BD 的所有节点上生成另一个随机网络。将这两个随机网络的所有边放入视图G2$ \mathcal G_2 $ 。

    为了生成上述四个随机网络,我们采用广泛被使用的优先连接过程preferential attachment process,该过程用一条边将新节点连接到现有节点,并且是广泛使用的、可以生成幂律分布网络的方法 。通过这种方式,在视图G1$ \mathcal G_1 $ 中,标签为 AB 的节点应该和标签为 CD 的节点有区分性;在视图G2$ \mathcal G_2 $ 中,标签为 AC 的节点应该和标签为 BD 的节点有区分性。

    更一般地,G(p)$ \mathcal G(p) $ 是通过对G(0)$ \mathcal G(0) $ 的调整来生成的:当一条边放入其中一个视图时,以概率1p$ 1-p $ 放入当前视图,而以概率p$ p $ 放入另一个视图。因此较大的p$ p $ 会导致网络更多的 collaboration,较小的p$ p $ 会导致网络更多的 preservation 。在p=0.5$ p=0.5 $ 的极端情况下,network embedding 过程只需要 collaboration,因为每条边都有相同的概率落入G1$ \mathcal G_1 $ 或G2$ \mathcal G_2 $ 。

    我们人工合成网络G(p)$ \mathcal G(p) $ 最终包含 4000 个节点、2 个视图。每个节点关联一个 labellabel 的取值集合为 {A,B,C,D} ,并且每种类型的 label1000 个节点。

  1. 对于每个G(p)$ \mathcal G(p) $ ,我们分别应用independent, one-space, MVN2VEC-CON, MVN2VEC-REG 等方法学习 node embedding,然后使用逻辑回归来执行分类任务来评估生成的 embedding 质量。

    我们从 4000 个样本中采样得到验证集,通过验证集来调优超参数。同时我们随机抽取一部分节点作为测试集,并给出不同方法生成的 embedding 在测试集上的分类准确性和交叉熵。

    结论:

    • p$ p $ 很小时,independent 模型优于 one-space 模型,此时 preservation 占据统治地位。
    • p$ p $ 很大时,one space 模型优于 independent 模型,此时 collaboration 占据统治地位,
    • 大多数情况下(除了p$ p $ 接近 0.5 之外),我们提出的 MVN2VEC 性能优于 independent/one-space 模型。这意味着 MVN2VEC 有可能通过同时建模 preservationcollaboration 来实现更好的性能。
    • p$ p $ 接近 0.5 时,one-space 效果更好。这是可以预期的,因为在G(0.5)$ \mathcal G(0.5) $ 中不需要 preservation。并且,任何针对 preservatinon 的额外建模都不会提高性能。

28.2.2 真实数据集

  1. 数据集:

    • Youtube 数据集:一个视频分享网站。我们使用该数据集构建了一个三视图网络,其中核心用户core user 为节点,三个视图分别为:共同好友关系、共同订阅者关系、共同爱好关系(都喜欢某个视频)。注意, core user 为数据集作者通过爬虫爬取到的那些用户,而他们的好友可能不属于 core user

      由于没有类别标签,因此我们在该数据集上执行链接预测任务,目标是预测两个 core user 之间是否是好友关系。由于原始数据集只有正样本(好友关系),因此对于每个 core user 的好友关系,我们随机选择 5 个非好友的 core user 来构造负样本。我们将数据集拆分为训练集、验证集、测试集。

    • Twitter 数据集:在线新闻和社交网站。我们使用该数据集构建了一个两视图网络,其中用户为节点,两个视图分别为:reply 关系、mention 关系。

      同样地,我们也在该数据集上执行链接预测任务,预测两个用户是否是好友。我们也采用相同的方式构造负样本。训练集、验证集、测试集的拆分方法与 Youtube 数据集中的拆分方法相同。

    • Snapchat 数据集:一个多媒体社交网络。我们使用该数据集构建一个三视图网络,其中用户为节点,三个视图分别为:好友关系、聊天关系、故事阅读关系。我们收集了 2017 年春季连续两周的数据作为构建网络的数据,下游评估任务的数据是接下来一周(第三周)收集的数据。

      我们在Snapchat 数据集上采用不同模型学到 node embedding,然后将 node embedding 作为输入从而执行下游的标签分类任务、链接预测任务。

      • 在分类任务中,我们根据第三周用户观看的历史记录,对用户是否观看了 10 个最热门的发现频道 discover channel 进行分类。对于每个频道,观看过该频道的用户都被标记为正样本。我们随机选择未观看该频道的 5 倍用户(正样本的5倍)作为负样本。这是一个多标签分类问题,旨在推断用户对不同发现频道的偏好,从而指导内容服务中的产品设计。

        然后,我们将这些用户随机拆分为训练集、验证集、测试集,拆分比例为 80%:10%:10%

      • 在连接预测任务中,我们预测两个用户是否会在第三周阅读彼此发布的 story。 正样本是一对好友,他们阅读了对方发布的 story;负样本是一对好友,他们未阅读对方发布的 story 。注意:这种方式产生的正样本比负样本更多,这也是在实验中观察到较高 PRC-AUC 的原因。

        数据被随机分为训练集、验证集、测试集,约束条件是用户最多只能在三个子集中的一个子集中显示为阅读者 viewer 。该任务旨在估计朋友之间阅读故事的可能性,以便 application 可以相应地对故事就那些排名。

      我们提供了 Snapchat 视图的一致性结果,可以看到在 Snapchat 网络中,视图一致性介于 YouTubeTwitter 之间。

  2. 数据处理:

    • 如果节点在多视图中至少一个视图中是孤立节点(在该视图中不与其它任何节点相连),则该节点将从评估中排除。这种处理方式可以确保仅嵌入单个视图时,每个节点都具有有效的embedding
    • 对于所有三个网络上的每个任务,训练集、验证集、测试集的拆分比例为 80%:10%:10% 。我们重复 20 次随机拆分数据集并执行评估,最终报告每个评估指标的均值和标准差。
  3. baseline 方法:

    • independent 模型:等价于θ=0$ \theta = 0 $ 的 MVN2VEC-CON ,以及γ=0$ \gamma=0 $ 的 MVN2VEC-REG 方法。它保留了每个视图独有的信息,但是不允许嵌入过程中跨视图的协同。

    • one-space 模型:它使得不同的视图可以协同学习统一的 embedding,但不会保留每个视图特有的信息。

    • view-merging 模型:它首先将所有视图合并为一个统一的视图,然后学习该统一视图的 embedding 。为满足所有视图重要性都相同的假设,我们将统一视图中边的权重调整为所有视图中该边的权重之和。

      这种方法是one-space 的一个替代方法,而且区别在于:随机游走是否能够穿越不同的视图。就像 one-space 一样,view-merging 方法也不会建模 perservation

    • single-view 模型:它仅从某一个视图中学习 embedding ,目的是为了验证引入更多的视图是否能够带来效果的提升。它等价于使用 DeepWalk 来嵌入多视图网络中的某一个视图。

    我们还尝试了两个用于多视图网络 embedding 的其它方法,包括:

    • MVE:一种基于注意力机制的多视图网络 embedding 的半监督方法。为了公平地比较,在我们的无监督链接预测实验中,我们将相同的 dummy class label 分配给 1% 随机选择的节点。我们观察到,随机选择节点的比例并不会显著影实验中的评估结果。
    • DMNE:一种基于深度学习体系结构的多视图网络embedding 方法。

    由于可扩展性的原因,我们在较小的 YouTubeTwitter 数据集上比较了这两个 baseline

  4. 评估方式:为公平起见,我们使用相同的、带有L2$ L_2 $ 正则化的逻辑回归模型来进行节点分类和链接预测任务,其中L2$ L_2 $ 正则化系数始终通过验证集来选择最优的。

    根据 《Line:L arge-scale information network embedding》,每个 embedding 向量通过投影到单位球上从而进行后处理。

    在多标签分类任务中,节点特征仅仅是节点的 embedding,并且为每个 label 训练一个独立的逻辑回归模型。在链接预测任务中,节点 pair 对的特征是两个节点 embedding 向量的 Hadamard product,正如 《node2vec: Scalable feature learning for networks》 所建议的。

  5. 超参数配置:

    • 对于 independent, MVN2VEC-CON, MVN2VEC-REG,我们设置 embedding 维度为d=128×M$ d= 128\times M $ 。即每个子视图的embedding 维度dm=128$ d_m = 128 $ 。

      对于 single-view,我们设置d=128$ d = 128 $ ;对于所有其它方法,我们同时评估了d=128$ d=128 $ 和d=128×M$ d=128\times M $ 。

    • 对于随机游走序列,我们设置每个序列长度为L=20$ L=20 $ ,窗口大小B=3$ B=3 $ 。对于 Snapchat 数据集,每个节点开始的随机游走序列数量S=10$ S=10 $ (因为数据集太大),其它数据集的S=50$ S=50 $ 。

    • 我们SkipGram 负采样比例为K=5$ K=5 $ 。

    • 每个模型仅训练一个 epoch

    • MVN2VEC 模型的θ,γ$ \theta,\gamma $ 经过验证集调优。

  6. 评估指标:

    • 对于链接预测任务,我们使用 ROC-AUCPRC-AUC 这两个指标。
    • 对于多标签分类任务,我们先计算每种标签的 ROC-AUC 以及 PRC-AUC,然后报告所有标签在这些指标上的均值。
  7. 实验结果:

    • 所有利用多视图的模型都优于仅使用单视图的模型,这证明了利用多视图的必要性。

    • one-space 方法和 view-merging 方法在所有数据集上的性能都差不多。这是可以预期的,因为它们都仅对 collaboration 进行建模,并且彼此之间的区别仅在于随机游走是否跨网络视图。

    • YouTube 上,我们提出的 MVN2VEC 模型表现不错,但是没有明显的超越 independent 模型。这是由于 YouTube 网络中,对 preservation 建模的需求占主导地位。在这种极端情况下,对collaboration 额外的建模并不会带来显著的效果提升。

    • Twitter 上,collaborationpreservation 更为重要,因此 one-space 方法要比 independent 方法更好。

      此外,MVN2VEC-REG 优于所有的 baseline ,而 MVN2VEC-CON 超越了 independent 但是比 one-space 更差。这一现象的原因可以解释为:尽管我们通过配置超参数θ[0,1]$ \theta\in [0,1] $ 来调节context embedding{ci(m)}$ \left\{\mathbf{\vec c}_i^{(m)}\right\} $ 的参数共享,但是MVN2VEC-CON 中每个视图的{vi(m)}$ \left\{\mathbf{\vec v}_i^{(m)}\right\} $ 相互独立,因此它建模 collaboration 的能力受到限制。

    • preservationcollaboration 目标而言,Snapchat 网络位于 YouTubeTwitter 之间。在 Snapchat 网络上,我们提出的 MVN2VEC 在所有指标上都优于所有 baseline 。这证明了通过同时建模 preservationcollaboratioin 来提升模型性能的可行性,并且不会使得模型过度复杂化、也不需要监督信息。

    • MVNYouTube 上的表现不如 MVN2VEC,我们认为 MVE 是一个 collaboration 框架,它并未显式地建模 preservation 。而 preservation 目标又是 Youtube 数据集必须的。

      同时,MVE 并未从其注意力机制中获得性能提升,因为在我们的实验设置中,并未为它提供所需要的监督信息。

    • DMNEYouTube 上性能较差,原因是我们采用原始论文的超参数。另外,DMNE 是为更通用的多网络 multi-network 而设计,并不是专门针对多视图网络而设计。

    这些观察结果共同证明了通过同时建模 preservationcollaboration 来提高性能的可行性,而不会使得模型过度复杂化,也不需要监督信息。

  8. 最后我们研究超参数的影响。

    • 首先评估 embedding 维度d$ d $ 的影响。我们通过不同的d$ d $ 来评估在G(0)$ \mathcal G(0) $ 上的分类效果。注意:G(0)$ \mathcal G(0) $ 仅需要对 preservation 进行建模。

      结论:

      • one-space 方法在d=256$ d=256 $ 时效果最佳,但是它比d=256$ d=256 $ 的 independent 效果更差。不能期望 one-space 方法采用更大维度的 embedding 空间来保持多视图中不同视图携带的信息。
      • independent 方法在d=512$ d=512 $ 时效果最佳。
      • 所有四种方法的最佳性能都集中在d=256512$ d=256\sim 512 $ 之间。特别是 one-space 在四种方法之间,到达峰值性能的d$ d $ 值最小。这是意料之中的,因为 one-space 不会划分 embedding 空间从而适应多个视图。

    • 然后我们评估θ,γ$ \theta,\gamma $ 的影响。这里我们并未针对每个视图来配置各自的θm,γm$ \theta_m,\gamma_m $ ,每个视图个性化的配置留待未来研究。

      我们首先关注 snapchat 网络。

      • 对于 MVN2VEC-REG ,当γ=0$ \gamma = 0 $ 时它仅建模 preservation;随着γ$ \gamma $ 的增加它逐渐建模更多的 collaboration ,可以看到对应地模型性能逐步改善。模型的性能峰值在γ=0.010.1$ \gamma = 0.01\sim 0.1 $ 之间达到。
      • 对于 MVN2VEC-CON,当θ=0$ \theta = 0 $ 时它仅建模 preservation;随着θ$ \theta $ 的增加它逐渐建模更多的 collaboration 。注意:当θ=1$ \theta = 1 $ 时,MVN2VEC-CON 虽然context embedding 的参数{ci(m)}$ \left\{\mathbf{\vec c}_i^{(m)}\right\} $ 共享,但是每个视图的参数{vi(m)}$ \left\{\mathbf{\vec v}_i^{(m)}\right\} $ 相互独立,这阻止了 MVN2VEC-CON 来建模更多的 collaboration

      YouTube 网络上,无论θ,γ$ \theta,\gamma $ 怎样变化 MVN2VEC 都不会明显优于 independent,因为 YouTube 网络被 preservation 统治。

      Twitter 网络上,当γ$ \gamma $ 较大时 MVN2VEC-REG 超越了 one-space;而无论θ$ \theta $ 怎样变化 MVN2VEC-CON 都无法超越 one-space,因为 Twitter 网络更多地需要建模 collaboration,而MVN2VEC-CON 的设计阻止了它建模更多的 collaboration

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文