和GFT类似,本文使用task-tree来作为统一不同图任务的学习实例。图中什么样的信息是可以实现跨图泛化的?过去的方法通常从2个角度出发:(1)一些方法利用graphon来作为跨图的可迁移pattern,如果两个图生成自相同的graphon,那么这两个图有相似的结构属性,但是这类方法依赖于强的生成假设,并且从大量图中计算graphon是计算复杂的;(2)可以通过寻找重复出现的motif来作为可迁移的pattern:在不同图中都可用于预测图属性的关键substructure,类似于自然语言中表示积极或者消极的词语就是关键子结构,在不同的句子中都可用于预测句子情感。但MPNN难以捕获这这些子结构。本文提出用task-tree来作为transferable pattern。
定义1(任务相关节点)节点级任务,task-relevant node就是节点本身 $v_i^t$;边级任务的task-relevant node是边的endpoints $\{v_i^t, v_j^t\}$ for target edge $e_{ij}$;对于图级任务,task-relevant nodes是 $\{v_i^t\}^{|V|}_{i=1}$为目标图中的所有节点。
定义2(计算树)对于一个节点 $v$,它的 $L$层计算树 $T^L_v$是以该节点为根节点的 $L$层subtree,其中 $T^1_v =v$。
定义3(Task-Trees)对于一个任务的一组task-relevant nodes ${v_i^t,\ldots,v_n^t}$和这些节点的计算树 $\{T_1, \ldots,T_n\}$。这些计算树可以通过引入连接到所有任务相关节点的虚拟节点构成一个更大的task-tree $T^t$。如下图所示,虚拟节点连接到任务相关的节点上,对于节点分类,目标节点被连接到虚拟节点;边任务上,endpoints被连接到虚拟节点。
对于一个task-tree $T^t$,它由一个虚拟节点 $v^t$和它的任务相关节点 $\{v_i^t,\ldots,v_n^t\}$,通过MEAN aggregator over computation trees来计算这个task-tree的表示:
$$ z^t=\phi\left(T^t\right)=\frac{1}{n} \sum_{i=1}^n \phi\left(T_i\right) $$
所有分类任务均通过任务目标task-tree的表示来做prediction。
GIT与GFT的区别:GFT通过实验证明计算树可以所谓跨任务的可迁移实例;GIT提供了理论基础。
Theoretical Analysis of Task-Trees Stability on Task-Trees 首先分析GNN在学习task-tree表示时的稳定性,如果GNN可以为具有相似subtree的task-tree和生成相似的embedding,那么就说明GNN关于task的输出时稳定的。即task-tree的子树越相似,那么他们的embedding越相似,那么具有相似subtree的task-tree可以用同一个GNN来学习。也就是说task-tree的相似度可以来决定两个任务是否可以用同一个GNN来学习。具体来说,用邻居的平均来表示每层subtree的信息: $\boldsymbol{x}_i^{(l)}=\frac{1}{\left|\left|\mathcal{N}_i\right|\right|} \sum_{j \in \mathcal{N}_i} \boldsymbol{x}_j^{(l-1)}$。给定两个 $L$层的task-tree $T_t^1$和 $T_t^2$,他们的task-relevant nodes分别是 $\{v_1, \ldots,v_n\}$和 $\{v_1, \ldots,v_m\}$,他们可能代表不同的任务,每个task-tree的subtree数量可能也不同,比如节点级任务的subtree和图级任务的subtree数量差别很大。用GNN为task的输出来定义task-tree之间的差异 $\Delta:=\left|\left|\phi\left(T_1^t\right)-\phi\left(T_2^t\right)\right|\right|$,它由如下bound:
$$ \begin{aligned}\Delta & =\left|\left|\phi\left(T_1^t\right)-\phi\left(T_2^t\right)\right|\right|=\left|\left|\frac{1}{n} \sum_{i=1}^n \phi\left(T_i\right)-\frac{1}{m} \sum_{j=1}^m \phi\left(T_j\right)\right|\right| \\ & \leq \frac{1}{n m} \sum_{i=1}^n \sum_{j=1}^m\left(\mathcal{C}_1\left|\left|\boldsymbol{x}_i^{(0)}-\boldsymbol{x}_j^{(0)}\right|\right|+\ldots\right. \\ & \left.+\mathcal{C}_1 \mathcal{C}_2^{L-1}\left|\left|\boldsymbol{x}_i^{(L-1)}-\boldsymbol{x}_j^{(L-1)}\right|\right|\right) \leq 2 \mathcal{B}_{\boldsymbol{x}} \cdot \mathcal{C}_1 \frac{\mathcal{C}_2^L-1}{\mathcal{C}_2-1}\end{aligned} $$
...