CS 848: Graph Analytics and Data Management

Winter 2020

Semih Salihoglu
firname [dot] lastname [at] uwaterloo [dot] ca
DC 3351
Meeting times: Tuesdays, 9am-12pm
Meeting location: DC 2568

Overview

Graphs are one of the most naturals data structures to represent connected entities in the real world. As such, many real world applications model their data in the form of a graph and analyze or query these graphs. Several of the numerous examples include neuro-scientists using brain networks to identify the functionality and importance of neurons, search engines, such as Google, using knowledge graphs for question answering, banks using transaction graphs to detect fraudulent money flow patterns, social networking applications, such as Facebook and LinkedIn, using their social networks to do recommendations. This seminar covers topics in graph analytics and data management that has enabled such applications. We will study the software systems for graph analytics and data management and cover algorithmic work focusing on several machine learning tasks, such as community detection, clustering, link prediction, and influence maximization. We will read a wide range of papers from different communities both within computer science, such as databases, machine learning, systems, and social network analysis, as well as outside of computer science such as biology and physics.

Prerequisites

Having a background on systems, such as having taken courses in distributed systems, computer architecture, is not strictly necessary but helpful. Similarly, having a background on network analytics and graph algorithms is also not necessary but will be helpful for appreciating the papers on graph analytics.

Workload & Mark Breakdown

The main workload will consist of a term-long project that students will do related to one of the topics covered in the seminar. The other workload includes paper reviews and two in-class presentations. In a typical seminar, we will have two paper presentations, roughly 25 minutes each, followed by about an hour of open discussions. Each week a different student will be leading the discussion. This is a seminar, so your participation in the class is very critical to everyone's learning. That is why it will be a significant part of your grade. Please ask questions and make comments throughout the discussions. The workload pieces and mark breakdown is as follows:

• Class Participation: 25%
• Paper Reviews: 10%
• Presentations: 20%
• Project: 45%

Projects

Project Deliverables

• Project Paper: The project papers will be 6 pages. You can have extra pages for the references. They will be written in the two-column ACM proceedings format, using one of the ACM SIG Proceedings Templates. Essentially they should be similar in structure to the papers we read in the seminar.
• Project Source Code: Please put your source code into github and include a link in your project writeup. On the github page, please document exactly how to run your source code.

Paper Reviews

For each class we will be writing two reviews for two of the papers assigned to that day (except the first seminar). If there are more than two papers assigned, you can pick any two of the assigned papers. You are allowed to skip 3 reviews throughout the term. The reviews will be written in the form of peer-reviewed conference reviews. So, they should be critiques that describe the strengths and weaknesses of the paper and contain suggestions to make the paper stronger. Each review must be written in the following template:

• Summary: Describe a brief summary of the paper desribing: (i) What is the problem the paper solves? (ii) Why is this prbolem important? (iii) Why is it hard? Why don't previous methods work? and (iv) What is the solution to the problem the authors propose?
• List 3 strengths of the paper.
• List 3 weaknesses of the paper.
• Suggestions for improvement/further research.

Presentations

Each student will be doing 2 presentations in the term. Each presentation will be about 25 minutes long. Here are the important points summarizing what you have to do for your presentations.

• You must present with slides. The content in your slides should be your own but you can use others' materials, e.g., figures from the paper we are reading, when necessary and by crediting your source on your slide.
• Please have a separate slide for each of 4 questions in the summary item in the Paper Review section.
• It is very helpful to demonstrate the ideas in the paper through examples. So try to have examples in your presentation, e.g., a simulation of some code or system component.

Schedule and Papers