Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation

2026/03/09 by Yuxin Tang, Zhiyuan Xin, Zhimin Ding +4 · 1 voice
Computer Science · #cs.AI #cs.DB #cs.MS

paper · pdf · doi:10.14778/3797919.3797921

Abstract

A tensor-relational computation is a relational computation where individual tuples carry vectors, matrices, or higher-dimensional arrays. An advantage of tensor-relational computation is that the overall computation can be executed on top of a relational system, inheriting the system's ability to automatically handle very large inputs with high levels of sparsity while high-performance kernels (such as optimized matrix-matrix multiplication codes) can be used to perform most of the underlying mathematical operations. In this paper, we introduce upper-case-lower-case EinSum, which is a tensor-relational version of the classical Einstein Summation Notation. We study how to automatically rewrite a computation in Einstein Notation into upper-case-lower-case EinSum so that computationally intensive components are executed using efficient numerical kernels, while sparsity is managed relationally.

Citations

• cuTeSpMM: Accelerating Sparse-Dense Matrix Multiplication using GPU Tensor Cores
• EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution
• Galley: Modern Query Optimization for Sparse Tensor Programs
• TorchGT: A Holistic System for Large-scale Graph Transformer Training
• PyTond: Efficient Python Data Science on the Shoulders of Databases
• The Duck's Brain: Training and Inference of Neural Networks in Modern Database Engines
• Optimizing Tensor Programs on Flexible Storage
• SparseTIR: Composable Abstractions for Sparse Compilation in Deep Learning
• Tensor Relational Algebra for Machine Learning System Design
• Array Programming with NumPy
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• SystemDS: A Declarative Machine Learning System for the End-to-End Data Science Lifecycle
• AliGraph: A Comprehensive Graph Neural Network Platform
• Pitfalls of Graph Neural Network Evaluation
• Format Abstraction for Sparse Tensor Algebra Compilers
• PlinyCompute: A Platform for High-Performance, Distributed, Data-Intensive Tool Development
• Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking
• Semi-Supervised Classification with Graph Convolutional Networks
• Revisiting Semi-Supervised Learning with Graph Embeddings
• A Comprehensive Survey on Graph Neural Networks
• Evolutionary trees from DNA sequences: A maximum likelihood approach

Discussions

• Yuxin Tang, Zhiyuan Xin, Zhimin Ding, Xinyu Yao, Daniel Bourgeois, Tirthak Patel, Chris Jermaine: Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation https://arxiv.org/ [bsky, 0 points, 0 comments]

Related

• EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution
• High Performance Rearrangement and Multiplication Routines for Sparse Tensor Arithmetic
• Sparse Tensor Algebra as a Parallel Programming Model
• Sparse Tensor Algebra Optimizations with Workspaces
• A High-Performance Sparse Tensor Algebra Compiler in Multi-Level IR