Meta-Graph Few Shot Link Prediction Via Meta Learning

2021-06-04

字数统计: 3.7k | 阅读时长≈ 16 分钟

https://arxiv.org/pdf/1912.09867

Meta-Graph Few Shot Link Prediction Via Meta Learning，2019，arxiv e-preprint

总结：基于梯度的元学习+图签名函数，采用VGAE作为链路预测模型。基于梯度的元学习在多个任务之间学习一个共享参数使得使得新图上的VGAE具有一个较好的初始参数；图签名函数（GCN实现）为每个图学习一个图签名融合到VGAE模型使得每个图的VGAE模型graph specific化。

1. 简介

1.1 摘要

We consider the task offew shot link prediction, where the goal is to predict missing edges across multiple graphs using only a small sample of known edges. We show that current link prediction methods are generally ill-equipped to handle thistask—as they cannot effectively transfer knowledge between graphs in a multi-graph setting and are unable to effectively learn from very sparse data. To address this challenge, we introduce a new gradient-based meta learning framework,Meta-Graph, that leverages higher-order gradients along with a learned graph signature function that conditionally generates a graph neural network initialization.Using a novel set of few shot link prediction benchmarks, we show that Meta-Graph enables not only fast adaptation but also better final convergence and can effectively learn using only a small sample of true edges.

本文作者考虑小样本链路预测任务，其目标是仅仅通过少量真实边就能够跨多个图正确预测图中缺失的边。现有的链路预测算法基本都难以处理这类问题，因为他们无法在不同的图之间传递知识，也无法仅仅通过少量真实边进行有效地学习。为了解决这个难题，本文作者提出了一种新的基于梯度的元学习架构Meta-Graph，它利用高阶梯度和图签名函数（对图神经网络进行条件初始化）。在一些小样本链路预测标准数据集上，实验结果表明Meta-Graph不仅可以快速适应新任务，还能得到一个比较好的收敛，仅仅通过少量真实边就能进行有效地预测。

1.2 本文工作

现有的链路预测算法通常都是在单个大型图上进行的，并且假设图相对完整（至少保留50%的边用于训练）。本文作者提出了针对小样本链路预测的模型，其目标是在多个只包含少量边的图上进行链路预测，应用于这样一个场景：可以获取到来自同一个域的大量图，但是每个图只包含少量真实边。例如在生物领域，不同的组织、细胞生物体之间存在交互反映形成相互作用网络，但是这些关系可能是noisy和sparse的，我们需要学习多个图之间的信息来克服这种稀疏性。

本文作者将传统小样本学习领域的基于梯度的元学习方法拓展到图上来，提出了一种新的架构Meta-Graph用于小样本链路预测。采样多个服从同一分布的图作为任务，学习一个全局参数集合，并应用策略来训练可以完成小样本链路预测任务的GNN。另外，为了让模型更快地适应新图，作者提出了一个图签名函数，根据输入图的结构对GNN链路预测模型进行初始化。

1.3 问题定义

假设存在一个图分布 $p(\mathcal G)$ （比如从同一个大图中采样得到），随机采样图 $\mathcal G_i\sim p(\mathcal G)$ 用于训练，图 $\mathcal G_i$ 定义为 $\mathcal G_i=(\mathcal V_i,\mathcal E_i, X_i)$ ， $\mathcal V_i$ 和 $\mathcal E_i$ 分别表示节点集合和边集合， $X_i\in\mathbb R^{|\mathcal V_i|\times d}$ 表示节点属性。
假设采样的每个图 $\mathcal G_i$ 都是一个简单图，即只包含一种类型的关系且不存在self-loop，图中的每个节点 $v\in\mathcal V_i$ 都存在一个来自同一个向量空间的属性向量 $x_v\in\mathbb R^d$ 。
假设训练期间，对于每个 $\mathcal G_i$ 只要少量边可见，即 $\mathcal E_i^{train}\subset\mathcal E$ ，且 $|\mathcal E_i^{train}|<<|\mathcal E_i|$ 。

学习目标：利用 $\mathcal G_i\sim p(\mathcal G),i=1...n$ 训练Meta-Graph，可以快速在一个新图上 $\mathcal G_*\sim p(\mathcal G)$ 有效地实现链路预测。具体来说就是学习到一个全局参数集合 $\theta$ 和一个图签名函数 $\mathcal \phi(\mathcal G_*)$ ，生成一个有效的初始参数 $\phi_*$ ，用于图 $\mathcal G_*$ 上进行链路预测。

对比传统链路预测

Meta-Graph不是在单个图上学习，而是从来自同一个分布域的多个图 $\{\mathcal G_1,...,\mathcal G_n\}$ 上学习。
小样本，假设只有非常少量的边在训练是可见 $\leq0.3$ （传统的通常 $\geq0.5$ ）。
区分global参数（对图之间的一些共性知识进行编码，图的潜在分布）和local参数（针对某个图进行优化），这策略让我们可以兼顾图之间的共性知识和每个图特有的知识。

2. 方法

分两部分：Local链路预测模型（针对每个图）；global模型（基于梯度的元学习）。

Meta-Graph的核心思想是使用基于梯度的元学习方法为local模型学习一个全局共享参数，同时为每个图 $\mathcal G_i$ 学习一个编码器，对初始参数进行graph-specific调整。

2.1 局部链路预测模型

本文使用变分图自编码器VGAEs作为链路预测架构的基础。给定图 $\mathcal G=(\mathcal V,A,X)$ ，VGAE学习一个预测模型 $q_\phi(Z|A,X)$ ， $Z\in\mathbb R^{|\mathcal V|\times d}$ 的每一行 $z_v\in\mathbb R^d$ 表示节点嵌入，可以用来评估两个节点之间是否存在边。定义 $q_{\phi}\left(z_{v} \mid A, X\right)=\mathcal{N}\left(z_{v} \mid \mu_{v}, \operatorname{diag}\left(\sigma_{v}^{2}\right)\right)$ ，其中正态分布的参数通过GNNs学习得到：

\mu=\operatorname{GNN}_{\mu}(A, X), \quad \text { and } \quad \log (\sigma)=\operatorname{GNN}_{\sigma}(A, X)\tag 1

VGAE的生成器定义为：

\begin{aligned} &p(A \mid Z)=\prod_{i=1}^{N} \prod_{j=1}^{N} p\left(A_{u, v} \mid z_{u}, z_{v}\right) &\text { with } \quad p\left(A_{u, v} \mid z_{u}, z_{v}\right)=\sigma\left(z_{u}^{\top} z_{v}\right) \end{aligned}\tag 2

节点u和v之间是否存在一条边和节点嵌入的点积成正比。这样负责预测的GNN模型的优化函数定义为：

\mathcal{L}_{G}=\mathbb{E}_{q_{\phi}}\left[\log p\left(A^{\text {train }} \mid Z\right)\right]-K L\left[q_{\phi}\left(Z \mid X, A^{\text {train }}\right) \| p(z)\right]\tag 3

2.2 整体架构

Meta-Graph的核心思想就是：**基于梯度的元学习方法优化一个共享的用于VGAE的初始参数$\theta$，同时也学习一个图编码函数$\psi\left(\mathcal{G}_{i}\right)$对初始参数$\theta$进行调整，使其graph-specific化。**具体来说，利用下面两个模块为每个图$\mathcal G_i$上的VGAE模型分配一个特有的初始化参数$q_{\phi_i}$用于链路预测：

全局共享的初始参数 $\theta$ ，通过元学习获得，采用二阶梯度下降进行优化，为所有图提供一个有效的初始化参数点。
图签名函数 $s_{\mathcal{G}_{i}}=\psi\left(\mathcal{G}_{i}\right)$ ，调整推理模型的参数 $\phi_i$ 。调整推理模型为 $q_{\phi_{i}}\left(Z \mid A, X, s_{\mathcal{G}_{i}}\right)$ ，把图的签名 $s_{\mathcal G_i}$ 作为条件输入。作者采用k层GCN计算图签名：
$\begin{aligned} &s_{\mathcal{G}}=\psi(\mathcal{G})=\operatorname{MLP}\left(\sum_{v \in \mathcal{V}} z_{v}\right) &\text { with } \quad Z=\operatorname{GCN}(A, X) \end{aligned}\tag 4$
其中GCN表示k层卷积神经网络，MLP表示全连接层神经网络。和全局参数 $\theta$ 一样，图签名模型 $\psi$ 也是通过二阶梯度下降进行优化。

1. 采样一个batch的训练图 2. 使用全局参数$\theta$和图签名$\psi$初始化每个图的链路预测模型VGAE 3. 对VGAE模型执行K次梯度下降（这里冻结$s_\mathcal G$） 4. 添加验证集的边后采用二阶梯度下降法优化全局参数$\theta$和签名函数

2.3 Meta-Graph的变体

在具体实现Meta-Graph架构的时候，作者考虑了几种不同的将图签名函数用到VGAE的方式。对于所有变体，都是采用标准的GCN作为VGAE的骨架，按照如下方式堆叠K层：

h_{v}^{(k)}=\operatorname{ReLU}\left(\sum_{u \in \mathcal{N}(v) \cup\{v\}} \frac{m_{s_{\mathcal{G}}}\left(W^{(k)} h_{u}^{(k-1)}\right)}{\sqrt{|\mathcal{N}(v)||\mathcal{N}(u)|}}\right)\tag 5

上面公式和标准GCN传播方法最大的不同就是加了一个调整函数 $m_{s_\mathcal G}$ ，用图签名对传播的消息进行调整。直觉上，作者是希望图签名能够编码图结构信息，然后用图签名调整VGAE模型的参数，使其适应于当前的图。

2.3.1 GS-Modulation

受 Gnn-film启发，采用basic feature-wise linear modulation定义调整函数 $m_{s_\mathcal G}$ ：

\begin{array}{c} \beta_{k}, \gamma_{k},=\psi(\mathcal{G}) \\ m_{\beta_{k}, \gamma_{k}}\left(W^{(k)} h_{u}^{(k-1)}\right)=\gamma_{k} \odot W h^{(k-1)}+\beta_{k} \end{array}\tag 6

这里通过对公式4的输出添加tanh函数，限制 $\beta_k$ 和 $\gamma_k$ 的范围为 $[-1,1]$ 。

2.3.2 GS-Gating

公式6定义的调整函数比较简单、直观，但是存在一个问题就是“always on”，有时候这种调节可能对学习起到反作用。为了让模型能够自适应的进行调整，对feature-wise线性调整做了改进，增加一个gating term $\rho_k$ ：

\begin{aligned} \beta_{k}, \gamma_{k}, \rho_{k} &=\psi(\mathcal{G}) \\ \beta_{k} &=\rho_{k} \odot \beta_{k}+\left(\mathbb{1}-\rho_{k}\right) \odot \mathbb{1} \\ \gamma_{k} &=\rho_{k} \odot \gamma_{k}+\left(\mathbb{1}-\rho_{k}\right) \odot \mathbb{1} \\ m_{\beta_{k}, \gamma_{k}}\left(W^{(k)} h_{u}^{(k-1)}\right) &=\gamma_{k} \odot W h^{(k-1)}+\beta_{k} \end{aligned}

2.3.3 GS-Weights

结合gating思想和feature-wise线性调整思想，分别求出调整前和调整后的信息，然后通过门向量将两者结合到一起：

\begin{aligned} \beta_{k}, \gamma_{k}, \rho_{k} &=\psi(\mathcal{G}) \\ h_{v}^{(k), 1} &=\operatorname{ReLU}\left(\sum_{u \in \mathcal{N}(v) \cup\{v\}} \frac{W^{(k)} h_{u}^{(k-1)}}{\sqrt{|\mathcal{N}(v) \| \mathcal{N}(u)|}}\right) \\ h_{v}^{(k), 2} &=\operatorname{ReLU}\left(\sum_{u \in \mathcal{N}(v) \cup\{v\}} \frac{m_{s_{\beta_{k}, \gamma_{k}}}\left(W^{(k)} h_{u}^{(k-1)}\right)}{\sqrt{|\mathcal{N}(v) \| \mathcal{N}(u)|}}\right) \\ h_{v}^{(k)} &=\rho_{k} \odot h_{v}^{(k), 1}+\left(\mathbb{I}-\rho_{k}\right) \odot h_{v}^{(k), 2}, \end{aligned}

3. 实验

设计了三个用于小样本链路预测任务的benchmark，三个benchmark中的图集合都是采样自同一个domain。80%的图用于训练，10%的图用于验证，这些图用来优化Meta-Graph的global参数和baseline的参数。剩余的10%的图用于测试，学习目标就是训练好的模型在测试图中能准确预测边。

一、数据集

PPI网络和3D点云数据FirstMMDB以及AMINER引用数据。

**二、baseline方法**

对Meta-Graph调整后作为baseline

直接使用MAML，预训练改进的VGAE（Finetune），直接将VGAE应用到每个测试图（No Finetune）。还有一些其他的Adamic和Deepwalk。

三、实验结果

实验部分主要研究四个问题：

和不同baseline方法相比，Meta-Graph的性能如何？

在只保留10%的边的情况下，Meta-Graph仍然具有很强大的性能。在Ego-AMINER数据集上的实验结果比较奇怪，和另外两个数据集不同，保留更多的边模型性能并没有呈递增趋势。作者猜测可能是因为MAML中使用的高阶梯度优化是不稳定的，这在一定程度上抵消了GS-gating（不是很懂）。作者在附录中贴了另一个实验结果，在训练时使用更多的边，模型性能会随着边密度增大而变好。
Meta-Graph的快速适应能力如何？在测试图上Meta-Graph执行少量梯度下降后效果如何？

模型执行5次梯度下降，发现Meta-Graph效果最好。同样地，在Ego-AMINER数据集上效果还是比较差。
下图展示了梯度下降过程中的AUC曲线，Meta-Graph少量梯度下降后就过拟合了需要提前终止梯度。