Tests of graph homogeneity, subgraph counts, and quasirandomness¶

作者: Rudolf Gr\"ubel
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://arxiv.org/abs/2609.02214

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是稠密随机图的同质性检验（goodness-of-fit test for graph homogeneity）。根本的统计问题是：给定一个观测到的稠密图（顶点数 n 很大，边数 ~ n²），能否检验它是否来自经典的 Erdős–Rényi (ER) 模型（即所有边独立同分布，概率为 p）？这等价于检验生成该图的图论极限对象——graphon——是否几乎处处为常数。该方向处于图极限理论（graph limit theory）、随机图与统计假设检验的交汇处，当前成熟度属于理论驱动、方法初现的阶段：已有若干基于子图计数的检验统计量被提出，但其渐近分布、一致性条件和计算可行性仍在被系统性地建立。

发展脉络（history）¶

奠基工作：图极限理论与拟随机性
Chung, Graham & Wilson (1989)：提出拟随机图（quasirandom graphs）的概念，并证明了一系列等价刻画。其中最核心的一条是：一个图序列是拟随机的（即渐近等价于 ER 图）当且仅当它的 C₄（4-圈）密度趋于 (K₂ 密度)⁴。这为用子图计数检验同质性提供了理论基础。
Lovász (2012) 的专著《Large Networks and Graph Limits》系统建立了稠密图的极限理论（graphon 模型），将图序列的收敛性、子图密度的极限与 graphon 上的积分联系起来。这为统计建模提供了严格的数学框架。
主要进展：子图计数的分布理论与检验
Janson, Łuczak & Ruciński (2000) 的专著《Random Graphs》系统处理了 ER 模型下子图计数的渐近分布，特别是通过图泛函的 Hoeffding 型分解（即 Z-基）得到了中心极限定理。这是本文分布理论的核心工具。
Brune, Flossdorf & Jentsch (2023) 提出了基于三角形计数的同质性检验，并讨论了稀疏情形（p 随 n 变化）下的行为。但本文指出，在固定 p 的稠密情形下，他们的检验需要 np² → 0 才能有效，而本文的检验在固定 p 下以更快的速率 n^{-3/2} 工作。
Ouadah, Robin & Latouche (2020) 提出了基于度分布（degree-based）的拟合优度检验，适用于独立图模型和可交换图模型（如随机块模型）。但这类检验只利用了一阶信息（度），对某些非 ER 的 graphon 可能不敏感。
当前 frontier：一致检验与效率比较
Kaur & Röllin (2021) 研究了稠密随机图模型中子图计数的高阶波动，通过广义 U-统计量和 Gaussian Hilbert 空间理论，给出了子图计数多元正态近似的定量界。这为理解检验统计量的高阶行为提供了工具。
本文（Grübel, 2026） 的位置：它利用拟随机性结果（C₄ 不等式）构造了一个对所有 graphon 备择假设一致的检验（Theorem 4），并系统分析了基于 P₃、K₃、C₄ 的多个检验的渐近分布和局部一致性。这是首次将拟随机性刻画直接转化为统计检验的一致性保证。

子线索聚类¶

基于子图计数的检验：这是本文的主线。统计量是特定子图（P₃、K₃、C₄）的密度与边密度幂次之差。核心挑战是处理抵消效应（cancellation effect）：单独的子图计数以速率 n^{-1} 波动，但它们的特定组合（如 t(P₃) - t(K₂)²）的波动速率降为 n^{-3/2}，需要精细的 Z-基分解来揭示。
基于度分布的检验：Ouadah et al. (2020) 为代表，利用度均方等统计量。这类检验计算简单，但只对某些偏离（如度分布不均）敏感，对更微妙的图结构偏离（如保持度分布但改变高阶结构）可能无效。
拟随机性与一致检验：Chung et al. (1989) 的拟随机性刻画为构造一致检验提供了理论依据。本文的 Theorem 4 是这一线索的直接统计实现。

这个方向在追问的核心问题¶

如何构造对所有备择假设一致的检验？ 即 omnibus test。本文用 C₄ 不等式给出了一个答案，但其他拟随机性刻画（如基于 K₄ 或更一般子图的）是否也能导出检验？
不同检验的局部效率如何比较？ 对于接近 ER 模型的备择（如随机块模型参数接近 p₁ = p₂），哪个检验的渐近相对效率最高？这需要大偏差理论或 Pitman 效率分析。
稀疏图（p → 0）情形下的检验行为？ 本文专注于稠密图（p 固定），但实际网络往往是稀疏的。子图计数的分布理论在稀疏情形下完全不同（如 Poisson 极限），检验方法需要重新设计。
计算可行性：子图计数（尤其是 C₄）的计算复杂度如何？本文指出可通过邻接矩阵的幂次高效计算，但更复杂的子图（如 K₄）可能带来计算瓶颈。

⚠️ 作者的 framing¶

作者将缺口 frame 为：虽然已有基于子图计数的检验（如三角形检验），但缺乏一个对所有 graphon 备择一致的理论保证，且已有检验的渐近分布推导不够系统（未充分利用 Z-基的抵消效应）。作者通过以下方式使本文成为“显然的下一步”： - 利用拟随机性结果（C₄ 不等式）直接构造一致检验（Theorem 4）。 - 用 Z-基分解统一处理多个检验的渐近分布，并揭示抵消效应是速率提升的关键。 - 在随机块模型和带状 graphon 两个参数族上评估其他检验的局部一致性，指出哪些备择会被“漏掉”。

被淡化或回避的竞争路线： - 度分布检验（Ouadah et al.）被提及但未深入比较。作者可能认为这类检验只利用一阶信息，对高阶结构偏离不敏感，但未给出理论上的效率比较。 - 稀疏图情形被明确排除（“p varies with n”被归为另一类模型），但实际应用中稀疏图更常见。

什么明显该被引/该存在、却没出现在 intro 里？ - 基于谱的检验：如检验图是否来自 ER 模型可通过比较邻接矩阵的特征值分布与 Wigner 半圆律。这类方法在随机矩阵理论中很成熟，但本文完全未提及。 - 基于图距离的检验：如用 cut distance 或 edit distance 构造检验。这些在图极限理论中很自然，但本文未涉及。 - 更一般的拟随机性刻画：如基于任意固定子图 H 的密度与边密度幂次的关系。Janson (2011) 的论文系统处理了这类问题，但本文只用了 C₄ 和 P₃ 两个特例。

张力¶

未见明显对立引用。所有被引工作基本一致地认为：子图计数是研究图结构的核心工具，ER 模型是基准零模型，拟随机性刻画提供了构造检验的理论基础。主要张力在于稀疏 vs. 稠密的设定差异，但本文明确限定在稠密情形，因此不构成矛盾。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

符号： - n：图的顶点数（样本量）。 - Gₙ：观测到的随机图，顶点集为 [n] = {1, ..., n}，边集 E(Gₙ) 是 [n] 上大小为 2 的子集的集合。 - p：ER 模型中的边概率，未知参数，p ∈ (0,1)。 - W：graphon，一个可测对称函数 W: [0,1]² → [0,1]。若 W ≡ p a.s.，则对应 ER 模型。 - H：一个固定的“小图”（如 K₂、P₃、K₃、C₄），顶点数 k = v(H)，边数 e(H)。 - t(H, Gₙ)：H 在 Gₙ 中的密度（归一化子图计数），定义为从 n 个顶点中无放回均匀抽取 k 个顶点，它们诱导的子图包含 H 的概率。即 t(H, Gₙ) = A(H, Gₙ) / (n)ₖ，其中 (n)ₖ = n(n-1)...(n-k+1)，A(H, Gₙ) 是 H 作为标记子图（labeled subgraph）出现的次数（考虑了顶点顺序）。 - t(H, W)：H 在 graphon W 下的极限密度，由积分 (1) 定义。 - Z_H(Gₙ)：中心化的子图计数，定义见 (5)，其中 1ₑ(Gₙ) 是边 e 的指示函数，p 是中心化参数。Z_H 在 ER 模型下均值为 0，且不同 H 的 Z_H 不相关。 - aut(H)：H 的自同构群大小。

模型： - 数据生成机制：观测图 Gₙ 来自 graphon 模型。具体地，先独立生成 n 个 [0,1] 上的均匀随机变量 U₁, ..., Uₙ（顶点潜在位置），然后对每对顶点 {i,j}，以概率 W(Uᵢ, Uⱼ) 独立地决定边是否存在。若 W ≡ p，则退化为 ER(n, p) 模型：所有边独立同分布，概率为 p。 - 待估对象：p（若零假设成立）或整个 graphon W（若备择成立）。检验的目标是判断 W 是否几乎处处为常数。

可观测数据： - 研究者能观测到的是图 Gₙ 的邻接矩阵 M ∈ {0,1}^{n×n}，其中 M_{ij} = 1 当且仅当 {i,j} ∈ E(Gₙ)。这是全部数据。 - 不可观测的是：顶点潜在位置 U₁, ..., Uₙ（在 graphon 模型中），以及 graphon W 本身。这些只能通过假设（如 ER 模型）或极限行为（如子图密度收敛）来间接推断。

第二步：讲最小内核¶

本文的核心数学问题可以浓缩为以下最简特例：

特例：检验一个图是否来自 ER 模型，仅使用边密度 t(K₂, Gₙ) 和2-路径密度 t(P₃, Gₙ) 的差值。

为什么这是最小内核？ 因为 P₃ 是除边之外最简单的连通子图（3 个顶点，2 条边），而拟随机性理论告诉我们：对于任何 graphon W，有 t(P₃, W) ≥ t(K₂, W)²，等号成立当且仅当 W 几乎处处为常数（即 ER 模型）。因此，检验 t(P₃, Gₙ) - t(K₂, Gₙ)² 是否显著大于 0 就是一个自然的检验。

核心数学困难：在 ER 模型下，t(P₃, Gₙ) 和 t(K₂, Gₙ) 各自以速率 n^{-1} 围绕其期望波动（即标准差 ~ n^{-1}），但它们的差值的波动速率是 n^{-3/2}！这意味着存在一个抵消效应：两个统计量的一阶波动相互抵消，只剩下二阶项。要证明这一点并导出极限分布，需要精细的分解。

关键想法：利用 Z-基分解。将 t(P₃, Gₙ) - t(K₂, Gₙ)² 展开为 Z_H 的线性组合，然后利用 Z_H 在 ER 模型下的正交性和已知的渐近正态性。具体地，在 ER(n, p) 下，可以证明（见 Theorem 1 证明中的 (16)）：

\[n^{3/2} \left[ t(P_3, G_n) - t(K_2, G_n)^2 \right] = n^{3/2} Z_{P_3}(G_n) + o_P(1),\]

其中 Z_{P₃} 是中心化的 P₃ 计数，其渐近方差为 2p²(1-p)²。因此，检验统计量 T₁ₙ 在零假设下渐近服从标准正态分布。

这个特例揭示了整篇论文的核心机制：通过构造子图密度的特定非线性组合，使得一阶项（来自边计数）相互抵消，从而暴露出更高阶的波动（来自更复杂的子图），这些高阶波动在 ER 模型下具有已知的极限分布，且对非 ER 的 graphon 敏感。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在稠密随机图（graphon 模型）中，检验图是否来自 Erdős–Rényi 模型（即 graphon 几乎处处为常数）的拟合优度检验问题。
核心工具/方法：利用图泛函的 Z-基分解（图版本的 Hoeffding 分解）揭示子图计数组合中的抵消效应，从而导出检验统计量在零假设下的渐近正态分布；利用拟随机性结果（C₄ 不等式）构造对所有备择一致的检验。
主要结论：给出了基于 P₃、K₃、C₄ 的四个检验统计量的渐近分布（Theorem 1, 2, 4, 6），其中基于 C₄ 的检验（Theorem 4）是 omnibus 的（对所有 graphon 备择一致）；在随机块模型和带状 graphon 两个参数族上评估了其他检验的局部一致性（Proposition 7, 8）；通过模拟验证了有限样本行为。

关键设定与假设¶

设定：观测图 Gₙ 来自 graphon 模型（Section 2.2），即存在一个 graphon W，使得 Gₙ 的分布由 W 决定。零假设 H₀：W ≡ p a.s. 对某个 p ∈ (0,1)（即 ER 模型）。备择假设 H₁：W 不是几乎处处常数。
假设：
稠密图：p 固定，不随 n 变化。这是全文的基础，因为子图计数的 n^{-3/2} 速率依赖于 p 固定。若 p → 0，速率会变化（如 Brune et al. 的 np² → 0 条件）。
图泛函的 Z-基分解存在且唯一（Section 2.4）：这要求图泛函是“可交换的”（即不依赖于顶点标号），且 Z_H 构成 L² 空间的正交基。这在 ER 模型下成立，因为边指示变量独立同分布。
渐近框架：n → ∞，所有结果都是极限的。有限样本行为通过模拟展示。
相比已有文献的放宽/强化：
相比 Brune et al. (2023) 的三角形检验，本文的检验在固定 p 下有效（无需 np² → 0），且速率更快（n^{-3/2} vs. n^{-1}）。
相比 Ouadah et al. (2020) 的度分布检验，本文的检验利用了高阶子图信息，理论上能检测更广泛的偏离。

主要结果¶

Theorem 1（基于 P₃ 的检验）： - 统计量：T₁ₙ = n^{3/2} / [√2 t̂ (1 - t̂)] · [t(P₃, Gₙ) - t(K₂, Gₙ)²]，其中 t̂ = t(K₂, Gₙ)。 - 零假设下：T₁ₙ →d N(0,1)。检验是单侧的（拒绝域 T₁ₙ > u_α）。 - 直觉：t(P₃, W) ≥ t(K₂, W)²，等号仅当 W 常数。因此 T₁ₙ 在备择下倾向于取大值。 - 技术难点：需要证明抵消效应，即 n^{3/2} 倍的差值收敛到 Z{P₃} 的缩放版本。

Theorem 2（基于 K₃ 的检验）： - 统计量：T₂ₙ = n^{3/2} / √φ(Gₙ) · [t(K₃, Gₙ) - t(K₂, Gₙ)³]，其中 φ(Gₙ) 是方差估计。 - 零假设下：|T₂ₙ| →_d N(0,1)。检验是双侧的（Remark 3 解释原因：三角形密度可能低于或高于 ER 预测，如二分图）。 - 技术难点：极限方差由 K₃ 和 P₃ 两个子图的贡献组成，需要处理它们的渐近独立性。

Theorem 4（基于 C₄ 的检验，omnibus）： - 统计量：T₃ₙ = n^{3/2} / [4√2 t̂³ (1 - t̂)] · [t(C₄, Gₙ) - t(K₂, Gₙ)⁴]。 - 零假设下：T₃ₙ →_d N(0,1)。检验是单侧的。 - 一致性：对任何非 ER 的 graphon W，有 T₃ₙ → ∞ a.s.，因此检验以概率 1 拒绝 H₀。这是本文的核心贡献。 - 证明思路：利用拟随机性结果 t(C₄, W) > t(K₂, W)⁴ 对非常数 W 严格成立，以及 t(C₄, Gₙ) 和 t(K₂, Gₙ) 几乎处处收敛到极限。

Theorem 6（基于 C₄ 和 P₃ 的检验）： - 统计量：T₄ₙ = n^{3/2} / [2√2 t̂³ (1 - t̂)] · [t(C₄, Gₙ) - t(P₃, Gₙ)²]。 - 零假设下：T₄ₙ →_d N(0,1)。单侧检验。 - 注意：该检验不是 omnibus 的，因为 t(C₄, W) = t(P₃, W)² 对某些非常数 W 也可能成立（如随机块模型中 γ = 1/2 的情形）。

Proposition 7 & 8（局部一致性分析）： - 在随机块模型（Proposition 7）和带状 graphon（Proposition 8）上，给出了 T₁、T₂、T₄ 何时一致（即能检测到偏离）的精确条件。例如，T₁ 在随机块模型中当块大小 γ ≠ 1/2 时一致，但当 γ = 1/2 时失效（因为此时 t(P₃, W) = t(K₂, W)² 即使 p₁ ≠ p₂）。

证明路线与技术技巧（以 Theorem 1 为例）¶

整体路线（3-5 步）： 1. 用 Z-基表示子图计数：将 A(P₃, Gₙ) 和 A(K₂, Gₙ) 展开为 Z_H 的线性组合（(13) 和 (14)）。这一步利用了 1ₑ = (1ₑ - p) + p 的分解和乘积展开。 2. 构造差值并识别主导项：计算 t(P₃, Gₙ) - t(K₂, Gₙ)² 的 Z-基表示。关键发现：系数最大的项（来自 Z_{K₂} 和常数项）相互抵消，剩下 Z_{P₃} 作为主导项（阶为 n^{-3/2}），其他项（如 Z_{K₂+K₂}）的阶更低（o(n^{-3/2})）。 3. 利用 Z-基的正交性和渐近正态性：在 ER(n, p) 下，Z_{P₃} 的方差为 aut(P₃) (n)₃ (p(1-p))² = 2 (n)₃ p²(1-p)²，且 n^{-3/2} Z_{P₃} 渐近正态 N(0, 2p²(1-p)²)（引用 Janson et al. 的定理）。 4. 学生化（studentization）：用 t(K₂, Gₙ) 一致估计 p，代入方差公式，由 Slutsky 引理得到 T₁ₙ →_d N(0,1)。

关键跳跃点： - 抵消效应的证明：需要精确计算 Z_{K₂} 的系数在差值中如何消失。这依赖于 Z-基分解的代数封闭性（图泛函的乘积仍可表示为 Z_H 的线性组合），以及系数对 n 的依赖关系的精确计算。例如，在 Theorem 1 的证明中，c₃(n, p) 的表达式显示 Z_{K₂} 的系数是 O(n^{-4})，远小于 n^{-3/2} 的量级。 - 处理高阶项：对于 Theorem 2 和 Theorem 4，需要处理更多类型的 Z_H（如 Z_{K₂+K₂}、Z_{P₃}Z_{K₂} 等）。证明中使用了 L² 范数界和 ∥X·Y∥₂ ≤ ∥X∥_∞ ∥Y∥₂ 的技巧来证明这些项是 o_P(n^{-3/2})。

技术技巧点名： - Z-基分解：图版本的 Hoeffding 分解，是全文的代数核心。它将图泛函表示为“中心化边指示变量乘积”的线性组合，这些变量在 ER 模型下正交。 - 抵消效应分析：通过精确计算 Z_H 的系数，识别哪些项在差值中相互抵消，从而暴露出主导项。这是统计技巧，不是纯代数。 - L² 范数界 + 一致界：用于处理高阶乘积项（如 Z_{K₂}·Z_{P₃}），证明它们相对于主导项可忽略。 - 学生化：用一致估计量代替未知参数 p，由 Slutsky 引理保证极限分布不变。 - 拟随机性不等式：Cauchy-Schwarz 不等式在 graphon 积分上的应用，得到 t(C₄, W) ≥ t(P₃, W)² ≥ t(K₂, W)⁴，等号条件刻画 ER 模型。

真实例子与应用¶

本文包含模拟实验（Section 5），无真实数据例子。

数据/场景：模拟数据来自随机块模型（表 1）和带状 graphon（表 2）。随机块模型参数：两个块，块大小 γ，块内概率 p₁ = 0.5 + β，块间概率 p₂ = 0.5 - β。带状 graphon 参数：带宽 β，概率 p = 0.5。
方法应用：对每个模拟图计算 T₁、T₂（双侧）、T₃、T₄ 及其偏置校正版本 T^{bc}，并与标准正态临界值比较，记录 10000 次重复中的拒绝率。
结果：
零假设（β=0 或 β=1）下，拒绝率接近名义水平 0.05，验证了渐近相似性。
偏置校正（T^{bc}）通常略微提高拒绝率（尤其当 β 接近 0 时）。
T₂ 的双侧版本优于单侧（Remark 3 的验证）。
在随机块模型中，当 γ=0.5（对称块）时，T₁ 的拒绝率很低（即使 β 很大），验证了 Proposition 7(a) 的结论（T₁ 在 γ=1/2 时失效）。而 T₂ 和 T₃ 在 γ=0.5 时表现良好。
在带状 graphon 中，所有检验在 β 远离 1 时拒绝率接近 1，但在 β 接近 1（接近零假设）时拒绝率下降。
这个例子想说明什么：验证理论结果（渐近分布、局部一致性条件），展示不同检验在不同备择下的表现差异，并说明偏置校正的实际益处。

🔎 结论是否比证明窄¶

Theorem 4 的一致性证明：证明中使用了“t(C₄, Gₙ) 和 t(K₂, Gₙ) 几乎处处收敛到极限”这一事实，这依赖于 graphon 模型下子图密度的 a.s. 收敛性（(1) 式）。但该收敛性要求 graphon W 是固定的（不随 n 变化）。如果考虑 W 随 n 变化的序列（如稀疏图），则一致性不再保证。论文在 Section 1 中明确排除了这种情况（“p varies with n”），但未在 Theorem 4 的陈述中重复这一限制。
Theorem 2 的方差估计：φ(Gₙ) 的表达式（6t̂³(1-t̂) + 18t̂⁴(1-t̂)²）是在假设 p 固定下推导的。若 p 接近 0 或 1，该估计可能不稳定，但论文未讨论边界行为。
模拟中的“一致性”：模拟中 n=100 时，T₃ 在 β=0.1 时的拒绝率仅为 0.068（表 1 上部分），远非 1。这并不矛盾，因为一致性是 n→∞ 的极限性质，有限 n 下功率可能很低。但论文未给出收敛速度的定量界。

四、开放问题¶

稀疏图情形下的检验：本文所有结果针对固定 p 的稠密图。对于 p → 0 的稀疏图，子图计数的极限分布变为 Poisson 型，抵消效应可能消失或改变。如何构造稀疏图下的 omnibus 检验？这扎根于论文 Section 1 中“p varies with n”的提及和 Section 6 中“large deviation results for random graphs”的展望。
检验的效率比较：论文只给出了局部一致性（哪些备择能检测到）的定性结果，未进行定量效率比较（如 Pitman 效率、Bahadur 效率）。对于接近 ER 模型的备择（如随机块模型中 p₁ ≈ p₂），哪个检验的渐近相对效率最高？这需要大偏差理论或高阶展开，扎根于 Section 6 中“efficiency concepts”的讨论和引用 [2]（Baringhaus & Grübel, 2026）对排列检验的效率分析。
更一般子图的 omnibus 检验：本文只用了 C₄ 的拟随机性刻画。是否存在基于其他子图（如 K₄、或任意固定子图 H）的类似检验？Janson (2011) 的论文系统研究了哪些子图能刻画拟随机性，但未转化为统计检验。这扎根于 Section 6 中“other quasirandomness results should lead to alternative procedures”的陈述。
两样本检验：本文处理的是单样本拟合优度检验。如何检验两个图是否来自同一个 graphon（即两样本问题）？这需要将分布理论从 ER 模型推广到一般 graphon，扎根于 Section 6 中“two-sample situation”的讨论和引用 [1]（Baringhaus & Grübel, 2025）对 copula 的两样本检验。

Maintained by 陈星宇 · Homepage · Source on GitHub