The Ubiquitous Sparse Matrix-Matrix Products
This work addresses a foundational computational bottleneck for researchers and practitioners in machine learning, computational biology, and scientific computing, offering a broad theoretical framework.
The paper tackles the problem of sparse matrix-matrix multiplication, a fundamental operation in data science applications like graph algorithms and neural networks, by providing a unifying treatment that extends to arbitrary algebraic semirings and heterogeneous algebras.
Multiplication of a sparse matrix with another (dense or sparse) matrix is a fundamental operation that captures the computational patterns of many data science applications, including but not limited to graph algorithms, sparsely connected neural networks, graph neural networks, clustering, and many-to-many comparisons of biological sequencing data. In many application scenarios, the matrix multiplication takes places on an arbitrary algebraic semiring where the scalar operations are overloaded with user-defined functions with certain properties or a more general heterogenous algebra where even the domains of the input matrices can be different. Here, we provide a unifying treatment of the sparse matrix-matrix operation and its rich application space including machine learning, computational biology and chemistry, graph algorithms, and scientific computing.