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 (University of Rochester)
  • वर्गीकरण: eess.SP (सिग्नल प्रोसेसिंग)
  • प्रकाशन समय: 31 दिसंबर 2024 को arXiv पर प्रस्तुत
  • पेपर लिंक: https://arxiv.org/abs/2501.00442

सारांश

यह पेपर नेटवर्क प्रसार स्रोत स्थानीयकरण की व्युत्क्रम समस्या को हल करने के लिए एक नवीन मॉडल-आधारित गहन शिक्षण समाधान प्रस्तावित करता है। ग्राफ़ सिग्नल प्रोसेसिंग (GSP) के प्रथम सिद्धांतों से शुरू करते हुए, लेखक समस्या को अग्रगामी प्रसार फ़िल्टर और स्रोत स्थिति को एन्कोड करने वाले विरल इनपुट सिग्नल के संयुक्त (अंधे) अनुमान में सरल बनाते हैं। यद्यपि इस अंधे विकनवल्यूशन कार्य में प्रेक्षणों में द्विरेखीय प्रकृति है, प्रसार फ़िल्टर की प्रतिवर्तनीयता की आवश्यकता के माध्यम से, इसे एक उत्तल अनुकूलन समस्या के रूप में तैयार किया जा सकता है और वैकल्पिक दिशा गुणक विधि (ADMM) का उपयोग करके हल किया जा सकता है। इसके बाद, लेखक नवीन ADMM पुनरावृत्तियों को प्रकट और काटते हैं, ग्राफ़ पर स्रोत स्थानीयकरण (SLoG-Net) के लिए एक पैरामीटरयुक्त तंत्रिका नेटवर्क आर्किटेक्चर प्राप्त करते हैं, और लेबल किए गए डेटा का उपयोग करके अंत-से-अंत प्रशिक्षण करते हैं। यह पर्यवेक्षित शिक्षण विधि व्याख्यात्मकता, पैरामीटर दक्षता और अनुमान समय नियंत्रणीय जटिलता जैसे लाभ प्रदान करती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

नेटवर्क प्रसार स्रोत स्थानीयकरण एक महत्वपूर्ण व्युत्क्रम समस्या है जिसका उद्देश्य प्रेक्षित प्रसार सिग्नल से नेटवर्क में स्रोत नोड स्थिति की पहचान करना है। विशेष रूप से:

  1. इनपुट: प्रेक्षित ग्राफ़ सिग्नल Y ∈ R^(N×P), ज्ञात ग्राफ़ टोपोलॉजी संरचना
  2. आउटपुट: विरल स्रोत सिग्नल X ∈ R^(N×P) और अज्ञात प्रसार फ़िल्टर गुणांक h
  3. बाधाएं: स्रोत सिग्नल विरलता रखता है (प्रत्येक स्तंभ में अधिकतम S≪N गैर-शून्य तत्व)

महत्व

यह समस्या कई क्षेत्रों में व्यापक अनुप्रयोग रखती है:

  • सेंसर-आधारित पर्यावरणीय निगरानी
  • सामाजिक नेटवर्क में विचार निर्माण
  • तंत्रिका संकेत प्रोसेसिंग
  • महामारी विज्ञान
  • गलत सूचना प्रसार का पता लगाना

मौजूदा विधियों की सीमाएं

  1. पारंपरिक GSP विधियां: मैट्रिक्स लिफ्टिंग तकनीकों पर निर्भर, बड़े ग्राफ़ पर उच्च कम्प्यूटेशनल जटिलता
  2. पुनरावृत्तिमूलक समाधानकर्ता: सावधानीपूर्वक स्टेप आकार और नियमितकरण पैरामीटर समायोजन की आवश्यकता, धीमा अभिसरण
  3. संभाव्य मॉडल: केवल विशिष्ट ग्राफ़ संरचनाओं (जैसे पेड़) पर इष्टतम, या प्रतिबंधात्मक निर्भरता धारणाओं की आवश्यकता
  4. पैरामीटर ट्यूनिंग: मौजूदा विधियों को पैरामीटर चयन के लिए महंगी ग्रिड खोज की आवश्यकता है

मुख्य योगदान

  1. सैद्धांतिक योगदान: अंधी ग्राफ़ फ़िल्टर पहचान समस्या को प्रतिवर्तनीय फ़िल्टर बाधाओं के तहत उत्तल अनुकूलन समस्या के रूप में पुनः तैयार करना
  2. एल्गोरिदम नवाचार: इस उत्तल अनुकूलन समस्या को कुशलतापूर्वक हल करने के लिए एक विशेष ADMM एल्गोरिदम विकसित करना
  3. आर्किटेक्चर डिज़ाइन: SLoG-Net प्रस्तावित करना, ADMM पुनरावृत्तियों को प्रशिक्षणीय तंत्रिका नेटवर्क परतों में मैप करने के लिए एल्गोरिदम अनरोलिंग के माध्यम से
  4. प्रदर्शन सुधार: पुनरावृत्तिमूलक ADMM के बराबर प्रदर्शन प्राप्त करना, लेकिन अनुमान समय में महत्वपूर्ण रूप से तेजी
  5. पैरामीटर सीखना: अंत-से-अंत प्रशिक्षण के माध्यम से स्वचालित रूप से स्टेप आकार और दंड पैरामीटर सीखना, मैनुअल ट्यूनिंग की आवश्यकता नहीं

विधि विवरण

कार्य परिभाषा

ग्राफ़ 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)

तकनीकी नवाचार बिंदु

  1. सीखने योग्य बाधाएं: निश्चित बाधा 1^T g̃ = 1 के स्थान पर पैरामीटरयुक्त मैट्रिक्स M^(k) और वेक्टर m^(k) का उपयोग
  2. परत-स्तरीय विघटन: पैरामीटर साझाकरण के बजाय प्रत्येक परत में विभिन्न पैरामीटर का उपयोग, अभिव्यक्ति क्षमता में वृद्धि
  3. कुशल मैट्रिक्स व्युत्क्रम: Z^T Z की विकर्ण संरचना और मैट्रिक्स व्युत्क्रम लेम्मा का उपयोग करके O(N^2) जटिलता प्राप्त करना
  4. अवशिष्ट कनेक्शन: ResNet जैसा डेटा प्रवाह डिज़ाइन, Z इनपुट सभी परतों तक

प्रायोगिक सेटअप

डेटासेट

  1. सिंथेटिक डेटा:
    • ग्राफ़ प्रकार: Erdős-Rényi, यादृच्छिक ब्लॉक मॉडल (SBM), Barabási-Albert, यादृच्छिक ज्यामितीय ग्राफ़
    • नोड संख्या: N = 20-100
    • विरलता: θ = 0.15
    • फ़िल्टर क्रम: L = 5
  2. वास्तविक डेटा:
    • डॉल्फिन सामाजिक नेटवर्क (N=62)
    • Zachary कराटे क्लब (N=34)
    • Digg 2009 डेटासेट का उप-ग्राफ़ (N=20)

मूल्यांकन मेट्रिक्स

  1. सापेक्ष त्रुटि (RE): ||X̂ - X_test||_F / ||X_test||_F
  2. समर्थन सेट सटीकता (ACC): स्रोत स्थिति की सही पहचान का अनुपात
  3. अनुमान समय: आगे प्रसार समय

तुलना विधियां

  1. ADMM आधारभूत: पुनरावृत्तिमूलक ADMM एल्गोरिदम
  2. GNN विधि: कनवल्यूशनल ग्राफ़ तंत्रिका नेटवर्क
  3. IVGD: प्रतिवर्तनीय प्रभावी-जागरूकता ग्राफ़ प्रसार तंत्रिका नेटवर्क

कार्यान्वयन विवरण

  • नेटवर्क परतें: K = 5
  • प्रशिक्षण सेट आकार: |T| = 200k
  • बैच आकार: P = 400
  • अनुकूलक: Adam
  • प्रशिक्षण युग: 30
  • बाधा पैरामीटर आयाम: d = 2

प्रायोगिक परिणाम

मुख्य परिणाम

1. ADMM के साथ तुलना

  • शोर मजबूती: SLoG-Net विभिन्न शोर स्तरों पर ADMM से बेहतर है
  • अनुमान गति: SLoG-Net अनुमान समय लगभग 0.009s है, ADMM को 1.99-7.42s की आवश्यकता है
  • पैरामीटर संख्या प्रभाव: जब प्रेक्षित सिग्नल संख्या P<160 हो, तो SLoG-Net ADMM से महत्वपूर्ण रूप से बेहतर है

2. विभिन्न ग्राफ़ प्रकारों पर प्रदर्शन

ग्राफ़ प्रकारNX̂ की MREĝ की MREACC
ER200.1490.1640.953
SBM200.2190.2150.914
RG200.3830.3770.869
BA200.5790.5370.772
karate340.4540.4520.958
dolphins620.7190.5780.841

3. कम्प्यूटेशनल जटिलता तुलना

NSLoG-NetADMM
200.95×10^-2s2.04s
401.09×10^-2s5.70s
601.27×10^-2s9.41s
801.42×10^-2s12.29s
1001.64×10^-2s14.62s

विलोपन प्रयोग

  1. प्रशिक्षण सेट आकार: |T|≥160k पर प्रदर्शन स्थिर हो जाता है
  2. नेटवर्क परतें: K=5 इष्टतम विकल्प है
  3. बाधा पैरामीटर आयाम: d=2 की तुलना में d=1 में महत्वपूर्ण सुधार है

वास्तविक डेटा प्रयोग

Digg 2009 डेटासेट पर:

  • SLoG-Net औसत AUC: 0.56
  • IVGD आधारभूत AUC: 0.51
  • यद्यपि पूर्ण प्रदर्शन सीमित है, SLoG-Net इस कठिन कार्य पर तुलना विधियों से बेहतर है

संबंधित कार्य

ग्राफ़ सिग्नल प्रोसेसिंग विधियां

  • पारंपरिक GSP विधियां मैट्रिक्स लिफ्टिंग और उत्तल प्रोग्रामिंग का उपयोग करती हैं
  • सीमाएं: उच्च कम्प्यूटेशनल जटिलता, पैरामीटर ट्यूनिंग कठिन

संभाव्य मॉडल

  • अधिकतम संभावना अनुमान विधियां
  • केवल विशिष्ट ग्राफ़ संरचनाओं पर इष्टतम

गहन शिक्षण विधियां

  • ग्राफ़ तंत्रिका नेटवर्क (GNN)
  • सिग्नल प्रोसेसिंग में एल्गोरिदम अनरोलिंग तकनीकों का अनुप्रयोग

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. SLoG-Net मॉडल-संचालित GSP विधि को डेटा-संचालित गहन शिक्षण के साथ सफलतापूर्वक जोड़ता है
  2. ADMM के बराबर प्रदर्शन प्राप्त करता है, लेकिन अनुमान गति में 2-3 परिमाण तेजी
  3. अंत-से-अंत प्रशिक्षण के माध्यम से स्वचालित रूप से अनुकूलन पैरामीटर सीखता है, मैनुअल ट्यूनिंग की आवश्यकता नहीं
  4. शोर वाले वातावरण में अच्छी मजबूती प्रदर्शित करता है

सीमाएं

  1. मापनीयता: वर्तमान में मुख्य रूप से छोटे-स्तरीय ग्राफ़ (N≤100) पर सत्यापित
  2. प्रशिक्षण डेटा आवश्यकता: बड़ी मात्रा में लेबल किए गए डेटा की आवश्यकता (200k नमूने)
  3. ग्राफ़ संरचना निर्भरता: प्रदर्शन ग्राफ़ की वर्णक्रमीय विशेषताओं से घनिष्ठ रूप से संबंधित
  4. फ़िल्टर प्रतिवर्तनीयता: मजबूत प्रतिवर्तनीयता धारणा पर निर्भर

भविष्य की दिशाएं

  1. बड़े-स्तरीय ग्राफ़: बड़े नेटवर्क के लिए मापनीय संस्करण विकसित करना
  2. स्थानांतरण शिक्षा: विभिन्न ग्राफ़ संरचनाओं के बीच मॉडल सामान्यीकरण का अध्ययन
  3. सैद्धांतिक विश्लेषण: स्थिरता और स्थानांतरणीयता के सैद्धांतिक गारंटी स्थापित करना
  4. अनुप्रयोग विस्तार: तंत्रिका विज्ञान, भूकंप विज्ञान, महामारी विज्ञान आदि क्षेत्रों में विस्तार करना

गहन मूल्यांकन

शक्तियां

  1. ठोस सैद्धांतिक आधार: GSP सिद्धांत पर आधारित, गणितीय व्युत्पत्ति कठोर
  2. विधि नवाचार शक्तिशाली: ग्राफ़ स्रोत स्थानीयकरण समस्या पर ADMM अनरोलिंग का पहला अनुप्रयोग
  3. व्यापक प्रयोग: सिंथेटिक और वास्तविक डेटा, कई ग्राफ़ प्रकार और मूल्यांकन मेट्रिक्स शामिल
  4. इंजीनियरिंग व्यावहारिकता: महत्वपूर्ण गति सुधार इसे व्यावहारिक अनुप्रयोग मूल्य प्रदान करता है
  5. अच्छी व्याख्यात्मकता: नेटवर्क आर्किटेक्चर अनुकूलन एल्गोरिदम के साथ सीधे मेल खाता है, समझने में आसान

कमियां

  1. स्केल सीमा: प्रयोग मुख्य रूप से छोटे-स्तरीय ग्राफ़ पर किए गए, बड़े-स्तरीय प्रयोज्यता अज्ञात
  2. मजबूत धारणाएं: फ़िल्टर प्रतिवर्तनीयता धारणा वास्तविक अनुप्रयोगों में संतुष्ट नहीं हो सकती
  3. अपूर्ण तुलना: अधिक नई गहन शिक्षण विधियों के साथ तुलना की कमी
  4. अपर्याप्त सैद्धांतिक विश्लेषण: अभिसरण और सामान्यीकरण क्षमता के सैद्धांतिक गारंटी की कमी

प्रभाव

  1. शैक्षणिक मूल्य: ग्राफ़ सिग्नल प्रोसेसिंग में एल्गोरिदम अनरोलिंग के अनुप्रयोग के लिए नई सोच प्रदान करता है
  2. व्यावहारिक मूल्य: नेटवर्क निगरानी, विचार विश्लेषण आदि क्षेत्रों में अनुप्रयोग संभावना है
  3. पुनरुत्पादनीयता: लेखक पूर्ण कोड कार्यान्वयन प्रदान करते हैं

लागू परिदृश्य

  1. छोटे से मध्यम-स्तरीय नेटवर्क पर स्रोत स्थानीयकरण कार्य
  2. वास्तविक समय आवश्यकता उच्च अनुप्रयोग परिदृश्य
  3. ग्राफ़ संरचना ज्ञात और अपेक्षाकृत स्थिर वातावरण
  4. प्रशिक्षण डेटा प्राप्त पर्यवेक्षित शिक्षण परिदृश्य

संदर्भ

पेपर ने 46 संबंधित संदर्भों का हवाला दिया है, जो ग्राफ़ सिग्नल प्रोसेसिंग, अनुकूलन सिद्धांत, गहन शिक्षण आदि कई क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करते हैं, अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करते हैं।

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला शैक्षणिक पेपर है जो अनुकूलन सिद्धांत और गहन शिक्षण को सफलतापूर्वक जोड़ता है, ग्राफ़ पर स्रोत स्थानीयकरण की महत्वपूर्ण समस्या को हल करता है। यद्यपि स्केलिंग और सैद्धांतिक विश्लेषण के पहलुओं में सुधार की गुंजाइश है, इसकी नवाचार शक्ति और व्यावहारिक मूल्य इसे इस क्षेत्र का एक महत्वपूर्ण योगदान बनाते हैं।