基于自适应谱带宽控制的几何感知图构建

# 基于自适应谱带宽控制的几何感知图构建
来源：https://arxiv.org/html/2609.03306

## 通过自适应谱带宽控制的几何感知图构建
致谢：本文被IEEE MLSP 2026接收。©2026 IEEE。允许个人使用本材料。任何其他用途必须获得IEEE的许可。

###### 摘要
核化图方法——谱聚类、扩散映射和稀疏核回归图——使用高斯核，其性能依赖于高斯带宽σ的选择，该参数控制局部核算子的谱特性。当σ过小时，核会高估局部复杂度，将每个样本视为独立方向；当σ过大时，核会将多个方向合并，条件数发散，所有几何区分能力都会丧失。我们提出一种尺度选择方法，使核的谱复杂度与底层流形的固有复杂度保持一致。我们提出一种逐节点带宽准则，通过联合匹配核的有效秩与通过最小生成树估计的局部本征维度来实现这一原则，将搜索锚定在流形一致的对数-对数缩放区域。我们在CIFAR-100上评估了六种编码器的SSL嵌入，结果表明自适应带宽在留一法分类和标签传播精度方面始终优于固定带宽方法和竞争性自适应方法。

Ecem Bozkurt, Antonio Ortega  
南加州大学电气与计算机工程系  
美国加利福尼亚州洛杉矶  
[email protected], [email protected]

索引术语——图信号处理、流形学习、自监督学习、表示几何、核方法。

## 1 引言

核化图作为谱算子。现代自监督学习编码器产生高维嵌入，作为分类、检索、聚类和基于图的学习等下游任务的输入。一大类基于图的信号处理和学习方法——谱聚类\[24\]、拉普拉斯特征映射\[3\]、扩散映射\[7\]和非负核图\[21\]——通过对成对距离应用高斯核，然后在所得矩阵上操作来构建相似性图。在所有这些方法中，带宽σ是主要的超参数。我们观察到，若不仔细选择σ，核空间中的局部特征（例如通过核矩阵秩估计的几何性质）可能与线性空间的局部性质（例如其局部本征维度）完全不同。局部核矩阵可能根据σ的选择表现出不同的谱特性，这会影响下游任务。

**图1**：局部核算子**K**_SS(σ)的谱区域。  
*左*：σ过小——类似单位阵、平坦谱，r_eff ≈ |S|，图碎片化，无几何信息。  
*中*：σ⋆——衰减谱，r_eff ≈ d̂，良态，几何信息丰富。  
*右*：σ过大——秩一，κ→∞，所有方向坍缩，区分能力丧失。

两种谱失败模式。当σ过小时，高斯核趋近于单位矩阵：每个数据点与其他点正交，有效秩被人为抬高，图变得不连通，谱算子不携带任何有用结构。当σ过大时，核坍缩为秩一矩阵：一个特征值主导，条件数κ发散，图变成密集的团，所有几何区分能力丧失（图1）。这两种情况对下游任务都无用。因此，我们感兴趣的是确定σ应在这两个区域之间的何处选择。

缺失的原则。现有的带宽选择方法处理了部分问题，但遗漏了一个统一原则（表1）。距离驱动方法\[26\]将σ锚定到局部邻居距离，但未考虑所得核的谱特性或高维下距离的不可靠性。密度归一化\[7\]校正了采样偏差，但不针对谱稳定性。对数-对数缩放方法\[22, 17\]利用了一个事实：对于从低维流形采样的数据，总核质量随带宽遵循可预测的缩放律。该关系的斜率可用于估计流形维数，并识别核提供底层几何忠实近似的尺度。Lindenbaum等人\[17\]进一步选择其隐含维度与外部本征维度估计相匹配的带宽。然而，这些方法为整个数据集估计单一全局尺度，而不适应密度或几何的局部变化。这些方法都没有通过询问*谱复杂度*（核算子解析的独立方向的有效数量，通过所得核的有效秩度量）是否与局部邻域的*几何复杂度*（局部数据流形的本征维度）一致来选择σ。

谱复杂度原则。为避免因不当选择σ而导致的谱失败模式（图1），我们假设：*当一个核在其谱中揭示的复杂度与局部数据流形的固有复杂度相当时，该核就在正确的尺度上运行*。

与近期观察的联系。三个最近的结果从不同方向支持这一原则。RankMe\[11\]确立有效秩——归一化特征值分布的熵——量化了表示中的活跃谱自由度数量。IDEST\[19\]表明基于最小生成树的本征维度能够跟踪经典估计器失效的高维、低样本区域中的几何结构。T-REGS\[18\]证明MST几何可以直接正则化并防止谱坍缩。这些结果共同表明，谱复杂度和本征维度都携带关于表示几何的有意义信息。因此，我们使用有效秩作为核可见复杂度的度量，使用本征维度作为流形复杂度的度量，并寻求两者在局部一致的带宽。

**贡献**：我们提出（i）一个逐节点带宽准则，用于选择核的有效秩与局部本征维度匹配的尺度，使核算子处于信息丰富的区域；（ii）经验证据表明，σ自适应改善了稀疏和密集图构建的基于图的推理，并且dimMST是距离集中下合适的复杂度目标。

## 2 相关工作

表1：带宽选择策略。核图算子的带宽选择。

与我们的工作最接近的是Lindenbaum等人\[17\]，其中选择了全局带宽和特征缩放矩阵，以使核隐含维度与外部估计匹配。我们的准则共享维度匹配的精神，但区别在于（i）它应用于*每个节点*，（ii）它使用有效秩而非核隐含维度作为谱度量，（iii）它使用dimMST\[19\]估计本征维度，该方法对影响作用于高维ℓ₂归一化嵌入的方法的距离集中具有鲁棒性。

非负核图。NNK图\[21\]通过核域中的非负二次规划移除冗余邻居，同时保留局部结构，这可以解释为线性空间中的几何条件。在这些用于研究SSL和LLM几何\[8, 1, 14\]的方法中，σ被视为外部超参数。相比之下，我们专注于选择带宽本身，保持NNK优化不变。虽然我们测试我们的σ选择准则来构建NNK图，但其基本思想更具普遍性：选择σ通过核权重调整邻居的相对重要性，因此是邻域选择的一种形式，无论邻域是显式定义（如NNK）还是通过权重衰减隐式定义（如k-NN）。

有效秩和本征维度。我们使用有效秩\[20\]作为谱复杂度度量：它是连续的、基于熵的，并且捕获信息在所有特征值方向上分布的均匀程度——不同于仅依赖二阶统计量的参与比或对小特征值敏感的原始秩。其在RankMe\[11\]中的最新应用进一步证实，有效秩是核算子解析多少有意义方向的可靠指标。另一方面，嵌入的本征维度表示线性空间中存在多少几何相关方向。我们使用基于MST的本征维度\[19\]，它在比Levina-Bickel\[16\]或TwoNN\[10\]更弱的假设下被证明是一致的，并且在距离集中下仍然有效。

## 3 方法

### 3.1 带宽问题的谱表征

对于节点**x**_j，具有候选邻居S_j且**x**_k ∈ S_j，定义局部高斯核矩阵**K**_SS(σ)，其元素为**K**_jk = exp(−∥**x**_j − **x**_k∥²/(2σ²))。本征维度d̂描述了局部数据流形中存在多少独立方向，直接作用于**x**_i，而有效秩r_eff(**K**_SS(σ))描述了在给定σ下核算子实际解析了多少独立方向。当这两个量不一致时，核被错误指定（见图1）：如果r_eff > d̂，核解析的方向多于流形拥有的方向，将噪声和环境维度视为真实结构，导致图沿虚假方向碎片化。在两种情况下，这种不匹配都会破坏图的几何保真度。

目标区域。我们寻求一个工作点，其中核看到的复杂度与流形提供的一致，即r_eff(**K**_SS(σ⋆)) ≈ d̂，其中**K**_SS(σ)解析约d̂_i个独立方向，匹配局部邻域的本征维度（见图1中）。在此区域中，条件数κ适中，图是良态的，谱算子捕获流形的局部几何。接下来，我们介绍用于优化σ的局部度量。

### 3.2 局部邻域度量

有效秩。我们使用**K**_SS(σ)的有效秩\[20\]：r_eff(**K**) = exp(−∑_j p_j log p_j)，其中p_j = λ_j / ∑_k λ_k。从信号处理的角度来看，r_eff量化了核算子表示的活跃谱自由度的数量：r_eff = 1表示秩一算子（所有能量在一个方向）；r_eff = |S|表示均匀算子（无主导方向）。目标是r_eff ≈ d̂_i：核应解析与局部流形相同数量的独立方向。

本征维度和流形复杂度。我们使用基于最小生成树的估计器（dimMST）\[19\]在k_cand邻域上估计局部本征维度d̂_i。最近邻估计器如Levina-Bickel\[16\]和TwoNN\[10\]依赖于点间距离的比率；在ℓ₂归一化嵌入上，这些比率失去对比度，并且在高维下距离集中时估计器变得不稳定。dimMST估计器依赖于生成树的增长率而非成对距离对比度。IDEST\[19\]表明dimMST在n ≈ d区域跟踪SSL表示质量，而TwoNN和MLE失败。我们的结果（图2）证实了这一点：dimMST与所有六个编码器在σ⋆处的r_eff对齐程度显著优于Levina-Bickel。

流形缩放一致性和对数-对数斜率。遵循Singer\[22\]和Lindenbaum\[17\]，在d̂维流形上，总核能量L_i(σ) = ∑_{j,k∈S_i} **K**_jk(σ)满足log L_i ≈ (d̂/2) log σ + C，在流形一致区域内。令ℓ_i(σ) = d log L_i(σ) / d log σ表示节点i处总核能量的对数-对数斜率，ℓ_max = max_{σ∈𝒢_i} ℓ_i(σ)表示局部带宽网格上的峰值斜率。我们计算ℓ_max = max_σ ℓ_i(σ)以定位一致缩放区域的峰值。它惩罚落入此线性区域之外的带宽。

### 3.3 带宽优化准则

为实现我们期望的带宽目标，我们组合先前引入的度量来定义最优性准则：

J_i(σ) = \underbrace{\frac{|r_{\mathrm{eff}}(\mathbf{K}_{SS}(\sigma)) - \hat{d}_i|}{\hat{d}_i}}_{\text{谱} \leftrightarrow \text{流形复杂度}} + \underbrace{\frac{\ell_{\max} - \ell_i(\sigma)}{\ell_{\max}}}_{\text{缩放一致性}}