Back to search

Georgia Institute of Technology

Scalable Algorithms for Hypergraph Analytics using Symmetric Tensor Decompositions

Abstract

dc:description.abstract

Tensors are higher-dimension generalizations of matrices and are used to represent multi-dimensional data. Tensor-based methods are receiving renewed attention in recent years due to their prevalence in diverse real-world applications. Symmetric tensors are an important class of tensors, arising in diverse fields such as signal processing, machine learning, and hypergraph analytics. Hypergraphs, generalizations of graphs which allow edges to span multiple vertices, have become ubiquitous in understanding real-world networks and multi-entity interactions. Affinity relations in a hypergraph can be represented as a high-order adjacency tensor which is sparse and symmetric. While mathematical research on symmetric tensors is longstanding, emerging massive data in these applications has sparked the demand for scalable, efficient algorithms that utilize advances in numerical linear algebra, numerical optimization, as well as high-performance computing. State-of-the-art tensor libraries incorporate high-performance tensor methods for general sparse tensors; however, they lack specialized algorithms for sparse tensors that are symmetric. This dissertation focuses on scaling hypergraph analytics to real-world datasets by taking advantage of the sparsity and symmetry of the associated adjacency tensors through the development of compact storage formats and efficient serial and parallel algorithms for tensor operations. We present a novel computation-aware compressed storage format - CSS - for sparse symmetric tensors, along with efficient parallel algorithms for symmetric tensor operations that are compute- and memory-intensive due to the high tensor order and the associated factorial explosion in the number of non-zeros. In order to scale to large multi-entity complex networks, we consider the problem of distributed-memory hypergraph analytics. To that end, we present algorithms for parallel distributed-memory line graph construction of hypergraphs and demonstrate their application to large-scale symmetric adjacency tensor decomposition for hypergraph clustering. For hypergraphs with varying edge cardinalities, the CSS format has been extended to the CCSS format, using which we present a new shared-memory parallel algorithm for a key symmetric tensor kernel in the complutation of hypergraph tensor eigenvector centrality. Finally, we present Coupled Symmetric Tensor Completion (CoSTCo), a Riemannian optimization framework for the task of link prediction in non-uniform hypergraphs and analyze its performance with both synthetic and real-world datasets against state-of-the-art general tensor completion algorithms.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computational Science and Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shivakumar, Shruti
Advisor dc:contributor.advisor
  • Aluru, Srinivas
Committee members dc:contributor.committeemember
  • Kannan, Ramakrishnan
  • Sarkar, Vivek
  • Vuduc, Richard W.
  • Kang, Sung Ha

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/73104

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shivakumar, Shruti. Scalable Algorithms for Hypergraph Analytics using Symmetric Tensor Decompositions. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/73104