🤖 machine learning

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

यह शोध पत्र रामानुजन प्रोपेगेशन (Ramanujan Propagation) प्रस्तुत करता है, जो एक ग्राफ रीवायरिंग रणनीति है जो गैर-ऋणात्मक प्रतिरोध वक्रता (non-negative resistance curvature) की गारंटी देने के लिए रामानुजन ग्राफों का लाभ उठाती है, जिससे ओवर-स्क्वैशिंगिंग (over-squashing) को कम किया जा सकता है और ग्राफ न्यूरल नेटवर्क में मौजूदा अत्याधुनिक तकनीकों से बेहतर प्रदर्शन किया जा सकता है।

मूल लेखक: Hugo Attali, Rachid El Jouhri

प्रकाशित 2026-06-23

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

CC BY 4.0

मूल लेखक: Hugo Attali, Rachid El Jouhri

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

यहाँ एक शोध पत्र (paper) का सरल भाषा और रचनात्मक उपमाओं (analogies) के साथ विवरण दिया गया है।

बड़ी समस्या: "भीड़भाड़ वाला गलियारा" प्रभाव (The "Crowded Hallway" Effect)

एक ग्राफ न्यूरल नेटवर्क (GNN) की कल्पना एक विशाल, जटिल इमारत (ग्राफ) में समाचार साझा करने की कोशिश कर रहे लोगों के समूह के रूप में करें।

यह कैसे काम करता है: प्रत्येक व्यक्ति (नोड) अपने निकटतम पड़ोसियों से बात करता है, जो फिर अपने पड़ोसियों से बात करते हैं, और इसी तरह यह सिलसिला चलता रहता है।
समस्या: यदि इमारत में संकरे गलियारे, बंद रास्ते (dead ends), या बहुत बड़े खुले कमरे हैं जहाँ हर कोई एक साथ जमा हो जाता है, तो समाचार विकृत (distort) हो जाता है।
- ओवर-स्क्वैशिंग (Over-squashing): कल्पना कीजिए कि आप एक पूरी लाइब्रेरी की जानकारी को एक छोटे से पोस्टकार्ड में दबाने की कोशिश कर रहे हैं। जैसे-जैसे संदेश सबसे दूर के कमरे से फ्रंट डेस्क तक पहुँचता है, पोस्टकार्ड पकड़े हुए व्यक्ति को बहुत अधिक जानकारी को एक बहुत छोटी जगह में कंप्रेस (compress) करना पड़ता है। जब तक यह पहुँचता है, विवरण खो जाते हैं। इसे ओवर-स्क्वैशिंग कहा जाता है।
- ओवरस्मूथिंग (Oversmoothing): कल्पना कीजिए कि एक भीड़ भरे कमरे में हर कोई एक ही चीज़ चिल्लाने लगता है जब तक कि हर कोई बिल्कुल एक जैसा न सुनाई देने लगे। अंततः, आप पहचान ही नहीं पाते कि कौन कौन है। यह ओवरस्मूथिंग है।

समाधान: एक "सुपर-हाइवे" बनाना

लेखक, ह्यूगो अट्टली और राशिद एल जौहरी, लोगों के बात करने से पहले इमारत के गलियारों को पुनर्गठित करने का एक नया तरीका प्रस्तावित करते हैं। वे इसे रामानुजन प्रोपेगेशन (Ramanujan Propagation) कहते हैं।

मौजूदा अव्यवस्थित गलियारों को ठीक करने के बजाय, वे एक विशेष ब्लूप्रिंट का उपयोग करके इमारत के कुछ हिस्सों को फिर से बनाने का सुझाव देते हैं जिसे रामानुजन ग्राफ (Ramanujan Graph) कहा जाता है।

रामानुजन ग्राफ क्या है?

रामानुजन ग्राफ की कल्पना एक पूरी तरह से डिज़ाइन किए गए सिटी ग्रिड (city grid) के रूप में करें।

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

उपमा (Analogy): कल्पना कीजिए कि मूल ग्राफ एक भूलभुलैया है जिसमें कई बंद रास्ते और बाधाएं (bottlenecks) हैं। रामानुजन ग्राफ उस भूलभुलैया में जादुई लिफ्टों और एक्सप्रेस टनल (express tunnels) की एक श्रृंखला जोड़ने जैसा है जो दूर के हिस्सों को सीधे जोड़ती है, यह सुनिश्चित करती है कि दो लोग चाहे एक-दूसरे से कितने भी दूर क्यों न हों, वे बिना संदेश के कुचले गए (crushed) जल्दी और स्पष्ट रूप से एक-दूसरे से बात कर सकें।

उन्होंने यह कैसे किया (एल्गोरिदम)

आप पूरी इमारत को नए भवन से बदल नहीं सकते, अन्यथा आप मूल संरचना के विशिष्ट विवरण खो सकते हैं (जैसे कि कौन से कमरे वास्तव में एक-दूसरे के बगल में हैं)।

इसलिए, लेखकों ने एक स्मार्ट निर्माण योजना बनाई:

पड़ोस को बनाए रखें: उन्होंने उन मूल कनेक्शनों को रखा जो स्थानीय विवरणों के लिए महत्वपूर्ण हैं।
सुपर-हाइवे जोड़ें: उन्होंने "परम्यूटेशन साइकिल्स" (permutation cycles) पर आधारित एक गणितीय रेसिपी का उपयोग करके उन नोड्स के बीच नए "एक्सप्रेस टनल" जोड़े जो मूल मानचित्र में पास हैं लेकिन नेटवर्क में दूर हैं।
जादुई डिग्री (Magic Degree): उन्होंने इमारत के आकार के आधार पर ठीक गणना की कि कितने नए टनल जोड़ने हैं। यदि इमारत बहुत बड़ी है, तो वे "रेसिस्टेंस" को कम रखने के लिए अधिक टनल जोड़ते हैं।

उन्हें क्या मिला (परिणाम)

लेखकों ने कई अलग-अलग डेटासेट्स (जैसे रासायनिक अणु, सोशल नेटवर्क और प्रोटीन संरचनाएं) पर इस नए "रामानुजन रीवायरिंग" का परीक्षण किया और इसकी तुलना नौ अन्य शीर्ष विधियों से की।

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

मुख्य निष्कर्ष (Bottom Line)

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

मुख्य बात: उन्होंने केवल नेटवर्क को गहरा (deeper) नहीं बनाया; उन्होंने इसे गणितीय रूप से सिद्ध तरीके से अधिक चौड़ा (wider) और बेहतर ढंग से जुड़ा हुआ बनाया, जिससे AI पहले की तुलना में डेटा में लंबी दूरी के संबंधों को बहुत बेहतर तरीके से समझ सका।

तकनीकी सारांश: गैर-ऋणात्मक प्रतिरोध वक्रता के साथ रामानुजन ग्राफ रीवायरिंग (Ramanujan Graph Rewiring with Non-Negative Resistance Curvature)

समस्या विवरण (Problem Statement)

ग्राफ न्यूरल नेटवर्क (GNNs) ने ग्राफ-संरचित डेटा पर सीखने के लिए एक प्रमुख प्रतिमान स्थापित किया है। हालांकि, मानक मैसेज पासिंग न्यूरल नेटवर्क (MPNNs) लंबी दूरी की निर्भरताओं (long-range dependencies) को संभालने में महत्वपूर्ण सीमाओं का सामना करते हैं। जैसे-जैसे दूरस्थ जानकारी को कैप्चर करने के लिए परतों (layers) की संख्या बढ़ती है, GNNs ओवर-स्क्वैशिंग (over-squashing) का सामना करते हैं, जो एक ऐसी घटना है जहाँ घातांकीय रूप से बड़े पड़ोस (neighborhoods) को निश्चित-आयामी एम्बेडिंग्स में संकुचित कर दिया जाता है, जिससे दूर के नोड्स की जानकारी खो जाती है। यह समस्या टोपोलॉजिकल बॉटलनेक्स (topological bottlenecks), जैसे कि विरल ब्रिज (sparse bridges) और बड़े व्यास (large diameters) द्वारा और भी बढ़ जाती है, जो प्रभावी सूचना प्रवाह में बाधा डालते हैं। इसके विपरीत, अत्यधिक सघन सबग्राफ (dense subgraphs) ओवरस्मूथिंग (oversmoothing) की ओर ले जा सकते हैं, जहाँ नोड प्रतिनिधित्व अविभेद्य हो जाते हैं। यद्यपि टोपोलॉजी को संशोधित करने और इन समस्याओं को कम करने के लिए विभिन्न ग्राफ रीवायरिंग तकनीकें प्रस्तावित की गई हैं, उनमें से कई महंगी वक्रता (curvature) या प्रतिरोध गणनाओं पर निर्भर करती हैं, या कुशल मैसेज पासिंग के लिए कठोर संरचनात्मक गारंटी प्रदान करने में विफल रहती हैं।

कार्यप्रणाली (Methodology)

लेखक रामानुजन प्रोपेगेशन (Ramanujan Propagation) पेश करते हैं, जो एक ग्राफ रीवायरिंग रणनीति है जो इनपुट ग्राफ $G$ से एक नया ग्राफ $G^*$ निर्मित करती है, जो $d$ -रेगुलर रामानुजन ग्राफ के गुणों को गैर-ऋणात्मक प्रतिरोध वक्रता (Non-negative Resistance Curvature - RN) के साथ जोड़ती है।

सैद्धांतिक आधार (Theoretical Foundations)

प्रतिरोध वक्रता और ओवर-स्क्वैशिंग: शोध पत्र नोड-स्तरीय प्रतिरोध वक्रता $p(v)$ को रैंडम वॉक में कम्यूट टाइम (commute time) की अवधारणा से जोड़ता है। यह स्थापित करता है कि बड़ी प्रतिरोध वक्रता मान नोड्स के बीच कम्यूट टाइम के बाउंड को कड़ा करते हैं, जिससे क्रॉस-नोड संवेदनशीलता (Jacobian sensitivities) के क्षय को कम किया जा सकता है और ओवर-स्क्वैशिंग को कम किया जा सकता है।
रामानुजन ग्राफ: एक $d$ -रेगुलर ग्राफ रामानुजन कहलाता है यदि इसके एडजेसेंसी मैट्रिक्स के सभी गैर-तुच्छ आइजनवैल्यू (non-trivial eigenvalues) $|\mu| \leq 2\sqrt{d-1}$ को संतुष्ट करते हैं। इन ग्राफों में इष्टतम स्पेक्ट्रल एक्सपेंशन गुण होते हैं।
गैर-ऋणात्मक प्रतिरोध वक्रता (RN): लेखक सिद्ध करते हैं कि एक रामानुजन ग्राफ के लिए जिसका डिग्री $d$ , वर्टिसिस $N$ की संख्या के साथ पर्याप्त रूप से स्केल होता है (विशेष रूप से $d \geq 4C^2 (\log N)^{2/3}$ ), वह ग्राफ गैर-ऋणात्मक प्रतिरोध व,,,,\ $p(v) \geq 0$ की गारंटी देता है।
संरचनात्मक गारंटी: इन शर्तों के तहत, परिणामी रामानुजन RN ग्राफ निम्नलिखित प्रदर्शित करता है:
- कम व्यास (Low Diameter): $O(\frac{\log N}{\log \log N})$ द्वारा सीमित, जो पथ लंबाई को काफी छोटा कर देता है।
- कम प्रभावी प्रतिरोध (Low Effective Resistance): अधिकतम प्रभावी प्रतिरोध को डिग्री $d$ द्वारा कड़ाई से नियंत्रित किया जाता है, जिससे कुशल संचार सुलभ होता है।
- ओवरफिटिंग का शमन: स्थिर डिग्री $d$ मूल ग्राफ में पाई जाने वाली स्थानीय टोपोलॉजिकल अनियमितताओं पर ओवरफिटिंग को रोकता है।

एल्गोरिद्मिक ढांचा (Algorithmic Framework)

प्रस्तावित रीवायरिंग एल्गोरिदम इस प्रकार आगे बढ़ता है:

डिग्री चयन: RN स्थिति को संतुष्ट करने के लिए लक्ष्य डिग्री $d = \lceil 4 (\log N)^{2/3} \rceil$ निर्धारित करें।
पोजीशनल एनकोडिंग: मूल ग्राफ की स्थानीय ज्यामिति को संरक्षित करने के लिए लैपलेसियन या रैंडम-वॉक एनकोडिंग का उपयोग करके प्रत्येक नोड के लिए पोजीशनल रिप्रेजेंटेशन $z_v$ की गणना करें।
ग्राफ निर्माण: फ्राइडमैन के परम्यूटेशन-साइकिल निर्माण (Friedman's permutation-cycle construction) का उपयोग करके समान वर्टेक्स सेट पर पुनर्गठित ग्राफ $G^*$ का निर्माण करें। एल्गोरिदम कैंडिडेट परम्यूटेशन साइकल को सैंपल करता है और उस एक को चुनता है जो पोजीशनल स्पेस में जुड़े नोड्स के बीच की दूरी ( $\Delta_{uv} = \|z_u - z_v\|^2$ ) को न्यूनतम करता है।
जटिलता: प्रीप्रोसेसिंग लागत डिस्टेंस मैट्रिक्स की गणना द्वारा संचालित होती है, जिसके परिणामस्वरूप $O(N^2)$ समय जटिलता आती है, जो क्यूबिक-टाइम रेजिस्टेंस-आधारित विधियों (जैसे GTR) या क्यूबिक/क्वाड्रेटिक कर्वेचर-आधारित विधियों (जैसे SDRF) की तुलना में काफी तेज़ है।

मुख्य योगदान (Key Contributions)

सैद्धांतिक गारंटी: यह शोध पत्र स्थापित करता है कि उपयुक्त रूप से चुने गए रामानुजन ग्राफ गैर-ऋणात्मक प्रतिरोध वक्रता की गारंटी देते हैं, जो ओवर-स्क्वैशिंग को कम करने के लिए एक कठोर संरचनात्मक प्रायर (structural prior) प्रदान करता है।
एल्गोरिद्मिक नवाचार: एक नवीन रीवायरिंग एल्गोरिदम जो मूल ग्राफ की स्थानीय कनेक्टिविटी और निकटता को संरक्षित करते हुए एक रामानुजन RN ग्राफ का निर्माण करता है, जिससे नैव रैंडम एक्सपेंशन के दोषों से बचा जा सके।
व्यापक मूल्यांकन: विविध बेंचमार्क पर नौ अत्याधुनिक (state-of-the-art) रीवायरिंग तकनीकों (SDRF, BORF, FoSR, GTR, PANDA और एक्सपेंडर-आधारित विधियों सहित) के विरुद्ध इस पद्धति का मूल्यांकन किया गया है।

प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने दो प्राथमिक बेंचमार्क पर RNRP का मूल्यांकन किया:

TUDataset: GCN और GIN बैकबोन का उपयोग करते हुए छह डेटासेट (REDDIT-B, IMIMB-B, MUTAG, ENZYMES, PROTEINS, COLLAB)।
- RNRP ने सभी बेसलाइन्स को लगातार पछाड़ दिया। उदाहरण के लिए, GIN बैकबोन के साथ, इसने REDDIT-B पर 92.42% सटीकता प्राप्त की (90.33% अगले सर्वश्रेष्ठ के मुकाबले) और MUTAG पर 89.50% प्राप्त की।
- इसने बैकबोन की तुलना में औसतन लगभग 12% सुधार प्रदर्शित किया।
लॉन्ग-रेंज ग्राफ बेंचमार्क (LRGB): पेप्टाइड्स-स्ट्रक्ट (रिग्रेशन) और पेप्टाइड्स-फंक (मल्टी-लेबल क्लासिफिकेशन)।
- RNRP ने अत्याधुनिक परिणाम प्राप्त किए, जो दोनों कार्यों में GCN बैकबोन में औसतन 14% का सुधार करता है।
- Peptides-Func पर, इसने 66.26% औसत परिशुद्धता (Average Precision) प्राप्त की, जो अगले सर्वश्रेष्ठ (LASER - 64.40%) से बेहतर है।
दक्षता: Reddit-Binary डेटासेट पर RNRP की प्रीप्रोसेसिंग GTR की तुलना में 65 $\times$ तेज़ और SDRF की तुलना में 200 $\times$ तेज़ है, जो कम्प्यूटेशनल लागत और भविष्य कहनेवाला प्रदर्शन के बीच एक बेहतर संतुलन प्रदान करती है।
एब्लेशन अध्ययन (Ablation Studies):
- निकटता संरक्षण (Proximity Preservation): नोड निकटता को संरक्षित करने वाली रीवायरिंग (RNRP), शुद्ध रैंडम रामानुजन RN ग्राफ की तुलना में काफी बेहतर प्रदर्शन करती है, जो पुष्टि करती है कि स्थानीय संरचना बनाए रखना महत्वपूर्ण है।
- ओवरस्मूथिंग: RNRP मूल ग्राफ की तुलना में प्रशिक्षण के दौरान उच्च डिरिचलेट ऊर्जा (Dirichlet energy) बनाए रखता है, जो लंबी दूरी के प्रसार क्षमताओं को संरक्षित करते हुए ओवरस्मूथिंग में कमी का संकेत देता है।

महत्व (Significance)

यह शोध पत्र रामानुजन ग्राफ को केवल विस्तार (expansion) के लिए एक ह्यूरिस्टिक के रूप में नहीं, बल्कि स्केलेबल, टोपोलॉजी-अवेयर मैसेज पासिंग के लिए एक कठोर संरचनात्मक प्रायर के रूप में स्थापित करता है। गैर-ऋणात्मक प्रतिरोध वक्रता और कम व्यास की गणितीय गारंटी देकर, प्रस्तावित विधि GNNs की मौलिक टोपोलॉजिकल बाधाओं को संबोधित करती है। यह कार्य प्रदर्शित करता है कि रामानुजन ग्राफ के स्पेक्ट्रल अनुकूलन (spectral optimality) को प्रतिरोध वक्रता के ज्यामितीय बाधाओं के साथ जोड़ने से एक ऐसी रीवायरिंग रणनीति प्राप्त होती है जो सैद्धांतिक रूप से सुदृढ़ और अनुभवजन्य रूप से श्रेष्ठ है, जो कम्प्यूटेशनल दक्षता बनाए रखते हुए लंबी दूरी की निर्भरता सीखने वाले कार्यों पर अत्याधुनिक प्रदर्शन प्राप्त करती है।