SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection

Abstract

While the self-attention mechanism has been widely used in a wide variety of tasks, it has the unfortunate property of a quadratic cost with respect to the input length, which makes it difficult to deal with long inputs. In this paper, we present a method for accelerating and structuring self-attentions: Sparse Adaptive Connection (SAC). In SAC, we regard the input sequence as a graph and attention operations are performed between linked nodes. In contrast with previous self-attention models with pre-defined structures (edges), the model learns to construct attention edges to improve task-specific performances. In this way, the model is able to select the most salient nodes and reduce the quadratic complexity regardless of the sequence length. Based on SAC, we show that previous variants of self-attention models are its special cases. Through extensive experiments on neural machine translation, language modeling, graph representation learning and image classification, we demonstrate SAC is competitive with state-of-the-art models while significantly reducing memory cost.

arXiv commentTo appear at NeurIPS 2020

References in corpus (18)

• Adam: A Method for Stochastic Optimization
• Neural Machine Translation by Jointly Learning to Align and Translate
• Semi-Supervised Classification with Graph Convolutional Networks
• Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
• Inductive Representation Learning on Large Graphs
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Predicting multicellular function through multi-layer tissue networks
• Learning to Propagate Labels: Transductive Propagation Network for Few-shot Learning
• Generating Long Sequences with Sparse Transformers
• Reformer: The Efficient Transformer
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Watch Your Step: Learning Node Embeddings via Graph Attention
• Geom-GCN: Geometric Graph Convolutional Networks
• Unifying Graph Convolutional Neural Networks and Label Propagation
• BP-Transformer: Modelling Long-Range Context via Binary Partitioning
• GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations
• Sparse Graph Attention Networks

Cited by in corpus (4)

• GNN-LM: Language Modeling based on Global Contexts via GNN
• Sparse Attentive Memory Network for Click-through Rate Prediction with Long Sequences
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers
• Summarize, Outline, and Elaborate: Long-Text Generation via Hierarchical Supervision from Extractive Summaries