DeepHAM: Applying Deep Learning and Reduction Peeling to Determine Optimal Heuristics for Finding Hamiltonian Paths

Who: Ed Bielawa (ebielawa), Hammad Izhar (hizhar), Joseph Rotella (jrotella)

Reflection

https://docs.google.com/document/d/1eFDpxD_rhgcHBhqWEHBeZ0lQYeLS5TkC9cuY1BwaffY/edit?usp=sharing (contains reflections for both check-ins as well as our final reflection)

Slides: https://drive.google.com/file/d/1MTHjt8m7yErb6-qF0wrdOiO6CMSN9tbZ/view

Introduction:

Building off of prior work done by Langedal et al., our goal is to use deep-learning techniques to generate heuristics for finding Hamiltonian paths in undirected graphs. This problem is of interest because it is NP-complete; Langedal et al. have shown that DL techniques can be successfully applied to generate novel heuristics for improving both the efficiency and correctness of polynomial-time approximation algorithms for NP-complete problems. We arrived at this topic through interests derived from prior coursework in theoretical computer science and graph theory. This is an unsupervised learning problem; we will be using a GNN after applying known kernelization techniques.

Related Work:

Langedal et al. (2022). Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks

This paper provides the main framework we would like to tackle our problem with. The idea is that there are already well-known methods, known as kernelization (or reduction) rules, which can be used to automatically identify vertices that should be in the minimum weighted vertex cover. We use these rules to reduce the graph to a state where we can no longer apply these rules. The GNN is then tasked with assigning probabilities to each vertex being a part of the vertex cover. We select the vertex with highest degree, and the repeat applying the reduction rules until a vertex cover is achived. After computing a vertex cover we can use search algorithms to try and improve the cover, until we can no longer.

Xin et al. (2021). NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem

This paper details an algorithm known to be a pretty good way of trying to approximate a solution to the Traveling Salesman Problem.

Data:

We will generate our own data for this project. In particular, we will generate random graphs. To obtain a random graph, we can start with a random spanning tree on n vertices, then aleatorically insert edges among the vertices of the tree to obtain a random graph with n vertices. To produce a graph with n vertices with a Hamiltonian path, we simply begin with the path graph Pn and insert random edges. Note: to prevent our model from “learning the specific path” with which we begin, we will need to randomize the vertex order in Pn. This is a relatively minor adjustment. Once we’ve trained the model on graphs with known Hamiltonian paths, we can begin to train it on completely random graphs. We plan to have our network attempt to learn reduction rules, so we will not apply these to the input data.

Methodology:

Our model will be a graph neural network (GNN) and use a standard training architecture for such a model, following a similar methodology to the one proposed by Langedal et al. We will first apply as many reductions as possible, based on which we will find a most-likely candidate from which to construct our Hamiltonian path. Since this approach worked well for solving the minimum weighted vertex cover—a similarly NP-complete problem on graphs—we believe that it should translate well to the case of Hamiltonian paths. Note that these reduction rules are not related to the model at all. Our goal is to simplify the graph as much as possible, then apply the model if necessary. In the event we hit significant obstacles for implementing this project, we would like to apply neural networks for other graph problems. Potential ideas include generating edge colorings of complete graphs to demonstrate tighter lower bounds for Ramsey numbers. The methodology would be similar. Attempt to apply as many relevant reduction rules as possible, and use a neural network to generate the most likely edge color. Another alternative could be maximal matchings for multipartite graphs. Again, similar methodology to the above cases, just using different reduction rules, loss metrics, and model architectures.

Metrics:

“Success” would be efficiently finding a Hamiltonian path. Since we have a virtually unlimited supply of data, there is no particularly notable “experimentation” procedure; we can simply generate more graphs and see how the model performs. (In addition to fully random generation, we can attempt to identify and construct particularly pathological examples so as to evaluate the model’s performance on edge cases.) Our notion of accuracy is the correctness of the path produced: whether a path is Hamiltonian does not admit degrees of accuracy, but we can still produce a graded notion of accuracy for intermediate stages based on the number of self-crossings of the output path of the model (more is worse; a Hamiltonian path has 0). In addition to these notions of accuracy, a key impetus for pursuing this project is efficiency; thus, we can also assess our model on the basis of its compute time. (Both compute time and result accuracy can also be benchmarked against existing approximation algorithms.)

Our base, target, and stretch goals are as follows: Base: Given an input graph, our network will generate a walk (given the significant complexity of the model and algorithms involved, we believe that this goal, while modest, is reasonable as a base goal) Target: For a graph with known Hamiltonian path, our model can find it. Verifying a proposed Hamiltonian path is indeed Hamiltonian is relatively efficient Stretch: Generalize to the cases of weighted (i.e., path weight-minimality/maximality) and/or directed graphs

Ethics:

The Hamiltonian path problem is closely related to the traveling salesperson problem (indeed, the canonical proof of the NP-hardness of TSP involves a reduction to HAMPATH). This problem is broadly relevant in a variety of applications, including package delivery, transportation, and civilian and military flight and UAV routing. These issues not only have logistical and efficiency implications for these sectors, but may also affect the individuals who work in or are affected by them, including those who deliver for delivery companies and civilians in areas in which autonomous weapons systems are used.

Deep Learning is a good approach to this problem because it is NP-complete, and so it is unlikely that a polynomial-time solution is possible. Moreover, it is hard to devise novel heuristics and effectively apply them, since the space of candidate heuristics is quite large; a deep learning model is well-suited to identifying particular such methods among the many possibilities, especially as demonstrated by the prior work cited earlier.

Division of Labor:

At this point in time, our effort is best spent in a largely centralized manner in understanding the exact techniques used in other applications of deep learning to graphs (including the architecture of GNNs) and translating them to the case of Hamiltonian paths. Once we have a clearer idea of exactly how we will structure our model, we will subdivide different components of the model implementation as well as the implementation of data generation, reductions rules for graphs, and metrics for the model (likely 2:1 between these two components). The division of labor may shift as we get a better grasp of the difficulty of these components.