Source localization is the inverse problem of graph information dissemination and has broad practical applications. However, the inherent intricacy and uncertainty in information dissemination pose significant challenges, and the ill-posed nature of the source localization problem further exacerbates these challenges. Recently, deep generative models, particularly diffusion models inspired by classical non-equilibrium thermodynamics, have made significant progress. While diffusion models have proven to be powerful in solving inverse problems and producing high-quality reconstructions, applying them directly to the source localization is infeasible for two reasons. Firstly, it is impossible to calculate the posterior disseminated results on a large-scale network for iterative denoising sampling, which would incur enormous computational costs. Secondly, in the existing methods for this field, the training data itself are ill-posed (many-to-one); thus simply transferring the diffusion model would only lead to local optima. To address these challenges, we propose a two-stage optimization framework, the source localization denoising diffusion model (SL-Diff). In the coarse stage, we devise the source proximity degrees as the supervised signals to generate coarse-grained source predictions. This aims to efficiently initialize the next stage, significantly reducing its convergence time and calibrating the convergence process. Furthermore, the introduction of cascade temporal information in this training method transforms the many-to-one mapping relationship into a one-to-one relationship, perfectly addressing the ill-posed problem. In the fine stage, we design a diffusion model for the graph inverse problem that can quantify the uncertainty in the dissemination. The proposed SL-Diff yields excellent prediction results within a reasonable sampling time at extensive experiments.
翻译:源定位是图信息传播的逆问题,具有广泛的实际应用。然而,信息传播中的内在复杂性和不确定性带来了重大挑战,并且源定位问题的不适定性进一步加剧了这些挑战。近年来,深度生成模型,特别是受经典非平衡热力学启发的扩散模型,取得了显著进展。虽然扩散模型在解决逆问题和产生高质量重建方面证明了其强大,但直接将其应用于源定位是不可行的,原因有两个。首先,在大规模网络上计算迭代去噪采样的后验传播结果是不可能的,这将产生巨大的计算成本。其次,在现有的领域方法中,训练数据本身是不适定的(多对一);因此,简单地转移扩散模型只会导致局部最优。为了解决这些挑战,我们提出了一种两阶段优化框架,即源定位去噪扩散模型(SL-Diff)。在粗略阶段中,我们设计源接近度作为监督信号生成粗颗粒源预测。这旨在有效地初始化下一阶段,显著减少其收敛时间并校准收敛过程。此外,这种训练方法中引入级联时间信息将多对一映射关系转化为一对一关系,完美解决了逆问题的问题。在精细阶段中,我们设计了一个用于图逆问题的扩散模型,可以量化传播中的不确定性。所提出的SL-Diff在广泛实验中产生了出色的预测结果,并在合理的抽样时间内实现。