[Research] Auton Lab meeting this Tuesday

[Artur Dubrawski]

Speaker: Purna Sarkar

Topic: Graphs, active pairs and approximate nearest neighbors

Abstract:

Random walks on graphs is an extremely well-explored area. Recently many
data-mining applications have been developed using a random walks
perspective. The graphs are obtained from a relational database (e.g the
IMDB database, social networks or 
recommender networks) which links entities who have been observed to
co-occur in some event. Random walks on such a graph gives rise to a very
intuitive distance measure on entities in the graph, namely the expected
hitting time, which is the expected number of hops a random walk takes to
hit a destination node starting from a source node. Though this measure
empirically proves to be highly predictive of the future behavior of the
entities, existing techniques in essence require computing the
pseudo-inverse of a sparse graph laplacian, and do
not scale very well for massive data sets.In this talk we'll describe these
concepts and why they are important in graph-based data mining. We are
currently developing strategies that are guaranteed to retrieve approximate
nearest neighbors under these kinds of distance measures 
within an epsilon distance of the true ones without looking at all pairs of
nodes. 

Place & time: The Usual (NSH 1507, 11:30am)

Date: Tuesday, October 24th.