Name:
Deepayan Chakrabarti

Contact info: Facebook
1601 Willow Rd, Menlo Park, CA 94025
Email:
deepay <at> cs <dot> cmu <dot> edu
deepay <at> fb <dot> com

Publications
Patents
Software
Resume
Photos



Thesis
Tools for Large Graph Mining [pdf, 5MB],
and a 17-page summary [pdf, 1.7MB]
Publications
  In reverse chronological order:
  1. Joint Inference of Multiple Label Types in Large Networks,
    by D. Chakrabarti, S. Funiak, J. Chang, and S. A. Macskassy, in ICML 2014.
    pdf and arXiv version, and ppt
  2. Speeding up Large-Scale Learning with a Social Prior,
    by D. Chakrabarti, and R. Herbrich, in KDD 2013.
    pdf
  3. Nonparametric Link Prediction in Dynamic Networks,
    by P. Sarkar, D. Chakrabarti, and M. Jordan, in ICML 2012.
    pdf
  4. Traffic Shaping to Optimize Ad Delivery,
    by D. Chakrabarti, and E. Vee, in EC 2012;
    invited to ACM Transactions on Economics and Computation:
    pdf and ppt
  5. Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks,
    by B. Aditya Prakash, D. Chakrabarti, M. Faloutsos, N. Valler, and C. Faloutsos, in ICDM 2011;
    invited to KAIS Journal Special Issue (ICDM Best Papers):
    pdf
  6. Preserving Pairwise Relationships in Subgraphs,
    by A. Vattani, M. Gurevich, and D. Chakrabarti, in ICML 2011:
    pdf
  7. Event Summarization using Tweets,
    by D. Chakrabarti, and K. Punera, in ICWSM 2011:
    pdf
  8. Theoretical Justification of Popular Link Prediction Heuristics,
    by P. Sarkar, D. Chakrabarti, and A. W. Moore, invited to IJCAI 2011 (best paper track):
    pdf, and ppt
    The original version of this paper was published in COLT 2010 (best student paper award).
  9. Non-parametric Link Prediction,
    by P. Sarkar, D. Chakrabarti, and M. Jordan:
    pdf on arXiv
  10. Theoretical Justification of Popular Link Prediction Heuristics,
    by P. Sarkar, D. Chakrabarti, and A. W. Moore, in COLT 2010 (Best Student Paper Award):
    pdf and ppt
    A more accessible version was published in IJCAI 2011 (best paper track).
  11. The Paths More Taken: Matching DOM Trees to Search Logs for Accurate Webpage Clustering,
    by D. Chakrabarti, and R. Mehta, in WWW 2010:
    pdf and ppt
  12. Kronecker Graphs: An Approach to Modeling Networks,
    by J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, in JMLR 2010, volume 11 (Feb), pages 985-1042:
    pdf
  13. Mining Broad Latent Query Aspects from Search Sessions,
    by X. Wang, D. Chakrabarti, and K. Punera, in KDD 2009:
    pdf
  14. Quicklink Selection for Navigational Query Results,
    by D. Chakrabarti, R. Kumar, K. Punera, in WWW 2009:
    pdf and ppt
  15. ShatterPlots: Fast Tools for Mining Large Graphs,
    by A. P. Appel, D. Chakrabarti, C. Faloutsos, R. Kumar, J. Leskovec, and A. Tomkins, in SDM, 2009:
    pdf
  16. Mortal Multi-Armed Bandits,
    by D. Chakrabarti, R. Kumar, F. Radlinski, and E. Upfal, in NIPS 2008:
    pdf and 1-page poster
  17. Generating Succinct Titles for Web URLs,
    by D. Chakrabarti, R. Kumar, and K. Punera, in KDD 2008:
    pdf and ppt
  18. A Graph-Theoretic Approach to Webpage Segmentation,
    by D. Chakrabarti, R. Kumar, and K. Punera, in WWW 2008:
    pdf and ppt
  19. Contextual Advertising by Combining Relevance with Click Feedback,
    by D. Chakrabarti, D. Agarwal, and V. Josifovski, in WWW 2008:
    pdf and ppt (1hr, 30 min)
  20. Epidemic Thresholds in Real Networks,
    by D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos, in ACM TISSEC, 10(4), 2008:
    pdf
  21. Estimating Rates of Rare Events at Multiple Resolutions,
    by D. Agarwal, A. Broder, D. Chakrabarti, D. Diklic, V. Josifovski, and M. Sayyadian, in KDD 2007:
    pdf and ppt
  22. Multi-armed Bandit Problems with Dependent Arms,
    by S. Pandey, D. Chakrabarti, and D. Agarwal, in ICML 2007:
    pdf and ppt
  23. Page-level Template Detection via Isotonic Smoothing,
    by D. Chakrabarti, R. Kumar, and K. Punera, in WWW 2007 (pages 61-70), Banff, Canada:
    pdf and ppt
  24. Bandits for Taxonomies: A Model-based Approach,
    by S. Pandey, D. Agarwal, D. Chakrabarti, and V. Josifovski, in SDM 2007, Minneapolis, Minnesota:
    pdf and ppt
  25. Information Survival Threshold in Sensor and P2P Networks,
    by J. Leskovec, D. Chakrabarti, C. Faloutsos, S. Madden, C. Guestrin, and M. Faloutsos, in IEEE INFOCOM 2007, Anchorage, Alaska:
    pdf
  26. Visualization of Large Networks with Min-cut Plots, A-plots and R-MAT,
    by D. Chakrabarti, C. Faloutsos and Y. Zhan, in the International Journal of Human-Computer Studies, 65(5), May 2007:
    pdf
  27. Graph Mining: Laws, Generators and Algorithms,
    by D. Chakrabarti and C. Faloutsos, in ACM Computing Surveys, 38(1), 2006:
    pdf
  28. Evolutionary Clustering,
    by D. Chakrabarti, Ravi Kumar and A. Tomkins, in KDD 2006, Philadelphia, Pennsylvania:
    pdf
  29. Neighborhood Formation and Anomaly Detection in Bipartite Graphs,
    by J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos, in ICDM 2005, Houston, Texas:
    pdf
    A related paper is the following one.
  30. Relevance Search and Anomaly Detection in Bipartite Graphs,
    by J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos, in SIGKDD Explorations 7(2), 2005.
  31. Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication,
    by J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, in PKDD 2005, Porto, Portugal:
    pdf
  32. AutoPart: Parameter-Free Graph Partitioning and Outlier Detection,
    by D. Chakrabarti, in PKDD 2004 (pages 112-124), Pisa, Italy:
    ps.gz and ppt
  33. Fully Automatic Cross-Associations,
    by D. Chakrabarti, S. Papadimitriou, D. Modha and C. Faloutsos, in KDD 2004 (pages 79-88), Washington, USA:
    pdf and ppt
  34. R-MAT: A Recursive Model for Graph Mining,
    by D. Chakrabarti, Y. Zhan and C. Faloutsos, in SIAM Data Mining 2004, Orlando, Florida, USA:
    pdf
    This is the basis for the new Graph500 supercomputer benchmark.
  35. NetMine: New Mining Tools for Large Graphs,
    by D. Chakrabarti, Y. Zhan, D. Blandford, C. Faloutsos and G. Blelloch, in the SDM 2004 Workshop on Link Analysis, Counter-terrorism and Privacy:
    pdf, ps.gz and ppt
  36. A Real-Time Expectation Maximization Algorithm for Acquiring Multi-Planar Maps of Indoor Environments with Mobile Robots,
    by S. Thrun, C. Martin, Y. Liu, D. Hahnel, R. Emery-Montemerlo, D. Chakrabarti, and W. Burgard, in IEEE Transactions on Robotics and Automation, 20 (3), pp. 433-442, 2004:
    pdf
  37. Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint,
    by Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos, in SRDS 2003 (pages 25-34), Florence, Italy:
    pdf, ps.gz and ppt
  38. F4: Large Scale Automated Forecasting using Fractals,
    by D. Chakrabarti and C. Faloutsos, in CIKM 2002 (pages 2-9), McLean, Virginia, USA:
    pdf, ps.gz and ppt
  39. Using EM to Learn 3D Models of Indoor Environments with Mobile Robots,
    by Y. Liu, R. Emery, D. Chakrabarti, W. Burgard and S. Thrun, in ICML 2001 (pages 329-336), Williamstown, MA, USA:
    pdf and ps.gz
  40. A Method for Acquiring Multi-Planar Volumetric Models with Mobile Robots based on the EM Algorithm,
    by S. Thrun, W. Burgard, D. Chakrabarti, R. Emery, and Y. Liu, in ISRR 2001:
    pdf
Invited Talks and Tutorials
  1. Nonparametric Link Prediction in Dynamic Graphs,
    in the Purdue Statistics Symposium, 2012:
    ppt
  2. Theoretical and Statistical Formulations of Link Prediction,
    in the Graph Exploitation Symposium at MIT Lincoln Lab, 2012.
  3. A Theoretical Justification of Link Prediction Heuristics,
    in MLG 2012:
    ppt
  4. Statistical Challenges in Computational Advertising,
    (with D. Agarwal), half-day tutorial in KDD 2009:
    ppt
  5. Algorithmic Challenges in Computational Advertising,
    (with D. Agarwal), half-day tutorial in CIKM 2008.
  6. Clustering Applications at Yahoo!,
    in NIPS 2009 Workshop on Clustering:
    ppt
Books and Book Chapters
  1. Graph Mining: Laws, Tools, and Case Studies,
    by D. Chakrabarti, and C. Faloutsos, published by Morgan Claypool in 2012.
  2. Graph Mining,
    by D. Chakrabarti, in Encyclopedia of Machine Learning, 2010, Part 8:
    link
  3. Graph Mining: Laws and Generators,
    by D. Chakrabarti, C. Faloutsos, and M. McGlohon, in Managing and Mining Graph Data, 2010:
    link
  4. Graph Patterns and the R-MAT Generator,
    by D. Chakrabarti, and C. Faloutsos, in Mining Graph Data, edited by L. Holder and D. Cook, published by Wiley in 2006:
    book on Amazon
Technical Reports
  1. ShatterPlots: Fast Tools for Mining Large Graphs,
    by A. P. Apple, D. Chakrabarti, C. Faloutsos, R. Kumar, J. Leskovec, and A. Tomkins, in 2008: CMU-ML-08-116:
    pdf
  2. Fully Automatic Cross-Associations,
    by D. Chakrabarti, S. Papadimitriou, D. S. Modha and C. Faloutsos, in 2004: CMU-CALD-04-107:
    pdf.gz
  3. Large-scale Automated Forecasting using Fractals,
    by D. Chakrabarti, in 2002: CMU-CALD-02-101:
    pdf
Patents
  1. System and method for detecting a web page template , Patent number 7987417,
    by D. Chakrabarti, K. Punera, and S. Ravikumar.
  2. Method for segmenting webpages by parsing webpages into document object modules (DOMs) and creating weighted graphs , Patent number 7974934,
    by S. Ravikumar, D. Chakrabarti, and K. Punera.
  3. System and method for determining impression volumes of content items in a taxonomy hierarchy , Patent number 7921073,
    by D. Agarwal, D. Diklic, D. Chakrabarti, A. Broder, and V. Josifovski.
  4. System and method for smoothing hierarchical data using isotonic regression , Patent number 7870474,
    by D. Chakrabarti, K. Punera, and S. Ravikumar.
  5. System and method using hierarchical clustering for evolutionary clustering of sequential data sets , Patent number 7734629,
    by D. Chakrabarti, S. Ravikumar, and A. Tomkins.
  6. Generating succinct titles for web URLs , Patent number 8346754,
    by S. Ravikumar, D. Chakrabarti, and K. Punera.
  7. Automatic visual segmentation of webpages , Patent number 8255793,
    by D. Chakrabarti, M. Mital, S. Hajela, and E. Velipasaoglu.
  8. Customization of information retrieval through user-supplied code, Patent number 6611834,
    by G. Aggarwal, D. Chakrabarti, P. K. Dubey, N. P. Garg, S. Ghosal, A. K. Gupta, A. Kulshreshtha, Ashutosh and S. K. V. Murthy.
  9. Named as a co-inventor in 12 other pending patents and 2 defensive publications.
Honors
  1. Our COLT 2010 work received the best student paper award.
  2. Our R-MAT work is the basis for the new Graph500 supercomputer benchmark.
  3. Siebel Scholar, 2002
Professional Service
  1. Senior PC on the KDD 2010 and 2014 research tracks.
  2. Posters chair for WWW 2010.
  3. PC member and reviewer on several conferences and journals, including KDD, WWW, ICML, SIGMOD, VLDB, and ICDE.
  4. Served on three NSF Panels.
  5. Local arrangements co-chair for KDD 2007.
  6. Student member of CMU departmental Ph.D. admissions committee for 2001-2003.
Software
  1. The CrossAssociations package for automatically grouping nodes in a large graph
  2. The NetMine package for extracting patterns from large graphs
  3. The F4 non-linear time series forecasting package