# Scalable tensor methods for nonuniform hypergraphs

arXiv: https://arxiv.org/abs/2306.17825 · HTML: https://mlsanity.com/paper/2306.17825/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 59 references that are in the map.
- First posted on arXiv 30 Jun 2023.

## Builds on (most cited first, 13 of 13)

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Hypernetwork Science via High-Order Hypergraph Walks](https://mlsanity.com/paper/1906.11295/) (2019)
- [Hypergraph Random Walks, Laplacians, and Clustering](https://mlsanity.com/paper/2006.16377/) (2020)
- [Random walks on hypergraphs](https://mlsanity.com/paper/1911.06523/) (2019)
- [Tensor Spectral Clustering for Partitioning Higher-order Network Structures](https://mlsanity.com/paper/1502.05058/) (2015)
- [The Spacey Random Walk: a Stochastic Process for Higher-order Data](https://mlsanity.com/paper/1602.02102/) (2016)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Three hypergraph eigenvector centralities](https://mlsanity.com/paper/1807.09644/) (2018)
- [Hypergraphx: a library for higher-order network analysis](https://mlsanity.com/paper/2303.15356/) (2023)
- [Modularity and Projection of Bipartite Networks](https://mlsanity.com/paper/1908.02520/) (2019)

## Built on by (most cited first, 1 of 1)

- [HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network](https://mlsanity.com/paper/2402.09676/) (2024)

## Abstract (arXiv)

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.