🤖 machine learning

GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories

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

मूल लेखक: Rahul Nandakumar, Deepayan Chakrabarti

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

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

CC BY 4.0

मूल लेखक: Rahul Nandakumar, Deepayan Chakrabarti

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

कल्पना कीजिए कि आपके पास लेगो (LEGO) सेट्स का एक डिब्बा है। कुछ किलों (castles) के हैं, कुछ अंतरिक्ष यान (spaceships) के हैं, और कुछ कारों के हैं। आप एक बिल्कुल नया लेगो सेट बनाना चाहते हैं जो आपके डिब्बे में मौजूद किलों की तरह ही दिखे और महसूस हो, लेकिन आपने कभी उनके निर्देश मैनुअल नहीं देखे हैं।

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

GraphWeave एक नया तरीका है जो पूरी तरह से अलग, अधिक स्मार्ट दृष्टिकोण अपनाता है। सीधे लेगो सेट बनाने के बजाय, यह पहले उन "डांस मूव्स" (नृत्य की मुद्राओं) को निर्धारित करता है जो लेगो के टुकड़ों द्वारा किए जाते हैं।

यह कैसे काम करता है, इसे सरल चरणों में यहाँ दिया गया है:

1. रैंडम वॉक का "डांस" (The "Dance" of the Random Walk)

कल्पना कीजिए कि आपने एक छोटे, अदृश्य रोबोट को एक लेगो किले पर गिरा दिया है। इस रोबोट के पास कोई नक्शा नहीं है; यह बस एक जुड़े हुए ब्रिक से दूसरे ब्रिक पर बेतरतीब ढंग से कूदता है।

अवलोकन (The Observation): यदि आप इस रोबोट को एक किले के ऊपर कूदने के लिए छोड़ देते हैं, तो यह टावरों या दीवारों के भीतर एक निश्चित लय (rhythm) में फंस जाता है। यदि आप इसे एक अंतरिक्ष यान पर छोड़ देते हैं, तो यह पूरी तरह से अलग लय में कूदता है।
ट्रैजेक्टरी (The Trajectory): यह रोबोट जिस रास्ते पर चलता है, उसे GraphWeave एक "रैंडम वॉक ट्रैजेक्टरी" कहता है। यह रोबोट के नृत्य का वीडियो रिकॉर्ड करने जैसा है। शोध का दावा है कि प्रत्येक ग्राफ प्रकार (किला, अंतरिक्ष यान, अणु) का अपना एक अद्वितीय "डांस सिग्नेचर" होता है।

2. डांस को उल्टा सीखना (Learning to Reverse the Dance)

शोधकर्ताओं ने एक एआई (विशेष रूप से एक "ट्रांसफॉर्मर", वही प्रकार का "दिमाग" जिसका उपयोग चैटबॉट्स में किया जाता है) को इन डांस वीडियो को देखने और पिछले कदम (step) की भविष्यवाणी करने के लिए प्रशिक्षित किया है।

यदि रोबक डांस के चरण 5 पर है, तो एआई सीखता है कि वह चरण 4 पर कहाँ था।
ऐसा बार-बार करने से, एआई इस विशिष्ट ग्राफ परिवार के लिए "डांस के नियमों" को सीख जाता है।

3. एक नया डांस बनाना (Creating a New Dance)

अब एक नया ग्राफ बनाने के लिए, GraphWeave एक खाली पन्ने से शुरुआत नहीं करता है। यह एक डांस के अंत (एक ऐसी अंतिम स्थिति जहाँ रोबोट स्वाभाविक रूप से उतरता है) से शुरू होता है और एआई को उल्टा (backwards) नाचने के लिए कहता है।

एआई चरण $k-1$ , फिर $k-2$ की भविष्यवाणी करता है, जब तक कि वह वापस शुरुआत तक नहीं पहुँच जाता।
यह एक बिल्कुल नया, वास्तविक "डांस वीडियो" (ट्रैजेक्टरी) बनाता है जो ऐसा लगता है जैसे उस ग्राफ परिवार से संबंधित हो जिसे आप बनाना चाहते हैं।

4. ग्राफ को बुनना (Weaving the Graph - "Weave" का अर्थ)

यही जादुई हिस्सा है। एक बार जब एआई ने ये नए डांस वीडियो बना लिए हैं, तो वह एक सरल प्रश्न पूछता है: "कौन सी लेगो संरचना एक रोबोट को ठीक इसी तरह नाचने के लिए मजबूर करेगी?"

यह एक गणितीय अनुकूलन उपकरण (mathematical optimization tool) का उपयोग करता है ताकि वह परफेक्ट ग्राफ खोज सके जो इन सभी उत्पन्न डांस मूवमेंट्स में पूरी तरह फिट बैठता हो।
एक-एक करके ब्रिक का अनुमान लगाने के बजाय, यह पूरे चित्र पर विचार करता है और सभी कनेक्शनों को एक साथ हल करता है। यह परिणाम को बहुत स्थिर बनाता है और त्रुटियों की संभावना को कम करता है।

यह बेहतर क्यों है?

यह कार्य GraphWeave की तीन मुख्य शक्तियों को उजागर करता है:

यह व्याख्या योग्य है (समझने में आसान): चूंकि यह विधि "रोबोट कैसे कूदता है" पर आधारित है, इसलिए हम वास्तव में देख सकते हैं कि एआई किन पैटर्न को सीख रहा है। यह कोई 'ब्लैक बॉक्स' नहीं है; यह एक मानचित्र है कि ग्राफ के माध्यम से सूचना कैसे प्रवाहित होती है।
यह बड़े चित्र को पकड़ता है: कई एआई तरीके छोटे विवरणों (जैसे "क्या यह ब्रिक उस एक से जुड़ता है?") में फंस जाते हैं और बड़े ढांचे (जैसे "क्या यह एक किला है या अंतरिक्ष यान?") को मिस कर देते हैं। GraphWeave बड़े पैमाने के ढांचे को पकड़ने में उत्कृष्ट है, जैसे कि समुदायों का निर्माण या नेटवर्क के माध्यम से यातायात का प्रवाह।
यह तेज़ है: यह कार्य दावा करता है कि GraphWeave अपने निकटतम प्रतिस्पर्धी से 10 गुना तेज़ है। यह हर एक ब्रिक को हाथ से तराशने के बजाय 3D प्रिंटर का उपयोग करने जैसा है।

उल्लेखित वास्तविक दुनिया के उदाहरण

इस कार्य का परीक्षण इन पर किया गया:

अणु (Molecules): ज्ञात दवाओं के समान नए रासायनिक संरचनाओं का निर्माण करना।
सोशल नेटवर्क (Social Networks): ऐसे नकली उपयोगकर्ता नेटवर्क बनाना जो वास्तविक दिखते हों (बॉट डिटेक्शन का परीक्षण करने के लिए उपयोगी)।
साइटेशन नेटवर्क (Citation Networks): यह मानचित्र बनाना कि वैज्ञानिक पेपर एक-दूसरे को कैसे संदर्भित करते हैं।

संक्षेप में: GraphWeave सीधे चित्र बनाने की कोशिश नहीं करता है। यह चित्र के भीतर गति के नियमों को सीखता है, गति के नए नियमों का एक सेट बनाता है, और फिर उस चित्र को बनाता है जो उन नियमों में पूरी तरह फिट बैठता है।

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

समस्या विवरण

यह कार्य एक अज्ञात परिवार के प्रशिक्षण ग्राफों (training graphs) के सेट से, उसी परिवार के नए ग्राफ उत्पन्न करने की चुनौती को संबोधित करता है। लक्ष्य प्रशिक्षण डेटा के अंतर्निहित संरचनात्मक पैटर्न को पकड़ना है—छोटे पैमाने के मोटिफ्स (जैसे अणुओं में बेंजीन रिंग) से लेकर बड़े पैमाने के गुणों (जैसे कम्युनिटी स्ट्रक्चर, डिग्री डिस्ट्रीब्यूशन) तक—और ऐसे नए ग्राफ बनाना है जो इन पैटर्न को प्रदर्शित करते हों।

मौजूदा दृष्टिकोण महत्वपूर्ण सीमाओं का सामना करते हैं:

एम्बेडिंग-आधारित डिफ्यूजन (Embedding-based Diffusion): ग्राफ एम्बेडिंग स्पेस में डिफ्यूज करने वाले तरीके अक्सर गैर-व्याख्यात्मक (non-interpretable) परिवर्तन उत्पन्न करते हैं; एम्बेडिंग स्पेस में छोटे बदलाव भी परिणामी ग्राफ में जटिल और अनैतिक संरचनात्मक संशोधनों का कारण बन सकते हैं।
डिस्क्रीट स्पेस में डिफ्यूजन (Diffusion in Discrete Space): नोड्स और एडजेस पर सीधे काम करने वाले तरीके अक्सर स्थानीय बदलाव (एज जोड़ना/हटाना) करते हैं जो व्यक्तिगत रूप से तो सहज हैं लेकिन विशिष्ट वैश्विक पैटर्न प्राप्त करने के लिए समन्वय करने में कठिन हैं। इसके विपरीत, वैश्विक बदलाव करने वाले तरीके लचीले तो हैं लेकिन इस संबंध में कोई व्याख्यात्मकता नहीं देते कि चरणों के अनुक्रम से कौन से पैटर्न उभरते हैं।
सामान्य मुद्दे: अधिकांश मौजूदा तरीके स्पष्ट रूप से या व्याख्यात्मक रूप से उनके द्वारा उत्पन्न मल्टी-स्केल पैटर्न को नियंत्रित करने में संघर्ष करते हैं, और उनमें से कई त्रुटियों के प्रति संवेदनशीलता या कम्प्यूटेशनल अक्षमता से ग्रस्त हैं।

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

GraphWeave एक नवीन दो-चरणीय ढांचे का प्रस्ताव करता है जो पैटर्न जनरेशन को ग्राफ कंस्ट्रक्शन से अलग करता है। सीधे ग्राफ या एम्बेडिंग्स पर डिफ्यूज करने के बजाय, यह रैंडम वॉक ट्राजेक्टरीज (RWTs) पर कार्य करता है।

1. मुख्य अवधारणा: स्मूद् रैंडम वॉक ट्राजेक्टरीज (RWTs)

विधि एक RWT को वेक्टर्स के एक अनुक्रम $\{v, Lv, L^2v, \dots, L^kv\}$ के रूप में परिभाषित करती है, जहाँ:

$A$ ग्राफ का एडजेसेंसी मैट्रिक्स (adjacency matrix) है।
$L$ एक स्मूद्ड नॉर्मलाइज्ड एडजेसेंसी मैट्रिक्स है: $L = (D')^{-1/2}((1-\alpha)A + \alpha I)(D')^{-1/2}$ , जहाँ $D'$ स्मूद्ड डिग्री को दर्शाता है और $\alpha$ एक स्मूथिंग पैरामीटर है जो सेल्फ-लूप्स पेश करता है।
$v$ एक स्टार्ट वेक्टर है जो $f(\cdot)$ नामक फंक्शन के माध्यम से नोड डिग्री से प्राप्त होता है।
ट्राजेक्टरी यह ट्रैक करती है कि $k$ स्टेप्स के रैंडम वॉक के दौरान एक वेक्टर कैसे विकसित होता है।

लेखक दिखाते हैं कि विभिन्न ग्राफ परिवार (जैसे Erdos-Renyi, Stochastic Block Models, Preferential Attachment) विशिष्ट RWT सिग्नेचर उत्पन्न करते हैं। महत्वपूर्ण रूप से, थ्योरम 1 बताता है कि बड़े $k$ के लिए RWT एक स्थिर वेक्टर $w$ की ओर अभिसरित (converge) होता है जो पूरी तरह से ग्राफ की नोड डिग्री पर निर्भर करता है। यह विशिष्ट ग्राफ संरचना के ज्ञान के बिना भी, एक डिग्री डिस्ट्रीब्यूशन से सैंपल करके एक यथार्थवादी "एंड वेक्टर" (end vector) बनाने में सक्षम बनाता है।

2. चरण 1: RWTs को रिवर्स करना सीखना (पैटर्न जनरेशन)

पहले चरण में वर्तमान स्टेप के दिए गए वर्तमान स्टेप के पिछले स्टेप की भविष्यवाणी करना सीखना शामिल है।

मॉडल: एक ट्रांसफार्मर आर्किटेक्चर को $v_{j+1}$ और फंक्शन $f$ और स्टेप इंडेक्स $j$ के दिए जाने पर $v_j$ की भविष्यवाणी करने के लिए प्रशिक्षित किया जाता है।
वेरिएबल साइज को संभालना: अलग-अलग आकार के ग्राफ को संभालने के लिए, इनपुट वेक्टर्स को एक बिनिंग फंक्शन $B(\cdot)$ और एक एम्बेडिंग $E(\cdot)$ का उपयोग करके प्रीप्रोसेस किया जाता है, जिससे ट्रांसफार्मर किसी भी लंबाई के अनुक्रम को प्रोसेस कर पाता है।
परम्यूटेशन इनवेरियंस (Permutation Invariance): मॉडल बिना पोजीशनल एम्बेडिंग या कॉज़ल मास्किंग के एक वैनिला ट्रांसफार्मर का उपयोग करता है, जो नोड रीऑर्डरिंग के प्रति अपरिवर्तनीयता सुनिश्चित करता है।
प्रशिक्षण उद्देश्य: सभी प्रशिक्षण RWTs में अनुमानित पिछले वेक्टर और वास्तविक पिछले वेक्टर के बीच मीन स्क्वेर्ड एरर (MSE) को कम करना।

3. चरण 2: RWTs उत्पन्न करना

एक बार जब रिवर्स प्रेडिक्टर $P$ प्रशिक्षित हो जाता है:

एक यथार्थवादी डिग्री डिस्ट्रीब्यूशन को सैंपल किया जाता है (उदाहरण के लिए, प्रशिक्षण ग्राफ की डिग्री को बदलकर या पावर लॉ को फिट करके)।
थ्योरम 1 (उपयोग करके) के आधार पर एक एंड वेक्टर $\bar{v}_k$ बनाया जाता है।
पूर्ण ट्राजेक्टरी $\{\bar{v}_1, \dots, \bar{v}_k\}$ उत्पन्न करने के लिए रिवर्स प्रेडिक्टर को पुनरावृत्त रूप से लागू किया जाता है: $\bar{v}_{k-1} = P(\bar{v}_k)$ , $\bar{v}_{k-2} = P(\bar{v}_{k-1})$ , आदि।
फंक्शन $f$ में भिन्नता लाकर एक ही एंड वेक्टर से कई ट्राजेक्टरीज उत्पन्न की जा सकती हैं।

4. चरण 3: ग्राफ इन्फरेंस (ऑप्टिमाइजेशन)

अंतिम चरण उत्पन्न RWTs के लिए सबसे उपयुक्त ग्राफ संरचना को पुनर्गठित करता है।

फॉर्मूलेशन: समस्या को एक एडजेसेंसी मैट्रिक्स $A$ खोजने के रूप में तैयार किया गया है ताकि स्मूद्ड नॉर्मलाइज्ड एडजेसेंसी $L$ इस शर्त को पूरा करे कि सभी उत्पन्न ट्राजेक्टरीज के लिए $L\bar{v}_j \approx \bar{v}_{j+1}$ हो।
ऑप्टिमाइजेशन: इसे एक इंटीजर लीनियर प्रोग्राम (ILP) के रूप में तैयार किया गया है जो $A$ के बाइनरी, सिमेट्रिक, जीरो डायगोनल होने और प्री-सैंपल की गई डिग्री डिस्ट्रीब्यूशन से मेल खाने की बाधाओं के अधीन, अनुमानित ट्रांजिशन और वास्तविक ट्रांजिशन के बीच के एरर को कम करता है।
रिलैक्सेशन (Relaxation): एक तेज़ विकल्प के रूप में, एक कॉनवेक्स रिलैक्सेशन (जहाँ $A_{ij} \in \{0,1\}$ को $[0,1]$ में बदला जाता है) के बाद थ्रेशोल्डिंग स्टेप प्रस्तावित किया गया है, हालांकि ILP अधिक सटीकता प्रदान करता है।

मुख्य योगदान

नवीन फॉर्मूलेशन: GraphWeave पहला ऐसा तरीका है जो ग्राफ जनरेशन को दो-चरणीय प्रक्रिया के रूप में तैयार करता है: यथार्थवादी पैटर्न बनाना (RWTs के माध्यम से) और उसके बाद उन्हें फिट करने के लिए ग्राफ का अनुकूलन करना। यह पैटर्न पहचान को संरचनात्मक निर्माण से अलग करता है।
व्याख्यात्मकता (Interpretability): अपने जनरेशन को रैंडम वॉक ट्राजेक्टरीज पर आधारित करके, यह विधि स्वाभाविक रूप से व्याख्यात्मक है। RWTs यह कैप्चर करते हैं कि वेक्टर्स (जैसे विचार, प्रवाह) कैसे विकसित होते हैं, जो कई ग्राफ-सिद्धांतिक अनुप्रयोगों के लिए एक केंद्रीय अवधारणा है।
मल्टी-स्केल स्ट्रक्चर को कैप्चर करना: यह विधि प्रभावी ढंग से स्थानीय संरचनाओं (विशिष्ट $f$ के चयन के माध्यम से) और बड़े पैमाने की संरचनाओं (कम्युनिटीज, कट्स, फ्लो, डिग्री डिस्ट्रीब्यूशन) दोनों को कैप्चर करती है, क्योंकि RWTs स्वाभाविक रूप से इन गुणों को एनकोड करते हैं।
मजबूती (Robustness): सभी एज को कई RWTs को फिट करने के लिए संयुक्त रूप से ऑप्टिमाइज़ करके, यह विधि ट्राजेक्टरी जनरेशन प्रक्रिया की त्रुटियों के प्रति मजबूत है।
सरलता और दक्षता: इसका कार्यान्वयन केवल मानक ऑफ-द-शेल्फ टूल्स (एक ट्रांसफार्मर और एक मानक ऑप्टिमाइज़र) पर निर्भर करता है। यह अपने सबसे प्रत्यक्ष प्रतिस्पर्धी (DiGress) की तुलना में 10 गुना तेज़ होने की रिपोर्ट किया गया है।

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

लेखकों ने चार सिम्युलेटेड डेटासेट्स (Stochastic Block Models, Watts-Strogatz, Barabasi-Albert, Expected Degree Random Graphs) और पांच रियल-वर्ल्ड बेंचमार्क्स (Cora, Citeseer, Pubmed, Proteins, QM9) पर GraphWeave का मूल्यांकन किया।

प्रदर्शन: GraphWeave ने लगातार स्टेट-ऑफ-द-आर्ट तरीकों (DiGress, GSDM, GRASP, GDSS, GraphRNN) को पछाड़ दिया।
मेट्रिक्स: सबसे महत्वपूर्ण सुधार बड़े पैमाने के स्ट्रक्चरल मेट्रिक्स में देखे गए, जिनमें शामिल हैं:
- डिग्री डिस्ट्रीब्यूशन
- कट साइज़
- कंडक्टेंस और मॉडुलैरिटी (Conductance and Modularity)
- पेजरैंक डिस्ट्रीब्यूशन
- मैक्स-फ्लो और रेजिस्टेंस
- ORBIT स्कोर (लोकल नेबरहुड्स)
कनेक्टिविटी: अपने कुछ प्रतिस्पर्धियों (जैसे GSDM, GraphRNN) के विपरीत, जो अक्सर डिस्कनेक्टेड ग्राफ उत्पन्न करते हैं, GraphWeave ने लगातार कनेक्टेड ग्राफ बनाए।
गति: Graphwise ने डिफ्यूजन-आधारित प्रतिस्पर्धियों की तुलना में काफी तेज़ ट्रेनिंग और जनरेशन समय प्रदर्शित किया।
ऑप्टिमाइजेशन तुलना: ILP दृष्टिकोण ने RWT पुनर्निर्माण में कॉनवेक्स रिलैक्सेशन दृष्टिकोण की तुलना में 20–55% बेहतर सटीकता प्राप्त की।

महत्व और दावे

यह कार्य दावा करता है कि GraphWeave मौजूदा ग्राफ जनरेशन विधियों के लिए एक सरल, व्याख्यात्मक और मजबूत विकल्प प्रदान करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

पैटर्न और स्ट्रक्चर को अलग करना: पैटर्न के सांख्यिकीय जनरेशन (RWTs) को ग्राफ कंस्ट्रक्शन से अलग करके, यह विधि एम्बेडिंग डिफ्यूजन की "ब्लैक-बॉक्स" प्रकृति और डिस्क्रीट डिफ्यूजन की समन्वय समस्याओं से बचती है।
अनुप्रयोग प्रासंगिकता: चूंकि कई डाउनस्ट्रीम अनुप्रयोग (जैसे इन्फ्लुएंस मैक्सिमाइजेशन, कम्युनिटी डिटेक्शन, मॉलिक्यूलर प्रॉपर्टी प्रेडिक्शन) रैंडम वॉक पर निर्भर करते हैं, इसलिए सही RWT सिग्नेचर वाले ग्राफ उत्पन्न करना उनके लिए तत्काल उपयोगिता सुनिश्चित करता है।
स्केलेबिलिटी: मानक ऑप्टिमाइज़र और ट्रांसफार्मर पर इसकी निर्भरता कुशल स्केलिंग को सक्षम बनाती है, जो गुणवत्ता और गति दोनों में प्रतिस्पर्धियों से बेहतर प्रदर्शन करती है, विशेष रूप से बड़े पैमाने की ग्राफ संरचनाओं के लिए।

लेखक निष्कर्ष निकालते हैं कि GraphWeave सफलतापूर्वक ऐसे ग्राफ उत्पन्न करता है जो प्रशिक्षण डेटा के मल्टी-स्केल पैटर्न को दर्शाते हैं, जिससे यह व्याख्यात्मक और कुशल ग्राफ जनरेशन के लिए एक नया प्रतिमान (paradigm) पेश करता है।