SVD-Based UGRM-GFT on Directed Product Graphs

तकनीकी सारांश: निर्देशित उत्पाद ग्राफों पर SVD-आधारित UGRM-GFT

समस्या विवरण
निर्देशित ग्राफों (Directed Graphs) पर पारंपरिक ग्राफ सिग्नल प्रोसेसिंग (GSP) मुख्य रूप से निश्चित प्रतिनिधित्व मैट्रिसेस (Representations) पर निर्भर करता है, जैसे कि लैपलेसियन (Laplacian) या एडजेसेंसी (Adjacency) मैट्रिक्स। ये कठोर संरचनाएं एक मॉडल की जटिल और परिवर्तनशील ग्राफ टोपोलॉजी, विशेष रूप से निर्देशित संदर्भों में जहाँ किनारों की दिशात्मकता विषम संबंधों (जैसे सूचना प्रवाह या कारण निर्भरता) को दर्शाती है, के अनुकूल होने की क्षमता को सीमित करती है। इसके अलावा, मौजूदा ग्राफ फूरियर ट्रांसफॉर्म (GFT) विधियां अक्सर संख्यात्मक अस्थिरता (जैसे जॉर्डन अपघटन) या उच्च कम्प्यूटेशनल जटिलता से ग्रस्त होती हैं। इसके अतिरिक्त, उत्पाद ग्राफों पर स्पैटियोटेम्पोरल (Spatiotemporal) सिग्नल्स को जब एकल निर्देशित ग्राफों तक सीमित किया जाता है, तो वे आयामों के बीच सहसंबंध गुणों को पकड़ने में विफल रहते हैं। जबकि हालिया SVD-आधारित दृष्टिकोणों ने स्थिरता संबंधी समस्याओं को संबोधित किया है, वे आमतौर पर स्थिर ऑपरेटरों से बंधे रहते हैं जिनमें ग्राफ डेटा में संरचनात्मक परिवर्तनों को समायोजित करने की लचीलापन का अभाव होता है।

कार्यप्रणाली
इन सीमाओं को दूर करने के लिए, लेखक सिंगुलर वैल्यू डिकंपोजिशन (SVD) और यूनिफाइड ग्राफ रिप्रेजेंटेशन मैट्रिक्स (UGRM) पर आधारित एक जनरलाइज्ड ग्राफ फूरियर ट्रांसफॉर्म (UGRM-GFT) प्रस्तावित करते हैं।

1. यूनिफाइड ग्राफ रिप्रेजेंटेशन मैट्रिक्स (UGRM): यह विधि एक पैरामीटराइज्ड मैट्रिक्स $P_{\alpha,k} = \alpha D + (2k - 1)(\alpha - 1)A$ का उपयोग करती है, जहाँ $D$ इन-डिग्री मैट्रिक्स है, $A$ एडजेसेंसी मैट्रिक्स है, और $\alpha, k \in [0, 1]$ ट्यून करने योग्य पैरामीटर हैं। यह फॉर्मूलेशन मैट्रिक्स को क्लासिकल रिप्रेजेंटेशन (लैपलेसियन, एडजेसेंसी, डिग्री, या साइनलेस लैपलेसियन) में अनुकूल रूप से बदलने की अनुमति देता है।
2. SVD-आधारित ट्रांसफॉर्म: लेखक eigen-decomposition के बजाय UGRM पर SVD लागू करते हैं। यह बाएं और दाएं सिंगुलर वेक्टर्स ($U_{\alpha,k}$ और $V_{\alpha,k}$) और सिंगुलर वैल्यूज ($\Sigma_{\alpha,k}$) प्रदान करता है। ट्रांसफॉर्म को संख्यात्मक स्थिरता और पूर्ण पुनर्निर्माण सुनिश्चित करने के लिए दोनों प्रकार के वेक्टर्स का उपयोग करके परिभाषित किया गया है।
3. स्पेक्ट्रल ऑर्डरिंग (Spectral Ordering): पेपर एक पैरामीटर-निर्भर स्पेक्ट्रल ऑर्डरिंग स्थापित करता है। यदि पैरामीटर $\beta = (2k-1)(\alpha-1)$ ऋणात्मक है, तो ऑपरेटर एक लैपलेसियन (डिफरेंस-लाइक) की तरह व्यवहार करता है, और सिंगुलर वैल्यूज गैर-घटते क्रम (non-decreasingly) में व्यवस्थित होती हैं (छोटी वैल्यूज = कम आवृत्ति/स्मूथनेस)। यदि $\beta \geq 0$ है, तो ऑपरेटर एडजेसेंसी-जैसा (प्रोपैगेशन-ओरिएंटेड) होता है, और सिंगुलर वैल्यूज गैर-बढ़ते क्रम (non-increasingly) में व्यवस्थित होती हैं (बड़ी वैल्यूज = उच्च ऊर्जा)।
4. निर्देशित कार्टेशियन उत्पाद ग्राफों के लिए दो वेरिएंट:
   • UGRM-GFT-I: यह उत्पाद ग्राफ के संयुक्त UGRM ($P_{\alpha,k}^{\boxtimes}$) पर सीधे SVD करता है। यह ग्लोबली कपल्ड सिग्नल्स के लिए उपयुक्त है लेकिन इसकी कम्प्यूटेशनल जटिलता $O(N^3)$ है जहाँ $N = N_1 N_2$।
   • UGRM-GFT-II: यह फैक्टर ग्राफ्स ($P_{\alpha,k}^1$ और $P_{\alpha,k}^2$) के UGRMs पर अलग-अलग SVD लागू करता है और उन्हें क्रोनकर प्रोडक्ट (Kronecker products) के माध्यम से पुनर्संयोजित करता है। यह दृष्टिकोण स्पेक्ट्रल एक्सप्रेसिवनेस को बनाए रखते हुए कम्प्यूटेशनल जटिलता को $O(N_1^3 N_2^3)$ से घटाकर $O(N_1^3 + N_2^3)$ कर देता है।

प्रमुख योगदान

• फ्रेमवर्क विकास: एक SVD-आधारित UGRM-GFT का प्रस्ताव जो सामान्य निर्देशित ग्राफों के अनुकूल एक लचीले, पैरामीटराइज्ड फ्रेमवर्क में पारंपरिक ग्राफ मैट्रिसेस को एकीकृत करता है।
• एल्गोरिदमिक दक्षता: UGRM-GFT-II का परिचय, जो स्पेक्ट्रल प्रदर्शन से समझौता किए बिना निर्देशित कार्टेशियन उत्पाद ग्राफों के लिए कम्प्यूटेशनल जटिलता को महत्वपूर्ण रूप से कम करता है।
• सैद्धांतिक विश्लेषण: प्रस्तावित विधि के लिए एप्रोक्सिमेशन एरर बाउंड्स की स्थापना। लेखक प्रस्तावित विधि के स्पेक्ट्रल व्यवहार को $\alpha$ और $k$ के सापेक्ष अभिलक्षणित करते हैं, यह सिद्ध करते हुए कि विधि सिग्नल की अंतर्निहित सहसंबंध संरचना के साथ ऑपरेटर को संरेखित करके टighter स्पेक्ट्रल कंसंट्रेशन प्राप्त करती है।
• क्लोज्ड-फॉर्म सॉल्यूशंस: फॉरवर्ड और इनवर्स ट्रांसफॉर्मेशन दोनों के लिए स्पष्ट क्लोज्ड-फॉर्म एक्सप्रेशन का व्युत्पन्न, जो डीनॉइजिंग जैसे व्यावहारिक अनुप्रयोगों को सुगम बनाता है।

प्रायोगिक परिणाम
लेखकों ने तीन वास्तविक दुनिया के डेटासेट्स पर विधि का मूल्यांकन किया: सी सरफेस टेम्परेचर (SST), PM-2.5 सांद्रता, और COVID-19 कन्फर्म मामले। इन डेटासेट्स को निर्देशित कार्टेशियन उत्पाद ग्राफों पर सिग्नल्स के रूप में मॉडल किया गया था।

• डीनॉइजिंग प्रदर्शन: विभिन्न शोर स्तरों ($\sigma \in \{0.1, 0.2, 0.3, 0.4\}$) और ग्राफ कनेक्टिविटी (3-NN, 5-NN, 7-NN) के तहत डीनॉइजिंग कार्यों में, UGRM-GFT ने पारंपरिक फिक्स्ड-मैट्रिक्स दृष्टिकोणों (Lap-GFT, Adj-GFT, Id-GFT, SLap-GFT) को लगातार पछाड़ दिया।
• मेट्रिक्स: प्रस्तावित विधियों ने उच्च सिग्नल-टू-नॉइज़ रेशियो (SNR) और कम बैंडलिमिटिंग एप्रोक्सिमेशन एरर (BAE) प्राप्त किया। उदाहरण के लिए, SST डेटासेट पर, UGRM-GFT-II ने 9.2665 dB के Lap-GFT-II की तुलना में 9.5254 dB का SNR प्राप्त किया।
• एनर्जी कॉम्पैक्शन: UGRM-GFTs ने बेहतर ऊर्जा संकेंद्रण (energy compaction) प्रदर्शित किया। SST डेटासेट पर, अग्रणी 40 स्पेक्ट्रल घटकों (स्पेक्ट्रम का 10%) ने कुल सिग्नल ऊर्जा का 95.91% कैप्चर किया, जो फिक्स्ड-मैट्रिक्स बेसलाइन्स (जैसे Adj-GFT ने केवल ~22-31% कैप्चर किया) से काफी बेहतर था।
• पैरामीटर अनुकूलन: बेयसियन ऑप्टिमाइज़ेशन ने इष्टतम पैरामीटर $(\alpha^*, k^*)$ की पहचान की जो डेटासेट के अनुसार भिन्न थे। स्मूथ जियोफिजिकल सिग्नल्स (SST, PM-2.5) ने लैपलेसियन-प्रधान शासन ($\beta < 0$) को प्राथमिकता दी, जबकि प्रोपैगेशन-आधारित COVID डेटासेट ने सीमा के करीब ($\beta \approx -0.04$) शासन को प्राथमिकता दी, जो विधि की अनुकूलन क्षमता को प्रमाणित करता है।
• दक्षता: UGRM-GFT-II ने $20 \times 20$ उत्पाद ग्राफ पर UGRM-GFT-I की तुलना में पैरामीटर ऑप्टिमाइज़ेशन रनटाइम को लगभग 22.7% कम कर दिया।

महत्व और दावे
पेपर का दावा है कि प्रस्तावित UGRM-GFT एक पैरामीटराइज्ड रिप्रेजेंटेशन पेश करके पारंपरिक GSP की कठोरता को संबोधित करता है जो ग्राफ सिग्नल्स की विशिष्ट सहसंबंध संरचनाओं के अनुकूल होता है। SVD का लाभ उठाकर, विधि संख्यात्मक स्थिरता सुनिश्चित करती है जबकि UGRM फ्रेमवर्क डिग्री और लैपलेसियन जानकारी के बीच एक निरंतर इंटरपोलेशन की अनुमति देता है। लेखक दावा करते हैं कि इस लचीलेपन से स्मूथ जियोफिजिकल फील्ड से लेकर अनियमित महामारी प्रसार पैटर्न तक, विविध प्रकार के सिग्नल्स के लिए बेहतर ऊर्जा संकेंद्रण और डीनॉइजिंग प्रदर्शन मिलता है। यह कार्य ऑपरेटर पैरामीटर्स के आधार पर स्पेक्ट्रल ऑर्डरिंग के लिए एक सैद्धांतिक आधार प्रदान करता है और विविध वास्तविक डेटा के माध्यम से व्यावहारिक उपयोगिता प्रदर्शित करता है।