Principled Approaches for Hierarchial Clustering via Optimization Models

Gökçe Kahvecioğlu, Amazon

Abstract

Given an undirected graph with positive weights on the edges we study a parametric bi-objective graph clustering problem. We remove a subset of edges to break the graph into smaller pieces, i.e., connected components, or clusters. We seek to maximize the number of clusters while minimizing the weight of the removed edges. We identify nested solutions that lie on the concave envelope of the efficient frontier, yielding a hierarchical family of clusters, in strongly polynomial time. We demonstrate the performance of our approach on a graph defined by the schedule of football teams within the National Collegiate Athletic Association, which has a known hierarchical structure, and on a set of synthetic graphs generated from a stochastic block model with embedded hierarchial structure.

Short Bio

Gokce Kahvecioglu is a Research Scientist in the Supply Chain Optimization Technologies group at Amazon. Before joining Amazon, she worked as a Senior Analyst in the Revenue Management division at United Airlines. She completed her B.Sc. (2012) and M.Sc. (2014) in Industrial Engineering at Sabanci University and earned her Ph.D. (2020) in Industrial Engineering and Management Sciences at Northwestern University. Gokce’s research spans several areas of stochastic and combinatorial optimization for data science and supply-chain management applications. She was a recipient of Fulbright Scholarship, and her PhD work was recognized by INFORMS Data Mining Society and Dow Sustainability Innovation Committee.

Venue

Friday, April 15, 2022, 5.00 pm - Zoom Meeting