Conformal Prediction for Multi-Source Detection on a Network

• URL: http://arxiv.org/abs/2511.08867v1
• Date: Thu, 13 Nov 2025 01:13:05 GMT
• Title: Conformal Prediction for Multi-Source Detection on a Network
• Authors: Xingchao Jian, Purui Zhang, Lan Tian, Feng Ji, Wenfei Liang, Wee Peng Tay, Bihan Wen, Felix Krahmer,
• Abstract summary: We study the multi-source detection problem.<n>Given snapshot observations of node infection status on a graph, estimate the set of source nodes that initiated the propagation.<n>We propose a novel conformal prediction framework that provides statistically valid recall guarantees for source set detection.
• Score: 59.17729745907474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 framework that provides statistically valid recall guarantees for source set detection, independent of the underlying diffusion process or data distribution. Our approach introduces principled score functions to quantify the alignment between predicted probabilities and true sources, and leverages a calibration set to construct prediction sets with user-specified recall and coverage levels. The method is applicable to both single- and multi-source scenarios, supports general network diffusion dynamics, and is computationally efficient for large graphs. Empirical results demonstrate that our method achieves rigorous coverage with competitive accuracy, outperforming existing baselines in both reliability and scalability.The code is available online.

Related papers

• Out-of-Distribution Detection on Graphs: A Survey [58.47395497985277]
  Graph out-of-distribution (GOOD) detection focuses on identifying graph data that deviates from the distribution seen during training.<n>We categorize existing methods into four types: enhancement-based, reconstruction-based, information propagation-based, and classification-based approaches.<n>We discuss practical applications and theoretical foundations, highlighting the unique challenges posed by graph data.
  arXiv  Detail & Related papers  (2025-02-12T04:07:12Z)
• Source-Free Domain-Invariant Performance Prediction [68.39031800809553]
  We propose a source-free approach centred on uncertainty-based estimation, using a generative model for calibration in the absence of source data. Our experiments on benchmark object recognition datasets reveal that existing source-based methods fall short with limited source sample availability. Our approach significantly outperforms the current state-of-the-art source-free and source-based methods, affirming its effectiveness in domain-invariant performance estimation.
  arXiv  Detail & Related papers  (2024-08-05T03:18:58Z)
• Tractable Function-Space Variational Inference in Bayesian Neural Networks [72.97620734290139]
  A popular approach for estimating the predictive uncertainty of neural networks is to define a prior distribution over the network parameters. We propose a scalable function-space variational inference method that allows incorporating prior information. We show that the proposed method leads to state-of-the-art uncertainty estimation and predictive performance on a range of prediction tasks.
  arXiv  Detail & Related papers  (2023-12-28T18:33:26Z)
• Window-Based Distribution Shift Detection for Deep Neural Networks [21.73028341299301]
  We study the case of monitoring the healthy operation of a deep neural network (DNN) receiving a stream of data. Using selective prediction principles, we propose a distribution deviation detection method for DNNs. Our novel detection method performs on-par or better than the state-of-the-art, while consuming substantially lower time.
  arXiv  Detail & Related papers  (2022-10-19T21:27:25Z)
• Diffusion Source Identification on Networks with Statistical Confidence [12.805268849262246]
  We introduce a statistical framework for the study of diffusion source identification and develop a confidence set inference approach inspired by hypothesis testing. Our method efficiently produces a small subset of nodes, which provably covers the source node with any pre-specified confidence level. This is the first diffusion source identification method with a practically useful theoretical guarantee on general networks.
  arXiv  Detail & Related papers  (2021-06-09T04:21:03Z)
• Improving Uncertainty Calibration via Prior Augmented Data [56.88185136509654]
  Neural networks have proven successful at learning from complex data distributions by acting as universal function approximators. They are often overconfident in their predictions, which leads to inaccurate and miscalibrated probabilistic predictions. We propose a solution by seeking out regions of feature space where the model is unjustifiably overconfident, and conditionally raising the entropy of those predictions towards that of the prior distribution of the labels.
  arXiv  Detail & Related papers  (2021-02-22T07:02:37Z)
• Unlabelled Data Improves Bayesian Uncertainty Calibration under Covariate Shift [100.52588638477862]
  We develop an approximate Bayesian inference scheme based on posterior regularisation. We demonstrate the utility of our method in the context of transferring prognostic models of prostate cancer across globally diverse populations.
  arXiv  Detail & Related papers  (2020-06-26T13:50:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.