RAwR: Role-Aware Rewiring via Approximate Equitable Partition

तकनीकी सारांश: RAwR: अनुमानित समतुल्य विभाजन (Approximate Equitable Partition) के माध्यम से भूमिका-जागरूक पुनर्गठन (Role-Aware Rewiring)

समस्या विवरण
ग्राफ न्यूरल नेटवर्क (GNNs) ने स्थानीय पड़ोस की जानकारी पर निर्भर नोड वर्गीकरण कार्यों में प्रभावकारما दिखाया है। हालांकि, उनका प्रदर्शन अक्सर तब घट जाता है जब भविष्यवाणी कार्य दीर्घ-दूरी की अंतःक्रियाओं (long-range interactions) पर निर्भर होते हैं। यह सीमा ओवरस्क्वैशिंग (oversquashing) के कारण होती है, जो एक ऐसी घटना है जहाँ संरचनात्मक बाधाएं (structural bottlenecks) नेटवर्क टोपोलॉजी में सिग्नल प्रसार को प्रतिबंधित करती हैं, जिससे लक्षित नोड तक पहुँचने से पहले ही दीर्घ-दूरी के संकेतों को संकुचित कर दिया जाता है। मौजूदा ग्राफ पुनर्गठन विधियाँ (जैसे, मास्टर नोड, वक्रता-आधारित दृष्टिकोण, स्पेक्ट्रल विधियाँ) वैश्विक सिग्नल प्रसार में सुधार करके ओवरस्क्वैशिंग को कम करने का लक्ष्य रखती हैं, लेकिन वे अक्सर यह अंतर करने में विफल रहती हैं कि विशिष्ट डाउनस्ट्रीम कार्यों के लिए कौन से दीर्घ-दूरी के संचार पथ संरचनात्मक रूप से प्रासंगिक हैं। हेटरोफिलिक (heterophilic) ग्राफों या उन परिदृश्यों में जहाँ नोड वर्ग तात्कालिक आसन्नता (adjacency) के बजाय संरचनात्मक भूमिकाओं को दर्शाते हैं, अंधाधुंध पुनर्गठन इष्टतम नहीं हो सकता है।

कार्यप्रणाली
लेखक RAwR (Role-Aware Rewiring) पेश करते हैं, जो एक गणनात्मक रूप से कुशल, मॉडल-अज्ञेतर (model-agnostic) ढांचा है जो अनुमानित समतुल्य विभाजन (Approximate Equitable Partitions - AEPs) से प्राप्त एक कोशेंट ग्राफ (quotient graph) के माध्यम से इनपुट ग्राफ को संवर्धित करता है।

1. अनुमानित समतुल्य विभाजन (AEPs):

   • एक समतुल्य विभाजन उन नोड्स को समूहित करता है जिनके पास विभाजन के प्रत्येक ब्लॉक में समान संख्या में पड़ोसी होते हैं। यह एक कोशेंट ग्राफ को प्रेरित करता है जो भूमिका-से-भूमिका (role-to-role) अंतःक्रियाओं का सटीक सारांश प्रस्तुत करता है।
   • RAwR एक $\epsilon$-AEP का उपयोग करता है, जो सटीक भूमिका समानता के बजाय एक सहनशीलता पैरामीटर $\epsilon$ के माध्यम से इसे शिथिल (relax) करता है। यह समान (लेकिन सटीक रूप से एक जैसी नहीं) संरचनात्मक भूमिकाओं वाले नोड्स को समूहित करने की अनुमति देता है, जिससे यह दृष्टिकोण वास्तविक दुनिया के ग्राफों में शोर (noise) के प्रति मजबूत बनता है।
   • विभाजन को $\epsilon$-BE एल्गोरिदम का उपयोग करके बहुपद समय (polynomial time) में कुशलतापूर्वक संगणना किया जाता है।

2. पुनर्गठन वेरिएंट्स (Rewiring Variants):
   इनपुट ग्राफ $G=(V, E)$ और एक $\epsilon$-AEP (सूचक मैट्रिक्स $R$ और कोशेंट मैट्रिक्स $Q$ के साथ) दिए जाने पर, RAwR एक संवर्धित एडजसेंसी मैट्रिक्स बनाता है। दो विशिष्ट वेरिएंट प्रस्तावित किए गए हैं:

   • RepNodes: प्रत्येक मूल नोड को उसके संरचनात्मक भूमिका के अनुरूप एक एकल आभासी प्रतिनिधि नोड (Virtual Representative Node - VN) से जोड़ता है। यह उन नोड्स के बीच दो-हॉप संचार पथ बनाता है जो टोपोलॉजिकल रूप से दूर हैं लेकिन संरचनात्मक रूप से समान हैं। इसमें कोशेंट मैट्रिक्स को शून्य ($Q=0$) सेट किया जाता है।
   • RepEdges: अपने प्रतिनिधियों से जोड़ने के अलावा, यह वेरिएंट अनवेटेड कोशेंट ग्राफ ($\bar{Q}$) के अनुसार प्रतिनिधि VNs को आपस में जोड़ता है, जिससे परस्पर क्रिया करने वाली भूमिकाओं के बीच संचार सक्षम होता है।

3. सैद्धांतिक आधार (शिक्षक-छात्र विश्लेषण):
   यह शोध पत्र पुनर्गठन के प्रभाव का विश्लेषण करने के लिए रैखिक GNN के शिक्षक-छात्र मॉडल का उपयोग करता है।

   • धारणा: वास्तविक लेबल एक "शिक्षक" GNN द्वारा उत्पन्न होते हैं जो एक गुप्त संरचना (RAwR-संवर्धित ग्राफ) पर कार्य करता है, जबकि एक "छात्र" GNN देखे गए ग्राफ से सीखने का प्रयास करता है।
   • स्पेक्ट्रल रोल लिफ्ट (Spectral Role Lift - SRL): विश्लेषण छात्र की त्रुटि के लिए एक ऊपरी सीमा (upper bound) व्युत्पन्न करता है, जिससे SRL का सूत्र बनता है, जिसे $\text{SRL} = \rho \sum_{j=1}^k \omega_j \Delta_j^2$ के रूप में परिभाषित किया गया है। यहाँ $\rho$ भूमिका उपस्थान (role subspace) में लेबलों की ऊर्जा को मापता है, $\Delta_j$ मूल और पुनर्गठित ग्राफों के बीच भूमिका-प्रासंगिक आइजन मानों (eigenvalues) में अंतर को दर्शाता है, और $\omega_j$ भूमिका भार (role weights) हैं।
   • अनुमानी चयन (Heuristic Selection): एक व्यावहारिक अनुमानी, SRL$^*$, प्रस्तावित है ताकि इष्टतम सहनशीलता पैरामीटर $\epsilon$ का चयन किया जा सके। यह 2-हॉप नेबर क्लास सिमिलरिटी (2NCS) मेट्रिक के साथ SRL को जोड़ता है ताकि उन मामलों को संभाला जा सके जहाँ लेबल सख्ती से भूमिका उपस्थान में नहीं होते हैं।

मुख्य योगदान

1. RAwR फ्रेमवर्क: एक नया पुनर्गठन तरीका जो सूचना को केवल आसानी से प्रसारित करने के बजाय उसे संरचनात्मक रूप से सार्थक पथों (संरचनात्मक भूमिकाओं) के माध्यम से रूट करता है। यह मास्टर नोड तकनीक को एक सीमा मामले (limit case) के रूप में पुनर्प्राप्त करता है, लेकिन $\epsilon$ के माध्यम से नियंत्रणीय सूक्ष्मता (granularity) प्रदान करता है।
2. संरचनात्मक साक्ष्य: यह प्रमाण कि RAwR इनपुट ग्राफ के औसत प्रभावी प्रतिरोध (mean effective resistance) को कम करता है, जो यह दर्शाता है कि यह डाउनस्ट्रीम GNN आर्किटेक्चर से स्वतंत्र रूप से दीर्घ-दूरी के प्रसार बाधाओं को कम करता है।
3. सैद्धांतिक विश्लेषण: एक शिक्षक-छात्र मॉडल का उपयोग करते हुए एक औपचारिक व्युत्पत्ति जो यह स्पष्ट करती है कि भूमिका-आधारित पुनर्गठन संदेश-पासिंग मॉडल के स्पेक्ट्रल रिस्पॉन्स को कैसे संशोधित करता है। इससे $\epsilon$ के चयन के लिए SRL मेट्रिक प्राप्त होता है।
4. पूरकता (Complementarity): साक्ष्य कि RAwR न केवल ओवरस्क्वैशिंग को संबोधित करने के लिए डिज़ाइन किए गए आर्किटेक्चर-स्तरीय समाधानों (जैसे GRAIN) के साथ प्रतिस्पर्धी है, बल्कि उनके ऊपर लागू होने पर प्रदर्शन में और सुधार करने के लिए पूरक भी है।

प्रायोगिक परिणाम
लेखकों ने होमोफिलिक (जैसे Cora, Citeseer), हेटरोफिलिक (जैसे Chameleon, Squirrel), और सिंथेटिक लॉन्ग-रेंज (ECHO) डेटासेट्स सहित विविध बेंचमार्क पर RAwR का मूल्यांकन किया।

• प्रदर्शन: RAwR नोड वर्गीकरण कार्यों में तुलना की गई विधियों (BORF, FOSR, SDRF, JDR, ComFy, TRIGON, और Master Node सहित) के बीच सर्वश्रेष्ठ औसत रैंक प्राप्त करता है।
• दीर्घ-दूरी और हेटरोफिलिक लाभ: सबसे महत्वपूर्ण सुधार हेटरोफिलिक और दीर्घ-दूरी वाले डेटासेट्स (जैसे ECHO) पर देखे गए हैं, जहाँ स्थानीय संदेश पासिंग अपर्याप्त है। उदाहरण के लिए, बिना नोड फीचर्स वाले ECHO "Caterpillar" डेटासेट पर, RepNodes के साथ सटीकता बेसलाइन के 38.82% से बढ़कर 76.47% हो गई।
• एब्लेशन अध्ययन (Ablation Studies):
  • RepNodes बनाम RepEdges: RepNodes आम तौर पर वास्तविक दुनिया के बेंचमार्क पर बेहतर प्रदर्शन करता है, जो यह सुझाव देता है कि तीव्र इंट्रा-रोल संचार सुधार का प्राथमिक स्रोत है।
  • रैंडम पार्टिशन: समान संख्या में वर्चुअल नोड्स के साथ रैंडम पार्टिशन के विरुद्ध RAW का तुलनात्मक अध्ययन दिखाता है कि लाभ केवल वर्चुअल नोड्स के जुड़ने से नहीं, बल्कि संरचनात्मक भूमिका असाइनमेंट से संचालित होते हैं। RAwR रैंडम कंट्रोल्स की तुलना में औसतन +3.66 प्रतिशत अंक बेहतर है।
  • SRL$^*$ अनुमानी: SRL$^*$ अनुमानी प्रतिस्पर्धी $\epsilon$ मानों का प्रभावी ढंग से चयन करती है, जो अक्सर ग्रिड-सर्च परिणामों के करीब होते हैं, विशेष रूप से वास्तविक दुनिया के डेटासेट्स पर।

महत्व और सीमाएँ
यह शोध पत्र दावा करता है कि RAwR सूचना को केवल यह भेजने के बजाय कि कैसे प्रसारित किया जाए, इस पर ध्यान केंद्रित करके कि सूचना को कहाँ रूट किया जाना चाहिए, पुनर्गठन के एक महत्वपूर्ण अंतराल को भरता है। संरचनात्मक भूमिकाओं का लाभ उठाकर, यह टोपोलॉजिकल रूप से दूर लेकिन संरचनात्मक रूप से समान नोड्स के बीच कुशल संचार को सक्षम बनाता है, जो सीधे ओवरस्क्वैशिंग की घटना को संबोधित करता है।

लेखक सीमाओं के संबंध में एक मध्यम स्वर बनाए रखते हैं:

• वर्तमान मूल्यांकन अनडिरेक्टेड (undirected) और अनवेटेड (unweighted) ग्राफ तक सीमित है, हालांकि AEPs को निर्देशित/भारित (directed/weighted) मामलों के लिए भी परिभाषित किया गया है।
• SRL व्युत्पत्ति एक रैखिक GNN को मानता है जो बहुपद फिल्टर के रूप में कार्य करता है; यह अनुमानी उन आर्किटेक्चर जैसे GAT या GIN के लिए कम सूचनात्मक हो सकती है जो इस मॉडल में आसानी से फिट नहीं होते हैं।
• प्रायोगिक ध्यान नोड वर्गीकरण पर है; अन्य ग्राफ लर्निंग कार्यों में विस्तार भविष्य के कार्य के लिए छोड़ दिया गया है।

संक्षेप में, RAwR पुनर्गठन का एक सिद्धांत-आधारित, भूमिका-आधारित दृष्टिकोण प्रदान करता है जो प्रभावी प्रतिरोध को कम करके और संदेश पासिंग को संरचनात्मक भूमिकाओं के साथ संरेखित करके, दीर्घ-दूरी और हेटरोफिलिक कार्यों पर GNN प्रदर्शन में सुधार करता है।