SLoG-Net: Algorithm Unrolling for Source Localization on Graphs

Chang Ye, Student Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE · 2025

Read SLoG-Net: Algorithm Unrolling for Source Localization on Graphs by Chang Ye, Student Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00442.txt.

Introduction

Chang Ye and Gonzalo Mateos present a paper, published in 2024, on finding the sources of a spread across a network. A hidden few nodes start a diffusion, and the task is to locate them from the trace left behind. From graph signal principles, the task splits into joint estimation of the diffusion filter and a sparse source signal.

A convexity trick turns that blind task into a solvable optimization, which the team solves with a standard split method. They then unroll a cut short form of those steps into a neural network, SLoG-Net, trained end to end on labeled cases. Tests match the slow solver scores with far faster inference and no hand tuning of step sizes.

Catalog record

CREATORChang Ye, Student Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00442

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SLoG-Net: Algorithm Unrolling for Source Localization on Graphs Thanks: Work in this paper is supported in part by the Center of Excellence in Data Science, an Empire State Development-designated Center of Excellence. Part of the results in this paper appeared at the 2022 EUSIPCO Conference [ 43 ] . (Corresponding author: Gonzalo Mateos) . Chang Ye and Gonzalo Mateos are with the Department of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627 USA (e-mail: [email protected]; [email protected]). Chang Ye, Student Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE Abstract We present a novel model-based deep learning solution for the inverse problem of localizing sources of network diffusion. Starting from first graph signal processing (GSP) principles, we show that the problem reduces to joint (blind) estimation of the forward diffusion filter and a sparse input signal that encodes the source locations. Despite the bilinear nature of the observations in said blind deconvolution task, by requiring invertibility of the diffusion filter we are able to formulate a convex optimization problem and solve it using the alternating-direction method of multipliers (ADMM). We then unroll and truncate the novel ADMM iterations to arrive at a parameterized neural network architecture for Source Localization on Graphs (SLoG-Net), that we train in an end-to-end fashion using labeled data. This supervised learning approach offers several advantages such as interpretability, parameter efficiency, and controllable complexity during inference. Our reproducible numerical experiments corroborate that SLoG-Net exhibits performance on par with the iterative ADMM baseline, but with markedly faster inference times and without needing to manually tune step-size or penalty parameters. Overall, our approach combines the best of both worlds by incorporating the inductive biases of a GSP model-based solution within a data-driven, trainable deep learning architecture for blind deconvolution of graph signals. I Introduction We study the inverse problem of localizing sources of network diffusion when the forward model is unknown, also referred to as blind graph filter identification [ 33 , 42 , 41 ] . In this problem, we observe P graph signals \{{\mathbf{y}}_{i}\}_{i=1}^{P} that we model as outputs of some diffusion graph filter, i.e., a polynomial in the graph-shift operator of a known graph [ 31 , 25 , 9 , 17 ] . The goal is to jointly identify the filter coefficients {\mathbf{h}} and the input signals \{{\mathbf{x}}_{i}\}_{i=1}^{P} that generated the network observations. We assume that the input signals are sparse, implying only a few source nodes inject a signal that spreads through the network [ 33 ] . This problem can be viewed as a form of blind deconvolution in graph domains and has applications in a variety of fields, including sensor-based environmental monitoring, opinion formation in social networks, neural signal processing, epidemiology, or disinformation campaigns. For prior related blind deconvolution approaches of (non-graph) signals, see e.g., [ 1 , 19 , 37 ] . I-A Proposed approach in context To solve this inverse problem in a supervised setting, we propose a novel data-driven machine learning model that blends graph signal processing (GSP) principles with deep learning (DL). Our algorithm unrolling [ 23 ] approach leverages the interpretability and parameter efficiency of model-based GSP methods, while also utilizing the power of DL to achieve satisfactory recovery performance and controllable complexity during inference; see also [ 6 , 24 ] for related ideas applied to graph signal denoising and [ 34 , 28 , 39 , 38 ] for network topology inference. Different from most early attempts to localizing sources on networks (e.g., [ 46 , 27 , 32 ] ), here we leverage the GSP toolbox [ 25 ] inspired by [ 26 , 33 , 44 ] . The idea in [ 33 ] is to cast the (bilinear) blind graph filter identification task as a linear inverse problem in the “lifted” rank-one, row-sparse matrix {\mathbf{x}}{\mathbf{h}}^{\top} ; see also [ 1 , 21 ] for seminal blind deconvolution work via convex programming. While the rank and sparsity minimization algorithms in [ 33 , 29 ] can successfully recover sparse inputs along with low-order graph filters (even from a single observation, i.e., with P=1 ), reliance on matrix lifting can hinder applicability to large graphs. Beyond this computational consideration, the overarching assumption of [ 33 ] is that the inputs \{{\mathbf{x}}_{i}\}_{i=1}^{P} share a common support when P>1 . Moreover, iterative solvers in [ 33 , 29 , 44 ] require carefully tuning step-sizes, as well as carrying out costly grid searches to select regularization parameters in the inverse problems. Instead, the algorithm unrolling-based DL model of this paper learns these parameters (and others) in a end-to-end fashion. Other works adopt probabilistic models of network diffusion, and resulting maximum-likelihood source estimators can only be optimal for particular (e.g., tree) graphs [ 27 ] , or rendered scalable under restrictive dependency assumptions [ 8 ] . Relative to [ 27 , 26 , 16 ] , the proposed framework can accommodate signals defined on general undirected graphs and relies on a convex estimator of the sparse sources of diffusion, which here we favorably exploit to design a DL architecture as well as to generate training examples. I-B Contributions and paper outline In this context, our starting point is the blind graph filter identification formulation in [ 42 ] . After reviewing the necessary GSP background, in Section II we reexamine and state the problem in the novel supervised learning setting dealt with here. The model-based approach in [ 42 ] imposes a mild requirement on invertibility of the graph filter, which facilitates a convex reformulation for the multi-signal case with arbitrary supports (Section III ); see also [ 37 ] for a time-domain precursor that inspired our line of work in graph settings. While [ 42 ] focused on fundamental exact recovery and noise stability guarantees (see also [ 35 , 41 ] for robustness to graph perturbations), here we shift gears to algorithmic issues and first develop a novel solver based on the alternating-directions method of multipliers (ADMM) [ 4 , Ch. 3.4.4] . The ADMM algorithm in Section III-B is of independent interest as an effective model-based solution to the problem of source localization on graphs (we reiterate that algorithms were only tangentially treated in e.g., [ 33 , 44 , 42 ] ). However, the ADMM’s main upshot here is in leveraging its primal and dual variable updates as the blueprint for (sub-)layers of a trainable parametric DL model with prescribed depth. This way we seek to overcome the burden of manually tuning step-size and penalty parameters, plus the time as well as computational overhead that comes with running hundreds or thousands of iterations to attain convergence each time a new problem instance is presented. To this end, in Section IV we unroll and truncate the ADMM iterations [ 23 , 40 , 24 ] , to arrive at a parameterized nonlinear DL architecture for S ource L ocalization o n G raphs (SLoG-Net), that we train in an end-to-end fashion using labeled data. This way we leverage inductive biases of a GSP model-based solution in a data-driven trainable deep network, which is interpretable, parameter efficient, and offers controllable complexity during inference [ 23 ] . To increase the model’s expressive power we

Read the complete text