📊 statistics

Directed Graph Topology Inference via Graph Filter Identification

यह शोध पत्र लीनियर डिफ्यूजन डायनेमिक्स द्वारा उत्पन्न नोडल मापों से निर्देशित ग्राफ टोपोलॉजी (directed graph topologies) का अनुमान लगाने के लिए एक नवीन रूपरेखा प्रस्तावित करता है, जो पहले द्विघातीय आव्यूह समीकरणों (quadratic matrix equations) के माध्यम से एक ग्राफ कनवल्शनल फ़िल्टर की पहचान करता है और फिर उस स्पार्स ग्राफ-शिफ्ट ऑपरेटर को पुनर्प्राप्त करता है जो फ़िल्टर के साथ कम्यूट (commute) करता है, एक ऐसी विधि जिसे सिंथेटिक और वास्तविक दुनिया के डेटासेट दोनों पर मान्य किया गया है।

मूल लेखक: Rasoul Shafipour, Andrei Buciulea, Santiago Segarra, Antonio G. Marques, Gonzalo Mateos

प्रकाशित 2026-06-29

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

CC BY 4.0

मूल लेखक: Rasoul Shafipour, Andrei Buciulea, Santiago Segarra, Antonio G. Marques, Gonzalo Mateos

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

कल्पना कीजिए कि आप एक जासूस हैं जो एक शहर में एक गुप्त, एकतरफा सड़क प्रणाली (one-way street system) के लेआउट का पता लगाने की कोशिश कर रहे हैं, जहाँ आपने पहले कभी यात्रा नहीं की है। आप सड़कों को देख नहीं सकते, और आपके पास कोई नक्शा भी नहीं है। आपके पास केवल कुछ "ट्रेसर" (जैसे धुआं या रंग) हैं जिन्हें आप अलग-अलग समय पर सिस्टम में छोड़ते हैं, और आप देखते हैं कि वे कहाँ पहुँचते हैं।

यह शोध पत्र इस बारे में है कि कैसे उस छिपे हुए एकतरफा रास्तों के नक्शे (एक डायरेक्टेड ग्राफ) को केवल यह देखकर रिवर्स-इंजीनियर किया जा सकता है कि चीजें इसमें कैसे बहती हैं।

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

मुख्य समस्या: "ब्लैक बॉक्स" शहर

कई वास्तविक दुनिया के नेटवर्क में—जैसे इंटरनेट पर सूचना कैसे फैलती है, शहर में ट्रैफ़िक कैसे चलता है, या स्टॉक की कीमतें एक-दूसरे को कैसे प्रभावित करती हैं—कनेक्शन एकतरफा होते हैं। व्यक्ति A का ट्वीट व्यक्ति B को प्रभावित कर सकता है, लेकिन इसका उल्टा नहीं हो सकता।

लेखक इन एकतरफा कनेक्शनों को खोजना चाहते हैं। वे यह मानकर चलते हैं कि नेटवर्क एक डिफ्यूजन मशीन (diffusion machine) की तरह काम करता है:

आप कुछ "इनपुट" (जैसे कोई अफवाह या स्टॉक ट्रेड) डालते हैं।
नेटवर्क इसे चरणों की एक श्रृंखला (जैसे एक फ़िल्टर) के माध्यम से प्रोसेस करता है।
आपको एक "आउटपुट" (जैसे अफवाह का फैलना या स्टॉक की कीमत में बदलाव) मिलता है।

चुनौती यह है: आप इनपुट और आउटपुट को जानते हैं, लेकिन आप उस मशीन (नेटवर्क मैप) या रेसिपी (फ़िल्टर) को नहीं जानते जो मशीन के अंदर है।

दो-चरणीय जासूसी कार्य

लेखक इस पहेली को सुलझाने के लिए एक चतुर दो-चरणीय रणनीति का प्रस्ताव करते हैं।

चरण 1: "रेसिपी" (फ़िल्टर) को रिवर्स-इंजीनियर करना

सबसे पहले, वे मैप को अनदेखा करते हैं और उस रेसिपी को समझने की कोशिश करते हैं जिसका उपयोग मशीन इनपुट को आउटपुट में बदलने के लिए करती है।

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

चरण 2: "मैप" (टोपोलॉजी) खोजना

एक बार जब आपके पास रेसिपी (फ़िल्टर) आ जाती है, तो वे वास्तविक सड़कों (नेटवर्क टोपोलॉजी) को खोजने के लिए इसका उपयोग करते हैं।

उपमा: अब जब आप सॉस की रेसिपी जानते हैं, तो आप रसोई को देखते हैं ताकि यह देख सकें कि कौन से बर्तन और पैन (नोड्स) किन पाइपों (एजेस) से जुड़े हैं।
नियम: रेसिपी पाइपों के अनुरूप होनी चाहिए। यदि रेसिपी कहती है "A और B को मिलाएं," तो वहां A से B तक एक पाइप होना चाहिए। लेखक सबसे सरल मैप (वह जिसमें सबसे कम पाइप हों) की तलाश करते हैं जो उनकी रेसिपी को सही साबित करे। वे यह भी सुनिश्चित करते हैं कि पाइप केवल एक दिशा में जाएं, जो वास्तविक दुनिया की प्रकृति से मेल खाता हो।

"क्लोज्ड-लूप" अपग्रेड

शोध पत्र में इस विधि का एक "प्रो" संस्करण पेश किया गया है जिसे जॉइंट आइडेंटिफिकेशन (Joint Identification) कहा जाता है।

उपमा: चरण 1 और चरण 2 को अलग-अलग करने के बजाय, कल्पना कीजिए कि एक जासूस लगातार अपने सिद्धांत को अपडेट करता है। "ठीक है, मुझे लगता है कि मैप इस तरह का है, इसलिए रेसिपी इस तरह की होनी चाहिए। लेकिन रुकिए, यदि रेसिपी इस तरह की है, तो शायद मैप वास्तव में इस तरह का है।"
वे दोनों चरणों को एक-दूसरे से बात करने देते हैं। मैप का अनुमान रेसिपी को परिष्कृत करने में मदद करता है, और रेसिपी का अनुमान मैप को परिष्कृत करने में मदद करता है। यह "फीडबैक लूप" उन्हें पुराने तरीके की तुलना में कम नमूनों (कम डेटा) के साथ पहेली को हल करने की अनुमति देता है।

वास्तविक दुनिया के परीक्षण

लेखकों ने केवल कागज पर गणित नहीं किया; उन्होंने वास्तविक डेटा पर अपने "जासूसी कार्य" का परीक्षण किया:

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

यह क्यों महत्वपूर्ण है

पिछले तरीके ज्यादातर "दो-तरफा" संबंधों (जैसे दोस्ती जहाँ A, B को पसंद करता है और B, A को पसंद करता है) के लिए काम करते थे। यह शोध पत्र एक-तरफा संबंधों (जैसे एक बॉस द्वारा कर्मचारी को आदेश देना, या एक वायरस का व्यक्ति A से B तक फैलना) को समझने के लिए पहला मजबूत टूलकिट प्रदान करता है।

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

तकनीकी सारांश: ग्राफ फ़िल्टर की पहचान के माध्यम से निर्देशित ग्राफ टोपोलॉजी का अनुमान (Directed Graph Topology Inference)

समस्या विवरण
यह शोध पत्र रैखिक प्रसार गतिकी (linear diffusion dynamics) से उत्पन्न नोडल मापों से एक निर्देशित ग्राफ (digraph) की टोपोलॉजी का अनुमान लगाने की चुनौती को संबोधित करता है। पूर्ववर्ती कार्य, जो व्हाइट सिग्नल उत्तेजनाओं वाले अनडिरेक्टेड (undirected) ग्राफों पर केंद्रित थे, के विपरीत यह समस्या एक सामान्य परिवेश पर विचार करती है जहाँ:

अंतर्निهم नेटवर्क एक निर्देशित ग्राफ (directed graph) है जिसमें एक गैर-सममित (non-symmetric) ग्राफ-शिफ्ट ऑपरेटर (GSO), $S$ होता है।
प्रेक्षित संकेत (observed signals), $y$ , इनपुट संकेतों $x$ पर कार्य करने वाले एक ग्राफ कनवोल्यूशन फ़िल्टर (जो $S$ का एक बहुपद है) द्वारा उत्पन्न होते हैं।
इनपुट संकेत अनिवार्य रूप से व्हाइट नहीं होते; उनमें ज्ञात कोवेरिएंस मैट्रिसेस $C_{x,m}$ द्वारा वर्णित मनमाने सहसंबंध (arbitrary correlations) होते हैं।
फ़िल्टर गुणांक और ग्राफ संरचना अज्ञात हैं।

मुख्य कठिनाई इसलिए उत्पन्न होती है क्योंकि निर्देशित ग्राफों के लिए, GSO और प्रेक्षण कोवेरिएंस मैट्रिक्स एक साथ विकर्णीय (simultaneously diagonalizable) नहीं होते हैं, जिससे अनडिरेक्टेड ग्राफों के लिए मानक स्पेक्ट्रल-आधारित दृष्टिकोण लागू नहीं हो पाते। लक्ष्य सबसे स्पार्स (sparse) वैध GSO $S$ को पुनः प्राप्त करना है जो इनपुट के पूर्व सांख्यिकीय ज्ञान को देखते हुए प्रेक्षित डेटा की व्याख्या कर सके।

कार्यप्रणाली (Methodology)
लेखक एक दो-चरणीय अनुमान ढांचे (two-step inference framework) का प्रस्ताव करते हैं, जिसके बाद नमूना जटिलता (sample complexity) में सुधार के लिए एक संयुक्त अनुकूलन (joint optimization) दृष्टिकोण अपनाया जाता है।

चरण 1: एसिमेट्रिक डिफ्यूजन फ़िल्टर की पहचान (Asymmetric Diffusion Filter Identification)
- प्रारूपण (Formulation): समस्या को द्विघात मैट्रिक्स समीकरणों के एक निकाय के रूप में मॉडल किया गया है: $C_{y,m} = H C_{x,m} H^\top$ , जहाँ $H$ अज्ञात फ़िल्टर है और $C_{y,m}$ अनुमानित आउटपुट कोवेरिएंस है।
- पहचान क्षमता (Identifiability): लेखक स्थापित करते हैं कि फ़िल्टर $H$ (चिह्न अस्पष्टता तक) पहचान योग्य है यदि इनपुट कोवेरिएंस में पर्याप्त स्पेक्ट्रल विविधता हो। विशेष रूप से, थ्योरम 1 सिद्ध करता है कि $M=4$ प्रक्रियाओं के साथ, विशिष्ट क्रस्कल-रैंक (Kruskal-rank) शर्तों को पूरा करने और इनपुट आइगेनबेसिस के पर्याप्त रूप से भिन्न होने पर विशिष्टता (uniqueness) की गारंटी है।
- एल्गोरिदम: इस गैर-कॉन्वेक्स सिस्टम को हल करने के लिए, समस्या को स्टिफ़ल मैनिफोल्ड बाधाओं (रोटेशन मैट्रिसेस पर ऑर्थोगोनैलिटी बाधाएं) के अधीन एक स्मूथ क्वाड्रेटिक मिनिमाइजेशन के रूप में पुनर्गठित किया गया है। एक इनएक्सैक्ट अल्टरनेटिंग मिनिमाइजेशन (IAM) एल्गोरिदम विकसित किया गया है, जो मैनिफोल्ड-प्रतिबंधित चरों के लिए रीमानियन ग्रेडिएंट डिसेंट और फ़िल्टर $H$ के लिए क्लोज्ड-फॉर्म अपडेट का उपयोग करता है।
चरण 2: डाइग्राफ टोपोलॉजी अनुमान (Digraph Topology Inference)
- प्रारूपण: दिए गए अनुमानित फ़िल्टर $\hat{H}$ के आधार पर, लक्ष्य एक ऐसा स्पार्स GSO $S$ खोजना है कि $HS = SH $(कम्यूटेटिविटी/विनिमयता), जो यह सुनिश्चित करता है कि$ H$, $S$ का एक बहुपद है।
- एल्गोरिदम: इसे एक ढीले (relaxed) कम्यूटेटिविटी प्रतिबंध के साथ एक कॉनवेक्स $\ell_1$ -नॉर्म मिनिमाइजेशन समस्या के रूप में तैयार किया गया है। एक प्रॉक्सिमल ग्रेडिएंट (PG) एल्गोरिदम का उपयोग किया जाता है, जो स्पर्सिटी बाधा और संरचनात्मक बाधाओं (जैसे गैर-ऋणात्मक भार, कोई सेल्फ-लूप नहीं) को एक कस्टम प्रॉक्सिमल ऑपरेटर के माध्यम से कुशलतापूर्वक संभालता है।
संयुक्त पहचान (क्लोज्ड-लूप) (Joint Identification - Closed-Loop)
- प्रदर्शन में सुधार के लिए, लेखक एक संयुक्त प्रारूप प्रस्तावित करते हैं जो फ़िल्टर पहचान और टोपोलॉजी अनुमान के बीच बारी-बारी से कार्य करता है। यह "क्लोज्ड-लूप" दृष्टिकोण फ़िल्टर अनुमान को नियमित (regularize) करने और इसके विपरीत, टोपोलॉजी अनुमान को नियमित करने के लिए वर्तमान $S$ अनुमान का उपयोग करता है।
- अभिसरण (Convergence): एक प्रमाणित अभिसरण एल्गोरिदम (एल्गोरिदम 3) प्रस्तुत किया गया है, जो $S$ के लिए प्रॉक्सिमल ग्रेडिएंट स्टेप्स, मैनिफोल्ड चरों के लिए रीमानियन ग्रेडिएंट स्टेप्स और $H$ के लिए यूक्लिडियन ग्रेडिएंट स्टेप्स के बीच बारी-बारी से कार्य करता है। सैद्धांतिक विश्लेषण हल्के अनुमानों के तहत एक क्रिटिकल पॉइंट तक अभिसरण की पुष्टि करता है।

प्रमुख योगदान (Key Contributions)

निर्देशित ग्राफों के लिए सामान्यीकरण: यह कार्य ग्राफ फ़िल्टर पहचान को सममित (undirected) से एसिमेट्रिक (directed) ऑपरेटरों तक विस्तारित करता है, जो GSO और आउटपुट कोवेरिएंस की गैर-विकर्णीयता (non-diagonalizability) की समस्या को संबोधित करता है।
पहचान क्षमता सिद्धांत (Identifiability Theory): यह शोध पत्र कठोर स्थितियाँ (थ्योरम 1) प्रदान करता है जिनके तहत एक एसिमेट्रिक डिफ्यूजन फ़िल्टर को कई इनपुट-आउटपुट प्रक्रियाओं के सेकंड-ऑर्डर सांख्यिकी से अद्वितीय रूप से पहचाना जा सकता है, जो इनपुट में स्पेक्ट्रल विविधता की आवश्यकता पर प्रकाश डालता है।
नवीन एल्गोरिदम:
- स्टिफ़ल मैनिफोल्ड पर फ़िल्टर पहचान के लिए एक IAM एल्गोरिदम।
- स्पार्स निर्देशित टोपोलॉजी को पुनः प्राप्त करने के लिए एक प्रॉक्सिमल ग्रेडिएंट विधि।
- एक संयुक्त, क्लोज्ड-लूप एल्गोरिदम जो फ़िल्टर और टोपोलॉजी अनुमान को परस्पर सुदृढ़ करता है।
अभिसरण गारंटी: यह पेपर $\ell_1$ -स्पर्सिटी, मैनिफोल्ड बाधाओं और कम्यूटेटिविटी कपलिंग वाले संयुक्त गैर-कॉन्वेक्स समस्या के लिए कुर्डिका-लोजसिएज़ (KL) प्रॉपर्टी का उपयोग करते हुए एक अभिसरण विश्लेषण प्रदान करता है।

प्रायोगिक परिणाम (Experimental Results)
प्रस्तावित विधियों का सिंथेटिक डेटा और वास्तविक दुनिया के केस स्टडीज पर मूल्यांकन किया गया:

सिंथेटिक डेटा: अर्डोस-रेनी (Erdős–Rényi), बाराबासी-अल्बर्ट (Barabási–Albert), और स्टोकेस्टिक ब्लॉक मॉडल ग्राफों पर प्रयोगों से पता चलता है कि क्लोज्ड-लूप (संयुक्त) दृष्टिकोण, ओपन-लूप (दो-चरणीय) दृष्टिकोण की तुलना में काफी बेहतर प्रदर्शन करता है, विशेष रूप से जब इनपुट प्रक्रियाओं ( $M$ ) या नमूनों ( $P$ ) की संख्या सीमित होती है। संयुक्त विधि ओपन-लूप विधि की तुलना में कम नमूनों के साथ लगभग पूर्ण सपोर्ट रिकवरी प्राप्त करती है।
वास्तविक दुनिया का डेटा (शहरी गतिशीलता): न्यूयॉर्क शहर में उबर पिकअप डेटा पर लागू किए जाने पर, एल्गोरिदम ने एक निर्देशित गतिशीलता ग्राफ का अनुमान लगाया। अनडिरेक्टेड मॉडलों के विपरीत, प्रस्तावित विधि ने एसिमेट्रिक ट्रैफिक फ्लो को पकड़ा, जिसने मैनहट्टन से आवासीय बोरो और हवाई अड्डों की ओर प्रमुख आउटबाउंड फ्लो को सही ढंग से पहचाना, जो शाम के आवागमन के पैटर्न के अनुरूप है।
वास्तविक दुनिया का डेटा (पोर्टफोलियो अनुकूलन): स्टॉक डेटा का उपयोग करते हुए एक वित्तीय अनुप्रयोग में, प्रस्तावित विधि द्वारा अनुमानित ग्राफों ने इनवर्स-डिग्री और इनवर्स-आइजनवेक्टर सेंट्रैलिटी वेटिंग रणनीतियों के तहत, बेसलाइन (GFI, TITD) और यूनिफॉर्म एलोकेशन की तुलना में काफी अधिक रिटर्न वाले पोर्टफोलियो दिए।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि इसका प्राथमिक महत्व एक एकीकृत ढांचे को प्रदान करने में है जो निर्देशित नेटवर्क टोपोलॉजी अनुमान के लिए ग्राफ स्टेशनैरिटी (जो समरूपता का तात्पर्य देता है) के प्रतिबंधात्मक अनुमान पर निर्भर नहीं करता है। ग्राफ फिल्टर और शिफ्ट ऑपरेटरों के बीच संरचनात्मक संबंध का लाभ उठाकर, यह विधि नेटवर्क में मौलिक कारण या दिशात्मक संबंधों को पुनः प्राप्त करती है।

लेखक नोट करते हैं कि हालांकि यह दृष्टिकोण प्रभावी है, लेकिन इसमें कुछ समझौते भी हैं: पहचान सुनिश्चित करने के लिए इसे एकाधिक इनपुट प्रक्रियाओं की आवश्यकता होती है और इसमें प्रति पुनरावृत्ति (iteration) क्यूबिक कम्प्यूटेशनल जटिलता ( $O(N^3)$ ) शामिल है। यह शोध पत्र स्वयं को उन अनुप्रयोगों के लिए एक पद्धतिगत प्रगति के रूप में प्रस्तुत करता है जहाँ दिशात्मकता महत्वपूर्ण है, जैसे कि कॉज़ल डिस्कवरी, परिवहन नेटवर्क और वित्तीय निर्भरता मॉडलिंग, जो सममित ग्राफ लर्निंग टूल के लिए एक अधिक सटीक विकल्प प्रदान करता है।