SLoG-Net: Algorithm Unrolling for Source Localization on Graphs

Basic Information

• Paper ID: 2501.00442
• Title: SLoG-Net: Algorithm Unrolling for Source Localization on Graphs
• Authors: Chang Ye, Gonzalo Mateos (University of Rochester)
• Classification: eess.SP (Signal Processing)
• Submission Date: December 31, 2024 to arXiv
• Paper Link: https://arxiv.org/abs/2501.00442

Abstract

This paper proposes a novel model-based deep learning solution for addressing the inverse problem of network diffusion source localization. Starting from first principles of graph signal processing (GSP), the authors reformulate the problem as joint (blind) estimation of the forward diffusion filter and sparse input signals encoding source locations. Despite the bilinear nature of observations in this blind deconvolution task, by imposing invertibility constraints on the diffusion filter, the problem can be formulated as a convex optimization problem and solved using the Alternating Direction Method of Multipliers (ADMM). Subsequently, the authors unroll and truncate the novel ADMM iterations to obtain a parameterized neural network architecture for source localization on graphs (SLoG-Net), trained end-to-end using labeled data. This supervised learning approach provides advantages including interpretability, parameter efficiency, and controllable inference-time complexity.

Research Background and Motivation

Problem Definition

Network diffusion source localization is an important inverse problem aimed at identifying source node locations in a network from observed diffusion signals. Specifically:

1. Input: Observed graph signal Y ∈ R^(N×P) with known graph topology
2. Output: Sparse source signal X ∈ R^(N×P) and unknown diffusion filter coefficients h
3. Constraints: Source signals exhibit sparsity (at most S ≪ N non-zero elements per column)

Significance

This problem has broad applications across multiple domains:

• Sensor-based environmental monitoring
• Opinion formation in social networks
• Neural signal processing
• Epidemiology
• Misinformation propagation detection

Limitations of Existing Methods

1. Traditional GSP methods: Rely on matrix lifting techniques with high computational complexity on large graphs
2. Iterative solvers: Require careful tuning of step sizes and regularization parameters with slow convergence
3. Probabilistic models: Optimal only on specific graph structures (e.g., trees) or require restrictive dependency assumptions
4. Parameter tuning: Existing methods require expensive grid search for parameter selection

Core Contributions

1. Theoretical Contribution: Reformulates the blind graph filter identification problem as a convex optimization problem under invertibility constraints
2. Algorithmic Innovation: Develops a specialized ADMM algorithm to efficiently solve the convex optimization problem
3. Architecture Design: Proposes SLoG-Net by mapping ADMM iterations to trainable neural network layers through algorithm unrolling
4. Performance Enhancement: Achieves performance comparable to iterative ADMM with significantly faster inference time
5. Parameter Learning: Automatically learns step sizes and penalty parameters through end-to-end training, eliminating manual tuning

Methodology Details

Task Definition

Given graph G(V,A) and observed signal Y = HX, where:

• H = Σ(l=0 to L-1) h_l S^l is an L-th order graph filter
• S is the graph shift operator (e.g., normalized adjacency matrix)
• X is the sparse source signal matrix

The objective is to jointly estimate filter coefficients h and sparse input X.

Model Architecture

1. Convex Reformulation

Under the filter invertibility assumption (Assumption 2), the problem is transformed to:

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

where g̃ is the frequency domain response of the inverse filter.

2. ADMM Algorithm

Using variable separation technique:

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

where Z = Y^T V ⊙ V, x = vecX.

ADMM update rules:

• Filter Update: g̃k+1 = Γ^(-1)Z^T(ρ_λxk - λk) + (ρ_μc - μk)1_N
• Source Signal Update: xk+1 = S_{ρ_λ^(-1)}(Zg̃k+1 + λk/ρ_λ)
• Lagrange Multiplier Update: λk+1 = λk + ρ_λ(Zg̃k+1 - xk+1)

3. SLoG-Net Architecture

Unrolls ADMM iterations into K neural network layers, each containing three sublayers:

Filter Sublayer 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])]

Source Signal Sublayer X_k:

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

Multiplier Sublayer 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)

Technical Innovations

1. Learnable Constraints: Replaces fixed constraint 1^T g̃ = 1 with parameterized matrix M^(k) and vector m^(k)
2. Layer-wise Decoupling: Uses different parameters per layer rather than parameter sharing for enhanced expressiveness
3. Efficient Matrix Inversion: Exploits diagonal structure of Z^T Z and matrix inversion lemma for O(N^2) complexity
4. Residual Connections: ResNet-like data flow design with Z input to all layers

Experimental Setup

Datasets

1. Synthetic Data:
   • Graph types: Erdős-Rényi, Stochastic Block Model (SBM), Barabási-Albert, Random Geometric Graphs
   • Number of nodes: N = 20-100
   • Sparsity: θ = 0.15
   • Filter order: L = 5
2. Real Data:
   • Dolphin social network (N=62)
   • Zachary's karate club (N=34)
   • Subgraph of Digg 2009 dataset (N=20)

Evaluation Metrics

1. Relative Error (RE): ||X̂ - X_test||_F / ||X_test||_F
2. Support Set Accuracy (ACC): Proportion of correctly identified source locations
3. Inference Time: Forward propagation duration

Comparison Methods

1. ADMM Baseline: Iterative ADMM algorithm
2. GNN Methods: Convolutional graph neural networks
3. IVGD: Invertible validity-aware graph diffusion neural network

Implementation Details

• Network layers: K = 5
• Training set size: |T| = 200k
• Batch size: P = 400
• Optimizer: Adam
• Training epochs: 30
• Constraint parameter dimension: d = 2

Experimental Results

Main Results

1. Comparison with ADMM

• Noise Robustness: SLoG-Net outperforms ADMM across different noise levels
• Inference Speed: SLoG-Net inference time ~0.009s, ADMM requires 1.99-7.42s
• Effect of Parameter Count: SLoG-Net significantly outperforms ADMM when observed signal count P < 160

2. Performance Across Different Graph Types

3. Computational Complexity Comparison

Ablation Studies

1. Training Set Size: Performance stabilizes at |T| ≥ 160k
2. Network Layers: K=5 is optimal
3. Constraint Parameter Dimension: d=2 shows significant improvement over d=1

Real Data Experiments

On Digg 2009 dataset:

• SLoG-Net average AUC: 0.56
• IVGD baseline AUC: 0.51
• Although absolute performance is limited, SLoG-Net still outperforms comparison methods on this challenging task

Related Work

Graph Signal Processing Methods

• Traditional GSP methods use matrix lifting and convex programming
• Limitations: High computational complexity, difficult parameter tuning

Probabilistic Models

• Maximum likelihood estimation approaches
• Optimal only on specific graph structures

Deep Learning Methods

• Graph neural networks (GNNs)
• Algorithm unrolling techniques in signal processing

Conclusions and Discussion

Main Conclusions

1. SLoG-Net successfully combines model-driven GSP methods with data-driven deep learning
2. Achieves performance comparable to ADMM with 2-3 orders of magnitude faster inference
3. Automatically learns optimization parameters through end-to-end training, eliminating manual tuning
4. Demonstrates good robustness in noisy environments

Limitations

1. Scalability: Currently validated primarily on small-scale graphs (N ≤ 100)
2. Training Data Requirements: Requires large amounts of labeled data (200k samples)
3. Graph Structure Dependence: Performance closely related to spectral properties of the graph
4. Filter Invertibility: Relies on strong invertibility assumptions

Future Directions

1. Large-Scale Graphs: Develop scalable versions for large-scale networks
2. Transfer Learning: Study model generalization across different graph structures
3. Theoretical Analysis: Establish theoretical guarantees for stability and transferability
4. Application Extensions: Extend to neuroscience, seismology, epidemiology, and other domains

In-Depth Evaluation

Strengths

1. Solid Theoretical Foundation: Based on GSP theory with rigorous mathematical derivations
2. Strong Methodological Innovation: First application of ADMM unrolling to graph source localization
3. Comprehensive Experiments: Covers synthetic and real data with multiple graph types and metrics
4. Engineering Practicality: Significant speed improvements provide practical application value
5. Good Interpretability: Network architecture directly corresponds to optimization algorithm, facilitating understanding

Weaknesses

1. Scale Limitations: Experiments primarily on small-scale graphs; large-scale applicability unknown
2. Strong Assumptions: Filter invertibility assumption may not hold in practical applications
3. Incomplete Comparisons: Lacks comparison with more recent deep learning methods
4. Insufficient Theoretical Analysis: Lacks theoretical guarantees for convergence and generalization

Impact

1. Academic Value: Provides new insights for algorithm unrolling applications in graph signal processing
2. Practical Value: Has application potential in network monitoring, opinion analysis, and related fields
3. Reproducibility: Authors provide complete code implementation

Applicable Scenarios

1. Source localization tasks on small to medium-scale networks
2. Applications with high real-time requirements
3. Environments with known and relatively stable graph structures
4. Supervised learning scenarios where training data is available

References

The paper cites 46 relevant references spanning graph signal processing, optimization theory, and deep learning, providing a solid theoretical foundation for the research.

Overall Assessment: This is a high-quality academic paper that successfully combines optimization theory with deep learning to address the important problem of source localization on graphs. While there is room for improvement in scalability and theoretical analysis, its innovation and practical value make it a significant contribution to the field.