Seminar "Large-scale Graphs: Algorithms and Techniques"

Dr. Srikanta Bedathur, Dr. Mauro Sozio

Content

The seminar covers the recent advances in storage, processing and mining of large-scale graphs. We cover topics mainly from database and algorithms research. An almost equal mix of systems and algorithmic approaches for scalable graph handling are included in the seminar.

Organization

• To register, send mail to the tutors (note that we have a limit on the total participants, so if you are keen on the seminar, it doesn't hurt to do it quickly!)
• Kickoff meeting is tentatively scheduled for April 20th, 10:00-12:00, at Room 021, Building E1.4 (MPI-INF).
• Regular meetings will be held every Tuesday, 10:00-12:00 at the same place.

Prerequisites

• Students planning to attend the course should have some knowledge about Algorithms, Database Systems, and Information retrieval (successful participation in courses like Information Retrieval and Data Mining, Database Systems is fine).

Requirements for the certificate

• Attend all talks - not just your own. If you are ill, please let us know in advance by writing a short mail.
• There will be two lectures given by the tutors -- we expect that all participants attend it. In the schedule below, contents of these lectures are indicated in this color.
  
• Prepare a 45 minutes talk about your topic that introduces the matter to your fellow students. Talks will be followed by approximately 15 minutes of discussion.
• Make a first appointment with your tutor (who will be announced along with the topics) to go through the outline of your talk already a few weeks in advance. You are responsible for scheduling the meetings with your tutor.
• You are very welcome to point out the advantages or potential weaknesses of the paper(s) in your talk. If you are unsure about what to present, ask your tutor. Note that, even though presentations of some papers are available on the Web, we expect that you prepare your own slides (which may be, of course, inspired by the original slides). You must send your slides to and discuss them with your tutor by the Friday before your talk (4pm) at the latest, otherwise your talk will be cancelled.
• Both the slides and the presentation itself must be given in English.
• For each talk, a second student will be preselected as an opponent. His or her role is to prepare tough questions to challenge the paper presented in the talk (not the talk itself or the speaker!). Avoid focusing on the paper's presentation style, or choice of colors for graphs etc. except when they significantly effect understanding of the technical contributions of the paper.
  To make life a little easier, the preliminary version of the slides will be sent to the opponent on the Tuesday before the talk. However, as interaction is an important part of science, we expect that every participant actively participates in the discussions.
• Atmost two weeks after the talk, the presenter and the opponent together have to submit a short (usually not longer than 5 pages) summary of the talk. The focus of this report should be on pointing out strengths and weaknesses of the approach presented in the paper(s), not just on summarizing the paper(s).
• Additional bonus points can be gained for preparing a report of the papers presented by the tutors (to be submitted after paper presentations). Of course, the number of bonus points are dependent on the quality of the report, and are determined by tutors.
  
• In other words: Your final grade will be influenced by the following components: Your oral presentation, the knowledge about your topic (your answers to questions after the presentation), the questions you asked as opponent, your general participation in the seminar, and your two written reports (one in the role of presenter, one in the role of opponent) + bonus points if obtained.
  

Schedule

(Note: Some of the papers below are not yet available online. They will be made available during the course of the seminar.)

• April 27, 2010
  H.Tong and C. Faloutsos. Center-piece Subgraphs: Problem Definition and Fast Solutions. KDD 2006.  PDF
• Lecturer: Tran Anh Tuan
• Opponent: Aravind Vasudevan
• Tutor: Mauro Sozio
  
• May 4, 2010
  M. Sozio and A. Gionis. The Community Search Problem and How to Plan a Successful Cocktail Party. KDD 2010.  PDF
  C. Karande, K. Chellapilla and R. Andersen. Speeding up Algorithms on Compressed Web Graphs. WSDM 2009.  PDF
• Lecturer:  Hassan Issa
• Opponent: Martin Vasileski
  
• Tutor: Mauro Sozio
  
• May 11, 2010
  P. Boldi and S. Vigna. The Webgraph Framework I: Compression Techniques. WWW 2004. PDF
  (additional material: F. Chierichetti, R. Kumar, S. Lattanzi, A. Panconesi and P. Raghavan. Models for the Compressible Web. FOCS 2009. PDF
• Lecturer: Andreas Frische
• Opponent: Javeria Iqbal
  
• Tutor: Mauro Sozio
  
• May 18, 2010 (Class cancelled)
  L.Backstrom, C. Dwork, J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. WWW 2007. PDF
• Lecturer: Aravind Vasudevan
• Opponent: Javeria Iqbal
  
• Tutor: Srikanta Bedathur
  
• May 25, 2010
  J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. WWW 2010. PDF
• Lecturer: Erdal Kuzey
• Opponent: Tran Anh Tuan
  
• Tutor: Mauro Sozio
  
• June 1, 2010
  D. Abadi, A. Marcus, S. Madden and K. Hollenbach. SW-Store: a vertically partitioned DBMS for Semantic Web data management. VLDBJ 18(2), 2009. PDF
  T. Neumann and G. Weikum. RDF-3X: a RISC-style engine for RDF. VLDBJ 19(1), 2010. PDF
  H. He and A. Singh. Graphs-at-a-time: Query Language and Access Methods for Graph Databases. SIGMOD 2008. PDF
• Lecturer: Martin Vasileski
• Opponent: Wenkai Dai
  
• Tutor: Srikanta Bedathur
  
• June 8, 2010
  F. Chierichetti, R. Kumar, and A. Tomkins. Max-Cover in Map-Reduce. WWW 2010. PDF
• Lecturer: Isha Khosla
• Opponent: Adrian Neumann
  
• Tutor: Mauro Sozio
  
• June 15, 2010
  S. Navlakha, R. Rastogi and N. Shrivastava. Graph summarization with bounded error. SIGMOD 2008. PDF
• Lecturer: Thaer Sammar
• Opponent: (tba)
  
• Tutor: Srikanta Bedathur
  
• June 22, 2010
  R. Jin, H. Hong, H. Wang, Y. Xiang and N. Ruan. Computing Label Constraint Reachability in Graph Databases. SIGMOD 2010. PDF
• Lecturer: Javeria Iqbal
• Opponent: Hassan Issa
  
• Tutor: Srikanta Bedathur
  
• June 29, 2010
  Z. Xu and A. Jacobsen. Processing Proximity Relations in Road Networks. SIGMOD 2010. PDF
• Lecturer: Adrian Neumann
• Opponent: Isha Khosla
  
• Tutor: Srikanta Bedathur
  
• July 6, 2010
  B. Dalvi, M. Kshirsagar and S. Sudarshan. Keyword search on external memory data graphs. PVLDB 2008. PDF
• Lecturer: Wenkai Dai
• Opponent: Andreas Frische
  
• Tutor: Srikanta Bedathur
  
• July 13, 2010
  M. Al Hassan and M. Zaki. Output Space Sampling for graph patterns. PVLDB 2009. PDF
• Lecturer: Aravind Vasudevan
• Opponent: Thaer Sammar
  
• Tutor: Srikanta Bedathur
  
• July 20, 2010
  G. Malewicz, M. Austern, A. Bik, J. Dehnert, I. Horn, N. Leiser and G. Czajkowski. Pregel: A System for Large-Scale Graph Processing. SIGMOD 2010. PDF
• Lecturer: Tran Anh Tuan
• Opponent: Erdal Kuzey
  
• Tutor: Srikanta Bedathur

• Homepage MPI-INF
• About the Institute
• Departments:
  • Algorithms & Complexity
  • Computer Vision and Multimodal Computing
  • Computational Biology & Applied Algorithmics
  • Computer Graphics
  • Databases and Information Systems
    • People
    • Research
    • Offers
    • Teaching
    • News & Events
    • Publications
    • Software
    • Useful Links
  • Computational Genomics and Epidemiology
  • Ontologies
  • Automation of Logic
• News
• People
• Services
• Library
• Doctoral Research Program
• Max Planck Center