Scalable tensor methods for nonuniform hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909160151449600 |
|---|---|
| author | Aksoy, Sinan G. Amburg, Ilya Young, Stephen J. |
| author_facet | Aksoy, Sinan G. Amburg, Ilya Young, Stephen J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_17825 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Scalable tensor methods for nonuniform hypergraphs Aksoy, Sinan G. Amburg, Ilya Young, Stephen J. Numerical Analysis Machine Learning Social and Information Networks Combinatorics Physics and Society 05C65, 15A69, 05C50, 05C85 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. |
| title | Scalable tensor methods for nonuniform hypergraphs |
| topic | Numerical Analysis Machine Learning Social and Information Networks Combinatorics Physics and Society 05C65, 15A69, 05C50, 05C85 |
| url | https://arxiv.org/abs/2306.17825 |