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

Yuxin Tang; Zhiyuan Xin; Zhimin Ding; Xinyu Yao; Daniel Bourgeois; Tirthak Patel; Chris Jermaine

cs.MSMar 9, 2026

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

Authors: Yuxin Tang, Zhiyuan Xin, Zhimin Ding, Xinyu Yao, Daniel Bourgeois, Tirthak Patel, Chris Jermaine

Organizations: Rice University Houston, Texas, USA

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.

Figures & tables

Dataset	Classes	Features	Nodes	Edges
Cora	7	1,433	2,485	5,069
Planetoid.Cora ( Yang et al., 2016 )	7	1,433	2,708	10,556
Planetoid
.CiteSeer ( Yang et al., 2016 )	6	3,703	3,327	9,104
CitationFull
.CiteSeer ( Bojchevski and Günnemann, 2017 )	6	602	4,230	10,674

Table 1. Statistics of the datasets after graph standardization. Datasets marked with * are used for distributed execution.

Dataset and		Tensor-based		SparseEinSum
num machines		DGL	Ali	Opt	2nd	3rd
ogbn-arxiv	1	4.3	12.9	8.3	13.4	21.8
	2	1.6	6.9	5.2	8.8	12.6
	4	0.9	3.4	2.0	4.1	6.3
	8	0.6	2.0	1.2	3.6	5.7
ogbn-products	1	20.3	96.7	31.4	35.7	37.2

Table 2. Running time comparison (in seconds) for one iteration of GCN training across different cluster sizes. DGL (PyTorch) and AliGraph are compared with the top three SparseEinSum decompositions.

Dataset	Qubits	Depth	Width	Gate Count
seca_n11	11	37	11	1275
multiplier_n13	13	7	13	496

Table 3. Dataset statistics for quantum benchmarks.

Circuit	Num	SparseEinSum
	Machines	Opt	2nd Best	3rd Best
seca_n11	1	36.124	26.7	32.013
	2	21.214	27.512	27.752
	4	13.817	14.347	15.424
	8	10.094	12.531	12.309
multiplier_n13	1	102.632	105.316	116.229

Table 4. Time (secs) vs. machines for quantum circuits.

Method	Datasets
	Cora	P.	P.Cite	C.Cite	A.	A.
		Cora	Seer	Seer	Photo	Comp
	Sparse Attention Computation
Hyper	866	901	1497	40	2416	7801
PstGSQL	8017	7990	12156	619	18429	OOD
SQLite	22052	22084	TLE	34875	TLE	OOD

Table 5. Running time (in seconds) for attention computations. P stands for Planetoid, C: CitationFull, A: Amazon. OOD is Out of Disk, as the database wrote too much data.

Method	Datasets
	Cora	P.	P.Cite	C.Cite	A.	A.
		Cora	Seer	Seer	Photo	Comp
	Graph Conv. Neural Network
Hyper	10.7	10.8	21.021	4.4	197.5	390.4
PstGSQL	16.0	16.0	30.9	7.7	436.1	830.3
SQLite	TLE	TLE	TLE	TLE	TLE	TLE

Table 6. Graph convolutional neural network running times (in seconds). TLE indicates Time Limit Exceeded.

UCLC EinSum	Planetoid.CiteSeer
$\textbf{T}_{I,k}^{0}\leftarrow\sum_{M}\textbf{X}_{I,M}\times\textbf{W}_{M,k}^{Q}$	X (INT i, INT m, DOUBLE val) $\textbf{W}^{Q}\texttt{(INT m, TENSOR[1024] val)}$
$\textbf{T}_{J,k}^{1}\leftarrow\sum_{N}\textbf{X}_{J,N}\times\textbf{W}_{N,k}^{K}$	X (INT j, INT n, DOUBLE val) $\textbf{W}^{K}\texttt{(INT n, TENSOR[1024] val)}$
$\textbf{T}_{I,J,k}^{2}\leftarrow\sum_{\emptyset}\textbf{T}_{I,k}^{0}\times\textbf{A}_{I,J}$	$\textbf{T}^{0}\texttt{(INT i, TENSOR[1024] val)}$ A (INT i, INT j, DOUBLE val)
$\textbf{T}_{I,J}^{3}\leftarrow\sum_{k}\textbf{T}_{I,J,k}^{2}\times\textbf{T}_{J,k}^{1}$	$\textbf{T}^{2}\texttt{(INT i, INT j,}$ TENSOR[1024] val) $\textbf{T}^{1}\texttt{(INT j, TENSOR[1024] val)}$
$\textbf{Attn}_{I,J}\leftarrow\sum_{\emptyset}\frac{1}{\sqrt{d_{k}}}(\textbf{T}_{I,J}^{3})$	$\textbf{T}^{3}\texttt{(INT i, INT j, DOUBLE val)}$

Table 7. Upper-case-lower-case Einstein notation produced by the SparseEinSum for Planetoid.CiteSeer.

Upper-Case-Lower-Case EinSum	CitationFull.CiteSeer	Amazon.Computers
$\textbf{T}_{I,K}^{0}\leftarrow\sum_{J}\hat{\textbf{D}}_{I,J}\times\hat{\textbf{A}}_{J,K}$	$\hat{\textbf{D}}\texttt{(INT i, INT j, DOUBLE }\texttt{val)}$ $\hat{\textbf{A}}\texttt{(INT j, INT k, DOUBLE val)}$	$\hat{\textbf{D}}\texttt{(INT i, INT j, DOUBLE val)}$ $\hat{\textbf{A}}\texttt{(INT j, INT k, DOUBLE val)}$
$\textbf{T}_{I,L}^{1}\leftarrow\sum_{K}\textbf{T}_{I,K}^{0}\times\hat{\textbf{D}}_{K,L}$	$\textbf{T}^{0}\texttt{(INT i, INT k, DOUBLE val)}$ $\hat{\textbf{D}}\texttt{(INT k, INT l, DOUBLE val)}$	$\textbf{T}^{0}\texttt{(INT i, INT k, DOUBLE val)}$ $\hat{\textbf{D}}\texttt{(INT k, INT l, DOUBLE val)}$
$\textbf{T}_{I,m}^{2}\leftarrow\sum_{L}\textbf{T}_{I,L}^{1}\times\textbf{H}_{L,m}^{(l)}$	$\textbf{T}^{1}\texttt{(INT i, INT l, DOUBLE val)}$ $\textbf{H}^{(l)}\texttt{(INT l, TENSOR[602] val)}$	$\textbf{T}^{1}\texttt{(INT i, INT l, DOUBLE val)}$ $\textbf{H}^{(l)}\texttt{(INT l, TENSOR[767] val)}$
$\textbf{T}_{I,n}^{3}\leftarrow\sum_{m}\textbf{T}_{I,m}^{2}\times\textbf{W}_{m,n}^{(l)}$	$\textbf{T}^{2}\texttt{(INT i, TENSOR[602] val)}$ $\textbf{W}^{(l)}\texttt{ (TENSOR[602][256] val)}$	$\textbf{T}^{2}\texttt{(INT i, TENSOR[767] val)}$ $\textbf{W}^{(l)}\texttt{ (TENSOR[767][256] val)}$
$\textbf{H}_{I,n}^{(l+1)}\leftarrow\sum_{\emptyset}\sigma(\textbf{T}_{I,n}^{3})$	$\textbf{T}^{3}\texttt{(INT i, TENSOR[256] val)}$	$\textbf{T}^{3}\texttt{(INT i, TENSOR[256] val)}$

Table 8. Upper-case-lower-case Einstein notation produced by the SparseEinSum compiler for the GCN computation, along with the corresponding relational schemas, for two of the test datasets.

Method	Datasets
	Cora	P.	P.Cite	C.Cite	A.	A.
		Cora	Seer	Seer	Photo	Comp
	Sparse Attention Computation
SEinSum	4.5	4.7	8.0	7.7	192	265
Greedy	21	23	52	17	769	884
	Dense Attention Computation

Table 9. Comparing pure greedy runtime with the full dynamic programming solution for the attention computation.

	Datasets
Comp-	Cora	P.	P.Cite	C.Cite	A.	A.
onent		Cora	Seer	Seer	Photo	Comp
	Sparse Attention Computation
Exec.	4.5	4.7	8.0	7.7	192	265
Schema	253	96	428	86	344	239
SQL	46	11	32	2.0	5.4	3.4

Table 10. Running time for the various system components, attention computation, in seconds. “Exec.” is the actual execution time, “Schema” is the time to pre-process the data and generate the schema, “SQL” is the time to generate the SQL including the data loading code, and “Kernels” is the time to generate the kernels using TACO.

	Perturbation
None	$C_{\textrm{xfer}}$	$C_{\textrm{xfer}}$	$C_{\textrm{krnel}}$	$C_{\textrm{krnel}}$	$C_{\textrm{fixed}}$	$C_{\textrm{fixed}}$
(as-is)	$\times\frac{1}{10}$	$\times 10$	$\times\frac{1}{10}$	$\times 10$	$\times\frac{1}{10}$	$\times 10$
192	130	253	294	1027	1027	305

Table 11. Effect of perturbing the various cost parameters (

C_{\textrm{xfer}},C_{\textrm{krnel}},C_{\textrm{fixed}}

) on the running time for the sparse attention computation on the Amazon.Photo data set.

Error	Datasets
	Cora	P.	P.Cite	C.Cite	A.	A.
		Cora	Seer	Seer	Photo	Comp
	Graph Conv. Neural Network
None	7.3	8.4	22.9	3.3	19.3	37.6
$\Gamma(1,1)$	7.2	8.3	21.5	3.4	19.5	37.1
$\Gamma(\frac{1}{3},3)$	16.1	16.0	31.9	8.0	435.9	839.9

Table 12. Graph neural network running times (in seconds) with erroneous/noisy cardinality estimates. Here,

\Gamma(\alpha,\theta)

means each estimate is multiplied by a random number generated using a Gamma

(\alpha,\theta)

distribution.

High-Performance Computing

High-performance computing (HPC) uses parallel systems and optimized software to solve computationally demanding scientific and engineering problems.

See all 143 papers

It's All Just Vectorization: einx, a Universal Notation for Tensor Operations
Jul 30, 2026Florian Fervers, Sebastian Bullinger, Christoph Bodensteiner +1
Fraunhofer IOSB
Fast LapSum: Exact Differentiable Top- $k$ at Million Scale
Aug 7, 2026Jakub Antczak, Joanna Wojciechowicz, Kamil Książek +3Differentiable Programming Differentiable Optimization
Wrocław University of Science and Technology Wrocław, Poland · Centre for Credible Artificial Intelligence Warsaw University of Technology Warsaw, Poland · Jagiellonian University Kraków, Poland
Graphical einops: bridging tensor networks and computation graphs
May 29, 2026Vincent Wang-Maścianica, Nikhil KhatriTensor Networks
†Laboratory for Human-Centered AI, Department of Philosophy, University of Oxford. · ‡Machine Learning Research Group, Department of Engineering Science, University of Oxford

Jul 30, 2026J/K move · Enter open · S save

It's All Just Vectorization: einx, a Universal Notation for Tensor Operations

Florian Fervers, Sebastian Bullinger, Christoph Bodensteiner, Michael Arens

Fraunhofer IOSB

Open paper AskPDF arXiv

Tensor operations represent a cornerstone of modern scientific computing. However, the Numpy-like notation adopted by predominant tensor frameworks is often difficult to read and write and prone to so-called shape errors, i.a., due to following inconsistent rules across a large, complex collection of operations. Alternatives like einsum and einops have gained popularity, but are inherently restricted to few operations and lack the generality required for a universal model of tensor programming. To derive a better paradigm, we revisit vectorization as a function for transforming tensor operations, and use it to both lift lower-order operations to higher-order operations, and conceptually decompose higher-order operations to lower-order operations and their vectorization. Building on the universal nature of vectorization, we introduce einx, a universal notation for tensor operations. It uses declarative, pointful expressions that are defined by analogy with loop notation and represent the vectorization of tensor operations. The notation reduces the large APIs of existing frameworks to a small set of elementary operations, applies consistent rules across all operations, and enables a clean, readable and writable representation in code. We provide an implementation of einx that is embedded in Python and integrates seamlessly with existing tensor frameworks: https://github.com/fferflo/einx

Abstract

High-Performance Computing

Explore similar work

It's All Just Vectorization: einx, a Universal Notation for Tensor Operations

Fast LapSum: Exact Differentiable Top-kkk at Million Scale

Graphical einops: bridging tensor networks and computation graphs

Fast LapSum: Exact Differentiable Top- $k$ at Million Scale