Less Is More -- On the Importance of Sparsification for Transformers and
  Graph Neural Networks for TSP
Attila Lischka Jiaming Wu Rafael Basso Morteza Haghir Chehreghani Balázs Kulcsár
Most of the recent studies tackling routing problems like the Traveling
Salesman Problem (TSP) with machine learning use a transformer or Graph Neural
Network (GNN) based encoder architecture. However, many of them apply these
encoders naively by allowing them to aggregate information over the whole TSP
instances. We, on the other hand, propose a data preprocessing method that
allows the encoders to focus on the most relevant parts of the TSP instances
only. In particular, we propose graph sparsification for TSP graph
representations passed to GNNs and attention masking for TSP instances passed
to transformers where the masks correspond to the adjacency matrices of the
sparse TSP graph representations. Furthermore, we propose ensembles of
different sparsification levels allowing models to focus on the most promising
parts while also allowing information flow between all nodes of a TSP instance.
In the experimental studies, we show that for GNNs appropriate sparsification
and ensembles of different sparsification levels lead to substantial
performance increases of the overall architecture. We also design a new,
state-of-the-art transformer encoder with ensembles of attention masking. These
transformers increase model performance from a gap of $0.16\%$ to $0.10\%$ for
TSP instances of size 100 and from $0.02\%$ to $0.00\%$ for TSP instances of
size 50.