Learning Probabilistic Sensor Placement for Detecting Diffusive Processes on Graphs
Alexandre Reiffers-Masson, Yézékaël Hayel, Lucas Drumetz · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
We study a probabilistic sensor placement problem for detecting diffusive processes on graphs under limited sensing resources. A diffusion process is modeled as a Markovian random walk propagating over a network toward a critical target node, while sensors placed at nodes detect the process. The objective is to allocate sensing resources to minimize the probability that the diffusion reaches the target without being detected. We formulate this problem as a non-convex optimization over the hitting probabilities of an absorbing Markov chain and show that its first-order optimality conditions admit a distributed message-passing representation. Building on this structure, we design a projected gradient ascent algorithm in which the gradient is approximated via local fixed-point iterations, and we show that the resulting method converges to stationary solutions of the constrained sensor placement problem. We then introduce a random-basis representation of the message-passing iterations that enables learning-to-optimize without differentiating through the underlying fixed-point equations. We derive an efficient stochastic gradient algorithm based on Monte-Carlo path sampling and demonstrate on synthetic graphs that the proposed approach converges rapidly to high-quality sensing strategies at scale.