汪佳龙作者澳门大学博士生学校图神经网络研究方向

浅谈零样本网络表示学习

1、什么是零样本网络表示学习

这个问题主要来自两篇论文 AAAI 2018 和 TKDE 2020,在正式开始介绍零样本网络表示学习(Zero-shot Graph Embedding, ZsGE)之前,我们首先介绍一下什么是零样本学习

论文标题:RSDNE: Exploring Relaxed Similarity and Dissimilarity from Completely-imbalanced Labels for Network Embedding
论文来源:AAAI 2018
论文链接:https://www.paperweekly.site/papers/3566
代码链接:https://github.com/zhengwang100/RSDNE


论文标题:Network Embedding with Completely-imbalanced Labels
论文来源:TKDE 2020 
论文链接:https://www.paperweekly.site/papers/3567
代码链接:https://github.com/zhengwang100/RECT

假设这样一个场景,现在我们有了一个训练用的数据集,里面有 A、B、C 三类样本,可是在测试的时却需要我们去识别 D 和 E 两种未见过的类的样本。这就是零样本学习 Zero Shot Learning (ZSL) 所需要解决的问题。

而在之前的研究中,ZSL 的研究主要局限于计算机视觉领域,也是 CV 领域非常热门的一个研究方向。这是由于自然界包含太多物品和场景了,我们需要 AI 系统有强大的泛化能力,即能够识别那些未见到的类(unseen class)。

在网络表示学习中,同样存在着类似情况。由于网络的复杂性,标注样本很可能无法涵盖所有的节点类别,甚至我们根本不知道网络中有多少类别。本文将介绍如何在网络中利用 ZSL的思维来学习到 unseen 类别节点的网络表示。

1.1 问题定义

如上图所示,零样本网络表示学习(Zero-shot Graph Embedding,ZsGE)是指标注样本无法覆盖所有类别时的网络节点特征学习问题。这里,“zero-shot”强调所设计的算法应该能够处理那些来自不可见类的节点,这种场景也可以被称为完全非平衡标注场景。

这个问题非常具有实际意义,特别是当图很大且节点的类别很多的场景。比如在真实社交网络中,用户的类别可能很多,我们也很难找出每一类用户,甚至我们根本就不知道网络中到底有多少种用户。

1.2 现有方法无法处理ZsGE

论文 TKDE 2020 测试了两个经典的监督网络表示学习算法:LSHM 和 GCN。为了模拟图上的零样本场景(ZsGE),在每次测试中,都从训练数据中移除 1-2 个类,然后进行网络表示学习,可以发现这两个方法的分类精度下降的很快 [10%-35%]。为什么会发生这个情况呢?论文是这样解释的:

简单来说,由于网络中 unseen 和 seen 类别的节点是相关连的,只在 seen 类别的节点上训练一个分类模型,只能得到一个全局的次优解。由此可以得到结论,传统的监督网络表示学习方法在处理未知样本时性能表现较差。

2、解决方案

2.1 RSDNE浅层算法

首先,AAAI 2018 给出了一个浅层方法 RSDNE。如上图所示,其思想是放松类内相似性(intra-class similarity)和类间差异性(inter-class dissimilarity)的约束。

具体的,对于类内相似性,在嵌入的空间中,该方法只需保证同一类的节点处于同一个流形上,即每个标注节点只需和 k(比如 k=5)个相同标注的节点相近,而不需要和所有相同标注的节点都相近。

对于类间差异性,在嵌入的空间中,此方法不要求不同标注的节点之间的距离非常大,只希望他们离得别太近即可。其公式包含三个部分:

1)保持原有网络结构信息:

公式 (4) 就是 DeepWalk 的矩阵分解形式,其中 U 就是我们最终要求的网络表示(Graph Embedding),H 为上下文表示(context embedding),M 的具体定义为:

2)relaxed 类内相似性

公式 (5) 是对类内关系 (intra-class) 进行建模,保证属于同一类的样本之间在同一个“流形”上的相似性。这里矩阵 S 描述了这种类内相似性,u_{i} 是 U 矩阵中的值,代表第 i 个节点的特征。

3)relaxed 类间差异性

公式 (6) 是对类间关系 (inter-class) 进行建模,保证属于不同类别的样本之间的区别性。这里 W 的定义非常简单:只是把原有描述网络结构的 M 中标签不同的节点的权重置零。

此外,AAAI 2018 也给出了一个 light 版本,把公式 (5) 的 S 矩阵的构造简单化了,比如在其提供的 python 版本的源代码中,直接事先预构造一个近邻矩阵 S 来表示同一类的流形结构。

此文给出的方法是一个基于矩阵分解的方法,不过类似的思想很容易扩展到 DeepWalk 这种非矩阵算法上,比如用少量单位长度的相同标签的 path 来近似描述内类相似性;将连续包含不同标签节点的 path 从不同标签处断开从而近似保持类间差异性。

2.2 RECT深层算法

其次,TKDE 2020 的工作给出了一个深度的方法 RECT。该方法可以进一步的处理带属性的图和多标签场景。如上图所示,RECT 算法的核心是训练一个语义图神经网络(Semantic GNN)。

具体的,受 ZSL 的启发,该方法将原始的二值标签映射到语义空间来训练一个 GNN 模型。值得注意的是,与 CV 中的 ZSL 方法不同,这里的类别语义直接从原始图中得到,即不依赖于任何的人工标注或者第三方语言工具。

具体来说,该方法首先使用 GNN layer 进行图卷积和 MLP 进行映射,之后最后定义了两个 Loss Function:

1)语义空间描述损失:

公式 (17) 希望预测得到的语义向量与样本真实的语义向量尽量的相似。这里真实语义是通过一个 readout 函数得到的:。在实验中,这个 readout 函数被简化成了 mean 函数,非常容易计算。

2)网络结构保持损失:

公式 (18) 希望得到的网络表示能够保持原有的网络结构。这是个无监督的模型,这里 M 是上面提到的 DeepWalk 的矩阵形式,U 是我们最终要求的网络表示。

3、实验结果

TKDE 2020 的论文一共在五个数据集上做了实验,包含不带属性,带属性,单标签,多标签的网络。

3.1 零样本场景下的实验结果

▲ 零样本下的节点分类

可以看到在该场景下,RSDNE 的方法要优于那些浅层的有监督方法。同时 RECT 方法效果最好,要明显优于那些深层的监督 GNN 方法,相比  GCN 精度提升 [30%-300%]

▲ 零样本下的可视化(前两个类作为 unseen,50%label rate)

从图中可以看到传统的监督算法(LSHM和GCN)的 seen  类分的比较开,但是 unseen 类完全的杂糅在了一起。相对应的,RSDNE 的效果就好很多,并且呈现出一种“流形”的感觉。此外,RECT 的效果最好,是因为考虑了节点的属性信息。

3.2 平衡场景下的实验结果

这里平衡场景是指传统的有监督的方法所要求的标注数据覆盖所有网络节点类别。

从结果上来看,当标签能够覆盖所有类时,RSDNE/RECT 方法也和当下最好的浅/深层方法效果持平。甚至 RECT 仍然优于著名的 GCN 算法 30%~300%。这意味着 ZsGE 的方法有很好的鲁棒性和普适性。

论文是这样解释的,GCN 和 APPNP 这些使用分类模型的有监督方法很容易被真实场景中标签数据的非平衡所影响;然而 RECT 这类语义方法则不会,这是由于在语义空间的各个维度上各种类别的分布是大致平衡的。

直观可以这样理解,比如可能身高超过 2m 的人很少,不过所有人在“身高”这个语义维度上都有定义。

4、思考

零样本学习作为迁移学习的一个新兴研究方向,在传统 CV 领域已经崭露头角,但如何将这种“零样本”思想转换到网络表示学习中,还处于初始探究的状态。

由于网络表示学习处理的目标是图结构数据,这又与传统 CV 存在很大的差别,相关理论还不完整,这给我们的研究带来了非常多的有趣的挑战。

参考文献

[1] RSDNE: Exploring Relaxed Similarity and Dissimilarity from Completely-imbalanced Labels for Network Embedding. (AAAI 2018).

[2] Network Embedding with Completely-imbalanced Labels. (TKDE 2020).

[3] 项目及代码: https://zhengwang100.github.io/project/zero_shot_graph_embedding.html

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论零样本学习
1
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

迁移学习技术

迁移学习是一种机器学习方法,就是把为任务 A 开发的模型作为初始点,重新使用在为任务 B 开发模型的过程中。迁移学习是通过从已学习的相关任务中转移知识来改进学习的新任务,虽然大多数机器学习算法都是为了解决单个任务而设计的,但是促进迁移学习的算法的开发是机器学习社区持续关注的话题。 迁移学习对人类来说很常见,例如,我们可能会发现学习识别苹果可能有助于识别梨,或者学习弹奏电子琴可能有助于学习钢琴。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

零样本学习技术

从仅仅一个或一小撮样本中学习一个新的概念,而普通的机器学习标准算法通常需要几十或几百个表现类似的样本。

矩阵分解技术

矩阵分解是一种将矩阵简化为其组成部分的方法。这种方法可以简化更复杂的矩阵运算,这些运算可以在分解的矩阵上执行,而不是在原始矩阵本身上执行。它的衍生Non-negative matrix factorization也被用于降维等操作上。

节点分类技术

节点分类任务是算法必须通过查看其邻居的标签来确定样本的标记(表示为节点)的任务。

暂无评论
暂无评论~