Computer Science Events
[PAST EVENT] Hypergraph Data Analysis: Algorithms and Applications
Hypergraph Data Analysis: Algorithms and Applications
Abstract: Networks provide an excellent way to model systems of interconnected data with pairwise relationships. However, there has been a growing realization that many complex datasets and systems in the real world are better characterized by multiway relationships. For example, social interactions often occur in groups, consumers purchase multiple products during a shopping trip, and chemical interactions typically involve more than two molecules. This realization has led to a surge of interest in algorithms for mining information from network data with generalized mathematical structures that encode higher-order relationships. One of the most flexible models for higher-order relationships is a hypergraph, which can encode multiway relationships of arbitrary size.
This talk will present our recent innovations in models and algorithms for common data science applications -- including community detection, localized clustering, and semi-supervised learning -- involving hypergraphs: specifically, hypergraph cut problems. We introduce a very general notion of a hypergraph cut function motivated by data science applications, one that hasn’t yet been considered despite decades of research into hypergraphs, and then consider algorithms and hardness results for minimizing special sub-classes of this function in practice. We apply these results to explore and tease out new insights from various real-world datasets, ranging from large retail product datasets to social group interaction networks. Scalability in terms of hyperedge size and number of hyperedges is often an issue with hypergraph generalizations, and we show localization techniques enable us to scale to datasets with millions of hyperedges of large size.
Short Bio: Nate Veldt is a postdoctoral associate in the Center for Applied Mathematics at Cornell University, working with Professors Jon Kleinberg and Austin Benson. Previously he completed a PhD at Purdue University, where he was advised by Professor David Gleich. Upon graduation from Purdue, he received the 2019 Dimitris N. Chorafas Foundation award for his dissertation on Optimization Frameworks for Graph Clustering.
Nate's research is broadly focused on algorithms and optimization techniques for data science and network analysis. More specifically his work brings together tools from scientific computing, machine learning, and theoretical computer science to develop algorithms for analyzing large networks and datasets that are both efficient and come with strong theoretical guarantees.
Contact
Prof. Andreas Stathopoulos