🤖 machine learning

Correlation Clustering with Random Partial Information

यह शोध पत्र प्रदर्शित करता है कि एक पूर्ण हस्ताक्षरित ग्राफ (complete signed graph) से यादृच्छिक रूप से उप-नमूनाकरण (randomly subsampling) करके बनाए गए ग्राफों पर सहसंबंध क्लस्टरिंग (correlation clustering), सामान्य अपूर्ण ग्राफ सीमाओं की तुलना में महत्वपूर्ण सुधार करने वाले और पूर्ण ग्राफों पर प्राप्त करने योग्य सीमाओं के करीब पहुँचने वाले सन्निकटन गारंटी (approximation guarantees) स्वीकार करता है, जो सैद्धांतिक विश्लेषण और प्रयोगात्मक परिणामों दोनों द्वारा समर्थित एक निष्कर्ष है।

मूल लेखक: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

प्रकाशित 2026-08-18

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

CC BY 4.0

मूल लेखक: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

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

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

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

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

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

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

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

तकनीकी सारांश: यादृच्छिक आंशिक सूचना के साथ सहसंबंध क्लस्टरिंग (Correlation Clustering with Random Partial Information)

समस्या की परिभाषा

सहसंबंध क्लस्टरिंग (Correlation clustering) एक अनसुपरवाइज्ड लर्निंग समस्या है जहाँ इनपुट एक अनडिरेक्टेड साइन्ड ग्राफ $G = (V, E)$ है जिसमें किनारों (edges) को धनात्मक ( $+$ ) या ऋणात्मक ($-$) लेबल किया गया है। लक्ष्य विसंगतियों (disagreements) को कम करने के लिए शीर्षों (vertices) को क्लस्टरों में विभाजित करना है। एक विसंगति तब होती है जब एक धनात्मक किनारा अलग-अलग क्लस्टरों के शीर्षों को जोड़ता है या एक ऋणात्मक किनारा एक ही क्लस्टर के भीतर होता है।

यह शोध पत्र पूर्ण ग्राफ (complete graphs) और सामान्य (अपूर्ण) ग्राफ (general/incomplete graphs) के बीच अप्रॉक्सिमेशन गारंटी में मौजूद अंतर को संबोधित करता है:

पूर्ण ग्राफ (Complete Graphs): दोनों मिन-डिसएग्रीमेंट (कुल विसंगतियों को न्यूनतम करना) और मिन-मैक्स (किसी भी शीर्ष से जुड़ी अधिकतम विसंगतियों को न्यूनतम करना) उद्देश्यों के लिए कांस्टेंट-फैक्टर अप्रॉक्सिमेशन उपलब्ध हैं।
सामान्य ग्राफ (General Graphs): ज्ञात सर्वोत्तम गारंटियाँ मिन-डिसएग्रीमेंट के लिए $O(\log n)$ और मिन-मैक्स के लिए $O(\sqrt{n})$ तक गिर जाती हैं।

इस कार्य को प्रेरित करने वाला केंद्रीय प्रश्न यह है कि क्या अपूर्ण ग्राफों के ऐसे स्वाभाविक वर्ग मौजूद हैं जो इन निचली सीमाओं (lower bounds) को दरकिनार कर सकें और पूर्ण ग्राफों पर प्राप्त होने वाली अप्रॉक्सिमेशन गारंटियों के करीब पहुँच सकें। लेखक उन ग्राफों का अध्ययन करते हैं जो एक पूर्ण साइन्ड ग्राफ $G$ से यादृच्छिक रूप से सबसैंपलिंग (randomly subsampling) द्वारा उत्पन्न होते हैं, जहाँ प्रत्येक किनारे को प्रायिकता $q$ के साथ स्वतंत्र रूप से हटा दिया जाता है। परिणामी ग्राफ को $G' \sim S_q(G)$ द्वारा दर्शाया गया है।

कार्यप्रणाली और एल्गोरिदम

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

केवल मूल पूर्ण ग्राफ $G$ तक पहुंच।
केवल अपूर्ण ग्राफ $G'$ तक पहुंच।
$G$ और $G'$ दोनों तक पहुंच।

मिन-मैक्स उद्देश्य (Min-Max Objective)

मिन-मैक्स उद्देश्य के लिए, लेखक एक कॉम्बिनेटोरियल एल्गोरिदम (एल्गोरिदम 2) प्रस्तुत करते हैं जो केवल अपूर्ण ग्राफ $G'$ पर कार्य करता है।

मुख्य विचार: एल्गोरिदम पूर्ण ग्राफों पर हाइड्रिच, इर्माई और एंड्रेस (2024) के कार्य से प्राप्त संरचनात्मक गुणों का लाभ उठाता है। विशेष रूप से, वे शीर्ष जिनका धनात्मक पड़ोस (positive neighborhood) काफी ओवरलैप करता है, उन्हें एक ही क्लस्टर में होना चाहिए, जबकि वे शीर्ष जिनके धनात्मक पड़ोस बहुत भिन्न हैं, उन्हें अलग-अलग क्लस्टरों में होना चाहिए।
तंत्र (Mechanism): एल्गोरिदम इष्टतम लागत $d$ के अनुमानों (guesses) के माध्यम से पुनरावृत्ति करता है। एक निश्चित अनुमान के लिए, यह एक सहायक ग्राफ $H$ बनाता है जहाँ एक किनारा $(u, v)$ तब मौजूद होता है यदि $G'$ में उनके धनात्मक पड़ोस का प्रतिच्छेदन (intersection) एक थ्रेशोल्ड ( $2d$ ) से अधिक हो। $H$ के कनेक्टेड कंपोनेंट्स क्लस्टरिंग का निर्माण करते हैं। जो शीर्ष बड़े कंपोनेंट्स का हिस्सा नहीं हैं, उन्हें सिंगलटन (singletons) के रूप में माना जाता है।
विश्लेषण: चेर्नऑफ बाउंड्स (Chernoff bounds) का उपयोग करते हुए, लेखक सिद्ध करते हैं कि उच्च प्रायिकता के साथ, किनारों का विलोपन इतने किनारे नष्ट नहीं करता कि उच्च-डिग्री वाले शीर्षों के लिए क्लस्टर संरचना अस्पष्ट हो जाए। एल्गोरिदम सभी अनुमानों में से न्यूनतम लागत वाला क्लस्टरिंग आउटपुट देता है।

मिन-डिसएग्रीमेंट उद्देश्य (Min-Disagreement Objective)

मिन-डिसएग्रीमेंट के लिए दृष्टिकोण पूर्ण ग्राफ पर $OPT(G)$ के परिमाण के आधार पर भिन्न होता है।

मामला 1: $G$ तक पहुंच ( $G$ या $OPT(G)$ बड़ा है)
यदि एल्गोरिदम के पास $G$ तक पहुंच है, या यदि $OPT(G) $पर्याप्त रूप से बड़ा ($ \Omega(\log n) $) है, तो लेखक दिखाते हैं कि पूर्ण ग्राफ$ G $के लिए कोई भी$ \alpha $-अप्रॉक्सिमेशन एल्गोरिदम$ G' $के लिए$ O(\alpha/(1-q)^2) $-अप्रॉक्सिमेशन प्रदान करता है। यह इस अवलोकन पर आधारित है कि$ G'$ पर इष्टतम समाधान की अपेक्षित लागत विलोपन प्रायिकता के सापेक्ष बहुत तेजी से कम नहीं होती है।

मामला 2: केवल $G'$ तक पहुंच और $OPT(G)$ छोटा है
यह तकनीकी रूप से सबसे चुनौतीपूर्ण सेटिंग है। लेखक $OPT(G) = O(\log^\gamma n)$ के मामले के लिए एक हाइब्रिड एल्गोरिदम (एल्गोरिदम 1) प्रस्तावित करते हैं:

तुच्छ क्लस्टर्स की पहचान (Identify Trivial Clusters): उन क्लस्टरों को हटा दें जो $G'$ में शून्य विसंगतियां उत्पन्न करते हैं।
बड़े क्लस्टर्स की रिकवरी (Recover Large Clusters): $G'$ $G^{'}$ में धनात्मक पड़ोस के प्रतिच्छेदन के आधार पर एक समानता ग्राफ (similarity graph) $H$ $H$ का निर्माण करें। यदि दो शीर्षों के बीच पर्याप्त संख्या में सामान्य धनात्मक पड़ोसी साझा हैं, तो वे जुड़े होते हैं। एल्गोरिदम $H$ $H$ में बड़े कनेक्टेड कंपोनेंट्स को रिकवर्ड इष्टतम क्लस्टर्स के रूप में पहचानता है।
- सैद्धांतिक औचित्य: लेम्मा 5 सिद्ध करता है कि $G$ में बड़े इष्टतम क्लस्टर्स के लिए, $G'$ में धनात्मक पड़ोस का प्रतिच्छेदन उच्च प्रायिकता के साथ बड़ा बना रहता है, जिससे सटीक रिकवरी संभव होती है।
अवशिष्ट क्लस्टरिंग (Cluster Residuals): शेष शीर्ष (अवशिष्ट सेट $R$ ) एक $O(\text{polylog}(n))$ आकार का सबग्राफ बनाते हैं। एल्गोरिदम इस छोटे अवशिष्ट उदाहरण के लिए सामान्य ग्राफ अप्रॉक्सिमेशन एल्गोरिदम (डेमेन आदि, 2006) लागू करता है।

मुख्य परिणाम और सैद्धांतिक गारंटियाँ

मिन-मैक्स परिणाम

थ्योरम 1: दिए गए $G' \sim S_q(G)$ के लिए, एक नियतकालिक (deterministic) एल्गोरिदम है जो उच्च प्रायिकता के साथ $O(\frac{\log n}{1-q})$ लागत वाला क्लस्टरिंग लौटाता है।
महत्व: यह सामान्य ग्राफों के $O(\sqrt{n})$ बाउंड में सुधार करता है। एल्गोरिदम कॉम्बिनेटोरियल है, जो पिछले सामान्य ग्राफ दृष्टिकोणों में उपयोग किए जाने वाले लीनियर प्रोग्रामिंग (LP) रिलेक्सेशन से बचता है।

मिन-डिसएग्रीमेंट परिणाम

थ्योरम 2 (छोटा OPT): यदि $OPT(G) = O(\log^\gamma n)$ $O P T (G) = O (lo g^{γ} n)$ है, तो केवल $G'$ $G^{'}$ का उपयोग करने वाला एक बहुपद-समय (polynomial-time) एल्गोरिदम उच्च प्रायिकता के साथ $O(\log(\frac{\log n}{(1-q)^2}))$ $O (lo g (\frac{l o g n}{( 1 - q ) ^{2}}))$ -अप्रॉक्सिमेशन प्राप्त करता है।
- स्थिर $q$ के लिए, यह सामान्य ग्राफों के $O(\log n)$ बाउंड से काफी बेहतर है।
थ्योरम 3 (पूर्ण रेंज के लिए $G$ तक पहुंच के साथ): यदि एल्गोरिदम के पास $G$ $G$ और $G'$ $G^{'}$ दोनों तक पहुंच है, तो एक बहुपद-समय एल्गोरिदम उच्च प्रायिकता के साथ $O(\max\{\frac{1}{(1-q)^2}, \log \log n + \log(\frac{1}{1-q})\})$ $O (max {\frac{1}{( 1 - q ) ^{2}}, lo g lo g n + lo g (\frac{1}{1 - q})})$ -अप्रॉक्सिमेशन प्राप्त करता है।
- यह $G$ पर मानक अप्रॉक्सिमेशन (बड़े $OPT $के लिए) और$ G' $पर विशिष्ट एल्गोरिदम 1 (छोटे$ OPT$ के लिए) चलाने और फिर बेहतर परिणाम चुनने से प्राप्त किया जाता है।

प्रयोगात्मक निष्कर्ष (Experimental Findings)

लेखक अपने सैद्धांतिक परिणामों को निम्नलिखित का उपयोग करके मान्य करते हैं:

फेसबुक ईगो-नेटवर्क्स (Facebook Ego-Networks): स्टैनफोर्ड लार्ज नेटवर्क डेटासेट कलेक्शन से सबग्राफ, जिन्हें साइन्ड ग्राफ में परिवर्तित किया गया है।
प्लांटेड-क्लिक इंस्टेंस (Planted-Clique Instances): नियंत्रित मापदंडों वाले स्टोकेस्टिक ब्लॉक मॉडल से उत्पन्न ग्राफ।

मिन-मैक्स प्रयोग:

छोटे ग्राफों पर जहाँ इष्टतम लागत को LP के माध्यम से बाउंड किया जा सकता है, एल्गोरिदम 2 का अनुभवजन्य (empirical) अप्रॉक्सिमेशन अनुपात सैद्धांतिक गारंटी $O(\frac{\log n}{1-q})$ के कम से कम बराबर है।
बड़े ग्राफों पर, एल्गोरिदम एक रीस्केल्ड कॉम्बिनेटोरियल बेसलाइन के विरुद्ध लगातार प्रदर्शन करता है।
एल्गोरिदम गणनात्मक रूप से कुशल है क्योंकि यह LP हल नहीं करता है, जिससे यह बड़े ग्राफों के लिए स्केलेबल बनता है।

मिन-डिसएग्रीमेंट प्रयोग:

लेखकों ने सीधे अपूर्ण ग्राफ $G'$ पर पिवट (Pivot) एल्गोरिदम (एलन, चरिकर और न्यूमैन, 2008) का परीक्षण किया।
हालांकि लेम्मा 2 में दी गई सैद्धांतिक गारंटी $G$ पर गणना किए गए क्लस्टरिंग पर लागू होती है, प्रयोगात्मक परिणाम बताते हैं कि $G'$ पर पिवट चलाने से भी व्यवहार में एक कांस्टेंट अप्रॉक्सिमेशन अनुपात प्राप्त होता है, विशेष रूप से प्लांटेड-क्लिक इंस्टेंस पर जहाँ अनुपात $O(\frac{1}{(1-q)^2})$ के साथ स्केल करता है।

महत्व और दावे

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

प्राकृतिक वर्ग: यह अपूर्ण ग्राफों के एक प्राकृतिक वर्ग (रैंडमली सबसैम्पल्ड पूर्ण ग्राफ) की पहचान करता है जहाँ अप्रॉक्सिमेशन कारक पूर्ण ग्राफों के करीब पहुँच सकते हैं, न कि सामान्य ग्राफों की वर्स्ट-केस सीमाओं को झेलते हैं।
एल्गोरिद्मिक दक्षता: प्रस्तावित मिन-मैक्स एल्गोरिदम कॉम्बिनेटोरियल है, जो LP-आधारित विधियों के लिए एक व्यावहारिक विकल्प प्रदान करता है जो अक्सर बड़े ग्राफों के लिए कठिन होती हैं।
मजबूती (Robustness): परिणाम प्रदर्शित करते हैं कि सहसंबंध क्लस्टरिंग लुप्त सूचना के प्रति मजबूत है, बशर्ते कि लुप्त होना यादृच्छिक हो और अंतर्निहित संरचना (इष्टतम क्लस्टर्स) पर्याप्त रूप से बड़ी या कुल लागत कम हो।
सीमित दायरा: लेखक स्पष्ट रूप से नोट करते हैं कि उनके सबसे मजबूत मिन-डिसएग्रीमेंट परिणाम में छोटे $OPT(G)$ का अनुमान एक स्वाभाविक सेटिंग है जो शोर वाले परिवर्तनों (noisy perturbations) से ग्राउंड ट्रुथ क्लस्टरिंग को रिकवर करने से संबंधित है, लेकिन वे यह दावा नहीं करते हैं कि वे सभी सामान्य ग्राफ इंस्टेंस के लिए समस्या को हल करते हैं। वे यह भी स्वीकार करते हैं कि $G'$ पर पिवट के प्रदर्शन का प्रयोगात्मक अवलोकन अनुभवजन्य है और अभी तक सैद्धांतिक रूप से सिद्ध नहीं हुआ है।