🤖 AI

GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning

GraphDC एक डिवाइड-एंड-कॉन्कर (विभाजन और विजय) मल्टी-एजेंट फ्रेमवर्क है जो जटिल ग्राफों को विशेष स्थानीय प्रसंस्करण और पदानुक्रमित एकीकरण के लिए छोटे उप-ग्राफों में विघटित करके स्केलेबल ग्राफ एल्गोरिदम तर्क को बढ़ाता है, जिससे यह विशेष रूप से बड़े पैमाने के इंस्टेंसों पर मौजूदा विधियों से बेहतर प्रदर्शन करता है।

मूल लेखक: Wenjin Li, Jiaming Cui

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

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

CC BY 4.0

मूल लेखक: Wenjin Li, Jiaming Cui

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

कल्पना कीजिए कि आप धागे की एक विशाल, उलझी हुई गांठ को सुलझाने की कोशिश कर रहे हैं जो कनेक्शनों के एक जटिल मानचित्र (एक "ग्राफ") का प्रतिनिधित्व करती है। यदि आप एक अकेले व्यक्ति (एक मानक AI मॉडल) से पूरे गांठ को एक साथ देखने और यह बताने के लिए कहते हैं कि दो विशिष्ट बिंदु आपस में कैसे जुड़े हैं, तो वह संभवतः घबरा जाएगा। उसका मस्तिष्क एक बार में बहुत सारी जानकारी को संभाल नहीं सकता है, और जैसे-जैसे गांठ बड़ी और जटिल होती जाती है, वह गलतियाँ करने लगता है या हार मान लेता है।

यही वह समस्या है जिसे GraphDC पेपर हल करने की कोशिश करता है।

समस्या: "एक मस्तिष्क" की बाधा (The "One Brain" Bottleneck)

लेखक बताते हैं कि जबकि आधुनिक AI (लार्ज लैंग्वेज मॉडल्स) कई चीजों में माहिर है, लेकिन यह बड़े, जटिल मानचित्रों के साथ संघर्ष करता है। जब मानचित्र बहुत बड़ा हो जाता है, तो AI एक ही समय में अपने दिमाग में हर एक कनेक्शन को ट्रैक करने की कोशिश करता है। यह एक शहर की पूरी जनसंख्या को याद रखने जैसा है ताकि दो घरों के बीच का सबसे छोटा रास्ता खोजा जा सके; आप विवरणों में खो जाएंगे।

समाधान: "विभाजित करो और जीतो" की टीम (The "Divide and Conquer" Team)

लेखक एक नया सिस्टम प्रस्तावित करते हैं जिसे GraphDC कहा जाता है। एक अकेले AI से सारा काम करवाने के बजाय, वे एक साथ काम करने वाली एआई एजेंटों की एक टीम का उपयोग करते हैं जो एक सुव्यवस्थित निर्माण दल (construction crew) की तरह काम करती है। वे "डिवाइड एंड कॉन्कर" (विभाजित करो और जीतो) नामक रणनीति का उपयोग करते हैं।

यह टीम कैसे काम करती है, इसे सिटी प्लानिंग (नगर नियोजन) के उदाहरण से समझते हैं:

स्प्लिटर (द सिटी प्लानर - द सिटी प्लानर):
सबसे पहले, एक "स्प्लिटर" विशाल, अव्यवस्थित मानचित्र को देखता है और उसे छोटे, प्रबंधनीय मोहल्लों (सबग्राफ्स) में काट देता है। यह एक बड़े शहर के मानचित्र को लेकर उसे अलग-अलग पिन कोड (zip codes) में काटने जैसा है।
लोकल एजेंट (द नेबरहुड इंस्पेक्टर्स - द नेबरहुड इंस्पेक्टर्स):
पूरे शहर की जांच करने के लिए एक व्यक्ति के बजाय, सिस्टम प्रत्येक मोहल्ले के लिए एक विशेष "इंस्पेक्टर" (एक AI एजेंट) नियुक्त करता है।

इंस्पेक्टर A केवल मोहल्ला 1 को देखता है।
इंस्पेक्टर B केवल मोहल्ला 2 को देखता है।
क्योंकि उन्हें केवल एक छोटे क्षेत्र पर ध्यान केंद्रित करना होता है, वे भ्रमित हुए बिना अपना काम बहुत सटीकता से कर सकते हैं। वे "क्या आप घर 27 से इस मोहल्ले के किनारे तक पहुँच सकते हैं?" जैसे सरल प्रश्नों के उत्तर देते हैं।

मास्टर एजेंट (द सिटी मेयर - द सिटी मेयर):
एक बार जब स्थानीय निरीक्षक अपना काम पूरा कर लेते हैं, तो वे अपनी छोटी, स्पष्ट रिपोर्ट एक "मेयर" (मास्टर एजेंट) को भेजते हैं।

मेयर को हर सड़क को देखने की आवश्यकता नहीं होती है।
मेयर को केवल मोहल्लों के बीच के कनेक्शनों (उन पुलों या सड़कों को जो मोहल्ला 1 को मोहल्ला 2 से जोड़ते हैं) को देखने और निरीक्षकों की रिपोर्टों को जोड़ने की आवश्यकता होती है।
इन स्थानीय उत्तरों को एक साथ जोड़कर, मेयर बड़े प्रश्न का उत्तर निकाल सकता है (जैसे, "क्या आप मोहल्ला 1 के घर 27 से मोहल्ला 2 के घर 97 तक पहुँच सकते हैं?")।

यह बेहतर क्यों काम करता है

पेपर का दावा है कि यह टीम वाला दृष्टिकोण "एक मस्तिष्क" वाले दृष्टिकोण की तुलना में दो मुख्य कारणों से बहुत बेहतर है:

कम बोझ (Less Overload): बड़े समस्या को छोटे टुकड़ों में तोड़कर, किसी भी अकेले AI को एक बार में बहुत अधिक जानकारी अपने दिमाग में रखने की आवश्यकता नहीं होती है।
बड़े मानचित्रों पर बेहतर सटीकता (Better Accuracy on Big Maps): लेखकों ने विभिन्न आकारों के ग्राफ पर इसका परीक्षण किया। उन्होंने पाया कि जब मानचित्र छोटे थे, तो एकल AI ठीक था। लेकिन जैसे-जैसे मानचित्र विशाल और सघन होते गए, एकल AI का प्रदर्शन गिर गया (वह अनुमान लगाने लगा)। हालाँकि, GraphDC टीम सबसे बड़े, सबसे जटिल मानचित्रों पर भी सटीक बनी रही।

पेपर से एक वास्तविक उदाहरण

पेपर एक ग्राफ में 100 नोड्स (बिंदुओं) के साथ दो बिंदुओं के बीच कनेक्शन की जाँच करने का एक विशिष्ट उदाहरण देता है।

पुराना तरीका: एक एकल AI पूरे मानचित्र में बिंदु A से बिंदु B तक एक पथ को ट्रेस करने की कोशिश करता है। वह बीच में ही खो जाता है और कहता है, "नहीं, वे जुड़े हुए नहीं हैं," भले ही वे वास्तव में जुड़े हों।
GraphDC का तरीका:
1. मानचित्र को दो क्लस्टरों में विभाजित किया जाता है।
2. एजेंट 1 जाँचता है कि क्या बिंदु A अपने क्लस्टर के "निकास" (exit) तक पहुँच सकता है। (हाँ)।
3. एजेंट 2 जाँचता है कि क्या क्लस्टर 2 का "प्रवेश" (entry) बिंदु B तक पहुँच सकता है। (हाँ)।
4. मास्टर एजेंट देखता है कि क्लस्टर 1 का निकास क्लस्टर 2 के प्रवेश से जुड़ता है।
5. निष्कर्ष: हाँ, वे जुड़े हुए हैं!

मुख्य निष्कर्ष (The Bottom Line)

पेपर निष्कर्ष निकालता है कि एक अकेले प्रतिभाशाली व्यक्ति के बजाय विशेषज्ञों की एक टीम के रूप में कार्य करके, AI बहुत कठिन ग्राफ समस्याओं को हल कर सकता है। उन्होंने केवल यह नहीं कहा कि यह सिद्धांत में काम करता है; उन्होंने प्रयोग चलाकर दिखाया कि GraphDC मौजूदा तरीकों को मात देता है, विशेष रूप से जब ग्राफ बड़े और कठिन होते जाते हैं। यह AI को बिना थके जटिल, बड़े पैमाने की पहेलियों को संभालने में मदद करने का एक व्यावहारिक तरीका है।

तकनीकी सारांश: GraphDC

समस्या विवरण

यद्यपि लार्ज लैंग्वेज मॉडल्स (LLMs) ने गणितीय तर्क में अपनी क्षमता प्रदर्शित की है, लेकिन ग्राफ एल्गोरिदम कार्यों पर उनका प्रदर्शन असंतोषजनक बना हुआ है, विशेष रूप से जैसे-जैसे ग्राफ का आकार और घनत्व बढ़ता है। ग्राफ जटिल टोपोलॉजिकल संरचनाएं रखते हैं जिनमें निर्भरताओं को ट्रैक करने और संरचनात्मक निरंतरता बनाए रखने के लिए व्यवस्थित, बहु-चरणीय तर्क की आवश्यकता होती है। मौजूदा विशिष्ट ग्राफ मॉडल अक्सर सामान्यीकरण और लचीलेपन की कमी प्रदर्शित करते हैं, जिन्हें कार्य-विशिष्ट डिजाइनों की आवश्यकता होती है। इसके विपरीत, साधारण (vanilla) LLM दृष्टिकोण स्केलेबिलिटी संबंधी समस्याओं से ग्रस्त होते हैं; जैसे-जैसे ग्राफ का आकार बढ़ता है, सीमित संदर्भ विंडो (context window) के भीतर मल्टी-हॉप निर्भरताओं को ट्रैक करने और तार्किक संचालन निष्पादित करने की मॉडल की क्षमता तेजी से घट जाती है। इसके अलावा, मौजूदा मल्टी-एजेंट समाधान (जैसे, प्रत्येक नोड के लिए एक एजेंट असाइन करना) अत्यधिक समन्वय लागत और कम्प्यूटेशनल बाधाएं उत्पन्न करते हैं, जिससे वे बड़े पैमाने के उदाहरणों के लिए अव्यावहारिक हो जाते हैं।

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

इन सीमाओं को दूर करने के लिए, लेखक GraphDC का प्रस्ताव करते हैं, जो स्केलेबल ग्राफ एल्गोरिदम तर्क के लिए डिज़ाइन किया गया एक 'डिवाइड-एंड-कॉन्कर' (विभाजन और विजय) मल्टी-एजेंट सिस्टम है। यह फ्रेमवर्क दो प्राथमिक चरणों में कार्य करता है:

1. ग्राफ-क्वेरी अपघटन (Graph-Query Decomposition)

इनपुट ग्राफ $G = (V, E)$ और रीजनिंग क्वेरी $Q$ को प्रबंधनीय उप-समस्याओं में विभाजित किया जाता है:

ग्राफ स्प्लिटिंग (Graph Splitting): एक ग्राफ स्प्लिटर $S$ मूल ग्राफ को $n$ छोटे सबग्राफों $\{g^{(i)}\}_{i=1}^n$ में विभाजित करता है। स्प्लिटिंग रणनीति को हल्का और विधि-स्वतंत्र (method-agnostic) बनाया गया है, जो नोड्स को सबग्राफ में क्लस्टर करती है और एग्जिट नोड्स ( $g^{(i)}_{exit}$ )—वे नोड्स जो अन्य सबग्राफ से जुड़ते हैं—की पहचान करती है।
इंटर-सबग्राफ पहचान (Inter-subgraph Identification): सिस्टम स्पष्ट रूप से इंटर-सबग्राफ किनारों ( $E_{inter}$ ) की पहचान करता है जो विभाजित घटकों के बीच संरचनात्मक निर्भरता को कैप्चर करते हैं।
सब-क्वेरी जनरेशन (Sub-query Generation): एक क्वेश्चन डिस्क्राइबर $D$ प्रत्येक सबग्राफ के लिए एक कार्य-जागरूक सब-क्वेरी $q^{(i)}$ उत्पन्न करता है। यह सब-क्वेरी सबग्राफ के एग्जिट नोड्स, वैश्विक कार्य विनिर्देश (global task specification) और एक प्रॉम्प्ट टेम्पलेट पर आधारित होती है, जिससे यह सुनिश्चित होता है कि स्थानीय एजेंट व्यापक संदर्भ के भीतर अपनी भूमिका को समझ सके।

2. पदानुक्रमित तर्क (Hierarchical Reasoning)

इस चरण में विशेषज्ञ एजेंटों द्वारा स्थानीय प्रसंस्करण के बाद वैश्विक एकीकरण शामिल है:

इंट्रा-सबग्राफ तर्क (Intra-subgraph Reasoning): प्रत्येक सबग्राफ $g^{(i)}$ को एक समर्पित सब-एजेंट को सौंपा जाता है। एजेंट सबग्राफ और उसकी सब-क्वेरी के आधार पर एक प्राकृतिक भाषा प्रतिक्रिया $a^{(i)}$ उत्पन्न करने के लिए एक LLM रीजनर $R$ का उपयोग करता है।
एक्सट्रैक्शन (Extraction): शोर और समन्वय ओवरहेड को कम करने के लिए, एक एक्सट्रैक्टर $E$ विस्तृत कच्ची प्रतिक्रिया को एक संक्षिप्त सब-आंसर ( $a^{(i)}_{extract}$ ) में सानित (distill) करता है, जिसमें केवल आवश्यक स्थानीय निष्कर्ष और संरचनात्मक तथ्य ही रखे जाते हैं।
इंटर-सबग्राफ सिंथेसिस (Inter-subgraph Synthesis): एक मास्टर एजेंट सभी निकाले गए सब-आंसर्स $\{a^{(i)}_{extract}\}$ को इंटर-सबग्राफ कनेक्टिविटी जानकारी $E_{inter}$ के साथ एकत्रित करता है। मास्टर एजेंट अंतिम वैश्विक उत्तर $A$ को संश्लेषित करने के लिए रीजनिंग मॉड्यूल $R$ का उपयोग करता है, जिससे उन निर्भरताओं को हल किया जाता है जो कई सबग्राफों में फैली हुई हैं, बिना पूरे ग्राफ को पुन: प्रोसेस किए।

मुख्य योगदान

पेपर तीन प्राथमिक योगदानों को रेखांकित करता है:

ग्राफ के लिए प्रथम डिवाइड-एंड-कॉन्कर MAS: लेखक पहला मल्टी-एजेंट सिस्टम (MAS) प्रस्तावित करते हैं जो व्यक्तिगत नोड्स को एजेंट असाइन करने के बजाय मूल ग्राफ को सबग्राफ में विभाजित करता है। यह दृष्टिकोण एजेंटों की संख्या और समन्वय ओवरहेड को कम करते हुए बड़े पैमाने की रीजनिंग समस्याओं को सहयोगात्मक रूप से हल करने में सक्षम बनाता है।
कार्य-अनुकूलित अपघटन एल्गोरिदम (Task-Tailored Decomposition Algorithm): एक विशेष ग्राफ अपघटन रणनीति पेश की गई है जो डाउनस्ट्रीम तर्क (reasoning) का समर्थन करने के लिए बनाई गई है। यह रणनीति ऐसे सबग्राफ बनाती है जो एजेंट-स्तरीय तर्क के लिए उपयुक्त हैं और स्थानीय समाधानों को वैश्विक उत्तर में एकीकृत करने की सुविधा प्रदान करती है।
स्केलेबिलिटी का अनुभवजन्य सत्यापन (Empirical Validation of Scalability): व्यापक प्रयोगों से पता चलता है कि यह फ्रेमवर्क चुनौतीपूर्ण ग्राफ रीजनिंग कार्यों पर मजबूत प्रदर्शन करता है, जो मौजूदा बेसलाइन्स की तुलना में, विशेष रूप से बड़े और घने ग्राफों पर, सटीकता और स्केलेबिलिटी में महत्वपूर्ण सुधार दिखाता है।

प्रयोगात्मक परिणाम

लेखकों ने दो डेटासेट्स पर GraphDC का मूल्यांकन किया: मानक NLGraph डेटासेट और एक नया निर्मित डेटासेट जिसमें बड़े ग्राफ (100 नोड्स तक) और घने संरचनात्मक निर्भरताएं शामिल हैं। सिस्टम की तुलना GPT-4.1-mini का उपयोग करके बिना फाइन-ट्यूनिंग के Few-Shot और चेन-ऑफ-थॉट (CoT) बेसलाइन्स से की गई।

NLGraph पर प्रदर्शन: GraphDC ने कनेक्टिविटी, शॉर्टेस्ट पाथ और साइकिल डिटेक्शन कार्यों में बेसलाइन्स को लगातार पछाड़ दिया। विशेष रूप से, "हार्ड" कठिनाई स्तरों पर, GraphDC ने महत्वपूर्ण लाभ दिखाया (उदाहरण के लिए, CoT की तुलना में कनेक्टिविटी में 8% की वृद्धि और शॉर्टेस्ट पाथ सटीकता में 174% की वृद्धि)।
बड़े ग्राफों पर स्केलेबिलिटी: लेखकों के कस्टम डेटासेट पर, मौजूदा विधियों (Few-Shot और CoT) ने जैसे-जैसे ग्राफ का आकार 40-60 नोड्स से अधिक हुआ, सटीकता में भारी गिरावट देखी, जो अक्सर साइकिल डिटेक्शन और शॉर्टेस्ट पाथ कार्यों पर रैंडम गेसिंग (50% सटीकता) के करीब पहुँच गई। इसके विपरीत, GraphDC ने मजबूत प्रदर्शन बनाए रखा। 80-100 नोड्स वाले ग्राफों के लिए, GraphDC ने बेसलाइन्स की तुलना में शॉर्टेस्ट पाथ सटीकता में 190% तक का सापेक्ष सुधार और कनेक्टिविटी में 24% का सुधार हासिल किया।
केस स्टडी: दो स्पार्स क्लस्टर्स वाले 100-नोड के ग्राफ पर एक कनेक्टिविटी केस स्टडी ने दर्शाया कि जहाँ एक सिंगल एजेंट दूरस्थ नोड्स के बीच लॉन्ग-रेंज पाथ को ट्रैक करने में विफल रहा, वहीं GraphDC ने समस्या को स्थानीय पहुंच (reachability) जांच और एक हल्के वैश्विक एकत्रीकरण चरण में सफलतापूर्वक विभाजित किया, जिससे सही कनेक्टिविटी प्राप्त हुई।

महत्व और दावे

पेपर का दावा है कि GraphDC उन ग्राफ इंस्टेंस को संभालने के लिए एक व्यावहारिक दिशा प्रदान करता है जो मोनोलिथिक LLMs या नादान रूप से समन्वित मल्टी-एजेंट सिस्टम की प्रभावी रीजनिंग क्षमता से अधिक हैं। नोड-स्तर से सबग्राफ-स्तर के अपघटन की ओर शिफ्ट होकर, यह फ्रेमवर्क LLM-आधारित तर्क को अत्यधिक कम्प्यूटेशनल लागत के बिना बड़े और अधिक जटिल ग्राफों तक प्रभावी ढंग से स्केल करता है। लेखक दावा करते हैं कि उनका कार्य यह प्रदर्शित करता है कि संरचित मल्टी-एजेंट सहयोग, बड़े संरचनात्मक निर्भरताओं के बीच वैश्विक निरंतरता बनाए रखनी हो, तो स्केलेबल ग्राफ एल्गोरिदम तर्क के लिए एक व्यवहार्य और आशाजनक दृष्टिकोण है। भविष्य के कार्यों के लिए अधिक उन्नत अपघटन रणनीतियों का पता लगाने और फ्रेमवर्क को ग्राफ रीजनिंग कार्यों की एक विस्तृत श्रृंखला तक विस्तारित करने का सुझाव दिया गया है।