1、什么是零样本网络表示学习
这个问题主要来自两篇论文 AAAI 2018 和 TKDE 2020,在正式开始介绍零样本网络表示学习(Zero-shot Graph Embedding, ZsGE)之前,我们首先介绍一下什么是零样本学习。
假设这样一个场景,现在我们有了一个训练用的数据集,里面有 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%]。
从图中可以看到传统的监督算法(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