2023/06/30 by Sinan G. Aksoy, Ilya Amburg, Aksoy, Sinan G. +3 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #05C50 #05C65 #05C85 #15A69 #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Visualization and Analytics #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2306.17825
openalex publication_date 2023/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
While multilinear algebra appears natural for studying the multiway interactions modeled by hypergraphs, tensor methods for general hypergraphs have been stymied by theoretical and practical barriers. A recently proposed adjacency tensor is applicable to nonuniform hypergraphs, but is prohibitively costly to form and analyze in practice. We develop tensor times same vector (TTSV) algorithms for this tensor which improve complexity from O(nr) to a low-degree polynomial in r, where n is the number of vertices and r is the maximum hyperedge size. Our algorithms are implicit, avoiding formation of the order r adjacency tensor. We demonstrate the flexibility and utility of our approach in practice by developing tensor-based hypergraph centrality and clustering algorithms. We also show these tensor measures offer complementary information to analogous graph-reduction approaches on data, and are also able to detect higher-order structure that many existing matrix-based approaches provably cannot.