1. 项目概述与核心价值在机器学习领域我们常常会遇到一类“不讲道理”的数据它们没有固定的顺序也没有一个绝对的朝向。想象一下你面前有一堆散落的乐高积木无论你怎么旋转它们或者打乱它们的摆放顺序它们拼出来的城堡还是那个城堡。对于计算机来说理解这种“无论怎么变换本质不变”的特性是一个巨大的挑战。这类数据无处不在在化学中一个分子无论其原子如何编号它的性质是固定的在天文学中一个星团无论从哪个角度观测其物理本质不变在计算机图形学中一个三维物体无论如何旋转和平移它仍然是同一个物体。处理这类数据的关键就在于不变性。不变性简而言之就是模型的输出不因输入数据的某种对称变换比如打乱顺序、旋转、镜像而改变。这听起来像是模型应该具备的基本素养但实现起来却暗藏玄机。传统的方法如图神经网络中的消息传递机制确实保证了置换不变性但它们往往在表达能力上有所妥协难以捕捉全局的、复杂的图结构属性。另一方面一些理论上具有“通用逼近”能力的模型又因为计算复杂度爆炸比如需要处理O(n^d)量级的张量而无法应用于大规模数据。这就形成了一个两难困境要么模型高效但表达能力有限要么模型强大但计算上不可行。我们今天要深入探讨的这项工作正是试图在这个困境中劈开一条新路。它源自一篇题为《A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features》的研究。其核心思想非常巧妙我们不一定非要追求在所有可能的数据上都完美无缺的“最坏情况”保证。相反如果我们愿意接受在一个测度为零的“坏”集合上可能失效那么就能以与输入数据规模同阶的计算成本构造出在“几乎所有”数据上都有效的轻量级不变特征。具体来说对于n个节点的加权图用对称矩阵表示该方法能构造O(n²)个不变特征对于固定维度d中的n个点组成的点云这个数量可以进一步降至O(n)。这背后的数学工具灵感来自于伽罗瓦理论——一个通常出现在抽象代数课本里研究域扩张对称性的理论。研究者们将其精髓提炼出来用于系统地构造这些“几乎处处”分离不同数据轨道的特征。这项工作的价值是立体的。在理论上它建立了一个连接经典不变性理论与现代机器学习需求的桥梁提供了一种松弛但实用的“通用逼近”新视角。在工程上它给出的特征构造方法计算高效复杂度与数据本身的大小相当使得处理超大规模点云例如天文学中数十亿个星体的数据成为可能。在应用上它可以直接用于分子性质预测、点云相似性比较等任务为科学计算领域提供了新的工具。接下来我们将层层剥开这个方法的数学内核与实现细节。2. 核心数学原理从伽罗瓦理论到不变特征要理解这个方法为何有效我们需要暂时走进抽象的数学世界。不用担心我会用尽可能直观的方式来解释。2.1 问题形式化我们到底在对付什么首先我们面对两种核心的数据结构及其对称性对称矩阵与置换群一个n×n的实对称矩阵X可以代表一个具有n个节点的加权无向图对角线是节点权重非对角线是边权重。这个矩阵的表示依赖于节点的编号顺序。如果我们打乱节点的编号即施加一个置换π对应的矩阵会变为PπXPπᵀ其中Pπ是置换矩阵。所有通过这种置换相互关联的矩阵都属于同一个图。因此我们真正关心的函数f(X)应该满足f(X) f(PπXPπᵀ)对所有置换π成立。这就是置换不变性。点云与正交群一个d×n的矩阵V代表d维空间中的n个点每列是一个点。我们关心的是点云本身的几何形状而不是它在空间中的具体摆放旋转、反射或点的标签顺序。因此一个函数g(V)如果同时满足g(V) g(UV)U是任意d×d正交矩阵代表旋转/反射和g(V) g(VPπᵀ)置换点的顺序那么它就是正交-置换不变的。一个关键的观察是对于点云V其格拉姆矩阵X VᵀV是一个n×n的对称半正定矩阵。并且一个函数g(V)是正交-置换不变的当且仅当存在一个置换不变的函数f使得g(V) f(VᵀV)。这就把点云的问题转化为了对称矩阵的问题但增加了一个约束X的秩最多为d因为来自d维空间中的点。所以问题的核心归结为如何为对称矩阵空间S(n)在点云情形下是秩≤d的半正定矩阵子集构造一组数量可控、易于计算的不变特征使得它们能“分离”几乎所有的轨道这里的“分离”是指对于两个不在“坏集合”中的矩阵X和Y如果它们不属于同一个置换轨道那么至少有一个特征值在这两个矩阵上不同。2.2 伽罗瓦理论的启示从大群到子群经典的不变理论致力于寻找生成所有不变多项式的基集但这对于置换群作用在对称矩阵上的情况来说已知是计算上难解的因为它至少和图同构问题一样难。本文的思路是退而求其次寻找有理函数域的生成元而不是多项式环的生成元。有理函数域包含了更丰富的函数类包括多项式、分式等更适合机器学习模型。这里伽罗瓦理论闪亮登场。在域论中伽罗瓦理论描述了域扩张的对称性伽罗瓦群与其中间域的一一对应关系。本文的作者们从中汲取灵感证明了一个适用于机器学习场景的“伽罗瓦定理”定理简化版设有一个群Γ作用在空间X上并且我们有一组Γ-不变函数{f₁, …, fᵣ}它们能“一般性地”分离Γ的轨道即除了一个测度为零的坏集它们能区分不同轨道。现在考虑Γ的一个有限指数子群G。如果我们能找到一组G-不变函数{f₁, …, fₛ}满足一个关键条件——在Γ中能同时固定所有f*ⱼ的元素恰好就是G——那么联合特征集{f₁, …, fᵣ, f₁, …, fₛ}就能一般性地分离G的轨道。这个定理的威力在于它提供了一种“升级”分离特征集的系统方法。我们可以从一个作用更“松散”、更容易找到分离特征的大群Γ开始然后通过精心挑选一个额外的特征f*将分离能力“收缩”到我们真正关心的、作用更“严格”的子群G上。实操心得理解这个定理的关键在于把握“固定”的含义。一个群元素γ“固定”函数f*意味着对于所有输入x有f*(γ·x) f*(x)。定理的条件要求只有子群G中的元素才能同时固定所有fⱼ。这个f就像一个“指纹”或“签名”它对大群Γ中除了G以外的变换是敏感的。通过检查这个指纹是否改变我们就能判断施加的变换是否属于我们允许的子群G。2.3 构造对称矩阵的轻量级特征现在我们将这个定理应用到对称矩阵的置换群作用上。我们的目标是分离Sn轨道即真正的图同构类。选择大群Γ我们选择一个比Sn更容易处理的大群。考虑两个独立的置换群一个群Sn只打乱矩阵的对角线元素{X₁₁, …, Xₙₙ}另一个群S_{n(n-1)/2}只打乱矩阵的非对角线元素{Xᵢⱼ, ij}同保持对称性即Xᵢⱼ和Xⱼᵢ被视为一对。这两个群的直积Γ Sn × S_{n(n-1)/2}就是一个作用更“解耦”的大群。构造Γ的分离特征对于Γ构造分离特征非常简单对角特征 (fᵈ)取对角线元素将它们排序。即fᵈₖ(X) 第k大的对角线元素值。这组特征共n个完全捕捉了对角线元素的多重集信息无视其顺序。非对角特征 (fᵒ)取所有上三角或下三角的非对角线元素将它们排序。即fᵒₗ(X) 第l大的非对角线元素值。这组特征共n(n-1)/2个完全捕捉了边权重的多重集信息。 显然{fᵈₖ}和{fᵒₗ}这总共O(n²)个特征一起可以唯一确定矩阵在Γ作用下的轨道。因为Γ允许对角线和非对角线独立置换所以只要这两组多重集分别相同矩阵就在同一个Γ轨道内。构造关键指纹f*现在我们需要一个函数f*它对于真正的置换群G (≅ Sn) 是不变的但对于Γ中那些不是由同一个底层索引置换所诱导的元素即对角和非对角置换不一致的元素是敏感的。一个巧妙的选择是 f*(X) Σ_{i≠j} Xᵢᵢ Xᵢⱼ 这个函数的意义是什么它的每一项XᵢᵢXᵢⱼ同时涉及了一个对角线元素和一个以i为端点的边。在Γ中如果一个变换(σ, τ)要固定f*那么它必须把形如XᵢᵢXᵢⱼ的项映射到同类项。这意味着变换必须保持“对角线元素索引”和“与该索引关联的边”之间的对应关系。可以严格证明能保持这种对应关系的(σ, τ)必然是由同一个底层索引置换所诱导的。也就是说在Γ中能固定f*的元素的集合恰好就是我们要的子群G。应用定理根据上述伽罗瓦定理联合特征集 {fᵈ₁, …, fᵈₙ, fᵒ₁, …, fᵒ_{n(n-1)/2}, f*} 就能一般性地分离Sn轨道。这里的“坏集合”B就是那些使得某个(γf* - f*)为零的矩阵构成的集合它是一个代数簇在连续空间中是测度为零的。计算复杂度计算fᵈ需要O(n log n)时间排序计算fᵒ需要O(n² log n)时间排序计算f*需要O(n²)时间双重循环求和。因此总复杂度是O(n² log n)与输入数据n²个矩阵元素的规模同阶是高效的。3. 从理论特征到实用模型有了这组理论上“几乎处处”分离的特征我们如何将其变成一个可用的机器学习模型呢这个过程涉及从分离性到逼近性的过渡以及模型的具体构建。3.1 从轨道分离到函数逼近定理4.4告诉我们这组特征{fᵈ, fᵒ, f*}能在除去一个坏集B的对称矩阵空间上分离所有不同的Sn轨道。这是一个关于区分不同数据点的结论。而机器学习通常关心的是用函数去拟合或逼近某个目标函数。这里需要一个关键的桥梁——Stone-Weierstrass定理。这个定理是数学分析中的经典结论简单说就是在一个紧致的豪斯多夫空间上如果一个函数代数能分离点即对于任意两个不同的点存在代数中的某个函数取值不同那么该代数在该空间上就是一致稠密的即可以一致逼近任何连续函数。在我们的场景中对称矩阵空间S(n)在Sn作用下的商空间S(n)/Sn在适当拓扑下是豪斯多夫空间。我们的不变特征诱导了这个商空间上的一组连续函数。这组函数生成的代数即这些函数的任意多项式组合在商空间上能分离点因为特征本身能分离轨道。因此由Stone-Weierstrass定理这个代数可以一致逼近该商空间上任何连续函数。回到原空间就意味着任何连续的、Sn不变的函数都可以被我们的特征的多项式函数一致逼近在紧集上。最后我们知道多层感知机MLP是通用函数逼近器。因此我们可以构建一个模型首先用我们构造的O(n²)个不变特征将输入矩阵X映射到一个向量然后将这个向量送入一个MLP中进行学习。由于MLP可以逼近特征空间上的任意连续函数而我们的特征又能逼近任意不变函数所以整个架构就具备了“通用逼近”不变函数的能力同样在除去坏集B的意义下。3.2 处理点云数据Gram矩阵与降维对于点云V ∈ R^{d×n}我们如前所述先计算其Gram矩阵X VᵀV然后应用上述对称矩阵的特征构造方法得到特征向量再输入MLP。这就自动保证了模型的正交-置换不变性。然而这里存在一个效率问题。一个d维点云只有O(dn)个自由参数但我们却使用了O(n²)个特征。当d固定且较小时例如3D点云d3这造成了信息冗余。能否将特征数量降至O(n)呢答案是肯定的这需要利用Gram矩阵的低秩特性。因为rank(X) ≤ d所以X不是一个普通的对称矩阵而是一个秩至多为d的半正定矩阵。这种低秩结构意味着它的信息可以被远少于n²个数字所捕获。核心思路命题6.5与定理6.4存在一个从O(n)个特征到我们之前构造的O(n²)个特征的泛函重构。也就是说对于“一般”的点云同样排除一个测度为零的坏集其完整的O(n²)个不变特征值可以通过一个固定的、连续的函数由仅仅O(n)个特定的不变特征完全恢复出来。这个结论的证明用到了低秩矩阵补全的思想。直观上一个秩为d的n×n对称矩阵理论上可以由其O(dn)个元素唯一确定在满足某些条件时。通过选择一组恰当的O(n)个特征例如某些特定的主子式或与一个随机向量相互作用的值可以唯一地确定整个矩阵在置换下的轨道从而也确定了所有其他不变特征。实操要点特征选择在实践中一种可行的O(n)特征集是计算点云V与d1个或稍多随机生成的、固定d维向量u₁, u₂, …的投影内积即计算向量Vᵀu_k ∈ R^n。然后对这些n维向量中的每一个取其排序后的元素作为特征。这样每个向量产生n个特征总共O(n)个。理论保证可以证明对于一般的点云这组O(n)个特征与之前的O(n²)个特征包含相同的分离信息。因此用这组O(n)特征训练MLP同样能实现通用逼近。计算优势将特征计算复杂度从O(n² log n)降至O(dn log n)。对于大规模点云如n10^10这是从不可行到可行的本质区别。3.3 模型架构与可变大小输入处理一个完整的模型架构如下特征提取层Invariant Feature Layer:输入对称矩阵X (n×n) 或点云V (d×n)。处理对于矩阵X直接计算排序后的对角线特征(fᵈ)、排序后的非对角线特征(fᵒ)以及交叉和特征(f*)拼接成一个O(n²)维向量。对于点云V计算Gram矩阵X VᵀV然后同上。或者采用高效的O(n)特征方案计算V与若干固定随机向量的投影对每个投影结果排序拼接成O(n)维向量。输出一个固定维度的特征向量维度取决于预设的最大n记为N_max。深度学习处理层DeepSets / MLP:输入上一步得到的特征向量核心使用一个多层感知机MLP来处理这个特征向量。MLP由全连接层和非线性激活函数如ReLU交替构成。关键这里使用DeepSets的思想。DeepSets是一种处理集合数据的经典架构其核心是“对每个元素应用相的函数φ然后聚合如求和最后用一个函数ρ处理聚合结果”。在我们的场景中特征提取层已经完成了“排序”这一强大的对称化聚合操作因此后续的MLP可以视为一个强大的函数ρ。输出模型预测值标量或向量。处理可变大小输入由于排序操作和f*的计算对输入大小n是自适应的因此模型可以处理不同的n。但是特征向量的长度会随着n变化。为了使用同一个MLP我们需要将特征向量填充或截断到一个统一的维度N_max一个预设的输入大小上界。填充策略对于fᵈ和fᵒ如果n N_max可以用一个特定的值如0或NaN填充到长度N_max和N_max(N_max-1)/2如果n N_max则截断但这可能损失信息。f*是一个标量不受影响。对于O(n)点云特征也采用类似填充策略。训练在训练时可以使用不同大小的样本批次每个样本的特征在输入MLP前被标准化到统一维度。注意事项坏集的存在模型在理论上无法区分坏集上的不同轨道。但在实践中这个坏集是测度为零的随机采样到的数据点几乎不可能落在上面。然而对于高度结构化或对称性极强的数据如所有节点权重相等的完全图需要保持警惕。排序操作的不可微性排序操作在反向传播中会带来梯度问题。在实际实现中通常使用可微分的排序近似如torch.sort返回的索引在PyTorch中是可微的尽管梯度在相等值处未定义或者使用SoftSort、Optimal Transport-based Sinkhorn排序等平滑近似。计算效率尽管特征计算是O(n²)或O(n)但对于非常大的n排序O(n² log n)可能成为瓶颈。可以考虑使用近似排序或分块排序策略。O(n)方案在d固定时显著更优。4. 实战应用与代码剖析理论再优美也需要实践检验。原论文在分子性质预测和点云距离预测两个任务上验证了方法的可行性。我们来深入看看如何具体实现并解析其中的关键代码。4.1 应用一分子性质预测分子可以自然地表示为图原子是节点键是边。预测分子的量子化学性质如HOMO-LUMO能隙、极化率是计算化学的核心任务。模型需要对原子的排列置换不变。数据处理分子被表示为图。每个原子对应一个节点具有特征如原子类型、电荷等。每个键对应一条边具有特征如键类型、长度等。为了应用本方法我们需要一个对称矩阵表示。一种简单的方式是构建一个加权邻接矩阵XXᵢᵢ可以包含原子特征如通过一个可学习的原子类型嵌入向量的模长或设为0。Xᵢⱼ (i≠j)如果原子i和j之间有键则值可以包含键特征如键长、类型嵌入如果没有键可以设为0或一个特殊的负值。也可以考虑更复杂的方案如利用原子对的3D距离。这样得到的X就是一个实对称矩阵直接输入到我们的不变特征提取层。模型实现要点PyTorch伪代码import torch import torch.nn as nn import torch.nn.functional as F class InvariantGraphModel(nn.Module): def __init__(self, max_n, hidden_dims, output_dim): super().__init__() self.max_n max_n # 特征维度对角(max_n) 非对角(max_n*(max_n-1)//2) 交叉和(1) self.feat_dim max_n (max_n*(max_n-1))//2 1 # 构建MLP layers [] prev_dim self.feat_dim for h_dim in hidden_dims: layers.append(nn.Linear(prev_dim, h_dim)) layers.append(nn.ReLU()) prev_dim h_dim layers.append(nn.Linear(prev_dim, output_dim)) self.mlp nn.Sequential(*layers) def extract_features(self, X): X: 批量的对称矩阵形状 (batch_size, n, n) 返回批量的不变特征向量形状 (batch_size, self.feat_dim) batch_size, n, _ X.shape device X.device # 1. 对角特征 f^d: 排序对角线元素 diag torch.diagonal(X, dim11, dim22) # (batch_size, n) f_d, _ torch.sort(diag, dim-1, descendingTrue) # (batch_size, n) # 2. 非对角特征 f^o: 获取上三角元素不含对角线排序 # 创建一个上三角掩码不含对角线 triu_mask torch.triu(torch.ones(n, n, devicedevice), diagonal1).bool() # 扩展掩码到批量维度 triu_mask_expanded triu_mask.unsqueeze(0).expand(batch_size, -1, -1) off_diag X[triu_mask_expanded].view(batch_size, -1) # (batch_size, n*(n-1)/2) f_o, _ torch.sort(off_diag, dim-1, descendingTrue) # 3. 交叉和特征 f* # f* sum_{i!j} X_ii * X_ij # 高效计算对于每个iX_ii * (sum_{j!i} X_ij) row_sums X.sum(dim2) - diag # 每行和减去对角线即 sum_{j!i} X_ij f_star (diag * row_sums).sum(dim1, keepdimTrue) # (batch_size, 1) # 4. 填充/截断到最大维度 # f_d 填充到 max_n if n self.max_n: pad_size self.max_n - n f_d_padded F.pad(f_d, (0, pad_size), value0.0) else: f_d_padded f_d[:, :self.max_n] # f_o 填充到 max_n*(max_n-1)//2 max_off_diag_len self.max_n * (self.max_n - 1) // 2 current_off_diag_len n * (n - 1) // 2 if current_off_diag_len max_off_diag_len: pad_size max_off_diag_len - current_off_diag_len f_o_padded F.pad(f_o, (0, pad_size), value0.0) else: f_o_padded f_o[:, :max_off_diag_len] # 拼接所有特征 features torch.cat([f_d_padded, f_o_padded, f_star], dim1) return features def forward(self, X): feats self.extract_features(X) out self.mlp(feats) return out注意事项与技巧排序稳定性torch.sort在遇到相等值时返回的索引顺序可能不稳定导致梯度微小波动。对于需要严格置换不变性的任务这可能不是问题因为特征值集合本身是确定的。如果追求完全稳定的梯度可以考虑使用可微排序的第三方库。填充值选择用0填充可能引入歧义因为0可能是一个有效的特征值如无边连接的权重。可以考虑使用一个远离正常数据范围的标志值如-1e9并在MLP第一层后通过掩码将其影响消除。特征标准化由于排序特征的值范围取决于输入数据在输入MLP前进行批归一化BatchNorm或层归一化LayerNorm通常有助于训练。4.2 应用二点云距离预测预测两个点云之间的几何距离如Gromov-Wasserstein距离是形状匹配、蛋白质结构比对等任务的基础。模型需要对两个点云各自的内部置换以及整体的旋转/反射不变。数据处理与模型调整对于一对点云V^A和V^B分别计算它们的Gram矩阵X^A和X^B。分别提取它们的不变特征向量feat^A和feat^B。一种简单的架构是将两个特征向量拼接起来输入MLP来预测它们之间的距离标量。更复杂的架构可以引入交叉注意力机制让特征在融合前进行交互。O(n)特征方案实现 对于点云实现高效的O(n)特征版本更为关键。class EfficientPointCloudModel(nn.Module): def __init__(self, d, max_n, num_projections, hidden_dims, output_dim): d: 点云维度 max_n: 最大点数 num_projections: 使用的随机投影向量数量K建议 d1 super().__init__() self.d d self.max_n max_n self.K num_projections # 初始化K个固定的随机投影向量 self.register_buffer(projection_vectors, torch.randn(self.K, d)) # 特征维度K个投影每个投影产生max_n个排序值 self.feat_dim self.K * self.max_n # 构建MLP layers [] prev_dim self.feat_dim for h_dim in hidden_dims: layers.append(nn.Linear(prev_dim, h_dim)) layers.append(nn.ReLU()) prev_dim h_dim layers.append(nn.Linear(prev_dim, output_dim)) self.mlp nn.Sequential(*layers) def extract_features(self, V): V: 批量的点云形状 (batch_size, d, n) 注意这里输入是 (batch_size, d, n)便于进行矩阵乘法 返回批量的O(n)不变特征形状 (batch_size, self.feat_dim) batch_size, d, n V.shape # 1. 投影: (batch_size, d, n) (K, d)^T - (batch_size, n, K) projections torch.matmul(V.transpose(1, 2), self.projection_vectors.T) # (batch_size, n, K) # 2. 对每个投影方向K个独立排序 # 将K维度移到前面以便并行排序: (batch_size, K, n) projections projections.permute(0, 2, 1) sorted_projections, _ torch.sort(projections, dim-1, descendingTrue) # (batch_size, K, n) # 3. 填充/截断到max_n if n self.max_n: pad_size self.max_n - n padded F.pad(sorted_projections, (0, pad_size), value0.0) # 在最后一维n维填充 else: padded sorted_projections[:, :, :self.max_n] # 4. 展平: (batch_size, K*max_n) features padded.reshape(batch_size, -1) return features def forward(self, V): feats self.extract_features(V) out self.mlp(feats) return out关键解析num_projections的选择理论上d1个一般位置的投影向量足以唯一确定一个d维点云的Gram矩阵从而确定其轨道。但在实践中为了鲁棒性和增加特征丰富度通常会选择稍多一些例如K d5 或 d10。随机向量的固定投影向量在模型初始化时随机生成并注册为缓冲区这意味着它们在训练过程中是固定的不参与梯度更新。这保证了特征提取的一致性。也可以将其设为可学习参数但可能会增加过拟合风险。计算复杂度投影操作复杂度为O(K * d * n)排序复杂度为O(K * n log n)。由于K和d是常数总复杂度为O(n log n)对于大规模点云极其高效。5. 常见问题、局限性与未来方向任何方法都有其边界。理解这些局限性和潜在问题能帮助我们在正确的场景下应用它并启发后续的改进。5.1 理论局限性“几乎处处”而非“处处”这是本方法最核心的理论松弛。坏集B虽然测度为零但并非空集。它包含那些具有高度对称性或特殊代数关系的矩阵/点云。例如所有对角线元素相等的矩阵。所有非对角线元素相等的矩阵。点云中所有点共线或共面且具有某种对称排列。在实践中随机数据几乎不可能落入坏集但如果你处理的数据恰好具有这些特殊结构模型可能无法区分原本不同的轨道。对坏集的敏感性虽然坏集很小但模型在坏集附近的行为可能不稳定。两个非常接近但分居坏集两侧的点其特征值可能发生突变导致模型预测剧烈变化。这需要在损失函数或正则化中加以考虑。连续性与平滑性排序操作本身是分段线性的其导数在相等点处不连续或未定义。这可能导致特征映射的 Lipschitz 常数较大在需要平滑性保证的应用中可能不是最优选择。5.2 实践挑战与解决方案挑战表现可能原因解决方案与缓解策略梯度流不稳定训练损失震荡难以收敛排序操作在相等值处的梯度未定义或爆炸填充值引入噪声。1. 使用可微排序的平滑近似如SoftSort、Sinkhorn排序。2. 在排序前为数据添加极小的随机噪声打破平局。3. 仔细设计填充策略或使用注意力掩码忽略填充部分。特征维度随n增长对于可变n需要填充/截断可能损失信息或引入偏差。模型架构需要固定大小的输入。1. 使用基于注意力的聚合器如Transformer代替简单填充直接处理可变长度序列。2. 采用层次化特征提取先对子图/子点云提取特征再聚合。3. 将n本身也作为一个标量特征输入MLP。计算瓶颈O(n²)版本处理大规模图n10^4时排序O(n² log n)和内存O(n²)成为瓶颈。特征数量与边数同阶。1. 优先使用点云的O(n)版本。2. 对于图考虑基于采样的近似随机采样节点子集计算特征或使用图分区技术。3. 探索基于谱方法或局部聚合的近似不变特征。信息损失排序操作丢弃了元素间的对应关系只保留了多重集信息。这是实现置换不变性的代价。1. 对于图数据可以结合使用局部节点级特征和全局排序后特征。2. 引入高阶的交互特征如f*它部分保留了索引关联信息。3. 与消息传递GNN结合将排序特征作为全局上下文输入到每一层。5.3 扩展与未来方向面向其他群作用本文的核心“伽罗瓦定理”框架具有一般性。未来可以探索将其应用于其他重要的群作用如特殊正交群SO(d)排除反射、缩放变换、甚至更复杂的李群和非紧致群。与深度架构的深度融合目前特征提取层和MLP是分离的。可以探索端到端的学习让网络的一部分学习如何生成更好的“指纹”函数f*或者学习更有效的投影向量在O(n)方案中。理论深化进一步刻画坏集B的具体几何与代数结构。研究如何构造在坏集上也有良好行为的特征或者如何设计模型使其对坏集不敏感。应用于动态图与时序点云将不变特征提取扩展到动态场景处理随时间变化的图或点云序列需要结合时间上的等变性或不变性。在我个人的实验和思考中这种方法最大的魅力在于其简洁性与强大理论保证的平衡。它没有使用复杂的消息传递或高阶张量仅仅通过排序和一个巧妙的交叉和就抓住了置换不变性的核心并且有坚实的数学基础说明“为什么这几乎总是有效的”。对于需要快速原型验证或处理超大规模对称数据的场景它是一个非常有力的工具。当然它并非银弹其对于连续对称性如旋转的处理依赖于先转化为Gram矩阵这可能会损失一些信息如全局平移。在实际项目中我通常会将其作为一个强大的基准模型或者作为一个组件与更复杂的几何深度学习模型结合使用以注入明确的不变性先验知识。
基于伽罗瓦理论的轻量级不变特征：高效处理置换与旋转对称数据
发布时间：2026/5/25 7:17:28
1. 项目概述与核心价值在机器学习领域我们常常会遇到一类“不讲道理”的数据它们没有固定的顺序也没有一个绝对的朝向。想象一下你面前有一堆散落的乐高积木无论你怎么旋转它们或者打乱它们的摆放顺序它们拼出来的城堡还是那个城堡。对于计算机来说理解这种“无论怎么变换本质不变”的特性是一个巨大的挑战。这类数据无处不在在化学中一个分子无论其原子如何编号它的性质是固定的在天文学中一个星团无论从哪个角度观测其物理本质不变在计算机图形学中一个三维物体无论如何旋转和平移它仍然是同一个物体。处理这类数据的关键就在于不变性。不变性简而言之就是模型的输出不因输入数据的某种对称变换比如打乱顺序、旋转、镜像而改变。这听起来像是模型应该具备的基本素养但实现起来却暗藏玄机。传统的方法如图神经网络中的消息传递机制确实保证了置换不变性但它们往往在表达能力上有所妥协难以捕捉全局的、复杂的图结构属性。另一方面一些理论上具有“通用逼近”能力的模型又因为计算复杂度爆炸比如需要处理O(n^d)量级的张量而无法应用于大规模数据。这就形成了一个两难困境要么模型高效但表达能力有限要么模型强大但计算上不可行。我们今天要深入探讨的这项工作正是试图在这个困境中劈开一条新路。它源自一篇题为《A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features》的研究。其核心思想非常巧妙我们不一定非要追求在所有可能的数据上都完美无缺的“最坏情况”保证。相反如果我们愿意接受在一个测度为零的“坏”集合上可能失效那么就能以与输入数据规模同阶的计算成本构造出在“几乎所有”数据上都有效的轻量级不变特征。具体来说对于n个节点的加权图用对称矩阵表示该方法能构造O(n²)个不变特征对于固定维度d中的n个点组成的点云这个数量可以进一步降至O(n)。这背后的数学工具灵感来自于伽罗瓦理论——一个通常出现在抽象代数课本里研究域扩张对称性的理论。研究者们将其精髓提炼出来用于系统地构造这些“几乎处处”分离不同数据轨道的特征。这项工作的价值是立体的。在理论上它建立了一个连接经典不变性理论与现代机器学习需求的桥梁提供了一种松弛但实用的“通用逼近”新视角。在工程上它给出的特征构造方法计算高效复杂度与数据本身的大小相当使得处理超大规模点云例如天文学中数十亿个星体的数据成为可能。在应用上它可以直接用于分子性质预测、点云相似性比较等任务为科学计算领域提供了新的工具。接下来我们将层层剥开这个方法的数学内核与实现细节。2. 核心数学原理从伽罗瓦理论到不变特征要理解这个方法为何有效我们需要暂时走进抽象的数学世界。不用担心我会用尽可能直观的方式来解释。2.1 问题形式化我们到底在对付什么首先我们面对两种核心的数据结构及其对称性对称矩阵与置换群一个n×n的实对称矩阵X可以代表一个具有n个节点的加权无向图对角线是节点权重非对角线是边权重。这个矩阵的表示依赖于节点的编号顺序。如果我们打乱节点的编号即施加一个置换π对应的矩阵会变为PπXPπᵀ其中Pπ是置换矩阵。所有通过这种置换相互关联的矩阵都属于同一个图。因此我们真正关心的函数f(X)应该满足f(X) f(PπXPπᵀ)对所有置换π成立。这就是置换不变性。点云与正交群一个d×n的矩阵V代表d维空间中的n个点每列是一个点。我们关心的是点云本身的几何形状而不是它在空间中的具体摆放旋转、反射或点的标签顺序。因此一个函数g(V)如果同时满足g(V) g(UV)U是任意d×d正交矩阵代表旋转/反射和g(V) g(VPπᵀ)置换点的顺序那么它就是正交-置换不变的。一个关键的观察是对于点云V其格拉姆矩阵X VᵀV是一个n×n的对称半正定矩阵。并且一个函数g(V)是正交-置换不变的当且仅当存在一个置换不变的函数f使得g(V) f(VᵀV)。这就把点云的问题转化为了对称矩阵的问题但增加了一个约束X的秩最多为d因为来自d维空间中的点。所以问题的核心归结为如何为对称矩阵空间S(n)在点云情形下是秩≤d的半正定矩阵子集构造一组数量可控、易于计算的不变特征使得它们能“分离”几乎所有的轨道这里的“分离”是指对于两个不在“坏集合”中的矩阵X和Y如果它们不属于同一个置换轨道那么至少有一个特征值在这两个矩阵上不同。2.2 伽罗瓦理论的启示从大群到子群经典的不变理论致力于寻找生成所有不变多项式的基集但这对于置换群作用在对称矩阵上的情况来说已知是计算上难解的因为它至少和图同构问题一样难。本文的思路是退而求其次寻找有理函数域的生成元而不是多项式环的生成元。有理函数域包含了更丰富的函数类包括多项式、分式等更适合机器学习模型。这里伽罗瓦理论闪亮登场。在域论中伽罗瓦理论描述了域扩张的对称性伽罗瓦群与其中间域的一一对应关系。本文的作者们从中汲取灵感证明了一个适用于机器学习场景的“伽罗瓦定理”定理简化版设有一个群Γ作用在空间X上并且我们有一组Γ-不变函数{f₁, …, fᵣ}它们能“一般性地”分离Γ的轨道即除了一个测度为零的坏集它们能区分不同轨道。现在考虑Γ的一个有限指数子群G。如果我们能找到一组G-不变函数{f₁, …, fₛ}满足一个关键条件——在Γ中能同时固定所有f*ⱼ的元素恰好就是G——那么联合特征集{f₁, …, fᵣ, f₁, …, fₛ}就能一般性地分离G的轨道。这个定理的威力在于它提供了一种“升级”分离特征集的系统方法。我们可以从一个作用更“松散”、更容易找到分离特征的大群Γ开始然后通过精心挑选一个额外的特征f*将分离能力“收缩”到我们真正关心的、作用更“严格”的子群G上。实操心得理解这个定理的关键在于把握“固定”的含义。一个群元素γ“固定”函数f*意味着对于所有输入x有f*(γ·x) f*(x)。定理的条件要求只有子群G中的元素才能同时固定所有fⱼ。这个f就像一个“指纹”或“签名”它对大群Γ中除了G以外的变换是敏感的。通过检查这个指纹是否改变我们就能判断施加的变换是否属于我们允许的子群G。2.3 构造对称矩阵的轻量级特征现在我们将这个定理应用到对称矩阵的置换群作用上。我们的目标是分离Sn轨道即真正的图同构类。选择大群Γ我们选择一个比Sn更容易处理的大群。考虑两个独立的置换群一个群Sn只打乱矩阵的对角线元素{X₁₁, …, Xₙₙ}另一个群S_{n(n-1)/2}只打乱矩阵的非对角线元素{Xᵢⱼ, ij}同保持对称性即Xᵢⱼ和Xⱼᵢ被视为一对。这两个群的直积Γ Sn × S_{n(n-1)/2}就是一个作用更“解耦”的大群。构造Γ的分离特征对于Γ构造分离特征非常简单对角特征 (fᵈ)取对角线元素将它们排序。即fᵈₖ(X) 第k大的对角线元素值。这组特征共n个完全捕捉了对角线元素的多重集信息无视其顺序。非对角特征 (fᵒ)取所有上三角或下三角的非对角线元素将它们排序。即fᵒₗ(X) 第l大的非对角线元素值。这组特征共n(n-1)/2个完全捕捉了边权重的多重集信息。 显然{fᵈₖ}和{fᵒₗ}这总共O(n²)个特征一起可以唯一确定矩阵在Γ作用下的轨道。因为Γ允许对角线和非对角线独立置换所以只要这两组多重集分别相同矩阵就在同一个Γ轨道内。构造关键指纹f*现在我们需要一个函数f*它对于真正的置换群G (≅ Sn) 是不变的但对于Γ中那些不是由同一个底层索引置换所诱导的元素即对角和非对角置换不一致的元素是敏感的。一个巧妙的选择是 f*(X) Σ_{i≠j} Xᵢᵢ Xᵢⱼ 这个函数的意义是什么它的每一项XᵢᵢXᵢⱼ同时涉及了一个对角线元素和一个以i为端点的边。在Γ中如果一个变换(σ, τ)要固定f*那么它必须把形如XᵢᵢXᵢⱼ的项映射到同类项。这意味着变换必须保持“对角线元素索引”和“与该索引关联的边”之间的对应关系。可以严格证明能保持这种对应关系的(σ, τ)必然是由同一个底层索引置换所诱导的。也就是说在Γ中能固定f*的元素的集合恰好就是我们要的子群G。应用定理根据上述伽罗瓦定理联合特征集 {fᵈ₁, …, fᵈₙ, fᵒ₁, …, fᵒ_{n(n-1)/2}, f*} 就能一般性地分离Sn轨道。这里的“坏集合”B就是那些使得某个(γf* - f*)为零的矩阵构成的集合它是一个代数簇在连续空间中是测度为零的。计算复杂度计算fᵈ需要O(n log n)时间排序计算fᵒ需要O(n² log n)时间排序计算f*需要O(n²)时间双重循环求和。因此总复杂度是O(n² log n)与输入数据n²个矩阵元素的规模同阶是高效的。3. 从理论特征到实用模型有了这组理论上“几乎处处”分离的特征我们如何将其变成一个可用的机器学习模型呢这个过程涉及从分离性到逼近性的过渡以及模型的具体构建。3.1 从轨道分离到函数逼近定理4.4告诉我们这组特征{fᵈ, fᵒ, f*}能在除去一个坏集B的对称矩阵空间上分离所有不同的Sn轨道。这是一个关于区分不同数据点的结论。而机器学习通常关心的是用函数去拟合或逼近某个目标函数。这里需要一个关键的桥梁——Stone-Weierstrass定理。这个定理是数学分析中的经典结论简单说就是在一个紧致的豪斯多夫空间上如果一个函数代数能分离点即对于任意两个不同的点存在代数中的某个函数取值不同那么该代数在该空间上就是一致稠密的即可以一致逼近任何连续函数。在我们的场景中对称矩阵空间S(n)在Sn作用下的商空间S(n)/Sn在适当拓扑下是豪斯多夫空间。我们的不变特征诱导了这个商空间上的一组连续函数。这组函数生成的代数即这些函数的任意多项式组合在商空间上能分离点因为特征本身能分离轨道。因此由Stone-Weierstrass定理这个代数可以一致逼近该商空间上任何连续函数。回到原空间就意味着任何连续的、Sn不变的函数都可以被我们的特征的多项式函数一致逼近在紧集上。最后我们知道多层感知机MLP是通用函数逼近器。因此我们可以构建一个模型首先用我们构造的O(n²)个不变特征将输入矩阵X映射到一个向量然后将这个向量送入一个MLP中进行学习。由于MLP可以逼近特征空间上的任意连续函数而我们的特征又能逼近任意不变函数所以整个架构就具备了“通用逼近”不变函数的能力同样在除去坏集B的意义下。3.2 处理点云数据Gram矩阵与降维对于点云V ∈ R^{d×n}我们如前所述先计算其Gram矩阵X VᵀV然后应用上述对称矩阵的特征构造方法得到特征向量再输入MLP。这就自动保证了模型的正交-置换不变性。然而这里存在一个效率问题。一个d维点云只有O(dn)个自由参数但我们却使用了O(n²)个特征。当d固定且较小时例如3D点云d3这造成了信息冗余。能否将特征数量降至O(n)呢答案是肯定的这需要利用Gram矩阵的低秩特性。因为rank(X) ≤ d所以X不是一个普通的对称矩阵而是一个秩至多为d的半正定矩阵。这种低秩结构意味着它的信息可以被远少于n²个数字所捕获。核心思路命题6.5与定理6.4存在一个从O(n)个特征到我们之前构造的O(n²)个特征的泛函重构。也就是说对于“一般”的点云同样排除一个测度为零的坏集其完整的O(n²)个不变特征值可以通过一个固定的、连续的函数由仅仅O(n)个特定的不变特征完全恢复出来。这个结论的证明用到了低秩矩阵补全的思想。直观上一个秩为d的n×n对称矩阵理论上可以由其O(dn)个元素唯一确定在满足某些条件时。通过选择一组恰当的O(n)个特征例如某些特定的主子式或与一个随机向量相互作用的值可以唯一地确定整个矩阵在置换下的轨道从而也确定了所有其他不变特征。实操要点特征选择在实践中一种可行的O(n)特征集是计算点云V与d1个或稍多随机生成的、固定d维向量u₁, u₂, …的投影内积即计算向量Vᵀu_k ∈ R^n。然后对这些n维向量中的每一个取其排序后的元素作为特征。这样每个向量产生n个特征总共O(n)个。理论保证可以证明对于一般的点云这组O(n)个特征与之前的O(n²)个特征包含相同的分离信息。因此用这组O(n)特征训练MLP同样能实现通用逼近。计算优势将特征计算复杂度从O(n² log n)降至O(dn log n)。对于大规模点云如n10^10这是从不可行到可行的本质区别。3.3 模型架构与可变大小输入处理一个完整的模型架构如下特征提取层Invariant Feature Layer:输入对称矩阵X (n×n) 或点云V (d×n)。处理对于矩阵X直接计算排序后的对角线特征(fᵈ)、排序后的非对角线特征(fᵒ)以及交叉和特征(f*)拼接成一个O(n²)维向量。对于点云V计算Gram矩阵X VᵀV然后同上。或者采用高效的O(n)特征方案计算V与若干固定随机向量的投影对每个投影结果排序拼接成O(n)维向量。输出一个固定维度的特征向量维度取决于预设的最大n记为N_max。深度学习处理层DeepSets / MLP:输入上一步得到的特征向量核心使用一个多层感知机MLP来处理这个特征向量。MLP由全连接层和非线性激活函数如ReLU交替构成。关键这里使用DeepSets的思想。DeepSets是一种处理集合数据的经典架构其核心是“对每个元素应用相的函数φ然后聚合如求和最后用一个函数ρ处理聚合结果”。在我们的场景中特征提取层已经完成了“排序”这一强大的对称化聚合操作因此后续的MLP可以视为一个强大的函数ρ。输出模型预测值标量或向量。处理可变大小输入由于排序操作和f*的计算对输入大小n是自适应的因此模型可以处理不同的n。但是特征向量的长度会随着n变化。为了使用同一个MLP我们需要将特征向量填充或截断到一个统一的维度N_max一个预设的输入大小上界。填充策略对于fᵈ和fᵒ如果n N_max可以用一个特定的值如0或NaN填充到长度N_max和N_max(N_max-1)/2如果n N_max则截断但这可能损失信息。f*是一个标量不受影响。对于O(n)点云特征也采用类似填充策略。训练在训练时可以使用不同大小的样本批次每个样本的特征在输入MLP前被标准化到统一维度。注意事项坏集的存在模型在理论上无法区分坏集上的不同轨道。但在实践中这个坏集是测度为零的随机采样到的数据点几乎不可能落在上面。然而对于高度结构化或对称性极强的数据如所有节点权重相等的完全图需要保持警惕。排序操作的不可微性排序操作在反向传播中会带来梯度问题。在实际实现中通常使用可微分的排序近似如torch.sort返回的索引在PyTorch中是可微的尽管梯度在相等值处未定义或者使用SoftSort、Optimal Transport-based Sinkhorn排序等平滑近似。计算效率尽管特征计算是O(n²)或O(n)但对于非常大的n排序O(n² log n)可能成为瓶颈。可以考虑使用近似排序或分块排序策略。O(n)方案在d固定时显著更优。4. 实战应用与代码剖析理论再优美也需要实践检验。原论文在分子性质预测和点云距离预测两个任务上验证了方法的可行性。我们来深入看看如何具体实现并解析其中的关键代码。4.1 应用一分子性质预测分子可以自然地表示为图原子是节点键是边。预测分子的量子化学性质如HOMO-LUMO能隙、极化率是计算化学的核心任务。模型需要对原子的排列置换不变。数据处理分子被表示为图。每个原子对应一个节点具有特征如原子类型、电荷等。每个键对应一条边具有特征如键类型、长度等。为了应用本方法我们需要一个对称矩阵表示。一种简单的方式是构建一个加权邻接矩阵XXᵢᵢ可以包含原子特征如通过一个可学习的原子类型嵌入向量的模长或设为0。Xᵢⱼ (i≠j)如果原子i和j之间有键则值可以包含键特征如键长、类型嵌入如果没有键可以设为0或一个特殊的负值。也可以考虑更复杂的方案如利用原子对的3D距离。这样得到的X就是一个实对称矩阵直接输入到我们的不变特征提取层。模型实现要点PyTorch伪代码import torch import torch.nn as nn import torch.nn.functional as F class InvariantGraphModel(nn.Module): def __init__(self, max_n, hidden_dims, output_dim): super().__init__() self.max_n max_n # 特征维度对角(max_n) 非对角(max_n*(max_n-1)//2) 交叉和(1) self.feat_dim max_n (max_n*(max_n-1))//2 1 # 构建MLP layers [] prev_dim self.feat_dim for h_dim in hidden_dims: layers.append(nn.Linear(prev_dim, h_dim)) layers.append(nn.ReLU()) prev_dim h_dim layers.append(nn.Linear(prev_dim, output_dim)) self.mlp nn.Sequential(*layers) def extract_features(self, X): X: 批量的对称矩阵形状 (batch_size, n, n) 返回批量的不变特征向量形状 (batch_size, self.feat_dim) batch_size, n, _ X.shape device X.device # 1. 对角特征 f^d: 排序对角线元素 diag torch.diagonal(X, dim11, dim22) # (batch_size, n) f_d, _ torch.sort(diag, dim-1, descendingTrue) # (batch_size, n) # 2. 非对角特征 f^o: 获取上三角元素不含对角线排序 # 创建一个上三角掩码不含对角线 triu_mask torch.triu(torch.ones(n, n, devicedevice), diagonal1).bool() # 扩展掩码到批量维度 triu_mask_expanded triu_mask.unsqueeze(0).expand(batch_size, -1, -1) off_diag X[triu_mask_expanded].view(batch_size, -1) # (batch_size, n*(n-1)/2) f_o, _ torch.sort(off_diag, dim-1, descendingTrue) # 3. 交叉和特征 f* # f* sum_{i!j} X_ii * X_ij # 高效计算对于每个iX_ii * (sum_{j!i} X_ij) row_sums X.sum(dim2) - diag # 每行和减去对角线即 sum_{j!i} X_ij f_star (diag * row_sums).sum(dim1, keepdimTrue) # (batch_size, 1) # 4. 填充/截断到最大维度 # f_d 填充到 max_n if n self.max_n: pad_size self.max_n - n f_d_padded F.pad(f_d, (0, pad_size), value0.0) else: f_d_padded f_d[:, :self.max_n] # f_o 填充到 max_n*(max_n-1)//2 max_off_diag_len self.max_n * (self.max_n - 1) // 2 current_off_diag_len n * (n - 1) // 2 if current_off_diag_len max_off_diag_len: pad_size max_off_diag_len - current_off_diag_len f_o_padded F.pad(f_o, (0, pad_size), value0.0) else: f_o_padded f_o[:, :max_off_diag_len] # 拼接所有特征 features torch.cat([f_d_padded, f_o_padded, f_star], dim1) return features def forward(self, X): feats self.extract_features(X) out self.mlp(feats) return out注意事项与技巧排序稳定性torch.sort在遇到相等值时返回的索引顺序可能不稳定导致梯度微小波动。对于需要严格置换不变性的任务这可能不是问题因为特征值集合本身是确定的。如果追求完全稳定的梯度可以考虑使用可微排序的第三方库。填充值选择用0填充可能引入歧义因为0可能是一个有效的特征值如无边连接的权重。可以考虑使用一个远离正常数据范围的标志值如-1e9并在MLP第一层后通过掩码将其影响消除。特征标准化由于排序特征的值范围取决于输入数据在输入MLP前进行批归一化BatchNorm或层归一化LayerNorm通常有助于训练。4.2 应用二点云距离预测预测两个点云之间的几何距离如Gromov-Wasserstein距离是形状匹配、蛋白质结构比对等任务的基础。模型需要对两个点云各自的内部置换以及整体的旋转/反射不变。数据处理与模型调整对于一对点云V^A和V^B分别计算它们的Gram矩阵X^A和X^B。分别提取它们的不变特征向量feat^A和feat^B。一种简单的架构是将两个特征向量拼接起来输入MLP来预测它们之间的距离标量。更复杂的架构可以引入交叉注意力机制让特征在融合前进行交互。O(n)特征方案实现 对于点云实现高效的O(n)特征版本更为关键。class EfficientPointCloudModel(nn.Module): def __init__(self, d, max_n, num_projections, hidden_dims, output_dim): d: 点云维度 max_n: 最大点数 num_projections: 使用的随机投影向量数量K建议 d1 super().__init__() self.d d self.max_n max_n self.K num_projections # 初始化K个固定的随机投影向量 self.register_buffer(projection_vectors, torch.randn(self.K, d)) # 特征维度K个投影每个投影产生max_n个排序值 self.feat_dim self.K * self.max_n # 构建MLP layers [] prev_dim self.feat_dim for h_dim in hidden_dims: layers.append(nn.Linear(prev_dim, h_dim)) layers.append(nn.ReLU()) prev_dim h_dim layers.append(nn.Linear(prev_dim, output_dim)) self.mlp nn.Sequential(*layers) def extract_features(self, V): V: 批量的点云形状 (batch_size, d, n) 注意这里输入是 (batch_size, d, n)便于进行矩阵乘法 返回批量的O(n)不变特征形状 (batch_size, self.feat_dim) batch_size, d, n V.shape # 1. 投影: (batch_size, d, n) (K, d)^T - (batch_size, n, K) projections torch.matmul(V.transpose(1, 2), self.projection_vectors.T) # (batch_size, n, K) # 2. 对每个投影方向K个独立排序 # 将K维度移到前面以便并行排序: (batch_size, K, n) projections projections.permute(0, 2, 1) sorted_projections, _ torch.sort(projections, dim-1, descendingTrue) # (batch_size, K, n) # 3. 填充/截断到max_n if n self.max_n: pad_size self.max_n - n padded F.pad(sorted_projections, (0, pad_size), value0.0) # 在最后一维n维填充 else: padded sorted_projections[:, :, :self.max_n] # 4. 展平: (batch_size, K*max_n) features padded.reshape(batch_size, -1) return features def forward(self, V): feats self.extract_features(V) out self.mlp(feats) return out关键解析num_projections的选择理论上d1个一般位置的投影向量足以唯一确定一个d维点云的Gram矩阵从而确定其轨道。但在实践中为了鲁棒性和增加特征丰富度通常会选择稍多一些例如K d5 或 d10。随机向量的固定投影向量在模型初始化时随机生成并注册为缓冲区这意味着它们在训练过程中是固定的不参与梯度更新。这保证了特征提取的一致性。也可以将其设为可学习参数但可能会增加过拟合风险。计算复杂度投影操作复杂度为O(K * d * n)排序复杂度为O(K * n log n)。由于K和d是常数总复杂度为O(n log n)对于大规模点云极其高效。5. 常见问题、局限性与未来方向任何方法都有其边界。理解这些局限性和潜在问题能帮助我们在正确的场景下应用它并启发后续的改进。5.1 理论局限性“几乎处处”而非“处处”这是本方法最核心的理论松弛。坏集B虽然测度为零但并非空集。它包含那些具有高度对称性或特殊代数关系的矩阵/点云。例如所有对角线元素相等的矩阵。所有非对角线元素相等的矩阵。点云中所有点共线或共面且具有某种对称排列。在实践中随机数据几乎不可能落入坏集但如果你处理的数据恰好具有这些特殊结构模型可能无法区分原本不同的轨道。对坏集的敏感性虽然坏集很小但模型在坏集附近的行为可能不稳定。两个非常接近但分居坏集两侧的点其特征值可能发生突变导致模型预测剧烈变化。这需要在损失函数或正则化中加以考虑。连续性与平滑性排序操作本身是分段线性的其导数在相等点处不连续或未定义。这可能导致特征映射的 Lipschitz 常数较大在需要平滑性保证的应用中可能不是最优选择。5.2 实践挑战与解决方案挑战表现可能原因解决方案与缓解策略梯度流不稳定训练损失震荡难以收敛排序操作在相等值处的梯度未定义或爆炸填充值引入噪声。1. 使用可微排序的平滑近似如SoftSort、Sinkhorn排序。2. 在排序前为数据添加极小的随机噪声打破平局。3. 仔细设计填充策略或使用注意力掩码忽略填充部分。特征维度随n增长对于可变n需要填充/截断可能损失信息或引入偏差。模型架构需要固定大小的输入。1. 使用基于注意力的聚合器如Transformer代替简单填充直接处理可变长度序列。2. 采用层次化特征提取先对子图/子点云提取特征再聚合。3. 将n本身也作为一个标量特征输入MLP。计算瓶颈O(n²)版本处理大规模图n10^4时排序O(n² log n)和内存O(n²)成为瓶颈。特征数量与边数同阶。1. 优先使用点云的O(n)版本。2. 对于图考虑基于采样的近似随机采样节点子集计算特征或使用图分区技术。3. 探索基于谱方法或局部聚合的近似不变特征。信息损失排序操作丢弃了元素间的对应关系只保留了多重集信息。这是实现置换不变性的代价。1. 对于图数据可以结合使用局部节点级特征和全局排序后特征。2. 引入高阶的交互特征如f*它部分保留了索引关联信息。3. 与消息传递GNN结合将排序特征作为全局上下文输入到每一层。5.3 扩展与未来方向面向其他群作用本文的核心“伽罗瓦定理”框架具有一般性。未来可以探索将其应用于其他重要的群作用如特殊正交群SO(d)排除反射、缩放变换、甚至更复杂的李群和非紧致群。与深度架构的深度融合目前特征提取层和MLP是分离的。可以探索端到端的学习让网络的一部分学习如何生成更好的“指纹”函数f*或者学习更有效的投影向量在O(n)方案中。理论深化进一步刻画坏集B的具体几何与代数结构。研究如何构造在坏集上也有良好行为的特征或者如何设计模型使其对坏集不敏感。应用于动态图与时序点云将不变特征提取扩展到动态场景处理随时间变化的图或点云序列需要结合时间上的等变性或不变性。在我个人的实验和思考中这种方法最大的魅力在于其简洁性与强大理论保证的平衡。它没有使用复杂的消息传递或高阶张量仅仅通过排序和一个巧妙的交叉和就抓住了置换不变性的核心并且有坚实的数学基础说明“为什么这几乎总是有效的”。对于需要快速原型验证或处理超大规模对称数据的场景它是一个非常有力的工具。当然它并非银弹其对于连续对称性如旋转的处理依赖于先转化为Gram矩阵这可能会损失一些信息如全局平移。在实际项目中我通常会将其作为一个强大的基准模型或者作为一个组件与更复杂的几何深度学习模型结合使用以注入明确的不变性先验知识。
