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 (University of Rochester)
  • শ্রেণীবিভাগ: eess.SP (সিগন্যাল প্রসেসিং)
  • প্রকাশনার সময়: 2024 সালের 31 ডিসেম্বর 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. উত্তল পুনর্নির্মাণ সূত্র

ফিল্টার বিপরীতযোগ্যতা অনুমানের অধীনে (অনুমান 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 epochs
  • সীমাবদ্ধতা প্যারামিটার মাত্রা: 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টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যা গ্রাফ সিগন্যাল প্রসেসিং, অপ্টিমাইজেশন তত্ত্ব, গভীর শিক্ষা ইত্যাদি একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের একাডেমিক পেপার যা অপ্টিমাইজেশন তত্ত্ব এবং গভীর শিক্ষাকে সফলভাবে একত্রিত করে, গ্রাফে উৎস স্থানীয়করণের এই গুরুত্বপূর্ণ সমস্যা সমাধান করে। যদিও স্কেলিং এবং তাত্ত্বিক বিশ্লেষণের ক্ষেত্রে উন্নতির অবকাশ রয়েছে, তবে এর উদ্ভাবনী পদ্ধতি এবং ব্যবহারিক মূল্য এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অবদান করে তোলে।