A discrete Benamou-Brenier formulation of Optimal Transport on graphs

यहाँ कियरन मॉरिस और ओलिवर जॉनसन के शोध पत्र "A discrete Benamou-Brenier formulation of Optimal Transport on graphs" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र ग्राफ (विशेष रूप से डिस्क्रीट डोमेन) पर वासरस्टीन-1 दूरी ($W_1$) को एक बेनामू-ब्रिएर (Benamou-Brenier) डायनेमिक फॉर्मुलेशन का उपयोग करके निरूपित करने की चुनौती को संबोधित करता है।

• संदर्भ: निरंतर स्थानों ($\mathbb{R}^d$) में, बेनामू-ब्रिएर फॉर्मुलेशन स्थिर ऑप्टिमल ट्रांसपोर्ट समस्या (परिवहन लागत को न्यूनतम करना) को एक डायनेमिक समस्या में पुन: पैरामीटराइज़ करता है, जिसमें एक समय-निर्भर प्रायिकता घनत्व $f_t$ और एक वेग क्षेत्र (velocity field) $v_t$ शामिल होता है, जो निरंतरता समीकरण (continuity equation) $\partial_t f_t + \nabla \cdot (f_t v_t) = 0$ द्वारा नियंत्रित होता है।
• अंतराल (The Gap): जबकि $W_2$ (एरबार-मास मेट्रिक) के लिए डिस्क्रीट एनालॉग मौजूद हैं, वे वास्तविक $W_2$ दूरी के अनुरूप नहीं हैं। $W_1$ के लिए, एक वास्तविक डिस्क्रीट बेनामू-ब्रिएर फॉर्मुलेशन पहले केवल पूर्णांक रेखा $\mathbb{Z}$ (हिलियन और जॉनसन) के लिए स्थापित किया गया था। सामान्य ग्राफों पर इस फॉर्मुलेशन को विस्तारित करने और परिणामी जियोडेसिक्स (geodesics) को वर्गीकृत करने की समस्या खुली हुई थी।
• लक्ष्य: एक सामान्य ग्राफ पर एक डिस्क्रीट ट्रांसपोर्ट समीकरण और एक संबद्ध ऊर्जा कार्यात्मक (energy functional) व्युत्पन्न करना जो सटीक रूप से $W_1$ दूरी को पुनः प्राप्त करता है, और इस कार्यात्मक को न्यूनतम करने वाले निरंतर-गति (constant-speed) जियोडेसिक्स को वर्गीकृत करना।

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

अ. डिस्क्रीट ट्रांसपोर्ट समीकरण (Discrete Transport Equation)

लेखक एक नवीन डिस्क्रीट ट्रांसपोर्ट समीकरण पेश करते हैं जिसमें एक ट्रिपल $(f, v, g)$ शामिल है:

• $f(t)$: ग्राफ $G=(V, E)$ के शीर्षों (vertices) $V$ पर परिभाषित प्रायिकता वितरणों का एक पथ।
• $v(t)$: किनारों (edges) $E$ पर परिभाषित एक वेग फलन (velocity function)।
• $g(t)$: किनारों (edges) $E$ पर परिभाषित एक वितरण फलन।

समीकरण को ग्राफ के इंसीडेंस मैट्रिक्स (incidence matrix) $\Omega$ का उपयोग करके परिभाषित किया गया है:
$$\partial_t f = \Omega \cdot (v \cdot g)$$
जहाँ उत्पाद $v \cdot g$ किनारों पर घटक-वार (component-wise) है। यह निरंतरता समीकरण का सामान्यीकरण है। पद $v \cdot g$ किनारों के माध्यम से द्रव्यमान के प्रवाह (flow of mass) को दर्शाता है।

ब. ऊर्जा कार्यात्मक (Energy Functional)

दूरी को फॉर्मुलेट करने के लिए, लेखक $q \geq 1$ के लिए एक ऊर्जा कार्यात्मक $I_q(v, g)$ परिभाषित करते हैं:
$$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q \, dt \right)^{1/q}$$
प्रस्तावित डिस्क्रीट दूरी $V_q(f(0), f(1))$ ट्रांसपोर्ट समीकरण और सीमा स्थितियों $f(0), f(1)$ को संतुष्ट करने वाले सभी $(f, v, g)$ के ऊपर इस ऊर्जा का इन्फिमम (infimum) है।

स. विश्लेषणात्मक दृष्टिकोण (Analytical Approach)

शोध पत्र दो मुख्य चरणों में आगे बढ़ता है:

1. ट्री ग्राफ्स (Tree Graphs): लेखक ट्री (वृक्ष) के लिए समस्या को हल करते हैं। वे ट्रांसपोर्ट समीकरण को उलटने (invert) के लिए टेल डिस्ट्रीब्यूशन (tail distributions) (जो $\mathbb{Z}$ पर संचयी वितरण फलनों के समान हैं) का उपयोग करते हैं। यह उन्हें एक न्यूनतमतम ट्रिपल को स्पष्ट रूप से निर्मित करने और यह सिद्ध करने की अनुमति देता है कि $V_q = W_1$ है।
2. सामान्य ग्राफ (General Graphs): चक्रों (cycles) वाले ग्राफों के लिए, इंसिडेंस मैट्रिक्स व्युत्क्रमणीय (invertible) नहीं होता है। लेखक बेकमैन समस्या (Beckmann problem) पर आधारित एक रिड्यूस्ड फॉर्मुलेशन का उपयोग करते हैं। वे दिखाते हैं कि किसी भी समाधान $(v, g)$ को बिना ऊर्जा बढ़ाए एक "निरंतर गति" (constant speed) समाधान में बदला जा सकता है, जो प्रभावी रूप से खोज स्थान को उन जोड़ों तक सीमित कर देता है जहाँ किसी भी समय किनारों पर प्रवाह का परिमाण समान रहता है।

3. प्रमुख योगदान (Key Contributions)

1. डिस्क्रीट ट्रांसपोर्ट समीकरण: ट्रांसपोर्ट समीकरण $\partial_t f = \Omega \cdot (vg)$ की परिभाषा, जो $v$ और $g$ के साथ एक किनारे-आधारित वितरण पेश करके ग्राफ पर द्रव्यमान संरक्षण को सही ढंग से मॉडल करती है।
2. $W_1$ के लिए बेनामू-ब्रिएर प्रमेय:
   • प्रमेय 1 (Trees): सिद्ध करता है कि रूटेड ट्री के लिए, ट्रांसपोर्ट समीकरण के अधीन ऊर्जा कार्यात्मक $I_2$ (और सामान्यतः $I_q$) का इन्फिमम सटीक रूप से स्थिर $W_1$ दूरी है।
   • प्रमेय 2 (General Graphs): इसे किसी भी जुड़े हुए ग्राफ तक विस्तारित करता है, यह सिद्ध करते हुए कि सभी $q \geq 1$ के लिए $V_q(f(0), f(1)) = W_1(f(0), f(1))$ है।
3. जियोडेसिक्स का लक्षण वर्णन (Characterization of Geodesics):
   • प्रपोजिशन 4: यह स्थापित करता है कि निरंतर गति ($|v_k| = c$) वाले न्यूनतमतम ट्रिपल्स $(v, g)$ द्वारा प्रेरित पथ ही निरंतर गति $W_1$ जियोडेसिक्स हैं।
   • कोरोलरी 1: यह प्रदर्शित करता है कि कॉन्वेक्स इंटरपोलेशन (convex interpolations) $f(t) = (1-t)f(0) + tf(1)$हमेशा ग्राफ पर निरंतर गति$W_1$ जियोडेसिक्स होते हैं।
   • गैर-विशिष्टता (Non-Uniqueness): शोध पत्र रेखांकित करता है कि जियोडेसिक्स अद्वितीय नहीं हैं। उदाहरण के लिए, दो बाइनोमियल वितरणों के बीच, वितरणों का रैखिक इंटरपोलेशन (कॉन्वेक्स) और अंतर्निहित पैरामीटर $p(t)$ का इंटरपोलेशन (गैर-रैखिक) दोनों ही वैध निरंतर गति जियोडेसिक्स हो सकते हैं।

4. मुख्य परिणाम (Key Results)

• फॉर्मुलेशन की समानता: डायनेमिक फॉर्मुलेशन (समय के ऊपर गतिज ऊर्जा को न्यूनतम करना) ग्राफ पर $W_1$ के लिए स्थिर कांतोरोविच (Kantorovich) फॉर्मुलेशन के गणितीय रूप से समकक्ष है।
• निरंतर गति समाधान: लेखक सिद्ध करते हैं कि किसी भी वैध ट्रांसपोर्ट पथ के लिए, एक "निरंतर गति" री-पैरामीट्रिज़ेशन मौजूद है जो ऊर्जा को न्यूनतम करता है। इस इष्टतम अवस्था में, वेग का परिमाण $|v|$ समय में स्थिर रहता है।
• मेट्रिक गुण: कार्यात्मक $V_q$ त्रिकोण असमानता (triangle inequality), समरूपता (symmetry) और धनात्मक निश्चितता (positive definiteness) का पालन करता है, जो पुष्टि करता है कि यह ग्राफ पर प्रायिकता मापों के स्थान पर एक वैध मेट्रिक है।
• बेकमैन से संबंध: इस फॉर्मुलेशन को बेकमैन फॉर्मुलेशन के एक समय-निर्भर सामान्यीकरण के रूप में दिखाया गया है (जो समय-स्वतंत्र है और कुल प्रवाह लागत को न्यूनतम करता है)।

5. महत्व (Significance)

• सैद्धांतिक एकीकरण: यह कार्य डिस्क्रीट सेटिंग में स्थिर ऑप्टिकल ट्रांसपोर्ट (कांतोरोविच/बेकमैन) और डायनेमिक ऑप्टिकल ट्रांसपोर्ट (बेनामू-ब्रिएर) के बीच के अंतर को पाटता है। यह सामान्य ग्राफों पर एक वास्तविक $W_1$ डायनेमिक फॉर्मुलेशन खोजने की खुली समस्या को हल करता है।
• एल्गोरिद्मिक निहितार्थ: जियोडेसिक्स को ट्रांसपोर्ट समीकरण के माध्यम से वर्गीकृत करके, शोध पत्र ग्राफ पर वासरस्टीन ग्रेडिएंट फ्लो (Wasserstein Gradient Flows) के लिए एक ढांचा प्रदान करता है। यह मशीन लर्निंग अनुप्रयोगों के लिए महत्वपूर्ण है जहाँ आवश्यकता होती है कि नेटवर्क संरचनाओं (जैसे सामाजिक नेटवर्क, जैविक नेटवर्क) पर प्रायिकता वितरण विकसित हों जबकि परिवहन लागत न्यूनतम रहे।
• ज्यामितीय अंतर्दृष्टि: जियोडेसिक्स का वर्गीकरण प्रकट करता है कि ग्राफ पर, वितरणों के बीच सबसे "सीधा" पथ अद्वितीय नहीं है। रैखिक (कॉन्वेक्स) और गैर-रैखिक (पैरामीटर-आधारित) दोनों जियोडेसिक्स का अस्तित्व नेटवर्क टोपोलॉजी के माध्यम से प्रायिकता द्रव्यमान कैसे घूमता है, इस पर नए दृष्टिकोण प्रदान करता है।
• सामान्यीकरण क्षमता: इंसिडेंस मैट्रिक्स और टेल डिस्ट्रीब्यूशन का उपयोग करने वाली पद्धति एक मजबूत टूलकिट प्रदान करती है, जो साधारण पथ या ट्री से परे, मनमाने डिस्क्रीट स्ट्रक्चर पर ऑप्टिमल ट्रांसपोर्ट के विश्लेषण की अनुमति देती है।

संक्षेप में, मॉरिस और जॉनसन ने डिस्क्रीट ग्राफ पर बेनामू-ब्रिएर फॉर्मुलेशन को सफलतापूर्वक सामान्यीकृत किया है, यह सिद्ध करते हुए कि एक विशिष्ट ऊर्जा कार्यात्मक का डायनेमिक मिनिमाइजेशन सटीक $W_1$ दूरी को पुनः प्राप्त करता है और उन जियोडेसिक्स का पूर्ण लक्षण वर्णन प्रदान करता है जो इस न्यूनतम को प्राप्त करते हैं।