📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

यह शोध पत्र ग्राफ और नोड-एट्रिब्यूटेड ग्राफ की तुलना करने के लिए ग्रोमोव-वासरस्टीन (Gromov–Wasserstein) और फ्यूज्ड ग्रोमोव-वासरस्टीन (fused Gromov–Wasserstein) दूरियों का उपयोग करके $k$ -निकटतम पड़ोसी (k-nearest neighbors) वर्गीकरण को लागू करता है, और इन क्लासिफायर्स की सार्वभौमिक निरंतरता (universal consistency) को सिद्ध करते हुए कई डेटासेट्स पर उनके मजबूत अनुभवजन्य प्रदर्शन (empirical performance) को प्रदर्शित करता है।

मूल लेखक: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

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

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

CC BY 4.0

मूल लेखक: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

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

कल्पना कीजिए कि आप अलग-अलग प्रकार की वस्तुओं के एक विशाल ढेर को छाँटने (sort करने) की कोशिश कर रहे हैं। कुछ सरल आकृतियाँ हैं, तो कुछ जटिल नेटवर्क जैसे कि सबवे मैप या सामाजिक समूह (social circles)। आपका लक्ष्य यह पता लगाना है कि एक नया, अनदेखा ऑब्जेक्ट किस श्रेणी में आता है, और इसके लिए आप उन वस्तुओं को देखते हैं जिन्हें आप पहले से जानते हैं। यह एक $k$ -नेरेस्ट नेबर्स ( $k$ -NN) क्लासिफायर का काम है।

$k$ -NN को अपने पड़ोसियों के बीच एक "लोकप्रियता प्रतियोगिता" (popularity contest) की तरह समझें। यदि आप एक नए ऑब्जेक्ट को ज्ञात वस्तुओं के एक कमरे में छोड़ देते हैं, तो आप उसके $k$ सबसे करीबी पड़ोसियों को देखते हैं। यदि उनमें से अधिकांश पड़ोसी "बिल्लियाँ" हैं, तो आप अनुमान लगाते हैं कि वह नया ऑब्जेक्ट भी एक बिल्ली ही है।

समस्या यह है: जब वस्तुएं जटिल नेटवर्क (ग्राफ) हों जिनका कोई मानक आकार या रूप न हो, तो "निकटता" (closeness) को कैसे मापा जाए? आप किसी मानचित्र पर दो बिंदुओं के बीच की दूरी को सीधे नहीं माप सकते।

यह शोध पत्र एक चतुर नया तरीका पेश करता है जिससे इस दूरी को ग्रोमो-वॉसरसेइन (Gromov–Wasserstein - GW) और फ्यूज्ड ग्रोमो-वॉसरसेइन (fGW) का उपयोग करके मापा जा सकता है। यहाँ इसका सरल विवरण दिया गया है:

1. समस्या: सेब की तुलना संत से (और संतों की तुलना हवाई जहाज से)

आमतौर पर, दो चीजों की तुलना करने के लिए, उन्हें एक ही आकार का होना चाहिए। यदि आप दो ग्राफ (बिंदुओं और रेखाओं के नेटवर्क) की तुलना करना चाहते हैं, तो पारंपरिक तरीके अक्सर उन्हें एक ही आकार में बदलने के लिए मजबूर करते हैं या उन्हें संख्याओं की एक सूची (एक "एम्बेडिंग") में बदल देते हैं। यह एक छोटे पारिवारिक वंश वृक्ष (family tree) की तुलना एक विशाल कॉर्पोरेट संगठनात्मक चार्ट से करने जैसा है, जिसमें दोनों को एक ही छोटे बॉक्स में दबा दिया जाता है। इससे जानकारी का नुकसान होता है।

2. समाधान: एक "आकार बदलने वाला" रूलर (The "Shape-Shifting" Ruler)

लेखक एक गणितीय उपकरण का उपयोग करते हैं जिसे ग्रोमो-वॉसरसेइन दूरी (Gromov–Wasserstein distance) कहा जाता है।

उपमा: कल्पना कीजिए कि आपके पास दो अलग-अलग शहर हैं। एक ग्रिड (जैसे मैनहट्टन) है, और दूसरा घुमावदार सड़कों का जाल (जैसे सैन फ्रांसिस्को) है। वे दिखने में बिल्कुल अलग हैं।
GW का जादू: सीधे सड़कों की तुलना करने के बजाय, GW पूछता है: "यदि मैं शहर A के लोगों को शहर B के जनसंख्या घनत्व के अनुसार जादुई रूप से पुनर्व्यवस्थित कर सकूँ, तो पड़ोसियों के बीच का 'संबंधात्मक अंतर' (relationship distance) कितना बदल जाएगा?"
इसे इस बात की परवाह नहीं है कि शहरों में 100 लोग हैं या 1,000। इसे केवल संबंधों के पैटर्न की परवाह है। यदि शहर A में एक "हब" है जिसके कई कनेक्शन हैं और शहर B में भी एक समान "हब" है, तो GW कहता है, "ये दोनों शहर संरचनात्मक रूप से समान हैं," भले ही वे मानचित्र पर अलग दिखते हों।

3. "फीचर्स" जोड़ना: फ्यूज्ड संस्करण

कभी-कभी आपके नेटवर्क के बिंदुओं में अतिरिक्त जानकारी होती है। उदाहरण के लिए, एक अणु (molecule) ग्राफ में, प्रत्येक परमाणु का एक विशिष्ट प्रकार (कार्बन, ऑक्सीजन) होता है। एक सामाजिक ग्राफ में, प्रत्येक व्यक्ति का एक पेशा होता है।

उपमा: कल्पना कीजिए कि आप फिर से दो शहरों की तुलना कर रहे हैं। GW सड़क के पैटर्न को देखता है। लेकिन क्या आप इमारतों के प्रकारों की भी तुलना करना चाहते हैं?
fGW का जादू: फ्यूज्ड ग्रोमो-वॉसरसेइन (fGW) दूरी इन दोनों को एक साथ करती है। यह जाँचती है कि क्या सड़क के पैटर्न मेल खाते हैं और क्या समान स्थानों पर इमारतें एक ही प्रकार की हैं। यह एक ऐसे रूलर की तरह है जो शहर के आकार और घरों के रंग, दोनों को मापता है।

4. बड़ा दावा: "यह हमेशा काम करता है" (यूनिवर्सल कंसिस्टेंसी)

लेखकों ने केवल एक नया रूलर नहीं बनाया; उन्होंने गणितीय रूप से सिद्ध किया कि इस रूलर का उपयोग $k$ -NN विधि के साथ करने पर यह लंबे समय में हमेशा काम करता है।

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

5. प्रयोग: क्या यह वास्तव में मदद करता है?

लेखकों ने वास्तविक दुनिया के डेटा पर अपने तरीके का परीक्षण किया:

अणु (Molecules): रसायनों को उनकी संरचना और परमाणु प्रकारों के आधार पर छाँटना।
सामाजिक नेटवर्क: मूवी सहयोग नेटवर्क (जैसे, "एक्शन" फिल्में बनाम "रोमांस" फिल्में) को छाँटना।
सिंथेटिक डेटा: सीमाओं का परीक्षण करने के लिए बनाए गए कृत्रिम नेटवर्क।

परिणाम:

उनके तरीके (GW- $k$ -NN और fGW- $k$ -NN) ने बहुत अच्छा प्रदर्शन किया, और अक्सर ग्राफ न्यूरल नेटवर्क (GCNs) और जटिल ग्राफ कर्नेल जैसे लोकप्रिय तरीकों को पछाड़ दिया या उनके बराबर रहे।
मुख्य निष्कर्ष: अणुओं के लिए अतिरिक्त डेटा (परमाणु प्रकार) के मामले में, "फ्यूज्ड" संस्करण (fGW) स्पष्ट विजेता था। इसने दिखाया कि संरचना और फीचर्स दोनों को एक साथ देखना, केवल एक को देखने की तुलना में बेहतर है।
दक्षता (Efficiency): हालांकि गणित भारी है, लेकिन यह तरीका अन्य जटिल तरीकों की तुलना में आश्चर्यजनक रूप से तेज़ और कुशल था, विशेष रूप से बिना विशेषताओं वाले (non-attributed) ग्राफ के लिए।

सारांश

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

उन्होंने क्या दावा नहीं किया:

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

तकनीकी सारांश: ग्रॉमोव-वासरस्टीन स्पेस में $k$ -निकटतम पड़ोसी ( $k$ -Nearest Neighbors)

समस्या विवरण
यह शोध पत्र ग्राफ-संरचित डेटा (जिसमें बिना विशेषता वाले ग्राफ और नोड-विशेषता वाले ग्राफ दोनों शामिल हैं) के वर्गीकरण की चुनौती को एक कठोर मीट्रिक लर्निंग फ्रेमवर्क के भीतर संबोधित करता है। पारंपरिक $k$ -निकटतम पड़ोसी ( $k$ -NN) क्लासिफायर उन दूरी कार्यों (distance functions) पर निर्भर करते हैं जो यूक्लिडियन या मानक मीट्रिक स्पेस में परिभाषित होते हैं। हालांकि, ग्राफ अक्सर जटिल संरचनाएं रखते हैं जहाँ प्रत्यक्ष तुलना करना कठिन होता है, विशेष रूप से जब ग्राफ में नोड्स की संख्या भिन्न हो या उनमें कोई कैनोनिकल एम्बेडिंग (canonical embedding) का अभाव हो। जबकि ग्रॉमोव-वासरस्टीन (GW) दूरी मीट्रिक मेजर स्पेस (mm-spaces) की तुलना करने के लिए एक ढांचा प्रदान करती है और फ्यूज्ड ग्रॉमोव-वासरस्टीन (fGW) दूरी इस विस्तार को नोड विशेषताओं को शामिल करने के लिए करती है, इन विशिष्ट मीट्रिक स्पेस के भीतर कार्य करने वाले $k$ -NN क्लासिफायर्स के सैद्धांतिक गुणों के बारे में पहले अज्ञात था। विशेष रूप से, यह स्पष्ट नहीं था कि क्या $k$ -NN सार्वभौमिक रूप से सुसंगत (universally consistent) है (अर्थात, इष्टतम बेयस जोखिम की ओर अभिसरण करता है) जब अंतर्निहित स्थान GW या fGW दूरियों के साथ ग्राफ का स्थान हो।

कार्यप्रणाली
लेखक GW और fGW दूरियों का उपयोग करके $k$ -NN वर्गीकरण को लागू करते हैं और इसकी सैद्धांतिक सुसंगतता (theoretical consistency) की जांच करते हैं। उनकी कार्यप्रणाली का मुख्य हिस्सा आवश्यक शर्तों को पूरा करने के लिए विचाराधीन मीट्रिक स्पेस के टोपोलॉजिकल गुणों को स्थापित करना है।

मीट्रिक स्पेस परिभाषाएं:
- GW स्पेस ( $\mathbb{X}$ ): परिमित सपोर्ट और यूनिफॉर्म प्रोबेबिलिटी मेजर वाले mm-spaces के तुल्यता वर्गों (equivalence classes) का स्थान, जो $p=2$ ग्रॉमोव-वासरस्टीन दूरी से सुसज्जित है। यह बिना विशेषता वाले ग्राफों को मॉडल करता है।
- fGW स्पेस ( $\mathbb{Y}^f$ ): संरचित वस्तुओं (फीचर मैप्स के साथ mm-spaces) के कमजोर आइसोमोर्फिज्म वर्गों का स्थान, जो फ्यूज्ड ग्रॉमोव-वासरस्टीन ( $p=1, q=2$ ) से सुसज्जित है। यह नोड-विशेषता वाले ग्राफों को मॉडल करता है।
सैद्धांतिक ढांचा:
लेखक लर्निंग थ्योरी के स्थापित परिणामों (विशेष रूप से चौधरी और दासगुप्ता [9]) पर भरोसा करते हैं जो यह बताते हैं कि $k$ -NN एक सेपरेबल मीट्रिक स्पेस पर सार्वभौमिक रूप से सुसंगत है यदि उस स्थान में $\sigma$ -फाइनाइट मीट्रिक डायमेंशन (लेबेग डिफरेंशिएशन स्थिति से संबंधित एक गुण) हो। GW और fGW स्पेस के लिए इसे सिद्ध करने के लिए, लेखक:
- इन ढांचों के भीतर $n$ -पॉइंट स्पेस के लिए परिमित-आयामी मॉडल (finite-dimensional models) का निर्माण करते हैं।
- $n$ -पॉइंट ग्राफों के स्पेस और यूक्लिडियन मैट्रिसेस के विशिष्ट कोटिएंट स्पेस (GW के लिए) तथा मैट्रिसेस और फीचर वेक्टर्स के उत्पाद स्पेस (fGW के लिए) के बीच बाय-लिप्सचिट्ज मैपिंग (bi-Lipschitz maps) के अस्तित्व को प्रदर्शित करते हैं।
- यह सिद्ध करते हैं कि इन कोटिएंट स्पेसों में परिमित असौड-नागाटा (Assouad-Nagata) डायमेंशन है।
- लेम्मा 2.4 का उपयोग करके यह दिखाने के लिए कि परिमित आयाम वाले स्थानों के बीच बाय-लिप्सचिट्ज मैपिंग का अस्तित्व यह दर्शाता है कि लक्ष्य स्थानों ( $\mathbb{X}$ और $\mathbb{Y}^f$ ) में $\sigma$ -फाइनाइट मीट्रिक डायमेंशन है।
संख्यात्मक प्रयोग:
लेखक सात बेंचमार्क डेटासेट्स पर GW- $k_n$ -NN और fGW- $k_n$ -NN के प्रदर्शन का मूल्यांकन करते हैं:
- विशेषता वाले ग्राफ (Attributed Graphs): BZR, COX-2, और PROTEINS (आणविक डेटासेट)।
- बिना विशेषता वाले ग्राफ (Non-attributed Graphs): IMDb-B, IMDb-M (सोशल नेटवर्क), और दो सिंथेटिक डेटासेट (ERSBM1, ERSBM2)।
- बेसलाइन्स (Baselines): ग्राफ कन्वोल्यूशनल नेटवर्क्स (GCN), विभिन्न ग्राफ कर्नेल विधियों (Shortest Path, Graphlet, HOPPER, Propagation), और GW/fGW कर्नेल्स का उपयोग करने वाले SVMs के साथ तुलना।

प्रमुख योगदान
इस कार्य का प्राथमिक योगदान GW और fGW दूरियों का उपयोग करके ग्राफ वर्गीकरण के संदर्भ में $k$ -NN क्लासिफायर्स की सार्वभौमिक सुसंगतता (universal consistency) का प्रमाण है।

सैद्धांतिक परिणाम:
- थ्योरम 1.8: सिद्ध करता है कि $k \to \infty$ और $k/n \to 0$ की शर्तों के तहत ग्राफ स्पेस $(\mathbb{X}, GW_2)$ पर GW- $k_n$ -NN क्लासिफायर सार्वभौमिक रूप से कमजोर रूप से सुसंगत (weakly consistent) है। यह $k/\log(n) \to \infty$ होने पर सार्वभौमिक रूप से दृढ़ रूप से सुसंगत (strongly consistent) है।
- थ्योरम 1.9: नोड-विशेषता वाले ग्राफों के स्पेस $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ पर fGW- $k_n$ -NN क्लासिफायर के लिए समान सुसंगतता परिणामों को सिद्ध करता है।
- ये परिणाम यह स्थापित करके प्राप्त किए गए हैं कि दोनों स्पेस सेपरेबल हैं और $\sigma$ -फाइनाइट मीट्रिक डायमेंशन रखते हैं, जो कि यूक्लिडियन स्पेस के कोटिएंट स्पेस में बाय-लिप्सचिट्ज एम्बेडिंग के माध्यम से प्राप्त किया गया है।
अनुभवजन्य परिणाम (Empirical Results):
- विशेषता वाले ग्राफ डेटासेट्स (BZR, COX-2, PROTEINS) पर, fGW- $k_n$ -NN ने लगातार उच्चतम औसत सटीकता प्राप्त की, जिसने GCNs और अन्य कर्नेल-आधारित विधियों को पछाड़ दिया। GW- $k_n$ -NN ने भी प्रतिस्पर्धी प्रदर्शन किया।
- बिना विशेषता वाले डेटासेट्स पर, GW- $k_n$ -NN ने ERSBM2 सिंथेटिक डेटासेट पर 100% सटीकता प्राप्त की और IMDb-B पर मजबूत प्रदर्शन किया, जो अक्सर ग्राफ कर्नेल्स और GCNs से बेहतर रहा।
- लेखक नोट करते हैं कि हालांकि GW/fGW विधियां व्याख्या योग्य (interpretable) हैं (छोटा अंतर संरचनात्मक समानता को दर्शाता है), वे कुछ कर्नेल विधियों की तुलना में गणनात्मक रूप से गहन हो सकती हैं, हालांकि वे कुछ संदर्भों में GW कर्नेल्स का उपयोग करने वाले SVMs की तुलना में दक्षता में सुधार प्रदान करते हैं।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह ग्रॉमोव-वासरस्टीन फ्रेमवर्क के भीतर मीट्रिक क्लासिफायर्स जैसे $k$ -NN के उपयोग के लिए एक सैद्धांतिक आधार स्थापित करता है। सार्वभौमिक सुसंगतता को सिद्ध करके, लेखक तर्क देते हैं कि ये विधियां केवल एक ह्यूरिस्टिक (heuristic) नहीं हैं बल्कि ग्राफ वर्गीकरण कार्यों के लिए सैद्धांतिक रूप से सुदृढ़ हैं।

इसका महत्व ऑप्टिमल ट्रांसपोर्ट थ्योरी और स्ट्रक्चर्ड डेटा के लिए सांख्यिकीय लर्निंग थ्योरी के बीच के अंतर को पाटने में निहित है। लेखक जोर देते हैं कि उनका दृष्टिकोण एक "अत्यधिक व्याख्या योग्य फ्रेमवर्क" प्रदान करता है जहाँ ग्राफों के बीच की दूरी सीधे संरचनात्मक समानता को मापती है (आइसोमोर्फिज्म शून्य दूरी को दर्शाता है)। वे स्पष्ट रूप से कहते हैं कि, उनकी जानकारी के अनुसार, यह ग्राफ वर्गीकरण के लिए GW- $k$ -NN का पहला अनुप्रयोग और इसकी सुसंगतता का पहला सैद्धांतिक प्रमाण है।

शोध पत्र भविष्य के सामान्यीकरण के संबंध में विनम्र रहता है। यह स्वीकार करता है कि हालांकि सुसंगतता विशिष्ट मापदंडों ( $p=2$ के लिए GW, $p=1, q=2$ के लिए fGW) के लिए सिद्ध की गई है, लेकिन यह एक खुला प्रश्न बना हुआ है कि क्या ये परिणाम अन्य पैरामीटर विकल्पों या अधिक सामान्य Z-ग्रॉमोव-वासरस्टीन सेटिंग्स में भी लागू होते हैं। लेखक अनुमान लगाते हैं कि, वासरस्टीन स्पेस के समान, विशिष्ट प्रतिबंधों के बिना पूर्ण सामान्यता में सार्वभौमिक सुसंगतता बनी रह सकती है।