This master's thesis investigates the application of Graph Neural Networks (GNNs) to address scalability challenges in combinatorial optimization, with a primary focus on the minimum Total Dominating set Problem (TDP) and additionally the related Carrier Scheduling Problem (CSP) in networks of Internet of Things. The research identifies the NP-hard nature of these problems as a fundamental challenge and addresses how to improve predictions on input graphs of sizes much larger than seen during training phase. Further, the thesis explores the instability in such scalability when leveraging GNNs for TDP and CSP. Two primary measures to counter this scalability problem are proposed and tested: incorporating node degree as an additional feature and modifying the attention mechanism in GNNs. Results indicate that these countermeasures show promise in addressing scalability issues in TDP, with node degree inclusion demonstrating overall performance improvements while the modified attention mechanism presents a nuanced outcome with some metrics improved at the cost of others. Application of these methods to CSP yields bleak results, evincing the challenges of scalability in more complex problem domains. The thesis contributes by detecting and addressing scalability challenges in combinatorial optimization using GNNs and provides insights for further research in refining methodologies for real-world applications. / Denna masteruppsats undersöker tillämpningen av Grafiska Neurala Nätverk (GNN) för att hantera utmaningar inom skalbarhet vid kombinatorisk optimering, med ett primärt fokus på minimum Total Dominating set Problem (TDP) samt även det relaterade Carrier Scheduling Problem (CSP) i nätverk inom Internet of Things. Studien identifierar den NP-svåra karaktären av dessa problem som en grundläggande utmaning och lyfter hur man kan förbättra prediktioner på indatagrafer av storlekar som är mycket större än vad man sett under träningsfasen. Vidare utforskar uppsatsen instabiliteten i sådan skalbarhet när man utnyttjar GNN för TDP och CSP. Två primära åtgärder mot detta skalbarhetsproblem föreslås och testas: inkorporering av nodgrad som ett extra attribut och modifiering av attention-mekanismer i GNN. Resultaten indikerar att dessa motåtgärder har potential för att angripa skalbarhetsproblem i TDP, där inkludering av nodgrad ger övergripande prestandaförbättringar medan den modifierade attention-mekanismen ger ett mer tvetydigt resultat med vissa mätvärden förbättrade på bekostnad av andra. Tillämpning av dessa metoder på CSP ger svaga resultat, vilket antyder om utmaningarna med skalbarhet i mer komplexa problemdomäner. Uppsatsen bidrar genom att upptäcka och adressera skalbarhetsutmaningar i kombinatorisk optimering med hjälp av GNN och ger insikter för vidare forskning i att förfina metoder för verkliga tillämpningar.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-344155 |
| Date | January 2023 |
| Creators | Hårderup, Peder |
| Publisher | KTH, Matematik (Avd.) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2023:446 |
Page generated in 0.0029 seconds