Our paper “Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components” was just accepted for publication at NeurIPS (joint work with Austin Benson and Jon Kleinberg). The paper applies new sparsification techniques for solving a common class of decomposable submodular function minimization problems. This is motivated by applications to hypergraph clustering, but solves a more general problem.
Preprint available at https://arxiv.org/abs/2110.14859
Our paper Generative hypergraph clustering: from blockmodels to modularity was just published at Science Advances. Joint work with Phil Chodrow and Austin Benson.
Abstract. Hypergraphs are a natural modeling paradigm for networked systems with multiway interactions. A standard task in network analysis is the identification of closely related or densely interconnected nodes. We propose a probabilistic generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum likelihood inference in this model leads to a clustering objective that generalizes the popular modularity objective for graphs. From this, we derive an inference algorithm that generalizes the Louvain graph community detection method, and a faster, specialized variant in which edges are expected to lie fully within clusters. Using synthetic and empirical data, we demonstrate that the specialized method is highly scalable and can detect clusters where graph-based methods fail. We also use our model to find interpretable higher-order structure in school contact networks, U.S. congressional bill cosponsorship and committees, product categories in copurchasing behavior, and hotel locations from web browsing sessions.
Our paper on The Generalized Mean Densest Subgraph Problem. was accepted to KDD 2021. Join work with Austin Benson and Jon Kleinberg.
The paper covers a generalized framework for dense subgraph detection, that unifies previous objectives such as the k-core problem and the densest subgraph problem. We prove polynomial time algorithms for a certain regime of the problem, as well as faster approximation algorithms based on a generalized “peeling” method.
