तकनीकी सारांश: ग्राफ न्यूरल नेटवर्क के लिए ट्रंकेटेड पोजीशनल एनकोडिंग को समझना

समस्या विवरण

ग्राफ न्यूरल नेटवर्क (GNNs), विशेष रूप से मैसेज पासिंग न्यूरल नेटवर्क (MPNNs), वैश्विक संरचनात्मक जानकारी को कैप्चर करने की अपनी क्षमता में मौलिक रूप से सीमित हैं, जो एक बाधा है जिसे 1-वीज़फाइलर-लेमान (1-WL) टेस्ट के समकक्ष औपचारिक रूप दिया गया है। इस बाधा को दूर करने के लिए, ग्राफ ट्रांसफॉर्मर (GTs) और उन्नत GNNs पोजीशनल एनकोिंग्स (PEs) का उपयोग करते हैं ताकि संरचनात्मक जानकारी को इंजेक्ट किया जा सके। PEs के दो प्रमुख परिवार हैं: स्पेक्ट्रल एनकोिंग्स (लैपलेसियन आइगेनस्पेस से व्युत्पन्न) और वॉक-आधारित एनकोिंग्स (एडजसेंसी मैट्रिक्स की घातों से व्युत्पन्न)।

सैद्धांतिक रूप से, इन एनकोिंग्स के पूर्ण संस्करण (उपयोग करके $\Omega(n)$ आइगेनवेक्टर्स या मैट्रिक्स घातों) समान अभिव्यंजक शक्ति (expressive power) रखते हैं, जो 1-WL और 3-WL परीक्षणों के बीच स्थित हैं। हालांकि, इन पूर्ण एनकोिंग्स की गणना करने के लिए $O(n^3)$ समय और स्थान जटिलता की आवश्यकता होती है, जो वास्तविक दुनिया के अनुप्रयोगों के लिए अत्यधिक महंगी है। फलस्वरूप, अभ्यासकर्ता ट्रंकेटेड वेरिएंट्स (जैसे कि पहले $k$ आइगेनवेक्टर्स या एडजसेंसी मैट्रिक्स की पहली $k$ घातों) पर निर्भर करते हैं। इन ट्रंकेटेड PEs के सैद्धांतिक गुण, अभिव्यंजक शक्ति और तुलनात्मक ताकत का अध्ययन काफी हद तक अनछुआ रहा है, जिससे सैद्धांतिक गारंटी और व्यावहारिक कार्यान्वयन के बीच एक अंतर पैदा हो गया है।

कार्यप्रणाली

लेखक सैद्धांतिक विश्लेषण और अनुभवजन्य सत्यापन (empirical validation) दोनों के माध्यम से ट्रंकेटेड PEs का एक व्यवस्थित अध्ययन शुरू करते हैं।

सैद्धांतिक ढांचा

यह शोध पत्र विभिन्न PEs की अभिव्यंजक शक्ति को वर्गीकृत करने के लिए WL पदानुक्रम (hierarchy) और इसके वेरिएंट्स का उपयोग करता है:

• $\psi$-WL टेस्ट: एक $\psi$ जैसे रिलेटिव पोजीशनल एनकोडिंग (RPE) का उपयोग करके नोड रंगों को अपडेट करने वाला WL टेस्ट का एक संस्करण।
• स्पार्स-$\psi$-WL टेस्ट: एक MPNN के लिए विस्तार जहाँ $\psi$ का उपयोग एज फीचर्स के रूप में किया जाता है।
• विश्लेषित मुख्य परिवार:
  1. ट्रंकेटेड आइजनस्पेस प्रोजेक्शन्स ($k$-EP-WL): लैपलेसियन के पहले $k$ आइजनस्पेस प्रोजेक्शन्स का उपयोग करना।
  2. ट्रंकेटेड वॉक एनकोिंग्स ($k$-Walk-WL): एडजसेंसी मैट्रिक्स की पहली $k$ घातों का उपयोग करना।
  3. इफेक्टिव रेजिस्टेंस (रेजिस्टेंस-WL): एक विशिष्ट स्पेक्ट्रल दूरी (1-हारमोनिक दूरी)।
  4. $k$-हारमोनिक दूरियाँ: इफेक्टिव रेजिस्टेंस का एक सामान्यीकरण जिसे $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ के रूप में परिभाषित किया गया है।

लेखक विशिष्ट ग्राफ जोड़े (जैसे, पाथ ग्राफ और कम्पलीट ग्राफ के उत्पाद, या साइकल बनाम डिस्कजॉइंट यूनियन ऑफ साइकल्स) का निर्माण करते हैं ताकि विभिन्न ट्रंकेटेड PEs और WL टेस्ट के तहत सेपेरेबिलिटी (separability) या इंडिस्टिंगुइशेबिलिटी (indistinguishability) को सिद्ध किया जा सके।

अनुभवजन्य मूल्यांकन (Empirical Evaluation)

तीन बेंचमार्क पर प्रयोग किए गए:

1. BREC: एक डेटासेट जिसे GNNs की "वास्तविक अभिव्यंजक क्षमता" (realized expressivity) को मापने के लिए डिज़ाइन किया गया है, जो 1-WL से 4-WL के बीच इंडिस्टिंगुइशेबल गैर-आइसोमोर्फिक ग्राफ्स को अलग करने की उनकी क्षमता का परीक्षण करता है।
2. ZINC-12k: आणविक घुलनशीलता के लिए एक ग्राफ रिग्रेशन बेंचमार्क, जिसका उपयोग इस परिकल्पना का परीक्षण करने के लिए किया जाता है कि ट्रंकेटेड PEs को मिलाने से प्रदर्शन में सुधार होता है।
3. ogbg-molhiv: HIV निषेध के लिए एक बाइनरी क्लासिफिकेशन बेंचमार्क।

लेखों ने स्पेक्ट्रल, वॉक और $k$-हारमोनिक एनकोडिंग के विभिन्न संयोजनों सहित विभिन्न ट्रंकेटेड PEs का उपयोग करके Graphormer-GD आर्किटेक्चर और MPNNs (GINE) का मूल्यांकन किया।

मुख्य योगदान और परिणाम

1. ट्रंकेटेड रूपों में अभिव्यंजक शक्ति का विचलन

यह शोध पत्र सिद्ध करता है कि जबकि पूर्ण स्पेक्ट्रल और वॉक एनकोिंग्स समान हैं, उनके ट्रंकेटेड रूप मौलिक रूप से भिन्न हैं:

• ट्रंकेटेड स्पेक्ट्रल बनाम 1-WL: लेखक दिखाते हैं कि ट्रंकेटेड आइजनस्पेस प्रोजेक्शन्स ($k$-EP-WL), 1-WL टेस्ट से भी कमजोर हो सकते हैं। विशेष रूप से, ऐसे ग्राफ जोड़े मौजूद हैं जो 1-WL द्वारा अलग किए जा सकते हैं लेकिन $k \in \Omega(n)$ के लिए $k$-EP-WL द्वारा नहीं पहचाने जा सकते (थ्योरम 4.1)।
• ट्रंकेटेड वॉक बनाम स्पेक्ट्रल: इसके विपरीत, ऐसे ग्राफ जोड़े मौजूद हैं जिन्हें एक एकल आइजनस्पेस प्रोजेक्शन (1-EP-WL) द्वारा अलग किया जा सकता है लेकिन $\Omega(n)$-साइज वॉक एनकोिंग्स द्वारा नहीं पहचाना जा सकता (थ्योरम 4.2)।
• निहितार्थ: कोई भी एकल ट्रंकेटेड PE परिवार पूर्णतः श्रेष्ठ नहीं है; वे अलग-अलग संरचनात्मक पहलुओं को कैप्चर करते हैं और मानक WL पदानुक्रम के साथ तुलनीय नहीं हो सकते हैं।

2. इफेक्टिव रेजिस्टेंस की सीमाएं

यह शोध पत्र इफेक्टिव रेजिस्टेंस (1-हारमोनिक दूरी) का विश्लेषण करता है और पाता है कि यह de-weighted ग्राफ्स पर पूर्ण आइजनस्पेस प्रोजेक्शन या वॉक एनकोिंग्स की तुलना में एक कमजोर PE है।

• थ्योरम 4.3: ऐसे भारित (weighted) ग्राफ मौजूद हैं जो रेजिस्टेंस-WL द्वारा अनिर्दिष्ट (indistinguishable) हैं लेकिन एडजसेंसी-WL (और इस प्रकार अनवेटेड ग्राफ्स पर 1-WL) द्वारा अलग किए जा सकते हैं।
• कोरोलरी 4.1: रेजिस्टेंस-WL ग्राफ के संपूर्ण स्पेक्ट्रम को एनकोड नहीं करता है, जो एक पिछले अनुमान को खारिज करता है।

3. $k$-हारमोनिक दूरियाँ एक सेतु के रूप में

लेखक स्पेक्ट्रल और पोलीनोमियल एनकोिंग्स के बीच एक प्राकृतिक सेतु के रूप में $k$-हारमोनिक दूरियों को पेश करते हैं।

• पूर्णता (Completeness): $\Theta(n)$ $k$-हारमोनिक दूरियों को जोड़ने से एक ऐसा एनकोडिंग प्राप्त होता है जो पूर्ण स्पेक्ट्रल या वॉक एनकोिंग्स के समान शक्ति रखता है (थ्योरम 4.6)।
• विभेदक शक्ति (Differential Power): $k$-हारमोनिक परिवार के भीतर भी, निश्चित आकार के एनकोडिंग्स भिन्न होते हैं। उदाहरण के लिए, बिहारमोनिक दूरी (2-harmonic) कुछ ट्री जोड़ों को निरंतर संख्या में इटरेशन में अलग कर सकती है, जबकि इफेक्टिव रेजिस्टेंस (1-harmonic) को $O(n)$ इटरेशन की आवश्यकता होती है (थ्योरम 4.7)।
• मजबूती (Robustness): हालांकि, यदि एक $k$-हारमोनिक दूरी ग्राफ के जोड़े को अलग करती है, तो अधिकांश अन्य $k$-हारमोनिक दूरियां भी उन्हें अलग करेंगी (थ्योरम 4.8)।

4. अनुभवजन्य निष्कर्ष: मिश्रण की शक्ति

• BREC परिणाम: $k$-हारमोनिक दूरियों ने सिंगल-चैनल, लो-ओवरहेड एनकोइंग्स के साथ प्रतिस्पर्धी परिणाम प्राप्त किए, जो अक्सर 1-WL और 3-WL के बीच के ग्राफ्स के लिए सैद्धांतिक सीमा के बराबर होते हैं।
• ZINC परिणाम: सबसे महत्वपूर्ण निष्कर्ष यह है कि विभिन्न परिवारों से PEs को मिलाना (जैसे, ट्रंकेटेड वॉक और $k$-हारमोनिक्स को जोड़ना) किसी भी एकल परिवार की तुलना में बेहतर प्रदर्शन करता है। ZINC-12k पर सबसे कम मीन एब्सोल्यूट एरर (MAE) प्राप्त करने के लिए ट्रंकेटेड वॉक और $k$-हारमोनिक्स का मिश्रण उपयोग किया गया, जिसने सिंगल-फैमिली बेसलाइन्स को पीछे छोड़ दिया।
• दक्षता: शोध पत्र नोट करता है कि $k$-हारमोनिक दूरियों को फास्ट लैपलेसियन सॉल्वर और जॉनसन-लिंडेनस्ट्रॉस प्रोजेक्शन्स का उपयोग करके $O(mk \cdot \text{poly}(\log n))$ समय में अनुमानित किया जा सकता है, जिससे सटीक गणना की $O(n^3)$ लागत से बचा जा सकता है।

महत्व और दावे

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

• सैद्धांतिक अंतर्दृष्टि: यह कार्य प्रदर्शित करता है कि ट्रंकेशन PEs द्वारा कैप्चर की गई जानकारी को मौलिक रूप से बदल देता है, जिससे वे विशिष्ट मामलों में मानक WL पदानुक्रम के साथ तुलनीय नहीं रह जाते।
• व्यावहारिक मार्गदर्शन: लेखक एक नियम-ऑफ-थंब (rule-of-thumb) प्रस्तावित करते हैं: जब ट्रंकेटेड एनकोइंग्स का उपयोग कर रहे हों, तो विभिन्न परिवारों के PEs को मिलाएं। यह दृष्टिकोण कंप्यूटेशनल लागत को नियंत्रित करते हुए पूरक संरचनात्मक संकेतों को कैप्चर करता है।
• सीमित दायरा: लेखक स्वीकार करते हैं कि हालांकि ग्राफ आइसोमोर्फिज्म एक सिद्धांतगत प्रॉक्सी है, वास्तविक दुनिया के कार्यों में डाउनस्ट्रीम सिग्नल (सेंट्रैलिटी, मोटिफ्स) शामिल होते हैं जो शायद आइसोमोर्फिज्म टेस्टिंग के साथ सख्ती से संरेखित न हों। अतः, प्राथमिक योगदान एक व्यवस्थित अनुभवजन्य अध्ययन के लिए एक सैद्धांतिक आधार और शुरुआती बिंदु स्थापित करना है, न कि सभी ग्राफ लर्निंग कार्यों के लिए सार्वभौमिक समाधान का दावा करना।