Colloquium Details
Faculty Search Colloquium: Mining and Searching Massive Graph Databases
| Author: | Xifeng Yan University of Illinois at Urbana-Champaign |
|---|---|
| Date: | March 07, 2006 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Dejing Dou |
Abstract
Graphs are ubiquitous with critical applications in domains ranging from software engineering to computational biology. However, it is challenging to analyze any reasonably large collection of graphs due to its high computational complexity. Development of scalable methods for the analysis of massive graph databases thus becomes one major thrust in data mining and database research.
In the core of many graph-related applications, there are two fundamental problems: how to mine graph patterns and how to process graph queries. My initial study grasped a tight connection between these two seemingly parallel areas. In this talk, I will first present a novel graph canonical labeling system that is able to speedup the discovery of frequent subgraph patterns. Next, discriminative pattern analysis is introduced for constructing compact yet high-quality graph indices, which are then applied to exact and approximate graph search in large graph databases. Such index mechanism is shown to be very effective in processing graph queries. The finding of graph pattern-based indexing is profound and yet to be fully explored since the same concept can also be applied to graph classification and clustering. In the end of my talk, I am going to examine broader applications of graph patterns, such as biological network analysis for functional annotation and program flow classification for software bug isolation.
Biography
Xifeng Yan is a Ph.D. candidate in the Department of Computer Science at the University of Illinois at Urbana-Champaign, under the supervision of Professor Jiawei Han. Xifeng got his M.S. from the University of New York at Stony Brook in 2001. His current research interests are data mining, bioinformatics, and database systems. Xifeng has published more than 20 papers in reputed journals and conferences, such as ACM-TODS, SIGMOD, SIGKDD, VLDB, ISMB, ICDE, and FSE. Two of his papers on graph indexing and similarity search were invited to ACM Transactions on Database Systems. His work on pattern summarization received the best student paper runner-up award in SIGKDD 2005. Xifeng has two pending U.S. patents, filed at the IBM T. J. Watson Research Center. He recently received the Department's nominee for the Ross J. Martin Award, an award given to one graduate student in the College of Engineering at the University of Illinois at Urbana-Champaign.