आईएसटीए शोधकर्ता जांच करते हैं कि ग्राफ आइसोमोर्फिज्म एल्गोरिदम इतने प्रभावी क्यों लगते हैं
ग्राफ़ हर जगह हैं. असतत गणित में, वे संरचनाएं हैं जो सार्वजनिक परिवहन नेटवर्क की तरह, बिंदुओं के बीच संबंध दिखाती हैं। गणितज्ञ लंबे समय से ऐसे एल्गोरिदम विकसित करने की मांग कर रहे हैं जो किन्हीं दो ग्राफ़ों की तुलना कर सकें। व्यवहार में, कई एल्गोरिदम हमेशा कुशलता से काम करते प्रतीत होते हैं। लेकिन सिद्धांत रूप में, इसकी कोई गारंटी नहीं है। एक नये में arXiv प्रीप्रिंट, शोधकर्ताओं से क्वान समूह इंस्टीट्यूट ऑफ साइंस एंड टेक्नोलॉजी ऑस्ट्रिया (आईएसटीए) ने इसका कारण समझने के लिए एक विधि विकसित की है।
कुछ गणितीय समस्याओं की कठिनाई यह जानने में निहित है कि वे कितनी कठिन हैं। यह कंप्यूटर विज्ञान में एक महत्वपूर्ण समस्या का मामला है जिसे “ग्राफ़ आइसोमोर्फिज्म परीक्षण” कहा जाता है, जिसके तहत वैज्ञानिक यह जांचने के लिए एल्गोरिदम का उपयोग करते हैं कि क्या दो ग्राफ़ समान हैं। सिद्धांत रूप में, इस बात से इंकार नहीं किया जा सकता है कि एल्गोरिदम ब्रह्मांड की आयु से अधिक समय तक चल सकता है। लेकिन व्यवहार में, कई एल्गोरिदम बिल्कुल ठीक काम करते प्रतीत होते हैं। लगभग हमेशा। ये एल्गोरिदम इतने प्रभावी क्यों लगते हैं' इंस्टीट्यूट ऑफ साइंस एंड टेक्नोलॉजी ऑस्ट्रिया (आईएसटीए) के पोस्टडॉक्स माइकल अनास्टोस और बेंजामिन मूर और सहायक प्रोफेसर मैथ्यू क्वान ने अपने नए प्रीप्रिंट में इस प्रश्न का समाधान किया है। अनास्टोस कहते हैं, “ग्राफ आइसोमोर्फिज्म समस्या की जटिलता कंप्यूटर विज्ञान में सबसे दिलचस्प सवालों में से एक है।” क्वान कहते हैं, “ग्राफ़ समरूपता समस्या कठिन नहीं लगती है, लेकिन हम किसी तरह अभी तक यह साबित नहीं कर सकते हैं कि यह आसान है।”
मॉडलिंग नेटवर्क की जटिलता
ग्राफ़ का उपयोग विभिन्न प्रकार की प्रणालियों को मॉडल करने के लिए किया जाता है, जैसे कि सामाजिक नेटवर्क, संचार मार्ग, कंप्यूटर नेटवर्क और अन्य। यह बात रासायनिक यौगिकों पर भी लागू होती है। क्वान कहते हैं, “रसायनज्ञ अणुओं की तुलना करने और रसायनों के डेटाबेस बनाने के लिए ग्राफ आइसोमोर्फिज्म परीक्षण एल्गोरिदम का उपयोग करते हैं।” इससे उन्हें अपने नव संश्लेषित यौगिकों की नवीनता की जांच करने की अनुमति मिलती है। लेकिन ग्राफ़, विशिष्ट कोणों और आयामों वाली ज्यामितीय आकृतियों के विपरीत, नेटवर्क का प्रतिनिधित्व करते हैं। इस प्रकार, वे बेहद जटिल हो सकते हैं और उनके कनेक्शन के नोड्स-बिंदुओं को स्वतंत्र रूप से स्थित किया जा सकता है, जो उन्हें दृष्टिगत रूप से पहचानने योग्य नहीं बनाता है। सभी संभावित परिस्थितियों में ऐसे जटिल ग्राफ़ों की तुलना करना गणितज्ञों को हैरान कर गया है।
रंगों से परिष्कृत करना
गणितज्ञों ने ग्राफ़ की तुलना करने के लिए विभिन्न रणनीतियाँ विकसित की हैं। 1970 के दशक से, एल्गोरिदम ग्राफ समरूपता का परीक्षण करने में सक्षम हैं, लेकिन घातांकीय समय में। इसका मतलब यह है कि ग्राफ़ की बढ़ती जटिलता ने एल्गोरिदम के चलने के समय को असंगत रूप से बढ़ा दिया और इसे काफी धीमा कर दिया। 2015 में, कंप्यूटर वैज्ञानिक और गणितज्ञ लास्ज़लो बाबाई ने “अर्ध-बहुपद समय” में चलने वाले एल्गोरिदम का प्रस्ताव देकर एक सफलता हासिल की। यह “बहुपद-समय” बेंचमार्क के काफी करीब आता है जो कुशल एल्गोरिदम को अकुशल एल्गोरिदम से अलग करता है। लेकिन पहले से ही 1980 में, एक अन्य शास्त्रीय प्रमेय-बाबई-एर्डोस-सेल्को प्रमेय-ने दिखाया कि आसान आइसोमोर्फिज्म परीक्षण को संभव बनाने के लिए लगभग सभी ग्राफ़ को फिर से लेबल किया जा सकता है। यह एक प्रकार के शोधन के कारण होता है जिसे “रंग शोधन” कहा जाता है, जिसके तहत एल्गोरिदम ग्राफ़ में प्रत्येक नोड के कनेक्शन का अध्ययन करता है और उसे एक रंग प्रदान करता है। इस प्रकार निर्दिष्ट अलग-अलग रंग एल्गोरिदम को आसानी से पहचानने की अनुमति देते हैं कि एक विशेष नोड कितने अन्य शीर्षों को 'देखता' है।
यह दृष्टिकोण ग्राफ़ के एक बड़े पूल में तुलना की सुविधा प्रदान करता है। “रंग परिशोधन पर आधारित एल्गोरिदम व्यवहार में ज्यादातर मामलों में काम करते प्रतीत होते हैं। लेकिन यह मामला कैसे हो सकता है जब सिद्धांत कहता है कि इसमें तेजी से समय लग सकता है'' अनास्टोस पूछते हैं। “हमारे काम का लक्ष्य बेहतर सबसे खराब स्थिति में चलने वाली गारंटी के लिए अनुकूलित एल्गोरिदम को डिजाइन करना नहीं है। इसके बजाय, हमारा लक्ष्य सैद्धांतिक औचित्य देना और यह जानकारी प्रदान करना है कि रंग शोधन पर आधारित एल्गोरिदम इतने प्रभावी क्यों लगते हैं।”
यादृच्छिक गड़बड़ी और सहज विश्लेषण
यह बेहतर ढंग से समझने के लिए कि रंग परिशोधन क्यों कारगर साबित होता है-कम से कम व्यवहार में अधिकांश मामलों में-अनास्टोस, क्वान और मूर ने इसे “सुचारू विश्लेषण” नामक एक अन्य अवधारणा के साथ जोड़ा। कंप्यूटर वैज्ञानिकों डैनियल स्पीलमैन और शांग-हुआ टेंग द्वारा 2000 के दशक की शुरुआत में पेश किया गया, यह एल्गोरिदम के औसत-मामले और सबसे खराब-मामले प्रदर्शन के बीच अंतर को पाटने के लिए एक सामान्य प्रतिमान है। स्मूथेड विश्लेषण ने 2008 में स्पीलमैन और टेंग को गोडेल पुरस्कार जीता, जो सैद्धांतिक कंप्यूटर विज्ञान में उत्कृष्ट शोधपत्रों के लिए एक वार्षिक पुरस्कार है।
सीधे शब्दों में कहें तो, सुचारू विश्लेषण पूरी तरह से सबसे खराब स्थिति पर ध्यान केंद्रित करने के बजाय ग्राफ़ में कनेक्शन में छोटे यादृच्छिक गड़बड़ी का परिचय देता है। “यदि कोई एल्गोरिदम किसी भी इनपुट को बेतरतीब ढंग से परेशान करने के बाद अच्छा प्रदर्शन करता है, तो यह हमें बताता है कि खराब इनपुट 'दुर्लभ', 'नाज़ुक', या 'अस्थिर' हैं, जो इस बात का कुछ औचित्य देता है कि हम उन्हें व्यवहार में क्यों नहीं देखते हैं, क्वान बताते हैं। “कोई फर्क नहीं पड़ता कि हम किस ग्राफ़ से शुरू करते हैं, नोड्स के बीच कुछ किनारों या कनेक्शनों को बेतरतीब ढंग से फ़्लिप करने के बाद, हम दिखाते हैं कि रंग शोधन पर आधारित एल्गोरिदम बहुत कुशल हो जाते हैं।” यह बताता है कि क्यों रंग परिशोधन पर आधारित एल्गोरिदम व्यवहार में घातीय चलने वाले समय में 'फंसने' की प्रवृत्ति नहीं रखते हैं।
एक पेचीदा समस्या से “कोई समस्या नहीं” तक''
एक जादुई एल्गोरिदम खोजने से दूर, जो किसी भी ग्राफ़ की तुलना कर सकता है, यहां तक कि सबसे खराब स्थिति में भी, आईएसटीए शोधकर्ताओं ने इस दर्शन को समझने की कोशिश की कि कुछ एल्गोरिदम व्यवहार में क्यों काम करते हैं। इस प्रकार, उनका लक्ष्य कम्प्यूटेशनल रूप से कठिन समस्या का गणितीय अर्थ निकालना था। सहज विश्लेषण के साथ रंग परिशोधन को जोड़कर, अनास्टोस और उनके सहयोगियों ने दिखाया कि मौजूदा एल्गोरिदम के लिए समस्याएं पैदा करने वाले ग्राफ़ की संरचना बेहद नाजुक होती है। जैसे ही वे इस संरचना से विचलित हुए, एल्गोरिदम ने और अधिक कुशलता से प्रदर्शन किया। अनास्टोस ने निष्कर्ष निकाला, “हम यह साबित करने के एक कदम और करीब आ रहे हैं कि ग्राफ आइसोमोर्फिज्म समस्या वास्तव में हल करना आसान है।”
प्रकाशन:
माइकल अनास्टोस, मैथ्यू क्वान और बेंजामिन मूर। 2024. ग्राफ समरूपता के लिए सुचारु विश्लेषण.arXiv. डीओआई: 10.48550/arXiv.2410.06095
