群不变谱嵌入

# 群不变谱嵌入  
来源：https://arxiv.org/html/2607.08987  

Yeari Vigder  
统计与运筹学系，特拉维夫大学，以色列特拉维夫  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(A\. Moscovich\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(Y\. Vigder\)  
同等贡献  

Paulina Hoyos  
数学系，德克萨斯大学奥斯汀分校，美国德克萨斯州奥斯汀  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(P\. Hoyos\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(J\. Kileel\)  
同等贡献  

David Thong  
数学系，KTH皇家理工学院，瑞典斯德哥尔摩  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(D\. Thong\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(J\. Andén\)  

Joakim Andén  
数学系，KTH皇家理工学院，瑞典斯德哥尔摩  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(D\. Thong\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(J\. Andén\)  

Joe Kileel  
数学系，德克萨斯大学奥斯汀分校，美国德克萨斯州奥斯汀  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(P\. Hoyos\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(J\. Kileel\)  

Amit Moscovich  
统计与运筹学系，特拉维夫大学，以色列特拉维夫  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(A\. Moscovich\),  
[email protected] (https://arxiv.org/html/2607.08987v1/mailto:[email protected])\(Y\. Vigder\)  

###### 摘要  
谱嵌入方法广泛应用于具有本征低维结构的高维数据集的降维和聚类。尽管许多实际感兴趣的数据集在旋转等对称性下具有不变性，但标准的谱嵌入方法并未考虑这一点，将对称相关的数据点视为无关。我们解决此问题的方法是将对称性直接纳入用于谱嵌入的亲和核中。我们分析了具有由紧致李群 \(G\) 给出的对称性的黎曼数据流形 \(\mathcal{M}\) 的情况，并证明在适当条件下，由三种类型的不变核构建的图拉普拉斯算子逐点收敛到商空间 \(\mathcal{M}/G\) 上的显式二阶微分算子。我们的分析表明收敛速率有所提高，因为有效维度根据群的维度而下降。我们在具有 \(\mathrm{SO}(2)\) 或 \(\mathrm{SO}(3)\) 对称性的数据集上验证了我们的方法，并表明 \(G\) 不变谱嵌入恢复了数据的内在几何结构，而标准谱嵌入即使在数据无限极限下也无法做到这一点。

> 关键词：降维，流形学习，图拉普拉斯，数据对称性，商流形，样本复杂度  
MSC 2020：62R07, 62R30, 58J70, 58J50, 35R02

## 1 引言

谱嵌入方法是分析具有本征低维结构的高维数据的强大工具。其基本操作原理是从数据点之间的成对亲和度构建图，然后使用图拉普拉斯算子的特征向量作为低维表示。这些方法广泛应用于降维、聚类、半监督学习和数据去噪等任务。

在本工作中，我们考虑在已知对称变换下具有不变性的数据集。例如，在单颗粒冷冻电子显微镜（cryo-EM）中，分子投影图像会受到随机面内旋转的影响。二维旋转通常被视为干扰参数，计算方法需要考虑这些参数（Singer 和 Sigworth，2020 (https://arxiv.org/html/2607.08987#bib.bib51)）。作为离散对称性的例子，考虑集合结构数据，例如使用邻接矩阵存储的未标记图。尽管顶点没有自然顺序，但它们仍被分配了任意的行/列索引。然而，对矩阵的行和列应用相同的置换会得到相同的图（Zaheer 等，2017 (https://arxiv.org/html/2607.08987#bib.bib77)；Maron 等，2019 (https://arxiv.org/html/2607.08987#bib.bib79)）。

对称感知机器学习的经典方法主要分为两类：数据增强和不变特征。数据增强通过包含每个数据点的变换副本扩大数据集；这在监督学习中广泛使用，并且可以确定性地降低样本复杂度（Chen 等，2020 (https://arxiv.org/html/2607.08987#bib.bib50)）。第二种方法依赖于手工制作的不变特征，例如图像的旋转不变描述符（Lowe，2004 (https://arxiv.org/html/2607.08987#bib.bib13)）或集合的置换不变统计量（Zaheer 等，2017 (https://arxiv.org/html/2607.08987#bib.bib77)）。在无监督设置中，这两种方法都不完全令人满意。数据增强将一个数据点的不同变换视为单独的观测，未能考虑到它们代表同一实例，并且还可能带来显著的内存开销。虽然不变特征在某些情况下有效，但它们不提供能够轻松跨不同领域和对称类型迁移的通用方法。

我们在本文中解决的核心问题是：*对于具有已知对称性的数据集，应该如何进行谱嵌入？*我们不是增强数据，而是提出“增强”亲和核，使得观测被视为等价类的代表。从数学上讲，我们希望通过使用群不变核函数过渡到商流形。图1 (https://arxiv.org/html/2607.08987#S1.F1) 在一个简单示例上说明了这一点。

![图1](https://arxiv.org/html/2607.08987#S1.F1)

图1：群轨道和商流形的示意图。平面环面 \(\mathcal{M}=\mathbb{T}^2\) 被绘制为一个基础正方形，对边等同。群 \(G=\mathbb{S}^1\) 通过 \(a\) 方向平移作用，因此每个水平轨道是一个等价类：\(x\) 和 \(x' = g \cdot x\) 代表同一个商点，而 \(y\) 位于不同的轨道上。商映射 \(\pi: \mathcal{M} \to \mathcal{N} = \mathcal{M}/G\) 将每个水平轨道压缩为 \(b\) 坐标上的一个点。一个 \(G\) 不变亲和核 \(K_G(x,y)\) 是一个实对称函数，仅依赖于 \(G\) 轨道 \([x]\) 和 \([y]\)。

### 1.1 我们的贡献

我们针对已知群 \(G\) 研究了三种广泛适用的群不变亲和核类别：(i) 在 \(G\) 上最小化；(ii) 在 \(G\) 上积分；以及 (iii) \(G\) 不变特征映射。我们分析了连续情况，其中数据位于黎曼流形 \(\mathcal{M}\) 上，对称性由紧致李群 \(G\) 通过等距作用平滑且自由地作用于 \(\mathcal{M}\)。我们的主要理论结果（定理 3.7 (https://arxiv.org/html/2607.08987#S3.Thmtheorem7)）证明，由 \(G\) 不变核构建的图拉普拉斯算子逐点收敛到商空间 \(\mathcal{N} = \mathcal{M}/G\) 上的显式二阶微分算子。关键的是，我们建立了收敛速率的改进：从标准图拉普拉斯收敛到 \(\mathcal{M}\) 上微分算子的速率 \(O(\varepsilon) + O_P\left(n^{-1/2} \varepsilon^{-1/2 - \dim(\mathcal{M})/4}\right)\)（见式 (6) (https://arxiv.org/html/2607.08987#S2.E6)）

\[
O(\varepsilon) + O_P\left(n^{-1/2} \varepsilon^{-1/2 - \mathrm{dim}(\mathcal{M})/4}\right) \qquad \text{(见 Eq.~\eqref{eq:LRW_convergence})} \tag{1}
\]

提升到使用 \(G\) 不变核收敛到 \(\mathcal{M}/G\) 上算子的速率 \(O(\varepsilon) + O_P\left(n^{-1/2} \varepsilon^{-1/2 - (\mathrm{dim}(\mathcal{M}) - \dim(G))/4}\right)\)（推论 3.9 (https://arxiv.org/html/2607.08987#S3.Thmtheorem9)）

\[
O(\varepsilon) + O_P\left(n^{-1/2} \varepsilon^{-1/2 - (\mathrm{dim}(\mathcal{M}) - \dim(G))/4}\right) \qquad \text{(推论~\ref{cor:improved_convergence_rate})} \tag{2}
\]

这反映了通过利用数据中的对称性实现了有效维度降低，类似于监督学习中关于增强的结果（Chen 等，2020 (https://arxiv.org/html/2607.08987#bib.bib50)）。此外，推论 3.15 (https://arxiv.org/html/2607.08987#S3.Thmtheorem15) 表明，当作用的所有轨道具有相同体积时，\(\mathcal{N}\) 上的特征函数与 \(\mathcal{M}\) 上的 \(G\) 不变特征函数之间存在双射。在第5节 (https://arxiv.org/html/2607.08987#S5) 中，我们在具有 \(\mathrm{SO}(2)\) 和 \(\mathrm{SO}(3)\) 对称性的问题上验证了我们的框架，展示了对称感知嵌入及其相较于标准谱方法更好的样本效率和可解释性。

### 1.2 相关工作

**流形学习与谱方法。**流形学习在无监督数据分析中有着悠久的历史。早期的例子包括 Isomap 和 LLE（Tenenbaum 等，2000 (https://arxiv.org/html/2607.08987#bib.bib34)；Roweis 和 Saul，2000 (https://arxiv.org/html/2607.08987#bib.bib83)），它们分别基于近似测地距离和局部线性近似。在本文中，我们考虑谱嵌入，其两种变体是拉普拉斯特征映射（Belkin 和 Niyogi，2003 (https://arxiv.org/html/2607.08987#bib.bib33)）和扩散映射（Coifman 和 Lafon，2006 (https://arxiv.org/html/2607.08987#bib.bib40)）。这些方法使用图拉普拉斯算子的特征向量来获得反映数据内在几何的低维坐标。图拉普拉斯方法的收敛结果由 Belkin 和 Niyogi (2008 (https://arxiv.org/html/2607.08987#bib.bib1))、Hein 等 (2007 (https://arxiv.org/html/2607.08987#bib.bib99)) 和 Singer (2006 (https://arxiv.org/html/2607.08987#bib.bib30)) 建立，改进的速率由 Calder 和 Trillos (2022 (https://arxiv.org/html/2607.08987#bib.bib41)) 以及 Cheng 和 Wu (2022 (https://arxiv.org/html/2607.08987#bib.bib17)) 获得。该理论被 Kileel 等 (2021 (https://arxiv.org/html/2607.08987#bib.bib19)) 和 Xu 与 Singer (2026 (https://arxiv.org/html/2607.08987#bib.bib115)) 扩展到非欧几里得亲和度。谱聚类利用相同的特征向量嵌入进行无监督划分（Ng 等，2001 (https://arxiv.org/html/2607.08987#bib.bib24)；von Luxburg，2007 (https://arxiv.org/html/2607.08987#bib.bib74)）。谱聚类的一致性由 von Luxburg 等 (2008 (https://arxiv.org/html/2607.08987#bib.bib75)) 建立。

**对称感知神经网络。**机器学习越来越多地利用对称性来提高效率和泛化能力。数据增强由 Chen 等 (2020 (https://arxiv.org/html/2607.08987#bib.bib50)) 分析，其中作者证明了在群对称性存在的情况下，添加数据点的变换副本可以降低训练的样本复杂度。不变性对核方法和回归的理论优势分析出现在 Tahmasebi 和 Jegelka (2023 (https://arxiv.org/html/2607.08987#bib.bib82)) 中。等变神经网络通过使用等变卷积层（Cohen 和 Welling，2016 (https://arxiv.org/html/2607.08987#bib.bib76)）、可操纵 CNN（Cohen 和 Welling，2017 (https://arxiv.org/html/2607.08987#bib.bib78)）和/或球面 CNN（Cohen 等，2018 (https://arxiv.org/html/2607.08987#bib.bib84)）直接将对称性纳入神经网络架构。张量场网络（Thomas 等，2018 (https://arxiv.org/html/2607.08987#bib.bib86)）和 SE(3)-Transformer（Fuchs 等，2020 (https://arxiv.org/html/2607.08987#bib.bib87)）处理 3D 点云的旋转和平移等变性，而 E(n) 等变图神经网络（Satorras 等，2021 (https://arxiv.org/html/2607.08987#bib.bib85)）为欧几里得对称性提供了灵活框架。关于深度神经网络置换对称性的工作，请参见 Zaheer 等 (2017 (https://arxiv.org/html/2607.08987#bib.bib77)) 和 Maron 等 (2019 (https://arxiv.org/html/2607.08987#bib.bib79))。几何深度学习与等变架构的综述见 Bronstein 等 (2021 (https://arxiv.org/html/2607.08987#bib.bib80))。

**对称感知谱方法。**Landa 和 Shkolniksy (2018 (https://arxiv.org/html/2607.08987#bib.bib31)) 的可操纵图拉普拉斯是图拉普拉斯的一种对称感知扩展，专门针对具有面内旋转对称性的 2D 图像数据集。该工作通过在亲和度构建中显式包含旋转副本，构建了一个旋转等变算子。与我们设置密切相关的，Rosen 等 (2024 (https://arxiv.org/html/2607.08987#bib.bib20)) 引入了 \(G\) 不变图拉普拉斯，用于数据位于已知李群 \(G\) 作用下的封闭流形上的情况。其构造通过纳入群 \(G\) 在数据集上作用生成的所有点对之间的距离来强制不变性。这相当于隐式（或闭式）数据增强，因为在概念上等同于将 \(G\) 作用生成的无限多个数据点应用于标准图拉普拉斯。与等变神经网络的方法类似，我们将群不变性直接纳入学习方法，而不是依赖数据增强，但这是在谱嵌入的无监督环境中进行的。除了在 \(G\) 上积分，我们还考虑了在 \(G\) 上最小化和对称不变特征映射。近期在 3D 分子中使用旋转不变度量的工作包括 Diepeveen 等 (2024 (https://arxiv.org/html/2607.08987#bib.bib112)) 和 Zhang 等 (2024 (https://arxiv.org/html/2607.08987#bib.bib113))。

## 2 谱嵌入背景

在本文中，\(\mathcal{M} \subseteq \mathbb{R}^D\) 表示一个无边的 \(d\) 维连通紧致黎曼子流形。数据点 \(\mathcal{X} = \{x_1, x_2, \dots, x_n\}\) 从 \(\mathcal{M}\) 上采样，并以 \(\mathbb{R}^D\) 中的向量形式给出。数据流形 \(\mathcal{M}\) 的几何结构通过一个合适的亲和核 \(K: \mathbb{R}^D \times \mathbb{R}^D \to \mathbb{R}\) 来捕获，该核衡量数据点之间的成对相似性。\(K\) 的常见选择是高斯核 \(K(x, y) = \exp(-\|x - y\|^2 / \varepsilon)\) 和 \(0/1\) 核 \(K(x, y) = \mathbf{1}(\|x - y\| \leq \varepsilon)\)，其中 \(\|\cdot\|\) 表示 \(\mathbb{R}^D\) 中的欧几里得范数，\(\varepsilon > 0\) 是带宽参数。参见附录D (https://arxiv.org/html/2607.08987#A4) 了解本文所用符号表。

令 \(W \in \mathbb{R}^{n \times n}\) 为权重矩阵，定义为：
\[
W_{ij} := K(x_i, x_j).
\]