跳转至

Network Cross-Validation for Nested Models by Edge-Sampling

讲者: Yuanxing Chen
会场: Prediction-Powered Inference and Network Data Analysis
报告题目: Penalized Network Cross-Validation for Nested Models by Edge-Sampling
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向解决的根本问题是：在拥有多种候选网络模型（如随机块模型SBM、度修正块模型DCBM、图模型graphon）时，如何从数据中一致地选出最能描述观测网络结构的那个模型（包括模型类与模型内参数，如社区数K）。当前成熟度：在单一模型类内（如确定SBM的社区数K）已有较成熟的理论与方法，但跨不同模型类（如SBM vs. DCBM, SBM vs. graphon）的选择问题，在本文之前缺乏严格的统计一致性理论。

发展脉络

  1. 奠基工作：网络模型本身的发展为模型选择提供了候选对象。Erdős–Rényi (1960) 的随机图模型是起点；Holland et al. (1983) 提出SBM，成为社区检测的核心模型；Karrer and Newman (2011) 提出DCBM，通过引入节点度异质性参数θ_i 来克服SBM假设同社区内节点度相同的限制；Aldous (1981) 的图模型则提供了一个非参数化的泛化框架。这些模型之间存在嵌套关系（SBM ⊂ DCBM ⊂ graphon），为嵌套模型选择提供了结构基础。

  2. 主要进展：社区数确定（单一模型类内）：大量工作聚焦于在给定模型类（如SBM或DCBM）内确定社区数K。代表性方法包括：

  3. 似然方法：Wang and Bickel (2017) 和 Hu et al. (2020) 发展了基于似然的模型选择准则。
  4. 谱方法：Le and Levina (2022) 和 Hwang et al. (2024) 利用谱特征来估计K。
  5. 检验方法：Wu et al. (2024) 提出特征间隙比检验；Jin et al. (2023) 和 Ma et al. (2021) 发展了序贯检验程序。

  6. 交叉验证方法：Chen and Lei (2018) 提出节点分裂CV，Li et al. (2020) 提出边采样CV（ECV），两者都旨在防止欠拟合，但未能有效防止过拟合，且通常需要预设社区数的上界。

  7. 当前前沿与本文位置：尽管社区数确定问题已被广泛研究，但跨模型类的选择（如SBM vs. DCBM, SBM vs. graphon）在本文之前“没有严格的统计理论框架”（作者原话）。本文声称填补了这一空白，提出了一个带惩罚的边采样嵌套网络交叉验证（PNN-CV）框架，并首次为这些跨类比较提供了一致性保证。

子线索聚类

  1. 社区数确定方法：包括似然方法（Wang and Bickel, 2017; Hu et al., 2020）、谱方法（Le and Levina, 2022; Hwang et al., 2024）、检验方法（Wu et al., 2024; Jin et al., 2023; Ma et al., 2021）和CV方法（Chen and Lei, 2018; Li et al., 2020）。这些方法主要处理单一模型类内的选择，且通常需要预设上界。

  2. 网络交叉验证方法：包括节点分裂（Chen and Lei, 2018）和边采样（Li et al., 2020）。这些方法将CV思想引入网络数据，但理论分析主要针对欠拟合，对过拟合的防范不足。

  3. 模型类比较：本文是这一子线索的核心工作，直接处理SBM、DCBM和图模型之间的选择。此前，作者指出“没有严格的统计理论框架”用于跨类比较。

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

  1. 如何同时防止欠拟合和过拟合？ 现有CV方法（如ECV）能防止欠拟合（选择过小的模型），但容易过拟合（选择过大的模型）。本文通过引入模型复杂度惩罚项来解决。
  2. 如何在不预设社区数上界的情况下进行一致选择？ 现有方法通常需要预设一个上界，这可能影响准确性。本文的惩罚机制允许候选集为整个[n]。
  3. 如何为跨模型类比较提供理论保证？ 这是本文的核心贡献，即首次为SBM vs. DCBM, SBM vs. graphon等比较提供一致性定理。
  4. 如何定义和量化不同模型类之间的“距离”或“可区分性”？ 本文通过定义“分离界”（separation bound）和“变化程度”（如Definition 4, 5）来刻画。

⚠️ 作者的framing

  • 作者把缺口frame成什么：作者将缺口frame为“缺乏跨模型类选择的严格理论框架”，并声称本文提供了“第一个一致性保证”。具体来说，作者强调现有CV方法（如ECV）在跨类比较时缺乏理论支持，且容易过拟合。本文的惩罚项被视为“关键理论创新”，因为它“显式地随模型复杂度缩放，以有效正则化选择过程”。
  • 哪些竞争路线被淡化或回避：
  • 节点分裂CV (Chen and Lei, 2018)：作者指出该方法在“Political Books”数据集上只用了SBM，因为担心过拟合。本文通过展示DCBM拟合更好来间接批评其保守性。
  • 似然方法 (Wang and Bickel, 2017; Hu et al., 2020)：这些方法主要针对单一模型类内的社区数选择，作者未深入讨论它们是否可扩展到跨类比较。
  • 谱方法 (Le and Levina, 2022)：作者在DCBM vs. SBM比较中使用了BHMC（一种谱方法）来估计K，但未将其作为模型选择方法本身。
  • 什么明显该被引/该存在、却没出现在intro里？：论文主要关注嵌套模型，但未讨论非嵌套模型（如SBM vs. 指数随机图模型ERGM）的选择问题。此外，对于图模型估计，作者只引用了Neighborhood Smoothing (Zhang et al., 2017) 和USVT (Chatterjee, 2015)，但未提及更近期的图模型估计方法（如基于网络矩的方法）。（这是值得研究者去查的问题：图模型估计领域是否有更优的估计器，其收敛速度可能改变本文定理的条件？）

张力

未见明显对立引用。所有被引工作基本在各自子问题（社区数确定、CV方法、模型估计）上形成共识，即跨类选择是一个开放问题。本文是第一个系统性尝试。

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

第一步：符号、模型与可观测数据

  • 符号：
  • n：节点数。
  • A：n × n 对称邻接矩阵，A_ij ∈ {0, 1}，A_ii = 0。
  • P：n × n 对称概率矩阵，P_ij = P(A_ij = 1)。
  • K：社区数（SBM/DCBM的参数）。
  • c = (c_1, ..., c_n)：节点社区归属向量，c_i ∈ [K]。
  • B：K × K 块间连接概率矩阵（SBM/DCBM参数）。
  • θ = (θ_1, ..., θ_n)：节点度异质性参数（DCBM特有）。
  • f：图函数（graphon），f: [0,1]² → [0,1]。
  • w：训练边比例（0 < w < 1）。
  • E：训练边集，E^c：评估边集。
  • Y：部分观测邻接矩阵，Y_ij = A_ij 若 (i,j) ∈ E，否则为0。
  • δ(m)：第m个模型类（如SBM、DCBM、graphon）。
  • d_m：模型δ(m)的复杂度度量（如SBM的K(K+1)/2）。
  • λ_n：惩罚项（可随机）。
  • L_m：带惩罚的损失函数。
  • ℓ_m：预测平方损失（不带惩罚）。

  • ℓ_0：Oracle损失，使用真实P。

  • 模型：

  • SBM：P_ij = B_{c_i, c_j}，其中B是K×K对称矩阵。社区归属c和块概率B是待估参数。
  • DCBM：P_ij = θ_i θ_j B_{c_i, c_j}，其中θ_i是节点度参数，满足约束Σ_{i: c_i=k} θ_i² = n_k（社区k的大小）。SBM是θ_i ≡ 1的特例。
  • Graphon：P_ij = f(ξ_i, ξ_j)，其中ξ_i ~ i.i.d. Uniform(0,1)，f是图函数。SBM是f为阶梯函数的特例。

  • 嵌套关系：SBM(K) ⊂ DCBM(K) ⊂ Graphon。即，SBM是DCBM的特例，DCBM是Graphon的特例。

  • 可观测数据：

  • 可观测：邻接矩阵A（所有A_ij）。这是唯一直接观测到的数据。
  • 潜在/不可观测：
    • 真实概率矩阵P。
    • 社区归属c（SBM/DCBM）。
    • 块概率矩阵B（SBM/DCBM）。
    • 度参数θ（DCBM）。
    • 图函数f和潜在变量ξ_i（Graphon）。
  • 识别依赖：所有模型选择都依赖于对P的估计。估计P需要从A中推断出这些潜在结构。本文通过边采样CV，在训练集E上估计P（得到\hat{P}），然后在评估集E^c上评估预测误差。

第二步：最小内核——在SBM中确定社区数K

本文的核心思想可以用一个最简特例来理解：在SBM中确定社区数K。这是论文Section 3的内容，也是整个框架的基础。

问题：给定一个由SBM生成的网络（真实社区数为K*），我们希望从候选集K = {1, 2, ..., n}中选出K*。

标准CV（如ECV）的困境： - 欠拟合：如果选K < K*，模型太简单，无法捕捉真实结构，在评估集上的预测误差会很大。CV能检测到这一点，从而避免欠拟合。 - 过拟合：如果选K > K*，模型更复杂，可能拟合了训练集中的噪声。但由于CV的评估集与训练集独立，过拟合的模型在评估集上的预测误差不一定比真实模型大，甚至可能更小（因为更复杂的模型可以更好地拟合评估集中的噪声模式）。因此，标准CV倾向于选择过大的K。

本文的解决方案（PNN-CV）： 1. 边采样：随机将n(n-1)/2个上三角边对分配到训练集E（概率w）和评估集E^c（概率1-w）。 2. 模型拟合：对于每个候选K，在训练集E上估计SBM。具体步骤： - 对部分观测矩阵Y进行秩为K的截断SVD，得到恢复的邻接矩阵\hat{A}^{(K)}。 - 对\hat{A}^{(K)}进行谱聚类，得到估计的社区标签\hat{c}^{(K)}。 - 基于\hat{c}^{(K)}和训练集E中的边，估计块概率矩阵\hat{B}^{(K)}（公式3.2）。 - 得到概率矩阵估计\hat{P}^{(K)}。 3. 评估：计算带惩罚的损失： L_K = (1/|E^c|) * Σ_{(i,j)∈E^c} (A_ij - \hat{P}^{(K)}_ij)² + d_K * λ_n 其中d_K = K(K+1)/2是模型复杂度（SBM的自由参数数），λ_n是惩罚项。 4. 选择：选择使L_K最小的K。

为什么惩罚能防止过拟合？ - 当K > K*时，模型更复杂（d_K更大）。标准CV的预测损失(1/|E^c|) * Σ (A_ij - \hat{P}^{(K)}_ij)²可能略小于真实模型（由于过拟合），但加上d_K * λ_n后，总损失L_K会变大。只要λ_n选择得当，就能使过拟合模型的总损失超过真实模型。 - 当K < K*时，模型欠拟合，预测损失很大，即使加上较小的惩罚项，总损失也很大。 - 因此，通过选择合适的λ_n（其阶数由Theorem 1的条件给出），PNN-CV可以同时防止欠拟合和过拟合，实现一致选择。

这个最小内核揭示了论文的核心数学困难：如何选择λ_n的阶数，使得它足够大以惩罚过拟合模型，但又足够小以避免惩罚真实模型？这需要对不同K下的预测误差的渐近行为有精确刻画（即Proposition A.1, A.2, A.3），这正是论文证明工作的核心。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：为嵌套网络模型（SBM、DCBM、Graphon）的跨类选择问题，提出了一个带惩罚的边采样交叉验证框架（PNN-CV），并建立了模型选择一致性的理论保证。
  2. 核心工具/方法：边采样CV + 模型复杂度惩罚项 + 模型特定的矩阵补全/估计算法（如截断SVD、谱聚类、球面谱聚类、邻域平滑）。
  3. 主要结论：在适当的正则条件下，PNN-CV能够以概率趋于1地选择出正确的模型（包括正确的模型类和正确的社区数K）。这是首次为SBM vs. DCBM, SBM vs. Graphon等跨类比较提供一致性保证。

关键设定与假设

  • 嵌套模型：论文假设候选模型是嵌套的（Definition 1），即更简单的模型是更复杂模型的子集。这适用于SBM ⊂ DCBM ⊂ Graphon。
  • 边采样：训练边集E通过独立同分布地以概率w采样每个上三角边对得到。w可以是常数或随n变化。
  • 估计程序：对于每个候选模型，论文假设存在一个估计程序\hat{δ}^{(m)}，其收敛速度由a_{n,w,m}刻画（Definition 2），且当模型错误时，其估计误差有下界b_{n,w,m}（Definition 3）。
  • 关键假设：
  • Assumption 1 (正确模型收敛)：对于所有大于等于真实模型的候选模型，估计器以速率a_{n,w,m'}收敛到真实P。
  • Assumption 2 (错误模型分离)：对于所有小于真实模型的候选模型，估计器与真实P至少相距b_{n,w,m'}。
  • Assumption 3 (一致性条件)：(1-w_n)b_{n,w} / max{√(a_{n,w}(1-w_n)||P||_∞), a_{n,w}} = ω(1) 且 n²(1-w_n)b_{n,w} = ω(1)。这保证了惩罚项λ_n的存在性，使得√(a_{n,w}(1-w_n)||P||_∞)和a_{n,w}远小于(1-w_n)λ_n，而(1-w_n)λ_n又远小于(1-w_n)b_{n,w}。
  • SBM特定假设：Assumption 4（平衡社区结构），Assumption 5（度条件ρ_n = Ω(log n/n)，B_0非奇异且行不同）。
  • DCBM特定假设：Assumption 6（度参数可识别性约束），Assumption 7（θ_i有界），Assumption 8（B_0正定且特征值有间隙），Assumption 9（度异质性足够大，a_{n,K*} ≫ n^{-1/4}ρ_n^{-1/4}w_n^{-1/4}）。
  • Graphon特定假设：Assumption 10（图模型估计器有已知收敛速率a_{n,w}），Assumption 11（图模型与SBM足够不同，b_{n,K}大于一个复杂表达式），Assumption 12（估计的社区标签平衡）。

主要结果

  1. Theorem 1 (SBM内K的选择)：在Assumptions 4-5下，若λ_n满足三个条件（o_P(ρ_n²), w_P(ρ_n/(n w_n)), w_P(log n/(n²(1-w_n)))），则P(\hat{K} = K*) → 1。关键：不要求候选集K有界，允许K = [n]。
  2. Theorem 2 (Affiliation SBM vs. General SBM)：在Theorem 1的条件下，若d_{1k}=2, d_{2k}=k(k+1)/2，则P((\hat{m}, \hat{K}) = (m*, K*)) → 1。
  3. Theorem 3 (SBM vs. DCBM)：在Assumptions 4-9下，若d_{1k}=k(k+1)/2, d_{2k}=k(k+3)/2，且λ_n满足o_P(ρ_n² a_{n,K})和w_P(ρ_n^{7/4} n^{-1/4} w_n^{-1/4})，则P((\hat{m}, \hat{K}) = (m*, K*)) → 1。关键：需要度异质性足够大（Assumption 9），否则SBM和DCBM不可区分。
  4. Theorem 4 (SBM vs. Graphon)：在Assumptions 4-5, 10-12下，若d_{1,k}=k(k+1)/2, d_2 = n^{3/4} / log^{1/2} n，且max K = O(n^{1/4})，λ_n满足特定条件，则P((\hat{m}, \hat{K}) = (m*, K*)) → 1。关键：图模型必须与任何SBM足够不同（Assumption 11），且SBM的候选社区数不能增长太快（O(n^{1/4})）。

证明路线与技术技巧

整体路线：论文的证明框架基于一个通用命题（Proposition 1），该命题将模型选择一致性问题归结为验证三个条件： 1. 正确模型的上界：对于所有大于等于真实模型的候选，其预测损失与Oracle损失之差有上界（由a_{n,w}控制）。 2. 错误模型的下界：对于所有小于真实模型的候选，其预测损失与Oracle损失之差有下界（由b_{n,w}控制）。 3. 惩罚项阶数：λ_n的阶数介于上界和下界之间，使得惩罚项能区分正确和错误模型。

然后，论文针对每个具体场景（SBM内、SBM vs. DCBM、SBM vs. Graphon），分别推导a_{n,w}和b_{n,w}的具体阶数，并验证Proposition 1的条件。

关键跳跃点： - SBM内K的选择：证明的核心在于刻画不同K下预测损失的渐近行为。对于K < K*（欠拟合），需要证明预测损失有Ω_P(n²ρ_n²(1-w))的下界（Proposition A.1）。这依赖于Lemma A.7，该引理指出当K < K*时，必然存在两个真实社区被合并，导致估计的块概率与真实值有显著差异。对于K > K*（过拟合），需要证明预测损失不会太小，即不会显著小于Oracle损失（Proposition A.2, A.3）。这通过将预测损失分解为每个估计块内的方差项来实现，并利用Hoeffding不等式进行概率控制。 - SBM vs. DCBM：证明的难点在于DCBM的估计误差分析。Proposition A.6给出了DCBM估计器预测损失的上界O_P(n^{7/4} ρ_n^{7/4} w^{-1/4} (1-w))。这需要精细地控制度参数θ的估计误差（Lemma A.10, A.11），以及块概率矩阵B的估计误差（公式A.23）。关键技巧是定义“好节点集”S_n（其中θ估计误差小），并分别处理S_n内和S_n外的节点对。 - SBM vs. Graphon：证明的核心是Proposition A.10，它给出了当真实模型为Graphon时，SBM估计器预测损失的下界Ω_P((1-w)n² b_{n,K})。这需要证明，对于任何平衡的社区划分，Graphon的真实概率矩阵与SBM的最佳块常数近似之间存在一个不可忽略的差距（由b_{n,K}刻画）。证明中使用了Hoeffding不等式和Union bound来处理所有可能的社区划分。

技术技巧点名： - Hoeffding不等式 & Bernstein不等式：贯穿全文，用于控制各种随机变量的偏差（如|E^c|的集中性、块内平均的偏差、预测损失的偏差）。 - 谱聚类 & 球面谱聚类：用于从恢复的邻接矩阵\hat{A}中估计社区标签。 - 低秩矩阵补全（截断SVD）：用于从部分观测矩阵Y中恢复完整的邻接矩阵\hat{A}（公式3.1）。 - Davis-Kahan定理的变体：用于控制特征向量估计误差（Lemma A.4, A.12）。 - Eldridge et al. (2017) 的逐元素特征向量分析：用于精细控制DCBM中度参数θ的估计误差（Lemma A.10）。 - 邻域平滑（NS）算法：用于估计Graphon模型（Proposition 2）。 - Union bound：用于处理多个候选模型或多个可能社区划分的情况。

真实例子与应用

  • 数据：“Political Books”网络（Krebs, 2004），包含105个节点（政治书籍），边表示频繁共同购买。书籍被手动标记为“中立”、“自由”、“保守”三类。
  • 方法应用：
  • 设定1：假设K=3（与手动标签一致），比较SBM-3和DCBM-3。
  • 设定2：不假设K，让PNN-CV同时选择模型类和K。
  • 对比方法：ECV（Li et al., 2020）。
  • 结果：
  • 设定1：PNN-CV在所有数据分割比例（2-fold到15-fold）下都100%选择DCBM-3，而ECV的选择不稳定，且倾向于选择更大K的DCBM。
  • 设定2：PNN-CV在所有分割比例下都100%选择DCBM-4。
  • 这个例子想说明什么：
  • 验证方法优势：PNN-CV比ECV更稳定，且能有效防止过拟合（ECV倾向于选择大K）。
  • 提供新见解：即使节点数只有105，DCBM也比SBM更适合该数据集，反驳了Chen and Lei (2018) 因担心过拟合而只使用SBM的做法。这表明该网络存在显著的度异质性。
  • 展示灵活性：PNN-CV不需要预设K的上界，能自动选择最优的K（本例中为4），揭示了手动标签可能未捕捉到的更细粒度结构（自由派书籍被分为两个子社区）。

🔎 结论是否比证明窄

  • Theorem 4 (SBM vs. Graphon) 的证明依赖于max K = O(n^{1/4})的假设（Remark 8）。作者承认当K增长更快时（如Ω(n^{1/3})），当前技术不足以保证一致性，并指出这“可能值得未来研究”。因此，该定理的结论在K增长较快时是不成立的，作者将其作为一个开放问题。
  • Theorem 3 (SBM vs. DCBM) 的证明依赖于Assumption 9，即度异质性必须足够大。如果θ_i只是常数的一个小扰动，则SBM和DCBM不可区分，一致性不成立。作者在Remark 2中承认了这一点。
  • Theorem 4 的证明还依赖于Assumption 11，即Graphon必须与任何SBM足够不同。如果Graphon非常接近一个SBM（例如，是一个近乎阶梯的函数），则一致性可能不成立。作者在Remark 5中讨论了这一点。
  • 总体而言，论文的结论是条件性的，依赖于一系列假设。这些假设在理论上刻画了模型可区分的边界，但在实际应用中可能难以验证。论文的贡献在于首次明确了这些边界条件，而非提供一个无条件适用的万能方法。

四、开放问题

  1. 扩展到非嵌套模型：论文仅处理嵌套模型。如何将PNN-CV扩展到非嵌套模型（如SBM vs. 指数随机图模型ERGM）？这需要重新定义“模型复杂度”和“分离界”。（扎根于：论文只讨论了嵌套模型，未提及非嵌套情况。）
  2. 处理有向网络和二分网络：论文专注于无向网络。扩展到有向或二分网络需要重新设计边采样方案和模型估计方法。（扎根于：Section 8 Discussion 第一点。）
  3. 纳入协变量信息：许多网络数据伴随节点或边的协变量。如何将协变量纳入模型选择过程，并选择涉及协变量的模型？（扎根于：Section 8 Discussion 第二点。）
  4. 放松K的增长速度限制：Theorem 4要求max K = O(n^{1/4})。作者指出当K增长更快时（如Ω(n^{1/3})）理论不成立。能否通过改进技术（如更精细的复杂度度量）来放松这一限制？（扎根于：Remark 8。）
  5. DCBM内社区数K的CV选择：Remark 4指出，通过CV选择DCBM的社区数在理论上仍然具有挑战性，并被视为一个有趣的未来方向。这直接关联到研究者对高阶U统计量和计算复杂性的兴趣，因为DCBM的估计可能涉及更复杂的计算。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论