UNCC College of Computing and Informatics

Graduate Seminar (2009 Fall)

Title: Graph-based Data Mining

Nikhil Ketkar, Ph.D

Postdoctoral Research Associate

Department of Computer Science

University of North Carolina at Charlotte

August 28 at 3:00pm
106 Woodward

Abstract:

The fields of machine learning and data mining are currently in the midst of what has been called a structural revolution, and the new field of graph mining has emerged. The focus of graph mining is the development of predictive and descriptive models from structured data represented as graphs. The distinguishing aspect of these models is that they incorporate both the entities as well as the relationships which are fundamental to the structural nature of the data. The motivation behind considering relationships is that they represent a rich source of information and this can lead to significant improvements in the predictive accuracy of the models. While incorporating structure can lead to potential improvement, this improvement comes at a high computational cost and a key challenge is scalability.

This talk will focus on the tasks of frequent subgraph mining, graph classification, and graph regression. Given a set of graph transactions, the task of frequent subgraph mining involves enumerating all subgraphs present in at least a given number of transactions. The graph classification problem is to induce a model from a set of graph transactions and associated class values which predicts the class value of unseen graphs. The graph regression problem can be seen as the general case of the graph classification problem where the value to be predicted is a real number. The problems of frequent subgraph mining, graph classification, and graph regression have applications in a variety of application domains where the underlying data cannot be represented as a simple table of features.

The key results presented in this talk include novel sampling approaches that allow us to mine exceedingly large graph transaction databases and pruning mechanisms that significantly improve feature extraction for graph classification and regression.

Bio:

Nikhil Ketkar completed his Ph.D. in Computer Science at Washington State University in May 2009. He is currently a postdoctoral research associate in the Department of Computer Science at the University of North Carolina at Charlotte. His research interests are in machine learning, data mining, and graph theory. The unifying theme of his work is investigating how structural information can be leveraged to develop better predictive and descriptive models and to develop algorithms and software infrastructure that facilitates the use of this methodology in various real world domains.

Back