Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

तकनीकी सारांश: आयामी न्यूनीकरण (Dimensionality Reduction) और नेटवर्क विज्ञान का मिलन

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

यद्यपि UMAP उच्च-आयामी डेटा को विज़ुअलाइज़ करने के लिए एक प्रमुख उपकरण है, मानक विश्लेणात्मक वर्कफ़्लो आमतौर पर परिणामी 2D स्कैटर प्लॉट को ही एकमात्र महत्वपूर्ण आर्टिफैक्ट (artifact) मानते हैं। यह दृष्टिकोण उस समृद्ध, मध्यवर्ती k-निकटतम-पड़ोसी (kNN) ग्राफ को त्याग देता है जिसे UMAP प्रोजेक्शन से पहले आंतरिक रूप से निर्मित करता है। लेखक तर्क देते हैं कि यह ग्राफ मूल उच्च-आयामी स्थान में डेटा मैनिफोल्ड की स्थानीय ज्यामिति और कनेक्टिविटी को 2D लेआउट की तुलना में अधिक निष्ठापूर्वक दर्शाता है, क्योंकि 2D लेआउट में अनिवार्य रूप से विरूपण (distortion) होता है। इस ग्राफ की अनदेखी करके, विश्लेषक उन अर्थ-बोध (sensemaking) कार्यों के अवसरों को खो देते हैं—जैसे कि प्रतिनिधि बिंदुओं की पहचान करना, घनत्व पदानुक्रम (density hierarchies) का विश्लेषण करना और स्थानीय सामंजस्य (local cohesion) का पता लगाना—जो 2D प्रोजेक्शन में ओझल हो जाते हैं।

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

यह शोध पत्र UMAP के आंतरिक kNN ग्राफ को मानक नेटवर्क विज्ञान एल्गोरिदम को सीधे उस पर लागू करके एक "प्रथम-श्रेणी के विश्लेषणात्मक संसाधन" के रूप में उन्नत करने का प्रस्ताव देता है, न कि 2D एम्बेडिंग पर। कार्यप्रणाली ग्राफ के विशिष्ट संरचनात्मक गुणों का लाभ उठाती है: स्थिर आउट-डिग्री $k$, परिवर्तनशील इन-डिग्री, और घनत्व-अनुकूलित एज वेट्स (edge weights)। तीन विशिष्ट एल्गोरिदम को सीधे ग्राफ पर लागू किया गया है:

1. प्रतिनिधि चयन के लिए पेजरैंक (PageRank for Representative Selection):

   • तंत्र: विकृत 2D स्पेस में ज्यामितीय सेंट्रोइड्स (centroids) के आधार पर उदाहरणों (exemplars) को चुनने के बजाय, लेखक kNN ग्राफ पर पेजरैंक लागू करते हैं।
   • तर्क: एक नोड का स्कोर ट्रांसिटिवली (transitive-ly) बढ़ता है; एक बिंदु केवल इसलिए उच्च रैंक नहीं पाता क्योंकि कई नोड्स उसकी ओर संकेत करते हैं (उच्च इन-डिग्री), बल्कि इसलिए पाता है क्योंकि संकेत करने वाले नोड्स स्वयं उच्च रैंक वाले हैं। यह उन वैश्विक रूप से प्रतिनिधि बिंदुओं की पहचान करता है जो मैनिफोल्ड में "अधिकारों" (authorities) के रूप में कार्य करते हैं।
   • कार्यान्वयन: एज वेट्स को UMAP के घनत्व-अनुकूलित सदस्यता स्ट्रेंथ (membership strengths) से प्राप्त किया जाता है।

2. घनत्व पदानिक्रम के लिए k-कोर अपघटन (k-Core Decomposition for Density Hierarchy):

   • तंत्र: लेखक ग्राफ के भीतर घने कोर क्षेत्रों और विरल परिधियों (peripheries) के बीच अंतर करने के लिए k-कोर अपघटन लागू करते हैं।
   • तर्क: मानक डिग्री-आधारित अपघटन के विपरीत, जो निश्चित आउट-डिग्री $k$ द्वारा सीमित है, यह विधि केवल इन-डिग्री के आधार पर अपघटन करती है। यह एक "कोरनेस" (coreness) स्कोर (0, 1, 2...) उत्पन्न करता है जो यह दर्शाता है कि एक नोड क्रमिक रूप से घने और अधिक परस्पर जुड़े उप-ग्राफों में कितनी गहराई से समाहित है।
   • लक्ष्य: उन क्रमिक उप-ग्राफ पदानिक्रमों और क्लस्टर के भीतर उप-श्रेणियों को प्रकट करना जिन्हें डिस्क्रीट क्लस्टरिंग लेबल (जैसे HDBSCAN) नहीं पकड़ पाते हैं।

3. स्थानीय सामंजस्य के लिए क्लस्टरिंग गुणांक (Clustering Coefficient for Local Cohesion):

   • तंत्र: प्रत्येक नोड के लिए क्लस्टरिंग गुणांक (CC) की गणना की जाती है ताकि उसके पड़ोसियों के उस अंश को मापा जा सके जो आपस में भी जुड़े हुए हैं।
   • तर्क: उच्च CC "टाइट-निट" सूक्ष्म-पड़ोसों (micro-neighborhoods) को इंगित करता है जहाँ बिंदु एक-दूसरे को निकटतम पड़ोसी के रूप में परस्पर स्वीकार करते हैं।
   • लक्ष्य: उन सेमेंटिक रूप से सुसंगत सूक्ष्म-क्लस्टरों (जैसे कि हस्तलेखन की विशिष्ट शैलियाँ) का पता लगाना जो 2D प्रोजेक्शन में एक अखंड द्रव्यमान (monolithic mass) के रूप में दिखाई दे सकते हैं।

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

यह शोध पत्र दो प्राथमिक योगदान देता है:

1. वैचारिक बदलाव (Conceptual Shift): यह आयामी न्यूनीकरण और नेटवर्क विज्ञान को जोड़ता है, जिसमें UMAP के त्याग दिए गए kNN ग्राफ को एक प्राथमिक संसाधन के रूप में माना जाता है। यह 2D स्कैटर प्लॉट के पूरक के रूप में अर्थ-बोध (sensemaking) को सक्षम बनाता है, विशेष रूप से प्रतिनिधित्व (representativeness), संरचनात्मक घनत्व और स्थानीय सामंजस्य को संबोधित करता है।
2. अनुभवजन्य सत्यापन (Empirical Validation): MNIST और Fashion MNIST पर मात्रात्मक और गुणात्मक मूल्यांकन के माध्यम से, लेखक प्रदर्शित करते हैं कि उनके ग्राफ-आधारित तरीके उद्देश्य-निर्मित तरीकों की तुलना में प्रतिस्पर्धी या श्रेष्ठ हैं:
   • पेजरैंक बनाम k-मेडॉइड्स (k-medoids): पेजरैंक-चयनित बिंदु k-मेडॉइड्स की तुलना में बेहतर वर्ग संतुलन (निम्न जेन्सन-शैनन डाइवर्जेंस) प्राप्त करते हैं, जो उच्च-विचरण वाले वर्गों से अधिक चयन करने की प्रवृत्ति रखता है। जबकि k-मेडॉइड्स बहुत छोटे बजट पर प्रतिनिधित्व में थोड़ा बेहतर प्रदर्शन करता है, पेजरैंक तेजी से बराबरी कर लेता है और डाउनस्ट्रीम SVM वर्गीकरण सटीकता में प्रतिस्पर्धी बना रहता है। महत्वपूर्ण रूप से, पेजरैंक के लिए केवल एक वैश्विक रैंकिंग गणना की आवश्यकता होती है, जबकि k-मेडॉइड्स को प्रत्येक बजट आकार के लिए पुन: चलाना पड़ता है।
   • k-कोर बनाम HDBSCAN: जहाँ HDBSCAN डिस्क्रीट क्लस्टर लेबल सौंपता है, वहीं k-कोर अपघटन क्लस्टरों के भीतर सेंट्रलिटी का एक क्रमिक पदानिक्रम प्रकट करता है। HDBSCAN सदस्यता संभावनाओं ने कोरनेस के साथ लगभग शून्य सहसंबंध दिखाया, जिससे पुष्टि होती है कि वे अलग-अलग प्रश्नों का उत्तर देते हैं (समूह सदस्यता बनाम समूह के भीतर स्थिति)।
   • क्लस्टरिंग गुणांक: CC उन विशिष्ट सूक्ष्म-पड़ोसों (जैसे अंक "6" की विशिष्ट शैलियाँ) की पहचान करता जो टोपोलॉजिकल रूप से सुसंगत हैं लेकिन 2D में दृष्टिगत रूप से अविभेद्य हो सकते हैं।

परिणाम (Results)

• स्थिरता (Stability): पेजरैंक रैंकिंग पड़ोस के आकार ($k=5$ से $100$) की 20x रेंज में अत्यधिक स्थिर है, जिसका माध्य स्पीयरमैन रैंक सहसंबंध ~0.95 है, जो यह दर्शाता है कि चयनित प्रतिनिधि किसी विशिष्ट$k$ मान का कृत्रिम परिणाम (artifact) नहीं हैं।
• प्रदर्शन (Performance):
  • प्रतिनिधित्व: पेजरैंक निकटतम प्रतिनिधियों के औसत कोसाइन दूरी (cosine distance) में k-मेडॉइड्स को टक्कर देता है, विशेष रूप से जैसे-जैसे चयन बजट बढ़ता है।
  • वर्ग संतुलन: पेज "ग्लोबल क्लास डिस्ट्रीब्यूशन" बनाए रखने में (निम्न JSD के साथ) k-मेडॉइड्स से काफी बेहतर प्रदर्शन करता है, विशेष रूप से $s \ge 200$ बजट पर।
  • डाउनस्ट्रीम उपयोगिता: पेजरैंक-चयनित उदाहरणों पर प्रशिक्षित SVM क्लासिफायर Fashion MNIST पर k-मेडॉइड्स के 2–3 प्रतिशत अंकों के भीतर सटीकता प्राप्त करते हैं और MNIST पर भी तुलनीय हैं।
  • संरचनात्मक अंतर्दृष्टि: k-कोर अपघटन विशिष्ट कोरनेस थ्रेसहोल्ड को फ़िल्टर करके उप-श्रेणियों (जैसे "बैग" क्लास के भीतर मैसेंजर बैग बनाम वेस्ट पैक) को सफलतापूर्वक अलग करता है। उच्च CC मान अंक "6" के क्लस्टर के भीतर सुसंगत हस्तलेखन शैलियों को अलग करता है।

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

लेखक का दावा है कि उनका कार्य UMAP के आंतरिक प्रतिनिधित्व की अनछपी क्षमता को प्रदर्शित करता है। इसके kNN ग्राफ को बनाए रखकर और उसका विश्लेषण करके, विश्लेषक उस संरचनात्मक जानकारी (सेंट्रलिटी, कनेक्टिविटी पदानिक्रम, स्थानीय सामंजस्य) तक पहुँच सकते हैं जो 2D प्रोजेक्शन में खो जाती है या विकृत हो जाती है।

यह शोध पत्र इन ग्राफ एल्गोरिदम को मौजूदा उपकरणों के प्रतिस्थापन के रूप में नहीं, बल्कि पूरक विधियों के रूप में प्रस्तुत करता है जो विशिष्ट लाभ प्रदान करते हैं:

• वे दूरी ऑब्जेक्टिव को अनुकूलित किए बिना प्रतिनिधियों को चुनने का एक पैरामीटर-मुक्त (या स्थिर) तरीका प्रदान करते हैं।
• वे डिस्क्रीट क्लस्टर असाइनमेंट के बजाय घनत्व का एक सतत पदानिक्रम (k-core के माध्यम से) प्रदान करते हैं।
• वे कंप्यूटेशनल रूप से कुशल हैं, जो UMAP के पूर्व-निर्धारित पड़ोसी सरणियों (neighbor arrays) का पुन: उपयोग करके 60,000 बिंदुओं पर 1 सेकंड से कम समय में चलते हैं।

लेखक निष्कर्ष निकालते हैं कि यह दृष्टिकोण समुदाय को "स्कैटर प्लॉट से परे देखने और उस ग्राफ के भीतर देखने" के लिए प्रोत्साहित करता है जिसने इसे बनाया है, जो यह सुझाव देता है कि यह दृष्टिकोण अन्य डाइमेंशनलिटी रिडक्शन विधियों (जैसे TriMap, PaCMAP) तक स्वाभाविक रूप से विस्तारित होता है जो kNN ग्राफ का निर्माण करते हैं।