[ML Lunch Seminar] Hanghang Tong: Proximity on Graphs

Speaker: Hanghang Tong, MLD, CMU
Title: Proximity on Graphs: Definitions, Fast Solutions and Applications
Venue: NSH 1507
Date: Monday October 29
Time: 12:00 noon


Abstract:
Graphs appear in a wide range of settings, like computer networks, the
world wide web, biological networks, social networks
(MSN/FaceBook/LinkedIn) and many more. How to find master-mind criminal
given some suspects X, Y and Z? How to find user-specific pattern (like,
e.g. a money-laundering ring)? How to track the most influential authors
over time? How to automatically associate digital images with proper
keywords? How to answer all these questions quickly on large (disk
resident) graphs? It turns out that the main tool behind these
applications (and many more) is the proximity measurement: given two
nodes A and B in a network, how close is the target node B related
to the source A?

In this talk, I will cover three aspects of the proximity on graphs: (1)
Proximity definitions. I will start with random walk with restart, the
main idea behind Google's PageRank algorithm, and talk about its
variants and generalizations. (2) Computational issue. Many proximities
measurements involve a specific linear system. I will give algorithms on
how to efficiently solve such linear system(s) in several different
settings. (3) Applications. I will show some applications of the
proximity, including link prediction, neighborhood formulation, image
caption, center-piece subgraph, pattern match etc.