💟 My Notebook 🌻

在llm里面，In-Context Learning就是用一些新任务的问答例子来提示LLM，使得LLM不需要更新参数，也能基于这些例子来对新的任务生成输出。 为LM的预训练任务实际上是next token prediction的任务，由于prompt和回答只是相邻的tokens，因此 Transformer 的自注意力可以计算要补全的句子和之前token之间的关系，从而让模型动态推断出新的决策规则。In-Context Learning实际上也是一种next token prediction的任务，所以In-Context Learning是和预训练任务相关的。 Prodigy和All in One (KDD 2023)是同期工作，目的都是为了去提示Pretrained graph model。 All in One 是已经有一个Pretrained graph model，然后用meta learning基于冻结的pretrained model，去学一个prompt graph，使得这个prompt graph和原图结合起来之后可以使预训练模型泛化到新的任务上。 All in One 存在的问题是，All in one要对测试图做finetune。但实际上我们知道foundation model是不需要fine tune的。遇到一个新任务，因为支持in-context learning，可以基于给出的prompt example 来对新任务直接做出预测。而Prodigy就是不需要fine tune的graph prompt方法，它是直接以in-context learning的方式来预训练模型。Prodigy在预训练图上构造一堆prompt example和queries，预训练的优化目标是使在给定prompt examples和query set的情况下，query set的预测损失最小，也就是说模型的参数由prompt examples来调整，优化目标是使得query set的损失最小。 Prompt Graph Representation 首先要基于预训练的图构造一个支持in-context learning的prompt graph。然后在这个prompt graph上以in-context learning的方式来预训练模型。具体来说，在预训练图上构造一个 $m$-way $k$-shot的分类任务。预训练图为MAG240M，该图中有122M个节点，1.3B条边，153个类。 在每次训练epoch中，采样 $m=30$个class，每个class选择 $k=3$个样本作为prompt examples $\mathcal{S}$，也就是每个epoch有90个prompt examples。每个类别取4个样本作为query set $\mathcal{Q}$。也就是 $\mathcal{S} = \{(x_i, y_i)\}^{mk}_{i = 1}$ 作为预训练阶段的support set。 $\mathcal{Q} = \{x_i\}^n_{i = 1}$作为预训练阶段的query set，也就是预训练阶段的优化目标是要在query set上的损失最小。 ...

目的：将图结构调整为适配LLM的输入。具体来说，将图节点表示为图结构感知和属性感知的序列，然后将序列映射到token embedding space中，从而使LLM可以用处理text tokens的方式来对Graph token embeddings进行处理。为了实现这个目标，就要求node sequence必须充分保存中心节点的结构信息。 Structure-Aware Graph Translation LLaGA的目的是将graph翻译成可被LLM理解的token embedding sequence的形式。同时，这可以利用LLM固有的推理能力来处理图的任务，并且无需改变LLM的参数（foundation model）。为了实现这个目标，LLaGA将图结构转化为node embedding sequences，这些sequences融合了图的局部和更大范围的结构信息，然后将node embedding sequences通过一个projector转化为LLM可以处理的token embedding sequence。 第一步是将图转换为node embedding sequences。由于图分析的基本单位是节点，所以本工作开发了2个节点级templates，这些templates是多功能的，不仅可以用于节点级任务，也可以用于边级任务。分别是一个Neighborhood Detail Template，提供对中心节点及其周围环境的深入观察；Hop-Field Overview Template，提供了一个节点邻居的总结视角，可以拓展到更大的域。这两个模板都旨在编码节点周围的结构信息，为分析提供不同的视角。 Neighborhood Detail Template Neighborhood Detail Template用于描述节点和其周围邻居的详细信息。给定一个中心节点 $v$，需要构造一个形状固定的tree。对于中心节点 $v$的每跳邻居，定义一组邻居采样的size： $n_1$, $n_2$, …，其中 $n_i$表示第 $i$跳邻居的采样数量。对于 $1$-hop邻居集合 $\mathcal{N}_v^1$，从其中随机采样 $n_1$个邻居，表示为 $\widetilde{\mathcal{N}}_v^1$。如果 $\left|\mathcal{N}_v^1\right|<n_1$，那么用placeholder nodes来补全 $n_1$个邻居。注意，这里定义的每跳邻居的采样数量 $n_1, n_2, \cdots$是应用于所有节点的。得到的 $v$-centered tree如下图所示： 这里定义 $n_2 = 3$，如果2跳邻居不满3个节点，那么用 placeholder node $[\text{pad}]$来占位。然后我们从tree的中心节点开始遍历，可以把这棵计算树转换为一个固定长度的node sequence。这个node sequence描述了以 $A$为中心的局部邻域内的节点相对结构位置（从近到远）。 上面的步骤将中心节点和它的结构信息编码成一个节点序列，然后我们需要把这个节点序列映射到embedding space中。对于TAG（Text-Attributed Graph），使用现成的语言模型 $\phi$，例如SBERT，RoBERTa或SimTeG来编码文本信息，placeholder node的特征被编码为 $0$向量。然后进一步融合结构信息，每个节点在tree中的结构信息用Laplacian Embedding来表示，也就是拉普拉斯矩阵的特征向量在node id的位置来表示这个node在Tree中的结构信息，也就是相邻的节点有相似的embedding： ...

本文的目的是在预训练图上训练一组通用的图词汇表（vocabulary）作为图上可迁移的通用pattern，这些词汇表可应用于跨领域的多任务中。 GNN的可迁移性 可迁移性指的是模型从source task中提取模式，这些模式的知识可以增强对目标任务的预测。近期的工作通过识别与各种任务相关的关键子结构，来研究图上可迁移的词汇表。例如，三元闭包（triadic closure），同质性，异质性对于节点分类至关重要；一些motif，比如三角形，k-cliques，和star，是图分类的基本组成成分，这些子结构可以作为通用可迁移的pattern，基于这些子结构在不同图中的形式，或者研究图具有怎样的子结构组成，可以推断图在各种任务上的表现。 拿自然语言来类比，positive sub-vocabulary 可以是 [happy, nice, great, … ]；negative sub-vocabulary 可以是[upset, bad, worse, … ]，对于一个句子，只需要用它来检索这个词汇表，就可以对这个句子是积极或者消极做出分类。 对于Graph也是一样，构建一些通用的子结构，下游graph去检索这些子结构，基于子结构的性质来对图的性质做出推理。 计算树（computation tree）作为可迁移的graph pattern Computation Tree：对于一个图 $\mathcal{G}(\mathcal{V}, \mathcal{E})$，关于节点 $v$，它的 $L$ 层计算树为 $\mathcal{T}_v^L$，且 $\mathcal{T}_v^1 = v$。这个tree通过递归融合邻居的子树得到。对于图 $\mathcal{G}$，它的 $L$层子树的集合可以表示为一个multiset： $\mathcal{T}_{\mathcal{G}}^L:=\left\{\mathcal{T}_v^L\right\}_{v \in \mathcal{V}}$ 。 为什么计算树比其他子结构（如motif）更适合做通用的vocabulary？ 首先，节点级、边级、图级任务都可以表示为计算树的分类任务。如下图所示： 计算树可以捕获图中重要的局部子树模式。如果两个节点的 $L$层计算树相似（同时考虑节点和特征），那么表明这两个节点共享相似的邻域信息，则这两个节点具有类似现象（analogous phenomena）。 两个具有相似计算树的图，是否以为这模型在这两个图上的迁移性更好？（Yes） 两个图具有相似的其他子结构（如motif），并不一定意味着两个图之间模型的迁移性更好 Theorem 2.2： $$ \Delta \triangleq\left|\left|\phi\left(\mathcal{T}_{v_1}\right)-\phi\left(\mathcal{T}_{v_2}\right)\right|\right|_2 \leq \mathcal{C}_1 \left| \left| \mathbf{x}_{v_1}-\mathbf{x}_{v_2}\right|\right|_2+\mathcal{C}_2 \sum_{j \in \mathcal{N}(v)} \Delta_{v_1, v_2, j}^{L-1} \leq 2 \mathcal{B}_{\mathbf{x}}\left(\mathcal{C}_1+\sum_{l=1}^L \mathcal{C}_2^l D_l\right) $$ ...

GOFA是OFA（ICLR 2024）的后续工作，用来解决OFA中存在的一些问题。 OFA用NOI Prompt Node来统一不同的分类任务，也就是用不同的NOI Prompt Node来表示不同的分类任务，然后用任务的文本描述作为这些表示任务的节点的文本特征，LLM 编码来数值化这个节点的初始特征，任务对应的label也用节点（Class Node）来表示，然后用每个class的文本描述作为这个Class Node的特征。GNN的训练目标就是训练NOI Prompt node的embedding 和class node的embedding，对于某个节点，如果我们要预测它关于某个任务的标签，只需要把它和这个任务对应的NOI Prompt Node连接起来，根据输出就可以知道这个节点在该任务下的标签。 但是，OFA存在以下问题：必须是已知任务，无法泛化到新的任务，因为新的任务NOI Prompt Node 未知，也不知道新任务的Class Node是什么， 因此下游任务必须得是预训练阶段见过的任务，不能是一个全新的任务。此外，可以看出由于OFA是一个supervised foundation model，所以他和参与训练的任务标签是强相关的，很难泛化到训练阶段没有见过的任务，GOFA就是用来解决OFA存在的问题，GOFA认为foundation model的训练过程应该不能有标签信息加入的，也就是需要是自监督的。 Unified Task Formats 模型的输入必须要统一，所以和过去的很多方法一样，GOFA用TAG来统一所有graph： $$ G=\left\{V, E, X_V, X_E\right\} $$ 自监督语言模型里面，模型训练的目标叫next-token prediction 通常是补全句子，比如给定一个句子，自监督语言模型的训练目标是基于这个句子来预测生下来的tokens，假设剩下来的token是apple，参数优化的目标就是使生成apple的likelihood要最大， 如下图所示： GOFA提出的自监督图模型，也继承这种做法，模型学习的目标是补全TAG图，有个目标节点，叫node of generation，也就是自监督学习要补全的节点，把它的文本属性截断，然后自监督学习的目标就是要生成这个NOG node 的剩下内容。但是，如果要生成这个节点剩下的内容的话，不能无视这种图中的边信息，因为图的结构可以帮助这个自监督任务生成正确的信息，所以自监督图模型需要充分理解图结构。比如上图中的Target就需要在理解边关系的情况下补全句子，因此，模型需要充分学习图结构。 GOFA: Generative One-For-All Model 怎么才能在充分学习图结构的情况下，补全目标节点的text，是GOFA的主要目标。 GOFA主要由2个模块组成，一个是Graph Language Encoder，还有一个是LLM Decoder。其中Graph Language Encoder的目的是用来学习节点的表示向量， 其中交替训练了LLM compressor和GNNlayer，LLM compressor用来学习TAG graph中的语义信息，GNN用来学习结构关系信息（也就是NOG Node和其他节点的交互）。因为GNN已经可以学到图的结构信息了，LLM compressor的作用就是把文本信息压缩到GNN学习的节点表示中。 第二个模块是一个LLM decoder，它的训练目标是，基于节点的向量表示，预测下一个token。 Graph Language Encoder Graph Language Encoder 包含LLM compressors和GNN Layers。对于一个NOG Node的text attribute，若它由 $l$个tokens组成 $\{x_i\}_{i = 1}^l$，通过一个pretrained LLM 比如Mistral-7B，可以将每个token映射为一个token embedding $q(x_i)$。那么将NOG Node的所有token $\left\{q\left(x_i\right)\right\}_{i=1}^l$ pooling成一个向量可以作为NOG Node的node feature vector。但是这种做法丢失太多semantic information。 ...

Overview The following two works reduce prediction discrimination by optimizing adjacency matrices, which can improve fairness for link prediction tasks: On Dyadic Fairness: Exploring and Mitigating Bias in Graph Connections （ICLR 2021） All of the Fairness for Edge Prediction with Optimal Transport (AISTATS 2021) 通过修改原图的敏感属性，使用对比学习来实现模型对敏感属性的鲁棒性，即敏感属性的修改不会影响模型的输出: Towards a Unified Framework for Fair and Stable Graph Representation Learning (UAI 2021) 使用对抗训练策略来增强图，使得增强图与敏感属性的关系（MI）最小，基于增强图训练的representation可以实现fairness: Learning Fair Graph Representations via Automated Data Augmentations (ICLR 2023) 证明了message passing的neighbor aggregation会使得拓扑偏差积累到node representation中，在GNN的signal denoising优化框架中加入fairness regularization，使得学习到的节点表示向量要满足，不同敏感group具有相同的期望logits: ...

What is in-context learning? “In-Context Learning is a way to use LLMs to learn tasks given only a few examples. During in-context learning, we give the LM a prompt that consists of a list of input-output pairs that demonstrate how to perform a task. At the end of the prompt, we append a test input and allow the LM to make a prediction just by conditioning on the prompt and predicting the next tokens. For example, to answer the two prompts below, the model needs to examine the training examples to figure out the input distribution (financial or general news), output distribution (Positive/Negative or topic), input-output mapping (sentiment or topic classification), and the formatting. “ ...

图神经网络的预训练任务和下游任务之间可能存在较大gap，直接将预训练模型应用在下游任务上可能会产生负迁移现象（“negative transfer”）。例如，binary edge prediction经常用于pretrain graph model。这样的预训练模型使得有边连接的节点在representation space中接近。但是下游任务可能是node-level 或graph-level tasks，下游的任务如果是节点分类任务，那么预训练模型需要针对额外的节点类别标签搜索更高维度的参数空间。如果图中相连节点的类别不同（heterophilic），那么基于edge prediction pretrained的模型会对下游任务参数负面效果。 为了解决上述问题，一个潜在的方向是将“pretraining and fine-tuning”拓展为“pretraining, prompting, and fine-tuning”。例如在自然语言处理中，如果要赋予预训练语言模型预测句子情感的能力（sentiment analysis），可以通过prompt来完成，而不需要优化pretrained model。 以上图为例，对于一个fronzen LLM（参数固定），如果要为这个模型赋予情感分析的能力，我们可以额外训练一个最佳的prompt，训练数据为prompt parameters，要求这个prompt tokens在tasker $\phi$的优化下，生成的下一个token是正确的情感（label为excited）。即训练得到一个最佳的prompt tokens，比如训练得到的最佳prompt tokens是“I feel so [mask]”，使得frozen LLM应用在“KDD2023 will witness many high-quality papers. I feel so ” 这个句子上时，可以将下一个词预测为情感词，这样LLM在输入包含prompt tokens的情况下，可以具备预测句子情感的能力。也就是说， Prompt Learning的目的是训练得到一堆tokens，使得这些tokens与原来的context拼起来可以使得LLM具备新的能力。 这篇文章的目的是在图上做Prompt Learning，也就是在训练一个prompt graph，使得现有图拼上这个prompt graph后，预训练的GNN可以在新的任务上（预训练阶段没有接触过的任务上）也表现的较好。 但是在graph上做Prompt Learning存在以下挑战： 自然语言处理中，prompt tokens是一个一维线性的句子，可以放在content的开头或结尾，但是在graph中，节点是非欧结构，因此如何组织prompt tokens，以及如何将graph prompts与input graph结合是一个挑战。 在自然语言处理中，类似于情感分析，和问答任务，这些任务都可以简单的重构为next token prediction（单词预测）的任务，所以只需要使用单词预测来训练prompt就可以。但是在图中，节点级任务、边级任务和图级任务难以统一成一种形式。因此如何将各种prompt任务统一来训练graph prompt也是一个挑战。 训练好prompt token的向量化信息、连接结构、以及插入到原图的方式，然后Frozen Pretrained Model应用在这个combined graph上后，就可以为Pretrained Model赋予处理新任务的能力。 Reformulating Downstream Tasks 将节点级和边级的下游任务统一为induced graph的标签预测问题。 ...

Paper 目的：在一个图上训练好的GNN，在未知的testing graph上的结果由于training和test数据分布的不同，可能存在很大的不确定性。通常来说，in-service的GNN在已知graph with labels的图上训练好后，需要部署在label未知的testing graph上，但是由于label未知，无法估计GNN在testing graph上的效果。 如上图所示，对于一个已经在训练图 $\mathcal{S}=(\mathbf{X}, \mathbf{A}, \mathbf{Y})$上well-trained & fixed GNN model $\mathrm{GNN}_{\mathcal{S}}^\star$，并且将它deploy in service。对于一个不知道label的测试图 $\mathcal{T}$，由于不知道label，如何评估GNN在该测试图上的性能是一个挑战。由于可见的训练graph和不可见的test graph的分布差异可能很大，因此GNN评估器GNNEvaluator需要充分学习多样化的图结构with diverse node context and graph structure distributions，从而可以评估不同数据分布的测试图潜在的效果。 假设：Covariate shift between the training graph $\mathcal{S}$ and the label-unlabeled graph $\mathcal{T}$ with respect to the label space。 即无论输入图是什么样的，输出的label space相同。 如何生成数量足够的graph set来训练GNNEvaluator $f_\theta$? Solution：采样一个seed subgraph $\mathcal{S}_{seed}$ from the observed training graph $\mathcal{S}$。采样原则是seed graph 要和 training graph之间满足相同的label space，所以原图中采样可以使采样图$\mathcal{S}_{seed}$的分布尽可能少的偏离原图，从而满足Covariate shift。如下图左边所示。 在得到采样seed graph $\mathcal{S}_{seed}$后，对 $\mathcal{S}_{seed}$做 $K$次增强，其中涉及的增强包括 $\texttt{EdgeDrop}$， $\texttt{NodeDrop(Subgraph)}$， $\texttt{AttrMask}$和 $\texttt{NodeMix}$。选择哪种增强有特定的概率 $\epsilon$。基于seed graph $\mathcal{S}_{seed}$，可以得到一个 meta-graph集合 $\mathcal{G}_{\text{meta}}=\left\{g_{\text {meta }}^i\right\}_{i=1}^K$，其中的每个meta-graph都是由seed graph 扰动而来，和原图具有相同的label space。每个meta-graph $g_{\text {meta }}^i=\left\{\mathbf{X}_{\text {meta }}^i, \mathbf{A}_{\text {meta }}^i, \mathbf{Y}_{\text {meta }}^i\right\}$，分别表示meta-graph的节点特征，结构和标签。通过这种方式可以为原图生成label space相同，但结构/特征都不相同图，拓展了差异性，基于这些图学习到的GNNEvaluator可以评估不同分布图的效果。 ...

本文旨在解决不同子图作为不同的client，由于client是locally accessible，所以client间存在的missing edges无法被server捕获的情况。与FedSage仅仅基于自身连接来expand missing neighbors（并且最小化生成neighbor和其他所有子图的距离） 的missing neighbors生成方式不同，本文提出的FedPub考虑了子图的社区结构，即不同社区的子图相互之间的边连接关系应该较弱，处于同一个社区的子图应存在更强的边连接关系。 Personalized Subgraph FL (Overall) 对于每个子图 $G_i \in \mathcal{G}$，传统的方法优化方式是学习global optimal parameters $\bar{\theta}$，使得该参数在所有clients上的总loss最小： $\min_{\overline{\theta}} \sum_{G_i \subset \mathcal{G}} \mathcal{L}\left(G_i ; \overline{\theta}\right)$。但是由于处在不同社区中的子图异质性很严重，并且不同社区的子图间的edges也很稀疏，这种强异质性很难学习到一个对所有子图都最优的 $\bar{\theta}$。因此本文提出，在同一个community的子图间共享参数，不同community的子图不共享参数，而不是使用全局通用参数 $\bar{\theta}$。因此，Personalized Subgraph FL的形式如下： $$ \begin{aligned} & \min_{\left\{\boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right\}_{i=1}^K} \sum_{G_i \subseteq \mathcal{G}} \mathcal{L}\left(G_i ; \boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right), \quad \boldsymbol{\theta}_i \leftarrow \boldsymbol{\mu}_i \odot\left(\sum_{j=1}^K \alpha_{i j} \boldsymbol{\theta}_j\right) \\ & \text { with } \alpha_{i k} \gg \alpha_{i l} \text { for } G_k \subseteq C \text { and } G_l \nsubseteq C \end{aligned} $$ 其中 $K$是client数量， $\theta_i$是属于community $C$ 的client $G_i$的可训练权重， $\alpha_{ij}$是client $i$ 和 $j$的权重聚合coefficient。如果client $k$和 $i$属于同一个community，而client $l$和 $i$不属于同一个community，那么它们关于 $i$的参数聚合系数 $\alpha_{i k} \gg \alpha_{i l}$。通过这种方式模型可以隐式地考虑不同subgraph之间的关系。 ...

Introduction Subgraph Federated Learning旨在多个分布式的子图上训练一个图模型，并且子图之间没有数据共享。面临2个挑战： Q1: 如何将各个子图上的模型融合成一个全局可用的模型，使其可以处理来自全局图的任何请求？ A1: 针对该挑战，本文提出FedSage将GraphSage和FedAvg结合。 Q2: 如何处理local subgraph之间缺失的边？ A2: 在FedSage的基础上添加一个邻居生成器。具体来说，为了得到missing neighbor generator，每个client首先通过随机移除一些节点和他们的边来损坏subgraph，然后基于损坏的图来和移除的节点来训练邻居生成器。邻居生成器不仅为子图中的每个节点生成missing neighbor number，也为每个节点生产missing neighbor features。然后用生成的节点邻居去修补subgraph，所谓模拟的跨子图交互。最后在修补好的子图上使用FedSage。 Collaborative Learning on Isolated Subgraphs：FedSage 对于一个被查询节点 $v\in V$，一个全局 $K$层GraphSage分类器 $F$通过融合 $v$和它的 $K$跳邻居来得到节点的预测值，其中每层的可学习参数为 $\phi = \{\phi^k\}^K_{k = 1}$，其中 $\phi^k$表示第 $k$层的权重矩阵。考虑一个子图 $G_i = \{V_i, E_i, X_i\}$， GraphSage通过一下式子计算节点 $v \in V_i$的第 $k \in [K]$层表示： $$ h_v^k=\sigma\left(\phi^k \cdot\left(h_v^{k-1} || \operatorname{Agg}\left(\left\{h_u^{k-1}, \forall u \in \mathcal{N}_{G_i}(v)\right\}\right)\right)\right) $$ 其中 $\mathcal{N}_{G_i}(v)$表示节点 $v$在子图 $G_i$中的邻居，上式表示邻居节点聚合后和中心节点拼接，然后再用参数 $\phi^k$做变换后得到中心节点的表示。 在FedSage中，全局模型 $F$的参数 $\phi$通过 $e_c$次训练迭代得到。在每次训练迭代 $t$中，每个client $D_i$首先拷贝全局参数 $\phi$到本地，作为本地模型的初始参数，再基于自身的数据更新参数 $\phi_i$： ...