💟 My Notebook 🌻

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$： ...

1. Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning (TAPE) Shallow model: Encoding the textual attributes using shallow or hand-crafted features such as skip-gram or bag-of-words (BoW) which used in PgG and DGL are limited in the complexity of the semantic features they can capture. LM: 指相对较小并且可以被fine-tune的模型。GIANT fine-tune an LM using neighborhood prediction task （在neighborhood prediction task上来微调LM模型）. GLEM fine-tune an LM to predict the label distribution from GNN’s output (GLEM 用GNN预测的伪标签作为监督信号，让LM来fine tune 节点的文本表示)。这些工作需要大量的计算资源，并且由于要微调模型的参数，所以选取的LM相对较小，比如BERT和DeBERTa，因此缺乏LLM的推理能力。 ...

paper Introduction 多层message passing后，GNN会导致Over-smoothing使得节点表示趋同。另一方面，标签不同的相邻节点特征会混合，导致不同标签节点边的难以区分，即Heterophily问题。在本文中，提出对传递到节点的message进行排序，即表示向量的特定neuron块编码特定hop的消息。通过将节点rooted computation tree的层次和表示向量neuron 块对齐。如下图所示，3层GNN对节点$v$的输出$h_v^{(3)}$的前$P_v^{(0)}$个neurons 编码1 hop邻居信息，$[P_v^{(0)}, P_v^{(1)}]$编码了第1层另据的信息。通过以确定的顺序编码邻居信息，来避免hops的特征融合，即一个节点的embedding的神经元要和计算书的层次对齐，不同层分配不同的neuron。也就是按照顺序将不同层的邻居信息编码到最终表示$h_v^{(k)}$的不同维度区间中。 Approach Aligning Rooted-Tree with Node Embedding 对于一个节点$v$，显然它的第$k-1$层rooted-tree $\mathcal{T}^{(k-1)}_v$是$k$层rooted-tree $\mathcal{T}^{(k)}_v$的子树: $$ \mathcal{T}_v^{(0)} \subseteq \mathcal{T}_v^{(1)} \subseteq \cdots \subseteq \mathcal{T}_v^{(k)} \subseteq \cdots \subseteq \mathcal{T}_v^{(K)} $$ 随着$k$的增加，$\mathcal{T}_v^{(K)}$会变得越来越大且复杂，且包含之前层的所有信息。所以$\mathcal{T}_v^{(K)}$需要更多neuron (最终表示向量$h_v^{(k)}$中的维度) 来编码信息。由于$\mathcal{T}_v^{(k-1)}$是$\mathcal{T}_v^{(k)}$的子树，所以在表示向量$h_v^{(k)}$中，编码tree $\mathcal{T}_v^{(k)}$信息的neurons要包含编码 tree$\mathcal{T}_v^{(k-1)}$信息的neurons。具体来说，关于节点$v$的$k-1$层rooted-tree $\mathcal{T}_v^{(k-1)}$，它的信息会被编码到$h_v^{(K)}$的前$P_v^{(k-1)}$个neuron中（维度），对于下一个层次的rooted-tree $\mathcal{T}_v^{(k)}$，它会被编码到$h_v^{(K)}$的前$P_v^{(k)}$个neuron（维度）中。因为$\mathcal{T}_v^{(k-1)}$是$\mathcal{T}_v^{(k)}$的子树，所以$P_v^{(k-1)} \leq P_v^{(k)}$。 $v$的$K$层最终表示$h_v^{(K)}$，它的每个维度是一个neuron，前$P_v^{(k-1)}$个neurons编码了前$k-1$ hop邻居的信息，前$P_v^{(k)}$个neurons编码了前$k$ hop邻居的信息， 在两个分割点$P_v^{(k-1)}$和$P_v^{(k)}$之间的neurons要编码的是第$k$ hop邻居的信息。所以节点$v$在$K$层GNN下的最终embedding$h_v^{(K)} \in \mathbb{R}^D$ 会被$K+1$个分割点分成$K+1$块，其中前$P_v^{(0)}$个neurons编码的是节点$v$的自身信息，$P_v^{(k)}$为$h_v^{(K)}$的split point，且： $$ P_v^{(0)} \leq P_v^{(1)} \leq \cdots \leq P_v^{(k)} \leq \cdots \leq P_v^{(K)} = D $$ The Split Point 分割点$P_v^{(k)}$是一个index，会将$D$维node embedding 分为2块，$[0, P_v^{(k)}-1]$的neurons编码了前$k$层邻居的信息。 定义一个$D$维gating向量$g^{(k)}_v = [1,1,1,1,1,1,0,0,0,0,0]$其中前$P_v^{(k)}$个entries是1， 后面为0，即筛选出前$k$层要编码进的neurons： $$ h_v^{(k)}=g_v^{(k)} \circ h_v^{(k-1)}+\left(1-g_v^{(k)}\right) \circ m_v^{(k)} $$ 其中第$k$层的信息$h_v^{(k-1)}$保留在第$k+1$层embedding $h_v^{(k)}$的前$P_v^{(k)}$个neuron中，而$h_v^{(k)}$的后面部分neuron编码新聚合的邻居信息，通过这种方式，将每一个hop的信息分开。 再下一层时， $h_v^{(k)}$的信息就会被编码到$D$个neurons中的前$P_v^{(k+1)}$个neuron中，那么其实$P_v^{(k)}$到$P_v^{(k+1)}$之间的neuron实际上只包含了$m_v^{(k)}$的信息，即第$k$个hop的信息。以这种方式将每一个hop的邻居信息按顺序编码到最终表示向量$h_v^{(K)}$中。 ...

paper GNN中的层次叠加需要稀疏矩阵乘法计算带来较大的计算开销，而MLP仅使用node feature可以避免此问题。本文发现大多数message-passing通过将训练参数设置为相同shape，可以推导出等效的MLP（PeerMLP），而使用PeerMLP来作为GNN的初始化参数可以相较于仅使用PeerMLP，效果提升极大。 从上图的蓝线可以看出，GNN通常需要更多的训练迭代次数才可以达到收敛，因为其中涉及复杂的稀疏矩阵乘法计算。而MLP不使用结构信息，训练速度更快，因此本文发现MLP和GNN可以有相同的训练权重空间，因此 Can we train GNNs more efficiently by leveraging the weights ofconverged MLPs? 本文进一步发现，对于一个GNN和它对应的PeerMLP （相同的weight），在PeerMLP上训练的权重可以优化GNN。基于该发现，图上训练好的PeerMLP作为GNN的权重矩阵$W$, 然后再考虑结构信息，可以发现GNN的效果相较于PeerMLP有很大的提升。 如表2所示，其中PeerMLP和GNN有相同的权重空间，首先在图上训练PeerMLP，得到收敛时的最有参数$w^\star_{mlp}$，PeerMLP的预测结果为$f_{m l p}\left(\mathbf{X} ; w_{m l p}^\star\right)$， 然后直接使用不训练而直接使用$w_{m l p}^\star$作为GNN的参数，即$f_{g n n}\left(\mathbf{X}, \mathbf{A} ; w_{m l p}^\star\right)$,可以看出，在考虑图结构后，GNN即使不训练，直接使用PeerMLP的权重矩阵，效果也有巨大提升。 受此启发，本文提出了用收敛的PeerMLP最优权重矩阵，作为GNN的初始化权重。从图1的红线可以看出，相较于随机初始化的GNN，MLPInit初始化的GNN在更少的epoch到达收敛 并且可以达到和相似的准确率。 从上表可以看出GNN的Propagation操作$AZ$的前向计算和反向梯度传播的耗时都远远超过Feature Transformation操作$WX$。Feature Tran的操作相对与Propagation，计算成本几乎可以忽略不计，所以如果预训练操作得到的$W$可以使得训练GNN时的epoch大幅下降，可以使模型更加高效。如下表所示，训练PeerMLP的时间再加上的权重迁移到GNN后的fine-tuning时间， 远少于在GNN上直接训练随机初始化参数的时间。 从下图同样可以看出PeerMLP的参数$w_{mlp}$的训练趋势，PeerMLP训练过程中每个epoch的$w_{mlp}$直接迁移到GNN上计算CE损失，可以发现使得MLP 的CE Loss下降的$w_{mlp}$同样可以使得GNN以同样的趋势下降。

1. Label Information Enhanced Fraud Detection against Low Homophily in Graphs (WWW ‘23) Introduction GNN4FD存在问题： 大多数基于GNN的欺诈检测器难以泛化到low homophily网络中，除此之外，如何充分利用label信息也是Fraud detection的重要因素。即如果一个Fraud node的邻居都是benign nodes，那么这样的图就是heterophily or low homophily graph，由于GNN的neighborhood aggregation机制，target node的表示会和它的邻居相似，无论他们的label是否不同，这样会使得GNN难以区分位于异质邻域内的Fraud nodes。另外， 现有的GNN4FD方法利用label信息的能力有限，这些方法仅在训练阶段使用label信息作为监督信号，但是在设计message passing 机制的过程中并没有使用label信息。 为了解决上述2个挑战，本文提出GAGA: 基于分组聚合的Transformer。 GAGA首先提出了一种预处理策略Group Aggregation (GA, 分组聚合)，然后每个节点的原始邻居特特征被分组为序列数据。 然后提出一种科学系的编码方式来编码structural，relational 和label信息 （全局），即整个图的relational encoding，group encoding 和 hop encoding （图中又几个relation就有几个relational embedding，取几个hop就又几个hop embedding..）。 最后用多头attention为每个节点聚合embedding sequence. Preliminaries Multi-relational fraud graph construction Multi-relational fraud graph $\mathcal{G}(\mathcal{V}, \mathcal{E}, \mathcal{X}, \mathcal{Y})$, 其中节点集$\mathcal{V}=\left\{v_1, v_2, \ldots, v_N\right\}(N=|\mathcal{V}|)$，$R$ 个邻接矩阵$\mathcal{E}=\left\{\mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_R\right\}(R=|\mathcal{E}|)$的多关系图 （$R$个关系）。节点feature vectors $X=\left\{\mathbf{x}_1, \mathrm{x}_2, \ldots, \mathrm{x}_N\right\}$以及节点的label集合$\mathcal{Y}$。 对于一个relation的邻接矩阵$\mathbf{A}_r$，如果$\mathbf{A}_1[u,v]=1$，那么在关系$r$下节点$u$和$v$被连接。每个节点$v \in \mathcal{V}$ 有一个$d$维feature vector $\mathbf{x}_v \in \mathbb{R}^d$。 在基于Graph的fraud detection中，我们考虑半监督场景，其中一小部分节点 $\hat{\mathcal{V}} \supset \mathcal{V}$是有label的 （$y=1$表示该节点为fraud node，$y=0$表示该节点为benign node）所以对于fraud graph，节点class数为2。 ...