*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Hanghang Tong
Machine Learning Department at Carnegie Mellon
For more information please contact Dr. Guy Lebanon
Title:
Fast Algorithms for Querying and Mining Large Graphs
Abstract:
Graphs appear in a wide range of settings and have posed a wealth of fascinating problems. In this talk, I will present our recent work on (1) querying (e.g., given a social network, how to measure the closeness between two persons? how to track it over time?); and (2) mining (e.g., how to identify abnormal behaviors of computer networks? In the case of virus attacks, which nodes are the best to immunize?) large graphs.
For the task of querying, our main finding is that many complex user-specific patterns on large graphs can be answered by means of proximity measurement. In other words, proximity allows us to query large graphs on the atomic levels. Then, I will talk about how to adapt querying tasks to the time evolving graphs. For fast computation of proximity, we developed a family of fast solutions to compute the proximity in several different scenarios. By carefully leveraging some important properties shared by many real graphs (e.g., the block-wise structure, the linear correlation, the skewness of real bipartite graphs, etc), we can often achieve orders of magnitude of speedup with little or no quality loss. For the task of mining, I will talk about immunization and anomaly detection. For immunization, we proposed a near-optimal, fast and scalable algorithm. For anomaly detection, we proposed a family of example-based low-rank matrix approximation methods. The proposed algorithms are provably equal to or better than best known methods in both space and time, with the same accuracy. On real data sets, it is up to 112x faster than the best competitors, for the same accuracy.
Bio:
Hanghang Tong got his Ph.D in the Machine Learning Department at Carnegie Mellon University in 2009. He has received best paper awards from SIAM-DM 2008 and ICDM 2006. He holds an M.S. degree and a B.S. degree from Tsinghua University, P.R. China. His research interests include data mining for multimedia.
To receive future announcements, please sign up to the cse-seminar email list:
https://mailman.cc.gatech.edu/mailman/listinfo/cse-seminar
