介绍

[!info] 这个是结合李沐和相关博客介绍整理，刚接触GNN

A Gentle Introduction to Graph Neural Networks

什么是图

表示实体(节点)集合之间的关系(边)

图里面可以嵌入信息，比如标量或向量

数据怎么表示成图

图像

把每个像素当成一个点，这样一个$224 \times 224$的图像就会变成一个$224 \times 224$的图上的每个点，周围的邻域就是每个点的邻居，绘制成邻接矩阵如下，发现会非常稀疏。

文本

我们可以通过将索引与每个字符、单词或标记相关联，并将文本表示为这些索引的序列来对文本进行重新排序。这创建了一个简单的有向图，其中每个字符或索引都是一个节点，并通过边连接到它后面的节点。

这只是粗略地表示，因为这样的话邻接矩阵只有两条对角线有值

分子

社交网络

图上问题

图层面

eg. 识别两个环
图的分类

顶点

节点标签预测

边

边缘级推理的一个示例是图像场景理解。除了识别图像中的对象之外，深度学习模型还可以用于预测它们之间的关系。我们可以将其称为边级分类：给定代表图像中对象的节点，我们希望预测这些节点中的哪些节点共享边或边的值是什么。如果我们希望发现实体之间的连接，我们可以认为图是完全连接的，并根据它们的预测值修剪边以获得稀疏图。

机器学习应用到图上

机器学习模型通常采用矩形或网格状阵列作为输入。因此，如何以与深度学习兼容的格式表示它们并不直观。图有多达四种类型的信息，我们可能希望使用它们来进行预测：节点、边、全局上下文和连通性。前三个相对简单：例如，对于节点，我们可以通过为每个节点分配索引 $i$ 并将 $node_i$ 的特征存储在 $N$ 中来形成节点特征矩阵 $N$ 。虽然这些矩阵具有可变数量的示例，但它们可以在没有任何特殊技术的情况下进行处理。

然而，表示图的连通性更复杂。也许最明显的选择是使用邻接矩阵，因为它很容易张量化。然而，这种表示有一些缺点。从示例数据集表中，我们可以看到图中的节点数量可以达到数百万，并且每个节点的边数可以高度可变。通常，这会导致非常稀疏的邻接矩阵，这是空间效率低下的。

另一个问题是，有许多邻接矩阵可以编码相同的连接性，并且不能保证这些不同的矩阵在深度神经网络中会产生相同的结果（也就是说，它们不是置换不变的）。
eg. 四个顶点互相连接，但是可以有多种不一样的图进行表示：

表示稀疏矩阵的一种优雅且节省内存的方法是邻接列表。这些将节点 $n_i$ 和 $n_j$ 之间的边 $e_k$ 的连通性描述为邻接列表的第k个条目中的元组（i，j）。由于我们期望边的数量远低于邻接矩阵的条目数量（ $n_{nodes}^2$ ），因此我们避免了对图的不连通部分的计算和存储。

使用邻接表来存储信息，两个数字表示两个点的连接，这样就可以做到对各种结果的适配

应该注意的是，图中使用每个节点/边/全局的标量值，但大多数实际的张量表示都有每个图属性的向量。我们将处理大小为 $[n_{nodes},node_{dim}]$ 的节点张量，而不是大小为 $[n_{nodes}]$ 的节点张量。其他图形属性也是如此。

图神经网络

既然图的描述是以矩阵格式的，它是置换不变的，我们将描述使用图神经网络（GNN）来解决图预测任务。GNN是对图的所有属性（节点、边、全局上下文）的可优化变换，其保持图的对称性（置换不变性）。我们将使用Gilmer等人提出的“消息传递神经网络”框架来构建GNN。

GNN采用“graph-in，graph-out”架构，这意味着这些模型类型接受图作为输入，将信息加载到其节点，边缘和全局上下文中，并逐步转换这些嵌入，而不改变输入图的连接性。

最简单的GNN

该GNN在图的每个组件(顶点、边、全局)上使用单独的多层感知器(MLP);我们称之为GNN层。对于每个节点向量，我们应用MLP并返回学习的节点向量。我们对每条边做同样的事情，学习每边嵌入，也对全局上下文向量做同样的事情，学习整个图的单个嵌入

由于是分别进行MLP，因此得到的是没有改变结构的结构，且由于没有考虑连接信息，因此不会改变结果。
由于GNN不会更新输入图的连通性，因此我们可以使用与输入图相同的邻接列表和相同数量的特征向量来描述GNN的输出图。但是，输出图已经更新了嵌入，因为GNN已经更新了每个节点，边缘和全局上下文表示。

怎么做预测

我们将考虑二元分类的情况，但这个框架可以很容易地扩展到多类或回归的情况。如果任务是对节点进行二进制预测，并且图已经包含节点信息，则方法很简单-对于每个节点嵌入，应用线性分类器，即在最后添加一个输出维度为2的全连接层，再过softmax得到输出。

然而，它并不总是那么简单。例如，您可能在图中的边中存储了信息，但在节点中没有信息，但仍然需要对节点进行预测。我们需要一种方法来从边缘收集信息，并将其提供给节点进行预测。我们可以通过合并来实现这一点。池化($\rho$)分为两个步骤：

1. 对于要合并的每个项，收集它们的每个嵌入并将它们连接到一个矩阵中。
2. 然后聚合收集的嵌入，通常通过求和操作。

把连边的向量都加起来，得到对应顶点的信息向量

如果我们只有节点级特征，并且试图预测二进制边缘级信息，模型看起来像这样，同样可以通过点得到边

有顶点但没有全局，那么把所有点加起来，再过全连接层：

最终流程：

但在这里还没有用到图的连通性信息

传递信息

把该点向量和该点邻居的两个顶点的向量都加在一起得到汇聚的向量，然后再更新

对于每个节点，收集其所有邻居的向量，然后求和后过MLP进行更新

有点像做卷积，但是没有加权

学习边表示

我们的数据集并不总是包含所有类型的信息（节点、边和全局上下文）。当我们想要对节点进行预测，但我们的数据集只有边信息时，我们在上面展示了如何使用池将信息从边路由到节点，但仅在模型的最后预测步骤。我们可以使用消息传递在GNN层内的节点和边之间共享信息。

我们可以采用与之前使用相邻节点信息相同的方式合并来自相邻边缘的信息，方法是首先汇集边缘信息，使用更新函数对其进行转换并存储。

但是，存储在图中的节点和边信息不一定是相同的大小或形状，因此不能立即清楚如何将它们组合。一种方法是学习从边空间到节点空间的线性映射，反之亦然。或者，可以在更新函数之前将它们连接在一起。

反过来也可以，两种方法导致不一样的结果

也可以结合两边的信息

全局信息

到目前为止，我们所描述的网络有一个缺陷：即使我们多次应用消息传递，图中彼此远离的节点也可能永远无法有效地相互传输信息。对于一个节点，如果我们有k层，信息将传播最多k步。对于预测任务依赖于相距较远的节点或节点组的情况，这可能是一个问题。一个解决方案是让所有节点都能够相互传递信息。不幸的是，对于大型图，这很快就变得计算昂贵（尽管这种称为“虚拟边”的方法已用于分子等小型图）

解决方法是加入一个master node/全局上下文向量$U$。这个全局上下文向量连接到网络中的所有其他节点和边，并且可以充当它们之间传递信息的桥梁，从而构建整个图的表示。这就创建了一个比其他方式更丰富、更复杂的图形表示。

因此汇聚的时候会汇聚U，更新的时候也会把U更新

在这个视图中，所有的图属性都已经学习了表示，所以我们可以在池化过程中通过调整我们感兴趣的属性相对于其他属性的信息来利用它们。例如，对于一个节点，我们可以考虑来自相邻节点的信息，连接的边缘和全局信息。为了在所有这些可能的信息源上嵌入新的节点，我们可以简单地将它们连接起来。此外，我们还可以通过线性映射将它们映射到相同的空间，并添加它们或应用特征调制层

Into the Weeds

其他图

虽然我们只描述了具有每个属性的矢量化信息的图，但图结构更灵活，可以容纳其他类型的信息。幸运的是，消息传递框架足够灵活，通常使GNN适应更复杂的图结构是关于定义如何通过新的图属性传递和更新信息。

我们可以考虑多边图或多重图，其中一对节点可以共享多种类型的边，当我们希望根据节点的类型对节点之间的交互进行不同建模时，就会发生这种情况。例如，对于社交网络，我们可以根据关系类型（熟人，朋友，家人）指定边类型。GNN可以通过针对每个边类型具有不同类型的消息传递步骤来适配。我们还可以考虑嵌套图，其中例如节点表示图，也称为超节点图。

嵌套图对于表示层次信息很有用。例如，我们可以考虑一个分子网络，其中一个节点代表一个分子，如果我们有一种方法（反应）将一个分子转化为另一个分子，则两个分子之间共享一条边.在这种情况下，我们可以在嵌套图上学习，方法是让一个GNN在分子水平上学习表示，另一个在反应网络水平上学习表示，并在训练过程中交替进行。

另一种类型的图是超图，其中一条边可以连接到多个节点，而不仅仅是两个节点。对于一个给定的图，我们可以通过识别节点的社区并分配一个连接到社区中所有节点的超边来构建超图。

图采样与批处理

训练神经网络的一个常见做法是使用在训练数据（小批量）的随机化恒定大小（批量大小）子集上计算的梯度来更新网络参数。
这种做法对图提出了挑战，因为相邻节点和边的数量可变，这意味着我们不能有一个恒定的批量大小。并且计算量太大，存不下所有中间值。
因此需要通过对原图进行采样来创建子图，子图保留了较大图的基本属性。这种图形采样操作高度依赖于上下文，并且涉及从图形中选择节点和边。这些操作在某些情况下可能是有意义的（引用网络），而在其他情况下，这些操作可能太强（分子，其中子图只是代表一个新的，更小的分子）。如何对图进行采样是一个开放的研究问题。

• 随机采样点+它的邻居
• 随机游走+步数
• 随机游走+邻居
• 取一个点，然后做BFS

归纳偏差

在图的情况下，我们关心每个图组件（边，节点，全局）如何相互关联，因此我们寻求具有关系归纳偏差的模型。模型应该保持实体之间的显式关系（邻接矩阵），并保持图形对称性（置换不变性）。我们希望实体之间的交互很重要的问题将受益于图结构。具体地说，这意味着在集合上设计变换：节点或边上的操作顺序不应该有关系，操作应该在可变数量的输入上工作。

比较聚合操作

没有一种操作是一致的最佳选择。当节点具有高度可变的邻居数量时，或者您需要局部邻居的特征的归一化视图时，均值运算可能很有用。当您想要突出显示局部邻域中的单个显著特征时，max操作非常有用。Sum通过提供特征的局部分布的快照，在这两者之间提供了平衡，但由于它没有归一化，也可以突出离群值。在实践中，通常使用sum。

GCN可以认为是子图的近似

GCN收集所有可能的大小为k的子图，并从一个节点或边的Vantage位置学习向量表示。可能的子图的数量可以组合地增长，因此从一开始就枚举这些子图，而不是像在GCN中那样动态地构建它们，可能会受到限制。

在机器学习领域，训练和测试数据共享相同分布的假设在现实场景中经常被违反，这需要有效的分布外(OOD)检测。本文提出了一种新的OOD检测方法，该方法利用KolmogorovArnold网络(KANs)独特的局部神经可塑性。与传统的多层感知器不同，KANs具有局部可塑性，允许它们在适应新任务的同时保留所学信息。我们的方法比较了经过训练的KAN与未经训练的KAN的激活模式来检测OOD样本。我们在图像和医学领域的基准测试中验证了我们的方法，与最先进的技术相比，展示了卓越的表现和鲁棒性。这些结果强调了KANs在提高不同环境下机器学习系统可靠性方面的潜力。

属于后处理方法，基于距离 #post-hoc

在OpenOOD benchmark上进行的实验：
alessandro-canevaro/KAN-OOD: Offical implementation of ICLR2025 paper Advancing Out-of-Distribution Detection via Local Neuroplasticity

ADVANCING OUT-OF-DISTRIBUTION DETECTION VIA LOCAL NEUROPLASTICITY
ICLR 2025

Introduction

大多数机器学习算法基于训练和测试数据共享相同分布，但是当遇到分布外的场景时这个假设会失效，影响模型准确性和可靠性。

KAN由于其基于样条的结构而表现出局部可塑性。这一特性确保了学习新任务只影响由训练数据激活的网络区域，从而保持了遥远和不相关区域的完整性。

如图1所示，我们的方法比较了两个相同初始化的KANs的激活模式:一个在分布内(InD)数据上训练，另一个未训练。OOD样本将主要触发已训练网络中未在学习阶段适应的区域，因此样本将产生更接近未训练网络的响应。

我的理解：上图看到OOD的结果比较平均，但ID的反应波动比较大

检测器将训练后的KAN模型与未训练的KAN模型的激活函数响应进行比较。差异较大的反应表明样品是InD，相似的反应表明样品是OOD。

KAN based OOD detection

Background

KAN是基于Kolmogorov-Arnold表示定理的神经网络架构。这个定理说明任何连续多元函数都可以表示为单个变量的连续函数的和。因此，KANs使用更简单的单变量组件近似高维函数，有效地解决了机器学习中的维度诅咒。

在实践中，KAN将多元函数分解为具有可学习系数的单变量b样条函数。设$x_{p}$为输入向量$\mathbf{x}∈R^{n_{in}}$的第p个分量(特征)，设$y_q$为输出向量$\mathbf{y}∈R^{n_{out}}$的第q个分量(特征)。KAN层使用单变量函数的矩阵$Φ = {p,q}$将$\mathbf{x}$转换为$\mathbf{y}$，其中每个p,q都由b样条参数化。每个b样条由$G + k$个具有可学习系数$c_{p,q,i}$的b样条基函数的线性组合组成。样条阶表示为$k$(通常为k = 3)，$G$为网格大小。
$$
y_{q} = \sum_{p}^{}\phi_{p,q}(x_{p}) \quad \text{with} \quad \phi_{p,q}(x_{p}) = \sum_{i=0}^{G+k}c_{p,q,i}B_{i}(x_{p})
$$
KAN层可以堆叠以构建更深的网络，允许跨多个阶段的复杂转换。残差连接通过可训练的权值和附加基函数为样条函数增加了灵活性，从而进一步提高了表现

KAN的局部神经可塑性由两个关键特性促进。首先，每个输入特征$x_{p}$都由它自己的激活函数${ϕ_{p,q} |∀q}$独立处理。其次，在反向传播期间，只有样本$x_p$附近的样条系数被修改，而激活函数的其他区域基本不变。

OOD + KAN

我们建议利用KAN的局部可塑性进行OOD检测。在训练期间看到的InD数据只影响网络的特定区域(样条网格系数)。通过确定一个区域是否包含InD数据并检查每个样本激活的区域，基于KAN的检测器可以区分InD和OOD样本。这种区分是通过比较训练后的激活函数的输出与训练前的值来实现的。步骤如下:

• 初始化：创造两个KAN，用ID数据集训练其中一个，另一个不训练
• 检测：
  • 使用给定的样本x在两个网络上执行前向传递，并保存激活函数的输出$\phi_{p,q}^{trained}(x_{p}), \phi_{p,q}^{untrained}(x_{p}), \forall p,q$
  • 计算二者的差距
    $$\Delta_{p,q}(x_{p}) = |phi_{p,q}^{trained}(x_{p}),-\phi_{p,q}^{untrained}(x_{p})| = \sum_{i} |c_{p,q,i}^{trained} - c_{p,q,i}^{untrained}| \cdot B_{i}(x_{p})$$
    其中，$|c_{p,q,i}^{trained} - c_{p,q,i}^{untrained}|$ 定义了网络中存储InD信息的位置，而 $B_{i}(x_{p})$ 作为掩码，制定了有样本$\mathbf{x}$激活的区域。因此将这两项相乘，提供了InD区域与给定样本之间重叠的定量度量。
  • 分析差异矩阵 $\Delta$，OOD样本趋向于在$∆$矩阵中有较高比例的条目接近于零，因此$S(\mathbf{x})$分数对应低
    $$
    S(\mathbf{x}) = F_{score}(\Delta(\mathbf{x}))
    $$

图2使用Liu等人(2024b)提出的玩具样例的修改版本说明了所提出算法的工作原理。该数据集是一个具有五个高斯峰的一维回归任务。我们使用其中的两个峰作为训练集和InD测试集，其余三个峰作为OOD测试集。这里的KAN模型由一个单层的一个输入和一个输出组成，即单个单变量函数$φ$具有200个样条系数。

(a)训练数据集的可视化，显示输入和目标之间的关系。
(b)未经训练的KAN模型在整个输入范围内的响应。
(c)经过训练的KAN模型在整个输入范围内的响应。
(d)说明输入与目标的测试数据集，通过将训练数据集(InD)与剩余输入范围(OOD)上的三个附加高斯峰相结合而创建。
(e) InD score $S(\mathbf{x})\quad ∀\mathbf{x}∈[−1,1]$，使用中位数作为评分函数(Fscore)。
(f)对InD评分施加阈值(λ = 1e−3)后的最终结果:蓝色区域表示预测InD区域，红色区域表示预测OOD区域。

捕捉联合特征分布

类似集成模型的思路

与mlp一样，KAN能够处理多变量输入并产生多变量输出。然而，与mlp中激活函数接收所有输入的加权和不同的是，在KANs中，每个激活函数只接收单个输入。虽然这种特性使KAN检测器能够有效地捕获输入特征的边缘分布，但它也限制了其对特征联合分布建模的能力。

为了克服这一限制，我们建议对InD数据集进行分区，并为每个分区训练单独的KAN模型。这样，复杂的训练分布被分解成更小的部分，仅使用边缘特征分布就可以准确地描述这些部分。可以使用各种技术对数据集进行分区。一种简单而有效的方法是根据类标签拆分数据集。另一种方法是应用k-means这样的聚类算法(Lloyd, 1982)，这种方法在没有类标签的情况下也有效，例如在回归任务中。

在形式上，数据集D被划分为P个不重叠的子集$D_1,D_2,\dots, D_p$。对于每个分区$D_i$，我们训练一个单独的检测器，记作$KAN_i$。虽然每个$KAN_i$的分区$D_i$不同，但训练任务总是相同的(例如，分类)。在推理过程中，我们通过汇总每个KAN模型的InD得分来计算样本$\mathbf{x}$的InD得分。令$∆^i(\mathbf{x})$为$KAN_i$的差分矩阵:
$$
S(\mathbf{x}) = F_{agg} (F_{score}(\Delta^1(\mathbf{x})), \dots, F_{score}(\Delta^P(\mathbf{x})),)
$$
$F_{agg}$ 是一个合适的聚合函数，如最大值函数。由于分区是不重叠的，对于InD样本，将**只有一个模型将样本识别为InD(高InD分数)**，而其余的模型均将其标记为OOD(低InD分数)。

实验

对于图像中的OOD检测，实验设置遵循OpenOOD (Yang et al.， 2022)基准协议。

考虑的OpenOOD基准使用预训练的ResNet骨干(He等人，2015)进行特征提取
我们利用预先训练的骨干的多个潜在层的信息。如Liu等人(2024a)所示，这种多层集成丰富了特征表示，从而提高了检测精度。具体来说，作者声称最后一层主要包含语义信息，而包括更靠近输入的层允许检测器捕获协变量信息。

结果

仍然使用常用的CIFAR-10和CIFAR-100作为训练ID样本，这里报告的是AUROC，附录中有FPR95的结果，但效果上没有太大区别