Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

यहाँ Lin, Mei, और Zhang द्वारा लिखित शोध पत्र "Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem" का विस्तृत तकनीकी सारांश दिया गया है।

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

ट्रैवलिंग सेल्समैन प्रॉब्लम (TSP) के लिए उच्च-प्रदर्शन वाले सॉल्वर, जैसे कि LKH (Lin-Kernighan-Helsgaun), सभी संभावित किनारों ($N(N-1)/2$) पर खोज नहीं करते हैं। इसके बजाय, वे एक कैंडिडेट ग्राफ (candidate graph) पर कार्य करते हैं, जो किनारों का एक विरल (sparsified) उपसमुच्चय होता है।

• ट्रेड-ऑफ (The Trade-off): एक कैंडिडेट ग्राफ इतना विरल होना चाहिए कि खोज तेज़ हो सके, लेकिन इतना घना भी होना चाहिए कि इष्टतम टूर (optimal tour) के किनारों को सुरक्षित रखा जा सके।
• वर्तमान ह्यूरिस्टिक्स की सीमाएँ:
  • $\alpha$-Nearest: यह विभिन्न पैमानों पर रिकॉल (recall) में मजबूत है (इष्टतम किनारों को बनाए रखता है), लेकिन यह घने ग्राफ बनाता है, जिससे सॉल्वर धीमा हो जाता है।
  • POPMUSIC: यह बहुत ही विरल ग्राफ बनाता है लेकिन बड़े पैमानों ($N > 200$) और कठिन स्थानिक वितरणों (spatial distributions) पर महत्वपूर्ण रिकॉल गिरावट का सामना करता है।
  • मौजूदा ML दृष्टिकोण: TSP स्पार्सिफिकेशन के लिए अधिकांश मशीन लर्निंग विधियाँ पूर्ण ग्राफ (complete graph) पर कार्य करती हैं। यह गणनात्मक रूप से महंगा है, स्केलेबिलिटी में कमजोर है, और अक्सर यूक्लिडियन दूरियों (EUC_2D) तक सीमित है, जिससे यह अन्य TSPLIB दूरी प्रकारों (जैसे, GEO, ATT, MAN_2D) पर सामान्यीकरण करने में विफल रहता है।

मुख्य प्रश्न: इष्टतम-टूर किनारों को हटाए बिना, एक उच्च-रिकॉल कैंडिडेट ग्राफ के घनत्व (density) को कैसे कम किया जाए, जबकि विभिन्न दूरी मेट्रिक्स और इंस्टेंस आकारों के बीच सामान्यीकरण क्षमता को बनाए रखा जा सके?

2. कार्यप्रणाली: दो-चरणीय ग्राफ स्पार्सिफिकेशन (Methodology: Two-Stage Graph Sparsification)

लेखक एक दो-चरणीय पाइपलाइन का प्रस्ताव करते हैं जो रिकॉल को अधिकतम करने और घनत्व को कम करने को अलग-अलग करता है।

चरण 1: ह्यूरिस्टिक यूनियन (रिकॉल को अधिकतम करना)

एक एकल ह्यूरिस्टिक पर निर्भर रहने के बजाय, यह विधि दो अग्रणी ह्यूरिस्टिक्स के यूनियन (union) को लेकर एक आधार कैंडिडेट ग्राफ ($G_b$) का निर्माण करती है:
$$E_{union} = E_{\alpha\text{-Nearest}} \cup E_{\text{POPMUSIC}}$$

• लक्ष्य: इष्टतम टूर किनारों का लगभग पूर्ण कवरेज (रिकॉल) प्राप्त करना।
• मुख्य अंतर्दृष्टि: यह यूनियन एक सोर्स-प्रोवेनेंस सिग्नल (source-provenance signal) बनाता है। $G_b$ में प्रत्येक किनारे के लिए, मॉडल जानता है कि वह केवल $\alpha$-Nearest द्वारा चुना गया था, केवल POPMUSIC द्वारा, या दोनों द्वारा। दोनों ह्यूरिस्टिक्स में मौजूद किनारे सांख्यिकीय रूप से अत्यधिक संभावना रखते हैं कि वे इष्टतम टूर का हिस्सा होंगे।

चरण 2: सीखा हुआ प्रूनिंग (घनत्व कम करना)

एक मशीन लर्निंग मॉडल को $G_b$ में किनारों को स्कोर करने और सबसे कम स्कोर वाले किनारों को हटाने (prune करने) के लिए प्रशिक्षित किया जाता है ताकि एक अंतिम विरल ग्राफ ($\tilde{G}$) प्राप्त हो सके।

• विशेषताएँ (Features): मॉडल निर्देशांक ज्यामिति (coordinate geometry) के बजाय डिस्टेंस-टाइप अगनोस्टिक (distance-type agnostic) विशेषताओं (रैंक, अनुपात, स्थानीय सांख्यिकी और सोर्स प्रोवेनेंस) का उपयोग करता है। यह मॉडल को EUC_2D, ATT, GEO, और MAN_2D पर कार्य करने में सक्षम बनाता है।
• परीक्षण किए गए मॉडल: लॉजिस्टिक रिग्रेशन (LR), लीनियर SVM, और XGBoost।
• प्रूनिंग नियम: एक नोड-स्तरीय नियम का उपयोग किया जाता है न कि वैश्विक थ्रेशोल्ड का। प्रत्येक नोड के लिए, किनारों को स्कोर के आधार पर क्रमबद्ध किया जाता है, और एक स्थानीय सॉफ्टमैक्स वितरण यह निर्धारित करता है कि संचयी द्रव्यमान थ्रेशोल्ड ($\eta$) के आधार पर कितने किनारे रखने हैं, जिससे टूर व्यवहार्यता बनाए रखने के लिए न्यूनतम डिग्री (जैसे, 2) सुनिश्चित होती है।
• प्रशिक्षण डेटा: लेबल के रूप में सटीक इष्टतम टूर (Concorde द्वारा गणना किए गए) का उपयोग करके $N=100$ आकार के इंस्टेंस पर प्रशिक्षित किया गया।

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

1. दो-चरणीय पाइपलाइन: पहले ऐसे दृष्टिकोण के रूप में जो पूर्ण ग्राफ के बजाय पहले से ही विरल ह्यूरिस्टिक कैंडिडेट ग्राफ पर सीखा हुआ प्रूनिंग लागू करता है। यह सभी किनारों को प्रोसेस करने की $O(N^2)$ जटिलता से बचता है।
2. सोर्स-प्रोवेनेंस सिग्नल: यह प्रदर्शित करता है कि दो ह्यूरिस्टिक्स का फ्यूजन एक शक्तिशाली फीचर (कि क्या एक किनारा दोनों के प्रतिच्छेदन/intersection में है) बनाता है जो लर्निंग समस्या को सुलभ बनाता है। यहाँ तक कि सरल लॉजिस्टिक रिग्रेशन भी उच्च प्रदर्शन करता है क्योंकि यह सिग्नल बहुत प्रभावी है।
3. सामान्यीकरण (Generalizability): यह विधि डिस्टेंस-टाइप अगनोस्टिक है। यह बिना पुन: प्रशिक्षण या पैरामीटर ट्यूनिंग के चार TSPLIB दूरी परंपराओं और पांच स्थानिक वितरणों पर कार्य करती है।
4. स्केलेबिलिटी: यह विधि अपने प्रशिक्षण आकार ($N=100$) की तुलना में 5 गुना बड़े इंस्टेंस आकार ($N=500$) तक सामान्यीकृत होती है, जो बड़े पैमाने पर खराब प्रदर्शन करने वाले सिंगल-स्टेज ह्यूरिस्टिक्स से बेहतर है।

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

प्रयोग 20 TSP परिवारों (4 दूरी प्रकार $\times$ 5 वितरण) पर किए गए, जिनका आकार $N \in \{50, 100, 200, 500\}$ था।

• घनत्व में कमी (Density Reduction): दो-चरणीय विधि यूनियन बेस की तुलना में कैंडिडेट ग्राफ के घनत्व को 37% से 47% तक कम करती है।
  • $N=500$ पर, किनारों की संख्या $\approx 5.93N$ (यूनियन) से घटकर $\approx 3.14N$ (यूनियन + XGBoost) हो जाती है।
• कवरेज रिटेंशन (Coverage Retention): आक्रामक प्रूनिंग के बावजूद, विधि सभी आकारों और दूरी प्रकारों में $\ge 99.69\%$ इष्टतम-टूर किनारों को बनाए रखती है।
• सॉल्वर प्रदर्शन:
  • अनप्रून्ड यूनियन बेस की तुलना में सॉल्विंग समय में 1.20$\times$ से 1.28$\times$ की गति वृद्धि (speedup) प्राप्त करने के लिए प्रून्ड ग्राफ को LKH को पास करने पर।
  • ऑप्टिमलिटी गैप (Optimality Gap): गैप बढ़ता नहीं है; कई मामलों में, यह थोड़ा कम हो जाता है, जो दर्शाता है कि प्रून्ड किनारे अनावश्यक थे।
• न्यूरल विधियों के साथ तुलना:
  • EUC_2D इंस्टेंस पर अत्याधुनिक न्यूरल स्पारसिफायर (DIFUSCO, AttGCN, DIMES) के विरुद्ध तुलना की गई।
  • प्रस्तावित विधि उच्च कवरेज (न्यूरल विधियों के 96-98% बनाम 99.95%) और कम घनत्व प्राप्त करती है।
  • महत्वपूर्ण रूप से, प्रस्तावित विधि गैर-यूक्लिडियन (non-Euclidean) दूरियों पर भी कार्य करती है जहाँ न्यूरल विधियाँ विफल हो जाती हैं।
• एब्लेशन अध्ययन (Ablation Studies):
  • पूर्ण ग्राफ पर सीधे ML लागू करना (चरण 1 को छोड़कर) क्लास असंतुलन और संरचनात्मक मार्गदर्शन की कमी के कारण अप्रभावी है।
  • अकेले POPMUSIC को प्रून करना हानिकारक है क्योंकि यह पहले से ही बहुत विरल है; मॉडल को सीखने के लिए "सुरक्षित" किनारे प्रदान करने के लिए यूनियन आवश्यक है।

5. महत्व और सीमाएँ (Significance and Limitations)

महत्व:

• व्यावहारिक दक्षता: प्रूनिंग चरण नगण्य ओवरहेड (< CPU पर प्रति इंस्टेंस 83ms) जोड़ता है, जिससे यह वास्तविक दुनिया के उपयोग के लिए व्यवहार्य हो जाता है।
• मजबूती (Robustness): यह एकल ह्यूरिस्टिक की तुलना में "रिकॉल बनाम स्पैरसिटी" के ट्रेड-ऑफ को बेहतर ढंग से हल करता है, विशेष रूप से बड़े पैमाने पर जहाँ POPMUSIC विफल हो जाता है।
• सरलता: सरल मॉडलों (लॉजिस्टिक रिग्रेशन) की सफलता यह सुझाव देती है कि ह्यूरिस्टिक यूनियन पर्याप्त सिग्नल प्रदान करता है, जिससे जटिल डीप लर्निंग आर्किटेक्चर की आवश्यकता कम हो जाती है।

सीमाएँ:

• अनुभवजन्य प्रकृति (Empirical Nature): कोई सैद्धांतिक गारंटी प्रदान नहीं की गई है कि इष्टतम किनारे सुरक्षित रहेंगे।
• प्रशिक्षण लागत: प्रशिक्षण के लिए सटीक इष्टतम टूर (Concorde के माध्यम से) की आवश्यकता होती है, जो बहुत बड़े $N$ के लिए स्केलेबिलिटी को सीमित करता है।
• कठिन मामले: "कॉरिडोर" (Corridor) वितरणों पर बड़े पैमाने पर प्रदर्शन थोड़ा कम हो जाता है, जहाँ लंबे, वैश्विक रूप से महत्वपूर्ण किनारों को स्थानीय विशेषताओं का उपयोग करके पहचानना कठिन होता है।
• सिंथेटिक बेंचमार्क: शास्त्रीय TSPLIB इंस्टेंस (जिनमें अलग संरचनात्मक गुण हो सकते हैं) पर प्रदर्शन का पूर्ण सत्यापन अभी बाकी है।

निष्कर्षतः, यह शोध पत्र एक अत्यंत प्रभावी, सामान्यीकरण योग्य और गणनात्मक रूप से कुशल TSP ग्राफ स्पारसिफिकेशन फ्रेमवर्क प्रस्तुत करता है, जो पारंपरिक तरीकों और हालिया न्यूरल दृष्टिकोणों दोनों से बेहतर प्रदर्शन करने के लिए क्लासिकल ह्यूरिस्टिक्स और लाइटवेट मशीन लर्निंग के तालमेल का लाभ उठाता है।