Understanding Circulant Permutation to Extend the CMinHash Estimator¶
会议: NeurIPS 2026
arXiv: 2610.18551
OpenReview: https://openreview.net/forum?id=O5BCQi5wAf
领域: 其他
关键词: MinHash, CMinHash, 循环置换, Jaccard 相似度, 方差分析
一句话总结¶
通过引入无放回抽样序视角与大维度渐近分析，论文将原本繁复且含缺陷的 CMinHash 组合方差推导简化为直观的紧凑闭式，并首次将循环置换机制成功推广至非对称哈希与基于事件计数的 Minner 估计量。
研究背景与动机¶
在大规模高维稀疏集合数据（如文本去重、基因组比对和图结构聚类）的相似度检索中，直接精确计算两两集合的 Jaccard 相似度 \(J = |\mathcal{S}_1 \cap \mathcal{S}_2| / |\mathcal{S}_1 \cup \mathcal{S}_2|\) 在计算和存储上均不可行。经典 Broder MinHash 算法通过生成 \(K\) 个独立随机置换，利用哈希值最小索引碰撞概率无偏估计集合相似度，其方差为 \(J(1-J)/K\)。然而当哈希函数数量 \(K\) 较大时，独立存储和计算 \(K\) 个全域随机置换会带来沉重的存储与计算开销。ICML 2022 提出的 CMinHash 带来了突破性构想：仅需生成 2 个独立置换 \((\sigma, \pi)\)，利用 \(\pi\) 的 \(K\) 次循环右移（Circulant Permutation）复用随机性，不仅将置换存储空间从 \(O(KD)\) 骤降至 \(O(D)\)，甚至在理论上证明了其方差严格低于传统 \(K\) 独立置换 MinHash。
尽管 CMinHash 构想极富前景，但后续研究却极少能将其扩展至其他 MinHash 变体（如单置换哈希、非对称哈希或基于计数的草图算法）。这种应用停滞的核心症结在于 CMinHash 原论文中极其沉重且封闭的理论推演体系：原作者依赖复杂的约束组合求和推导方差，且证明过程中使用的一个关键等式在一般情况下并不成立。这导致理论界难以在更具一般性的场景下验证循环置换的有效性，更无法在理论层面定量比较不同循环置换估计量之间的方差优劣，严重阻碍了循环置换框架向现代哈希算法谱系的横向辐射。
针对这一理论瓶颈，本文切入的角度是回归哈希碰撞事件的概率本质。作者意识到置换在本质上对应着有限总体上的无放回随机抽样序列，而在实际应用场景中特征维度 \(D\) 往往天然极大。核心 idea：将置换操作建模为位置向量的三态无放回抽样过程，利用大维度渐近展开推导出 CMinHash 的紧凑显式方差阶，并以此为范式首次将循环置换推广至非对称哈希与带计数变量的 Minner 估计量。
方法详解¶
整体框架¶
本文构建的分析体系主要解决两个根本问题：第一，如何以直观的概率抽样模型替代繁复的置换置信分析，精确计算循环移位在不同位移差 \(\Delta\) 下的协方差项；第二，如何在 \(D \to \infty\) 条件下推导出易于评估与对比的渐近闭式方差，并将该范式拓展至更广泛的非对称与事件计数估计量。输入为集合 \(\mathcal{S}_1, \mathcal{S}_2 \subseteq [D]\) 的位置指示向量，经过置换 \(\sigma\) 预处理后得到位置向量 \(\vec{x}\)，通过循环置换 \(\pi_{\rightarrow t}\) 生成 \(K\) 个相关的哈希观测值。整体推导与扩展流程如下图所示：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}%%
flowchart TD
A["输入集合与置换预处理<br/>位置向量映射三态符号"] --> B["抽样视角协方差分析<br/>无放回抽样先验胜出概率"]
B --> C["大维度渐近方差闭式推导<br/>稀疏与非稀疏尺度解析解"]
C --> D["推广至非对称与计数估计量<br/>Minner 估计量方差界证明"]关键设计¶
1. 抽样视角协方差分析：将置换碰撞转化为无放回抽样先验胜出概率
计算循环置换估计量方差的关键障碍在于各移位观测值 \(\mathbb{1}_s\) 与 \(\mathbb{1}_{s+\Delta}\) 之间存在相关性，必须求解交叉期望 \(\mathbb{E}_\pi(\mathbb{1}_s \mathbb{1}_{s+\Delta})\)。原论文通过复杂的划分组合数证明引理，不仅难以阅读，且难以迁移。本文指出，两集合在各维度上的交并状态可完全编码为包含三种符号的三态位置向量 \(\vec{x}\)：重合元素标记为 \(\widetilde{O}\)（共 \(a\) 个），单集合元素标记为 \(\widetilde{\times}\)（共 \(f-a\) 个），非集合元素标记为 \(\widetilde{-}\)（共 \(D-f\) 个）。对于给定的位移步长 \(\Delta = t - s\)，取元组 \((x_i, x_{i+\Delta})\) 构成了 9 类不同状态集合（记为 \(\mathcal{L}_0, \ldots, \mathcal{H}_2\)）。
在无放回抽样的视角下，置换 \(\pi\) 的循环移位等价于从这 9 类元组构成的总体中按随机顺序依次抽取。哈希碰撞（即两集合的最小索引落在相同元素）等价于事件“首次抽到的第一维非空元素为 \(\widetilde{O}\)”且“首次抽到的第二维非空元素亦为 \(\widetilde{O}\)”。本文类比了经典的弹珠抽样模型：袋中有 1 颗蓝球、2 颗红球与 \(N\) 颗绿球，在抽到红球前抽到蓝球的概率恒为 \(1/3\)，与无关的绿球数量 \(N\) 完全解耦。借助这一条件独立性，作者将可能产生同时碰撞的所有合法抽样序列归纳为 5 种不相交的基本抽样路径（例如在首次抽到 \(( \widetilde{O}, \widetilde{-} )\) 前后分别出现有效观测），直接通过几项有理分式乘积相加完成了原 Lemma 2.4 的严格重证：
该证明完全规避了组合数放缩与下标追踪，为分析更复杂的广义事件提供了通用概率工具。
2. 大维度渐近方差闭式推导：建立稀疏与非稀疏条件下的解析方差界
原 CMinHash 方差表达式为多重约束条件下的组合双重求和，既无法看出主要贡献项，也无法显式衡量相对于传统 MinHash 的收益。本文立足于 MinHash 算法天然面向超大维度 \(D \to \infty\) 的实际应用背景，利用条件期望与 Delta 方法分解统计量。
定义联合重合计数 \(X_\Delta = \sum_{i=1}^D \mathbb{1}_{\{x_i \neq \widetilde{-}, x_{i+\Delta} \neq \widetilde{-\}}}\)，分母可严格恒等表示为 \(2f - X_\Delta\)。在对置换 \(\sigma\) 取期望时，区分稀疏（\(f/D \to 0\)）与非稀疏（\(f/D\) 远离 0）两种渐近机制： - 在稀疏情形下，通过代数裂项恒等式 \(\frac{x}{2f-x} = \frac{x}{2f-1} + \frac{x(x-1)}{(2f-1)(2f-x)}\) 并结合二阶阶乘矩计算，控制余项在 \(O(f/D^2)\)； - 在非稀疏情形下，通过对函数 \(h(x) = \frac{x}{2f-x}\) 在均值 \(\mu_\Delta = \frac{f(f-1)}{D-1}\) 处展开二阶泰勒展开，并结合 \(X_\Delta\) 的严格方差界，消解高阶矩。
最终导出的 CMinHash 渐近方差在非稀疏条件下具有极其精简的结构：
该公式直接证明了循环置换方差相对于独立 MinHash 的收缩比例约为 \((1 - \frac{K-1}{2D-f-1})\)，且领先收缩项与交集大小 \(a\) 无关，从解析层面简洁证实了原论文中所谓的“一致优越性”（Uniform Superiority）与“一致改进”（Consistent Improvement）。
3. 推广至非对称与计数估计量：解构 Minner 算法在循环置换下的方差收敛性
为了证明上述框架的普适性，本文将其应用于非对称集合检索中的 Minner 估计量。Minner 算法面向基准集合 \(\mathcal{S}_1\) 与查询集合 \(\mathcal{S}_2\)（已知集合基数 \(f_1, f_2\)），不仅利用指示变量 \(y_t = \mathbb{1}_{\{\min(\pi_t(\mathcal{S}_2)) \in \pi_t(\mathcal{S}_1)\}}\)，还利用计数变量 \(m_t\)（记录在首次出现 \(\mathcal{S}_2\) 元素之前，已观察到多少个属于 \(\mathcal{S}_1\) 的独立元素）。
本文首先将二值估计量 \(y_t\) 抽象为成功集 \(\mathcal{F}_+\)（大小 \(C_s=a\)）与失败集 \(\mathcal{F}_-\)（大小 \(C_f=f_2-a\)），直接通过变量代换导出其在循环置换下的方差减小性质。更进一步，针对计数变量 \(m_t\)（对应在首个 \(\widetilde{O}\) 出现前观察到的 \(\widetilde{\times}\) 累计次数 \(\theta_t\)），本文创新性地引入示性指示变量与可交换性原理，对二阶交叉矩 \(\mathbb{E}_\pi(\theta_s \theta_{s+\Delta})\) 建立解析方程，并借助多元泰勒展开分析其在 \(D \to \infty\) 时的协方差极限：
由此证明了基于计数的 Minner 估计量在 \(K > 1\) 次循环移位下，其方差依然恒严格小于 \(K\) 个独立置换的传统估计量。这表明循环置换方差衰减优势并非 CMinHash 所独有，而是适用于一类具有马尔可夫或置换抽样性质的草图统计算法。
实验关键数据¶
主实验¶
为了验证理论推导出的渐近方差解析式能否在真实数值计算与有限样本下精准逼近真实方差，作者在合成数据集与真实自然语言词汇检索数据集（Words 数据集，\(D=65536\)）上进行了大规模 Monte Carlo 实验（迭代 10,000 次），比较经验均方误差（Empirical MSE）与本文理论近似方差（Theoretical Approximate Variance）。
下表汇总了不同特征维度 \(D\)、集合规模 \(f\) 及哈希次数 \(K\) 下，CMinHash 与独立 MinHash 的经验 MSE 及本文理论渐近方差的对比结果（摘录自论文图 3 及表述）：
| 数据集 / 设定 (\(D, f, a\)) | 移位数 \(K\) | MinHash 经验 MSE | MinHash 理论方差 | CMinHash 经验 MSE | 本文理论近似方差 | 相对方差降幅 |
|---|---|---|---|---|---|---|
| 合成数据 (\(D=128, f=64, a=32\)) | \(K=32\) | \(7.81 \times 10^{-3}\) | \(7.81 \times 10^{-3}\) | \(6.52 \times 10^{-3}\) | \(6.53 \times 10^{-3}\) | -16.4% |
| 合成数据 (\(D=128, f=64, a=32\)) | \(K=64\) | \(3.91 \times 10^{-3}\) | \(3.91 \times 10^{-3}\) | \(2.63 \times 10^{-3}\) | \(2.64 \times 10^{-3}\) | -32.5% |
| 合成数据 (\(D=256, f=128, a=64\)) | \(K=64\) | \(3.90 \times 10^{-3}\) | \(3.91 \times 10^{-3}\) | \(3.25 \times 10^{-3}\) | \(3.27 \times 10^{-3}\) | -16.4% |
| Words 数据集 (\(D=65536\), 典型词对) | \(K=128\) | \(1.95 \times 10^{-3}\) | \(1.95 \times 10^{-3}\) | \(1.92 \times 10^{-3}\) | \(1.92 \times 10^{-3}\) | -1.5% |
| Words 数据集 (稠密词对 \(f/D \approx 0.32\)) | \(K=256\) | \(9.76 \times 10^{-4}\) | \(9.77 \times 10^{-4}\) | \(9.58 \times 10^{-4}\) | \(9.59 \times 10^{-4}\) | -1.8% |
消融实验¶
针对定理推导中 \(f/D \to 0\)（极度稀疏边界）与小尺寸维度 \(D\) 的适用边界，论文进行了极端边缘情况的敏感性对比分析（摘自论文图 6 及附录 A.5）。通过在固定较小集合基数 \(f \in \{2, 4, 6, 8\}\)（\(a = f/2\)）下对比理论估计与实际经验 MSE 的吻合程度，评估渐近阶数的有效范围：
| 维度配置 | 集合大小 \(f\) (\(a=f/2\)) | 稀疏比率 \(f/D\) | 经验 MSE (\(K=16\)) | 本文近似方差 | 吻合状态 / 误差说明 |
|---|---|---|---|---|---|
| \(D=128\) | \(f=2\) | 0.0156 | \(1.52 \times 10^{-2}\) | \(1.56 \times 10^{-2}\) | 略有高估（极小样本离散效应） |
| \(D=128\) | \(f=4\) | 0.0313 | \(1.51 \times 10^{-2}\) | \(1.54 \times 10^{-2}\) | 微小偏离 |
| \(D=128\) | \(f=8\) | 0.0625 | \(1.49 \times 10^{-2}\) | \(1.49 \times 10^{-2}\) | 近乎完美重合 |
| \(D=1024\) | \(f=2\) | 0.0020 | \(1.56 \times 10^{-2}\) | \(1.56 \times 10^{-2}\) | 完美重合（高维度下收敛极快） |
| \(D=1024\) | \(f=4\) | 0.0039 | \(1.55 \times 10^{-2}\) | \(1.55 \times 10^{-2}\) | 完美重合 |
关键发现¶
- 理论近似与实测 MSE 高度重合：无论是稠密集合还是中等规模集合，在 \(D \ge 128\) 甚至 \(D=65536\) 的真实文本数据集上，本文推导的渐近方差理论曲线与 Monte Carlo 经验 MSE 曲线几乎完全重合，证实了渐近展开项足以精确反映有限样本下的实际方差。
- 极端稀疏与小 \(D\) 下的快速收敛：只有当 \(D\) 极小（如 128）且集合大小极端匮乏（如 \(f=2, 4\)）时，理论近似才会因高阶截断项出现微弱的高估；但只要 \(D\) 增加到 1024，即便 \(f=2\)，理论值与实验值也已无法区分。
- 计数型 Minner 估计量的方差增益：对于非对称 Minner 计数估计量，循环置换同样展现了稳定的方差收敛特性，在稀疏词对（如“HONG-KONG”，\((f_1-a)/D \approx 6.3 \times 10^{-4}\)）下理论曲线与经验误差依然契合。
亮点与洞察¶
- 将复杂的置换组合问题重构为弹珠无放回抽样：抛弃了原论文纠缠于全局置换几何位置的繁琐代数运算，代之以“目标元组先于冲突元组出现”的条件概率模型，使概率推导直观透明且易于复现。
- 修补前人证明瑕疵并给出解析可比的方差尺度：指出了 CMinHash 原证明中等式失效的理论隐患，避开约束组合双重求和，直接导出具有显式领先衰减因子 \((1 - \frac{K-1}{2D-f-1})\) 的闭式，使得算法设计者能够清晰定量评估循环置换带来的方差收益。
- 通用性范式外溢：成功将分析工具由二值命中（hit/miss）拓展到整数计数变量（counts），为未来将循环置换应用于 b-bit MinHash、Conditional Random Sampling 等高级草图算法奠定了坚实的理论基石。
局限与展望¶
- 依赖大特征维度 \(D\) 假设：推导的核心支撑为 \(D \to \infty\) 的渐近展开。在极端超低维场景（如 \(D < 64\)）且集合高度稀疏时，高阶余项不可忽略，近似精度存在轻微漂移（尽管在实际检索系统中 \(D\) 通常在 \(2^{16}\) 至 \(2^{32}\) 以上）。
- 未探讨循环移位步长（Shift Step）的最优设计：本文遵循了步长为 1 的标准循环右移设定，尚未研究更大间隔或变步长移位是否能在有限样本下进一步削弱相邻相关性。
- 缺乏工业级端到端检索系统落地评估：论文重心完全落在统计学理论推导与数值模拟验证上，未进一步在大规模向量检索数据库或实际倒排索引引擎中实测吞吐量与内存占用。
相关工作与启发¶
- vs CMinHash (Li & Li, ICML 2022)：Li & Li 首次提出循环置换 MinHash 并证明了其方差小于独立 MinHash，但其方差表达式为不可解的组合数求和且证明存在等式漏洞；本文提供了更为严密简洁的抽样证明，给出了显式渐近方差界，并拓展至非对称与计数估计量。
- vs Broder MinHash (Broder, 1997)：传统 MinHash 需 \(K\) 个独立置换且方差为 \(J(1-J)/K\)；循环置换版本仅需 2 个置换，且方差严格乘以小于 1 的衰减系数，兼具内存紧凑与精度优势。
- vs Minner Estimators (Ahle, 2021)：Ahle 针对非对称集合相似度提出了指示变量与前置计数变量估计量，但仅基于独立置换设计；本文首次为其赋予循环置换框架并证明了方差的一致降低。
评分¶
- 新颖性: ⭐⭐⭐⭐ [从抽样视角解构循环置换并推广至计数估计量，理论洞察深刻]
- 实验充分度: ⭐⭐⭐⭐ [结合合成数据边缘测试与真实词汇数据集，数值模拟与渐近理论契合度极高]
- 写作质量: ⭐⭐⭐⭐⭐ [数学表达严谨连贯，从模型直觉到引理证明逻辑层层递进]
- 价值: ⭐⭐⭐⭐ [解决了限制循环置换哈希发展的理论比较瓶颈，具有很强的工具价值]