•   When: Tuesday, January 05, 2021 from 02:00 PM to 03:00 PM
•   Speakers: Nate Veldt, Postdoctoral Associate, Center for Applied Mathematics, Cornell University
•   Location: ZOOM
•   Export to iCal

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 recent innovations in models and algorithms for common data science applications -- including community detection, partitioning, sparsification, and semi-supervised learning -- involving hypergraphs: specifically, hypergraph cut problems. I will first 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. I will demonstrate how these results can be used to explore and tease out new insights from various real-world datasets, ranging from large retail product datasets to food webs. Scalability in terms of hyperedge size and number of hyperedges is often an issue with hypergraph generalizations, and I will show how localization techniques make it possible to scale to data with millions of hyperedges of large size.

Bio:

 Nate Veldt is a postdoctoral associate in the Center for Applied Mathematics and Cornell University, working with Professors Jon Kleinberg and Austin Benson. Prior to this he completed his 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.