Solution-Space Exploration for Data-Mining Applications

Speaker: Evimaria Terzi, Boston University

In many data-mining applications, the input consists of a collection of entities (e.g., reviews about a product, experts that declare certain skills, network nodes or edges) and the goal is to identify a subset of important entities (e.g., useful reviews, competent experts, influential nodes respectively). Existing work achieves this goal by formalizing and solving an appropriate ``selection" problem.

The solution to such selection problems is a group of entities that  optimizes an objective function. While these formulations are very interesting, they give no information about other groups of entities that are almost as good as the one reported, implying that entities not in that group are unimportant.

In this talk, we will discuss how to address this drawback by proposing a framework where the importance of an entity is evaluated by exploring the solution space of the underlying selection problem; i.e., going beyond one single solution.

From the technical point of view, we will describe two specific instances of this framework where the underlying selection problem is the set cover and the spanning tree of a graph. We will further demonstrate the practical utility of these formulations in a wide set of data-mining applications.

We will conclude the talk by discussing some cross-cutting data-mining research themes that stem from specific, yet diverse, application domains.

Bio: Evimaria Terzi is an Associate Professor at the Computer Science Department at Boston University. Before joining BU in 2009, she was a research scientist at IBM Almaden Research Center. Evimaria has received her Ph.D. from University of Helsinki, Finland and her MSc from Purdue University. Evimaria is a recipient of the Microsoft Faculty Fellowship (2010) and the NSF CAREER award (2012). Her research interests span a wide range of data-mining topics including algorithmic problems arising in online social networks, social media and recommender systems.

For more information, please contact Prof. Claudio Silva.