तकनीकी सारांश: पदानुक्रमों के सघन ज्यामितीय निरूपण (Compact Geometric Representations of Hierarchies)

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

यह शोध पत्र पदानुक्रमित डेटा पुनर्प्राप्ति (hierarchical data retrieval) के लिए ज्यामितीय निरूपण (एम्बेडिंग्स) की गणना करने की चुनौती को संबोधित करता है। आधुनिक मशीन लर्निंग में, डेंस रिट्रीवल (dense retrieval) आमतौर पर क्वेरी और दस्तावेज़ों को एक साझा एम्बेडिंग स्पेस में मैप करता है जहाँ प्रासंगिकता उनके वेक्टर्स के आंतरिक गुणनफल (inner product) द्वारा निर्धारित होती है। हालांकि यह 'फ्लैट रिट्रीवल' के लिए प्रभावी है, लेकिन यह दृष्टिकोण तब चुनौतियों का सामना करता है जब प्रासंगिकता जटिल तर्क या पदानुक्रमित संरचनाओं, जैसे कि निर्देशित अचक्रीय ग्राफ़ (Directed Acyclic Graphs - DAGs) द्वारा परिभाषित होती है।

विशेष रूप से, यह शोध पत्र रीचेबिलिटी एम्बेडिंग्स (reachability embeddings) की जांच करता है। एक DAG $G=(V, E)$ के लिए, लक्ष्य दो मैपिंग $a, b: V \to \mathbb{R}^d$ का निर्माण करना है ताकि किसी भी नोड्स के जोड़े $u, v$ के लिए, आंतरिक गुणनफल $\langle a(u), b(v) \rangle > 0$ हो यदि और केवल यदि $v$, $u$ से $G$ में सुलभ (reachable) है (इसे $u \leadsto_G v$ द्वारा दर्शाया गया है)।

पिछले कार्य (You et al., 2025) ने स्थापित किया कि यदि किसी नोड के वंशजों (descendants) की संख्या $s$ द्वारा सीमित है, तो $O(s \log n)$ आयाम में एम्बेडिंग्स मौजूद होते हैं। हालांकि, यह सीमा गहरे पदानुक्रमों (जैसे कि ट्री जहाँ $s \approx n$) के लिए काफी खराब हो जाती है, जिससे कुल नोड्स की संख्या के समान आयामों की आवश्यकता हो सकती है। केंद्रीय प्रश्न यह है कि क्या सघन (compact) एम्बेडिंग्स मौजूद हैं जिनका आयाम कुल नोड संख्या या गहराई के बजाय विशिष्ट संरचनात्मक ग्राफ मापदंडों (जैसे कि treewidth या cross-edges) पर निर्भर करता है।

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

लेखक कम आयाम प्राप्त करने के लिए विशिष्ट ग्राफ मापदंडों का लाभ उठाने वाले 'कंस्ट्रक्टिव एल्गोरिदम' प्रस्तावित करते हैं। कार्यप्रणाली तीन मुख्य सैद्धांतिक योगदानों में विभाजित है:

1. निर्देशित वृक्ष और वन (Directed Trees and Forests)

मूलित निर्देशित वृक्षों (rooted directed trees) के लिए, लेखक एक मानक डेप्थ-फर्स्ट सर्च (DFS) से प्राप्त 'डिस्कवरी' और 'फिनिशिंग' समय का उपयोग करते हैं।

• तंत्र (Mechanism): एक DFS ट्री में, $v$, $u$ का वंशज है यदि और केवल यदि अंतराल $[d_v, f_v]$, $[d_u, f_u]$ के भीतर समाहित है।
• निर्माण (Construction): वे $\mathbb{R}^3$ में वेक्टर्स को इस प्रकार परिभाषित करते हैं कि आंतरिक गुणनफल $(f_u - d_v)(d_v - d_u)$ के बराबर होता है। यह उत्पाद धनात्मक होता है यदि और केवल यदि $d_u < d_v < f_u$, जो ठीक से रीचेबिलिटी स्थिति के अनुरूप है।
• परिणाम: यह किसी भी निर्देशित वृक्ष के लिए एक स्थिर आयाम एम्बेडिंग ($d=3$) प्रदान करता है, जो वृक्ष के आकार या गहराई से स्वतंत्र है।

2. क्रॉस-एजेस द्वारा पैरामीटराइज्ड DAGs (DAGs Parameterized by Cross-Edges)

सामान्य DAGs के लिए, लेखक स्पैनिंग फॉरेस्ट (spanning forest) के एम्बेडिंग को "क्रॉस-एजेस" (वे किनारे जो चुने गए स्पैनिंग फॉरेस्ट का हिस्सा नहीं हैं) को ध्यान में रखते हुए विस्तारित करते हैं।

• तंत्र: वे स्पैनिंग फॉरेस्ट के लिए 3-आयामी एम्बेडिंग से शुरुआत करते हैं। प्रत्येक क्रॉस-एज $(x_i, y_i)$ के लिए, वे एक अतिरिक्त समन्वय (coordinate) पेश करते हैं।
• निर्माण: नया समन्वय तब सक्रिय होता है (एक बड़े मान $M$ के साथ) जब क्वेरी नोड $x_i$ तक पहुँच सकता है और दस्तावेज़ नोड $y_i$ से सुलभ है। एक पर्याप्त बड़ा $M$ यह सुनिश्चित करता है कि क्रॉस-एज का उपयोग करने वाला कोई भी पथ धनात्मक आंतरिक गुणनफल उत्पन्न करता है, जबकि अप्राप्य जोड़े ऐसा नहीं करते हैं।
• परिणाम: एम्बेडिंग आयाम $d = 3 + k$ है, जहाँ $k$ क्रॉस-एजेस की संख्या है।

3. ट्रेewidth द्वारा पैरामीटराइज्ड DAGs (DAGs Parameterized by Treewidth)

सीमित ट्रेewidth $t$ वाले ग्राफों के लिए, लेखक संतुलित वर्टेक्स सेपरेटर्स (balanced vertex separators) पर आधारित एक पुनरावर्ती निर्माण (recursive construction) का उपयोग करते हैं।

• तंत्र: इस गुण का उपयोग करते हुए कि ट्रेewidth $t$ वाले ग्राफों में आकार $\le t+1$ के सेपरेटर्स होते हैं जो ग्राफ को अधिकतम $2n/3$ आकार के घटकों में विभाजित करते हैं, वे उप-ग्राफों को पुनरावर्ती रूप से एम्बेड करते हैं।
• निर्माण: एम्बेडिंग तीन भागों से मिलकर बना है:
  1. पुनरावर्ती निर्देशांक (Recursive Coordinates): उप-घटकों के लिए एम्बेडिंग्स।
  2. सेपरेशन निर्देशांक (Separation Coordinates): दो निर्देशांक जो $(u, v)$ के जोड़ों पर, जहाँ $u$ और $v$ अलग-अलग घटकों में स्थित हैं, एक बड़ा नकारात्मक दंड (penalty) लगाते हैं, जिससे स्प्लिट के पार गलत सकारात्मक (false positives) को रोका जा सके।
  3. कनेक्शन निर्देशांक (Connection Coordinates): $|S|$ निर्देशांक (जहाँ $S$ सेपरेटर है) जो एक बड़ा धनात्मक पद योगदान करते हैं यदि सेपरेटर वर्टेक्स के माध्यम से एक पथ मौजूद है।
• परिणाम: यह $O(t \log n)$ का एम्बेडिंग आयाम प्रदान करता है।

मुख्य योगदान और सैद्धांतिक सीमाएँ (Key Contributions and Theoretical Bounds)

शोध पत्र विभिन्न ग्राफ वर्गों के लिए आवश्यक एम्बेडिंग आयाम के लिए दोनों ऊपरी सीमा (constructive algorithms) और मिलान या निकट-मिलान निचली सीमाएं (lower bounds) प्रदान करता है।

ग्राफ वर्ग (Graph Class)	ऊपरी सीमा (आयाम)	निचली सीमा (आयाम)
सामान्य DAG	$O(n)$ (निहित)	$\Omega(n)$ (Theorem 6.3)
निर्देशित वृक्ष (Directed Trees)	3 (Theorem 3.1)	3 (Lemma B.3)
ट्रेewidth $t$	$O(t \log n)$ (Theorem 5.1)	$\Omega(t / \log(n/t))$ (Theorem 6.7)
क्रॉस-एजेस $k$	$3 + k$ (Theorem 4.1)	$\Omega(k^{1/4})$ और $\Omega(\frac{k \log(n^2/k)}{n \log n})$ (Theorems 6.8, 6.9)

मुख्य सैद्धांतिक अंतर्दृष्टि:

• वृक्षों के लिए टाइटनेस (Tightness for Trees): छोटे निर्देशित वृक्षों के लिए भी 3 का स्थिर आयाम आवश्यक है।
• अतुलनीयता (Incomparability): लेखक यह प्रदर्शित करते हैं कि ट्रेewidth और क्रॉस-एजेस पर आधारित सीमाएं अतुलनीय हैं; एक ग्राफ में स्थिर ट्रेewidth हो सकता है लेकिन $\Omega(n)$ क्रॉस-एजेस हो सकते हैं, या इसके विपरीत।
• निचली सीमाएं (Lower Bounds): सामान्य DAGs के लिए, रैखिक आयाम $\Omega(n)$ आवश्यक है। सीमित ट्रेewidth के लिए, आयाम को $t$ के साथ स्केल करना चाहिए, हालांकि लॉगरिदमिक कारकों के कारण निचली सीमा ऊपरी सीमा से थोड़ी कमजोर है।

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

लेखक अपने रचनात्मक दृष्टिकोण को वास्तविक दुनिया के पदानुक्रमित डेटासेट पर अनुभवजन्य रूप से मान्य करते हैं: WordNet (82k नोड्स), Gene Ontology (24k नोड्स), और Cora (2.7k नोड्स)।

• विधि: उन्होंने पुनरावर्ती सेपरेटर-आधारित निर्माण (धारा 5) को लागू किया और इसकी तुलना You et al. (2025) के "हैंडक्राफ्टेड एम्बेडिंग्स" से की, जो नॉर्मलाइज्ड एंसेस्टर वेक्टर्स का योग करते हैं।
• प्रदर्शन:
  • WordNet: प्रस्तावित विधि ने आयाम 152 पर 100% रिकॉल प्राप्त किया। बेसलाइन को 95% रिकॉल तक पहुँचने के लिए आयाम 512 की आवश्यकता थी और आयाम 128 पर केवल ~51% रिकॉल प्राप्त हुआ।
  • Cora और Gene Ontology: समान रुझान देखे गए, जहाँ प्रस्तावित विधि उच्च-रिकॉल शासन (high-recall regimes) में बेसलाइन की तुलना में काफी कम आयामों पर सटीक पुनर्प्राप्ति की गारंटी देती है।
• महत्व: प्रयोग पुष्टि करते हैं कि सैद्धांतिक $O(t \log n)$ सीमा व्यावहारिक रूप से मामूली स्थिरांक कारकों के साथ बनी रहती है, और रचनात्मक विधि उच्च-रिकॉल शासन में पूर्ववर्ती ह्यूरिस्टिक दृष्टिकोणों से बेहतर प्रदर्शन करती है।

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

यह शोध पत्र इस खुले प्रश्न को हल करने का दावा करता है कि क्या पदानुक्रमित पुनर्प्राप्ति के लिए सूक्ष्म-स्तरीय (fine-grained) एम्बेडिंग्स मौजूद हैं जो केवल कुल नोड्स के बजाय संरचनात्मक ग्राफ गुणों द्वारा पैरामीटराइज्ड हों।

• सैद्धांतिक प्रभाव: यह स्थापित करता है कि निर्देशित वृक्षों के लिए, रीचेबिलिटी को स्थिर आयाम (3) में कैप्चर किया जा सकता है, जो वृक्ष की ऊंचाई के साथ स्केल होने वाली पिछली सीमाओं की तुलना में एक महत्वपूर्ण सुधार है। यह इसे सीमित ट्रेewidth वाले ग्राफों तक विस्तारित करता है, जो $O(t \log n)$ का आयाम प्रदान करता है।
• व्यावहारिक प्रभाव: एम्बेडिंग्स की रचनात्मक प्रकृति बिना किसी महंगे प्रशिक्षण (सीखे गए एम्बेडिंग्स के विपरीत) के नियत (deterministic), तेज़ पीढ़ी की अनुमति देती है। यह विधि 100% रिकॉल की गारंटी देती है, जबकि सीखी गई बेसलाइन अक्सर कम आयामों के लिए सटीकता का त्याग करती हैं।
• सीमाएं: लेखक नोट करते हैं कि हालांकि वृक्षों के लिए सीमाएं सटीक हैं, लेकिन ट्रेewidth-पैरामीटर्ड ग्राफों के लिए ऊपरी और निचली सीमाओं के बीच एक अंतर है। इसके अतिरिक्त, विधि के लिए अच्छे वर्टेक्स सेपरेटर्स खोजने की आवश्यकता होती है, जो व्यवहार में एक अनुमान (approximation) समस्या है।

यह कार्य पदानुक्रमों को ज्यामितीय स्थानों में प्रस्तुत करने के लिए एक कठोर आधार प्रदान करता है, यह प्रदर्शित करते हुए कि ट्रेewidth और क्रॉस-एजेस जैसे संरचनात्मक पैरामीटर रीचेबिलिटी एम्बेडिंग की जटिलता को देखने के लिए सही लेंस हैं।