2025-11-16T19:07:13.213602

SLoG-Net: Algorithm Unrolling for Source Localization on Graphs

Ye, Mateos

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.

academic

SLoG-Net: Algorithm Unrolling for Source Localization on Graphs

基本信息

论文ID: 2501.00442
标题: SLoG-Net: Algorithm Unrolling for Source Localization on Graphs
作者: Chang Ye, Gonzalo Mateos (University of Rochester)
分类: eess.SP (Signal Processing)
发表时间: 2024年12月31日提交至arXiv
论文链接: https://arxiv.org/abs/2501.00442

摘要

本文提出了一种新颖的基于模型的深度学习解决方案，用于解决网络扩散源定位的逆问题。从图信号处理(GSP)的第一性原理出发，作者将问题简化为前向扩散滤波器和编码源位置的稀疏输入信号的联合(盲)估计。尽管该盲去卷积任务中观测值具有双线性性质，但通过要求扩散滤波器的可逆性，能够将其表述为凸优化问题并使用交替方向乘子法(ADMM)求解。随后，作者展开并截断新颖的ADMM迭代，得到用于图上源定位(SLoG-Net)的参数化神经网络架构，并使用标记数据进行端到端训练。这种监督学习方法提供了可解释性、参数效率和推理时可控复杂度等优势。

研究背景与动机

问题定义

网络扩散源定位是一个重要的逆问题，旨在从观测到的扩散信号中识别网络中的源节点位置。具体来说：

输入：观测到的图信号 Y ∈ R^(N×P)，已知图拓扑结构
输出：稀疏源信号 X ∈ R^(N×P) 和未知扩散滤波器系数 h
约束：源信号具有稀疏性(每列最多S≪N个非零元素)

重要性

该问题在多个领域具有广泛应用：

基于传感器的环境监测
社交网络中的舆论形成
神经信号处理
流行病学
虚假信息传播检测

现有方法局限性

传统GSP方法：依赖矩阵提升技术，在大图上计算复杂度高
迭代求解器：需要仔细调整步长和正则化参数，收敛缓慢
概率模型：仅在特定图结构(如树)上最优，或需要限制性依赖假设
参数调优：现有方法需要昂贵的网格搜索来选择参数

核心贡献

理论贡献：将盲图滤波器识别问题重新表述为在可逆滤波器约束下的凸优化问题
算法创新：开发了专门的ADMM算法来高效求解该凸优化问题
架构设计：提出SLoG-Net，通过算法展开将ADMM迭代映射为可训练的神经网络层
性能提升：实现与迭代ADMM相当的性能，但推理时间显著更快
参数学习：通过端到端训练自动学习步长和惩罚参数，无需手动调优

方法详解

任务定义

给定图G(V,A)和观测信号Y = HX，其中：

H = Σ(l=0 to L-1) h_l S^l 是L阶图滤波器
S是图移位算子(如归一化邻接矩阵)
X是稀疏源信号矩阵

目标是联合估计滤波器系数h和稀疏输入X。

模型架构

1. 凸重构公式

在滤波器可逆性假设下(Assumption 2)，将问题转换为：

min ||X||_{1,1} = ||(Y^T V ⊙ V)g̃||_1
s.t. 1^T_N g̃ = 1

其中g̃是逆滤波器的频域响应。

2. ADMM算法

使用变量分离技术：

min ||x||_1
s.t. Zg̃ - x = 0, 1^T_N g̃ = c

其中Z = Y^T V ⊙ V，x = vecX。

ADMM更新规则：

滤波器更新：g̃k+1 = Γ^(-1)Z^T(ρ_λxk - λk) + (ρ_μc - μk)1_N
源信号更新：xk+1 = S_{ρ_λ^(-1)}(Zg̃k+1 + λk/ρ_λ)
拉格朗日乘子更新：λk+1 = λk + ρ_λ(Zg̃k+1 - xk+1)

3. SLoG-Net架构

将ADMM迭代展开为K层神经网络，每层包含三个子层：

滤波器子层G_k：

g̃[k+1] = (Z^T Z + ρ_2^(k) M^(k)M^(k)T)^(-1)[Z^T(x[k] - ρ_1^(k)λ[k]) + M^(k)(ρ_2^(k)m^(k) - ρ_1^(k)μ[k])]

源信号子层X_k：

x[k+1] = S_{τ^(k)}(α_1^(k)Zg̃[k+1] + α_2^(k)λ[k])

乘子子层M_k：

λ[k+1] = β_1^(k)λ[k] + β_2^(k)Zg̃[k+1] + β_3^(k)x[k+1]
μ[k+1] = γ^(k)μ[k] + M^(k)T g̃[k+1] + m^(k)

技术创新点

可学习约束：用参数化矩阵M^(k)和向量m^(k)替代固定约束1^T g̃ = 1
层级解耦：每层使用不同参数而非参数共享，提高表达能力
高效矩阵求逆：利用Z^T Z的对角结构和矩阵求逆引理实现O(N^2)复杂度
残差连接：类似ResNet的数据流设计，Z输入到所有层

实验设置

数据集

合成数据：
- 图类型：Erdős-Rényi、随机块模型(SBM)、Barabási-Albert、随机几何图
- 节点数：N = 20-100
- 稀疏度：θ = 0.15
- 滤波器阶数：L = 5
真实数据：
- 海豚社交网络(N=62)
- Zachary空手道俱乐部(N=34)
- Digg 2009数据集的子图(N=20)