💻 computer science

COREKG: Coreset-Guided Personalized Summarization of Knowledge Graphs

यह शोधपत्र COREKG प्रस्तुत करता है, जो एक व्यक्तिगत नॉलेज ग्राफ सारांशीकरण ढांचा (personalized knowledge graph summarization framework) है जो कोसेट सिद्धांत (coreset theory) और संवेदनशीलता-आधारित महत्व नमूनाकरण (sensitivity-based importance sampling) का लाभ उठाकर सघन, उपयोगकर्ता-विशिष्ट उपग्राफ (subgraphs) उत्पन्न करता है जो अत्याधुनिक विधियों की तुलना में उच्च सटीकता और संरचनात्मक कवरेज बनाए रखते हुए स्टोरेज और क्वेरी रनटाइम को काफी कम कर देता है।

मूल लेखक: Sohel Aman Khan, Raghava Mutharaju, Supratim Shit

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

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

CC BY 4.0

मूल लेखक: Sohel Aman Khan, Raghava Mutharaju, Supratim Shit

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

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

आमतौर पर, लाइब्रेरियन सबसे प्रसिद्ध किताबों को चुनकर पूरे पुस्तकालय का एक "सारांश" (summary) बनाने की कोशिश करते हैं। लेकिन समस्या यह है: आप शायद केवल "19वीं सदी की कविता" वाली किताबों में रुचि रखते होंगे, जबकि आपका पड़ोसी केवल "अंतरिक्ष यात्रा" में रुचि रखता होगा। सभी के लिए एक ही सारांश देना बहुत सामान्य (generic) है; यह वैसा ही है जैसे आपको अंतरिक्ष यात्रा पर एक किताब दे दी जाए जब वास्तव में आप कविता चाहते थे।

यहीं पर COREKG पेपर काम आता है। यह आपके लिए एक व्यक्तिगत मिनी-लाइब्रेरी बनाने का एक नया तरीका प्रस्तावित करता है।

मुख्य विचार: "स्मार्ट सैंपलर" (The Smart Sampler)

विशाल पुस्तकालय की हर किताब को पढ़ने के बजाय, COREKG कोर्सेट थ्योरी (Coreset Theory) नामक एक चतुर तकनीक का उपयोग करता है। इसे एक "स्मार्ट सैंपलर" के रूप में सोचें।

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

सैंपलिंग प्रक्रिया: बेहतरीन हिस्सों का चयन

अब, सिस्टम को अपना व्यक्तिगत सारांश बनाना है। यह केवल शीर्ष 1,000 तथ्यों को नहीं चुनता। इसके बजाय, यह उन स्कोर के आधार पर भाग्य का खेल खेलता है:

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

इसे सेंसिटिविटी-बेस्ड इम्पोर्टेंस सैंपलिंग (Sensitivity-Based Importance Sampling) कहा जाता है। यह एक शेफ की तरह है जो सूप के लिए सामग्री चुन रहा है: वे सबसे स्वादिष्ट मसालों (उच्च संवेदनशीलता) का एक मुट्ठी भर हिस्सा लेते हैं और फीके मसालों को बहुत कम लेते हैं।

गुप्त नुस्खा: वेटेड बैग (The Weighted Bag)

यहाँ एक पेचीदा हिस्सा है जो गणित को काम करने लायक बनाता है। यदि सिस्टम एक "दुर्लभ" लेकिन महत्वपूर्ण तथ्य चुनता है (एक ऐसा तथ्य जिसे अक्सर नहीं चुना गया लेकिन वह अत्यंत महत्वपूर्ण है), तो वह उस तथ्य को एक भारी वजन (heavy weight) देता है।

उपमा: कल्पना कीजिए कि आप एक सर्वेक्षण (survey) कर रहे हैं। यदि आप एक बड़े शहर के 100 लोगों का साक्षात्कार लेते हैं, तो प्रत्येक व्यक्ति 1,000 लोगों का प्रतिनिधित्व करता है। यदि आप एक छोटे से गाँव के 1 व्यक्ति का साक्षात्कार लेते हैं, तो वह व्यक्ति 10,000 लोगों का प्रतिनिधित्व करता है। गणित को निष्पक्ष बनाने के लिए आप उस गाँव वाले व्यक्ति को "10,000 का वजन" देते हैं।
COREKG में, यदि कोई तथ्य दुर्लभ लेकिन महत्वपूर्ण है, तो उसे उच्च वजन मिलता है। यदि कोई तथ्य सामान्य है और अक्सर चुना जाता है, तो उसे छोटा वजन मिलता है।

यह सुनिश्चित करता है कि भले ही आपका सारांश बहुत छोटा हो (शायद मूल लाइब्रेरी का केवल 1%), यह गणितीय रूप से आपके विशिष्ट प्रश्नों के उत्तर देते समय बिल्कुल मूल लाइब्रेरी की तरह व्यवहार करता है।

यह पुराने तरीकों से बेहतर क्यों है?

पेपर इसकी तुलना अन्य "सारांश" उपकरणों (जैसे GLIMPSE, PEGASUS, और APEX2) से करता है।

पुराने तरीके अक्सर पूरी लाइब्रेरी का सारांश बनाने की कोशिश करते हैं, या वे अनुमान (heuristics) का उपयोग करते हैं जो उन विशिष्ट विवरणों को छोड़ सकते हैं जिनकी आपको आवश्यकता है।
COREKG प्रत्येक उपयोगकर्ता के लिए एक अनूठी लाइब्रेरी बनाता है।
परिणाम: वास्तविक दुनिया की बड़ी लाइब्रेरीज़ (Freebase, DBpedia, Wikidata) पर परीक्षण किए जाने पर, COREKG प्रश्नों के सही उत्तर देने (उच्च सटीकता) और जानकारी की संरचना को बनाए रखने में बहुत बेहतर था, जबकि उसने स्टोरेज स्पेस के बहुत छोटे हिस्से का उपयोग किया।

गारंटी

लेखकों ने केवल यह अनुमान नहीं लगाया कि यह काम करेगा; उन्होंने इसे गणित से सिद्ध किया है। उन्होंने दिखाया कि यदि आप इस "सेंसिटिविटी" पद्धति के आधार पर पर्याप्त तथ्य चुनते हैं, तो आपकी मिनी-लाइब्रेरी आपको मूल लाइब्रेरी के समान ही उत्तर देगी, जिसमें त्रुटि की संभावना बहुत ही कम और अनुमानित होगी।

संक्षेप में

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

तकनीकी सारांश: COREKG – कोरसेट-निर्देशित व्यक्तिगत ज्ञान ग्राफ सारांशीकरण (Coreset-Guided Personalized Summarization of Knowledge Graphs)

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

फ्रीबेस (Freebase), डीबीपीडिया (DBpedia) और विकीडेटा (Wikidata) जैसे नॉलेज ग्राफ (KGs) सर्च इंजन, रिकमेंडेशन सिस्टम और प्रश्न उत्तर (QA) जैसे अनुप्रयोगों के लिए केंद्रीय बन गए हैं। हालाँकि, उनका विशाल पैमाना और उच्च कनेक्टिविटी कुशल क्वेरी करने, विज़ुअलाइज़ेशन और तर्क (reasoning) के लिए महत्वपूर्ण चुनौतियाँ पेश करती है। जबकि सामान्य KG सारांशीकरण विधियाँ डेटा के आकार को कम करने पर ध्यान केंद्रित करती हैं, वे अक्सर वैश्विक संरचनात्मक पैटर्न को पकड़ने पर केंद्रित होती हैं, जिसके परिणामस्वरूप सारांश अत्यधिक सामान्यीकृत हो जाते हैं और व्यक्तिगत उपयोगकर्ताओं की विशिष्ट सूचना आवश्यकताओं को पूरा करने में विफल रहते हैं।

मौजूदा व्यक्तिगत दृष्टिकोण, जैसे कि GLIMPSE और iSummary, उपयोगकर्ता की रुचियों के अनुरूप सारांश बनाने का प्रयास करते हैं लेकिन उनकी सीमाएँ हैं: GLIMPSE सघन (dense) क्वेरी इतिहास मानता है और सारांश की विरलता (sparsity) पर स्पष्ट नियंत्रण की कमी है, जबकि iSummary काफी हद तक समग्र वर्कलोड कवरेज पर निर्भर करता है। अन्य विधियाँ जैसे PEGASUS और APEX2 ह्यूरिस्टिक्स या हीट डिफ्यूजन मॉडल का उपयोग करती हैं जो शायद औपचारिक सन्निकटन गारंटी (formal approximation guarantees) प्रदान नहीं कर पातीं या बिखरे हुए (sparse) और विषम (skewed) क्वेरी लॉग के साथ संघर्ष करती हैं। एक ऐसे फ्रेमवर्क की आवश्यकता है जो विविध उपयोगकर्ता क्वेरी पैटर्नों के बीच सैद्धांतिक गारंटी, कंप्यूटेशनल दक्षता और मजबूती (robustness) के साथ व्यक्तिगत KG सारांशीकरण प्रदान करे, जो सघन ऐतिहासिक डेटा पर निर्भर न हो।

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

लेखक COREKG प्रस्तावित करते हैं, जो कोरसेट सिद्धांत (coreset theory) को नॉलेज ग्राफ के क्षेत्र में अनुकूलित करता है। एक कोरसेट डेटा का एक छोटा, भारित (weighted) उपसमुच्चय है जो सिद्ध त्रुटि सीमाओं के साथ एक लागत फलन (cost function) का अनुमान लगाता है। COREKG प्रत्येक उपयोगकर्ता के लिए एक व्यक्तिगत कोरसेट का निर्माण करता है, जो सेंसिटिविटी-आधारित महत्व नमूनाकरण (sensitivity-based importance sampling) के आधार पर प्रासंगिक ट्रिपल्स (triples) को सैंपल करता है।

2.1 फ्रेमवर्क अवलोकन (Framework Overview)

COREKG पाइपलाइन प्रत्येक उपयोगकर्ता के लिए स्वतंत्र रूप से कार्य करती है और निम्नलिखित चरणों में विभाजित है:

प्रीप्रोसेसिंग और उपयोगकर्ता मॉडलिंग (Preprocessing & User Modeling):
- सीड निष्कर्षण (Seed Extraction): प्रत्येक उपयोगकर्ता को उनके क्वेरी इतिहास से निकाले गए "सीड एंटिटीज" (प्रत्यक्ष रुचि के नोड्स) के सेट द्वारा मॉडल किया जाता है।
- क्वेरी फ़िल्टरिंग (Query Filtering): वैश्विक क्वेरी लॉग को केवल उन क्वेरीज़ को रखने के लिए फ़िल्टर किया जाता है जिनमें उपयोगकर्ता की सीड एंटिटीज में से कम से कम एक का उल्लेख होता है, जिससे एक उपयोगकर्ता-विशिष्ट क्वेरी वर्कलोड बनता है।
- नॉर्मलाइजेशन (Normalization): सिमेंटिक निरंतरता सुनिश्चित करने के लिए SPARQL क्वेरी को नॉर्मलाइज किया जाता है (डुप्लिकेट हटाना, प्रीफिक्स का विस्तार करना)।
सेंसिटिविटी स्कोर गणना (Sensitivity Score Computation):
- एक दिए गए उपयोगकर्ता $u$ और उनके वर्कलोड $Q$ के लिए, एक ट्रिपल $t$ की सेंसिटिविटी $s(t)$ की गणना की जाती है। यह स्कोर उपयोगकर्ता की विशिष्ट क्वेरीज़ के लिए ट्रिपल के महत्व को मापता है।
- औपचारिक रूप से, $s(t) = \sum_{q \in Q} \frac{1}{|T_q|} \cdot \mathbb{I}[t \in T_q]$ , जहाँ $T_q$ उपयोगकर्ता की क्वेरी $q$ से संबंधित ट्रिपल्स का सेट है, और $\mathbb{I}$ एक इंडिकेटर फंक्शन है।
- जो ट्रिपल उपयोगकर्ता की क्वेरीज़ में बार-बार आते हैं या कम उत्तर सेट वाली क्वेरीज़ में आते हैं, उन्हें उच्च सेंसिटिविटी स्कोर प्राप्त होता है। यह सुनिश्चित करता है कि सैंपलिंग वितरण वैश्विक सांख्यिकी के बजाय व्यक्तिगत उपयोगकर्ता व्यवहार के अनुरूप हो।
कोरसेट निर्माण (सैंपलिंग और वेटिंग) (Coreset Construction - Sampling & Weighting):
- मूल ग्राफ $G$ से ट्रिपल्स को संभाव्यता वितरण $p(t) = \frac{s(t)}{S}$ के अनुसार सैंपल किया जाता है, जहाँ $S$ कुल सेंसिटिविटी है।
- प्रत्येक सैंपल किए गए ट्रिपल $t$ को एक भार $w(t) = \frac{1}{m \cdot p(t)} = \frac{S}{m \cdot s(t)}$ दिया जाता है, जहाँ $m$ सैंपल का आकार है। यह वेटिंग सैंपलिंग बायस (sampling bias) को ठीक करती है, यह सुनिश्चित करती है कि कोरसेट पर अपेक्षित लागत, पूर्ण ग्राफ की लागत के बराबर हो।
- परिणामस्वरूप एक भारित सबग्राफ (कोरसेट) प्राप्त होता है जो उपयोगकर्ता के विशिष्ट वर्कलोड के लिए पूर्ण ग्राफ की उपयोगिता का अनुमान लगाता है।

2.2 सैद्धांतिक गारंटी (Theoretical Guarantees)

पेपर एक औपचारिक प्रमेय (Theorem 4.1) प्रदान करता है जो यह स्थापित करता है कि निर्मित कोरसेट $C$ , उच्च संभावना ( $1-\delta$ ) के साथ एक सीमित सापेक्ष त्रुटि $\epsilon$ के भीतर पूर्ण ग्राफ $G$ की वास्तविक लागत का अनुमान लगाता है। आवश्यक सैंपल आकार $m$ , क्वेरी की संख्या $|Q|$ और वांछित त्रुटि सीमाओं पर निर्भर करता है, लेकिन यह पूर्ण ग्राफ के आकार $|T|$ से स्वतंत्र है।

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

पेपर चार प्राथमिक योगदानों को रेखांकित करता है:

COREKG फ्रेमवर्क: कोरसेट-निर्देशित व्यक्तिगत KG सारांशीकरण के लिए एक दृष्टिकोण जो नॉलेज ग्राफ डेटा के लिए कोरसेट सिद्धांत को अनुकूलित करता है, जो सिद्ध सन्निकटन गारंटी और व्यावहारिक स्केलेबिलिटी प्रदान करता है।
सेंसिटिविटी-आधारित सैंपलिंग: एक ऐसा फॉर्मूलेशन जो उपयोगकर्ता-विशिष्ट क्वेरी वर्कलोड के आधार पर ट्रिपल की प्रासंगिकता को मापता है, जिससे विविध वैयक्तिकरण परिदृश्यों में मजबूती सुनिश्चित होती है।
सैद्धांतिक सीमाएं (Theoretical Bounds): उपयोगकर्ता-विशिष्ट वर्कलोड लागतों पर एक वर्स्ट-केस सन्निकटन गारंटी, जो पूर्ण ग्राफ के आकार से स्वतंत्र है, जहाँ सभी क्वेरी मूल्यांकन सीधे कोरसेट पर किए जाते हैं।
अनुभवजन्य सत्यापन (Empirical Validation): फ्रीबेस, डीबीपीडिया और विकीडेटा पर क्वेरी कवरेज और F1 स्कोर दोनों में COREKG को स्टेट-ऑफ-द-आर्ट बेसलाइन्स (GLIMPSE, PPR, iSummary, PEGASUS, APEX2) से बेहतर प्रदर्शन करते हुए दिखाने वाले व्यापक प्रयोग।

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

लेखकों ने SPARQL क्वेरी वर्कलोड का उपयोग करके तीन वास्तविक दुनिया के डेटासेट्स (Freebase, DBpedia, Wikidata) पर COREKG का मूल्यांकन किया। मूल्यांकन संरचनात्मक कवरेज (क्वेरी पैटर्न का संरक्षण) और F1 स्कोर (क्वेरी-उत्तर सटीकता) पर केंद्रित था।

प्रदर्शन: COREKG ने लगातार सभी बेसलाइन्स की तुलना में उच्च F1 स्कोर और कवरेज प्राप्त किया। उदाहरण के लिए, DBpedia पर, COREKG ने 58.64% का F1 स्कोर और 68.07% का कवरेज प्राप्त किया, जो APEX2 (47.52% F1, 42.06% कवरेज) और iSummary (19.38% F1, 12.55% कवरेज) से काफी बेहतर है।
बजट संवेदनशीलता (Budget Sensitivity): विभिन्न सारांश बजटों (1,000 से 100,000 ट्रिपल्स तक) में, COREKG ने श्रेष्ठ प्रदर्शन बनाए रखा। जबकि PEGASUS जैसे अन्य तरीकों ने उच्च कवरेज लेकिन अत्यंत निम्न F1 स्कोर दिखाया (जो खराब प्रासंगिकता का संकेत देता है), COREKG ने दोनों मेट्रिक्स को प्रभावी ढंग से संतुलित किया।
एब्लेशन अध्ययन (Ablation Study):
- यूनिफॉर्म सैंपलिंग (COREKG-Uniform): सेंसिटिविटी सैंपलिंग के स्थान पर यूनिफॉर्म रैंडम सैंपलिंग का उपयोग करने से प्रदर्शन लगभग शून्य हो गया, जो क्वेरी-आधारित सेंसिटिविटी की आवश्यकता की पुष्टि करता है।
- ग्लोबल वर्कलोड (COREKG-Global): उपयोगकर्ता-विशिष्ट कंडीशनिंग को हटाने और ग्लोबल वर्कलोड का उपयोग करने से प्रदर्शन में काफी गिरावट आई, जो वैयक्तिकरण की आवश्यकता को प्रमाणित करता है।
- अनवेटेड सैंपलिंग (COREKG-Unweighted): सैंपल पर समान भार देने से प्रदर्शन में भारी गिरावट आई, जो वेटिंग के माध्यम से बायस सुधार के महत्व को उजागर करता है।

5. महत्व और दावे (Significance and Claims)

पेपर का दावा है कि COREKG मौजूदा सारांशीकरण विधियों के महत्वपूर्ण अंतर को संबोधित करता है, जो ग्लोबल या एग्रीगेट यूजर मॉडलिंग से हटकर स्पष्ट प्रति-उपयोगकर्ता वैयक्तिकरण की ओर जाता है, जो सैद्धांतिक गारंटी पर आधारित है।

दक्षता (Efficiency): उपयोगकर्ता के क्वेरी पैटर्न के आधार पर केवल प्रासंगिक जानकारी बनाए रखकर, COREKG स्टोरेज आवश्यकताओं और क्वेरी रनटाइम को काफी कम कर देता है।
मजबूती (Robustness): हीट डिफ्यूजन या सघन ऐतिहासिक डेटा पर निर्भर विधियों के विपरीत, COREKG अपनी सेंसिटिविटी-आधारित सैंपलिंग के माध्यम से बिखरे हुए (sparse) और विषम (skewed) वर्कलोड को प्रभावी ढंग से संभालता है।
सैद्धांतिक सुदृढ़ता (Theoretical Soundness): विधि एक "सिद्ध सन्निकटन गारंटी" प्रदान करती है, जो यह सुनिश्चित करती है कि सारांश एक छोटी, सीमित सापेक्ष त्रुटि तक पूर्ण ग्राफ की क्वेरी-उत्तरिंग सिमेंटिक्स को सुरक्षित रखता है।

लेखक निष्कर्ष निकालते हैं कि COREKG व्यक्तिगत KG सारांशीकरण के लिए एक मजबूत दृष्टिकोण है, जो उन डेटा-संचालित अनुप्रयोगों में एक व्यवहार्य विकल्प प्रदान करता है जहाँ उपयोगकर्ता-विशिष्ट प्रासंगिकता और कंप्यूटेशनल दक्षता सर्वोपरि है। कार्य स्पष्ट रूप से बिखरे हुए वर्कलोड की प्रतिनिधिता और प्रति-क्वेरी (बजाय एग्रीगेट) गारंटी की कमी के संबंध में सीमाओं को नोट करता है, जो भविष्य के अनुसंधान के लिए दिशाओं के रूप में पहचाने गए हैं।