Fast Parallel Tensor Times Same Vector for Hypergraphs

Abstract

Hypergraphs are a popular paradigm to rep- resent complex real-world networks exhibiting multi-way relationships of varying sizes. Mining centrality in hyper- graphs via symmetric adjacency tensors has only recently become computationally feasible for large and complex datasets. To enable scalable computation of these and related hypergraph analytics, here we focus on the Sparse Symmetric Tensor Times Same Vector (S3TTVC) oper- ation. We introduce the Compound Compressed Sparse Symmetric (CCSS) format, an extension of the compact CSS format for hypergraphs of varying hyperedge sizes and present a shared-memory parallel algorithm to compute S3TTVC. We experimentally show S3TTVC computation using the CCSS format achieves better performance than the naive baseline, and is subsequently more performant for hypergraph H-eigenvector centrality.