Graph Neural Networks Meet Local Search for the Weighted Total Domination Problem

Abstract

In den letzten Jahren (oder eher Jahrzehnten) gewinnen neuronale Netze als zentraler Bestandteil vieler moderner Ansätze für maschinelles Lernen immer mehr an Bedeutung, nicht nur in der IT-bezogenen Forschung, sondern auch in Anwendungen aus der realen Welt. Graph Neural Networks (GNNs) sind in der Öffentlichkeit weniger bekannt, werden jedoch nicht nur in vielen modernen Anwendungsfeldern wie Natural Language Processing oder Visual Computing verwendet, sondern können auch auf klassische Graphenprobleme wie das Problem des Handelsreisenden angewandt werden.In sogenannten End-to-end Learning Ansätzen wird ein neuronales Netz mit dem Ziel trainiert, mit nur minimalen weiteren algorithmischen Hilfestellungen Näherungslösungen für kombinatorische Optimierungsprobleme zu liefern. Trotz ausgefeilter Techniken bleibt die Qualität solcher Lösungen häufig immer noch weit hinter jenen klassischer Optimierungsalgorithmen zurück. In dieser Arbeit beschäftigen wir uns damit, die Ausgabe eines solchen GNNs zu verwenden, um die Performance eines klassischen metaheuristischen Ansatzes, der Adaptive Large Neighborhood Search (ALNS), auf dem eigentlichen Problem zu verbessern. Eine ALNS besteht aus Destroy- und Repair-Methoden, die auf einer temporären Lösung des Problems agieren. Zunächst entwickeln und testen wir traditionelle Methoden. Danach werden Destroy-Methoden entwickelt, die die Ausgabe des GNNs verwenden, und wir vergleichen die beiden Ansätze.Dies wird anhand des Weighted Total Domination Problem (WTDP) demonstriert, ein klassisches Graphenproblem, das das bekannte (Total) Dominating Set Problem um eine Zielfunktion erweitert, die Gewichte auf Knoten und Kanten des Graphen miteinbezieht. Im Zuge der Arbeit werden für dieses Problem auch Regeln zur Vorbehandlung der Probleminstanzen, ein neuartiger Ansatz für eine "abstimmungsbasierte" ALNS-Methode, sowie die Berechnung von Features zum Trainieren des GNNs vorgestellt.Unsere Ergebnisse zeigen, dass ein Mix aus traditionellen ALNS Methoden, zusammen mit den vom GNN unterstützten Methoden, im Allgemeinen bessere Lösungen liefern als die traditionellen Methoden alleine.

In the last years (or rather decades), neural networks as the core of many modern-day machine learning approaches are becoming more influential, not only in computer science related research, but also in real world applications. Graph Neural Networks (GNNs), while less known in the public, are not only used in popular fields like natural language processing or visual computing, but are also applied to classical graph problems such as the Travelling Salesman Problem (TSP).In so-called end-to-end learning approaches, a neural network is trained with the goal to find approximate solutions for combinatoric optimization problems with minimal additional algorithmic help. Despite sophisticated techniques, the quality of such solutions often falls far behind those from classical optimization algorithms. In this work, we investigate the possibilities of using the output to improve a metaheuristical approach, the Adaptive Large Neighborhood Search (ALNS). An ALNS consists of destroy- and repair-methods that act on intermediate solutions. We first develop and test traditional methods, and afterwards use a set of destroy-methods that utilize the output of the GNN for each vertex. Both approaches are experimentally compared.This demonstrated on the Weighted Total Domination Problem (WTDP), an extension of the well-known Dominating Set Problem, which introduces an objective function based on vertex and edge weights. For this problem, we also present preprocessing rules, a novel "voting-based" ALNS method, and custom feature computations for GNN training.Our results show that the mix of the traditional ALNS methods, together with the GNN-supported methods, are in general performing better than the traditional methods alone.