Graph Few-shot Learning via Knowledge Transfer

2021-06-04

论文笔记 / 小样本图学习

字数统计: 3.4k | 阅读时长≈ 14 分钟

https://arxiv.org/pdf/1910.03053

Graph Few-shot Learning via Knowledge Transfer，2020，AAAI

总结：本文利用FSL中元学习思想，随机采样一系列图（等同于元学习中的一系列任务），提出的GFL模型主要背靠原型网络，计算每个类别的原型，然后根据节点和类别原型之间的距离判断节点所属类别。然后在这个基础上做了很多缝合和优化工作：

借鉴Diffpool方法，学习图的层级表示，并融合到PGNN参数中，使得每个图都有独特的 $\phi_i$
在初始节点嵌入的基础上，在属于同一个类别的所以节点之间构造关系结构R，弥补原始节点嵌入只聚合了距离较近的邻居信息这一缺陷
在损失函数中引入图自编码器损失，来提高训练的稳定性和节点表示的质量

1. 简介

1.1 摘要

Towards the challenging problem of semi-supervised node classification, there havebeen extensive studies. As a frontier, Graph Neural Networks (GNNs) have arousedgreat interest recently, which update the representation of each node by aggregatinginformation of its neighbors. However, most GNNs have shallow layers with alimited receptive field and may not achieve satisfactory performance especiallywhen the number of labeled nodes is quite small. To address this challenge, weinnovatively propose a graph few-shot learning (GFL) algorithm that incorporatesprior knowledge learned from auxiliary graphs to improve classification accuracyon the target graph. Specifically, a transferable metric space characterized by a nodeembedding and a graph-specific prototype embedding function is shared betweenauxiliary graphs and the target, facilitating the transfer of structural knowledge.Extensive experiments and ablation studies on four real-world graph datasetsdemonstrate the effectiveness of our proposed model.

对于半监督节点分类这个难题，业内已经有了很多相关研究。GNN作为研究前沿，通过聚合邻居信息来更新节点表示，最近吸引了很多关注。但是，大部分GNNs都是浅层模型，接受域有限，很难取得令人满意的表现，尤其在有标签节点数量很少的时候。为了解决这个问题，我们创新地提出了图小样本学习（GFL）算法，利用从辅助图中学习到的先验知识来提高目标图中的分类准确率。具体来说，利用结构化知识的可迁移性，辅助图和目标图共享一个由节点嵌入和图原型嵌入函数构成的可迁移度量空间。在真实图数据集上的大量实验表明我们提出的模型十分有效。

1.2 本文工作

图中的半监督节点分类问题时十分重要且具有挑战的，在标注数据（获取成本高）有限的情况下更是如此。最近，GNN通过聚合邻居信息来不断更新节点特征，在这些任务中取得了不错的表现。但是随着层数增加，GNN训练难度加大，并且会出现过平滑问题，这限制了GNN的表现。尤其在有标签数据很少的情况下，GNNs无法获取足够多的的全局信息，表现很差。

受小样本学习的启发，本文作者希望利用从辅助图中学习到的知识来提高目标图中节点分类的准确性。其背后的想法是：辅助图和目标图之间很可能共享局部拓补结构和类相关的节点特征。

最近小样本学习的两个方向是：gradient-based方法和metric-based方法，前者将可迁移的知识视作初始参数，后者将可迁移的知识视作一个度量空间。本文作者提出了一种基于度量学习的原生的图小样本学习模型GFL。

GFL学习一个可迁移的度量空间，节点的标签被预测为距离最近的类原型所代表的类别。度量空间通过两个嵌入函数来刻画：节点嵌入和类别原型。具体来说：

GFL首先通过图自编码器（GNN为骨架）学习每个节点的表示
然后为了更好地捕捉全局信息，作者为每个类别构建一个关系结构，通过prototype GNN来学习每个类别的原型。

最重要的是这两个嵌入函数都编码了从辅助图中学习到的结构知识，以此来弥补标注数据不足的问题。除了这两个节点层面的结构，作者还通过一个层次图门来描述graph-level的表示，进一步强化“相似的图有相似的度量空间”。

1.3 问题定义

按照 $\varepsilon$ 概率分布采样一系列图 $\{\mathcal G_1,...,\mathcal G_{N_t}\}$ ，每个图 $\mathcal G_i\sim\varepsilon$ ，且提供少量 $n^{s_i}$ 个有标签节点support集合 $S_i=\{(x_{i,j}^{s_i},y_{i,j}^{s_i})\}_{j=1}^{n^{s_i}}$ 和query节点集合 $Q_i=\{(x_{i,j}^{q_i},y_{i,j}^{q_i})\}_{j=1}^{n^{q_i}}$ 。Query集 $Q_i$ 中的每个节点 $j$ ，我们假设可以通过相似度量 $d$ 来关联其节点嵌入 $f_\theta(A,x_{i,j}^{q_i}):\mathbb R^h\rightarrow \mathbb R^{h'}$ 和支持集中的表示 $(f_\theta(A,x_{i,j}^{s_i}),y_{i,j}^{s_i})$ ，以此预测节点 $j$ 对应的label。

具体来说，在原型网络中，类别 $k$ 的原型 $c_i^K$ 定义为 $c_i^k=\sum_{x_{i,j}^{s_i}\in S_i^k}f_\theta(A,x_{i,j}^{s_i})/|S_i^k|$ （就是类别k下所有节点表示的平均值）。对于图 $\mathcal G_i$ ，其查询集 $Q_i$ 上的损失定义为 $\mathcal L_i=\sum_k\mathcal L_i^k$ ，其中：

\mathcal L_i^k=-\sum\limits_{(x_{i,j}^{q_i},y_{i,j}^{q_i})\in Q_i^k}log\frac{exp(-d(f_\theta(A,x_{i,j}^{q_i}),c_i^k))}{\sum_{k'}exp(-d(f_\theta(A,x_{i,j}^{q_i}),c_i^{k'}))}

在训练阶段，嵌入函数 $f_\theta$ 的参数通过 $min_\theta\sum_{i=1}^{N_t}\mathcal L_i$ 来优化。训练完毕后，给定一个只有少量support nodes的新图 $\mathcal G_t$ ，学习到的嵌入函数可以用来提高学习效率。

2. 方法

GFL架构如上图所示，共包含三个组件：graph structured prototype，hierachical graph representation gate和auxiliary graph reconstruction。

2.1 Graph Structured Prototype

总结：在属于同一类别的节点之间构建关系结构R，并将GNN模型应用于R进一步完善节点表示。随后根据原型网络（小样本中的方法）思想，计算每个类别原型c。

大多数情况下，图中一个节点扮演**两个重要角色**：

一个是和邻居（可能属于不同类别）之间的局部交互（embedding结果 $Z_i$ 来描述这种局部信息）
另一个是和同类别节点（距离可能相对较远）之间的交互（作者通过prototype GNN模型来对支持集节点之间的关系结构建模，并学习其原型）

给定每个节点的表示，首先提取属于类别k的所有样本的关系结构。对于每一个图 $\mathcal G_i$ ，样本集 $S_i^k$ 的关系结构构建方法为：

基于一些相似度度量，比如k-hop共同邻居的数量。为了提高 $R_i^k$ 的稳定性，避免异常节点的影响，本文中作者引入了一个阈值 $\mu$ ，如果两个节点之间的相似度小于 $\mu$ ，那么边权重设置为一个固定值 $\mu_0$ 。

然后，作者通过PGNN模型对相同类别间的节点的关系进行建模，对原始节点嵌入进一步优化 $PGNN_\phi(\mathcal R^k_i,f_\theta(S_i^k))$ ，其中PGNN的参数为 $\phi$ ，这是一个全局共享的参数。

类别原型计算方法如下， $j$ 表示j-th节点的表示：

c_i^k=Pool_{j=1}^{n^{s_i^k}}(PGNN_\phi(\mathcal R_i^k,f_\theta(S_i^k))[j])

其中 $Pool$ 表示最大或这平均池化操作， $n^{s_i^k}$ 表示 $S_i^k$ 中节点数量。

2.2 Hierachical Graph Representation Gate

总结：2.1节中类别原型的计算高度依赖PGNN模型，而PGNN的参数 $\phi$ 是全局共享的。考虑到不同图可能有不同的拓扑结构，所以作者参照Diffpool学习每个图的层级表示 $h$ ，然后通过门函数将其于 $\phi$ 融合到一起形成新的参数 $\phi'$ ，这样每个图都有自己独特的PGNN参数 $\phi'$ ，可以学到作者所谓的graph-specific信息。

如上图所示，层级图模型和Diffpool中的类似，包含Node Assignment和Representation Fusion两部分。

Node Assignment

该阶段学习一个从当前层节点映射到下一层节点的分配概率矩阵。 $K^r$ 表示第r层图的节点数， $X_i^r$ 表示特征矩阵， $A_i^r$ 表示邻接矩阵，从 $k^r$ 节点到 $k^{r+1}$ 节点的assignment value计算方法如下：
$p_i^{k^r\rightarrow k^{r+1}}=\frac{exp(AGNN(A_i^r,X_i^r)[k^r,k^{r+1}])}{\sum_{\bar k^{r+1}=1}^{K^{r+1}}exp(AGNN(A_i^r,X_i^r)[k^r,\bar k^{r+1}])}$
其中 $exp(AGNN(A_i^r,X_i^r)[k^r,k^{r+1}])\in\mathbb R^1$ 表示从 $r$ 层 $k^r$ 节点到 $r+1$ 层 $k^{r+1}$ 的分配概率，整个 $r$ 层到 $r+1$ 层的分配矩阵为 $P^{r\rightarrow r+1}_i\in\mathbb R^{K^r\times K^{r+1}}$ 。
Representation Fusion

得到assignment矩阵 $P_i^{r\rightarrow r+1}$ 后， $r+1$ 层的邻接矩阵 $A_i^{r+1}=(P_i^{r\rightarrow r+1})^TA_i^rP_i^{r\rightarrow r+1}$ ，特征矩阵 $X_i^{r+1}=(P_i^{r\rightarrow r+1})^TFGNN(A_i^r,X_i^r)$ 。

这样聚合 $r+1$ 层所有节点的特征表示就是该层整图的特征表示：

h_i^{r+1}=Pool_{k^{r+1}=1}^{K^{r+1}}((P_i^{r\rightarrow r+1})^TFGNN(A_i^r,X_i^r)[k^{r+1}])

得到所有层的图表示 $\{h_i^1,...,h_i^R\}$ 后，在通过聚合其将所有表示聚合到一起作为最终的表示。本文采用的聚合方式是加权聚合，权重向量 $q_i$ 是可学习参数：

h_i=AGG_{att}(\{h_i^1,...,h_i^R\})=\sum\limits_{r=1}^R\beta_i^rh_i^r=\sum\limits_{r=1}^R\frac{q_i^Th_i^r}{\sum_{r'=1}^Rq_i^Th_i^{r'}}h_i^r

得到最终图层级表示 $h_i$ 后，作者引入门函数将其和PGNN参数 $\phi$ 融合到一起，得到graph-specific参数 $\phi_i$ ：

\phi_i=g_i\circ\phi=\mathcal T(h_i)\circ\phi

其中 $\circ$ 表示element-wise乘法， $g_i=\mathcal T(h_i)=\sigma(W_gh_i+b_g)$ ， $W_g$ 和 $b_g$ 是可学习参数。

2.3 Auxiliary Graph Recontruction

在实际中，只通过类别匹配的损失函数很难学习到非常有效的节点表示，这激励这我们要设计一个新约束条件来训练稳定、高质量的节点表示。因此，对于节点嵌入函数，我们使用一个图自编码器对其进行优化，重构损失定义如下：

\mathcal L_r(A_i,X_i)=||A_i-GNN_{dec}(Z_i)GNN^T_{dec}(Z_i)||_F^2

其中 $Z_i=GNN_{enc}(A_i,H_i)$ 是每个节点的表示。回顾1.3问题定义中定义的损失函数，这样GFL的整体优化目标就是 $min_\Theta\sum_{i=1}^{N_t}\mathcal L_i+\gamma\mathcal L_r(A_i,X_i)$ ， $\Theta$ 表示所有的可学习参数。