Using graph neural networks in local search for edge-based relaxations of the maximum clique problem

Abstract

Diese Arbeit untersucht den Einsatz von \emph{Graph Neural Networks} (GNNs) in einer Metaheuristik für kantenbasierte Relaxationen des Maximum Clique Problems (MCP), dem Maximum Quasi-Clique Problem (MQCP) und dem Maximum Defective Clique Problem (MDCP). Das Ziel des MCPs ist es, eine Knotenmenge maximaler Kardinalität zu finden, sodass alle Knoten miteinander durch eine Kante verbunden sind. Das Problem ist ein fundamentales NP-schweres kombinatorisches Optimierungsproblem mit zahlreichen Anwendungen, z.B. in der Bioinformatik oder der Analyse von sozialen Netzwerken. In manchen Anwendungen ist es notwendig, dass nicht nach vollständigen, sondern sehr dichten Subgraphen gesucht wird, weswegen das MQCP und das MDCP eingeführt wurden. Im Rahmen dieser Arbeit orientieren wir uns an den führenden heuristischen Methoden für die genannten Probleme und entwickeln eine Metaheuristik, LSBM, die auf lokaler Suche basiert und ein GNN verwendet, um die Nachbarschaft des derzeitigen Lösungskandidaten auf Knoten einzuschränken, die am ehesten zu einer Verbesserung der Lösung führen. In diesem Zusammenhang präsentieren wir auch einen Trainingsalgorithmus LSBM-T, der verwendet wird, um das GNN zu trainieren, eine Nachbarschaftssuche zu imitieren. Wir untersuchen unterschiedliche Ansätze, die Knoten im GNN zu initialisieren und verwenden eine Encoder-Decoder Architekur für das GNN, die auf dem Attention-Mechanismus aufbaut. Die Ergebnisse unser Evaluierung zeigen, dass unser Ansatz auf Benchmark-Instanzen mit bis zu 300 Knoten mit den führenden Methoden, die algorithmisch komplexer aufgebaut sind, in Bezug auf Lösungsqualität mithalten kann, auf größeren Instanzen jedoch nocht nicht. Darüber hinaus zeigen wir, dass unser Trainingsalgorithmus LSBM-T das GNN erfolgreich trainiert, und der Einsatz des GNNs in LSBM zu deutlich besseren Ergebnis führt als eine andere häufig verwendete Knotenbewertungsfunktion.

This thesis investigates the utilization of Graph Neural Networks (GNNs) in a local search-based metaheuristic for edge-based relaxations of the Maximum Clique Problem (MCP), namely, the Maximum Quasi-Clique Problem (MQCP) and the Maximum Defective Clique Problem (MDCP). The MCP is the problem of finding fully connected subsets of vertices of maximum size in a graph. It is a well-studied, fundamental NP-hard combinatorial optimization problem and has numerous applications in, e.g., bioinformatics and social network analysis. Some real-world applications however require relaxations of the clique model. Thus, researchers have come up with the MQCP and MDCP as a theoretical model for such applications. Due to the computational complexity of the considered problems, real-world instances are often infeasible to solve in practice using exact methods. Therefore, we develop a heuristic solution approach that is centered around local search, like most state-of-the-art algorithms for the MQCP and MDCP. We study and review the relevant literature and build upon the leading (meta)heuristic algorithms for the MQCP. The first main contribution of this thesis is a local search-based metaheuristic named LSBM that can utilize a GNN as a scoring function for restricting the neighborhoods during the local search procedure to the most promising vertices. Secondly, we propose a training algorithm LSBM-T that trains the GNN-based scoring function offline on randomly generated representative instances in an imitation learning setting. The expert strategy being imitated is an exhaustive search of a user-defined neighborhood structure. The GNN is thus trained to predict, which vertices in a neighborhood will most likely lead to an improved solution. We investigate different centrality-based and learning-based feature initialization methods, as the input graphs of the considered problems are non-attributed.Furthermore, we present an attention-based Encoder-Decoder GNN architecture built upon similar applications of GNNs in combinatorial optimization. The results on benchmark instances from the literature indicate that our approach can match the solution quality of the algorithmically more complex state-of-the-art methods for most instances with 300 vertices or less, but is not competitive yet for larger instances. However, it can clearly be seen that our training algorithm LSBM-T successfully trains the GNN-based scoring function to effectively guide the search, and LSBM with the trained GNN-based scoring function yields substantially better solutions than LSBM with a so far most often used scoring function.