This paper introduces a novel conformal prediction (CP) framework for multi-source detection on networks. The task is to estimate the set of source nodes that initiated information or infection propagation, given snapshot observations of node infection status on a graph. The core idea is to provide statistically valid recall guarantees for source set detection, independent of the underlying diffusion process or data distribution, by leveraging principled non-conformity score functions and a calibration set. The main empirical claim is that the proposed method achieves rigorous coverage with competitive accuracy and outperforms existing baselines in both reliability and scalability, yielding smaller prediction sets while maintaining statistical guarantees.
Problem
The paper addresses several bottlenecks in existing multi-source detection methods:
Lack of Statistical Guarantees: Many existing methods, including data-driven machine learning techniques like Graph Neural Networks (GNNs), lack statistical performance guarantees for source set detection.
Dependence on Specific Diffusion Models/Assumptions: Early centrality-based methods offer provable guarantees only for specific graph structures (e.g., trees) and require heuristic adaptations for general graphs. Data-driven methods often require knowledge about propagation models and parameter ranges for simulating training data.
Computational Infeasibility: The multi-source detection problem is challenging because different source sets can produce identical observed infection patterns, and exhaustively enumerating all possible source sets is computationally infeasible.
Limited Applicability to Multi-Source Scenarios: Existing CP methods for set estimation often focus on finding a collection of subsets containing the ground truth label subset, which is impractical for network multi-source detection. Traditional CP methods for single-source detection cannot be directly extended to multi-source scenarios due to computational infeasibility of hypothesis testing for all possible node subsets.
Key Contributions
The paper proposes non-conformity score designs for set estimation problems, specifically targeting a nominal recall rate with statistical guarantee, which yield efficient (i.e., small) prediction sets.
It applies the proposed score to the multi-source detection problem, enabling it to work under an arbitrary number of sources and propagation models, unlike existing methods that often deal only with single-source detection.
The paper numerically validates the advantage of its proposed method on the multi-source detection problem under real-world network propagation.
Method
The method proposes a conformal prediction (CP) framework for multi-source detection, aiming to construct a prediction set C of nodes such that its recall rate for identifying the true source nodes exceeds 1 – β with probability at least 1 – α, where α, β ∈ [0, 1] are user-specified nominal levels.
Method Flow:
Pre-trained Predictor: A pre-trained neural network, specifically a Graph Neural Network (GNN), is used as a point estimator. This GNN, denoted as f(X) = (π(v))v∈V ∈ RN, takes snapshots of node infection status X as input and outputs estimated probabilities π(v) for each node v being a source. A larger π(v) indicates a higher likelihood of v ∈ Y.
Non-conformity Scores: The method defines non-conformity scores s: X × 2V → R, which quantify how atypical a given input-output pair is. Higher values indicate less conformity. The scores are designed to be monotone: if γ(X, U₁) ⊆ γ(X, U₂), then s(X, γ(X, U₁)) ≤ s(X, γ(X, U₂)). Two examples of non-conformity scores are provided:
spre (precision-based): s_pre(X,U) = 1 / |γ(X,U)| * Σ_{z∈γ(X,U)} π(z)
srec (recall-based): s_rec(X,U) = Σ_{z∈γ(X,U)} π(z) / Σ_{z∈V} π(z)
These scores are meaningful as they represent non-conformity in terms of precision and recall rate, respectively, under an oracle case.
Calibration Set: A calibration dataset {(Xi, Yi) : i ∈ [n]} is used to empirically estimate the distribution of prediction errors.
Prediction Set Construction (for β = 0): For the special case where β = 0 (requiring all source nodes to be included), the prediction set Ĉ(Xn+1; α) is defined as:
Ĉ(Xn+1; α) := {v ∈ V : s(Xn+1, {v}) ≤ ĝα}
where ĝα := Q({s(Xi, Yi)}i=1, (1 − α)(1 + 1/n)) is the empirical (1-α) quantile of the calibration scores.
Generalization for Recall Rate Guarantee (β ∈ [0, 1]): To handle arbitrary recall levels, a two-step strategy is employed:
Shrinking Map: A map v : X × 2V → 2V is defined such that v(X, U) ⊆ U and |v(X, U)| ≥ (1 – β)|U|. This map shrinks the ground truth set Y by retaining only a (1 – β) fraction of its elements, specifically those with the largest predicted probabilities.
Prediction Set Construction: The prediction set Ĉ(Xn+1; α, β) is then constructed by applying the prediction set construction from step 4, but using the shrunken sets v(Xi, Yi) for calibration:
Ĉ(Xn+1; α, β) := {v ∈ V : s(Xn+1, {v}) ≤ ĝα}
where ĝα := Q({s(Xi, v(Xi, Yi))}i=1, (1 − α)(1 + 1/n)).
This construction ensures that the prediction set satisfies the recall rate guarantee.
Technical Details
Architecture: The backbone for the conformal prediction framework is the SD-STGCN model (Sha, Al Hasan, and Mohler 2021). Its output is modified to N × 2 channels.
Loss/Objective: The loss function of the SD-STGCN model is adapted for binary node classification in the multi-source detection setting. Not stated in the paper.
Optimization: Not stated in the paper.
Data Handling:
Diffusion Path Dataset: Access to a diffusion path dataset is assumed, which can be derived from real-world diffusion examples or generated through simulations when propagation models and parameter ranges are known.
Multiple Snapshots: The method assumes multiple snapshots of node status are available as inputs, compatible with the SD-STGCN model.
Calibration Set: A calibration set of size n = 7600 is used for all experiments.
Training Data: The pre-trained model is trained on a separate set of 20,000 samples.
Implementation Details: The method is implemented using two non-conformity score designs: setCP-pre and setCP-rec. Experiments are repeated over 50 random splits of the calibration and test sets.
Results
Datasets: SIR and SI propagation processes are simulated over three social networks:
highSchool (N = 774)
bkFratB (N = 58)
sfhh (N = 403)
These networks are obtained by aggregating contact records within groups of people.
Metrics:
Inclusion Rates (empirical recall rate)
Prediction Set Size
Average time (in seconds)
Baselines:
ADiT (Dawkins, Li, and Xu 2021)
ArbiTree (Cauchois, Gupta, and Duchi 2021)
Numeric Results:
Inclusion Rates: All methods (setCP-rec, setCP-pre, ArbiTree, ADiT) achieve the desired recall rate (1 – β) with probability at least (1 – α) across various nominal levels and propagation scenarios. For example, in Table 1, for highSchool network with α = 0.05, β = 0.3, setCP-rec has an inclusion rate of 1.000 ± 0.000, and setCP-pre has 0.951 ± 0.012.
Prediction Set Size:
setCP-rec and setCP-pre consistently achieve the best or second-best efficiency in terms of prediction set size, producing substantially smaller prediction sets than ArbiTree.
For highSchool network (N = 774), SIR model, α = 0.05, β = 0.3: setCP-rec prediction set size is 774.000 ± 0.000, setCP-pre is 21.333 ± 0.486, ArbiTree is 763.480 ± 3.888.
Under SI model (σinf = 0.25), |Y| = 1, α = 0.1: setCP-rec prediction set size is 23.315 ± 0.626, setCP-pre is 25.691 ± 0.324, ADiT is 24.432 ± 0.698, ArbiTree is 624.442 ± 14.545.
Prediction set sizes under the SIR model are always smaller than those under the SI model.
Prediction set size increases with larger values of Ro.
Runtime/Training Cost:
Average time (in seconds) for computing on 400 test samples under the SI model (σinf = 0.25), |Y| = 1, with α = 0.05, 0.07, 0.10, 0.15, 0.20:
setCP-rec: 1.392 ± 0.008
setCP-pre: 1.559 ± 0.008
ADiT: 792.170 ± 23.936
ArbiTree: 79.637 ± 1.208
setCP-rec and setCP-pre are substantially faster than both ADiT and ArbiTree.
The computational complexity for evaluating the prediction set in (15) is O(N log N).
Weaknesses / Limitations
Dependence on Calibration Data: The approach relies on having access to a calibration set of diffusion data. In some applications, this data may need to be synthetically generated based on prior knowledge of the propagation model and parameter ranges, which might require external expert input.
Mismatch in Prior Knowledge: Future work is needed to study how mismatch in prior knowledge affects the performance of the method and how to adaptively update predictions using new data.
Large Prediction Sets for Small β: When the nominal recall rate is high (i.e., β is small), setCP-rec can produce large, uninformative prediction sets. This limitation stems from its score definition in (8), which does not penalize the size of the prediction set. In the extreme case where β = 0, if the GNN assigns zero probability to any true source node, srec will result in the entire node set V being selected.
Evidence
Method evidence: "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." (section: Abstract)
Result evidence: "Across most nominal level settings, setCP-rec and setCP-pre consistently achieve the best or second-best efficiency in terms of predict set size, producing substantially smaller prediction sets than ArbiTree." (section: 5.1 Conformalized Detection under Different Nominal Levels)
Limitation evidence: "One limitation of our approach is its dependence on having access to a calibration set of diffusion data. In some applications, this can be synthetically generated based on prior knowledge of the propagation model and parameter ranges, which may require external expert input." (section: 6 Conclusion and Limitations)
Additional Figures
Figure 1: Illustration of γ(X, U). Suppose the nodes are indexed such that π
Figure 2: Illustration of ν(X, U). Suppose the nodes are indexed such that π