🤖 machine learning

Generalized Schrödinger Bridge on Graphs

यह शोध पत्र ग्राफ पर जनरलाइज्ड श्रोडिंगर ब्रिज (GSBoG) प्रस्तुत करता है, जो एक स्केलेबल, डेटा-संचालित ढांचा है जो एंडपॉइंट बाधाओं को संतुष्ट करने और स्टेट-डिपेंडेंट रनिंग कॉस्ट को कम करने के लिए ट्राजेक्टरी-लेवल लाइकलीहुड्स को अनुकूलित करके किसी भी मनमाने ग्राफ पर निष्पादन योग्य कंटीन्यूअस-टाइम मार्कोव चेन पॉलिसियों को सीखता है।

मूल लेखक: Panagiotis Theodoropoulos, Juno Nam, Evangelos Theodorou, Jaemoo Choi

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

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

CC BY 4.0

मूल लेखक: Panagiotis Theodoropoulos, Juno Nam, Evangelos Theodorou, Jaemoo Choi

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

कल्पना कीजिए कि आप एक विशाल, जटिल शहर के ट्रैफिक मैनेजर हैं। यह शहर सड़कों और कारों से नहीं बना है, बल्कि नोड्स (जैसे गोदाम, बंदरगाह, या यहाँ तक कि सूक्ष्म प्रोटीन आकार) और एजेस (वे सड़कें जो उन्हें जोड़ती हैं) से बना है।

आपका काम लोगों की एक भीड़ (या "द्रव्यमान/मास") को एक शुरुआती बिंदु (स्रोत) से एक गंतव्य (लक्ष्य) तक एक विशिष्ट समय सीमा के भीतर पहुँचाना है। लेकिन इसमें एक पेंच है:

आप केवल मौजूदा सड़कों के माध्यम से ही लोगों को चला सकते हैं।
आप ट्रैफिक जाम (भीड़भाड़) से बचना चाहते हैं।
आप चाहते हैं कि लोग सबसे कुशल, कम तनावपूर्ण मार्ग का पालन करें, न कि केवल सबसे छोटे मार्ग का।

लंबे समय तक, इस समस्या को हल करने के लिए मौजूदा तरीके ऐसे थे जैसे पूरे शहर के ट्रैफिक प्रवाह को कागज के एक ही विशाल टुकड़े पर योजना बनाने की कोशिश करना। वे एक स्थिर (static) मानचित्र की गणना करते थे कि हर किसी को कहाँ होना चाहिए, लेकिन वे आपको यह आसानी से नहीं बता पाते थे कि वास्तविक समय में कारों को कैसे चलाना है, खासकर यदि शहर बहुत बड़ा हो या सड़कें विरल (कम कनेक्शन वाली) हों। वे अक्सर ट्रैफिक जाम में फंस जाते थे या गणित को हल करने के चक्कर में कंप्यूटर को क्रैश कर देते थे।

पेश है GSBoG (ग्राफ पर सामान्यीकृत श्रोडिंगर ब्रिज - Generalized Schrödinger Bridge on Graphs)।

इस शोध पत्र के लेखक इस समस्या को प्रबंधित करने का एक नया, स्मार्ट तरीका पेश करते हैं। यह कैसे काम करता है, इसके लिए सरल उपमाओं का उपयोग किया गया है:

1. "स्मार्ट भीड़" बनाम "स्थिर मानचित्र" (The "Smart Crowd" vs. The "Static Map")

पुराने तरीके एक स्थिर मानचित्र देने और यह कहने जैसे थे, "वहाँ जाओ।" यदि मानचित्र बहुत अधिक भीड़भाड़ वाला हो जाता, तो लोग जमा होने लगते।

GSBoG स्मार्ट, स्वायत्त (self-driving) टैक्सियों के एक बेड़े को नियुक्त करने जैसा है। एक स्थिर मानचित्र के बजाय, ये टैक्सियाँ एक गतिशील नीति (dynamic policy) सीखती हैं। वे केवल यह नहीं जानतीं कि कहाँ जाना है; वे यह भी जानती हैं कि हर पल कैसे आगे बढ़ना है।

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

2. "परीक्षण और त्रुटि" से सीखना (The "Trial and Error" Approach)

पूरे शहर की हर एक सड़क के लिए एक साथ गणित हल करने की कोशिश करने के बजाय (जो विशाल शहरों के लिए असंभव है), GSBoG एक कण-आधारित दृष्टिकोण (particle-based approach) का उपयोग करता है।

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

3. ट्रैफिक जाम की "लागत" (The "Cost" of Traffic Jams)

यह शोध पत्र एक विशेष विशेषता पेश करता है: स्टेट-डिपेंडेंट कॉस्ट्स (State-Dependent Costs)।

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

4. उन्होंने इसका परीक्षण कहाँ किया?

लेखकों ने केवल सिद्धांत की बात नहीं की; उन्होंने इसे तीन बहुत अलग "शहरों" पर परखा:

सप्लाई चेन सिटी: 9,500+ स्थानों (जैसे बंदरगाह और गोदाम) का एक विशाल नेटवर्क।
- परिणाम: अन्य तरीकों ने या तो कंप्यूटर को क्रैश कर दिया या भारी ट्रैफिक जाम पैदा किया। GSBoG ने वस्तुओं को सफलतापूर्वक पहुँचाया, ट्रैफिक को सुचारू रखा, और मुख्य केंद्रों को जाम होने से बचाया।
असाइनमेंट पहेली (The Assignment Puzzle): श्रमिकों को नौकरियों से मिलाने का कार्य (जैसे लोगों को मिलाने वाला डेटिंग ऐप)।
- परिणाम: GSBoG ने लगभग हर बार सटीक मिलान पाया, जिससे साबित हुआ कि यह जटिल पेयरिंग समस्याओं को कुशलतापूर्वक संभाल सकता है।
प्रोटीन फोल्डिंग लैब: एक सूक्ष्म दुनिया जहाँ एक छोटा प्रोटीन (Chignolin) एक अव्यवस्थित आकार से एक व्यवस्थित, कार्यात्मक आकार में मुड़ने (fold होने) की कोशिश करता है।
- परिणाम: प्रकृति में, यह बहुत दुर्लभ होता है। GSBoG ने एक मार्गदर्शक की तरह काम किया, प्रोटीन को धीरे से एक सुचारू, कम ऊर्जा वाले पथ पर धकेला ताकि वह सही ढंग से फोल्ड हो सके, और उन उच्च-ऊर्जा "चट्टानों" से बचा जो उसे तोड़ सकती थीं।

मुख्य निष्कर्ष (The Big Takeaway)

शोध पत्र का दावा है कि GSBoG एक स्केलेबल, डेटा-संचालित उपकरण है जो जटिल नेटवर्क में चीजों को ले जाने का तरीका सीखता है।

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

संक्षेप में, GSBoG एक अराजक, भीड़भाड़ वाले और जटिल परिवहन समस्या को गति के एक सुचारू, बहते हुए प्रवाह में बदल देता है, जो एक कठोर, वैश्विक मानचित्र के बजाय स्मार्ट, स्थानीय निर्णयों द्वारा निर्देशित होता है।

तकनीकी सारांश: ग्राफ पर सामान्यीकृत श्रोडिंगर ब्रिज (GSBoG)

समस्या विवरण
ग्राफ पर परिवहन एक मौलिक चुनौती है जो आपूर्ति श्रृंखलाओं और यातायात बुनियादी ढांचे से लेकर आणविक गतिकी (molecular kinetics) जैसे डोमेन में फैली हुई है। जबकि ग्राफ पर ऑप्टिमल ट्रांसपोर्ट (OT) स्रोत और लक्ष्य संभाव्यता वितरणों (probability distributions) को मिलाने के लिए सिद्धांतवादी विधियाँ प्रदान करता है, मौजूदा दृष्टिकोण अक्सर स्थिर कपलिंग (static couplings) प्रदान करते हैं जो समय-निर्भर द्रव्यमान संचलन का वर्णन करने में विफल रहते हैं या निष्पादनीय नियंत्रण नीतियां (executable control policies) प्रदान नहीं कर पाते हैं। इसके अलावा, ग्राफ परिवहन के लिए गतिशील सूत्रण (dynamic formulations), जैसे कि संभाव्यता सिम्प्लेक्स पर हैमिल्टनियन प्रवाह को हल करने वाले, बड़े और विरल (sparse) टोपोलॉजी पर खराब स्केलेबिलिटी से ग्रस्त होते हैं और अक्सर विशिष्ट अनुप्रयोग-आधारित अवस्था-निर्भर लागतों (जैसे भीड़भाड़ या ऊर्जा बाधाएं) के तहत मध्यवर्ती प्रक्षेप पथों (intermediate trajectories) को अनुकूलित करने के लिए पर्याप्त अभिव्यंजना (expressivity) की कमी रखते हैं। मुख्य चुनौती एक व्यवहार्य, टोपोलॉजी-सम्मानजनक विकास (evolution) का निर्माण करना है जो नेटवर्क लागतों को कम करते हुए और क्षमता सीमाओं जैसे परिचालन संबंधी बाधाओं को समायोजित करते हुए मध्यवर्ती वितरणों को नियंत्रित कर सके।

कार्यप्रणाली
लेखक ग्राफ पर सामान्यीकृत श्रोडिंगर ब्रिज (GSBoG) पेश करते हैं, जो किसी भी ग्राफ पर निष्पादनीय, नियंत्रित निरंतर-समय मार्कोव चेन (CTMC) नीतियों को सीखने के लिए एक डेटा-संचालित ढांचा है। यह विधि निरंतर अवस्था स्थानों से डिस्क्रीट, ग्राफ-संरचित डोमेन तक 'जनरलाइज्ड श्रोडिंगर ब्रिज' (GSB) के सिद्धांतों का विस्तार करती है।

गणितीय सूत्रण:
- समस्या को एक CTMC के पाथ मेजर्स (path measures) पर एक कॉस्ट फंक्शनल को न्यूनतम करने के रूप में तैयार किया गया है। उद्देश्य एक रनिंग कॉस्ट $f_t(x, p_t)$ (अवस्था और मार्जिनल वितरण पर निर्भर) को एक KL डाइवर्जेंस टर्म के साथ जोड़ता है, जो नियंत्रित गतिकी को एक संदर्भ CTMC प्रक्रिया की ओर नियमित (regularize) करता है।
- लेखक निरंतर-अवस्था सूत्रण के समानांतर डिस्क्रीट अनुकूलन स्थितियों को व्युत्पन्न करते हैं। वे स्थापित करते हैं कि इष्टतम नियंत्रित ट्रांजिशन दरें $u^*_t(y, x)$ एक हॉफ-कोले (Hopf-Cole) रूपांतरण का पालन करती हैं: $u^*_t(y, x) = r_t(y, x) \exp(-V_t(y) + V_t(x))$ , जहाँ $V_t$ एक समय-निर्भर विभव (potential) फलन है और $r_t$ संदर्भ दर है।
- इससे श्रोडिंगर पोटेंशियल $(\phi_t, \hat{\phi}_t)$ के लिए समीकरणों का एक युग्मित सिस्टम प्राप्त होता है, जो निरंतर सेटिंग्स में फॉकर-प्लैंक समीकरण के समान है लेकिन ग्राफ के निरंतरता समीकरण (continuity equation) के माध्यम से परिभाषित है।
एल्गोरिदम दृष्टिकोण (gIPF और TD):
- पूरे ग्राफ और समय क्षितिज (time horizon) पर कम्प्यूटेशनल रूप से अत्यधिक खर्चीले ग्लोबल सॉल्वर से बचने के लिए, GSBoG जनरलाइज्ड इटरेटिव प्रोपोर्शनल फिटिंग (gIPF) का उपयोग करते हुए एक कण-आधारित (particle-based), डेटा-संचालित दृष्टिकोण अपनाता है।
- विधि डिंकिन के फॉर्मूला (Dynkin's formula) का उपयोग निरंतर GSB में उपयोग किए जाने वाले फॉरवर्ड-बैकवर्ड स्टोकेस्टिक डिफरेंशियल इक्वेशंस (FBSDEs) के डिस्क्रीट एनालॉग को व्युत्पन्न करने के लिए करती है।
- प्रशिक्षण उद्देश्य में दो वैकल्पिक घटक शामिल हैं:
  - IPF लॉस: एंडपॉइंट मार्जिनल बाधाओं ( $p_0 = \mu, p_1 = \nu$ ) को संतुष्ट करने के लिए सीखे गए पाथ मेजर और संदर्भ प्रक्रिया के बीच विसंगति को कम करता है।
  - टेम्पोरल-डिफरेंस (TD) लॉस: जेनरेटर-अनुमानित वृद्धियों (increments) और वास्तविक प्रक्षेप पथ वृद्धियों के बीच विचलन को दंडित करके अवस्था- और वितरण-निर्भर रनिंग कॉस्ट के साथ निरंतरता को स्पष्ट रूप से लागू करता है।
- एल्गोरिदम लॉग-पोटेंशियल को न्यूरल नेटवर्क (या एम्बेडिंग) का उपयोग करके पैरामीटराइज करता है और केवल स्थानीय ग्राफ पड़ोस पर दरों का मूल्यांकन करते हुए स्टोकेस्टिक ग्रेडिएंट डिसेंट के माध्यम से उन्हें अपडेट करता है।

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

प्रथम डेटा-संचालित GSB ग्राफ पर: यह पेपर किसी भी ग्राफ पर डेटा-संचालित तरीके से 'जनरलाइज्ड श्रोडिंगर ब्रिज' का पहला सूत्रण प्रस्तुत करता है, जो हाल के डिस्क्रीट डिफ्यूजन कार्यों से भिन्न है जो ग्राफ जनरेशन पर ध्यान केंद्रित करते हैं।
स्केलेबल पॉलिसी लर्निंग: ग्लोबल टाइम-एक्सपेंडेड फ्लो को हल करने के बजाय कण-आधारित सैंपलिंग के माध्यम से प्रक्षेप पथ-स्तरीय नीतियों को सीखकर, GSBoG उन बड़े, विरल ग्राफों पर स्केलेबिलिटी प्राप्त करता है जहाँ पारंपरिक डायनेमिक OT विधियाँ मेमोरी बाधाओं के कारण विफल हो जाती हैं।
लागत-जागरूक गतिकी (Cost-Aware Dynamics): ढांचा स्पष्ट रूप से सामान्य रनिंग कॉस्ट (जैसे भीड़भाड़ दंड) के तहत मध्यवर्ती व्यवहार को अनुकूलित करता है, यह सुनिश्चित करता है कि परिणामी नीतियां न केवल टोपोलॉजिकल रूप से व्यवहार्य हों बल्कि परिचालन रूप से भी कुशल हों।
सैद्धांतिक व्युत्पत्ति: लेखक डिस्क्रीट अनुकूलन स्थितियों और CTMC के जेनरेटर पर आधारित एक सुलभ लर्निंग ऑब्जेक्टिव का कठोर व्युत्पन्न प्रदान करते हैं, जो स्टोकेस्टिक कंट्रोल थ्योरी और डिस्क्रीट ग्राफ ट्रांसपोर्ट के बीच के अंतर को पाटते हैं।

प्रायोगिक परिणाम
लेखक तीन चुनौतीपूर्ण वास्तविक दुनिया के ग्राफ टोपोलॉजी पर GSBoG का मूल्यांकन करते हैं:

सप्लाई चेन नेटवर्क (9,559 नोड्स): GSBoG ने ऐसी रूटिंग नीतियां सीखीं जिन्होंने एंडपॉइंट सप्लाई/डिमांड वितरणों से मेल खाया और Attraction Flow और Dynamic W1 flow जैसे बेसलाइनों की तुलना में मध्यवर्ती भीड़भाड़ और पीक नोड ऑक्यूपेंसी को काफी कम कर दिया। विशेष रूप से, GSBoG एकमात्र ऐसा तरीका था जिसने स्पष्ट हार्ड बाधाओं के बिना प्रेरित एज फ्लो को क्षमता सीमाओं के भीतर रखा, जबकि ग्लोबल सॉल्वर (GrSB) मेमोरी की कमी के कारण पूरा होने में विफल रहे।
बैलेंस्ड असाइनमेंट टास्क: अलग-अलग आकार के बाइपार्टाइट ग्राफ ( $n=6$ से $20$) पर, GSBoG ने इष्टतम स्टेटिक OT समाधान के साथ लगभग पूर्ण ओवरलैप ( $n \le 10$ के लिए 100% सटीकता) प्राप्त किया, जबकि एक सॉफ्ट कपलिंग सीखी जिसने असाइनमेंट लागतों को कम किया।
विस्क्रीटाइज्ड मॉलिक्यूलर डायनेमिक्स (Chignolin Folding): प्रोटीन फोल्डिंग के मार्कोव स्टेट मॉडल (MSM) पर लागू करते हुए, GSBoG ने अनफोल्डेड से फोल्डेड अवस्था की ओर दुर्लभ-घटना संक्रमणों (rare-event transitions) को निर्देशित किया। इसने अनियंत्रित गतिकी या कमिटर-गाइडेड बायस की तुलना में 99.7% फोल्डिंग दर हासिल की और ऊर्जा बाधा को काफी कम (1.80 $k_B T$ ) कर दिया, और फ्री एनर्जी रनिंग कॉस्ट को शामिल करने पर इसमें 1.39 $k_B T$ का और सुधार हुआ।

स्केलेबिलिटी विश्लेषण
प्रयोगों से पता चलता है कि GSBoG कुल नोड्स के बजाय स्थानीय ब्रांचिंग फैक्टर के साथ रैखिक रूप से स्केल करता है। $10^6$ नोड्स तक के ग्राफों पर, GSBoG कम मेमोरी उपयोग (~~1.4 GB) और कम रनटाइम (~~1 घंटा) के साथ व्यवहार्य रहा, जबकि डायनेमिक OT विधियाँ या तो असंभव (N/A) हो गईं या उन्हें बहुत अधिक संसाधनों (जैसे 22 GB मेमोरी, 4.6 घंटे) की आवश्यकता पड़ी।

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