💻 computer science

Acyclic Graph Pattern Counting under Local Differential Privacy

यह शोध पत्र एक पुनरावर्ती उप-पैटर्न गणना तंत्र (recursive subpattern counting mechanism) और नोड दोहराव को समाप्त करने के लिए एक रैंडम मार्किंग तकनीक को पेश करते हुए, लोकल डिफरेंशियल प्राइवेसी के तहत मनमाने अचकल ग्राफ पैटर्न (arbitrary acyclic graph patterns) को गिनने के लिए पहला सामान्य ढांचा प्रस्तुत करता है, जिससे मौजूदा एड-हॉक समाधानों की तुलना में उपयोगिता और संचार दक्षता में महत्वपूर्ण सुधार प्राप्त होता है।

मूल लेखक: Yihua Hu, Kuncan Wang, Wei Dong

प्रकाशित 2026-03-23

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

CC BY 4.0

मूल लेखक: Yihua Hu, Kuncan Wang, Wei Dong

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

कल्पना कीजिए कि आप एक विशाल, हलचल भरे शहर के मेयर हैं जो हजारों मोहल्लों (नोड्स) से बना है और सड़कों (एजेस) द्वारा आपस में जुड़ा हुआ है। आप यह जानना चाहते हैं कि आपके शहर में विशिष्ट प्रकार की कितनी सड़क यात्राएं मौजूद हैं। उदाहरण के लिए: "कितने 3-स्टॉप वाले टूर हैं?" या "कितने स्टार-आकार के चौराहे (एक केंद्र जो कई स्पोक्स से जुड़ा हो) मौजूद हैं?"

इसे ग्राफ पैटर्न काउंटिंग (Graph Pattern Counting) कहा जाता है। यह समझने के लिए अविश्वसनीय रूप से उपयोगी है कि एक नेटवर्क कैसे काम करता है, चाहे वह सोशल मीडिया कनेक्शन हो, ट्रैफिक फ्लो हो, या बीमारी का प्रसार।

हालाँकि, एक समस्या है: प्राइवेसी (गोपनीयता)।
यदि आप प्रत्येक नागरिक से उनके आस-पास के मोहल्ले का नक्शा भेजने के लिए कहते हैं, तो वे यह प्रकट कर सकते हैं कि वे किसे जानते हैं, वे कहाँ रहते हैं, या वे किससे जुड़े हुए हैं। उनकी सुरक्षा के लिए, हम लोकल डिफरेंशियल प्राइवेसी (LDP) का उपयोग करते हैं।

LDP को एक "नॉइज़ मशीन" (शोर पैदा करने वाली मशीन) की तरह समझें। नागरिक को मेयर को अपना नक्शा भेजने से पहले, वह उसे एक मशीन के माध्यम से गुजारता है जो उसमें रैंडम स्टैटिक (शोर/धुंधलापन) जोड़ देती है। अब नक्शा धुंधला हो गया है। मेयर यह ठीक-ठीक नहीं देख सकता कि कौन किससे जुड़ा है, लेकिन यदि वह सभी से धुंधले नक्शे एकत्र करता है, तो शहर का समग्र आकार फिर से स्पष्ट हो जाता है।

समस्या: "एड हॉक" (Ad Hoc) का झमेला

अब तक, LDP के तहत इन पैटर्न को गिनने की कोशिश करना केवल कुछ विशिष्ट टुकड़ों के साथ पहेली सुलझाने जैसा था।

यदि आप ट्रायंगल्स (Triangles) (3 लोग जो एक-दूसरे को जानते हैं) को गिनना चाहते थे, तो शोधकर्ताओं के पास एक विशेष तरीका था।
यदि आप स्टार्स (Stars) (एक व्यक्ति जो कई अन्य लोगों को जानता है) को गिनना चाहते थे, तो उनके पास एक दूसरा तरीका था।
लेकिन यदि आप किसी रैंडम, जटिल आकार (जैसे एक घुमावदार रास्ता या एक अजीब पेड़ जैसी संरचना) को गिनना चाहते थे, तो कोई सामान्य नियम नहीं था। शोधकर्ताओं को हर एक आकार के लिए एक नया, भद्दा तरीका बनाना पड़ता था। यह अक्षम, धीमा और अक्सर बहुत गलत उत्तर (उच्च त्रुटि) देने वाला था।

समाधान: एक यूनिवर्सल "लेगो" (Lego) किट

यह पेपर पहला सामान्य समाधान (General Solution) पेश करता है जो किसी भी ऐसे आकार को गिन सकता है जो खुद पर वापस नहीं लौटता (जिसे एसाइक्लिक पैटर्न्स - Acyclic Patterns कहा जाता है)। इसे एक यूनिवर्सल लेगो किट के रूप में सोचें जो किसी भी गैर-लूपिंग संरचना को बना सकती है, चाहे वह कितनी भी जटिल क्यों न हो।

लेखकों ने दो बड़ी समस्याओं का समाधान किया:

1. "टेलीफोन गेम" की चुनौती (निर्माण का सामान्यीकरण)

एक विकेंद्रीकृत शहर में, कोई भी अकेला व्यक्ति पूरे नक्शे को नहीं जानता। एक लंबा रास्ता बनाने के लिए, आपको जानकारी को पड़ोसी से पड़ोसी तक पहुँचाने की आवश्यकता होती है।

पुराना तरीका: हर कोई अपने पूरे मोहल्ले की सूची मेगाफोन में चिल्लाकर बता देता था। मेयर उसे जोड़ने की कोशिश करता था। यह शोर भरा, अस्त-व्यस्त था, और "स्टैटिक" (शोर) ने सिग्नल को दबा दिया था।
नया तरीका: लेखकों ने एक रिकर्सिव रिले सिस्टम (Recursive Relay System) बनाया।
- कल्पना करें कि एक रिले रेस चल रही है।
- राउंड 1: हर कोई गिनता है कि कितने 1-स्टेप वाले रास्ते उनके पास समाप्त होते हैं। वे इस संख्या को (थोड़े से शोर के साथ) अपने पड़ोसियों को फुसफुसाकर बताते हैं।
- राउंड 2: पड़ोसी उन संख्याओं को लेते हैं, उन्हें जोड़ते हैं, और 2-स्टेप वाले रास्तों की गिनती को फुसफुसाकर बताते हैं।
- राउंड K: यह तब तक जारी रहता है जब तक कि पूरे पथ की गिनती चरण-दर-चरण बनती नहीं जाती।
- यह क्यों काम करता है: पूरा नक्शा चिल्लाने के बजाय, वे केवल गिनती को पास करते हैं। इससे शोर कम रहता है और सिग्नल मजबूत होता है।

2. "डबल-बुकिंग" की चुनौती (डुप्लिकेट को हटाना)

एक "पाथ" (पथ) का अर्थ है अलग-अलग स्थानों पर जाना। आप एक ही यात्रा में एक ही घर को दो बार नहीं देख सकते।

समस्या: एक शोर भरे, विकेंद्रीकृत सिस्टम में, आप यह कैसे रोकेंगे कि कोई रास्ता किसी ऐसे घर पर वापस न लौट आए जहाँ वह पहले ही जा चुका है? एक ट्रायंगल में, यह आसान है क्योंकि सभी करीब होते हैं। लेकिन एक लंबे पथ में, शुरुआत और अंत मीलों दूर हो सकते हैं।
रचनात्मक समाधान: "रैंडम मार्किंग" (कलर-कोडिंग ट्रिक)।
- कल्पना करें कि गिनती शुरू होने से पहले प्रत्येक नागरिक को 0 से 10 तक एक रैंडम "टिकट नंबर" दिया जाता है।
- नियम यह है: आप यात्रा के तीसरे स्टॉप तभी बन सकते हैं जब आपका टिकट "3" कहता हो।
- यदि आपके पास टिकट "3" है, तो आप केवल उन लोगों को सुनते हैं जिनका टिकट "2" है और उन लोगों से बात करते हैं जिनका टिकट "4" है।
- जादू: क्योंकि हर किसी के पास श्रृंखला में एक विशिष्ट स्थान के लिए एक अद्वितीय टिकट है, इसलिए एक ही यात्रा में एक ही व्यक्ति पर दोबारा आना गणितीय रूप से असंभव है। यदि आप किसी से मिलते हैं, तो उनका टिकट नंबर अनिवार्य रूप से अलग होगा, जिसका अर्थ है कि वे एक अलग व्यक्ति हैं।
- यह एक कठिन "डुप्लिकेट का पता लगाने" वाली समस्या को एक सरल "टिकट का पालन करने" वाले नियम में बदल देता है।

परिणाम: तेज़, सस्ता और सटीक

लेखकों ने वास्तविक दुनिया के डेटा (जैसे ईमेल नेटवर्क और सोशल मीडिया) पर अपने नए "यूनिवर्सल किट" का परीक्षण किया।

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

बड़ी तस्वीर

पुराने तरीकों को समुद्र तट पर रेत के हर कण को गिनने की कोशिश करने के रूप में सोचें, जिसमें हर व्यक्ति को रेत की एक बाल्टी लेकर आने के लिए कहा जाता है। यह धीमा, अव्यवस्थित है, और बाल्टियाँ पानी (शोर) से भरी हुई हैं।

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

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

यहाँ हु, वांग और डोंग के शोध पत्र "Acyclic Graph Pattern Counting under Local Differential Privacy" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र एज-लोकल डिफरेंशियल प्राइवेसी (Edge-LDP) के तहत विकेंद्रीकृत परिवेश में एसाइक्लिक ग्राफ पैटर्न (जैसे पाथ, ट्री, स्टार्स) को गिनने की चुनौती का समाधान करता है।

संदर्भ: एज-एलडीपी (Edge-LDP) में, ग्राफ का प्रत्येक नोड अपने आसन्न किनारों (incident edges) को रखता है और उसे एक अविश्वसनीय विश्लेषक (untrusted analyzer) को भेजने से पहले इस डेटा को स्थानीय रूप से निजीकृत करना होता है। लक्ष्य विशिष्ट सबग्राफ (पैटर्न) की कुल गणना का अनुमान लगाना है बिना संवेदनशील एज जानकारी को प्रकट किए।
अंतराल (Gap): मौजूदा एलडीपी (LDP) समाधान काफी हद तक विशेष मामलों पर केंद्रित हैं, जो केवल स्टार्स या ट्रायंगल्स जैसे सरल ढांचों तक सीमित हैं। किसी भी मनमाने एससाइक्लिक पैटर्न के लिए कोई सामान्य तंत्र मौजूद नहीं है।
चुनौतियां:
1. सामान्यीकरण (Generalization): संरचना-विशिष्ट धारणाओं पर निर्भर किए बिना वितरित डेटा से जटिल पैटर्न का निर्माण करना।
2. नोड डुप्लीकेशन (Node Duplication): यह सुनिश्चित करना कि पैटर्न के उदाहरण में नोड्स अलग-अलग हों (कोई चक्र न बने)। विकेंद्रीकृत एलडीपी में, एक एकल नोड आसानी से यह पता नहीं लगा सकता कि पैटर्न में एक दूर स्थित नोड पहले से ही विज़िट किया जा चुका है या नहीं, जिससे डुप्लिकेट्स को रोकना कठिन हो जाता है।
बेसलाइन सीमा (Baseline Limitation): वार्नर के रैंडमाइज्ड रिस्पांस (RR) का उपयोग करके एक शोर युक्त वैश्विक ग्राफ को पुनर्गठित करने वाला एक सीधा दृष्टिकोण खराब उपयोगिता (utility) देता है, जिसका एरर बाउंड $O(N^k)$ है (जहाँ $N$ नोड्स की संख्या है और $k$ पैटर्न का आकार है), जो वास्तविक गणना स्केल $O(N \cdot d(G)^k)$ की तुलना में घातांकीय रूप से बहुत खराब है।

2. कार्यप्रणाली (Methodology)

लेखक एक सामान्य ढांचा प्रस्तावित करते हैं जो रिकर्सिव सबपैटर्न काउंटिंग को रैंडम मार्किंग तकनीक के साथ जोड़ता है। समाधान तीन प्रगतिशील चरणों में विकसित किया गया है:

A. आधार: $k$ -लाइन वॉक काउंटिंग (k-Line Walk Counting)

पाथ (paths) को हल करने से पहले, लेखक पहले $k$ -लाइन वॉक (किनारों के अनुक्रम जहाँ नोड्स दोहराए जा सकते हैं) के लिए समाधान निकालते हैं।

तंत्र: एक मल्टी-राउंड एग्रीगेशन दृष्टिकोण।
- आरंभीकरण (Initialization): प्रत्येक नोड 1 की गणना के साथ शुरू करता है (जो 0-लंबाई वाले वॉक का प्रतिनिधित्व करता है)।
- रिकर्सिव एग्रीगेशन: राउंड $\ell$ में, प्रत्येक नोड अपने पड़ोसियों से $(\ell-1)$ -लंबाई वाले वॉक की गणना को एकत्रित करता है, पिछले राउंड की अधिकतम गणना के पैमाने पर लाप्लास नॉइज़ (Laplace noise) जोड़ता है, और परिणाम प्रसारित करता है।
- प्राइवेसी: प्राइवेसी बजट $\epsilon$ को $k$ राउंड में विभाजित किया जाता है ( $\epsilon/k$ प्रति राउंड)।
अनुकूलन (Optimization):
- राउंड रिडक्शन: दूसरे-से-अंतिम नोड द्वारा अंतिम चरण को स्थानीय रूप से कंप्यूट करने से प्रक्रिया को $k-1$ राउंड में पूरा किया जा सकता है।
- कम्युनिकेशन: नोड्स केवल अपने पड़ोसियों के साथ संचार करते हैं (लागत $O(M)$ ), न कि सभी नोड्स को ब्रॉडकास्ट करते हैं, जिससे कुल संचार $O(N^2)$ से घटकर $O(M+N)$ हो जाता है।
परिणाम: $\tilde{O}(\sqrt{N} d(G)^{k-1})$ का एडिटिव एरर प्राप्त होता है।

B. विस्तार: $k$ -लाइन पाथ काउंटिंग (k-Line Path Counting)

वॉक को पाथ (जहाँ नोड्स अलग-अलग होने चाहिए) में बदलने के लिए, लेखक रैंडम मार्किंग पेश करते हैं।

अवधारणा: कलर-कोडिंग से प्रेरित, प्रत्येक नोड को एक रैंडम "मार्क" (0 से $k$ के बीच एक पूर्णांक) सौंपा जाता है।
प्रतिबंध: एक नोड को केवल अपने मार्क के अनुरूप विशिष्ट राउंड में भाग लेने की अनुमति होती है। उदाहरण के लिए, मार्क $r$ वाला नोड केवल पथ के $(r+1)$ -वें स्थान के लिए डेटा प्रोसेस करता है।
प्रभाव: यह सुनिश्चित करता है कि एक वैध पाथ इंस्टेंस के सभी नोड्स के लिए अलग-अलग मार्क्स होने चाहिए, जो वैश्विक दृश्यता (global visibility) की आवश्यकता के बिना प्रभावी रूप से नोड डुप्लीकेशन को रोकता है।
अनुमान (Estimation): चूंकि एक विशिष्ट पाथ के सही सीक्वेंस ऑफ मार्क्स प्राप्त करने की संभावना $(k+1)^{-(k+1)}$ है, इसलिए अनबायस्ड एस्टीमेट प्रदान करने के लिए अंतिम एकत्रित गणना को $(k+1)^{k+1}$ द्वारा रीस्केल किया जाता है।
प्राइवेसी: मार्क्स ग्राफ संरचना से स्वतंत्र हैं, इसलिए उन्हें प्रकाशित करने से कोई प्राइवेसी लॉस नहीं होता है। लाप्लास नॉइज़ केवल एग्रीगेशन स्टेप्स में जोड़ा जाता है।

C. सामान्यीकरण: मनमाने एससाइक्लिक पैटर्न काउंटिंग (Arbitrary Acyclic Pattern Counting)

इस ढांचे को किसी भी एससाइक्लिक पैटर्न (जैसे जटिल ट्री) के लिए विस्तारित किया जाता है, जिसमें पैटर्न को एक रूटेड ट्री के रूप में माना जाता है।

ट्री फॉर्मुलेशन: पैटर्न को एक परिभाषित वर्टेक्स ऑर्डरिंग (पत्तियों से रूट की ओर नीचे से ऊपर) के साथ एक ट्री स्ट्रक्चर में प्री-प्रोसेस किया जाता है।
रिकर्सिव सबट्री काउंटिंग:
- पत्तियों (leaves) के अनुरूप मार्क वाले नोड्स गणना को 1 से शुरू करते हैं।
- आंतरिक नोड्स (internal vertices) के अनुरूप मार्क वाले नोड्स, उचित मार्क्स वाले पड़ोसियों से अपने बच्चों (ट्री स्ट्रक्चर में) की गणना को एकत्रित करते हैं।
- ब्रांचिंग के लिए गणनाओं को गुणा किया जाता है, न कि केवल जोड़ा जाता है।
परिणाम: यह तंत्र पाथ काउंटिंग तंत्र की तरह ही समान एसिम्प्टोटिक एरर बाउंड और कम्युनिकेशन एफिशिएंसी बनाए रखता है।

3. मुख्य योगदान (Key Contributions)

पहला सामान्य समाधान: यह शोध पत्र पहला सामान्य एलडीपी (LDP) तंत्र प्रस्तुत करता है जो स्टार्स या ट्रायंगल्स जैसे विशिष्ट मामलों से आगे बढ़कर मनमाने एससाइक्लिक ग्राफ पैटर्न को गिनने में सक्षम है।
नवीन तकनीकें:
- रिकर्सिव सबपैटर्न काउंटिंग: एक एलडीपी-अनुकूलित ढांचा जो संचार राउंड के माध्यम से पैटर्न को क्रमिक रूप से बनाता है।
- एलडीपी के लिए रैंडम मार्किंग: गैर-निजी एल्गोरिदम से अनुकूलित एक तकनीक, जो नोड्स को पैटर्न में विशिष्ट स्थानों तक सीमित करके विकेंद्रीकृत सेटिंग्स में "नोड डुप्लीकेशन" की समस्या को हल करती है।
सैद्धांतिक गारंटी:
- एरर बाउंड: $k$ किनारों वाले किसी भी एससाइक्लिक पैटर्न के लिए, तंत्र $\tilde{O}(\sqrt{N} d(G)^k)$ का एडिटिव एरर प्राप्त करता है। यह बेसलाइन RR विधियों के $O(N^k)$ एरर की तुलना में एक महत्वपूर्ण सुधार है।
- अनबायस्डनेस (Unbiasedness): एस्टीमेटर्स को अनबायस्ड सिद्ध किया गया है।
- जटिलता: तंत्र $O(k)$ राउंड के साथ चलता है जिसका कुल संचार लागत $O(M+N)$ है और स्थानीय गणना $O(d(G))$ है।
स्टार्स के लिए विशेष अनुकूलन: $k$ -स्टार काउंटिंग के लिए एक समर्पित एक-राउंड तंत्र जो रैंडम मार्किंग की आवश्यकता के बिना स्टेट-ऑफ-द-आर्ट उपयोगिता प्राप्त करता है।

4. प्रयोगात्मक परिणाम (Experimental Results)

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

उपयोगिता में सुधार (Utility Improvement):
- वॉक काउंटिंग: बेसलाइन्स की तुलना में रिलेटिव एरर में 110 $\times$ तक की कमी।
- पाथ काउंटिंग: उपयोगिता में 2,600 $\times$ तक का सुधार।
- एससाइक्लिक पैटर्न काउंटिंग: उपयोगिता में 46 $\times$ तक का सुधार।
- स्टार काउंटिंग: एरर में 710 $\times$ तक की कमी, जिसमें रिलेटिव एरर लगातार 0.5% से नीचे रहा।
कम्युनिकेशन दक्षता (Communication Efficiency):
- RR-आधारित बेसलाइन्स (जो अक्सर $O(N^2)$ संचार की आवश्यकता होती है) की तुलना में 300 $\times$ से 650 $\times$ तक कम संचार लागत प्राप्त की।
- प्रस्तावित विधि की संचार लागत किनारों की संख्या ( $O(M)$ ) के साथ रैखिक रूप से स्केल करती है, जो इसे बड़े ग्राफों के लिए स्केलेबल बनाती है।
एरर विश्लेषण: प्रयोगों ने पुष्टि की कि जबकि सैद्धांतिक विश्लेषण बताता है कि सैंपलिंग एरर हावी है, व्यवहार में, सैंपलिंग एरर और डीपी (DP) नॉइज़ के बीच का अंतर छोटा है। प्रति रन कम प्राइवेसी बजट के साथ कई रन चलाने की रणनीति को कुल एरर को और अधिक अनुकूलित करने के लिए दिखाया गया।

5. महत्व (Significance)

यह कार्य गोपनीयता-संरक्षित ग्राफ एनालिटिक्स में एक महत्वपूर्ण अंतराल को भरता है। एलडीपी (LDP) के तहत एससाइक्लिक पैटर्न काउंटिंग के लिए एक सामान्य, कुशल और सैद्धांतिक रूप से सुदृढ़ समाधान प्रदान करके, यह उपयोगकर्ता की गोपनीयता से समझौता किए बिना विकेंद्रीकृत वातावरण (जैसे सोशल नेटवर्क) में जटिल नेटवर्क संरचनाओं (जैसे कम्युनिटी डिटेक्शन, फ्रॉड रिंग्स, और इंफॉर्मेशन डिफ्यूजन) के विश्लेषण को सक्षम बनाता है। एरर का $O(N^k)$ से $\tilde{O}(\sqrt{N} d(G)^k)$ में परिवर्तन वास्तविक दुनिया के अनुप्रयोगों के लिए प्राइवेट ग्राफ माइनिंग की व्यवहार्यता में एक मौलिक छलांग का प्रतिनिधित्व करता है।