Conformal Prediction for Network-Assisted Regression¶
作者: Robert Lunde, Elizaveta Levina, Ji Zhu
来源: Journal of the American Statistical Association
主题: 非参数 / 半参数
相关性: 6/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么： 这个子方向要解决的根本统计问题是：在观测到一个图（网络）及其节点属性时，如何为新加入或观测不完整的节点的响应变量构造具有有限样本覆盖保证的预测区间。核心困难在于，节点的网络协变量（如嵌入坐标、子图计数）与常规协变量（如人口统计学特征）之间由于网络拓扑的连接而产生复杂的依赖结构，这使得基于节点独立抽样的经典推断方法（包括经典保形预测）的覆盖保证失效。当前该方向的成熟度处于"方法刚提出、理论保证初步建立"的阶段：已有工作证明了在特定网络可交换性下保形预测的边际有效性，但对条件有效性（即针对特定特征组合的覆盖）和更广泛网络协变量的适用性，理论仍留有缺口。
发展脉络（history）： - 奠基工作：Vovk et al. (2005) 与 Shafer & Vovk (2008) 建立了保形预测框架，核心假设是数据点的可交换性，由此推出有限样本下的精确边际覆盖。作者在 intro 中指出这些工作"established finite-sample validity under exchangeability"，但留下了一个口子：网络数据节点之间天然具有依赖，不可交换。 - 主要进展（依赖数据下的保形预测）：为了处理依赖，若干工作尝试放宽可交换性。作者引用了 Barber et al. (2023)（研究时间序列等依赖结构下的保形预测）与 Chernozhukov et al. (2021)（研究横截面依赖）。作者指出这些工作"either require stationarity or impose restrictive dependence structures"，在网络数据中难以直接套用，因为网络依赖既非时间序列平稳，也非简单的横截面相关。 - 网络模型与可交换性：网络数据的自然对称性是联合可交换性（joint exchangeability，又称可交换数组）。作者引用了 Hoover (1982) 与 Aldous (1981) 的可交换数组表示定理，以及 Bickel & Chen (2009) 与 Caron & Fox (2017) 在网络估计中的应用。作者指出这些工作"leveraged exchangeability for estimation"，但未将其用于预测推断。 - 当前 frontier 与本文位置：作者引用了 Lunde et al. (2022)（作者自己的前期工作），这是首次将联合可交换性与保形预测结合的尝试。作者指出该工作"established marginal validity for a restricted class of network covariates"，留下的口子是：协变量类别受限（主要是邻接矩阵的泛函），且未触及条件有效性。本文的位置：放宽协变量类别至广泛的图泛函与节点泛函，并首次在网络保形预测中建立渐近条件有效性。
子线索聚类： 1. 经典保形预测与可交换性：Vovk et al. (2005), Shafer & Vovk (2008), Romano et al. (2019)。这一簇在做：基于 i.i.d. 或可交换假设，构造分布自由的预测区间，并探索条件有效性（通过分位数回归或分箱）。 2. 依赖数据下的保形预测：Barber et al. (2023), Chernozhukov et al. (2021), Musayev (2024)。这一簇在做：在时间序列、横截面依赖等非 i.i.d. 设定下，寻找替代可交换性的结构假设（如平稳性、混合条件），以恢复某种覆盖保证。 3. 网络可交换数组与统计推断：Hoover (1982), Aldous (1981), Bickel & Chen (2009), Caron & Fox (2017)。这一簇在做：用可交换数组表示定理为网络数据提供非参数模型基础，并在此下做参数估计或模型检验，但未涉预测区间。
这个方向在追问的核心问题： 1. 在节点间存在复杂拓扑依赖的网络数据中，能否构造具有有限样本覆盖保证的预测区间？当前瓶颈：经典保形预测要求节点独立或可交换，网络节点既非独立也非逐点可交换。 2. 联合可交换性（一种关于数组排列对称性的弱假设）能否替代逐点可交换性，成为网络保形预测的理论基石？当前瓶颈：联合可交换性只保证数组分布对节点指标重排的不变性，需证明保形预测的覆盖逻辑在此不变性下仍成立。 3. 在网络设定下，能否超越边际覆盖，实现条件覆盖（即对特定 \(X=x\) 的覆盖率达 \(1-\alpha\)）？当前瓶颈：即使在 i.i.d. 设定下，有限样本条件覆盖也已被证明不可能（Barber et al. 2021），只能追求渐近条件覆盖；网络设定下因依赖更重，渐近条件覆盖的建立更困难。
⚠️ 作者的 framing： - 作者把缺口 frame 成：已有网络保形预测（Lunde et al. 2022）只对"受限类别的网络协变量"有效，且缺乏条件有效性；本文通过引入更一般的协变量类别与分箱策略，成为"显然的下一步"。 - 被淡化或回避的竞争路线：作者未讨论基于子图抽样或块抽样的推断方法（如网络抽样推断文献），这些方法通过设计抽样方案规避依赖，而非在依赖结构中寻找对称性。也未讨论基于随机图模型参数推断（如 ERGM）的预测方法，这些方法依赖强参数模型假设，但可能给出更窄的区间。 - 明显该被引却未出现的：网络数据中的社区结构或低秩结构对可交换性的破坏——如果真实网络有社区标签且标签影响响应，联合可交换性可能不成立；作者未引用任何讨论可交换性假设失效或敏感性检验的工作。此外，网络因果推断文献（如利用网络干扰做因果推断）也未出现，尽管预测区间与因果推断的识别假设有深层联系。
张力： 未见明显对立引用。被引工作之间是互补关系：经典保形预测提供框架，依赖数据保形预测提供处理依赖的思路，可交换数组提供网络对称性模型。但存在一个隐含张力：Barber et al. (2021) 证明了有限样本条件覆盖的不可能性，而本文声称渐近条件覆盖——这两者不矛盾，但作者未明确讨论从"不可能"到"渐近可能"的过渡条件（如分箱宽度的选择）如何规避 Barber et al. 的否定结论。
二、最核心、最简单的例子 / 数学问题¶
第一步：符号、模型、可观测数据交代清楚
- 符号：
- \(n\)：观测网络中的节点数。
- \(A \in \{0,1\}^{n \times n}\)：观测到的邻接矩阵，\(A_{ij}=1\) 表示节点 \(i\) 与 \(j\) 有连边。
- \(X_i \in \mathbb{R}^p\)：节点 \(i\) 的常规协变量（如人口统计学特征）。
- \(Y_i \in \mathbb{R}\)：节点 \(i\) 的响应变量。
- \(Z_i\)：节点 \(i\) 的网络协变量，由 \(A\) 与全体 \(X\) 计算得出（如嵌入坐标、度数、局部子图计数）。\(Z_i\) 是 \(A\) 和 \(X\) 的泛函，因此节点间通过 \(A\) 产生依赖。
- \(\tilde{A}, \tilde{X}, \tilde{Y}, \tilde{Z}\)：新节点（测试节点）加入网络后形成的增广数组。\(\tilde{A}\) 包含新节点与旧节点的连边信息。
- \(\pi\)：节点指标的排列。
-
\(\alpha\)：目标覆盖率水平（如 0.9）。
-
模型（数据生成机制）： 数据由一个可交换数组生成。具体而言，存在一个潜在的无穷数组 \((A_{ij}, X_i, Y_i)_{i,j \in \mathbb{N}}\)，其分布满足联合可交换性：对任意有限节点指标的排列 \(\pi: \mathbb{N} \to \mathbb{N}\)，
\[(A_{\pi(i)\pi(j)}, X_{\pi(i)}, Y_{\pi(i)})_{i,j \in \mathbb{N}} \stackrel{d}{=} (A_{ij}, X_i, Y_i)_{i,j \in \mathbb{N}}.\]这意味着：分布对节点指标的重排是不变的。观测数据 \((A_{ij})_{1 \le i,j \le n}, (X_i)_{1 \le i \le n}, (Y_i)_{1 \le i \le n}\) 是该无穷数组的前 \(n\) 个指标的投影。网络协变量 \(Z_i = f_i(A, X)\) 是图泛函，要求 \(f_i\) 在排列下满足特定的等变性或不变性（详见后文）。 -
可观测数据与不可观测量：
- 可观测：对训练节点 \(1, \dots, n\)，观测到 \(A, X_i, Y_i\)，并由此计算出 \(Z_i\)。对测试节点 \(n+1\)，观测到 \(\tilde{X}_{n+1}\)，以及 \(\tilde{A}\) 中新节点与旧节点的连边 \(\tilde{A}_{i, n+1}\)（\(i \le n\)），由此可计算出 \(\tilde{Z}_{n+1}\)。
- 不可观测：测试节点的响应 \(\tilde{Y}_{n+1}\) 是要预测的对象。此外，无穷数组的潜在分布本身不可观测，保形预测不要求估计它，只要求可交换性成立。
第二步：最小内核——联合可交换性下的保形预测覆盖逻辑
剥掉所有一般性设定（如多维协变量、分箱条件覆盖、泛函类别细节），最小内核是：证明在联合可交换性下，保形预测的非一致性得分（nonconformity scores）仍然构成一个可交换序列，从而经典保形预测的覆盖逻辑直接成立。
最简特例：\(d=1\)（单维常规协变量），网络协变量取最简单的度数 \(Z_i = \sum_{j=1}^n A_{ij}\)，非一致性得分取绝对残差 \(R_i = |Y_i - \hat{\mu}(Z_i, X_i)|\)（\(\hat{\mu}\) 是在全体训练数据上拟合的回归函数）。
要证的命题退化成：在联合可交换性下，增广得分序列 \((R_1, \dots, R_n, R_{n+1})\) 的分布对任意排列 \(\pi\) 是不变的。
证明怎么走： 1. 由联合可交换性定义，\((A, X, Y)\) 的分布对节点指标重排不变。 2. 度数泛函 \(Z_i = \sum_j A_{ij}\) 是等变的（equivariant）：对排列 \(\pi\)，新网络中度数 \(Z_{\pi(i)} = \sum_j A_{\pi(i)\pi(j)} = \sum_j A_{ij}\)（因为 \(A\) 的分布不变），即 \(Z\) 随 \(X, Y\) 同步重排。 3. 回归函数 \(\hat{\mu}\) 是在全体训练数据 \((Z_i, X_i, Y_i)_{i=1}^n\) 上拟合的。如果 \(\hat{\mu}\) 是对数据重排不变的泛函（如最小二乘、随机森林等），那么 \(\hat{\mu}\) 在重排后的数据上拟合结果与原结果在排列意义上相同。 4. 因此，绝对残差 \(R_i = |Y_i - \hat{\mu}(Z_i, X_i)|\) 作为 \((A, X, Y)\) 与 \(\hat{\mu}\) 的泛函，其联合分布对排列不变。即 \((R_1, \dots, R_n, R_{n+1})\) 是可交换序列。 5. 由经典保形预测逻辑：如果 \(R_{n+1}\) 与 \(R_1, \dots, R_n\) 可交换，则 \(R_{n+1}\) 在 \(R_1, \dots, R_{n+1}\) 中的秩服从均匀分布。由此，预测区间 \(\hat{C} = \{y : R_{n+1}(y) \le \text{quantile}_{1-\alpha}(R_1, \dots, R_n, R_{n+1}(y))\}\) 的覆盖率精确为 \(1-\alpha\)。
为什么成立的核心：联合可交换性保证了网络协变量（只要它是等变泛函）与响应变量同步重排，从而残差序列恢复可交换性，绕过了节点间的依赖障碍。 论文的一般情形只是将 \(Z_i\) 从度数推广到更广泛的图泛函类，并将边际覆盖推广到渐近条件覆盖。
三、这篇论文做了什么¶
三句话： ①研究了在网络辅助回归中（利用网络协变量与常规协变量预测节点响应），如何构造具有覆盖保证的预测区间问题。 ②核心方法是利用网络数据的联合可交换性假设，证明保形预测的非一致性得分序列仍可交换，从而恢复有限样本边际覆盖，并通过分箱策略实现渐近条件覆盖。 ③主要结论是：对广泛的等变图泛函类（包括嵌入坐标、子图计数等），网络保形预测在有限样本下达到精确边际覆盖 \(1-\alpha\)；在分箱宽度趋于零、样本量趋于无穷的条件下，达到渐近条件覆盖。
关键设定与假设： 在第二节最小记号基础上补全： - 联合可交换性假设（Assumption 1）：\((A_{ij}, X_i, Y_i)_{i,j \in \mathbb{N}}\) 是可交换数组。统计含义：网络数据的生成机制对节点标签无偏好，是网络非参数模型的最弱对称性假设。相比已有文献（如 i.i.d. 假设），它允许节点间通过 \(A\) 产生任意复杂的依赖，只要求整体对称性。相比 Lunde et al. (2022)，该假设相同，但本文在更宽的协变量类下证明覆盖。 - 等变泛函假设（Assumption 2）：网络协变量 \(Z_i = f_i(A, X)\) 必须满足排列等变性：对任意排列 \(\pi\)，\(f_{\pi(i)}(\pi A, \pi X) = f_i(A, X)\)，其中 \(\pi A\) 表示对 \(A\) 的行列同步重排。统计含义：协变量的计算方式必须尊重网络的对称性——如果节点标签重排，协变量值跟着重排，但数值本身不变（如度数、嵌入坐标的排列版本）。相比 Lunde et al. (2022) 只允许邻接矩阵的某些泛函，本文允许任何满足等变性的泛函，包括谱嵌入、局部子图计数等。 - 回归函数的排列不变性：\(\hat{\mu}\) 作为训练数据的泛函，对数据重排不变。统计含义：回归算法不能依赖节点标签的顺序（几乎所有标准算法都满足）。 - 分箱假设（用于条件覆盖）：将协变量空间划分为若干箱 \(B_k\)，新节点落入箱 \(B_k\) 时，只在落入同一箱的训练节点上计算保形分位数。统计含义：通过局部化保形预测，逼近条件覆盖。
主要结果： 1. 定理 1（有限样本边际覆盖）：在联合可交换性与等变泛函假设下，网络保形预测区间 \(\hat{C}_{n+1}\) 的覆盖率为 \(P(\tilde{Y}_{n+1} \in \hat{C}_{n+1}) = 1-\alpha\)。直觉：增广得分序列可交换，新节点得分的秩均匀分布。必要条件：测试节点的连边 \(\tilde{A}_{i, n+1}\) 必须在计算 \(Z_{n+1}\) 前观测到，且 \(Z_{n+1}\) 的计算方式与训练节点的 \(Z_i\) 一致（等变性）。解决的技术难点：在节点依赖下证明得分序列的可交换性——关键在于联合可交换性保证了全体变量（包括网络泛函）的同步重排。 2. 定理 2-3（渐近条件覆盖）：在分箱策略下，如果分箱宽度趋于零（箱数趋于无穷但每箱样本量也趋于无穷），且回归函数 \(\hat{\mu}\) 一致收敛于真实条件均值 \(\mu(z,x)\)，则条件覆盖率 \(P(\tilde{Y}_{n+1} \in \hat{C}_{n+1} \mid \tilde{Z}_{n+1}=z, \tilde{X}_{n+1}=x) \to 1-\alpha\)。直觉：分箱将连续条件变量离散化，在每箱内近似可交换，箱越细条件越精确，回归估计越准残差越近似同分布。必要条件：每箱内需有足够节点（需网络总节点数 \(n \to \infty\)），且回归估计有一致收敛速率。解决的技术难点：条件覆盖在有限样本下不可能（Barber et al. 2021），本文通过渐近分析绕过——分箱宽度与样本量的双极限需要精细平衡。
证明路线与技术技巧： - 整体路线（定理 1）： 1. 建立联合可交换性 → 增广数组 \((\tilde{A}, \tilde{X}, \tilde{Y})\) 的分布对排列不变。 2. 证明等变泛函 \(Z_i\) 在排列下同步重排 → 增广协变量 \((Z_1, \dots, Z_n, \tilde{Z}_{n+1})\) 与 \((X_1, \dots, X_n, \tilde{X}_{n+1})\) 联合可交换。 3. 证明回归函数 \(\hat{\mu}\) 的排列不变性 → 残差 \(R_i\) 作为 \((Z_i, X_i, Y_i)\) 与 \(\hat{\mu}\) 的泛函，在排列下同步重排。 4. 得出增广残差序列 \((R_1, \dots, R_n, R_{n+1})\) 可交换 → 新节点残差 \(R_{n+1}\) 的秩均匀分布。 5. 由秩均匀分布推出覆盖率 \(1-\alpha\)。 - 整体路线（定理 2-3，渐近条件覆盖）： 1. 将协变量空间分箱 → 在每箱内，节点近似可交换（因联合可交换性在箱内子集上仍成立）。 2. 分析分箱保形预测的覆盖率 → 覆盖率偏差来自两部分：箱内残差非同分布（因条件均值估计误差 \(\hat{\mu} - \mu\) 不为零）、箱内离散化误差（箱非无穷小）。 3. 控制回归估计误差 → 假设 \(\hat{\mu}\) 一致收敛，残差近似同分布，覆盖率偏差趋于零。 4. 控制离散化误差 → 分箱宽度趋于零，条件分布跨箱变异消失。 5. 双极限平衡 → 得出渐近条件覆盖。 - 关键跳跃点： - 从联合可交换性到得分序列可交换：这是最吃功夫的步骤。联合可交换性是关于无穷数组的性质，而得分序列是有限样本的泛函。需要证明：在增广数组（加入测试节点）上，联合可交换性仍成立，且泛函的等变性保证得分序列继承可交换性。作者用排列不变泛函的组合（composition of permutation-invariant functions）来论证：如果 \(f\) 对输入重排不变，\(g\) 对输入重排等变，则 \(g \circ f\) 的适当组合仍保持可交换性。 - 渐近条件覆盖的双极限：分箱宽度 \(h_n \to 0\) 与样本量 \(n \to \infty\) 需要同步，且每箱内节点数 \(n_k \to \infty\)。作者需要控制分箱保形预测的覆盖率偏差的上界，这涉及非参数回归的一致收敛速率与分箱内残差分布的均匀控制。 - 技术技巧点名： - 可交换数组表示定理（Aldous-Hoover）：用于建立网络数据的非参数模型基础，说明联合可交换性等价于存在潜在 i.i.d. 变量生成网络（但潜在变量不可观测，不用于推断）。 - 排列等变性：用于证明网络协变量在节点重排下同步变化，是得分序列可交换性的关键。等变性是泛函的代数性质，不涉及概率。 - 分箱保形预测：用于逼近条件覆盖。分箱将连续条件变量离散化，在每箱内做边际保形预测，是 Romano et al. (2019) 在 i.i.d. 设定下提出的方法，本文将其移植到网络设定。 - 非参数回归一致收敛：用于控制渐近条件覆盖中的残差分布偏差。作者假设 \(\hat{\mu}\) 满足一致收敛速率（如 \(|\hat{\mu} - \mu|_\infty = O_P(r_n)\)），这是 M-估计理论的标准结果。
真实例子与应用： - 模拟实验：在多种网络生成模型（如随机块模型 SBM、潜在空间模型）下，模拟网络数据，计算网络协变量（度数、谱嵌入坐标），拟合回归，构造保形预测区间。验证：边际覆盖率是否达到 \(1-\alpha\)，条件覆盖率是否随 \(n\) 增大趋近 \(1-\alpha\)。结果：边际覆盖率精确达标，条件覆盖率随 \(n\) 增大收敛，但在小样本或分箱过细时偏低（因箱内样本不足）。 - 引文网络数据集（Cora）：Cora 是一个论文引文网络，节点是论文，连边是引用关系，常规协变量是论文的词频特征，响应变量是论文的类别标签（7 类）。作者将多类响应转为二值（某类 vs 其他），用谱嵌入坐标作为网络协变量，拟合逻辑回归，构造保形预测区间。结果：加入网络协变量后，预测区间宽度比只用常规协变量时更窄（因网络信息提升了预测精度），且覆盖率仍达标。这个例子想说明：网络协变量确实提升预测效率，且本文方法在真实数据上可行。
🔎 结论是否比证明窄： - 作者在摘要与 intro 中声称"finite sample validity for a wide range of network covariates"，但定理 1 的严格证明要求网络协变量满足排列等变性（Assumption 2）。某些常见的网络泛函（如基于固定节点排序的嵌入、或依赖外部节点属性的泛函）可能不满足等变性，此时覆盖保证不成立。作者未在摘要中明确提及这一限制。 - 渐近条件覆盖（定理 2-3）要求回归函数 \(\hat{\mu}\) 一致收敛与分箱宽度的双极限，这些条件在实际中难以验证（特别是 \(\hat{\mu}\) 的一致收敛速率在网络依赖数据下可能不成立）。作者在定理陈述中列出了条件，但在讨论部分未充分强调这些条件的实际约束力。
四、开放问题（点到为止，扎根具体语句）¶
- 联合可交换性假设的失效与敏感性：本文的覆盖保证完全依赖联合可交换性（Assumption 1）。当网络存在社区结构且社区标签影响响应时，可交换性可能近似但不精确成立。要估什么：在可交换性近似成立（如分布对排列的偏差可控）时，覆盖率的偏差上界是多少？扎根点：作者在 Section 6 Discussion 中提到"exchangeability may not hold exactly in practice"，但未给出偏差的定量分析。
- 网络协变量等变性的边界：定理 1 要求协变量满足排列等变性（Assumption 2），但某些实用泛函（如基于节点度排序的嵌入、或依赖外部属性的泛函）可能不满足。要证什么：对不满足等变性的泛函，覆盖保证是否仍近似成立，或需要何种修正？扎根点：作者在 Section 3.2 提到"most common network covariates satisfy equivariance"，但未讨论不满足时的后果。
- 渐近条件覆盖中回归一致收敛的验证：定理 2-3 要求 \(\hat{\mu}\) 一致收敛于 \(\mu\)，但在网络依赖数据下，M-估计的一致收敛速率可能比 i.i.d. 情形更慢或需要更强条件。要证什么：在网络依赖（联合可交换）下，常见回归算法（如随机森林、神经网络）的一致收敛速率是多少？扎根点：作者在定理证明中假设了收敛速率 \(r_n\)，但未给出具体算法在网络数据下的速率结果。
- 分箱策略在网络协变量空间上的适用性：网络协变量（如谱嵌入坐标）的分布可能高度非均匀或具有低维结构（如集中在几个簇），分箱可能产生大量空箱或样本不足的箱。要算什么：在网络协变量空间上，如何自适应选择分箱宽度或使用其他局部化策略（如核加权保形预测），以在有限样本下逼近条件覆盖？扎根点：作者在 Section 5 使用了固定分箱，并在模拟中观察到小样本时条件覆盖率偏低，这指向分箱策略的改进空间。
Maintained by 陈星宇 · Homepage · Source on GitHub