Machine Learning with Graphs

Logistics

Instructor: Arlei Silva
Lectures: Tuesday, Thursday 2:30-3:45 DCH 1070 (Duncan Hall)
Office hours: Monday 2:30-3:30, Wednesday 10:00-11:00 DCH 3001 (Duncan Hall)
Teaching assistants: Guanchu Wang (guanchu.wang@rice.edu), Ruixiang Tang (rt39@rice.edu)
Piazza: piazza.com/rice/spring2022/comp559001
Zoom: riceuniversity.zoom.us/j/91437109393?pwd=SW1XV0tjaFp0bEJ6OUpjTFlrL3JWQT09

Course description

Graphs show up in machine learning in many forms. Oftentimes, the input data can be naturally represented as a graph, such as for relational learning tasks applied to social networks and graph kernels applied to chemical data. Other times, graphs are just a framework to express some intrinsic structure in the data, such as for graphical models and non-linear embedding. In both cases, recent advances in representation learning (or graph embedding) and deep learning have generated a renewed interest in machine learning on graphs. This course will overview both traditional and more recent graph-based machine learning algorithms.

At the end of the course, students are expected to be able to: (1) identify the appropriate graph-based machine learning algorithm for a given problem; (2) extend existing algorithms to solve new related problems; and (3) recognize some of the key research challenges in the field.

The course will be a mixture of lectures, student presentations, homework assignments (including programming), and a hands-on semester-long project.

Credit hours: 3

Recommended prerequisites

Undergraduate-level linear algebra, undegraduate-level probability and statistics, basic Python programming.

Course materials

No textbook is required. Lecture notes will be shared for reference after the class. The notes will be based on a recommended list of references.

Grading

• 40% Semester-long project (proposal, progress report, final report, brief presentation);
• 40% Weekly homework assignments;
• 20% Paper presentation.

Logistics

Homeworks and reports should be submitted on Canvas. Questions should be submitted on Piazza. For personal matters, please email the instructor or the TAs.

Rice honor code

Students are expected to adhere to the Rice Honor Code. You are encouraged to collaborate and to find resources online. However, all the material to be graded is expected to be original. The exceptional use of someone else's work, such as a figure, should be properly recognized.

Students with disabilities

If you have a documented disability that may affect academic performance, you should: 1) make sure this documentation is on file with Disability Support Services (Allen Center, Room 111 / adarice@rice.edu / x5841) to determine the accommodations you need; and 2) meet with me to discuss your accommodation needs.

Related courses at Rice

• ELEC 573: Network Science and Analytics taught by Prof. Segarra in the Fall;
• ECE677-001: Distributed Optimization & ML taught by Prof. Uribe in the Fall;
• CAAM 570: Graph Theory taught by Prof. Hicks in the Spring.

Schedule

• 1/11: Logistcs, overview, introduction (notes)
• 1/13: Graph algorithms I (notes)
• 1/18: Graph algorithms II (notes)
• 1/20: Network science I (notes)
• 1/25: Network science II (notes)
• 1/28: Problems
• 2/01: Evaluation
• 2/03: Spectral graph theory I
• 2/08: Spectral graph theory II
• 2/10: Spring recess
• 2/15: Non-linear embedding I
• 2/17: Non-linear embedding II
• 2/22: Graph kernels I
• 2/24: Graph kernels II
• 3/01: Optimization on graphs I
• 3/03: Optimization on graphs II
• 3/08: Graphical models I
• 3/10: Graphical models II
• 3/15: Spring break
• 3/17: Spring break
• 3/22: Graphical models III
• 3/24: Graphical models IV
• 3/29: Graph embedding I
• 3/31: Graph embedding II
• 4/05: Graph neural networks I
• 4/07: Graph neural networks II
• 4/12: Paper presentations I
• 4/14: Paper presentations II
• 4/19: Project presentations I
• 4/21: Project presentations II

References

1. Christopher M Bishop. Pattern Recognition and Machine Learning. Springer, 2006


2. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer, 2009


3. Lise Getoor and Ben Taskar. Introduction to statistical relational learning. MIT press, 2007


4. John A Lee and Michel Verleysen. Nonlinear dimensionality reduction. Springer, 2007


5. Fan RK Chung Spectral Graph Theory. AMS, 1997


6. Swarnendu Ghosh, Nibaran Das, Teresa Goncalves, Paulo Quaresma, and Mahantapas Kundu. The journey of graph kernels through two decades. Computer Science Review, 27:88-111, 2018

111, 2018.
7. Daniel Spielman. Spectral and Algebraic Graph Theory. Incomplete Draft, 2019


8. Mark Newman. Networks. Oxford university press, 2018


9. William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2020