BU CS599 Advanced Topics in CS
Graph Analytics – Fall 2021

Graphs are mathematical objects that model pairwise relations between entities/objects. They model a wide variety of important datasets including the World Wide Web, online social networks and other social media, transportation networks, scientific collaborations, and even the human brain. This class aims to introduce students to cutting-edge research on applied graph algorithms, and machine learning with graphs. Topics of interest include motifs as building blocks of networks, motif detection and counting algorithms, worst case optimal joins, graph generative models starting from random binomial graphs to deep learning based models, graph clustering and dense cluster detection algorithms, node embeddings for downstream machine learning tasks on graphs, and graph neural networks.

Syllabus

A tentative syllabus is available here.

Where and When

• Time: Weekly on Tue and Thu, 11am-12.15pm
  
• Location:  MCS B33
  
• Office hours: Weekly on Friday 5-6pm, MCS 102

Blackboard

We will use blackboard for online discussions/questions etc.

Prerequisites

One should have had the Algorithm Design course (CS330). Familiarity with coding is necessary. Some more advanced courses in machine learning, statistics, and computer science will be helpful but are not required.

Grading

The final grade will be computed as a weighted sum of two grades:

1. Project (60%)
2. Assignment (40%)

• Teams up to two (2) people are allowed for the class project. The project is an opportunity for you to explore an interesting graph mining problem. A wide variety of projects is allowed ranging from systems-oriented projects on managing efficiently big graphs, to graph algorithm design and deep learning on graphs. Your performance will be evaluated on the technical depth, the scope of the project, the clarity of your technical report, and your final presentation.
  
• The assignment is individual. It is a challenging assignment, so make sure you start working early You may discuss the problems with other students, but you must write your solutions independently, based on your own understanding. Academic integrity dictates citing any sources that you use on the problem set. Finally, using Github is mandatory for submitting your code.

Schedule

– 9/2: Lecture 1, Introduction (Slides)

– 9/7: Lecture 2, Motifs (Slides)

– 9/9: Lecture 3, Color coding (Slides)

– 9/14: Lecture 4, Triangle counting (Slides)

– 9/16: Lecture 5, Triangle counting (cont.), Loomis-Whitney inequality (Slides)

– 9/21: Lecture 6, WCOJ (Slides)

– 9/23: Lecture 7, WCOJ (cont.) (Slides)

– 9/28: Lecture 8, Empirical properties of real world networks (Slides)

– 9/28: Lecture 9, Random graph models (Slides)

– 10/5: Lecture 10, Erdős–Rényi model (Notes)

– 10/7: Lecture 11, Erdős–Rényi model (cont.) (Notes)

– 10/14: Lecture 12 (Guest Lecture by Kostas Sotiropoulos)
Link prediction
Part 1,
Part 2 Signed Networks (Jure Leskovec slides),
Part 3 TwitterMancer

– 10/19: Lecture 13, Connectivity in ER, stochastic blockmodel

– 10/21: Lecture 14, Morris counter, Distinct elements (Slides)

– 10/26: Lecture 15, Distinct elements (cont.) (Slides)

– 10/28: Lecture 16, Frequent items (Blackboard)

– 11/2: Lecture 17, Graph Streaming algorithms (Slides)

– 11/4: Lecture 18, Heavy Hitters (blackboard)

– 11/9: Lecture 19, Hackathon

– 11/11: Lecture 20, Hackathon

– 11/16: Lecture 21, Dense subgraph discovery I (Slides)

– 11/18: Lecture 22, Dense subgraph discovery II (Slides)

– 11/23: Lecture 23, Spectral Graph Theory I (Blackboard)

– 11/25: Thanksgiving break

– 11/30: Lecture 24, Spectral Graph Theory II (Blackboard)

– 12/2: Lecture 25, Cheeger’s inequality (Blackboard)

– 12/7: Project presentations I

– 12/9: Project presentations II