🤖 machine learning

Full-Spectrum Graph Neural Network: Expressive and Scalable

यह शोध पत्र फुल-स्पेक्ट्रम GNN (FSpecGNN) का प्रस्ताव करता है, जो एक स्केलेबल सेकंड-ऑर्डर स्पेक्ट्रल ग्राफ न्यूरल नेटवर्क है जो सिग्नल्स को नोड-पेयर डोमेन में उठाता है और क्लासिकल GNNs की एक्सप्रेसिविटी सीमाओं को पार करने के लिए बाइवेरिएट स्पेक्ट्रल फ़िल्टरिंग का उपयोग करता है, जिससे नोड-पेयर सिग्नल्स का यूनिवर्सल एप्रोक्सिमेशन और हेटरोफिलिक ग्राफ्स पर मजबूत प्रदर्शन प्राप्त होता है।

मूल लेखक: Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia

प्रकाशित 2026-05-08

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक जटिल सामाजिक नेटवर्क को समझने की कोशिश कर रहे हैं, जैसे कि एक हाई स्कूल कैफेटेरिया या एक विशाल ऑनलाइन समुदाय। आप यह पता लगाना चाहते हैं कि कौन किस समूह का हिस्सा है, कौन किसका दोस्त है, और जानकारी कैसे प्रवाहित होती है।

लंबे समय तक, कंप्यूटरों ने इस काम के लिए ग्राफ न्यूरल नेटवर्क (GNN) नामक एक उपकरण का उपयोग किया। एक मानक GNN को एक ऐसे व्यक्ति के रूप में सोचें जो कैफेटेरिया में घूम रहा है, अपने आस-पास के पड़ोसियों से हाथ मिला रहा है, और पूछ रहा है, "तुम्हारे दोस्त कौन हैं?" वे इस जानकारी को इकट्ठा करते हैं और अपनी समझ को अपडेट करते हैं।

हालाँकि, यह शोध पत्र बताता है कि इस दृष्टिकोण में एक बड़ी खामी है: मानक GNN बहुत सरल हैं। वे "1-WL टेस्ट" नामक एक नियम द्वारा सीमित हैं। सरल शब्दों में, इसका मतलब है कि वे दो ऐसे समूहों के बीच अंतर नहीं कर सकते जो बाहर से एक जैसे दिखते हैं, भले ही उनके आंतरिक संबंध पूरी तरह से अलग हों। यह दो जुड़वा बच्चों के बीच अंतर करने की कोशिश करने जैसा है जो बाहर से बिल्कुल एक जैसे दिखते हैं, केवल यह देखकर कि वे किन लोगों के पास खड़े हैं; यदि वे समान लोगों के पास खड़े होते हैं, तो मानक GNN उन्हें एक ही व्यक्ति समझ लेता है।

बड़ा विचार: "फुल-स्पेक्ट्रम" अपग्रेड

लेखक एक नया उपकरण प्रस्तावित करते हैं जिसे FSPECGNN (फुल-स्पेक्ट्रम ग्राफ न्यूरल नेटवर्क) कहा जाता है। यह समझने के लिए कि इसमें क्या खास है, आइए देखें कि यह खेल के नियमों को कैसे बदलता है।

1. "वन-ऑन-वन" से "डबल-डेट" तक

पुराना तरीका (मानक GNN): कंप्यूटर एक समय में एक व्यक्ति (एक नोड) को देखता है। वह पूछता है, "इस व्यक्ति का सिग्नल क्या है?" और इसे उनके कनेक्शन के आधार पर फ़िल्टर करता है। यह एक भीड़ भरे कमरे में एक व्यक्ति की आवाज़ सुनने जैसा है।
नया तरीका (FSPECGNN): कंप्यूटर लोगों के जोड़ों (नोड पेयर्स) को एक साथ देखता है। केवल व्यक्ति A को सुनने के बजाय, यह व्यक्ति A और व्यक्ति B के बीच के संबंध को सुनता है।
- उपमा: कल्पना कीजिए कि आप एक गाना समझने की कोशिश कर रहे हैं। पुराना तरीका केवल धुन (एक के बाद एक बजने वाले नोट्स) को सुनता है। नया तरीका हारमनी (तालमेल) सुनता है (दो नोट्स एक साथ कैसे बजते हैं)। जोड़ों का विश्लेषण करके, कंप्यूटर उन "कॉर्ड्स" (स्वर-संगतियों) को सुन सकता है जिन्हें पुराना तरीका मिस कर देता है, जिससे यह उन समूहों के बीच अंतर करने में सक्षम होता है जो दूर से देखने में एक जैसे लगते हैं।

2. "फुल स्पेक्ट्रम" फ़िल्टर

पुराना तरीका: कंप्यूटर एक सरल फ़िल्टर का उपयोग करता है जो केवल एकल आवृत्तियों (frequencies) की परवाह करता है (जैसे रेडियो किसी एक स्टेशन को ट्यून करना)। यह मानता है कि यदि दो चीजें जुड़ी हुई हैं, तो वे समान हैं।
नया तरीका: कंप्यूटर एक बाइवेरियट फ़िल्टर (bivariate filter) का उपयोग करता है। यह एक फैंसी तरीका है यह कहने का कि यह एक ही समय में दो आवृत्तियों के संयोजन को ट्यून कर सकता है।
- उपमा: एक रंग पैलेट (color palette) के बारे में सोचें। पुराना तरीका केवल लाल को लाल के साथ, या नीला को नीले के साथ मिला सकता था। नया तरीका लाल को नीले के साथ, या हरे को पीले के साथ मिला सकता है, जिससे पूरी तरह से नए शेड्स बनते हैं। यह इसे उन जटिल स्थितियों को संभालने में सक्षम बनाता है जहाँ जुड़े हुए लोग वास्तव में एक-दूसरे से अलग होते हैं (एक अवधारणा जिसे "हेटरोफिली" कहा जाता है)।

यह क्यों मायने रखता है? "हेटरोफिली" की समस्या

शोध पत्र एक विशिष्ट समस्या पर प्रकाश डालता है: हेटरोफिली (Heterophily)।

होमोफिली (सामान्य स्थिति): "एक जैसे लोग एक साथ रहते हैं।" कई ग्राफ में, दोस्तों की रुचियां समान होती हैं। मानक GNN यहाँ ठीक काम करते हैं।
हेटरोफिली (समस्या): "विपरीत आकर्षित करते हैं।" कुछ नेटवर्क में (जैसे राजनीतिक बहस या शिकारी-शिकार पारिस्थितिकी तंत्र), आपके पड़ोसी अक्सर आपके विपरीत होते हैं। यदि आप एक "बिल्ली" हैं, तो आपके पड़ोसी "कुत्ते" हो सकते हैं।
- विफलता: मानक GNN आपको अपने पड़ोसियों के साथ मिलाने की कोशिश करते हैं। यदि आप एक बिल्ली हैं और आपके पड़ोसी कुत्ते हैं, तो GNN आपको एक "बिल्ली-कुत्ता" हाइब्रिड बनाने की कोशिश करता है, जो आपकी पहचान को बिगाड़ देता है।
- समाधान: शोध पत्र गणितीय रूप से सिद्ध करता है कि इसे ठीक करने के लिए, आपको जोड़ों के बीच के अंतर को देखना होगा, न कि केवल समानता को। नया "फुल-स्पेक्ट्रम" तरीका इन "विपरीत" पड़ोसियों से होने वाले शोर (noise) को स्वाभाविक रूप से कम कर सकता है और आपकी पहचान को स्पष्ट रख सकता है। यह शोर-रद्द करने वाले (noise-canceling) हेडफ़ोन पहनने जैसा है जो विशेष रूप से उन लोगों की आवाज़ों को ब्लॉक करते हैं जो आपसे असहमत हैं, ताकि आप अपने स्वयं के विचारों को स्पष्ट रूप से सुन सकें।

क्या यह व्यावहारिक है? (स्केलेबिलिटी ट्रिक)

आप सोच सकते हैं, "यदि मुझे 10 लाख की आबादी वाले शहर में हर जोड़े को देखना पड़ता है, तो यह एक ट्रिलियन जोड़े होंगे! यह गणना करना असंभव है।"

लेखकों ने इसे एक चतुर गणितीय शॉर्टकट से हल किया है।

समस्या: सभी जोड़ों की सीधे गणना करना समुद्र के किनारे रेत के हर कण को एक-एक करके उठाने जैसा है।
समाधान: वे एक "लो-रैंक एप्रोक्सिमेशन" (low-rank approximation) का उपयोग करते हैं। इसे ऐसे समझें कि समुद्र तट केवल यादृच्छिक, अद्वितीय कणों से नहीं बना है, बल्कि मुख्य रूप से कुछ दोहराए जाने वाले पैटर्न से बना है। प्रत्येक कण को गिनने के बजाय, वे पैटर्न को गिनते हैं और गुणा करते हैं।
परिणाम: यह नया तरीका बड़े ग्राफों पर भी पुराने, सरल तरीकों जितना ही तेज़ है। इसके लिए सुपरकंप्यूटर की आवश्यकता नहीं है; यह मानक हार्डवेयर पर कुशलता से चलता है।

परिणाम

लेखकों ने इस नए उपकरण का परीक्षण दो मुख्य चीजों पर किया:

आकृतियों की गिनती: उन्होंने AI को ग्राफ में विशिष्ट पैटर्न (जैसे त्रिकोण या चक्र) गिनने के लिए कहा। नया टूल इस कार्य के लिए मौजूदा सबसे शक्तिशाली (लेकिन बहुत धीमे) उपकरणों के समान प्रभावी था, जो साबित करता है कि यह मानक GNN की तुलना में अधिक "स्मार्ट" है।
मिश्रित समूहों को छाँटना: उन्होंने इसे उन ग्राफों पर परखा जहाँ पड़ोसी अलग-अलग होते हैं (हेटरोफिलिक)। नए टूल ने लगातार अन्य सभी तरीकों को पछाड़ दिया, और उन समूहों को सही ढंग से पहचाना जिन्हें अन्य तरीके पहचानने में विफल रहे।

सारांश

यह शोध पत्र FSPECGNN पेश करता है, जो नेटवर्क का विश्लेषण करने के लिए कंप्यूटर का एक स्मार्ट तरीका है।

पुराने GNN: व्यक्तियों और उनके तत्काल दोस्तों को देखते हैं। सरल समूहों के लिए अच्छे हैं, लेकिन जटिल या मिश्रित समूहों के लिए खराब हैं।
FSPECGNN: जोड़ों और उनके संयुक्त "हारमनी" (तालमेल) को देखता है। यह उन जटिल संरचनाओं के बीच अंतर कर सकता है जो पुराने तरीके के लिए एक जैसे दिखते हैं।
जादू: यह "विपरीत" (हेटरोफिली) को पूरी तरह से संभालता है और यह सब बिना धीमा हुए करता है, जो इसे जटिल डेटा को समझने के लिए एक शक्तिशाली, व्यावहारिक अपग्रेड बनाता है।

तकनीकी सारांश: फुल-स्पेक्ट्रम ग्राफ न्यूरल नेटवर्क: एक्सप्रेसिव और स्केलेबल

समस्या विवरण

मानक स्पेक्ट्रल ग्राफ न्यूरल नेटवर्क (GNNs) ग्राफ प्रोपेगेशन को लाप्लासियन फिल्टरिंग के रूप में पैरामीटराइज़ करते हैं। जबकि यह स्थापित है कि स्पेक्ट्रल GNNs नोड सिग्नल्स का यूनिवर्सल एप्रोक्सिमेशन कर सकते हैं, गैर-आइसोमोर्फिक ग्राफों के बीच अंतर करने की उनकी एक्सप्रेसिव पावर 1-डायमेंशनल वीज़फिल्डर-लीमैन (1-WL) टेस्ट द्वारा सख्ती से सीमित है। यह सीमा उच्च-क्रम (higher-order) सिग्नल्स को यूनिवर्सल एप्रोक्सिमेट करने में उनकी अक्षमता को दर्शाती है। मौजूदा दृष्टिकोण जो 1-WL से ऊपर उठने का प्रयास करते हैं, वे आमतौर पर मैसेज पासिंग को स्थानिक डोमेन (spatial domain) में उच्च-क्रम डोमेन (जैसे नोड पेयर्स) तक लिफ्ट करते हैं, लेकिन एक संगत स्केलेबल स्पेक्ट्रल फ्रेमवर्क की कमी थी।

कार्यप्रणाली

लेखक FSPECGNN (फुल-स्पेक्ट्रम ग्राफ न्यूरल नेटवर्क) प्रस्तावित करते हैं, जो शास्त्रीय स्पेक्ट्रल GNNs का एक सेकंड-ऑर्डर जनरलाइजेशन है। कार्यप्रणाली दो मुख्य सैद्धांतिक प्रगतियों पर आधारित है:

सिग्नल डोमेन लिफ्टिंग: नोड सिग्नल्स $x \in \mathbb{R}^V$ को फ़िल्टर करने के बजाय, FSPECGNN नोड-पेयर सिग्नल्स $\varepsilon \in \mathbb{R}^{V \times V}$ पर कार्य करता है। यह सिग्नल को नोड डोमेन से नोड-पेयर डोमेन में लिफ्ट करता है।
बाइवैरियट स्पेक्ट्रल फिल्टरिंग: शास्त्रीय स्पेक्ट्रल फिल्टरिंग आइजनवैल्यूज (eigenvalues) पर एक यूनिवैरियट फंक्शन $g(\lambda)$ $g (λ)$ लागू करती है। FSPECGNN इसे आइजनवैल्यूज के जोड़ों पर एक बाइवैरियट फिल्टर $g(\lambda_i, \lambda_j)$ $g (λ_{i}, λ_{j})$ के रूप में विस्तारित करता है।
- फुल-स्पेक्ट्रम कन्वल्यूशन को इस प्रकार परिभाषित किया गया है:
  $G_\lambda *_{\mathcal{G}} \varepsilon = \sum_{i,j} g(\lambda_i, \lambda_j) u_i u_i^\top \varepsilon u_j u_j^\top$
  जहाँ $L = U\Lambda U^\top$ ग्राफ लाप्लासियन का आइजनडिकंपोजिशन (eigendecomposition) है।
- यह फॉर्मूलेशन शास्त्रीय स्पेक्ट्रल GNNs का सामान्यीकरण करता है, जिन्हें डायगोनल स्पेशल केस के रूप में दिखाया गया है (जो डायगोनल $g(\lambda_i, \lambda_i)$ तक फिल्टर को प्रतिबंधित करके प्राप्त होता है)।

स्केलेबिलिटी कार्यान्वयन:
नोड-पेयर डोमेन ( $n^2 \times n^2$ ) में प्रत्यक्ष गणना बड़े ग्राफों के लिए अव्यवहार्य है। इसे संबोधित करने के लिए, लेखक लो-रैंक टेंसर डिकंपोजिशन का उपयोग करके एक स्केलेबल कार्यान्वयन प्रस्तावित करते हैं:

बाइवैरियट पॉलिनोमियल फिल्टर को सेपरेबल यूनिवैरियट पॉलिनोमिअल्स के योग द्वारा एप्रोक्सिमेट किया जाता है: $P(L \otimes I, I \otimes L) \approx \sum_{r=1}^S f_r(L) \otimes h_r(L)$ ।
$(A \otimes B)\text{vec}(\varepsilon) = \text{vec}(B\varepsilon A^\top)$ के गुण का उपयोग करते हुए, कन्वल्यूशन को $h(L) \varepsilon f(L)^\top$ के रूप में कंप्यूट किया जाता है, जिससे $n^2$ -डायमेंशनल ऑपरेटर के स्पष्ट निर्माण से बचा जा सकता है।
प्रारंभिक नोड-पेयर सिग्नल $\varepsilon$ का निर्माण आइडेंटिटी और एक GAT लेयर ( $I + \alpha \text{GAT}$ ) के लर्नबल कॉम्बिनेशन के माध्यम से किया जाता है, जो फीचर-डिपेंडेंट ऑफ-डायगोनल मिक्सिंग को प्रेरित करता है।

मुख्य योगदान

सैद्धांतिक एक्सप्रेसिविटी:
- यूनिवर्सल एप्रोक्सिमेशन: लेखक सिद्ध करते हैं कि लीनियर FSPECGNN, वन-डायमेंशनल नोड-पेयर सिग्नल्स को यूनिवर्सल एप्रोक्सिमेट कर सकता है (थ्योरम 3.4), जो नोड्स से नोड पेयर्स तक स्पेक्ट्रल GNNs की यूनिवर्सलिटी को विस्तारित करता है।
- 1-WL सुप्रेमेसी: यह पेपर स्थापित करता है कि FSPECGNN, 1-WL अपर बाउंड को पार कर सकता है। विशेष रूप से, सिंपल स्पेक्ट्रम और नॉन-जीरो स्पेक्ट्रल कोएफिशिएंट्स की स्थितियों के तहत, FSPECG परंपरा के अनुसार FSPECG, Local 2-GNN (एक स्पैटियल सेकंड-ऑर्डर मॉडल) के समकक्ष एक्सप्रेसिविटी प्राप्त कर सकता है, और विशिष्ट बाइवैरियट पॉलिनोमिअल्स के साथ इससे भी आगे निकल सकता है (थ्योरम 3.8)।
हेटरोफिलिक ग्राफ लर्निंग:
- लेखक हेटरोफिलिक ग्राफ्स में क्लास सेपरेशन के लिए इष्टतम कन्वल्यूशन का विश्लेषण करते हैं। वे सिद्ध करते हैं कि इष्टतम ऑपरेटर के लिए इंटर-क्लास कनेक्शन को दबाने के लिए स्पेक्ट्रल बेसिस में ऑफ-डायगोनल कंपोनेंट्स की आवश्यकता होती है (थ्योरम 4.1)।
- एक मौलिक सीमा सिद्ध की गई है: शास्त्रींय स्पेक्ट्रल कन्वल्यूशन (डायगोनल फिल्टर्स) इस इष्टतम ऑपरेटर को तब तक साकार नहीं कर सकते जब तक कि वे आइडेंटिटी के स्केलर मल्टीपल के रूप में डीजेनरेट न हो जाएं (थ्योरम 4.2)। FSPECGNN, ऑफ-डायगोनल स्पेक्ट्रल इंटरैक्शन की अनुमति देकर, इस इष्टतम ऑपरेटर को साकार कर सकता है।
स्केलेबिलिटी:
- प्रस्तावित लो-रैंक एप्रोक्सिमेशन मौजूदा पॉलिनोमियल स्पेक्ट्रल GNNs के समान $O(Kmd) $की कम्प्यूटेशनल कॉम्प्लेक्सिटी तक कम कर देता है, जबकि आइजनडिकंपोजिशन की$ O(n^3) $लागत और स्पष्ट नोड-पेयर ऑपरेशंस की$ O(n^4)$ मेमोरी से बचता है।

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

पेपर तीन कार्यों पर FSPECGNN का मूल्यांकन करता है:

हेटरोफिलिक नोड क्लासिफिकेशन:
- आठ डेटासेट्स (जैसे, Texas, Wisconsin, Squirrel, Roman Empire) पर परीक्षण किया गया।
- FSPECGNN वेरिएंट्स (Chebyshev, ChebNetII, और Bernstein बेस का उपयोग करते हुए) ने लगातार स्टेट-ऑफ-द-आर्ट स्पेक्ट्रल बेसलाइन्स (ChebNet, GPRGNN, BernNet, आदि) को पछाड़ दिया।
- एब्लेशन स्टडीज ने पुष्टि की कि ऑफ-डायगोनल इंटरैक्शन या "इन-फिल्टर" को हटाने से प्रदर्शन काफी गिर गया, जो क्रॉस-आइजनस्पेस कपलिंग को मॉडल करने की आवश्यकता को प्रमाणित करता है।
सबस्ट्रक्चर काउंटिंग (एक्सप्रेसिविटी वैलिडेशन):
- होमोमॉर्फिज्म और (कॉर्डल) साइकिल काउंटिंग बेंचमार्क पर मूल्यांकन किया गया।
- FSPECGNN ने Local 2-GNN और Local 2-FGNN के प्रदर्शन के बराबर प्रदर्शन किया, जो इस सैद्धांतिक भविष्यवाणी की पुष्टि करता है कि यह स्पैटियल सेकंड-ऑर्डर मॉडल्स की एक्सप्रेसिविटी से मेल खाता है।
- इसने इन कार्यों पर स्पेक्ट्रल इनवेरिएंट GNNs और मानक MPNNs की तुलना में काफी बेहतर प्रदर्शन किया।
दक्षता (Efficiency):
- FSPECGNN ने स्पैटियल सेकंड-ऑर्डर बेसलाइन्स (Local 2-GNN, Local 2-FGNN, Subgraph GNN) की तुलना में काफी कम रनटाइम (लगभग 5 $\times$ तेज़) और कम पीक GPU मेमोरी प्रदर्शित की।

महत्व और दावे

पेपर का दावा है कि FSPECGNN, स्पैटियल हायर-ऑर्डर GNNs के लिए एक सिद्धांत आधारित स्पेक्ट्रल काउंटरपार्ट प्रदान करता है। इसका प्राथमिक महत्व स्पेक्ट्रल मेथड्स और हायर-ऑर्डर एक्सप्रेसिविटी के बीच के अंतर को पाटने में निहित है:

यह दर्शाता है कि हेटरोफिली एक स्वाभाविक रूप से सेकंड-ऑर्डर घटना है जिसके लिए ऑफ-डायगोनल स्पेक्ट्रल कंपोनेंट्स की आवश्यकता होती है, जिनकी शास्त्रीय स्पेक्ट्रल GNNs में संरचनात्मक रूप से कमी होती है।
यह एक स्केलेबल आर्किटेक्चर प्रदान करता है जो स्पष्ट हायर-ऑर्डर स्पैटियल मेथड्स की अत्यधिक कम्प्यूटेशनल लागत के बिना, सेकंड-ऑर्डर मॉडलिंग (1-WL से ऊपर, पेयर्स पर यूनिवर्सल एप्रोक्सिमेशन) के सैद्धांतिक लाभों को बनाए रखता है।
यह कार्य डायगोनल स्पेक्ट्रल फिल्टर्स की एक मौलिक सीमा की पहचान करता है और इसे दूर करने के लिए एक सामान्यीकरण योग्य फ्रेमवर्क (k-वें ऑर्डर तक विस्तार योग्य) प्रस्तावित करता है।