ECE Faculty Candidate Seminar
Dr. Aritra Konar
University of Virginia
Wednesday, January 15, 2020
11:15 a.m. – 12:15 p.m.
“Fast and Efficient Approximation Algorithms for Large-Scale Graph-Mining”
Networks are a powerful formalism for modeling complex interactions amongst entities in social, biological and technological systems. The advent of online social networks and the widespread availability of large-scale biological data necessitates the development of computationally efficient algorithmic tools for analyzing and extracting interpretable patterns from massive networks. A key challenge in this regard stems from the fact that many fundamental graph-mining primitives take the form of NP--hard combinatorial optimization problems, which do not even admit meaningful approximation guarantees in the worst-case. In this talk, I will focus on two such prominent problems: (a) network alignment, and (b) clique mining. For the former problem, I will demonstrate how insights from discrete optimization can be leveraged to design a new combinatorial local-search algorithm that judiciously exploits problem structure to arrive at high-quality, approximate solutions. On the other hand, for the latter problem, I will show how structural properties of real-world networks can be exploited to develop simple techniques based on triangle-counting for discovering large cliques and quasi-cliques in graphs. The effectiveness of the algorithms will be showcased on several real-world datasets.
Aritra Konar received the B.Tech. degree in Electronics and Communications Engineering from West Bengal University of Technology, West Bengal, India, and the M.S. and Ph.D. degrees in Electrical Engineering from the University of Minnesota, Minneapolis, USA, in 2011, 2014, and 2017 respectively. He is currently a postdoctoral researcher in the ECE Department at the University of Virginia, VA, USA. His research interests include graph mining, machine learning, optimization theory, and signal processing. He was the recipient of the Doctoral Dissertation Fellowship from the University of Minnesota in 2016.
Faculty Host: Dr. Selin Aviyente (firstname.lastname@example.org)
Michigan State University is committed to providing equal opportunity for participation in all programs, services and activities. Accommodations for persons with disabilities may be requested by contacting Shaunak Bopardikar (email@example.com)