Purnamrita Sarkar

• Home
• Research
• Contact

Research

My focus has primarily been on efficient models and algorithms for very large graphs. Specific projects include:

     - Efficiently computing hitting and commute times between nodes in very large graphs.
     - Dynamic visualization of large social networks.

Relevant Publications

 Theoretical Justification of Popular Link Prediction Heuristics, (COLT '10) [Slightly revised from the COLT camera-ready version with proofs included]

     - Link prediction is an interesting and important practical problem in social networks. There are many different graph-based heuristics for doing link prediction, namely number of common neighbors between two nodes, shortest path etc. By using a generative model for link formation, and geometric intuitions, we justify some popular link prediction heuristics. Here is the presentation.

     &bull Received the Mark Fulk Best Student Paper Award


 Fast Nearest-neighbor Search in Disk-resident Graphs (KDD '10)

     - We examine the problem of computing random walk based measures on large disk-resident graphs. We also examine the relationship between different proximity measures in order to analyze the effect of high degree nodes on random walks. The technical report can be found  here.


 Fast Dynamic Reranking in Large Graphs (WWW '09)

     - In this paper we consider the problem of re-ranking search results by incorporating user feedback. We propose to use a graph theoretic measure for discriminating irrelevant results from relevant results using a few labeled examples provided by the user. We present efficient sampling and neighborhood expansion algorithms to compute the top k nodes under this measure. Here is the presentation.


 Fast Incremental Proximity Search in Large Graphs (ICML '08) [Slightly revised from the ICML camera-ready version]

     - In this paper we combine random sampling with deterministic neighborhood expansion schemes to compute approximate  nearest neighbors of a query under hitting and commute times. Resulting algorithms can process queries on the fly without any preprocessing. This is of crucial importance for graphs which change quickly over time. Here is the presentation.


 A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs (UAI '07)

    - We present GRANCH, an algorithm to compute all interesting pairs of approximate nearest neighbors  in truncated commute times in a graph, without computing it between all pairs. Our algorithm provably prunes away uninteresting  pairs of nodes in the graph, and as a result quickly finds the "potential nearest neighbors".


 A Latent Space Approach to Dynamic Embedding of Co-occurrence Data (AISTATS '07)

    - We propose a graphical model to compute dynamic embeddings of co-occurrence data. We show how to make inference tractable by using Kalman Filters, which also provides distributional information of the embedding inferred.


 Dynamic Social Network Analysis using Latent Space Models (SIGKDD Explorations: Special Edition on Link Mining '05)
        - An initial version appeared in NIPS 2005.

    - We present a dynamic model for social networks changing over time. We combine a new dynamic multidimentional scaling algorithm with a tractable local optimization technique for inference. Both of these algorithms are highly efficient (sub-quadratic in size of the social network).