CSE Seminar: Hanghang Tong

Event Details
  • Date/Time:
    • Tuesday March 16, 2010 - Wednesday March 17, 2010
      2:00 pm - 2:59 pm
  • Location: Klaus 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

For more information, contact Dr. Guy Lebanon.


Summary Sentence: Fast Algorithms for Querying and Mining Large Graphs

Full Summary: No summary paragraph submitted.

Hanghang Tong

Machine Learning Department at Carnegie Mellon

For more information please contact Dr. Guy Lebanon


Fast Algorithms for Querying and Mining Large Graphs


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.


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:


Additional Information

In Campus Calendar

Computational Science and Engineering, College of Computing, School of Computational Science and Engineering

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Mike Terrazas
  • Workflow Status: Published
  • Created On: Mar 11, 2010 - 11:39am
  • Last Updated: Oct 7, 2016 - 9:51pm