Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP

• URL: http://arxiv.org/abs/2403.17159v1
• Date: Mon, 25 Mar 2024 20:16:16 GMT
• Title: Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP
• Authors: Attila Lischka, Jiaming Wu, Rafael Basso, Morteza Haghir Chehreghani, Balázs Kulcsár,
• Abstract summary: We propose a data preprocessing method that allows the encoders to focus on the most relevant parts of the Traveling Salesman Problem (TSP) instances only. We show that for GNNs appropriate sparsification and ensembles of different sparsification levels lead to substantial performance increases of the overall architecture.
• Score: 8.317022421446639
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity [74.51827323742506]
  We evaluate the necessity of adopting multi-layer attentions in Transformers on graphs. We show that one-layer propagation can be reduced to one-layer propagation, with the same capability for representation learning. It suggests a new technical path for building powerful and efficient Transformers on graphs.
  arXiv  Detail & Related papers  (2024-09-13T17:37:34Z)
• Graph as Point Set [31.448841287258116]
  This paper introduces a novel graph-to-set conversion method that transforms interconnected nodes into a set of independent points. It enables using set encoders to learn from graphs, thereby significantly expanding the design space of Graph Neural Networks. To demonstrate the effectiveness of our approach, we introduce Point Set Transformer (PST), a transformer architecture that accepts a point set converted from a graph as input.
  arXiv  Detail & Related papers  (2024-05-05T02:29:41Z)
• CT-MVSNet: Efficient Multi-View Stereo with Cross-scale Transformer [8.962657021133925]
  Cross-scale transformer (CT) processes feature representations at different stages without additional computation. We introduce an adaptive matching-aware transformer (AMT) that employs different interactive attention combinations at multiple scales. We also present a dual-feature guided aggregation (DFGA) that embeds the coarse global semantic information into the finer cost volume construction.
  arXiv  Detail & Related papers  (2023-12-14T01:33:18Z)
• SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations [75.71298846760303]
  We show that a one-layer attention can bring up surprisingly competitive performance across node property prediction benchmarks. We frame the proposed scheme as Simplified Graph Transformers (SGFormer), which is empowered by a simple attention model. We believe the proposed methodology alone enlightens a new technical path of independent interest for building Transformers on large graphs.
  arXiv  Detail & Related papers  (2023-06-19T08:03:25Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Is Attention All NeRF Needs? [103.51023982774599]
  Generalizable NeRF Transformer (GNT) is a pure, unified transformer-based architecture that efficiently reconstructs Neural Radiance Fields (NeRFs) on the fly from source views. GNT achieves generalizable neural scene representation and rendering, by encapsulating two transformer-based stages.
  arXiv  Detail & Related papers  (2022-07-27T05:09:54Z)
• FQ-ViT: Fully Quantized Vision Transformer without Retraining [13.82845665713633]
  We present a systematic method to reduce the performance degradation and inference complexity of Quantized Transformers. We are the first to achieve comparable accuracy degradation (1%) on fully quantized Vision Transformers.
  arXiv  Detail & Related papers  (2021-11-27T06:20:53Z)
• Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
  Vision Transformers (ViTs) have achieved impressive performance over various computer vision tasks. We propose Single-Path Vision Transformer pruning (SPViT) to efficiently and automatically compress the pre-trained ViTs. Our SPViT can trim 52.0% FLOPs for DeiT-B and get an impressive 0.6% top-1 accuracy gain simultaneously.
  arXiv  Detail & Related papers  (2021-11-23T11:35:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.