Two-Sample Hypothesis Testing for Subspace Equality in Network Data¶
作者: Rajdeep Brahma, Joshua Agterberg, Yuguo Chen
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://arxiv.org/abs/2606.06482
一、领域脉络与小综述¶
这个方向是什么： 网络数据的两样本假设检验旨在判断两个观测网络是否由相同的潜在结构生成。在低秩随机图模型（如随机块模型 SBM、混合隶属度块模型 MMSBM、广义随机点积图 GRDPG）下，核心统计问题是如何基于带噪的邻接矩阵，推断两个网络的概率矩阵是否共享相同的列空间（即潜在子空间），同时不受边概率全局密度波动（nuisance parameter）的干扰。当前该方向处于理论渐近分布与可行推断初步建立、但稀疏设定与计算受限下界尚未完全闭合的阶段。
发展脉络： - 奠基工作：Tang et al. (2017b) 建立了基于随机点积图（RDPG）的非参数两样本检验框架，检验潜在位置是否相等；Agterberg et al. (2020) 将其推广至含负或重复特征值的 GRDPG。这些工作依赖置换检验，未给出封闭渐近分布。 - 主要进展： - 子抽样/重抽样路线：Chakraborty et al. (2025)、Lunde and Sarkar (2023)、Deng et al. (2024)、Zu and Qin (2025) 利用子抽样构造检验统计量；Bhadra et al. (2025)、Levin and Levina (2025) 采用 Bootstrap。这些方法计算开销大，渐近理论依赖重抽样近似。 - 高阶矩/U-统计量路线：Bravo-Hermsdorff et al. (2023)、Shao et al. (2023)、Zhang and Xia (2022) 利用图累积量或 U-统计量；Shen and Lu (2020) 研究组合-概率权衡。这些方法往往需要匹配高阶矩，计算复杂。 - 矩阵范数/极值路线：Chatterjee et al. (2023)、Ghoshdastidar et al. (2020) 基于矩阵范数；Fu et al. (2022) 基于块概率最大标准化偏差的极值检验，但依赖社区恢复的一致性。 - 谱投影极限定理路线：Xia (2021) 与 Bao et al. (2021) 给出了奇异子空间投影距离的正态近似，但假设 i.i.d. 高斯噪声；Fan et al. (2022a)、Zheng and Tang (2024)、Liu et al. (2025) 给出单个特征向量的极限定理；Agterberg (2024)、Cheng et al. (2021) 处理小特征间隙与不对称性。 - 当前 frontier 与本文位置：现有谱推断多针对单个特征向量（局部）或假设高斯噪声（全局）。本文首次在异方差 Bernoulli 噪声下，直接对全局子空间投影矩阵差的 Frobenius 范数建立渐近正态极限定理，并给出封闭的均值/方差表达式与一致估计量，无需重抽样或高阶矩计算。
子线索聚类： 1. 非参数/重抽样推断：Tang et al. (2017b), Agterberg et al. (2020), Chakraborty et al. (2025), Bhadra et al. (2025) 等。依赖置换或子抽样，计算密集，渐近 pivot 不封闭。 2. 矩方法/U-统计量：Bravo-Hermsdorff et al. (2023), Shao et al. (2023), Zhang and Xia (2022)。需计算图累积量或高阶 U-统计量，理论复杂度高。 3. 谱扰动与极限定理：Xia (2021), Bao et al. (2021), Fan et al. (2022a), Agterberg (2024)。多为高斯噪声或单向量极限，本文填补 Bernoulli 噪声下全局投影距离极限定理的空白。
核心追问与瓶颈： 1. 如何在异方差 Bernoulli 噪声下，对子空间投影差建立封闭的渐近分布，而非依赖重抽样？ 2. 如何使检验对边概率全局密度波动稳健，只对子空间结构差异敏感？ 3. 在多稀疏设定（\(n\rho_n \gg \log n\)）下，渐近正态是否成立？估计量一致性需要多密（\(n\rho_n \gg \sqrt{n}\)）？ 4. 局部功效的分离率（separation rate）是什么？在 SBM/MMSBM 下对应多大的社区结构差异？
⚠️ 作者的 framing： - 作者将缺口 frame 为：现有非参数/重抽样方法计算密集且无封闭分布；现有谱极限定理多针对高斯噪声或单向量；因此，直接在 Bernoulli 噪声下对全局投影距离建立渐近正态是"显然的下一步"。 - 被淡化或回避的竞争路线：基于矩阵范数的检验（Chatterjee et al. 2023, Ghoshdastidar et al. 2020）在更稀疏设定下可能有不同分离率，作者未对比；极值检验（Fu et al. 2022）在社区恢复后对局部偏差敏感，作者强调全局投影距离的稳健性但未讨论局部检验的互补性。 - 明显该引但未出现的文献：针对常数平均度（\(n\rho_n = O(1)\)）极稀疏网络的谱检验或下界文献（如极稀疏 SBM 的检测阈值文献）未在 intro 出现，这可能是因为作者的理论要求 \(n\rho_n \gg \log n\)，回避了极稀疏设定。
张力： 未见明显对立引用。不同路线（重抽样 vs 矩 vs 谱极限）在不同设定下各有优势，本文的理论在 \(n\rho_n \gg \log n\) 下给出封闭分布，但更稀疏设定下的可行性未被讨论，与极稀疏文献可能存在设定上的张力。
二、这篇论文做了什么¶
三句话： ①研究了两个网络是否共享相同潜在子空间（列空间相等）的假设检验问题，涵盖 SBM 与 MMSBM 的社区结构相同但边概率不同的情形。 ②核心工具是基于两个网络领先子空间投影矩阵之差的 Frobenius 范数构造检验统计量，并利用特征向量扰动的矩阵级数展开与鞅中心极限定理推导其渐近正态性。 ③主要结论是在平均期望度至少随节点数对数增长（\(n\rho_n \gg \log n\)）时，适当中心化与尺度化后统计量依分布收敛至高斯变量；在更密条件（\(n\rho_n \gg \sqrt{n}\)）下给出一致估计量与局部功效分析，分离率为 \(\|V^{(1)}V^{(1)\top} - V^{(2)}V^{(2)\top}\|_F^2 \gg k/(n^{3/2}\rho_n)\)。
关键设定与假设： - 模型：\(A^{(i)} \sim \text{Ber}(P^{(i)})\)，\(P^{(i)}\) 为 \(n \times n\) 对称低秩矩阵，秩 \(k\) 固定，\(P^{(i)} = V^{(i)}\Lambda^{(i)}V^{(i)\top}\)。 - 假设检验：\(H_0: V^{(1)}V^{(1)\top} = V^{(2)}V^{(2)\top}\) vs \(H_1: V^{(1)}V^{(1)\top} \neq V^{(2)}V^{(2)\top}\)。在 GRDPG 下等价于潜在位置矩阵列空间相同（Proposition 1）；在 SBM/MMSBM（含纯节点）下等价于社区隶属矩阵置换等价（\(Z^{(1)} \cong Z^{(2)}\)）（Proposition 2）。 - Assumption 1（渐近 regime）：\(a\rho_n \leq P_{ij} \leq b\rho_n\)，\(\rho_n \to 0\)，\(k\) 固定。统计含义：边概率均匀稀疏，秩固定。 - Assumption 2（稀疏 regime）：\(n\rho_n \gg \log n\)。统计含义：网络以高概率连通，投影距离可收敛；比极稀疏（常数平均度）强，但为推断而非估计的最低要求。 - Assumption 2'（密 regime）：\(n\rho_n \gg \sqrt{n}\)。统计含义：保证 plug-in 估计量一致性，是检验可行性的充分条件。 - Assumption 3（特征值 scaling）：\(C_i < |\lambda_i|/(n\rho_n) < D_i\)。统计含义：特征值与稀疏参数同阶，保证信号强度与噪声可分离；在平衡社区 SBM/MMSBM 下自动满足（Proposition 3）。 - Assumption 4（Incoherence）：\(\sqrt{\psi_1 k/n} \leq \|V_{j\cdot}\|_2 \leq \sqrt{\psi_2 k/n}\)，\(|(VV^\top)_{ij}| \asymp k/n\)。统计含义：特征向量行范数均匀，避免少数节点主导；在平衡社区 SBM/MMSBM 下由社区平衡性推出（Lemmas 20, 21）。 - 相比已有文献：放宽了 Xia (2021) 的 i.i.d. 高斯噪声假设至异方差 Bernoulli；放宽了 Tang et al. (2017a) 的置换检验需求至封闭渐近分布；但稀疏条件（\(n\rho_n \gg \log n\)）比极稀疏文献强，密条件（\(n\rho_n \gg \sqrt{n}\)）为估计一致性所需。
主要结果： - Theorem 1（两样本渐近正态，稀疏 regime）：在 Assumptions 1-4 下，\(H_0\) 成立时，
证明路线与技术技巧： - 整体路线： 1. 矩阵级数展开：利用 Xia (2021) 的 Theorem 1，在事件 \(E_{\text{good}}\)（\(\|X\| \lesssim \sqrt{n\rho_n}\)）下，将投影差 \(\hat{V}\hat{V}^\top - VV^\top\) 展开为噪声矩阵 \(X\) 的多项式级数 \(S_l(X)\)，分离二阶项 \(T_1^{(S)} = 2\|\beta^\perp X \beta^{-1}\|_F^2\) 与高阶项。 2. 二阶项渐近分布：证明 \(T_1^{(S)}\) 经中心化与尺度化后服从渐近正态。关键步骤：将 \(T_1^{(S)}\) 重写为鞅差阵列之和，验证条件方差发散与 Lyapunov 条件（四阶矩可忽略），应用鞅 CLT（Bai and Silverstein 2010, Lemma 9.12）。 3. 高阶项控制：证明三阶项均值 \(o(k/(n^2\rho_n^2))\)，方差 \(O(k^2/(n^4\rho_n^3))\) 相对二阶项方差 \(O(k^2/(n^3\rho_n^2))\) 可忽略；四阶及以上项在 \(E_{\text{good}}\) 下范数 \(O_p(k/(n^2\rho_n^2))\)，可被中心化/尺度化吸收。 4. 两样本推广：两样本统计量分解为两个单样本投影差平方减去交叉项，二阶项重写为块矩阵二次型，同样应用鞅 CLT；交叉项方差由独立性与条件期望控制。 5. 估计量一致性：将 plug-in 误差分解为特征向量/特征值扰动与 \(\Sigma\) 估计误差的级数展开，逐项用 \(\ell_{2,\infty}\) 范数扰动界（Agterberg et al. 2025, Lemma C.6）与 Bernstein 不等式控制，在 Assumption 2' 下余项可忽略。 - 关键跳跃点： - Lemma 4/9（鞅 CLT）：将二次型 \(\|\beta^\perp X \beta^{-1}\|_F^2\) 重写为按上三角元素顺序揭示的鞅差阵列，计算条件方差 \(\eta\) 的期望与方差，验证 \(E[\eta]/\sqrt{\text{Var}(\eta)} \gg 1\) 与 \(E[\eta] \to \infty\)。难点在于系数 \(b_{ri}, c_{ri}\) 的矩估计与条件方差四阶矩的控制，需精细计数。 - Lemma 2/7（方差近似）：证明 \(\text{Var}(\|\beta^\perp X \beta^{-1}\|_F^2) / \text{Var}(\|X\beta^{-1}\|_F^2) \to 1\)，即投影 \(\beta^\perp\) 不改变主导方差阶。难点在于 \(\beta^\perp\) 引入的交叉项需用 Incoherence 控制为低阶。 - Lemma 6/11（三阶项方差）：证明三阶项方差相对二阶项可忽略。难点在于异方差 Bernoulli 下，需将三阶迹展开为索引配置，识别"完全分离"单项（主导方差）与含 \(VV^\top\) 的余项（低阶），用 Incoherence 与索引计数控制。 - 技术技巧点名： - 矩阵级数展开（Xia 2021 Theorem 1）：用于将投影差展开为噪声多项式，分离二阶与高阶项。 - 鞅中心极限定理：用于二阶项的渐近正态证明，按上三角元素顺序构造鞅差阵列。 - Bernstein 不等式：用于控制线性项与估计量误差的集中。 - \(\ell_{2,\infty}\) 范数扰动界（Agterberg et al. 2025）：用于控制经验特征向量的行范数扰动，保证 Incoherence 在经验版本下成立（\(E_{\text{very good}}\)）。 - Davis-Kahan 界：用于控制投影差范数的初步界（Lemma 1）。 - 索引配置计数：用于高阶迹的方差计算，识别主导配置与低阶配置。 - Hadamard 积与对角校正：用于精确计算 Bernoulli 噪声下二次型的均值与方差（\(\Sigma \circ \beta^\perp + \text{Diag}(\Sigma \cdot d - \text{diag}(\Sigma) \circ d)\)）。
真实例子与应用： - US Flight 数据：\(n=343\) 机场，\(T=69\) 月（2016-01 至 2021-09），每月一个二值网络（有无航班）。用肘部法选 \(k=5\)。 - 方法应用：对每对年-月计算检验 \(p\)-值，Bonferroni 校正后比较。 - 结果：1 月与 11 月跨年比较所有 \(p\)-值大于阈值（绿色），结构稳定；6 月跨年比较中 2020-06 与其他年的 \(p\)-值小于阈值（红色），检测出 COVID-19 导致的结构断裂；2020-06 与 2021-06 的 \(p\)-值也不显著，说明 2021 年 6 月结构恢复。 - 说明什么：验证检验对真实结构变化的敏感性，同时对季节性密度波动（1 月、11 月）稳健，不误报。
🔎 结论是否比证明窄： - Theorem 1 声称在 Assumption 2（\(n\rho_n \gg \log n\)）下渐近正态，但均值/方差表达式（Eq. 6-7）包含 \(O_p(k/(n^2\rho_n^2))\) 与 \(o(k^2/(n^3\rho_n^2))\) 余项，这些余项在 \(n\rho_n \gg \log n\) 下不一定消失（仅保证可被中心化/尺度化吸收）。Theorem 2 在 Assumption 2'（\(n\rho_n \gg \sqrt{n}\)）下余项消失，但 Theorem 1 的严格证明仅保证"中心化/尺度化后余项可忽略"，并未证明余项本身趋于 0。作者在文中明确指出这一区别（Section 2.1 最后一段），但 Theorem 1 的陈述可能被泛泛理解为"均值/方差为 Eq. 6-7"，实际上 Eq. 6-7 是包含余项的近似表达式。 - Proposition 4 证明 plug-in 估计量误差下界 \(\max(k/(n^2\rho_n^2), k\sqrt{\log n}/(n^2\rho_n^{3/2}))\) 在 SBM 下不可改进，这意味着 Assumption 2' 是估计量一致性的必要条件，但 Theorem 1 的渐近正态在更弱条件（Assumption 2）下成立，只是无法构造一致估计量。作者明确区分了这两点，但读者可能误以为检验在 Assumption 2 下即可完全数据驱动实施。
三、开放问题¶
- 极稀疏设定（\(n\rho_n = O(\log n)\) 或常数平均度）下的可行性：本文理论要求 \(n\rho_n \gg \log n\)，在更稀疏网络下投影距离可能不收敛（Agterberg and Cape 2025），但是否存在其他检验统计量（如基于邻接矩阵局部特征或子抽样）可在极稀疏下达到非平凡功效？扎根于 Section 2.1 对 Assumption 2 的讨论："if \(n\rho_n \ll \log n\), then the network is disconnected w.h.p., and the Frobenius distance fails to converge"。
- 秩 \(k\) 未知时的自适应检验：本文假设 \(k\) 已知，但实际中 \(k\) 需估计。将秩估计的不确定性融入检验统计量的渐近分布是否可行？扎根于 Section 6："incorporating the theoretical uncertainty of rank selection into the asymptotic distribution of the test statistic is a mathematically non-trivial task"。
- 依赖边或重尾噪声下的极限定理：当前假设独立 Bernoulli 边，若边存在弱依赖（如传递性、互惠性）或重尾权重，鞅 CLT 与方差计算是否仍成立？扎根于 Section 6："Investigating the robustness of the test statistic under weak, local edge dependencies poses a challenging and valuable open problem"。
四、最核心、最简单的例子 / 数学问题¶
最简特例：平衡 SBM，\(k=2\)，\(n\rho_n \gg \sqrt{n}\)
设两个网络均为 2-社区 SBM，社区大小各 \(n/2\)，块矩阵 \(B^{(1)} \neq B^{(2)}\) 但社区划分相同（\(Z^{(1)} = Z^{(2)}\)）。此时 \(H_0\) 成立（\(V^{(1)}V^{(1)\top} = V^{(2)}V^{(2)\top}\)，因为列空间相同）。
- 概率矩阵：\(P^{(i)} = Z B^{(i)} Z^\top\)，秩 2。特征向量 \(V^{(i)} = Z (Z^\top Z)^{-1/2} U_i\)，其中 \(U_i\) 为正交矩阵。因 \(Z\) 相同，\(V^{(1)}V^{(1)\top} = Z (Z^\top Z)^{-1} Z^\top = V^{(2)}V^{(2)\top}\)，即投影矩阵相同。
- 检验统计量：\(T_n = \|\hat{V}^{(1)}\hat{V}^{(1)\top} - \hat{V}^{(2)}\hat{V}^{(2)\top}\|_F^2\)。在 \(H_0\) 下，展开为 \(2\|\beta^\perp X^{(1)} \beta^{-1}\|_F^2 + 2\|\beta^\perp X^{(2)} \beta^{-1}\|_F^2 - 2\text{tr}(S_{1,1}(X^{(1)})S_{2,1}(X^{(2)}) + \cdots)\)。
- 二阶项：\(T_2^{(S)} = 2\|\beta^\perp X^{(1)} \beta^{-1}\|_F^2 + 2\|\beta^\perp X^{(2)} \beta^{-1}\|_F^2 - 2\text{tr}(\beta^\perp X^{(1)} \beta^{-1} \beta^{-1} X^{(2)} + \beta^{-1} X^{(1)} \beta^\perp X^{(2)} \beta^{-1})\)。因 \(X^{(1)}, X^{(2)}\) 独立，交叉项均值 0，方差由 \(\Sigma^{(1)}, \Sigma^{(2)}\) 控制。
- 渐近正态：单样本二阶项 \(2\|\beta^\perp X \beta^{-1}\|_F^2\) 可重写为 \(\sum_{i=1}^n Q_i\)，其中 \(Q_i = 2X_{i\cdot}^\top \beta^{-2} X_{i\cdot}\) 为二次型。按上三角元素顺序揭示 \(X_{ij}\)，构造鞅差阵列，条件方差 \(\eta \asymp n^4 \gamma^2 \rho_n\)（\(\gamma \asymp 1/(n^2\rho_n^2)\)），\(E[\eta] \to \infty\)，\(E[\eta]/\sqrt{\text{Var}(\eta)} \gg 1\)，故 CLT 成立。
- 为什么成立：Incoherence 保证 \(\beta^\perp\) 投影不改变方差主导阶；Bernoulli 噪声的异方差性通过 Hadamard 积与对角校正精确计入均值/方差；密条件保证高阶项与估计误差可忽略。
核心数学困难：在异方差 Bernoulli 下，二次型的方差计算需精确处理对角与非对角项的不同贡献（\(\Sigma \circ \beta^\perp\) vs \(\text{Diag}(\Sigma \cdot d)\)），且高阶迹的方差需识别"完全分离"配置（主导）与含 \(VV^\top\) 的配置（低阶）。本文通过索引计数与 Incoherence 将含 \(VV^\top\) 的配置控制为低阶，从而分离出主导方差项，这是突破 Xia (2021) 高斯假设的关键。
Maintained by 陈星宇 · Homepage · Source on GitHub