跳转至

Conformal Network Link Prediction with False Discovery Rate Control Under Unstructured Missingness

作者: Wenqin Du, Wanteng Ma, Dong Xia, Yuan Zhang, Wen Zhou
来源: Journal of Computational and Graphical Statistics
主题: 数理统计 / 假设检验
相关性: 6/10
机构绿灯: University of Southern California(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:在部分观测的网络中,如何同时预测多条缺失的边(link prediction),并保证这些预测中假阳性比例(FDR)受控。这是一个将"预测"与"多重假设检验"结合的问题——不仅要给出哪些边可能存在的排序,还要给出一个可证明的、在有限样本下成立的错误率上界。该子方向的成熟度处于快速发展期:方法上已从纯算法(如矩阵补全、图神经网络)转向统计推断框架(共形预测、e值),但如何在网络这种强依赖结构下同时处理"未知缺失机制"与"复杂边依赖"仍是开放挑战。

发展脉络

  • 奠基工作:共形预测框架由 Vovk et al. (2005) 建立,其核心思想是利用数据交换性构造分布自由的预测集。Lei et al. (2018) 与 Tibshirani et al. (2019) 将其推广到回归与协变量偏移场景,奠定了"共形p值"的理论基础。本文的p值构造(式13)直接继承自 Jin and Candès (2022) 的"selection by prediction"框架,后者首次将共形p值用于筛选问题并给出FDR控制。
  • 主要进展:将共形推断引入矩阵/网络数据是近年关键一步。Gui et al. (2023) 提出 conformalized matrix completion (cmc),在随机缺失(missing-at-random)下给出逐点预测区间,但其FDR控制依赖对缺失概率(odds ratio)的准确估计。Shao and Zhang (2023) 则处理任意缺失模式,但聚焦于预测区间覆盖而非多重检验。Marandon (2024) 首次将共形p值用于链接预测的FDR控制,但限于无权重网络且要求缺失率仅取两个值(均匀缺失)。
  • 当前frontier:处理"非均匀、未知、结构化"缺失模式下的多重检验,同时保持有限样本保证。这需要放弃全局交换性,转而利用局部结构(如行内交换性)构造有效p值。
  • 本文位置:本文声称填补的缺口是——在加权图模型(weighted graphon)框架下,允许完全未知且非均匀的缺失概率,通过"多重分割"策略在局部恢复交换性,再通过e值聚合实现全局FDR控制。其位置是 cmc(需估计缺失率)与 Marandon(需均匀缺失)之间的推广。

子线索聚类

  1. 共形预测与分布自由推断(Vovk et al., 2005; Lei et al., 2018; Tibshirani et al., 2019):核心是交换性假设,目标是无模型假设的有限样本保证。本文的p值构造属于此线。
  2. 矩阵补全与网络预测(Candès et al., 2011; Koltchinskii et al., 2011; Davenport et al., 2014; Gao et al., 2015; Xu, 2018):将网络视为随机矩阵,利用低秩或图模型结构估计缺失条目。本文的图模型假设(式2)继承此线,但关注点从点估计转向推断。
  3. 多重检验与FDR控制(Benjamini-Hochberg, 1995; Ferreira & Zwinderman, 2006; Wang & Ramdas, 2022):BH程序与e值框架。本文的局部BH与全局e-BH聚合属于此线。
  4. 缺失数据分析(Rubin, 1976; Little & Rubin, 2019; Mohan & Pearl, 2021):本文的Assumption 1.1(缺失独立于网络)是MCAR的推广,但允许缺失概率随位置变化。

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

  1. 如何在非交换性数据上做共形推断? 网络边之间存在复杂依赖,全局交换性不成立。已知解法是寻找局部交换性子结构(本文的行内分割),但代价是样本量减少、功效下降。
  2. 如何在未知缺失机制下做有效推断? 若缺失概率未知且非均匀,观测到的边集不再代表原始分布。cmc 通过估计缺失率解决,但估计误差会破坏FDR控制;本文通过构造不依赖缺失率的局部交换性来规避。
  3. 如何聚合多个局部检验结果? 局部检验的p值可能因分割方式不同而相关,直接合并会破坏FDR控制。e值框架(Wang & Ramdas, 2022)允许任意依赖下的聚合,但e值的构造需要仔细设计。

⚠️ 作者的 framing

作者将缺口框定为:"现有方法(cmc, Marandon)要么需要均匀缺失率,要么需要估计缺失概率,而本文在完全未知、非均匀缺失下实现FDR控制"。这是典型的"推广性缺口"叙事。被淡化的竞争路线包括:(1) 基于图神经网络的方法(如 Zhao et al., 2024),它们不做统计保证但预测精度可能更高;(2) 基于模型的方法(如随机块模型),它们假设更强的结构但可能获得更紧的界。作者在引言中明确说"to date, valid FDR control for multiple link prediction under general network settings remains an open challenge"——这是其framing的核心断言。

张力

未见明显对立引用。但存在一个微妙张力:Shao and Zhang (2023) 声称处理"任意缺失模式"(arbitrary missing pattern),而本文的Assumption 1.1(缺失独立于网络)实际上比"任意"更弱。作者通过强调"非均匀但独立"来区分——即缺失概率可以随位置变化,但不能依赖网络值。这是一个值得研究者注意的边界。


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

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

符号: - \(A \in \mathbb{R}^{n \times n}\):网络的邻接矩阵,\(A_{i,j}\) 表示从节点 \(i\) 到节点 \(j\) 的边权重(可为连续值)。这是随机变量,也是我们想要推断的对象。 - \(M \in \{0,1\}^{n \times n}\):缺失指示矩阵,\(M_{i,j}=1\) 表示 \(A_{i,j}\) 缺失。这是随机变量,但独立于 \(A\)(Assumption 1.1)。 - \(M^c = \mathbf{1}\mathbf{1}^\top - M\):观测指示矩阵。 - \(D_{\text{test}} = \{(i,j): M_{i,j}=1\}\):测试集(缺失边的集合)。 - \(c_{i,j}\):用户设定的阈值,用于定义原假设 \(H_{i,j}: A_{i,j} \le c_{i,j}\)。这是已知常数。 - \(\xi_i \sim \text{Uniform}[0,1]\):节点的潜在变量(图模型中的"身份")。这是潜在变量,不可观测。 - \(f(\cdot, \cdot)\):图模型函数(graphon),决定边概率/权重。这是未知的,但本文方法不估计它。 - \(\hat{A}_{i,j}\):对 \(A_{i,j}\) 的预测值(由任意算法给出)。 - \(S(\hat{A}_{i,j}; z) := z - \hat{A}_{i,j}\):非一致性得分(nonconformity score),衡量预测与阈值 \(z\) 的偏差。 - \(p_{i_0,j}\):共形p值,定义见式(13)。 - \(\alpha_{BH}, \alpha_{eBH}\):局部BH与全局e-BH的名义FDR水平。

模型: - 数据生成:\(A_{i,j} \sim f(\xi_i, \xi_j)\),其中 \(\{\xi_i\}\) i.i.d. Uniform[0,1]。这称为加权图模型(weighted graphon model),是网络数据的非参数模型。 - 缺失机制:\(M\) 独立于 \(A\),但 \(M_{i,j}\) 的分布可以随 \((i,j)\) 变化(非均匀缺失)。 - 可观测数据:\(A \circ M^c\)(观测到的边)和 \(M\)(缺失模式)。注意:\(\{\xi_i\}\) 和 \(f\) 都不可观测。

关键区分: - 可观测:\(A \circ M^c\)(部分邻接矩阵)、\(M\)(缺失指示)、\(c_{i,j}\)(阈值)。 - 不可观测(潜在):完整的 \(A\)、\(\{\xi_i\}\)、\(f\)。 - 要推断的:对每个 \((i,j) \in D_{\text{test}}\),判断 \(H_{i,j}: A_{i,j} \le c_{i,j}\) 是否成立,并控制错误拒绝的比例(FDR)。

第二步:最小内核

问题:假设你有一个 \(n=3\) 的三人社交网络,只知道部分朋友关系。你想预测"谁和谁是朋友",但不想错得太离谱——希望预测出的朋友关系中,假的比例不超过某个数(比如10%)。

最小设定: - 节点 \(\{1,2,3\}\),邻接矩阵 \(A\) 是 \(3\times3\) 对称矩阵,\(A_{i,j} \in \{0,1\}\)(朋友=1,非朋友=0)。 - 假设观测到 \(A_{1,2}=1\)(1和2是朋友),\(A_{1,3}=0\)(1和3不是朋友),\(A_{2,3}\) 缺失(不知道2和3是否朋友)。 - 目标是:判断 \(H_{2,3}: A_{2,3} \le 0\)(即2和3不是朋友)是否成立,并控制FDR。

核心困难:你只有一条观测(\(A_{1,2}=1\)),如何判断 \(A_{2,3}\)?如果直接预测 \(A_{2,3}=1\),你没有任何依据——因为 \(A_{1,2}\) 和 \(A_{2,3}\) 可能相关(如果1和2是朋友,2和3可能也是朋友),也可能不相关。

本文的关键洞察:虽然 \(A_{2,3}\) 不可观测,但如果你能构造一个"预测器" \(\hat{A}_{2,3}\)(比如用 \(A_{1,2}\) 和 \(A_{1,3}\) 的某种函数),并且这个预测器在可交换的数据上表现一致,那么你就可以用校准集(calibration set)来估计预测误差的分布,从而构造有效的p值。

最小例子: - 假设你决定用"共同朋友数"来预测:\(\hat{A}_{2,3} = A_{1,2} \cdot A_{1,3}\)。这里 \(\hat{A}_{2,3}=0\)(因为 \(A_{1,3}=0\))。 - 但你没有校准集来评估这个预测的可靠性。本文的方法是通过多重分割:将观测到的边分成训练集和校准集,用训练集拟合预测器,用校准集计算非一致性得分,然后构造p值。

为什么这很难:网络数据中,\(A_{2,3}\) 和 \(A_{1,2}\) 是相关的(通过共享节点2),所以你不能把每条边当作独立样本。本文通过行内分割(row-wise splitting)来规避:固定节点 \(i_0\),该行的所有边 \(A_{i_0,j}\) 在给定 \(\xi_{i_0}\) 后是条件独立的(因为 \(\xi_j\) 是i.i.d.)。这恢复了局部交换性,使得共形p值有效。

数学上要证明的核心命题:对于任意固定的行 \(i_0\),构造的p值 \(p_{i_0,j}\) 满足 \(\mathbb{P}(p_{i_0,j} \le \alpha \mid \text{null}) \le \alpha\)(即p值在零假设下随机控制),且这些p值在行内是条件独立的。然后通过e值聚合,将行内控制提升为全局FDR控制。


三、这篇论文做了什么

三句话

  1. 研究问题:在部分观测的加权/无权网络中,如何同时预测多条缺失边,并保证FDR受控,且不要求缺失率已知或均匀。
  2. 核心方法:提出共形链接预测(CLP),通过行内多重分割恢复局部交换性,构造有效共形p值;再通过e值聚合与去随机化,实现全局FDR控制。
  3. 主要结论:在加权图模型假设下,CLP对任意缺失模式(只要独立于网络)提供有限样本FDR控制,且在模拟和真实数据上优于现有方法(cmc, dss)。

关键设定与假设

  • 假设1(Assumption 1.1):缺失模式 \(M\) 独立于网络 \(A\)。这是本文的核心假设,比MCAR弱(允许非均匀缺失率),但比MAR强(不允许缺失依赖于潜在变量 \(\xi_i\))。相比 Gui et al. (2023) 的随机缺失假设,本文允许 \(q_{i,j}\) 随 \((i,j)\) 变化;相比 Marandon (2024) 的均匀缺失假设,本文去掉了这一限制。
  • 模型(式2):\(A_{i,j} \sim f(\xi_i, \xi_j)\),\(\{\xi_i\}\) i.i.d. Uniform[0,1]。这是加权图模型,涵盖了伯努利图、高斯权重图等。注意:本文方法不要求 \(f\) 已知,也不要求估计 \(f\)。
  • 技术假设:预测器 \(\hat{A}\) 的构造需满足式(5)的交换性条件——即对校准集和测试集的排列不变。这通过"预测器只依赖训练集,且训练集与校准集/测试集可交换"来实现。
  • 无平局假设:非一致性得分无平局(或采用随机破平局),这是共形p值有效性的标准条件。

主要结果

  • 定理2.2(Oracle FDR控制):若预测器满足交换性(式5),则局部BH程序在每行内控制FDR ≤ α_BH。这是共形p值标准理论的直接应用,但关键在于是行内控制,而非全局。
  • 定理2.4(经验FDR控制):用式(10)-(12)构造的经验预测器(基于多重分割)仍满足行内FDR控制。这需要证明经验非一致性得分的交换性——通过精心构造 \(\Omega_{j_0}\)(完全观测的行集合)来实现。
  • 定理2.5(全局FDR控制):通过e值聚合(式14-15),将各行局部检验结果合并,实现全局FDR ≤ α_eBH。e值的关键性质是:在任意依赖结构下,\(\mathbb{E}[\sum e_{i,j} / |D_{\text{test}}|] \le 1\) 对零假设成立,从而保证e-BH的FDR控制。

证明路线与技术技巧

  1. 整体路线:三步走——(1) 行内分割恢复交换性;(2) 构造共形p值并局部BH;(3) e值聚合实现全局控制。
  2. 关键跳跃点:
  3. 如何恢复交换性:直接对所有观测边做共形不成立(因为边依赖)。本文的关键是行内分割:固定行 \(i_0\),该行的边 \(\{A_{i_0,j}\}\) 在给定 \(\xi_{i_0}\) 后条件独立(因为 \(\xi_j\) i.i.d.)。这允许在行内构造有效的共形p值。
  4. 如何处理未知缺失率:不直接估计 \(q_{i,j}\),而是通过"完全观测的行"(\(\Omega_{j_0}\))来构造预测器。\(\Omega_{j_0}\) 中的行对所有相关列都无缺失,因此其数据分布与完整数据一致(条件于 \(\xi\)),从而保持交换性。
  5. 如何聚合局部结果:局部BH的拒绝集 \(R_{i_0,k_0}^{BH}\) 不能直接合并(因为不同行的p值可能相关)。本文利用 e-BH 的性质:将每个局部拒绝事件转化为e值(式14),e值在零假设下期望≤1,且对任意依赖鲁棒。
  6. 技术技巧点名:
  7. 多重分割:将测试集分成 \(k\) 个子集,每个子集用不同的校准集,提高数据利用率。
  8. e值构造:利用BH程序的leave-one-out分析(Ferreira & Zwinderman, 2006),证明式(14)是有效e值。
  9. 去随机化:重复多次随机分割,取平均e值,提高稳定性(类似 bagging)。

真实例子与应用

  • 数据:国际双边贸易流数据(Helpman et al., 2008),158个国家,1989年。\(A_{i,j}\) 为对数贸易额,缺失表示无贸易记录。
  • 应用方式:随机掩盖10%的边(2496条),设定 \(c_{i,j}=0.2\)(即检验贸易额是否>0.2),比较CLP与cmc的FDR和功效。
  • 结果:CLP在所有名义水平(α=0.1, 0.2, 0.3)下控制FDR,而cmc在α=0.2和0.3时FDR超标(图6左)。CLP的功效也高于cmc(图6右)。
  • 想说明什么:在真实数据中,缺失模式往往非均匀(贸易网络中小国数据更可能缺失),cmc因需要估计缺失率而失效,CLP通过不依赖缺失率的设计保持有效性。

🔎 结论是否比证明窄

  • 窄的地方:定理2.2-2.5的证明依赖于行内交换性,这要求图模型(式2)中 \(\xi_i\) 是i.i.d.的。对于更一般的图模型(如度修正的随机块模型),行内交换性可能不成立。作者在结论中未明确讨论这一限制。
  • 泛化声称:作者声称方法适用于"加权、无权、无向、有向、二部网络",但正文只详细处理了有向加权网络,无向/二部网络的证明放在附录D,且依赖对称性扩展。有向网络的处理(\(A_{i,j}\) 和 \(A_{j,i}\) 独立)在无向网络中不成立,附录D的证明是否覆盖了这种依赖需要仔细核查。
  • 经验预测器的交换性:定理2.4的证明依赖于 \(\Omega_{j_0}\) 的构造,但 \(\Omega_{j_0}\) 本身依赖于 \(M\)(缺失模式)。虽然 \(M\) 独立于 \(A\),但 \(\Omega_{j_0}\) 的随机性是否会影响条件交换性,证明中处理得比较简略。

四、开放问题

  1. 最优e值膨胀因子:作者在式(14)中使用了 \(|I_{i_0}^{test}(k_0)|/\alpha_{BH}\) 的膨胀因子,并提到"更优的因子可能提升功效"(结论部分)。要确认这是否为真缺口,可查阅 Wang & Ramdas (2022) 关于e-BH最优性的讨论——若存在更紧的e值构造,则本文的膨胀因子是次优的。
  2. 块状缺失模式:作者在结论中提到"block-wise aggregation under missingness"是未来工作。本文的多重分割假设缺失模式是随机的,但实际网络(如社交网络)中缺失常呈块状(某社区整体缺失)。要确认这是否为真缺口,可查阅 Athey et al. (2021) 关于块状缺失下矩阵补全的工作——若已有方法处理块状缺失,则本文的缺口叙事需重新评估。
  3. 功效的理论刻画:本文只证明了FDR控制,未给出功效(power)的下界。对于给定的信号强度 \(\delta\)(如 \(c_{i,j} = A_{i,j} - \delta\)),CLP的功效如何随 \(n\)、缺失率、图模型复杂度变化?这需要minimax分析,可参考 Gao et al. (2015) 的图模型估计下界。
  4. 去随机化的理论保证:作者采用多次随机分割取平均e值(去随机化),但未证明这一步骤是否保持FDR控制。Ren & Barber (2024) 对去随机化knockoffs有理论分析,但本文的e值构造不同,需要独立的证明。

提示:要确认上述是否真缺口,建议查阅近5年(2020-2025)关于"共形p值 + 网络数据"的文献,特别是 Sesia 组(如 Marandon, 2024; Bashari et al., 2024)和 Candès 组(如 Jin & Candès, 2022)的后续工作。若多篇论文都指向同一问题,则为共识性缺口;若互相矛盾,则为机会。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论