← नवीनतम पेपर
🤖 AI

CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support

यह शोध पत्र CGS का प्रस्ताव करता है, जो एक नवीन कॉन्फ़िगर करने योग्य ग्राफ़ सारांशीकरण ढांचा (framework) है जो लॉसलेस परिणामों या सीमित पड़ोस हानि (neighborhood loss) के साथ कई ग्राफ़ प्रश्नों का समर्थन करने के लिए सामान्य पड़ोस वाले नोड्स को एकत्रित करके संक्षिप्त सारांश उत्पन्न करता है, जबकि उपयोगकर्ताओं को सहने योग्य त्रुटि प्रकारों और थ्रेशोल्ड को अनुकूलित करने की अनुमति देता है।

मूल लेखक: Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal

प्रकाशित 2026-07-14
📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें
CC BY 4.0

मूल लेखक: Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal

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

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

यह बिल्कुल वही समस्या है जिसे इस शोध पत्र के लेखक CGS (कॉन्फ़िगरेबल ग्राफ समराइज़र) नामक एक नए टूल के साथ हल कर रहे हैं। वे एक जटिल नेटवर्क (जैसे सोशल मीडिया फ्रेंड लिस्ट या कनेक्शन का जाल) को एक विशाल मानचित्र की तरह मानते हैं और इसे एक "समरी मैप" (सारांश मानचित्र) में सिकोड़ने की कोशिश करते हैं जो ले जाने में आसान हो लेकिन इतना सटीक हो कि "मेरे दोस्त कौन हैं?" या "A से B तक जाने का सबसे तेज़ रास्ता क्या है?" जैसे सवालों के जवाब दे सके।

मुख्य विचार: पड़ोसियों का समूह बनाना

CGS की मूल तकनीक एक पार्टी में उन लोगों को समूह में रखने जैसी है जो दोस्तों के ठीक उसी समूह को जानते हैं। यदि एलिस और बॉब दोनों चार्ली, डेव और ईव को जानते हैं, लेकिन उनमें से कोई भी अन्य किसी को समान रूप से नहीं जानता, तो CGS कहता है, "हे, चलो एलिस और बॉब को एक ही 'सुपर-पर्सन' में मिला देते हैं।"

जब आप ऐसा करते हैं, तो आप जगह बचाते हैं क्योंकि आपको उन सभी साझा कनेक्शनों को दो बार सूचीबद्ध करने की आवश्यकता नहीं होती है। हालाँकि, लोगों को आपस में जोड़ने से एक जोखिम पैदा होता है: आप अनजाने में एक ऐसा कनेक्शन बना सकते हैं जो मौजूद नहीं था (एक "फॉल्स पॉजिटिव," जैसे यह सोचना कि एलिस de फ्रैंक को जानती है जबकि वह नहीं जानती) या एक कनेक्शन खो सकते हैं जो मौजूद था (एक "फॉल्स नेगेटिव," जैसे यह भूल जाना कि बॉब फ्रैंक को जानता है)।

CGS के तीन रूप

शोध पत्र का तर्क है कि एक ही आकार सबके लिए उपयुक्त नहीं होता। आपकी ज़रूरत के आधार पर, आप बहुत सख्त होना चाह सकते हैं, या आप थोड़ी ढील देने के लिए तैयार हो सकते हैं। इसीलिए उन्होंने अपने टूल के तीन अलग-अलग संस्करण बनाए हैं:

  1. CGS-E (द परफेक्शनिस्ट): यह संस्करण लॉसलेस (lossless) है। यह वादा करता है कि जब आप बाद में 'सुपर-पर्सन्स' को फिर से खोलेंगे (un-glue करेंगे), तो आपको ठीक मूल मानचित्र वापस मिल जाएगा। कोई अतिरिक्त सड़कें नहीं, कोई गायब सड़कें नहीं। यह एक परफेक्ट फोटोकॉपी की तरह है जो बस छोटी करके फोल्ड की गई है।
  2. CGS-I (द इंटरसेक्शन): यह एक लॉसी (lossy) संस्करण है जिसे फॉल्स पॉजिटिव (नकली किनारे/edges) से बचने के लिए डिज़ाइन किया गया है। यह गारंटी देता है कि यह कभी भी ऐसा कनेक्शन नहीं बनाएगा जो मूल ग्राफ में मौजूद नहीं था। हालाँकि, इसे हासिल करने के लिए, यह कुछ वास्तविक कनेक्शनों को छोड़ सकता है (जिससे फॉल्स नेगेटिव की अनुमति मिलती है)। खोई हुई जानकारी की मात्रा को एक "टॉलरेंस नॉब" (सहनशीलता के बटन) द्वारा नियंत्रित किया जाता है। इसे एक ऐसे मानचित्र के रूप में सोचें जो कुछ साइड सड़कों को छोड़ सकता है, लेकिन इसमें दिखाई देने वाला हर रास्ता निश्चित रूप से असली है। यह रूट नेविगेशन जैसी चीज़ों के लिए बेहतरीन है, जहाँ आप नहीं चाहेंगे कि आपको ऐसी सड़क पर भेजा जाए जो अस्तित्व में ही नहीं है।
  3. CGS-U (द यूनियन): यह दूसरा लॉसी संस्करण है जिसे फॉल्स नेगेटिव (छूटे हुए किनारे) से बचने के लिए डिज़ाइन किया गया है। यह गारंटी देता है कि यह किसी भी वास्तविक कनेक्शन को नहीं छोड़ेगा जो मूल ग्राफ में मौजूद था। हालाँकि, यह सुनिश्चित करने के लिए कि कोई कमी न रहे, यह कुछ अतिरिक्त, नकली कनेक्शन जोड़ सकता है (जिससे फॉल्स पॉजिटिव की अनुमति मिलती है)। यह एक ऐसे मानचित्र की तरह है जो हर संभावित पथ दिखाता है, यहाँ तक कि वे भी जो पड़ोसी के आँगन के माध्यम से शॉर्टकट हैं। यह फ्रेंड रिकमेंडेशन के लिए एकदम सही है, जहाँ आप किसी संभावित मित्र को दिखाने के बजाय जिसे आप नहीं जानते, उसे मिस नहीं करना चाहेंगे।

"सुरक्षा जाल" (बाउंडेड लॉस)

लेखकों ने महसूस किया कि कभी-कभी आपको लचीलेपन की आवश्यकता होती है। उन्होंने एक "टॉलरेंस नॉब" (जिसे नेबरहुड लॉस थ्रेशोल्ड कहा जाता है) पेश किया। आप टूल को बता सकते हैं, "मुझे इस विशिष्ट व्यक्ति के लिए 25% विवरण खोने में कोई आपत्ति नहीं है, लेकिन उस दूसरे व्यक्ति के लिए, मुझे 100% सटीकता चाहिए।"

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

उन्होंने क्या खारिज किया

शोध पत्र बहुत स्पष्ट है कि उनके लक्ष्यों के लिए क्या काम नहीं करता है। वे उन तरीकों के विरुद्ध तर्क देते जो:

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

वे कितने आश्वस्त हैं?

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने इसका व्यापक परीक्षण किया।

  • मापे गए परिणाम: उन्होंने अपने कोड को 10 वास्तविक दुनिया के डेटासेट (जैसे DBLP, LiveJournal, और Email-Enron) और सिंथेटिक ग्राफ पर चलाया।
  • आंकड़े: वास्तविक ग्राफों पर, उनके लॉसलेस संस्करण (CGS-E) ने मौजूदा सर्वोत्तम टूल्स की तुलना में डेटा को 27% (LiveJournal डेटासेट पर) और 41% (CA-AstroPh डेटासेट पर) बेहतर तरीके से कंप्रेस किया।
  • सटीकता: लॉसी संस्करणों के लिए, उन्होंने दिखाया कि भले ही उन्होंने 50% लॉस टॉलरेंस की अनुमति दी थी, वास्तविक औसत एरर अक्सर बहुत कम (डेटासेट के आधार पर लगभग 0.18 से 0.26) था।
  • क्वेरी परफॉरमेंस: उन्होंने क्वेरी की गति को मापा। उन्होंने पाया कि हालांकि छोटे सारांश मानचित्र को देखना पूर्ण मानचित्र को देखने की तुलना में थोड़ा धीमा है (क्योंकि कंप्यूटर को थोड़ा "लोकल अन-फोल्डिंग" करना पड़ता है), फिर भी यह बहुत तेज़ है—नेबरहुड क्वेरी माइक्रोसेकंड में और शॉर्टेस्ट पाथ क्वेरी मिलीसेकंड में चलती है।

ट्रेड-ऑफ (समझौता)

पेपर स्वीकार करता है कि CGS को सारांश मानचित्र बनाने में अन्य विधियों की तुलना में थोड़ा अधिक समय लगता है (विशाल ग्राफ के लिए यह मिनटों से घंटों तक लग सकता है)। हालाँकि, वे तर्क देते हैं कि यह एक उचित सौदा है क्योंकि सारांश बनाना आमतौर पर एक बार का काम है जो ऑफलाइन किया जाता है, और परिणामी मानचित्र प्रश्नों का उत्तर देने और स्थान बचाने में बहुत बेहतर है।

संक्षेप में, लेखक सुझाव देते हैं कि यह चुनने की अनुमति देकर कि आप सूचना को कैसे खोना चाहते हैं (या बिल्कुल नहीं खोना चाहते) और यह नियंत्रित करके कि आप कितना खोने के लिए तैयार हैं, CHS विशाल नेटवर्क को बिना तोड़े छोटा करने का एक स्मार्टर और अधिक लचीला तरीका बनाता है।

अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?

आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।

Digest आज़माएँ →

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

इस विषय के सभी पेपर देखें 🤖 cs.AI →