🔢 mathematics

RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks

यह शोध पत्र RTD-Lite प्रस्तुत करता है, जो एक स्केलेबल एल्गोरिदम है जो $O(n^2)$ जटिलता के साथ भारित ग्राफ (weighted graphs) की टोपोलॉजिकल कनेक्टिविटी संरचनाओं की कुशलतापूर्वक तुलना करता है, जिससे टोपोलॉजिकल विशेषताओं को संरक्षित करने के लिए आयामी न्यूनीकरण (dimensionality reduction) और न्यूरल नेटवर्क प्रशिक्षण में इसका प्रभावी अनुप्रयोग संभव हो पाता है।

मूल लेखक: Eduard Tulchinskii, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, Serguei Barannikov

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

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

CC BY 4.0

मूल लेखक: Eduard Tulchinskii, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, Serguei Barannikov

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

कल्पना कीजिए कि आपके पास शहर के दो विशाल, जटिल मानचित्र हैं। एक मानचित्र आज की सड़कों को दिखाता है, और दूसरा उसी शहर का थोड़ा अलग संस्करण दिखाता है—शायद कुछ नए पुल बनाए गए हैं, या कुछ पुरानी सड़कें बंद कर दी गई हैं। आपका लक्ष्य यह पता लगाना है कि ये दोनों मानचित्र वास्तव में कितने अलग हैं, न कि केवल व्यक्तिगत सड़कों को देखकर, बल्कि यह समझकर कि बड़ी तस्वीर क्या है: पड़ोस कैसे जुड़ते हैं, यातायात कैसे बहता है, और शहर का "आकार" कैसे बदलता है।

यह वह समस्या है जिसे "RTD-Lite" पेपर हल करने की कोशिश करता है, लेकिन डेटा के बजाय शहरों के लिए।

समस्या: "भारी" कैलकुलेटर

मशीन लर्निंग की दुनिया में, डेटा को अक्सर ग्राफ (बिंदुओं से जुड़ी रेखाएं) के रूप में दर्शाया जाता है। दो ग्राफों की तुलना करने के लिए, वैज्ञानिक एक शक्तिशाली उपकरण का उपयोग करते हैं जिसे टोपोलॉजिकल डेटा एनालिसिस (TDA) कहा जाता है। TDA को एक उन्नत स्कैनर के रूप में समझें जो केवल बिंदुओं को नहीं गिनता; यह डेटा में "छेद" (holes), "क्लस्टर" (clusters), और "लूप" (loops) को भी देखता है।

हालाँकि, इसे करने का मौजूदा तरीका (जिसे RTD कहा जाता है) ऐसा है जैसे आप एक विशाल जिग्सॉ पहेली को हाथ से, एक-एक टुकड़े करके, भारी सीसे के जूते पहनकर सुलझाने की कोशिश कर रहे हों। यह अविश्वसनीय रूप से सटीक है, लेकिन यह इतना धीमा और गणनात्मक रूप से महंगा है कि जब डेटा बहुत बड़ा हो जाता है (जैसे कि एक पूरे शहर के बजाय एक अकेले मोहल्ले का विश्लेषण करना), तो यह कंप्यूटर को क्रैश कर देता है।

समाधान: RTD-Lite (द "लाइट" वर्जन)

लेखक RTD-Lite पेश करते हैं, जो एक नया, सुव्यवस्थित तरीका है। यदि मूल RTD एक भारी-भरकम एक्सकैवेटर (खुदाई करने वाली मशीन) है, तो RTD-Lite एक फुर्तीला, उच्च-गति वाला ड्रोन है।

यह इस तरह काम करता है, एक सरल उपमा का उपयोग करते हुए:

"मिनिमम स्पैनिंग ट्री" (कंकाल):
कल्पना कीजिए कि आप कम से कम बाड़ (fencing) लगाकर एक पड़ोस के सभी घरों को जोड़ना चाहते हैं। आप केवल सबसे आवश्यक सड़कों का उपयोग करके पड़ोस का एक "कंकाल" बनाएंगे। गणित में, इसे मिनिमम स्पैनिंग ट्री (MST) कहा जाता है।

RTD-Lite आपके दोनों मानचित्रों के लिए यह "कंकाल" बनाता है।
फिर यह कंकालों की तुलना करता है। यदि कंकाल अलग दिखते हैं, तो इसका मतलब है कि डेटा की अंतर्निहित संरचना बदल गई है।

"बारकोड" शॉर्टकट:
पुराना तरीका शहर के हर संभव पैमाने (एक अकेले घर से लेकर पूरे महानगर तक) के लिए एक "बारकोड" की गणना करने की कोशिश करता है। इसमें बहुत समय लगता है।
RTD-Lite चतुर है: यह महसूस करता है कि कई लर्निंग कार्यों के लिए, आपको हर छोटी बारीकी की आवश्यकता नहीं होती है। यह एक सरलीकृत बारकोड की गणना करता है जो सबसे महत्वपूर्ण परिवर्तनों पर ध्यान केंद्रित करता है: डेटा के क्लस्टर कैसे जुड़ते या अलग होते हैं।

उपमा: दीवार के अंतर को देखने के लिए हर एक ईंट को गिनने के बजाय, RTD-Lite बस यह जांचता है कि क्या दीवार अभी भी खड़ी है या वह मलबे के ढेर में बदल गई है। यह धूल में उलझने के बजाय बदलाव के "आकार" को पकड़ लेता है।

यह क्यों महत्वपूर्ण है (परिणाम)

पेपर का दावा है कि RTD-Lite तीन मुख्य कारणों से गेम-चेंजर है:

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

सारांश

RTD-Lite जटिल डेटा के "आकार" की तुलना करने के लिए एक नया, सुपर-फास्ट टूल है। यह अतीत की धीमी और भारी गणनाओं को छोड़ने के लिए डेटा के "कंकाल" से जुड़े एक चतुर शॉर्टकट का उपयोग करता है। यह वैज्ञानिकों को विशाल डेटासेट का तेज़ी से विश्लेषण करने की अनुमति देता है और बड़ी तस्वीर देखे बिना बेहतर, अधिक कुशल AI मॉडल को प्रशिक्षित करने में मदद करता है।

लेखकों ने अपना कोड सार्वजनिक कर दिया है, ताकि कोई भी अपने स्वयं के डेटा पर इस टोपोलॉजिकल विश्लेषण के "लाइट" वर्जन को आजमा सके।

तकनीकी सारांश: RTD-Lite

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

भारित ग्राफों (weighted graphs) की तुलना करना मशीन लर्निंग, नेटवर्क विज्ञान और कम्प्यूटेशनल बायोलॉजी में एक मौलिक कार्य है। जबकि टोपोलॉजिकल डेटा एनालिसिस (TDA) मल्टी-स्केल टोपोलॉजिकल फीचर्स को कैप्चर करने के लिए पर्सिस्टेंस बारकोड्स (persistence barcodes) जैसे मजबूत उपकरण प्रदान करता है, भारित ग्राफों की तुलना करने वाली मौजूदा विधियाँ अक्सर कम्प्यूटेशनल अक्षमता से ग्रस्त होती हैं। विशेष रूप से, पूर्ण पर्सिस्टेंट होमोलॉजी (full persistent homology) की गणना करने की उच्च जटिलता वास्तविक दुनिया के लर्निंग कार्यों, जैसे कि न्यूरल नेटवर्क ट्रेनिंग और डाइमेंशनलिटी रिडक्शन में, जहाँ स्केलेबिलिटी महत्वपूर्ण है, में कठोर टोपोलॉजिकल तुलना की प्रयोज्यता को सीमित कर देती है। तुलनात्मक क्रॉस-बारकोड्स (comparative cross-barcodes) पर आधारित रिप्रेजेंटेशन टोपोलॉजी डायवर्जेंस (RTD) मेट्रिक, जो टोपोलॉजिकल विषमता को मापता है, बड़े पैमाने के डेटासेट के लिए कम्प्यूटेशनल रूप से निषेधात्मक हो जाता है।

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

लेखक RTD-Lite पेश करते हैं, जो दो भारित ग्राफों, $A$ और $B$ , के टोपोलॉजिकल फीचर्स की कुशलतापूर्वक तुलना करने के लिए डिज़ाइन किया गया एक स्केलेबल एल्गोरिदम है, जिनके बीच वर्टेक्स सेट्स के लिए एक-से-एक पत्राचार (one-to-one correspondence) है। यह विधि पूर्ण पर्सिस्टेंस बारकोड की गणना किए बिना, मनमाने पैमानों (arbitrary scales) पर कनेक्टिविटी और क्लस्टर संरचनाओं (शून्य-आयामी होमोलॉजी) में विसंगतियों को कैप्चर करने पर ध्यान केंद्रित करती है।

मुख्य तंत्र (Core Mechanism)

एल्गोरिदम इनपुट ग्राफ $A$ और $B$ से निर्मित एक ऑक्जिलरी ग्राफ $C$ पर कार्य करता है:

ग्राफ निर्माण: एक ऑक्जिलरी ग्राफ $C$ बनाया जाता है जिसमें $A$ और $B$ के समान वर्टेक्स सेट होता है। $C$ में एक किनारे (edge) $e$ का भार $c_e = \min(a_e, b_e)$ के रूप में परिभाषित किया जाता है, जहाँ $a_e$ और $b_e$ , $A$ और $B$ में संगत किनारों के भार हैं (अनुपस्थित किनारों को अनंत भार माना जाता है)।
MST उपयोग: यह विधि मिनिमल स्पैनिंग ट्री (MST) का लाभ उठाती है। यह ग्राफ $C$ का MST और ग्राफ $A$ का MST कंप्यूट करती है।
इंटरवल गणना: $C$ के MST में प्रत्येक किनारे $e$ (भार $c_e$ के साथ) के लिए, एल्गोरिदम उस न्यूनतम स्तर $t(e)$ की पहचान करता है जिस पर $C$ में $e$ द्वारा जुड़े दो क्लस्टर $A$ में एक एकल क्लस्टर में विलीन हो जाते हैं। यह तब तक किनारों को पुनरावृत्ति से जोड़ने से प्राप्त होता है जब तक कि $A$ के MST से एक पथ $e$ के सिरों को नहीं जोड़ देता।
बारकोड जनरेशन: परिणाम अंतरालों (intervals) का एक सेट $[c_e, t(e)]$ है, जिसे RTD-Lite बारकोड कहा जाता है। इन अंतरालों की लंबाई का योग, $\sum (t(e) - c_e)$ , RTD-Lite मेट्रिक मान कहलाता है, जिसे $RTDL(A, B)$ द्वारा दर्शाया गया है।

एल्गोरिदम (Algorithms)

पेपर दो एल्गोरिदम प्रस्तावित करता है:

एल्गोरिदम 1 (डायरेक्ट): अंतरालों के पूर्ण सेट (बारकोड) की गणना करता है। इसमें किनारों को सॉर्ट करना, MST बनाना, और कनेक्टिविटी को ट्रैक करने के लिए अस्थायी प्रतियों के साथ एक डिसजॉइंट सेट यूनियन (DSU) संरचना का उपयोग करना शामिल है।
एल्गोरिदम 2 (सिम्प्लीफाइड): व्यक्तिगत अंतरालों के पुनर्निर्माण के बिना केवल अंतराल की लंबाई के योग ($RTDL(A, B) $) की गणना करता है। यह$ A$ के MST में किनारों के भार का योग ( $s_A$ ) और $C$ के MST का भार ( $s_C$ ) निकालता है, और $s_A - s_C$ लौटाता है। यह दृष्टिकोण गणितीय रूप से सिद्ध है कि यह सीधे मेथड के समान ही कुल योग देता है।

जटिलता (Complexity)

दोनों एल्गोरिदम $O(n^2)$ की समय और मेमोरी जटिलता प्राप्त करते हैं, जहाँ $n$ वर्टेक्स की संख्या है। यह मानक RTD की तुलना में एक महत्वपूर्ण सुधार है, जिसमें पर्सिस्टेंस बारकोड गणना शामिल है जो सिमप्लेक्स की संख्या के आधार पर क्यूबिक या उससे अधिक हो सकती है। $O(n^2)$ जटिलता MST निर्माण के लिए प्रिम्स (Prim's) एल्गोरिदम और DSU प्रबंधन के लिए आवश्यक रैखिक ऑपरेशंस से प्राप्त होती है।

अवकलनीयता (Differentiability)

RTD-Lite अंतरालों के छोर (endpoints) किनारों के भार या किनारों के भार के न्यूनतम (minimums) द्वारा निर्धारित होते हैं, जिससे वे (सब-)डिफरेंशिएबल (sub-differentiable) बन जाते हैं। यह गुण इस मेट्रिक को एक डिफरेंशिएबल लॉस फंक्शन के रूप में न्यूरल नेटवर्क ट्रेनिंग में एकीकृत करने की अनुमति देता है, जिससे टोपोलॉजिकल संरचनाओं को बनाए रखने के लिए ग्रेडिएंट-आधारित अनुकूलन सक्षम होता है।

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

कुशल मेट्रिक प्रस्ताव: शून्य-आयामी होमोलॉजी (कनेक्टेड कंपोनेंट्स) पर ध्यान केंद्रित करते हुए, RTD फीचर्स के एक बड़े उपसमुच्चय को कुशलतापूर्वक कंप्यूट करने के लिए RTD-Lite का परिचय।
जटिलता विश्लेषण: यह विस्तृत प्रदर्शन कि RTD-Lite दोनों समय और मेमोरी में द्विघातीय ( $O(n^2)$ ) रूप से स्केल करता है, जिससे यह उन बड़े डेटासेट के लिए व्यवहार्य हो जाता है जहाँ मानक RTD विफल हो जाता है।
लर्निंग में एकीकरण: सीखी गई रिप्रजेंटेशन्स में टोपोलॉजिकल संरचनाओं को बनाए रखने के लिए एक लॉस फंक्शन कंपोनेंट के रूप में RTD-Lite को न्यूरल नेटवर्क ट्रेनिंग में शामिल करने का एक ढांचा।
अनुभवजन्य सत्यापन (Empirical Validation): सिंथेटिक और वास्तविक दुनिया के डेटासेट पर व्यापक प्रयोग जो दिखाते हैं कि RTD-Lite टोपोलॉजिकल अंतरों की प्रभावी ढंग से पहचान करता है, जबकि मौजूदा तरीकों की तुलना में गणना समय को काफी कम कर देता है।

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

लेखकों ने कई परिदृश्यों में RTD-Lite का मूल्यांकन किया:

सिंथेटिक डेटा (क्लस्टर्स और रिंग्स): क्लस्टर्स या रिंग्स की अलग-अलग संख्या वाले पॉइंट क्लाउड्स से जुड़े प्रयोगों में, RTD-Lite ने बढ़ती टोपोलॉजिकल विषमता के प्रति एक मोनोटोनिक रिस्पॉन्स दिखाया। इसके विपरीत, सेंटर्ड कर्नेल एलाइनमेंट (CKA) मेट्रिक ने अराजक व्यवहार प्रदर्शित किया, जो टोपोलॉजिकल परिवर्तनों को लगातार प्रतिबिंबित करने में विफल रहा।
UMAP रिप्रजेंटेशन्स: अलग-अलग पड़ोसी काउंट के साथ UMAP द्वारा उत्पन्न MNIST डेटासेट के 2D रिप्रजेंटेशन्स की तुलना करते समय, RTD-Lite और RTD ने टोपोलॉजिकल संरचना बदलने के साथ मोनोटोनिक रूप से बढ़ती विषमता दिखाई। CKA फिर से एक सुसंगत पैटर्न दिखाने में विफल रहा।
न्यूरल नेटवर्क रिप्रजेंटेशन्स:
- CNNs: CIFAR-10 पर, RTD-Lite ने सटीक रूप से पहचाना कि विभिन्न इनिशियलाइजेशन के साथ प्रशिक्षित नेटवर्क के लेयर्स, अन्य नेटवर्क्स के उनके संबंधित लेयर्स के प्रति सबसे अधिक समान थे। इसने संबंधित लेयर्स को मैच करने में 98% क्लासिफिकेशन एक्यूरेसी हासिल की, जो RTD (98%) और CKA (96%) के तुलनीय है, लेकिन RTD की तुलना में लगभग 6 गुना तेज़ गणना समय के साथ।
- GNNs: Amazon Computers डेटासेट पर, RTD-Lite स्कोर विभिन्न GNN आर्किटेक्चर (GCN, GraphSAGE, GAT, ClusterGCN) के बीच संबंधित लेयर्स के लिए सबसे कम थे, जो मानक RTD स्कोर के साथ अच्छी तरह से संरेखित हैं।
स्केलेबिलिटी: 50,000 वर्टेक्स के डेटासेट (पूर्ण CIFAR-10 ट्रेनिंग सेट) के लिए, RTD-Lite ने 3.75 मिनट में तुलना पूरी की। मानक RTD GPU मेमोरी बाधाओं के कारण विफल हो गया, और CKA ने 36 मिनट लिए।
डाइमेंशनलिटी रिडक्शन (ऑटोएनकोडर्स): डाइमेंशनलिटी रिडक्शन के लिए ऑटोएनकोडर्स (Spheres, F-MNIST, और COIL-20 डेटासेट्स पर) में लॉस फंक्शन के रूप में उपयोग किए जाने पर, RTD-Lite ने ग्लोबल मैनिफोल्ड स्ट्रक्चर को बनाए रखने में RTD-AE और TopoAE के समान प्रदर्शन किया। महत्वपूर्ण रूप से, RTD-Lite के साथ ट्रेनिंग करना काफी तेज़ था और इसमें अक्सर RTD-आधारित लॉस के लिए आवश्यक दो-चरणीय प्रशिक्षण प्रक्रिया (रिकंस्ट्रक्शन लॉस के बाद टोपोलॉजिकल लॉस) की आवश्यकता नहीं थी।

महत्व और दावे (Significance and Claims)

पेपर का दावा है कि RTD-Lite ग्राफ तुलना से जुड़ी महत्वपूर्ण कम्प्यूटेशनल बाधा को दूर करता है। पूर्ण पर्सिस्टेंस बारकोड गणनाओं के ओवरहेड के बिना टोपोलॉजिकल संरचनाओं को बनाए रखते हुए, जटिलता को $O(n^2)$ तक कम करके, यह बड़े पैमाने के लर्निंग कार्यों में कठोर टोपोलॉजिकल विश्लेषण के अनुप्रयोग को सक्षम बनाता है। लेखक दावा करते हैं कि RTD-Lite एक व्यावहारिक उपकरण के रूप में कार्य करता है:

CNNs और GNNs में न्यूरल रिप्रजेंटेशन्स की तुलना करने के लिए।
टोपोलॉजिकल संरचनाओं को बनाए रखते हुए डाइमेंशनलिटी रिडक्शन को बढ़ाने के लिए।
मौजूदा ग्राफ तुलना विधियों के लिए एक स्केलेबल विकल्प के रूप में जो या तो मल्टी-स्केल टोपोलॉजिकल संवेदनशीलता की कमी रखते हैं या स्केल नहीं कर पाते हैं।

यह कार्य RTD-Lite को सभी संदर्भों में पूर्ण TDA के प्रतिस्थापन के रूप में नहीं, बल्कि एक अत्यधिक कुशल सन्निकटन (approximation) के रूप में स्थापित करता है जो आवश्यक टोपोलॉजिकल विसंगतियों (विशेष रूप से क्लस्टर संरचनाओं) को कैप्चर करता है, जो आधुनिक मशीन लर्निंग पाइपलाइनों में एकीकरण के लिए उपयुक्त है।