Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions cannot be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge intersections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

Hypergraphs are a popular paradigm to represent 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) operation. 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.

Hypergraphs offer flexible and robust data representations for many applications, but methods that work directly on hypergraphs are not readily available and tend to be prohibitively expensive. Much of the current analysis of hypergraphs relies on first performing a graph expansion – either based on the nodes (clique expansion), or on the hyperedges (line graph) − and then running standard graph analytics on the resulting representative graph. However, this approach suffers from massive space complexity and high computational cost with increasing hypergraph size. Here, we present efficient, parallel algorithms to accelerate and reduce the memory footprint of higher-order graph expansions of hypergraphs. Our results focus on the hyperedge-based s-line graph expansion, but the methods we develop work for higher-order clique expansions as well. To the best of our knowledge, ours is the first framework to enable hypergraph spectral analysis of a large dataset on a single shared-memory machine. Our methods enable the analysis of datasets from many domains that previous graph-expansion-based models are unable to provide. The proposed s-line graph computation algorithms are orders of magnitude faster than state-of-the-art sparse general matrix-matrix multiplication methods, and obtain approximately 2–31× speedup over a prior state-of-the-art heuristic-based algorithm for$s$-line graph computation.

In forming teams or groups, one often aims to balance expertise in a main focus area while also encouraging diversity of skills in each team. In this paper we model the problem of finding diverse groups of individuals who have expertise in a given task as a clustering problem on hypergraphs with heterogeneous edge types. Here, the hyperedge types encode past experience types of groups, and the output of the clustering is groups of individuals (nodes). Unlike complementary problems that seek to find fair or balanced clusters (e.g., in terms of some protected node attributes), our model encourages diversity of past experience within these groups by striking a balance between experience and diversity with respect to node participation in edge types. We show that naive objectives lead to no diversity-experience tradeoff, which motivates our refined model based on regularizing an edge-based hypergraph clustering objective. While optimizing our objective is NP-hard, we design a 2-approximation algorithm that works for a more general class of problems where each node is allowed to have a preference for a particular cluster, and illustrate a technique for computing regularization strength bounds that reveal meaningful diversity/experience tradeoff regimes. We illustrate the utility of our framework on several real-life datasets – most notably to online review platform data – to curate sets of reviews for a given type of product which exhibit a tradeoff between reviewer experience, or familiarity with a product type, and experience, or the reviewer's tendency to also review related product types. In the setting allowing for node preferences, we show that our framework discovers sets of reviews sensitive to user preference.

Modern graph or network datasets often contain rich structure that goes beyond simple pairwise connections between nodes. This calls for complex representations that can capture, for instance, edges of different types as well as so-called “higher-order interactions” that involve more than two nodes at a time. However, we have fewer rigorous methods that can provide insight from such representations. Here, we develop a computational framework for the problem of clustering hypergraphs with categorical edge labels — or different interaction types — where clusters corresponds to groups of nodes that frequently participate in the same type of interaction.