Risk averse graph mining

Tuesday, July 16, 2019

2.30 p.m.

ISI seminar room 1st floor

Prof. Charalampos Tsourakakis Boston University, Massachusetts, USA - Harvard University, Massachusetts, USA - ISI Foundation

Uncertain graphs model various important real-world settings, ranging from influence maximization, and entity resolution to protein interactions, and kidney exchanges. Mining such graphs poses significant challenges. Simple graph queries on deterministic graphs may become NP-hard, or even #P-complete on uncertain graphs, and furthermore even if we could find the optimal solutions in expectation, these may involve significant risk. In this talk we will present recent contributions to finding risk-averse (i) maximum matchings in uncertain graphs, (ii) dense subgraphs. Our algorithmic primitives in contrast to existing risk averse algorithmic approaches are time-, and space- efficient, and come with solid approximation guarantees. We evaluate our methods on a variety of real-world uncertain graphs where we observe interesting trade-offs between risk and reward.

Charalampos Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Dr. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He has received the 10-year highest impact paper award from IEEE, has won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.

Joint work with Tianyi Chen (Boston University), Johnson Lam (Boston University), Shreyas Sekar (Harvard), Naonori Kakimura (Keio University) and Jakub Pachocki (OpenAI).