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: グラフ上の源定位のためのアルゴリズムアンローリング

基本情報

論文ID: 2501.00442
タイトル: SLoG-Net: Algorithm Unrolling for Source Localization on Graphs
著者: Chang Ye, Gonzalo Mateos (ロチェスター大学)
分類: eess.SP (信号処理)
提出日: 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アルゴリズムを開発
アーキテクチャ設計: ADMM反復をトレーニング可能なニューラルネットワーク層にマッピングするSLoG-Netを提案
性能向上: 反復ADMMと同等の性能を実現しながら、推論時間を大幅に短縮
パラメータ学習: エンドツーエンド学習により、ステップサイズと罰則パラメータを自動学習し、手動調整を不要にする

方法の詳細

タスク定義

グラフG(V,A)と観測信号Y = HXが与えられたとき、以下が成立する:

H = Σ(l=0 to L-1) h_l S^l はL次グラフフィルタ
Sはグラフシフト演算子(例:正規化隣接行列)
Xは疎源信号行列

目標はフィルタ係数hと疎入力Xを結合推定することである。

モデルアーキテクチャ

1. 凸再構成公式

フィルタ可逆性仮定(仮定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層ニューラルネットワークに展開し、各層は3つのサブ層を含む:

フィルタサブ層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)

技術的革新点

学習可能な制約: 固定制約1^T g̃ = 1をパラメータ化行列M^(k)とベクトルm^(k)で置換
層別デカップリング: 各層が異なるパラメータを使用し、パラメータ共有ではなく表現力を向上
効率的な行列反転: 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)