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: فك الخوارزمية لتحديد موقع المصدر على الرسوم البيانية

المعلومات الأساسية

  • معرّف الورقة: 2501.00442
  • العنوان: SLoG-Net: Algorithm Unrolling for Source Localization on Graphs
  • المؤلفون: Chang Ye, Gonzalo Mateos (جامعة روتشستر)
  • التصنيف: eess.SP (معالجة الإشارات)
  • تاريخ النشر: تم تقديمه إلى arXiv في 31 ديسمبر 2024
  • رابط الورقة: 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. صيغة إعادة البناء المحدبة

تحت افتراض قابلية عكس المرشح (الافتراض 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.009 ثانية، بينما يحتاج ADMM إلى 1.99-7.42 ثانية
  • تأثير عدد المعاملات: عندما يكون عدد الإشارات المرصودة P<160، يتفوق SLoG-Net بشكل كبير على ADMM

2. الأداء على أنواع رسوم بيانية مختلفة

نوع الرسم البيانيNMRE of X̂MRE of ĝACC
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:

  • متوسط AUC لـ SLoG-Net: 0.56
  • AUC لخط الأساس IVGD: 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 مرجعاً ذا صلة، تغطي معالجة إشارات الرسوم البيانية ونظرية التحسين والتعلم العميق وغيرها من المجالات المهمة، مما يوفر أساساً نظرياً متيناً للبحث.

التقييم الشامل: هذه ورقة بحثية عالية الجودة تجمع بنجاح بين نظرية التحسين والتعلم العميق لحل مشكلة مهمة وهي تحديد موقع المصدر على الرسوم البيانية. على الرغم من وجود مجال للتحسين في قابلية التوسع والتحليل النظري، فإن قيمتها الابتكارية والعملية تجعلها مساهمة مهمة في هذا المجال.