📊 statistics

Active Learning on Adversarially Corrupted Graphs

यह शोध पत्र एक कुशल सक्रिय शिक्षण (active learning) एल्गोरिदम प्रस्तावित करता है जो ग्राफ के वर्टेक्स एक्सपेंशन (vertex expansion) और एडवर्सरी की शक्ति का लाभ उठाकर, कम वर्टेक्स एक्सपेंशन वाले सेट खोजने के लिए एक नवीन सम-वर्ग (sum-of-squares) आधारित दृष्टिकोण का उपयोग करते हुए, ग्राफ में प्रतिकूल रूप से दूषित (adversarially corrupted) वर्टिस को लगभग पुनर्प्राप्त करता है।

मूल लेखक: Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi, Emmanuel Esposito, Silvio Lattanzi

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

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

CC BY 4.0

मूल लेखक: Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi, Emmanuel Esposito, Silvio Lattanzi

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

कल्पना कीजिए कि आप एक विशाल, हलचल भरे शहर (ग्राफ) के प्रबंधक हैं। इस शहर के अधिकांश लोग ईमानदार नागरिक हैं जो एक अच्छी तरह से जुड़े हुए पड़ोस (मूल ग्राफ, $G^*$ ) में रहते हैं। हालाँकि, शरारती तत्वों (विरोधी) के एक समूह ने गुप्त रूप से उनके ठीक बगल में एक छिपा हुआ, नकली गाँव बनाया है। ये शरारती तत्व घुलने-मिलने और पकड़े बिना अराजकता फैलाने के लिए खुद को छिपाना चाहते हैं।

यहाँ समस्या यह है कि शरारती तत्व चतुर हैं। वे अपने नकली गाँव के अंदर जितने चाहें उतने रास्ते बना सकते हैं। वे ईमानदार नागरिकों से जोड़ने के लिए कुछ गुप्त सुरंगें भी बना सकते हैं। लेकिन एक शर्त है: वे ईमानदार नागरिकों से जुड़ने के लिए केवल सीमित संख्या में ही ये गुप्त सुरंगें बना सकते हैं। यदि वे बहुत अधिक सुरंगें बनाते हैं, तो शहर अचानक होने वाले इन अजीब कनेक्शनों पर ध्यान दे देगा।

आपका लक्ष्य उस नकली गाँव को खोजना और शरारती तत्वों की पहचान करना है। हालाँकि, आप केवल मानचित्र को देखकर ऐसा नहीं कर सकते; मानचित्र अव्यवसाजित है और शरारती तत्वों ने इसे विकृत कर दिया है। यह जानने का एकमात्र तरीका कि कोई व्यक्ति शरारती है या नहीं, उनसे सीधे पूछना ("लेबल क्वेरी") है। हालाँकि, लोगों से पूछना महंगा और समय लेने वाला है। आप कम से कम लोगों से पूछकर लगभग सभी बुरे लोगों को खोजना चाहते हैं।

शोध पत्र का समाधान: "एक्सपेंशन" जासूस

लेखकों, मार्को ब्रेसन और उनकी टीम ने इस समस्या को हल करने के लिए एक चतुर जासूसी एल्गोरिदम डिजाइन किया है। यह इस प्रकार काम करता है, सरल उपमाओं का उपयोग करते हुए:

1. "भीड़भाड़ बनाम विरल" नियम (वर्टेक्स एक्सपेंशन)
उनकी सफलता का रहस्य वर्टेक्स एक्सपेंशन (vertex expansion) की अवधारणा में निहित है। एक पड़ोस को घरों के एक समूह के रूप में सोचें।

उच्च विस्तार (High Expansion): यदि आप ईमानदार शहर में घरों का कोई भी समूह चुनते हैं, तो वे आमतौर पर उस समूह के बाहर के कई अन्य घरों से जुड़े होते हैं। यह एक व्यस्त बाजार चौक की तरह है जहाँ हर कोई एक-दूसरे को जानता है; आप आसानी से एक छोटे समूह को नहीं छिपा सकते क्योंकि वे कनेक्शनों से घिरे होते हैं।
निम्न विस्तार (Low Expansion): यदि घरों का एक समूह अलग-थलग है, जिसमें बाहर जाने के लिए बहुत कम सड़कें हैं, तो वहाँ छिपना आसान है।

शरारती तत्व एक "निम्न विस्तार" क्षेत्र बनाने की कोशिश करते हैं—एक छिपा हुआ गाँव जो आंतरिक रूप से मजबूती से जुड़ा हुआ है लेकिन बाहरी दुनिया के साथ उसके कनेक्शन बहुत कम हैं। लेखक सिद्ध करते हैं कि यदि ईमानदार शहर "अच्छी तरह से जुड़ा हुआ" (उच्च विस्तार) है, तो शरारती तत्व प्रभावी ढंग से नहीं छिप सकते जब तक कि वे बहुत कम संख्या में हों या उनकी गुप्त सुरंगें बहुत कम हों।

2. जासूस की रणनीति
एल्गोरिदम एक साथ सभी बुरे लोगों को खोजने की कोशिश नहीं करता है। इसके बजाय, यह "कमजोर कड़ी खोजने" का खेल खेलता है:

चरण 1: "ढीले सिरों" की तलाश करें। एल्गोरिदम शहर के मानचित्र को स्कैन करता है ताकि लोगों के एक ऐसे समूह को खोजा जा सके जिनके पास शेष शहर के मुकाबले बहुत कम कनेक्शन हैं, लेकिन वे आपस में बहुत अधिक जुड़े हुए हैं। यह घरों के एक ऐसे समूह को खोजने जैसा है जहाँ मुख्य शहर की ओर केवल एक या दो सड़कें जाती हैं।
चरण 2: "एसओएस" (SOS) परीक्षण। इसे कुशलतापूर्वक करने के लिए, एल्गोरिदम एक परिष्कृत गणितीय उपकरण (जिसे "सम-ऑफ-स्क्वायर्स" एल्गोरिदम कहा जाता है) का उपयोग करता है। इसे एक सुपर-पावर्ड आवर्धक लेंस (magnifying glass) के रूप में समझें जो सड़कों के जटिल जाल में तुरंत सबसे संदिग्ध, अलग-थलग समूहों का पता लगा सकता है।
चरण 3: "स्वाद परीक्षण" (सवाल पूछना)। एक बार जब एल्गोरिदम को एक संदिग्ध क्लस्टर मिल जाता है, तो वह यह मान नहीं लेता कि वहाँ मौजूद सभी लोग बुरे हैं। वह उस क्लस्टर से कुछ यादृच्छिक (random) लोगों को चुनता है और उनसे पूछता है, "क्या आप एक शरारती तत्व हैं?"
- यदि उत्तर "हाँ" है, तो पूरा क्लस्टर संभवतः नकली गाँव है।
- यदि उत्तर "नहीं" है, तो एल्गोरिदम को एहसास होता है कि उसने एक गलत अलार्म पाया है और वह आगे बढ़ जाता है।
चरण 4: दोहराएं। एक बार जब एक नकली गाँव की पहचान कर ली जाती है और उसे हटा दिया जाता है, तो शहर थोड़ा छोटा हो जाता है। एल्गोरिदम शेष मानचित्र पर इस प्रक्रिया को दोहराता है। क्योंकि ईमानदार शहर बहुत अच्छी तरह से जुड़ा हुआ है, नकली हिस्सों को हटाने से मानचित्र टूटता नहीं है; यह केवल शेष ईमानदार हिस्सों का विश्लेषण करना आसान बना देता है।

बड़ी खोज

शोध पत्र की मुख्य सफलता यह दिखाने में है कि आपको कितने प्रश्न पूछने की आवश्यकता है, यह दो चीजों पर निर्भर करता है:

शरारती तत्वों ने कितनी गुप्त सुरंगें बनाईं (उनका "बजट")।
ईमानदार शहर कितना अच्छी तरह से जुड़ा हुआ है (उसका "विस्तार")।

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

यह क्यों महत्वपूर्ण है (शोध पत्र के अनुसार)

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

उन्होंने एक नया टूल (प्रमेय 4) भी बनाया है जो किसी भी नेटवर्क में इन "ढीले" क्लस्टरों को खोजने में मदद करता है, जिसे वे मानते हैं कि शरारती तत्व वाली समस्या से स्वतंत्र रूप से भी उपयोगी है।

संक्षेप में: यह शोध पत्र हमें सिखाता है कि एक अच्छी तरह से जुड़े हुए संसार में, एक छोटे समूह के लिए बुरे तत्वों के रूप में छिपना बहुत कठिन है, बशर्ते हमारे पास उन कुछ "गुप्त दरवाजों" को पहचानने का एक स्मार्ट तरीका हो जिनका उपयोग वे दुनिया में प्रवेश करने के लिए करते हैं।

तकनीकी सारांश: प्रतिकूल रूप से दूषित ग्राफ पर सक्रिय शिक्षण (Active Learning)

समस्या का निरूपण
यह शोध पत्र उन ग्राफों पर सक्रिय शिक्षण (active learning) की समस्या को संबोधित करता है जहाँ अंतर्निहित संरचना के साथ एक प्रतिकूल (adversary) द्वारा छेड़छाड़ की गई है। इस परिवेश में एक प्रारंभिक "ग्राउंड-ट्रुथ" ग्राफ $G^* = (V^*, E^*)$ और दूषित (दुर्भावनापूर्ण) शीर्षों (vertices) का एक सेट $I$ शामिल है। एक प्रतिकूल पक्ष एक बजट $b$ के साथ, तीन चरणों के माध्यम से एक अंतिम ग्राफ $G$ का निर्माण करता है:

ताज़ा शीर्षों के एक सेट $I$ पर एक मनमाना सबग्राफ बनाना (जहाँ $|I| \le |V^*|$ )।
$V^*$ के अधिकतम $b$ शीर्षों को सेट $I$ से जोड़ना। यह प्रतिकूल की शक्ति को परिभाषित करता है: $G$ में $I$ के फ्रंटियर (frontier) का आकार $b$ द्वारा सीमित है (अर्थात, $|\partial_G(I)| \le b$ )।
$G^*$ के भीतर मनमाने ढंग से किनारे (edges) जोड़ना।

एल्गोरिदम परिणामी ग्राफ $G$ प्राप्त करता है और एक लेबल ऑरेकल (label oracle) $O_{G,I}$ तक पहुँच रखता है, जो यह प्रकट करता है कि क्वेरी किया गया शीर्ष $I$ का हिस्सा है या नहीं। लक्ष्य कमजोर रिकवरी (weak recovery) प्राप्त करना है: एक उपसमुच्चय $\hat{I}$ की पहचान करना ताकि सममित अंतर (symmetric difference) $|\hat{I} \triangle I| \le \gamma |V(G)|$ उच्च प्रायिकता के साथ हो सके, जिसमें लेबल क्वेरीज़ की न्यूनतम संख्या का उपयोग किया गया हो। चुनौती यह है कि $G^*$ और दूषित सबग्राफ $G[I]$ मनमाने हो सकते हैं, और प्रतिकूल ग्राफ की संरचना में महत्वपूर्ण हेरफेर कर सकता है, बशर्ते कि मूल ग्राफ से कनेक्शन की संख्या कम रहे।

कार्यप्रणाली
प्रस्तावित समाधान वर्टेक्स एक्सपेंशन (vertex expansion) के संरचनात्मक गुण और एक पुनरावर्ती (recursive) एल्गोरिद्मिक ढांचे पर निर्भर करता है।

संरचनात्मक अंतर्दृष्टि: मुख्य अंतर्ज्ञान यह है कि यदि दूषित शीर्षों का सेट $I$ , ग्राफ के "अच्छे" भागों की तुलना में काफी छोटा वर्टेक्स एक्सपेंशन रखता है, तो इसे अलग किया जा सकता है। विशेष रूप से, लेखक एक ऐसी स्थिति को परिभाषित करते हैं जहाँ $I$ , शेष ग्राफ के सापेक्ष "खराब विस्तार" (poorly expanding) वाला होता है। यदि $I$ एक विशिष्ट एक्सपेंशन गैप शर्त को पूरा करता है, तो कोई भी सेट $S$ जिसका बाउंड्री (boundary) छोटा है और आकार $I$ के तुल्य है, $I$ के साथ अत्यधिक सह-संबंधित (correlated) होगा।
एल्गोरिद्मिक कोर (Sum-of-Squares): ऐसे सेट $S$ को खोजने के लिए, लेखक सम-ऑफ-स्क्वायर्स (Sum-of-Squares - SoS) एल्गोरिदम को अनुकूलित करते हैं, विशेष रूप से Feige et al. (2005) द्वारा प्रस्तावित वर्टेक्स एक्सपेंशन के लिए सेमीडेफिनेट प्रोग्रामिंग (SDP) रिलैक्सेशन को संशोधित करते हैं।
- मानक वर्टेक्स एक्सपेंशन एल्गोरिदम अक्सर वापस किए गए सेट के आकार की गारंटी देने में विफल रहते हैं या ऐसे अप्रोक्सिमेशन फैक्टर प्रदान करते हैं जो इस विशिष्ट प्रतिकूल सेटिंग के लिए बहुत ढीले होते हैं।
- लेखक डिग्री-4 SoS रिलैक्सेशन के लिए एक नवीन राउंडिंग एल्गोरिदम (rounding algorithm) पेश करते हैं। यह राउंडिंग सुनिश्चित करती है कि आउटपुट सेट $S$ कार्डिनैलिटी बाधाओं (विशेष रूप से, $|S| = \Theta(|I|)$ ) को पूरा करता है जबकि एक छोटा बाउंड्री बनाए रखता है।
- यह अनुकूलन एल्गोरिदम को एक ऐसा सेट $S$ खोजने की अनुमति देता है जो आकार संबंधी बाधाओं के अधीन न्यूनतम वर्टेक्स एक्सपेंशन को अनुमानित (approximate) करता है, जो एक स्वतंत्र रुचि का परिणाम है (प्रमेय 4)।
पुनरावर्ती परिशोधन (Recursive Refinement): एल्गोरिदम पुनरावृत्ति में कार्य करता है:
- यह शेष दूषित शीर्षों के साथ अत्यधिक सह-संबंधित सेट $S$ खोजने के लिए SoS-आधारित प्रक्रिया का उपयोग करता है।
- यह निर्धारित करने के लिए कि कौन सा सेट दूषित नोड्स के बहुमत को धारण करता है, यह $S$ और इसके पूरक (complement) के एक छोटे यादृच्छिक नमूने (random sample) पर ऑरेकल को क्वेरी करता है।
- पहचाने गए सेट को ग्राफ से हटा दिया जाता है, और प्रक्रिया अवशेष ग्राफ (residual graph) पर दोहराई जाती है।
- लेखक सिद्ध करते हैं कि संरचनात्मक गुण (विशेष रूप से, शेष ग्राउंड-ट्रुथ ग्राफ का वर्टेक्स एक्सपेंशन) इन पुनरावृत्तियों के माध्यम से पर्याप्त रूप से संरक्षित रहते हैं, जिससे एल्गोरिदम उच्च अंश की पहचान होने तक दूषित नोड्स को रिकवर करना जारी रख सकता है।

मुख्य परिणाम
मुख्य योगदान प्रमेय 3 है, जो कमजोर रिकवरी के लिए क्वेरी जटिलता स्थापित करता है। एल्गोरिदम $(\gamma, \delta, q, b)$ -कमजोर रिकवरी प्राप्त करता है यदि:

क्वेरी बजट $q$ इस प्रकार स्केल होता है: $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$ ।
प्रतिकूल का बजट $b$ , ग्राउंड-ट्रुथ ग्राफ $G^*$ के वर्टेक्स एक्सपेंशन द्वारा सीमित है: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$ , जहाँ $\partial_{\eta n}(G^*)$ कम से कम $\eta n$ आकार के उपसमुच्चयों का न्यूनतम फ्रंटियर है।

अनिवार्य रूप से, आवश्यक क्वेरीज़ की संख्या प्रतिकूल के बजट $b$ के रैखिक (linear) में है और वांछित सटीकता $\gamma$ के व्युत्क्रमानुपाती (inversely proportional) है, बशर्ते कि प्रतिकूल का बजट ग्राफ की कनेक्टिविटी (वर्टेक्स एक्सपेंशन) के सापेक्ष छोटा हो।

इसके अतिरिक्त, प्रमेय 4 एक सहायक परिणाम प्रस्तुत करता है: एक रैंडमाइज्ड पॉलिनॉमियल-टाइम एल्गोरिदम जो एक ऐसे सेट को खोजता है जिसमें छोटा वर्टेक्स एक्सपेंशन और आकार $[m, n-m]$ के संतुलित रेंज के भीतर होता है, जो कुछ मापदंडों के लिए $O(\sqrt{\log n})$ का अप्रोक्सिमेशन फैक्टर प्राप्त करता है। यह स्मॉल-सेट एक्सपेंशन समस्याओं के लिए मौजूदा सीमाओं में सुधार करता है या उन्हें पूरक बनाता है।

महत्व और दावे
शोध पत्र यह दावा करता है कि यह पहली बार है जब यह प्रदर्शित किया गया है कि वर्टेक्स एक्सपेंशन संरचनात्मक प्रतिकूल हमलों के प्रति मजबूत सक्रिय शिक्षण एल्गोरिदम के लिए क्वेरी जटिलता निर्धारित करने वाला एक मौलिक माप है।

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

लेखक एक विनम्र लहजा बनाए रखते हैं, यह नोट करते हुए कि उनके परिणाम विशिष्ट एक्सपेंशन गैप्स पर निर्भर करते हैं और जैसे-जैसे वांछित सटीकता $\gamma$ कम होती है या प्रतिकूल का बजट बढ़ता है, क्वेरी जटिलता घट जाती है। वे सभी संभावित ग्राफ संरचनाओं या मनमाने प्रतिकूल बजटों के लिए समस्या को हल करने का दावा नहीं करते हैं, बल्कि इनपुट ग्राफ के संरचनात्मक गुणों, क्वेरी लागत और सटीकता के बीच एक सटीक ट्रेड-ऑफ स्थापित करते हैं।

शोध पत्र का समाधान: "एक्सपेंशन" जासूस

बड़ी खोज

यह क्यों महत्वपूर्ण है (शोध पत्र के अनुसार)

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