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

2020/03/22 by Xiaoya Li, Li, Xiaoya, Yuxian Meng +9 · 13 citations
Computer Science · Mathematics · #Advanced Graph Neural Networks #Algorithm #Artificial intelligence #Computation and Language (cs.CL) #Computer science #Construct (python library) #Dense graph #FOS: Computer and information sciences #Graph #Machine Learning (cs.LG) #Mathematics #Property (philosophy) #Quadratic equation #Recommender Systems and Techniques #Sequence (biology) #Structuring #Theoretical computer science #Topic Modeling #Variety (cybernetics) #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2003.09833

published in arXiv (Cornell University) (Cornell University) · To appear at NeurIPS 2020

openalex publication_date 2020/03/22 · openalex created_date 2020/03/27 · arxiv created 2020/09/29 · arxiv updated 2020/09/30 · openalex updated_date 2026/07/28

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.

Citations

• Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
• Adam: A Method for Stochastic Optimization
• Long Short-Term Memory
• Neural Machine Translation by Jointly Learning to Align and Translate
• Collective Classification in Network Data
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Representation Learning on Graphs with Jumping Knowledge Networks
• GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations
• Learning to Propagate Labels: Transductive Propagation Network for Few-shot Learning
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Generating Long Sequences with Sparse Transformers
• Sparse Graph Attention Networks
• Reformer: The Efficient Transformer
• Geom-GCN: Geometric Graph Convolutional Networks
• Unifying Graph Convolutional Neural Networks and Label Propagation
• ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks
• Learning Multiple Layers of Features from Tiny Images

Cited by

• BLaST: High Performance Inference and Pretraining using BLock Sparse Transformers

Related

• A Generic Shared Attention Mechanism for Various Backbone Neural Networks
• Efficient Attention Network: Accelerate Attention by Searching Where to Plug
• Less Memory, Faster Speed: Refining Self-Attention Module for Image Reconstruction
• Convolutional Self-Attention Networks
• Element-wise Attention Is All You Need