Conformal Prediction for Multi-Source Detection on a Network
Xingchao Jian, Purui Zhang, Lan Tian, Feng Ji, Wenfei Liang, Wee Peng Tay, Bihan Wen, Felix Krahmer
检测信息的来源或感染在网络中传播是一个基本挑战,在错误信息跟踪,流行病学和其他中的应用。 我们研究多源检测问题:给定图上节点感染状态的快照观察,估计启动传播的源节点集。 现有方法要么缺乏统计保障,要么仅限于特定的扩散模型和假设。 我们提出了一种新的构象预测框架,为源集检测提供统计上有效的召回保证,独立于底层扩散过程或数据分布。 我们的方法引入了原则性评分函数来量化预测概率和真实来源之间的对齐,并利用校准集构建具有用户指定的召回和覆盖水平的预测集。 该方法适用于单源和多源场景,支持一般网络扩散动力学,并且对大图形具有计算效率。 经验结果表明,我们的方法以具有竞争力的准确性实现了严格的覆盖,在可靠性和可扩展性方面优于现有的基线。
Detecting the origin of information or infection spread in networks is a fundamental challenge with applications in misinformation tracking, epidemiology, and beyond. We study the multi-source detection problem: given snapshot observations of node infection status on a graph, estimate the set of source nodes that initiated the propagation. Existing methods either lack statistical guarantees or are limited to specific diffusion models and assumptions. We propose a novel conformal prediction frame...