Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems
Graph diffusion problems such as the propagation of rumors, computer viruses,
or smart grid failures are ubiquitous and societal. Hence it is usually crucial
to identify diffusion sources according to the current graph diffusion
observations. Despite its tremendous necessity and significance in practice,
source localization, as the inverse problem of graph diffusion, is extremely
challenging as it is ill-posed: different sources may lead to the same graph
diffusion patterns. Different from most traditional source localization
methods, this paper focuses on a probabilistic manner to account for the
uncertainty of different candidate sources. Such endeavors require overcoming
challenges including 1) the uncertainty in graph diffusion source localization
is hard to be quantified; 2) the complex patterns of the graph diffusion
sources are difficult to be probabilistically characterized; 3) the
generalization under any underlying diffusion patterns is hard to be imposed.
To solve the above challenges, this paper presents a generic framework: Source
Localization Variational AutoEncoder (SL-VAE) for locating the diffusion
sources under arbitrary diffusion patterns. Particularly, we propose a
probabilistic model that leverages the forward diffusion estimation model along
with deep generative models to approximate the diffusion source distribution
for quantifying the uncertainty. SL-VAE further utilizes prior knowledge of the
source-observation pairs to characterize the complex patterns of diffusion
sources by a learned generative prior. Lastly, a unified objective that
integrates the forward diffusion estimation model is derived to enforce the
model to generalize under arbitrary diffusion patterns. Extensive experiments
are conducted on 7 real-world datasets to demonstrate the superiority of SL-VAE
in reconstructing the diffusion sources by excelling other methods on average
20% in AUC score.