From 2^N to N^2: Tree-Free Scalable Sparse Symmetric Tucker Decomposition

Abstract

Symmetric sparse tensors arise naturally from multi-relational data, such as co-purchasing patterns, co-authorship networks, and temporal interaction data, and Tucker decomposition of such data extracts low-rank latent structure. The primary computational bottleneck is the Symmetric Sparse Tensor Times Same Matrix Chain (S3TTMc), which contracts the tensor with the factor matrix along all but one mode through a Kronecker product per nonzero. State-of-the-art methods exploit redundancy across nonzeros that share common index subsequences by organizing computation on a global prefix tree, enabling memoization of intermediate Kronecker products. However, as tensor dimensions grows, nonzero indices overlap less and the housekeeping cost of maintaining the tree grows exponentially, leaving \(\mathcal {O}(2^N)\) intermediate products per nonzero, multi-gigabyte working sets, and a traversal order that limits parallel scalability. We propose SPLIT N2, a nonzero-parallel algorithm that eliminates the tree: a chain of symmetric extensions reduces the per-nonzero cost from \(\mathcal {O}(2^N)\) to \(\mathcal {O}(N^2)\) symmetric vector–tensor products, computed independently for each nonzero. On real-world and synthetic tensors, SPLIT N2 achieves up to 504 × kernel speedup and 109 × end-to-end Tucker decomposition speedup, with 4–7 orders-of-magnitude reduction in memory footprint. Since its memory footprint depends only on rank and tensor order—not on the global index structure—SPLIT N2 enables decomposition of tensors with higher orders, larger dimensions, more nonzeros, and higher ranks than any prior tree-based method.