How use DGL to solve ATSP graph? as it is directed graph

[walidgeuttala]

Let’s say I have a directed ATSP graph. The best approach to solving such a problem is to transform it into a string graph, where the edges become nodes and weights are assigned at the node level. Then, we learn the probability of the edge belonging to the optimal solution given the labels. But what if we don’t have labels? What do you think is the best loss function to encode properties about the ATSP problem? For example, the cycle, ensuring all nodes are visited once, and selecting the most important edges with the least global effect in the loss. On the other hand, do you think transforming ATSP to string graph in the undirected way is the best approach? Or should we encode edge types such as source-source, parallel, source-target, target-source, and target-target? Alternatively, should we apply a heterogeneous graph with 5 types of edges and 1 type of node? Keeping in mind the structure of the string graph with the 5 subgraph edge types, which may exhibit similarities and sometimes contain many connected components. What is the most efficient way of solving this problem? I hope you share your ideas so I can learn, as I’m new to using GNN and DGL.

Or perhaps it’s better not to use GNNs for ATSP, as the graph is complete and lacks any unique relations except for the weights

[dyru]

1. By string graph, you actually mean line graph, right (coz you mentioned the edge types such as source-source, parallel, etc.)? It is an interesting view that converting the problem to assigning probabilities of belonging to an optimal path to edges, but deriving a solution from the probability matrix could still be non-trivial. Could you elaborate more on how will you define such probabilities?

2. ASTP requires global information in the whole graph with sufficient interactions, which contains very long dependencies on the graph. However, GNNs focus more on the patterns of local structures. I think it might not be a good solution to modeling such long dependencies.

[walidgeuttala]

Hi @dyru , thank you for your comment.

1. As we train the model to generate the probability matrix, if it predicts the matrix very well, we have two options. If the ATSP problem we have has a unique solution, then running a greedy search will result in the tour, starting from node 0 and selecting the best probability in each row, which will determine the best edges. On the other hand, we could apply local search methods such as 2-opt or beam search, which would give us good results as studied in the literature.
2. That sounds logical. However, on the other hand, our ATSP graph is a complete graph, and the line graph will be well-connected. This means that if we use 3 or 4 layers of GNN, it will cover the entire graph to learn the global properties. But at the same time, we will face two problems: oversmoothing and oversquashing, which are addressed in the literature. Additionally, we can add some edges that can transform the information better than the original graph, but we need a mechanism to do this effectively. Also, I think the line graph is a heterophilic graph, as just changing one edge from the neighboring edge could result in a very bad cost most of the time. However, the general rule is that the GNN was created to solve sparse graphs, and the line graph is sparse. I think if we could overcome these problems and study the properties very well, we could find a good GNN method that solves the problem very effectively.