🤖 machine learning

Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

यह शोध पत्र एक रैंडमाइज्ड रिफाइनमेंट एल्गोरिदम और एक शुद्धता-संरक्षण बैचिंग स्कीम को पेश करते हुए विशाल ग्राफों के लिए वीज़फाइलर-लेमैन स्थिर कलरिंग की गणना करने हेतु एक GPU-त्वरित दृष्टिकोण प्रस्तुत करता है, जो दो क्रमों (orders of magnitude) तक की गति वृद्धि प्राप्त करता है और 30 बिलियन से अधिक किनारों वाले वेब-स्केल ग्राफों के विश्लेषण को सक्षम बनाता है जो पहले अव्यवहार्य थे।

मूल लेखक: Filippo Biondi, Mirco Tribastone, Max Tschaikowski

प्रकाशित 2026-07-07

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

CC BY 4.0

मूल लेखक: Filippo Biondi, Mirco Tribastone, Max Tschaikowski

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

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

यह उस समस्या का मूल है जिसे यह शोध पत्र हल करता है। कंप्यूटर विज्ञान की दुनिया में, इसे वेइसफिलेर-लेमैन (1-WL) टेस्ट कहा जाता है। यह देखने का एक तरीका है कि एक कंप्यूटर प्रोग्राम (विशेष रूप से एक ग्राफ न्यूरल नेटवर्क) कितना "स्मार्ट" है कि वह नेटवर्क के विभिन्न हिस्सों के बीच अंतर कर सके। यदि प्रोग्राम दो लोगों के बीच अंतर नहीं कर पाता क्योंकि वे एक ही पैटर्न में फिट बैठते हैं, तो उन्हें एक ही "रंग" या लेबल मिल जाता है।

समस्या यह है: एक छोटे शहर के लिए यह करना आसान है। लेकिन एक ऐसे शहर के लिए जिसमें 30 बिलियन एजेस हैं (जैसे कि पूरा वेब), यह मौजूदा उपकरणों के साथ असंभव है। क्यों?

पुराना तरीका बहुत धीमा है: पारंपरिक तरीके ऐसे हैं जैसे एक अकेला लाइब्रेरियन हर किताब को एक-एक करके चेक करने की कोशिश कर रहा हो। वे क्रमिक (sequential) हैं और आधुनिक सुपर-फास्ट कंप्यूटरों (GPUs) का प्रभावी ढंग से उपयोग नहीं कर सकते।
मेमोरी की समस्या: इस जांच को करने के लिए, पुराने तरीकों को शहर का पूरा नक्शा एक ही समय में अपने दिमाग (RAM) में रखने की आवश्यकता होती है। किसी भी एक कंप्यूटर के पास 30-बिलियन-एज वाले नक्शे के लिए पर्याप्त मेमोरी नहीं है।

लेखक, फिलिपो बियोंडी, मिरको ट्रिबैस्टोन और मैक्स चास्काव्स्की ने इन दोनों समस्याओं को हल करने के लिए GPUs (गेमिंग कंप्यूटर और AI सर्वर में उपयोग होने वाली शक्तिशाली चिप्स) का उपयोग करके एक नई प्रणाली बनाई। उन्होंने इसे दो मुख्य ट्रिक्स के साथ किया था:

ट्रिक 1: "रैंडम गेस" गणित (रैंडमाइज्ड रिफाइनमेंट)

लाइब्रेरियन द्वारा हर एक नियम को एक-एक करके चेक करने के बजाय, नया तरीका एक गणितीय शॉर्टकट का उपयोग करता है।

उपमा: कल्पना कीजिए कि आप जानना चाहते हैं कि क्या दो समूह समान हैं। हर व्यक्ति का इंटरव्यू लेने के बजाय, आप शहर के हर व्यक्ति को एक रैंडम, अद्वितीय ID कार्ड बांट देते हैं। फिर, आप हर किसी से उनके दोस्तों के ID नंबरों को जोड़ने के लिए कहते हैं।
जादू: यदि दो लोगों के दोस्त बिल्कुल समान हैं, तो उन्हें बिल्कुल समान कुल योग (sum) प्राप्त होगा। यदि उनके दोस्त अलग हैं, तो योग लगभग निश्चित रूप से अलग होगा।
यह बेहतर क्यों है: पुराना तरीका "फ्लोटिंग-पॉइंट" गणित (जैसे दशमलव वाला कैलकुलेटर) का उपयोग करता है, जो बहुत बड़े नंबरों के मामले में गड़बड़ हो सकता है। यह नया तरीका एक विशेष "क्लॉक" सिस्टम (मॉड्यूलर अंकगणित) के भीतर पूर्णांक गणित (integer math) का उपयोग करता है। यह एक घड़ी के चेहरे पर गणित करने जैसा है जहाँ नंबर वापस शून्य पर आ जाते हैं। यह GPUs पर अविश्वसनीय रूप से तेज़ है और कुछ चतुर संभाव्यता गणित (probability math) के साथ, उन्होंने सिद्ध किया है कि यह 99.9999999% सटीक है। यह एक "रैंडमाइज्ड" अनुमान है जो इतना स्मार्ट है कि यह लगभग एक गारंटी है।

ट्रिक 2: "पजल पीस" रणनीति (बैचिंग)

तेज़ गणित के बावजूद, आप अभी भी एक सिंगल कंप्यूटर की मेमोरी में 30-बिलियन-एज का नक्शा नहीं समा सकते।

उपमा: कल्पना कीजिए कि आप एक विशाल जिग्सॉ पजल को हल करने की कोशिश कर रहे हैं, लेकिन आपके पास केवल एक छोटी मेज है। आप पूरे पजल को एक साथ नहीं बिछा सकते। इसलिए, आप पजल को छोटे, प्रबंधनीय टुकड़ों (बैच) में काट देते हैं।
सावधानी: यदि आप केवल प्रत्येक टुकड़े को अकेले हल करते हैं, तो आप उन किनारों पर गलतियाँ कर सकते हैं जहाँ टुकड़े आपस में जुड़ते हैं।
समाधान: लेखकों ने इस पजल को काटने और फिर से जोड़ने के लिए एक सख्त नियम विकसित किया।
1. उन्होंने एजेस को बैचों में विभाजित किया।
2. उन्होंने "आंतरिक" लोगों (जिनके दोस्त केवल उसी विशिष्ट टुकड़े के भीतर हैं) और "सीमावर्ती" लोगों (जिनके दोस्त अन्य टुकड़ों में हैं) की पहचान की।
3. वे पहले "आंतरिक" लोगों को हल करते हैं। "सीमावर्ती" लोगों को अभी के लिए अकेला छोड़ दिया जाता है, उन्हें अद्वितीय व्यक्तियों के रूप में माना जाता है।
4. एक बार जब एक टुकड़ा हल हो जाता है, तो वे इसे अपने स्वयं के एक छोटे, सरल संस्करण ("क्वोटिएंट ग्राफ") में छोटा कर देते हैं।
5. वे इस प्रक्रिया को दोहराते हैं, बार-बार पजल को छोटा करते जाते हैं, जब तक कि पूरा मामला उनकी मेज पर फिट न हो जाए।

यह सुनिश्चित करता है कि भले ही वे छोटे टुकड़ों पर काम कर रहे हों, अंतिम परिणाम पूरे शहर के लिए गणितीय रूप से सही होने की गारंटी देता है।

परिणाम: गति और पैमाना

शोध पत्र ने वास्तविक दुनिया के डेटा पर इसका परीक्षण किया, जिसमें विशाल वेब ग्राफ शामिल थे।

गति: उनका GPU सिस्टम पारंपरिक CPU तरीकों की तुलना में 138 गुना तक तेज़ था। कुछ ग्राफों पर, यह मल्टी-कोर CPU प्रयासों की तुलना में लगभग 450 गुना तेज़ था।
पैमाना: उन्होंने 30 बिलियन से अधिक एजेस वाले ग्राफों पर इन पैटर्न को सफलतापूर्वक कंप्यूट किया।
- वास्तविकता की जाँच: अन्य सभी तरीके, जो विशाल मेमोरी वाले शक्तिशाली सर्वरों पर चल रहे थे, इन ग्राफों का सामना करते ही क्रैश हो गए या समय समाप्त (timeout) हो गया। लेखकों की विधि ही एकमात्र थी जिसने काम पूरा किया।
सटीकता: जब उन्हें "पजल पीस" पद्धति का उपयोग करना पड़ा (क्योंकि ग्राफ एक बार में जाने के लिए बहुत बड़ा था), तो अंतिम परिणाम अभी भी आदर्श समूहीकरण के अविश्वसनीय रूप से करीब था—आमतौर पर आदर्श से 5% के भीतर।

सारांश

संक्षेप में, लेखकों ने एक ऐसी समस्या ली जो वर्तमान कंप्यूटरों के लिए बहुत बड़ी और बहुत धीमी थी। उन्होंने धीमे, त्रुटिपूर्ण "चेकलिस्ट" तरीके को एक तेज़, रैंडम-नंबर-आधारित गणितीय ट्रिक से बदल दिया जो GPUs पर पूरी तरह से चलता है। फिर, उन्होंने एक विशाल समस्या को छोटे-छोटे टुकड़ों में काटने का तरीका बनाया जिन्हें स्वतंत्र रूप से हल किया जा सकता है और बिना सटीकता खोए फिर से जोड़ा जा सकता है।

परिणाम? पहली बार, हम पूरे वेब की संरचना का विश्लेषण करने में सक्षम हैं ताकि हम देख सकें कि हमारे AI मॉडल कितने "स्मार्ट" हैं, जो कि पहले असंभव था।

तकनीकी सारांश: GPU के साथ विशाल ग्राफों पर Weisfeiler–Leman अभिव्यक्तता विश्लेषण को स्केल करना

समस्या विवरण
वेइसफिलेर-लेमन (1-WL) परीक्षण और उससे संबंधित स्थिर कलरिंग (stable coloring), ग्राफ न्यूरल नेटवर्क (GNNs) की अभिव्यक्त शक्ति को समझने के लिए मौलिक हैं। 1-WL स्थिर कलरिंग, ग्राफ संरचनाओं के बीच अंतर करने की मैसेज-पासिंग GNNs की क्षमता पर एक ऊपरी सीमा (upper bound) प्रदान करती है; समान स्थिर रंग प्राप्त करने वाले नोड्स ऐसे नेटवर्कों के लिए अविभेद्य होते हैं। हालाँकि, वास्तविक दुनिया के विशाल ग्राफों के लिए इस स्थिर कलरिंग की गणना करना दो महत्वपूर्ण बाधाओं का सामना करता है:

क्रमिक निष्पादन (Sequential Execution): विभाजन परिशोधन (partition refinement) पर आधारित शास्त्रीय एल्गोरिदम (जैसे कि $O(m \log n)$ स्प्लिटर-आधारित दृष्टिकोण) स्वाभाविक रूप से क्रमिक हैं और आधुनिक GPU आर्किटेक्चर की व्यापक समानांतर क्षमता (massive parallelism) का लाभ नहीं उठा सकते।
वैश्विक मेमोरी आवश्यकताएँ (Global Memory Requirements): इन एल्गोरिदमों के लिए पूरे ग्राफ का एक साथ मेमोरी में रहना आवश्यक है। यह "वैश्विक" प्रकृति उन वेब-स्केल ग्राफों (जैसे कि दस अरबों किनारों वाले ग्राफ) के विश्लेषण को रोकती है जो एकल डिवाइस या बड़े CPU क्लस्टरों की क्षमता से अधिक हैं।

समस्या को समानांतर या रैखिक बनाने के मौजूदा प्रयास अक्सर फ्लोटिंग-पॉइंट अंकगणित पर निर्भर करते हैं, जो बड़े पैमाने पर संख्यात्मक अस्थिरता (numerical instability) पैदा करता है, या वे डिवाइस मेमोरी से बड़े ग्राफों की मेमोरी बाधा को संबोधित करने में विफल रहते हैं।

कार्यप्रणाली
लेखक एक दो-आयामी दृष्टिकोण प्रस्तावित करते हैं जो 1-WL स्थिर कलरिंग के रैखिक-बीजगणितीय (linear-algebraic) व्याख्या का उपयोग करते हुए कंप्यूट स्केलेबिलिटी को मेमोरी स्केलेबिलिटी से अलग करता है।

1. यादृच्छिक रैखिक-बीजगणितीय परिशोधन (कंप्यूट स्केलेबिलिटी)
क्रमिक विभाजन परिशोधन के बजाय, लेखक समस्या को समतुल्य विभाजनों (equitable partitions) के अपवर्तनीय गुण (invariance property) का उपयोग करके पुनर्गठित करते हैं: एक विभाजन तब स्थिर होता है जब और केवल तभी जब एडजेसेंसी मैट्रिक्स के तहत किसी ब्लॉक-कॉस्टेंट वेक्टर का प्रतिबिंब भी ब्लॉक-कॉस्टेंट रहता है।

एल्गोरिदम: विधि वर्तमान विभाजन पर सममित (symmetric) यादृच्छिक वेक्टरों को नमूना लेती है, उन्हें एडजेसेंसी मैट्रिक्स से गुणा करती है ($z = Aw$), और परिणामी वेक्टर की समरूपता के आधार पर विभाजन को परिष्कृत करती है।
अंकगणितीय डोमेन: फ्लोटिंग-पॉइंट पावर इटरेशन से होने वाली संख्यात्मक अस्थिरता (जो बड़े ग्राफों पर गलत विलय का कारण बन सकती है) से बचने के लिए, एल्गोरिदम पूरी तरह से अनसाइंड 64-बिट पूर्णांक अंकगणित का उपयोग करते हुए मॉड्यूलर रिंग $\mathbb{Z}/2^{64}\mathbb{Z}$ के भीतर कार्य करता है।
सैद्धांतिक गारंटी: एडजेसेंसी मैट्रिक्स के रो-सम (row sums) को $2^{64}/2$ द्वारा सीमित करने की संरचनात्मक बाधा का लाभ उठाते हुए, लेखक एक संभावabilistic शुद्धता गारंटी प्राप्त करते हैं कि एक यादृच्छिक प्रोब (probe) किसी भी छूटे हुए परिशोधन का पता लगाने में अधिकतम $10^{-9}$ की विफलता संभावना के साथ काम करेगा, जो कि फील्ड (field) की आवश्यकता वाले शास्त्रीय श्वार्ट्ज-ज़िपल लेम्मा (Schwartz–Zippel lemma) को दरकिनार करता है।
GPU मैपिंग: मुख्य ऑपरेशन एक सिंगल स्पार्स मैट्रिक्स-वेक्टर मल्टीप्लिकेशन (SpMV) और उसके बाद एक लेक्सिकोग्राफिक सॉर्ट में बदल जाता है, जो GPU हार्डवेयर पर अत्यधिक कुशल हैं।

2. शुद्धता-संरक्षण बैचिंग (मेमोरी स्केलबिलिटी)
उन ग्राफों को संभालने के लिए जो डिवाइस मेमोरी में फिट नहीं होते हैं, लेखक एक बैचिंग योजना पेश करते हैं जो वैश्विक स्थिर कलरिंग की शुद्धता को बनाए रखते हुए किनारों के सेट को विसंयुक्त उपसमुच्चयों (disjoint subsets) में विभाजित करती है।

आंतरिक बनाम सीमावर्ती नोड्स (Inner vs. Boundary Nodes): किनारों के एक दिए गए बैच के लिए, नोड्स को "आंतरिक" (सभी निर्गत किनारे बैच के भीतर हैं) या "सीमावर्ती" (निर्गत किनारे बैच की सीमाओं को पार करते हैं) के रूप में वर्गीकृत किया जाता है।
स्थानीय परिशोधन: एल्गोरिदम प्रत्येक बैच को स्वतंत्र रूप से संसाधित करता है। महत्वपूर्ण रूप से, प्रत्येक बैच के लिए प्रारंभिक विभाजन सभी आंतरिक नोड्स को एक ही ब्लॉक में और सभी सीमावर्ती नोड्स को सिंगलटन ब्लॉक्स में रखता है। यह सुनिश्चित करता है कि परिशोधन केवल उन नोड्स को मर्ज करता है जिनकी पूर्ण पड़ोस संबंधी जानकारी उस बैच के भीतर उपलब्ध है।
पुनरावर्ती संकुचन (Iterative Contraction): स्थानीय परिशोधनों को एक वैश्विक विभाजन में मिलाया जाता है। एल्गोरिदम फिर एक कोटिएंट ग्राफ (जहाँ नोड्स वर्तमान विभाजन के ब्लॉक्स का प्रतिनिधित्व करते हैं) का निर्माण करता है और इस प्रक्रिया को दोहराता है।
समाप्ति: यह प्रक्रिया तब तक चलती है जब तक कि घटाया गया ग्राफ एक एकल बैच में फिट न हो जाए (जो कि प्रमाणित सबसे मोटे स्थिर कलरिंग को देता है) या एक फिक्स्ड पॉइंट तक न पहुँच जाए। यदि फिक्स्ड पॉइंट तक पहुँचने से पहले ग्राफ मेमोरी में फिट हो जाता है, तो परिणाम एक वैध स्थिर कलरिंग होता है जो सबसे मोटे वाले का परिशोधन (refinement) है।

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

यादृच्छिक परिशोधन एल्गोरिदम: एक मॉन्टे कार्लो फ्रेमवर्क जो सटीक पूर्णांक अंकगणित में संचालित होता है और टाइट संभाव्यता गारंटी ( $<10^{-9}$ त्रुटि) प्रदान करता है, जिससे फ्लोटिंग-पॉइंट विधियों के परिशुद्धता नुकसान से बचा जा सकता है।
बैचिंग योजना: एक अपघटन रणनीति जो स्वतंत्र किनारों के उपसमुच्च्यों को संसाधित करके और कोटिएंट ग्राफों के माध्यम से परिणामों को जोड़कर, डिवाइस मेमोरी से अधिक बड़े ग्राफों पर 1-WL गणना करने की अनुमति देती है, जो स्थिर कलरिंग गुण को प्रमाणित रूप से बनाए रखती है।
GPU कार्यान्वयन: एक CUDA-आधारित कार्यान्वयन जो इन एल्गोरिदम को सीधे GPU प्रिमिटिव्स (SpMV, सॉर्टिंग, रिडक्शन) पर मैप करता है, जिससे CPU बेसलाइन की तुलना में भारी गति मिलती है।

प्रायोगिक परिणाम
लेखकों ने ग्यारह मध्यम-पैमाने के ग्राफों और तीन वेब-स्केल ग्राफों (33-48 बिलियन किनारे) पर अपने दृष्टिकोण का मूल्यांकन किया।

शुद्धता: मध्यम-पैमाने के ग्राफों पर जहाँ पूरा ग्राफ मेमोरी में फिट बैठता है ( $N_b=1$ ), यादृच्छिक एल्गोरिदम ने सटीक सबसे मोटा स्थिर कलरिंग प्राप्त किया, जो नियतात्मक (deterministic) बेसलाइन से मेल खाता है।
संख्यात्मक स्थिरता: प्रस्तावित पूर्णांक-अंकगणित विधि ने उन नोड्स को सफलतापूर्वक अलग किया जिन्हें बड़े ग्राफों (जैसे कि it-2004 डेटासेट ने 800,000 से अधिक ब्लॉक्स का अंतर दिखाया) पर पिछले फ्लोटिंग-पॉइंट पावर-इटरेशन विधि द्वारा गलत तरीके से मर्ज कर दिया गया था।
बैचिंग गुणवत्ता: मेमोरी बाधाओं का अनुकरण करने के लिए कई बैचों ( $N_b=2, 4$ ) का उपयोग करने पर, परिणामी विभाजन अनुभवजन्य रूप से सबसे मोटे स्थिर कलरिंग के 5% के भीतर थे। कई डेटासेट्स के लिए, यह अंतर शून्य था।
प्रदर्शन:
- गति: सिंगल-GPU कार्यान्वयन ने शास्त्रीय सिंगल-थ्रेडेड CPU विभाजन परिशोधन पर 138x तक और मल्टीकोर CPU बेसलाइन पर 449x तक की गति प्राप्त की।
- स्केलेबिलिटी: 30 बिलियन से अधिक किनारों वाले वेब-स्केल ग्राफों पर, सभी CPU बेसलाइन (मल्टीकोर सिम्बोलिक रिडक्शन सहित) या तो समय समाप्त (timeout) हो गए या मेमोरी समाप्त हो गई। प्रस्तावित विधि ने इन उदाहरणों के लिए स्थिर कलरिंग सफलतापूर्वक कंप्यूट की, जिससे ब्लॉक्स की संख्या में ~39-46% की कमी आई।

महत्व और दावे
यह शोध दावा करता है कि यह कार्य 30 बिलियन से अधिक किनारों वाले वेब-स्केल ग्राफों पर 1-WL स्थिर कलरिंग को सफलतापूर्वक कंप्यूट करने वाला पहला कार्य है, जो मेमोरी और कंप्यूट सीमाओं के कारण पहले असंभव था। इसका महत्व है:

अभिव्यक्तता विश्लेषण को सक्षम बनाना: छोटे या मध्यम ग्राफों तक सीमित रहने के बजाय वास्तविक दुनिया के विशाल डेटासेट्स पर GNN अभिव्यक्तता का अनुभवजन्य विश्लेषण करने की अनुमति देना।
आर्किटेक्चरल फिट: यह प्रदर्शित करना कि 1-WL समस्या, जिसे पारंपरिक रूप से क्रमिक और वैश्विक माना जाता है, को GPU आर्किटेक्चर के अनुकूल रैखिक-बीजगणितीय स्वरूपों और बैचिंग रणनीतियों का उपयोग करके प्रभावी ढंग से समानांतर और वितरित किया जा सकता है।
मजबूती (Robustness): एक ऐसी विधि प्रदान करना जो संख्यात्मक रूप से स्थिर (पूर्णांक अंकगणित के माध्यम से) और मेमोरी-स्केलेबल (बैचिंग के माध्यम से) दोनों है, जो पूर्ववर्ती दृष्टिकोणों की विशिष्ट विफलता मोड को दूर करती है।

लेखक निष्कर्ष निकालते हैं कि उनकी विधि 1-WL अभिव्यक्तता विश्लेषण को उस स्तर पर सक्षम बनाती है जो पहले अप्राप्य था, साथ ही यह भी उल्लेख करते हैं कि स्थिर कलरिंग और समतुल्य विभाजनों के बीच पत्राचार भविष्य के डाउनस्ट्रीम ग्राफ ML कार्यों और गैर-रेखीय गतिशील प्रणालियों के लिए मॉडल रिडक्शन हेतु नई संभावनाएं प्रदान करता है।

ट्रिक 1: "रैंडम गेस" गणित (रैंडमाइज्ड रिफाइनमेंट)

ट्रिक 2: "पजल पीस" रणनीति (बैचिंग)

परिणाम: गति और पैमाना

सारांश

इसी तरह के और पेपर