Scalable tensor methods for nonuniform hypergraphs
This work addresses computational bottlenecks for researchers analyzing multiway interactions in hypergraphs, offering scalable methods that can detect higher-order structures missed by matrix-based approaches.
The paper tackled the problem of applying tensor methods to nonuniform hypergraphs, which were previously hindered by high computational costs, by developing implicit TTSV algorithms that reduce complexity from O(n^r) to a low-degree polynomial in r, enabling practical applications like centrality and clustering.
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(n^r)$ 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.