Colloquium: Tina Eliassi-Rad

You are cordially invited to attend this School of Informatics colloquium:

Friday, February 20, 2009
3:00 p.m.
Informatics East (I2), Rom 130

Tina Eliassi-Rad, Lawrence Livermore National Laboratory, will present, "Classification in Sparsely Labeled Networks."

Abstract:
In this talk, I will address the problem of classification in partially labeled networks (a.k.a. within-network classification), where observed class labels are sparse. Recent techniques in statistical relational learning have been shown to perform well on network classification tasks by exploiting dependencies between class labels of neighboring nodes. However, relational classifiers can fail when unlabeled nodes have too few labeled neighbors to support learning (during the training phase) and/or inference (during the testing phase). This situation arises in many real-world tasks where observed labels are sparse (i.e., less than 10% of the total population). Examples include identification of suspicious blog postings, malicious web pages, and fraudulent cell phones. I will motivate a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks. Our approach works by adding "ghost edges" to a network, which enable the flow of information from labeled to unlabeled nodes. Through experiments on real-world data sets, we demonstrate that our approach performs well across a range of conditions where existing approaches, such as collective classification and semi-supervised learning, fail. On all tasks, our approach improves classification performance by up to 15% over existing approaches. Furthermore, our approach runs in time proportional to L*E, where L is the number of labeled nodes and E is the number of edges. I will conclude by placing this work in the context of my research program on role discovery in dynamic heterogeneous networks.