Research map / Graph learning / Graph algorithms and clustering
Multiple-Source Localization from a Single-Snapshot Observation Using Graph Bayesian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BOSouL, a simulation-based Bayesian optimization method with a graph spectral Gaussian kernel and graph stratified sampling for multi-source localization from a single snapshot, applicable to any diffusion model.
Problem
Multi-source localization from a single-snapshot observation on networks, where limited information, source interactions, and dependence on the diffusion model make heuristic/greedy methods ineffective.
Approach
Treats candidate source sets as inputs to a Gaussian process surrogate (with a graph spectral Gaussian kernel built from graph Fourier representations) optimized by expected improvement, where each candidate's likelihood is estimated by diffusion simulations under any chosen model, and samples are drawn via graph stratified sampling over clusters.
Key results
- Under SIR on all five graphs, BOSouL achieves the lowest localization error, with improvements up to 29% over baselines on SW, CiteSeer and PubMed.
- Under SI, BOSouL outperforms the other four methods on four of five datasets; on CiteSeer NetSleuth leads by only 0.4.
- On a 1,000-node SW graph BOSouL takes 396.69 seconds, about six times slower than the slowest baseline LISN, but its runtime scales near-linearly and the gap narrows with graph size.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GSG instead of RBF while retaining random sampling (ablation) | BOSI · SIR, SW | localization error: 7.4$\pm$0.6 -> 6.6$\pm$1.5; -10.8% | Helped |
| Use GSG instead of RBF while retaining random sampling (ablation) | BOSI · SIR, ER | localization error: 6.0$\pm$1.2 -> 5.8$\pm$0.5; -3.3% | Helped |
| Use GSG instead of RBF while retaining random sampling (ablation) | BOSI · SIR, Cora | localization error: 8.6$\pm$2.3 -> 6.6$\pm$1.1; -23.2% | Helped |
| Use GSG instead of RBF while retaining random sampling (ablation) | BOSI · SIR, CiteSeer | localization error: 7.6$\pm$2.5 -> 6.2$\pm$1.8; -18.4% | Helped |
| Use GSG instead of RBF while retaining random sampling (ablation) | BOSI · SIR, PubMed | localization error: 7.6$\pm$2.3 -> 7.6$\pm$2.2; 0% | No clear effect |
| Use GSS instead of random sampling while retaining GSG (ablation) | BOSI · SIR, SW | localization error: 6.6$\pm$1.5 -> 6.4$\pm$0.9; -2.7% | Helped |
| Use GSS instead of random sampling while retaining GSG (ablation) | BOSI · SIR, ER | localization error: 5.8$\pm$0.5 -> 5.6$\pm$0.9; -3.3% | Helped |
| Use GSS instead of random sampling while retaining GSG (ablation) | BOSI · SIR, Cora | localization error: 6.6$\pm$1.1 -> 6.4$\pm$1.7; -2.4% | Helped |
| Use GSS instead of random sampling while retaining GSG (ablation) | BOSI · SIR, CiteSeer | localization error: 6.2$\pm$1.8 -> 5.4$\pm$2.7; -10.5% | Helped |
| Use GSS instead of random sampling while retaining GSG (ablation) | BOSI · SIR, PubMed | localization error: 7.6$\pm$2.2 -> 7.2$\pm$2.6; -5.2% | Helped |
| Use BOSI instead of the baselines | BOSI · SIR, SW; ER; Cora; CiteSeer; PubMed | localization error: up to 29% | Helped |
| Use BOSI instead of the baselines | BOSI · SI, four datasets; CiteSeer | localization error: 0.4 | Mixed |
Surprising findings
- Ablation shows the GSG kernel gives no improvement on PubMed (0% change), and GSS gives only modest gains on some datasets.
- BOSouL runs about six times slower than the slowest baseline at N=1,000, and on a 5,000-node graph it is slightly slower than LISN in the reported runs.
Limitations
- Simulation-based approach is substantially slower than heuristic baselines at small graph sizes.
- Only a limited set of diffusion models (SI, SIR, SIS, IC) and a fixed infection rate of 0.1 are evaluated.
- Candidate pool restricted to top-a nodes by degree, which may miss true sources outside it.
Experimental setup
Datasets: Cora CiteSeer PubMed Watts-Strogatz synthetic graphs Erdős–Rényi synthetic graphs
Benchmarks: Cora CiteSeer PubMed SW ER
Metrics: source localization distance (min summed shortest distance) runtime
Baselines: Jordan centrality NetSleuth LISN LPSI
Builds on: Bayesian optimization LPSI NetSleuth NDLib
Closest papers by meaning
- Stochastic Localization via Iterative Posterior Sampling (ICML 2024 · similarity 0.86)
- RDPI: A Refine Diffusion Probability Generation Method for Spatiotemporal Data Imputation (AAAI 2025 · similarity 0.84)
- Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization (ICML 2025 · similarity 0.84)
- BO4Mob: Bayesian Optimization Benchmarks for High-Dimensional Urban Mobility Problem (NeurIPS 2025 · similarity 0.83)
- Sampling from Binary Quadratic Distributions via Stochastic Localization (ICML 2025 · similarity 0.83)
- Tempered Guided Diffusion (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.