On the impossibility of detecting a late change-point in the preferential attachment random graph model¶

作者: Ibrahim Kaddouri, Zacharie Naulet, Élisabeth Gassiat
来源: Bernoulli
主题: 数理统计 / 假设检验
相关性: 4/10
机构绿灯: Université Paris-Saclay（US News 前 50，免分进入精读）
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

本方向研究的是在动态随机图（特别是 preferential attachment 模型）中检测结构突变（change-point）的统计可行性。具体地，给定一个在时间上逐步增长的图，其生长规则（如新节点连接已有节点的概率规则）可能在某个时间点发生改变；我们只能观测到最终图的一个快照（snapshot，即 n 个节点及其边），而没有节点加入的时间标签（unlabeled），目标是判断生长参数是否发生过变化。这是一个典型的复合假设检验问题，其核心困难在于：图的拓扑结构（度序列、子图计数等）携带有生长历史的信息，但观测到的单一快照中，时间信息被严重压缩，导致检测能力受限于变点位置（是早期变点还是晚期变点）以及可观测到的图信息量（labeled vs unlabeled）。该方向的成熟度目前处于中等偏高阶段：已有大量工作处理了早期变点（比例尺度的变点）的检测与定位，但晚期变点（变点发生在接近观测时刻）的检测理论目前仍处于探索与猜想验证阶段。

发展脉络（从 introduction + 参考文献构建）¶

奠基工作：Barabási & Albert (1999) 提出了 preferential attachment 模型，奠定了“增长 + 偏好连接”作为幂律度分布成因的理论基础。后续 Deijfen et al. (2007) 将其推广为随机初始度数的 affine preferential attachment 模型（参数 δ 控制 base attractiveness）。这些建模工作为后续的统计推断提供了基础。
早期变点检测（比例尺度）：Bhamidi, Jin & Nobel (2015) 首先在 preferential attachment 模型中提出了变点检测与定位问题，但处理的是早期变点（τ_n = αn，α∈(0,1)）。他们证明变点不会改变度指数，但会影响度分布，并给出了一致估计量。Banerjee, Bhamidi & Carmichael (2018) 则进一步区分为两种时间尺度：标准模型（τ_n = γn）和快速大爆炸模型（τ_n = n^γ），证明在第一种尺度下可通过经验度分布的 sup-范数近似得到一致估计量。Wang, Yu & Rinaldo (2018) 和 Zhao, Chen & Lin (2019) 则从更一般的动态网络变点检测入手，但他们的模型假设序列中每个时间点对应一个独立的图，而非单图演化。
正式定义晚期变点与信息结构：Bet et al. (2023) 是本文最直接的先行工作。他们首次正式提出了单快照下的晚期变点检测问题，定义变点位置为 τ_n = n - c n^γ (γ∈(0,1)，即 Δ_n = c n^γ)。基于低度顶点数量（degree-1 vertices）构造检验，证明当 γ > 1/2（即 Δ_n / n^{1/2} → ∞）时检验具有渐近功效。他们同时猜想：当 Δ_n = o(n^{1/2}) 时，基于 unlabeled graph 的检测是不可能的。这正是本文要解决的核心猜想的一部分。
似然比与估计理论：Gao & van der Vaart (2016) 建立了 affine preferential attachment 模型下 MLE 的渐近正态性与效率；Gao et al. (2017) 将其推广到更一般的 sublinear attachment 函数估计。Cirkovic, Wang & Zhang (2022) 进一步提出了基于似然比的变点检测框架（包括单个与多个变点），并证明估计量的一致性。
本文的位置：本文直接延续 Bet et al. (2023) 的猜想，但使用不同的技术工具（似然比分析而非基于度数的检验统计量），在 unlabeled 设定下将不可检测的条件从 Δ_n = o(n^{1/2}) 弱化至 Δ_n = o(n^{1/3})，并同时完整解决了 labeled 设定下的可检测性条件（Δ_n → ∞）。本文是对 Bet 猜想的部分验证，但并未完全解决。

子线索聚类¶

变点的早期 vs 晚期：
早期（比例尺度 τ_n = αn）：Bhamidi et al. (2015)、Banerjee et al. (2018)，都用度分布的大样本近似，可一致估计变点。
晚期（τ_n = n - Δ_n，Δ_n = o(n)）：Bet et al. (2023) 提出猜想，本文证明部分结果。
观测信息结构（labeled vs unlabeled）：
Labeled（已知每个节点的“年龄”/时间标签）：Gao & van der Vaart (2016)、Cirkovic et al. (2022) 等的工作基于 labeled log-likelihood，可获得渐近正态的估计量。
Unlabeled（仅图拓扑，无时间标签）：Bet et al. (2023) 和本文聚焦该场景，信息量大幅减少，导致晚期变点不可检测区域显著扩大。
检验统计量 vs 似然比框架：
基于特定度数的检验（如 Bet et al. 用度数为 1 的顶点数）：计算简单但可能需要较强的假设才能达到接近最优的检测边界。
基于似然比的检验（本文）：理论上更本质，可直接刻画检测的 impossibility 区间。但似然比在 unlabeled 情况下计算困难，需要复杂的技术分析（本文贡献之一）。

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

Q1：在 unlabeled 单个快照下，晚期变点检测的精确不可检测门槛（minimax 意义下的检测速率）是什么？Bet 猜想为 Δ_n = o(n^{1/2})，本文证明 Δ_n = o(n^{1/3}) 时不可能。这个 gap 是否可通过改进 lower bound 或 upper bound 进一步缩小？
Q2：当 Δ_n 足够大时，optimal detection rate 是多少？是否存在一个检验（如基于更精细的度数分布函数）达到该率？
Q3：Labeled vs unlabeled 的信息量差距到底有多大？本文证明 labeled 情况下只需 Δ_n → ∞ 即可检测，而 unlabeled 需要 Δ_n 至少以多项式速率增长。这个差距的精确阶是否就是 n^{1/2}（如 Bet 猜想）？
Q4：更一般的 attachment 函数（如 sublinear、time-varying）下，变点检测问题会如何变化？目前的结论只限于 affine (linear) preferential attachment。

⚠️ 作者的 framing（必须标注为“作者说法”）¶

作者将缺口 frame 为：“Bet et al. 猜想（Δ_n = o(n^{1/2}) 时检测不可能）只能用更精细的似然比分析来证明或否定。我们通过分析 unlabeled graph 的似然比，证明当 Δ_n = o(n^{1/3}) 时检测不可能，从而向验证该猜想迈进一步。” 同时，作者特别强调了labeled vs unlabeled 的判若鸿沟，使得晚变点检测问题在 unlabeled 情境下成为即使轻微后期变点（Δ_n 很小）也无法检测的极端困难问题。

被淡化/回避的竞争路线： - 基于度数的检验：作者在 introduction 末尾提到“已有方法（Bet 等）只能在 Δ_n ≫ n^{1/2} 时工作”，暗示这些方法不可能达到更优。 - 更复杂的图统计量：作者没有讨论是否可以用子图计数（如三角形、星形）或 spectral 统计量来获得比低度顶点更好的检测能力。这也许是一个被低估的方向。

明显该被引/该存在、却没出现在 intro 里： - 现代 graph limit theory（graphon estimation, network moment testing）的相关工作，如 Gao & Ma (2021) 关于 network hypothesis testing 的 minimax lower bound。这些工作依赖于不同的图模型（独立实现而非增长模型），但可以为“从单次实现中做检验”提供下界思路。 - Higher-order influence functions / U-statistics 在随机图模型中的应用。虽然模型不同，但 U-statistics 在度分布估计中有潜力。这恰好是 researcher 的熟悉领域。

张力¶

未见明显对立引用。但存在一个 open tension：对 unlabeled 图，Bet et al. 认为 Δ_n = o(n^{1/2}) 不可检测；本文只证明了 o(n^{1/3}) 不可检测（更弱）。两个结果之间没有矛盾（前者的猜想更强），但 哪一个更接近真实门槛？ 这是一个真实的 open question。

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

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

符号（逐个定义）： - $n$：图的顶点数（总观测规模）。 - $\tau_n$：变点发生的时间（第 $\tau_n$ 个顶点加入后变点发生），满足 $1 \le \tau_n \le n$。在本文中关注晚期变点：$\tau_n = n - \Delta_n$，其中 $0 \le \Delta_n \le n$，$\Delta_n$ 为“观测延迟”（变点距离观测终点的步数）。 - $G_n$：生长至 $n$ 个顶点的unlabeled（顶点无标签）随机图，即只能看到其拓扑结构。这是本文主要观测对象。 - $G_n^{\text{labelled}}$：生长至 $n$ 个顶点的labeled图，即每个顶点配有自身加入顺序的标签（时间标签 1,...,n）。 - $\delta_t$：t 时刻的affine attachment parameter。在 null 下恒为 $\delta_0$；在 alternative 下，$\delta_t = \delta_0$ 对 $t \le \tau_n$，$\delta_t = \delta_1$ 对 $t > \tau_n$。 - 在 affine preferential attachment 模型中，新节点以概率 $\propto d_v(t) + \delta_t$ 连接到已有顶点 $v$，其中 $d_v(t)$ 是 $v$ 在时刻 $t$ 的度数。 - $\delta_0, \delta_1 > -1$（为控制度分布幂律尾，一般需 $\delta > -1$）。 - $H_0$: $\delta_t \equiv \delta_0$（无变点） vs $H_1$: 存在 $\tau_n$ 使参数从 $\delta_0$ 变为 $\delta_1$。 - $\Delta_n$：检测任务的关键参数。

模型（数据生成机制）：采用经典的 affine preferential attachment 模型，也称为 Barabási-Albert 模型的广义形式。过程如下： 1. 初始图：$m_0$ 个顶点和若干边。 2. 在时刻 $t = m_0+1, ..., n$，新顶点 $v_t$ 加入，它带有 $m$ 条边。 3. 这 $m$ 条边分别连接到已有的顶点。每条边连接到某个已有顶点 $u$ 的概率为：

\[\mathbb{P}(\text{连接 } u) = \frac{\deg_{t-1}(u) + \delta(t)}{(2m)(t-1) + \delta(t)(t-1)}\]

其中 $\deg_{t-1}(u)$ 是 $u$ 在时刻 $t-1$ 时的度数，$\delta(t)$ 是时刻 $t$ 的 affine 参数。 4. 当 $\delta(t) \equiv \delta_0$ 时，得到的度分布满足幂律 $P(D \ge k) \approx C k^{-(1+\delta_0/m)}$（近似地）。

可观测数据（关键区分）： - Labeled 场景：我们能观测到完整的生长序列 $(G_1, G_2, ..., G_n)$ —— 即知道每个顶点加入的时间顺序。这意味着我们可以观察从变点时刻到终点的完整过程。 - 观测目标：知道每个边的方向（指向哪）以及每个顶点加入的精确顺序。 - 不可观测：只有此时才算是完全观测到动态过程。 - Unlabeled 场景：我们只能观测到最终图 $G_n$（$n$ 个顶点，边集），但不知顶点加入的顺序，不知变点位置。这是典型的“单快照”场景。 - 观测目标：只有无标签的图拓扑结构。 - 不可观测（需要假设才能推断的）：顶点的时间标签 $\sigma$（permutation），变点位置 $\tau_n$，以及原始的进化轨迹。

第二步：讲最小内核¶

这个论文的核心数学难题可以浓缩成下面这个最简例子：

最简设定： - $m = 1$（每个新节点只带来一条边，即得到一棵树）。这是该模型最简单的版本。 - $\delta_0 = 0$，$\delta_1 = 1$（简化，但不改变本质）。 - 我们想要判断：第二个 half 的生长参数是否从 0 变成了 1。 - 我们只观测到最后的树 $T_n$，且不知道哪个顶点先加入（unlabeled）。

在这个最简设定下，定理在说什么？ 如果 $\Delta_n = o(n^{1/3})$，那么观测 $T_n$ 的似然比在 $H_0$ 和 $H_1$ 下趋向于 1（总变差距离趋于 0），因此任何检验的功效趋于显著性水平。换句话说，当变点距离观测终点太近（$\Delta_n$ 增长太慢），unlabeled 树的结构几乎完全由变点前的主体生长决定，变点后的小部分生长（$\Delta_n$ 个节点）无法在拓扑结构中留下可检测的信号。

为什么？ - 在 preferential attachment 树的成长中，新节点几乎总是连接到度数最高的顶点之一（因偏好性）。 - 变点后的 $\Delta_n$ 步：参数从 $\delta_0$ 变为 $\delta_1$（比如增大），导致新节点更倾向于连到较老的高值顶点（因参数增大放大了偏好性）。但这 $\Delta_n$ 步相对于 $n$ 来说太小（$n^{1/3}$ 量级），它们引入的度分布或拓扑变化在整体的度序列中占比极小。 - 从概率的角度：两个假设下的树拓扑只在度数极高的那几个顶点上有微小差异（这种差异随 $\Delta_n$ 增长而衰减）。当 $\Delta_n = o(n^{1/3})$ 时，该差异在 total variation 意义下趋向于零。

所以，最小内核总结：本文证明的核心就是：当变点后的步数 $\Delta_n$ 的增长慢于 $n^{1/3}$ 时，unlabeled 树的新生部分产生的结构信号在信息论上下跌到无法检测的水平。证明依赖的核心工具是对 unlabeled graph 似然比的精确 bound，该 bound 本质上刻画了图的拓扑结构相对于生长参数变化的敏感性量级**。

三、这篇论文做了什么（本次重心）¶

三句话¶

研究了什么问题：在 affine preferential attachment 随机图中的晚期变点检测问题——即在未标记（unlabeled）和标记（labeled）两种观测结构下，确定变点 $\tau_n = n - \Delta_n$ 在何种 $\Delta_n$ 条件下是不可能被检测的。
核心工具/方法：对 labeled 和 unlabeled 两种情况下的似然比（likelihood ratio）进行严格分析，给出似然比的显式表达，并证明其在 $H_0$ 和 $H_1$ 下的渐近性质。利用这些绪论，推导出变点检测的 impossibility 条件。
主要结论：
对于 labeled graph：变点检测是可能的当且仅当 $\Delta_n \to \infty$。
对于 unlabeled graph：变点检测不可能当 $\Delta_n = o(n^{1/3})$（此结果部分验证了 Bet et al. 关于 $\Delta_n = o(n^{1/2})$ 的猜想）。

关键设定与假设¶

完整设定（建立在第二节最小记号基础上）： - 模型：affine preferential attachment 随机图，参数 $m \ge 1$（每次新节点带来的边数）。初始图 $G_0$ 是固定的小图（不影响渐近结果）。 - 变点机制：参数 $\delta(t)$ 在 $t \le \tau_n$ 时取 $\delta_0$，$t > \tau_n$ 时取 $\delta_1$，$\delta_0, \delta_1 > -1$，且 $\delta_0 \neq \delta_1$。 - 检测目标：假设检验 $H_0: \delta_t \equiv \delta_0$ vs $H_1: \exists \tau_n \text{ 使得变点在 } \tau_n$。注意 $H_0$ 是“简单”假设（参数已知），$H_1$ 是复合假设（变点位置未知，变点后的参数 $\delta_1$ 也假设已知。但结果对未知 $\delta_1$ 也成立，通过取 worst-case 最不利 $\delta_1$）。 - 观测： - Labeled: 整个序列 $(G_t)_{t=1}^n$（含顶点顺序标签） - Unlabeled: 仅最终图 $G_n$

假设： - A1（亲和参数已知）：$\delta_0$ 已知（在 $H_0$ 下）。这是为了焦点清晰地分析 impossibility 下界。实际中可通过估计得到，但不会改变本质。 - A2（变点位置未知但在一定范围内）：$\tau_n$ 属于一个已知的有界区间（如$\tau_n = n - \Delta_n$ 且 $\Delta_n$ 已知范围）。在 impossibility 证明中，我们可以 worst-case 地取最有利的 $\tau_n$（即假设已知精确变点），若即便如此都不可检测，则原复合检验更不可检测。 - A3（无平行边）：整个过程无平行边产生 —— 这是标准的 preferential attachment 模型设定。

与已有文献相比： - 相比 Bet et al. (2023)：该项工作假设 $\delta_0$ 已知，$\delta_1$ 未知或已知（本文假设已知，但结果可推广）。本文使用的技术（似然比）与 Bet（基于 degree-1 计数）完全不同，且得到更紧的 impossibility 结果（$n^{1/3}$ vs 猜想的 $n^{1/2}$）。 - 相比 Cirkovic et al. (2022)：后者考虑了 labeled 下的 MLE 与 likelihood ratio，但未系统分析 unlabeled 场景。本文是首次在 unlabeled 下给出 rigorous 的 impossibility lower bound。

主要结果¶

Theorem 1（Labeled graph 的可检测性） - 陈述：在 labeled 观测下，检验 $H_0$ vs $H_1$ 是可能的当且仅当 $\Delta_n \to \infty$。更精确地，存在一个检验（基于 labeled 似然比）使得：若 $\Delta_n \to \infty$，则其功效趋于 1；若 $\Delta_n = O(1)$（有界），则对任意检验，其功效不能大于显著性水平 $\alpha$ 的某个常数倍。 - 直觉：Labeled 图蕴含了每个顶点加入的准确时间步。如果 $\Delta_n$ 有界（如 $\Delta_n \le 10$），那么我们只能观察到变点后的少数几步，这些步中包含的变点“信号”太少，以至于无法支持可靠检测。反之，只要 $\Delta_n$ 无界增长，信号最终积累到可被检测。 - 必要条件：$\Delta_n \to \infty$ 是这个问题的相变条件（sharp threshold）。证明依赖对 labeled 似然比在 $H_0$ 和 $H_1$ 下的渐近方差分析。

Theorem 2（Unlabeled graph 的不可检测性） - 陈述：若 $\Delta_n = o(n^{1/3})$，则在 unlabeled 观测下，任何检验的功效（power）趋于显著性水平 $\alpha$。即，不可能一致地检测到变点。 - 直觉：证明的信息论核心是：当 $\Delta_n$ 远小于 $n^{1/3}$ 时，$H_0$ 和 $H_1$ 下产生的 unlabeled 图 $G_n$ 的分布之间总变差距离 (TV distance) 趋于 0。因此没有检验能区分。 - 必要条件：证明仅覆盖了 $\Delta_n = o(n^{1/3})$，而 Bet 猜想关口是 $\Delta_n = o(n^{1/2})$。因此 gap 仍在。证明需突破的关键是：将 unlabeled 图的似然比写为 labeled 似然比在均匀置换下的平均（即关于未标签的边际化）。这一平均化的困难在于 置换求和 的复杂度，需要精细的 combinatorial 界来控制。

Corollary 1（对 Bet 猜想的验证） - 陈述：若 $\Delta_n = o(n^{1/3})$，满足 Bet 猜想的条件（$\Delta_n = o(n^{1/2})$），因此证实了猜想的一个子集。 - 证明：直接从 Theorem 2 得出。

证明路线与技术技巧¶

整体路线（3-5步逻辑主干）：

Step 1：写出 labeled 下的似然比 - 在 labeled 场景下，变点检测的似然比（$H_1$ vs $H_0$）可以显式写出：

\[\Lambda_n^{\text{labelled}} = \prod_{t = \tau_n+1}^{n} \frac{ \prod_{v \in \text{nbr}(v_t)} (\deg_{t-1}(v) + \delta_1) }{ \prod_{v \in \text{nbr}(v_t)} (\deg_{t-1}(v) + \delta_0) }\]

其中 $\text{nbr}(v_t)$ 表示新顶点 $v_t$ 连接的 $m$ 个邻居。 - 关键：这是步与步之间条件独立的乘积形式，因此易于通过鞅方法分析其渐近性质。

Step 2：labeled 下的检测结论（Theorem 1） - 将 $\Lambda_n^{\text{labelled}}$ 在 $H_0$ 下用 $\chi^2$ 波动作为考试统计量。直接用 Cela 不等式（Hoeffding 型）证明：当其对数 $\log \Lambda_n$ 的期望与方差都随 $\Delta_n$ 发散时，检验功效 $\to 1$。而当 $\Delta_n = O(1)$ 时，$\log \Lambda_n$ 的方差有界，故无法区分。

Step 3：unlabeled 下的似然比 = labeled 似然比的置换平均 - 令 $\sigma : [n] \to [n]$ 为一个置换（将顶点编号映到时间顺序）。则 unlabeled 似然比 $LR_n^{\text{unlabelled}}$ 是在所有可能的 $\sigma$ 下 $\Lambda_n^{\text{labelled}}$ 的平均。 - 数学上：

\[LR_n^{\text{unlabelled}} = \frac{1}{n!} \sum_{\sigma} \Lambda_n^{\text{labelled}, \sigma}\]

。 - 注意 $\Lambda_n^{\text{labelled}, \sigma}$ 本质上与 $\Lambda_n^{\text{labelled}}$ 相同，只是经过了置换。控制这个平均的难度在于：邻域结构随置换变化，求和项数超大（$n!$）。

Step 4：核心 bound：对 $LR_n^{\text{unlabelled}}$ 的方差/期望比 - 定义 $D_n = \text{TV}(P_0, P_1)$ 为两个分布的总变差距离。为证明 impossibility，需证明 $D_n \to 0$。 - 通过 Pinsker 不等式或 Hoffman-Trevisan 方法，$D_n^2 \le \frac12 \mathbb{E}_0[ (LR_n^{\text{unlabelled}})^2 ]$。 - 问题归结为：证明 $\mathbb{E}_0[ (LR_n^{\text{unlabelled}})^2 ] \to 1$ 当 $\Delta_n = o(n^{1/3})$。

Step 5：最困难的部分：控制 $LR_n^{\text{unlabelled}}$ 的二阶矩 - 展开：

\[\mathbb{E}_0[ (LR_n^{\text{unlabelled}})^2 ] = \mathbb{E}_0\left[ \frac{1}{(n!)^2} \sum_{\sigma_1, \sigma_2} \Lambda_n^{\text{labelled}, \sigma_1} \Lambda_n^{\text{labelled}, \sigma_2} \right]\]

- 使用本地极限理论（local limit theory for random graphs）：对于每个固定的 $\sigma_1, \sigma_2$，$\Lambda_n^{\text{labelled}, \sigma_1} \Lambda_n^{\text{labelled}, \sigma_2}$ 的期望与 $H_0$ 下某一“双标签耦合”概率相关。该耦合的渐近行为可通过度分布的高斯近似（Edgeworth 展开）刻画。 - 最终 bound 需要控制置换对重叠数的影响：当 $\sigma_1$ 与 $\sigma_2$ 在时间轴上的时间跨度差距很小时，$\Lambda_n^{\text{labelled}, \sigma_1} \Lambda_n^{\text{labelled}, \sigma_2}$ 更倾向于接近 1。而这些“接近”组合的总计数与 $n^{1/3}$ 密切相关，最终导致当 $\Delta_n = o(n^{1/3})$ 时二阶矩趋于 1。

关键跳跃点： - 引理 4（Lemma 4）：证明对于任意置换 $\sigma$，$\Lambda_n^{\text{labelled}, \sigma}$ 的均值为 1，且方差有界（不依赖于 $\sigma$）。这个引理建立了 labeled 似然比在 $H_0$ 下的基准行为。 - 引理 8（Lemma 8）：对 $\mathbb{E}_0[ \Lambda_n^{\text{labelled}, \sigma_1} \Lambda_n^{\text{labelled}, \sigma_2} ]$ 给出显式 bound，该 bound 取决于 $\sigma_1$ 和 $\sigma_2$ 的时间轴 joint distribution。关键参数是偏移量 $\ell = |\sigma_1^{-1}(v) - \sigma_2^{-1}(v)|$ 的分布。 - 引理 9（Lemma 9）：核心的 combinatorial 推论：对 $\Delta_n$ 求和后，若 $\Delta_n = o(n^{1/3})$，则总变差距离 $D_n \to 0$。

技术技巧点名： - 似然比分解与鞅：用于 labeled 情况下的渐近分析。 - 置换平均 + 组合 bounds：unlabeled 下将检验统计量视为 labeled 似然比的均匀平均，这正是处理“无标签”问题的标准技巧。 - 本地极限理论（Local Limit Theorem）：用于控制 $\Lambda_n^{\text{labelled}, \sigma} $ 的平方期望，这是最细腻的部分。需要随机图度分布的局部 Gaussian 近似。 - Hoffman-Trevisan bound：通过 KL 散度 或 Hellinger 距离控制总变差距离，转换为二阶矩问题。 - Chaining / Union bound 技巧：用于处理大量置换的组合求和，保证 bound 不随 $n!$ 发散。

真实例子与应用¶

本文为纯理论，无实证例子。 唯一提到“实际例子”的是：作者在引言中提及他们的结果与 Bet et al. 的构念一致，但未做任何模拟或数据实验。这是一个纯理论论文。

🔎 结论是否比证明窄¶

存在若干 claim 超出了证明的严格覆盖范围：

Theorem 2（unlabeled impossibility）的陈述是“当 $\Delta_n = o(n^{1/3})$ 时检测不可能”，但作者在引言中写为“部分验证了 Bet 的猜想（$\Delta_n = o(n^{1/2})$）”。应注意到：$o(n^{1/3})$ 比 $o(n^{1/2})$ 强（更严格），因此本文只验证了更小的一类条件。如在正文中，作者写“we make a step towards proving the conjecture by proving the impossibility ... when $\Delta_n = o(n^{1/3})$.” 这比猜想的 $o(n^{1/2})$ 弱，本文并未完全证明猜想。
关于 labeled 情况的必胜条件（Theorem 1）：仅对已知 $\delta_1$（或可 worst-case 化的变点后参数）成立。作者在引言中称“labeled graph ... detection is possible if and only if $\Delta_n \to \infty$”，这个严格性只在 $\delta_1$ 已知时保证；如需处理未知 $\delta_1$，需额外步骤（taking supremum over $\delta_1$），但作者在正文注释了伸展是直接的。
关于 $\delta_0$ 和 $\delta_1$ 的绝对值：Theorem 2 在证明中隐含了 $|\delta_1 - \delta_0|$ 固定（不趋于 0）的条件。如果 $\delta_1$ 趋近 $\delta_0$（即小效应），那么门槛可能变化。这在正文中未明确讨论。
幂律 exponent 的影响：文中只说了“当 $\Delta_n = o(n^{1/3})$ 时”，但没有说明 $m=1$ 和 $m>1$ 的差异是否影响门槛的常数。原则上，$m$ 增大（每次加多条边）可能会放大变点信号，但 Theorem 2 的证明未显式分离 $m$ 的作用。

四、开放问题（点到为止，扎根具体语句）¶

完全的 Bet 猜想：本文只验证了 $\Delta_n = o(n^{1/3})$，但猜想是 $o(n^{1/2})$。是否能通过改进本地极限理论或找到更紧的组合 bound 来将门槛从 $n^{1/3}$ 提升到 $n^{1/2}$？这对应了本文 Theorem 2 和 Abstract 中“step towards proving the conjecture”的明确 gap。要确认这个 gap 是否真实存在，建议阅读近期 5 篇关于随机图检测 impossibility 下界的工作（如 Ben-Hamou et al. (2024) 对随机块模型的检测下界），看他们是否也使用 $o(n^{1/3})$ 类似的限制。
Optimal detection regime：如果 $\Delta_n$ 大于 $n^{1/3}$（甚至达到 $\Theta(n^{1/2})$），是否存在一个检验能达到这个门槛？本文只给出了 impossibility，未给出 matching upper bound。这就需要构造一个检验（例如基于更精细的子图计数或度谱分析）并证明其在 $\Delta_n \gg n^{1/3}$ 时拥有非平凡功效。这在作者 Section 6 (Discussion) 中被提到： “an interesting question remains: is detection possible for $\Delta_n = n^{1/2}$?” 这正是 next step.
非affine attachment函数：本文严格限于 affine (linear) preferential attachment。但实际网络（如 citation network）的 attachment 机制可能更一般（sublinear, superlinear, time-varying）。之前 Gao et al. (2017) 提出了更一般的 sublinear 估计。对这类更一般的 attachment 函数，变点检测是否也有“labeled vs unlabeled”的 sharp 差异？这需要本文的似然比框架推广到非线性情形。这在 Cirkovic et al. (2022) 的变体估计中已被部分处理，但作者未提及推广。
多变点与多个变点后阶段：本文只讨论单个变点。若出现多个变点（Cirkovic et al. 2022 考虑了多变的 MLE）、或变点后参数再次变化，会导致检测困难度的叠加还是抵消？作者在 introduction 里提到“the effect of the change point does not change the degree exponent” (Bhamidi et al. 2015)，但多变点下度指数可能更复杂。

Maintained by 陈星宇 · Homepage · Source on GitHub