🤖 machine learning

The Polynomial Counting Capabilities of Message Passing Neural Networks

यह शोध पत्र मैसेज पासिंग न्यूरल नेटवर्क्स (MPNNs) की बहुपद गणना क्षमताओं (polynomial counting capabilities) की जांच करता है, जो यह प्रदर्शित करता है कि वे मीन एग्रीगेशन (mean aggregation) का उपयोग करके, विशेष रूप से रेगुलर ग्राफ, नॉन-नेस्टेड मोडैलिटीज या ट्री-लाइक संरचनाओं जैसी स्थितियों के तहत, नोड-लेबल वाले ग्राफ में वैश्विक और विशिष्ट स्थानीय बहुपद बाधाओं (global and specific local polynomial constraints) को सत्यापित कर सकते हैं।

मूल लेखक: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

प्रकाशित 2026-05-12

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

CC BY 4.0

मूल लेखक: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

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

एक मेसेज पासिंग न्यूरल नेटवर्क (MPNN) की कल्पना एक शहर (ग्राफ) में काम करने वाली जासूसों की एक टीम के रूप में करें। प्रत्येक जासूस (एक नोड) एक चौराहे पर खड़ा होता है और सुराग इकट्ठा करने के लिए अपने आस-पास के पड़ोसियों से बात करता है। उनके पास एक विशेष रेडियो भी है जिससे वे पूरे शहर में हो रही गतिविधियों का सारांश सुन सकते हैं।

इस शोध पत्र का लक्ष्य यह पता लगाना है कि ये जासूस गिनती (counting) करने में कितने कुशल हैं। विशेष रूप से, क्या वे केवल यह गिन सकते हैं कि "आस-पास कितने लाल घर हैं?" क्या वे जटिल गणितीय पहेलियों को हल कर सकते हैं जैसे, "क्या लाल घरों की संख्या का वर्ग, नीले घरों की संख्या के घन (cube) से अधिक है?"

यहाँ इस शोध के निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: लीनियर बनाम पॉलिनोमियल काउंटिंग (Linear vs. Polynomial Counting)

पिछले अधिकांश शोधों ने दिखाया है कि ये जासूस लीनियर काउंटिंग में माहिर हैं।

उदाहरण: "क्या नीले घरों से अधिक लाल घर हैं?" (यह $Red > Blue$ की तरह है)।
सीमा: वे पॉलिनोमियल काउंटिंग में संघर्ष करते थे, जहाँ संख्याओं को आपस में गुणा किया जाता है (वर्ग, घन, आदि)।
शोध का लक्ष्य: लेखक यह देखना चाहते थे कि क्या ये जासूस इन कठिन, "पॉलिनोमियल" गणितीय समस्याओं को संभाल सकते हैं।

2. गुप्त हथियार: "मीन" एग्रीगेटर (The "Mean" Aggregator)

जासूसों के पास अपने पड़ोसियों को सुनने के अलग-अलग तरीके हैं:

सम (Sum): वे अपने आस-पास से सुनी गई सभी संख्याओं को जोड़ देते हैं।
मैक्स (Max): वे केवल सबसे तेज़ आवाज़ को सुनते हैं।
मीन (Mean/औसत): वे सभी आवाजों का औसत निकालते हैं।

लेखकों ने पाया कि पॉलिनोमियल काउंटिंग के लिए मीन (औसत) ही असली सफलता का मंत्र है। औसत निकालकर, जासूस जटिल गणित के लिए आवश्यक विभाजन (division) और गुणा (multiplication) को स्वाभाविक रूप से संभाल सकते हैं। हालाँकि, इसे पूरी तरह से काम करने के लिए, शहर को कुछ विशिष्ट नियमों की आवश्यकता होती है।

3. सफलता के तीन नियम

शोध पत्र में पाया गया कि इन कठिन गणितीय पहेलियों को हल करने के लिए, शहर (ग्राफ) को आमतौर पर तीन "विशेष शर्तों" में से एक की आवश्यकता होती है:

शर्त A: "मार्क्ड" जासूस (द वीआईपी - The "Marked" Detective)
कल्पना करें कि एक जासूस ने एक चमकीली, अनूठी टोपी पहनी है जो किसी और के पास नहीं है। यह एक "मार्क्ड नोड" है।
- यह कैसे मदद करता है: यह टीम को एक निश्चित संदर्भ बिंदु (reference point) देता है। इसके बिना, जटिल विभाजन करते समय जासूस भ्रमित हो जाते हैं कि कौन सी संख्या किसकी है।
- वास्तविक दुनिया की उपमा: यह एक मानचित्र पर "यहाँ से शुरू करें" (Start Here) के संकेत की तरह है ताकि आप जानते रहें कि आप बाकी शहर के सापेक्ष कहाँ हैं।
शर्त B: "परफेक्टली रेगुलर" शहर (The "Perfectly Regular" City)
कल्पना करें कि एक ऐसा शहर जहाँ हर चौराहे से निकलने वाली सड़कों की संख्या बिल्कुल समान है।
- यह कैसे मदद करता है: यदि प्रत्येक जासूस के पास समान संख्या में पड़ोसी हैं, तो गणित सुसंगत रहता है। यदि एक जासूस के पास 3 पड़ोसी हैं और दूसरे के पास 10, तो "औसत" निकालना कठिन और तुलना करने में अव्यवस्थित हो जाता है।
- वास्तविक दुनिया की उपमा: एक पूरी तरह से सममित ग्रिड, जैसे शतरंज का बोर्ड, जहाँ प्रत्येक वर्ग के ठीक 4 पड़ोसी होते हैं।
शर्त C: "ट्री-लाइक" शहर (The "Tree-Like" City)
कल्पना करें कि एक ऐसा शहर जिसमें कोई लूप या घेरे (loops or circles) नहीं हैं—जैसे कि एक वंशावली (family tree) या एक शाखा वाली नदी।
- यह कैसे मदद करता है: यह संरचना जानकारी को चक्करों में फंसने से रोकती है, जिससे जासूस केंद्र से विभिन्न "दूरियों" पर चीजों को बिना भ्रमित हुए गिन सकते हैं।

4. बड़ी खोजें

परिदृश्य 1: पूरे शहर को देखना (ग्लोबल काउंटिंग)
यदि जासूसों को केवल पूरे शहर में चीजें गिननी हैं (विशिष्ट मोहल्लों को अनदेखा करते हुए), तो वे पॉलिनोमियल गणित की समस्याओं को हल कर सकते हैं यदि वहां एक मार्क्ड जासूस (शर्त A) मौजूद है। उन्हें शहर के पूरी तरह से नियमित होने की आवश्यकता नहीं है।

परिदृश्य 2: मोहल्लों को देखना (लोकल काउंटिंग)
यदि जासूसों को विशिष्ट मोहल्लों में गिनती करनी है (जैसे, "इस विशिष्ट जासूस के कितने लाल पड़ोसी हैं?"), तो यह कठिन हो जाता है।

कठोर मोड (Strict Mode): यदि वे केवल "मीन" (औसत) का उपयोग करते हैं, तो शहर को परफेक्टली रेगुलर (शर्त B) होना चाहिए और जासूस मार्क्ड (शर्त A) होना चाहिए और उसके पास एक सेल्फ-लूप (अपनी ही गली के कोने पर खड़ा होना) होना चाहिए।
शिथिल मोड (Relaxed Mode): यदि जासूसों को "मीन" के अलावा "सम" या "मैक्स" का उपयोग करने की अनुमति है, तो वे इन समस्याओं को तब भी हल कर सकते हैं जब शहर परफेक्टली रेगुलर नहीं है। उन्हें बस मार्क्ड जासूस और सेल्फ-लूप की आवश्यकता है।

परिदृश्य 3: गहरा नेस्टिंग (रूसी गुड़िया - The Russian Dolls)
कभी-कभी गणित नेस्टेड होता है: "पड़ोसियों के पड़ोसियों के पड़ोसियों की गिनती करें।"

शोध पत्र में पाया गया कि यदि शहर ट्री-लाइक (शर्त C) है और जासूसों के पास मार्क्ड स्थिति है, तो वे इन गहरे, नेस्टेड पॉलिनोमियल समस्याओं को हल कर सकते हैं।
यदि उन्हें "सम" या "मैक्स" सहायकों का उपयोग करने की अनुमति दी जाती है, तो वे और भी अधिक जटिल ट्री संरचनाओं को संभाल सकते हैं।

5. निष्कर्ष (The Takeaway)

यह शोध पत्र सिद्ध करता है कि MPNNs हमारी सोच से कहीं अधिक शक्तिशाली हैं, लेकिन उन्हें थोड़ी मदद की आवश्यकता है।

वे जटिल पॉलिनोमियल गणित (जैसे $x^2 + y^3$ ) कर सकते हैं यदि हम उन्हें एक संदर्भ बिंदु (एक मार्क्ड नोड) दें।
यदि हम चाहते हैं कि वे विशिष्ट मोहल्लों को देखें, तो शहर को सममित (regular) या पेड़ के आकार का (tree-shaped) होना चाहिए, जब तक कि हम उन्हें अतिरिक्त उपकरण (Sum/Max) न दें।

संक्षेप में: ये न्यूरल नेटवर्क प्रतिभाशाली गणितज्ञों की तरह हैं, लेकिन जटिल गणना पहेलियों को हल करने के लिए उन्हें एक स्पष्ट शुरुआती बिंदु और एक सुसंगत वातावरण की आवश्यकता होती है। उन शर्तों के बिना, वे गणित में खो जाते हैं।

तकनीकी सारांश: मैसेज पासिंग न्यूरल नेटवर्क्स की बहुपद गणना क्षमताएं (The Polynomial Counting Capabilities of Message Passing Neural Networks)

समस्या विवरण (Problem Statement)
हालिया शोध ने स्थापित किया है कि मैसेज पासिंग न्यूरल नेटवर्क्स (MPNNs) एक थ्रेशोल्ड तक या रैखिक अंकगणितीय बाधाओं (linear arithmetic constraints) को संतुष्ट करने वाली तार्किक गुणों को व्यक्त कर सकते हैं, जिन्हें अक्सर काउंटिंग वाले फर्स्ट-ऑर्डर लॉजिक (FOC2) के अंशों या लीनियर इंटीजर अरिथमेटिक के विस्तारों का उपयोग करके वर्णित किया जाता है। हालांकि, बहुपद गणना बाधाओं (polynomial counting constraints - गैर-रैखिक अंकगणित) के संबंध में MPNNs की अभिव्यंजक शक्ति (expressive power) को समझने में एक अंतर बना हुआ है, जो उन्नत ग्राफ वर्गीकरण तकनीकों जैसे कि बहुपद कर्नेल (polynomial kernels) के लिए प्रासंगिक हैं। यह शोध पत्र इस बात की जांच करता है कि किन परिस्थितियों में MPNNs, विशेष रूप से वे जो मीन एग्रीगेशन (mean aggregation) का उपयोग करते हैं, पीनो मोडल लॉजिक (PML) द्वारा परिभाषित गुणों को पहचान सकते हैं। PML, ग्रेडेड मोडल लॉजिक का विस्तार है जो केवल रैखिक के बजाय बहुपद बाधाओं (जैसे, $x_1^2 \cdot x_2 \leq x_3$ ) की अनुमति देता है।

कार्यप्रणाली (Methodology)
लेखक MPNNs की अभिव्यंजक क्षमताओं का विश्लेषण करने के लिए एक औपचारिक ढांचे का उपयोग करते हैं, जिसमें उन्हें PML के अंशों के साथ तुलना की जाती है।

मॉडल परिभाषा (Model Definition): अध्ययन उन MPNNs ( $M_{mean}$ ) पर केंद्रित है जो स्थानीय (पड़ोस) और वैश्विक (पूरे ग्राफ) जानकारी के लिए मीन एग्रीगेशन का उपयोग करते हैं। लेखक अन्य वेरिएंट्स ( $M_{mean, x}$ ) पर भी विचार करते हैं जो अतिरिक्त सम (sum) या मैक्स (max) एग्रीगेशन की अनुमति देते हैं।
लॉजिक परिभाषा (Logic Definition): वे PML को परिभाषित करते हैं, जहाँ मोडल फॉर्मूला $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ विशिष्ट पड़ोस (मोडालिटीज़ $\pi \in \{id, E_{in}, E_{out}, \top\}$ द्वारा परिभाषित) के भीतर उप-फॉर्मूला $\phi_i$ को संतुष्ट करने वाले नोड्स को गिनता है और यह जाँचता है कि क्या गिनती एक पीनो अंकगणितीय बाधा $\psi$ को संतुष्ट करती है।
पहचान ढांचा (Recognition Framework): एक MPNN को पॉइंटेड ग्राफों के वर्ग पर एक फॉर्मूला $\phi$ को "पहचानने" वाला कहा जाता है यदि नेटवर्क की आउटपुट स्टेट फोकस नोड $v$ के लिए गैर-शून्य (विशेष रूप से $\geq c(|V|)$ ) है, यदि ग्राफ $\phi$ को संतुष्ट करता है, और अन्यथा शून्य है। निश्चितता $c(|V|)$ ग्राफ के आकार पर निर्भर हो सकती है।
निर्माण रणनीति (Construction Strategy): प्रमाण विशिष्ट MPNN आर्किटेक्चर को परत-दर-परत बनाने के माध्यम से किए जाते हैं। ये निर्माण एग्रीगेटेड मानों पर अंकगणितीय संचालन (गुणा, जोड़, तुलना) करने के लिए "गैजेट्स" (ReLU न्यूरॉन्स के संयोजन) का उपयोग करते हैं। एक प्रमुख तकनीकी चुनौती मीन एग्रीगेशन (जैसे, $1/|V|$ या $1/|neigh(v)|$) द्वारा पेश किए गए हर (denominators) को संभालना है, जब अलग-अलग डिग्री के बहुपद पदों का मूल्यांकन किया जाता है।

प्रमुख योगदान और परिणाम (Key Contributions and Results)
यह शोध पत्र उन विशिष्ट संरचनात्मक धारणाओं की पहचान करता है जो मीन MPNNs को बहुपद गणना गुणों को कैप्चर करने में सक्षम बनाती हैं। परिणामों को मोडालिटी की गहराई (उथली बनाम नेस्टेड) और उपयोग किए गए मोडालिटी के प्रकार (वैश्विक बनाम स्थानीय) के आधार पर वर्गीकृत किया गया है।

वैश्विक मोडालिटीज़ (उथली गहराई) (Global Modalities - Shallow Depth):
- समरूप बाधाएं (Homogeneous Constraints): केवल वैश्विक मोडालिटी ( $\top$ ) और समरूप पीनो टर्म्स (कोई स्थिरांक पद नहीं, सभी मोनोमियल्स के लिए समान डिग्री) का उपयोग करने वाले फॉर्मूलों के लिए, मीन MPNN बिना किसी अतिरिक्त ग्राफ धारणा के लॉजिक को पहचान सकते हैं (लेम्मा 1)।
- सामान्य बहुपद बाधाएं (General Polynomial Constraints): मनमाने वैश्विक बहुपद बाधाओं (गैर-समरूप टर्म्स और स्थिरांकों सहित) को पहचानने के लिए, इनपुट ग्राफों में एक मार्क्ड नोड (एक अद्वितीय रंग वाला नोड) होना चाहिए। इस धारणा के तहत, मीन MPNNs $|V|^k$ तक हरों (denominators) को संरेखित कर सकते हैं और लॉजिक को पहचान सकते हैं (थ्योरम 1)।
स्थानीय मोडालिटीज़ (उथली गहराई) (Local Modalities - Shallow Depth):
- नियमितता की आवश्यकता (Regularity Requirement): केवल स्थानीय मोडालिटीज़ ( $E_{in}, E_{out}$ ) का उपयोग करने वाले फॉर्मूलों के लिए, मीन MPNNs को इनपुट ग्राफों के नियमित (सभी नोड्स का समान इन/आउट-डिग्री) होने की आवश्यकता होती है और फोकस नोड को स्ट्रॉन्गली मार्क्ड (मार्क्ड और स्वयं का लूप/self-loop वाला) होना चाहिए। यह नेटवर्क को स्थानीय पड़ोस के आकार को सामान्य (normalize) करने की अनुमति देता है (थ्योरम 2)।
- नियमितता को शिथिल करना (Relaxing Regularity): यदि MPNN को मीन के अलावा सम (sum) या मैक्स (max) एग्रीगेशन का उपयोग करने की अनुमति दी जाती है, तो नियमितता की धारणा को हटाया जा सकता है। नेटवर्क किसी भी ऐसे ग्राफ पर स्थानीय बहुपद बाधाओं को पहचान सकता है जहाँ फोकस स्ट्रॉन्गली मार्क्ड है (थ्योरम 3)।
मिश्रित मोडालिटीज़ (उथली गहराई) (Mixed Modalities - Shallow Depth):
- जब वैश्विक और स्थानीय मोडालिटीज़ को मिलाया जाता है, तो पिछले अनुभागों के परिणामों को जोड़ा जा सकता है। मीन MPNNs इन फॉर्मूलों को नियमित, स्ट्रॉन्गली मार्क्ड ग्राफों पर पहचानते हैं (थ्योरम 4)।
- सम/मैक्स एग्रीगेशन जोड़ने के साथ, नियमितता की धारणा को फिर से हटाया जा सकता है (थ्योरम 5)।
नेस्टेड मोडालिटीज़ (मनमानी गहराई) (Nested Modalities - Arbitrary Depth):
- वैश्विक नेस्टिंग (Global Nesting): वैश्विक मोडालिटीज़ को नेस्ट करने से गहराई 1 से अधिक की अभिव्यंजक शक्ति नहीं बढ़ती है; उन्हें फ्लैट किया जा सकता है (प्रपोजिशन 1)।
- स्थानीय नेस्टिंग (Local Nesting): नेस्टेड स्थानीय मोडालिटीज़ वाले फॉर्मूलों के लिए, यह शोध पत्र $(T \circlearrowleft_\phi)^p_\bullet$ नामक ग्राफों का एक वर्ग पेश करता है। ये "वृक्ष जैसी" (tree-like) संरचनाएं हैं जहाँ फोकस मार्क्ड है, और ग्राफ संरचना यह सुनिश्चित करती है कि विशिष्ट दूरियों पर नोड्स के लिए अद्वितीय ट्रेस (traces) हों (पड़ोस की गणना में अस्पष्टता से बचने के लिए)।
- परिणाम: मीन MPNNs इन वृक्ष जैसी, नियमित, स्ट्रॉन्गली मार्क्ड ग्राफों पर नेस्टेड स्थानीय PML को पहचान सकते हैं (थ्योरम 6)। यदि सम/मैक्स एग्रीगेशन की अनुमति दी जाती है, तो नियमितता प्रतिबंध हटा दिया जाता है, जिससे सामान्य वृक्ष-जैसी, स्ट्रॉन्गली मार्क्ड ग्राफों पर पहचान संभव होती है (थ्योरम 7)।

महत्व और दावे (Significance and Claims)
यह शोध पत्र दावा करता है कि यह पहचानता है कि किन न्यूनतम शर्तों की आवश्यकता MPNNs को रैखिक अंकगणित से आगे बढ़कर बहुपद गणना (polynomial counting) तक सामान्य करने (generalize) के लिए होती है।

सैद्धांतिक सामान्यीकरण (Theoretical Generalization): परिणाम बताते हैं कि मीन एग्रीगेशन वाले MPNNs उन तकनीकों को सामान्य कर सकते हैं जिनका उपयोग बहुपद कर्नेल (जैसे, बहुपद कर्नेल के साथ SVMs) पर आधारित ग्राफ वर्गीकरण के लिए किया जाता है, बशर्ते इनपुट डेटा विशिष्ट संरचनात्मक गुणों (मार्क्ड नोड्स, नियमितता, या वृक्ष-नुमा संरचना) को संतुष्ट करता हो।
एग्रीगेशन की भूमिका (Role of Aggregation): अध्ययन इस बात पर प्रकाश डालता है कि जबकि सख्त संरचनात्मक धारणाओं के तहत मीन एग्रीगेशन बहुपद गणना के लिए पर्याप्त है, सम या मैक्स एग्रीगेशन को शामिल करने से इन आवश्यकताओं (विशेष रूप से नियमितता की आवश्यकता को हटाने) में काफी ढील मिलती है।
सीमाएं (Limitations): लेखक स्पष्ट रूप से कहते हैं कि इन संरचनात्मक धारणाओं (मार्क्ड नोड्स, नियमितता, या वृक्ष-नुमा संरचना) के बिना, मीन MPNNs सभी बहुपद बाधाओं को व्यक्त नहीं कर सकते। उदाहरण के लिए, लेम्मा 2 दर्शाता है कि मीन MPNNs एक सरल बहुपद बाधा को संतुष्ट करने वाले कुछ गैर-नियमित ग्राफों के बीच अंतर नहीं कर सकते।

शोध पत्र निष्कर्ष निकालता है कि हालांकि MPNNs में बहुपद गणना क्षमताएं हैं, उन्हें साकार करने के लिए या तो विशिष्ट वास्तुशिल्प विकल्पों (सम/मैक्स जोड़ना) या विशिष्ट डेटा प्रीप्रोसेसिंग/संरचनात्मक धारणाओं (नोड्स को मार्क करना, नियमितता या वृक्ष-नुमा संरचना सुनिश्चित करना) की आवश्यकता होती है। भविष्य के कार्य के रूप में मोडालिटीज़ के मनमाने Boolean संयोजनों और विभिन्न दूरियों पर गणनाओं की तुलना करने का सुझाव दिया गया है, जो वर्तमान में उपयोग किए गए PML ढांचे में कवर नहीं किए गए हैं।