Machine Learning with Graphs / Spring 2024
Graphs offer a natural way to represent complex relationships among objects of all kinds. Neural network learning with graphs has become important in both academic research and industrial applications. This course (for graduate and undergraduate students who meet the prerequisites) offers a mixture of fundamental concepts, algorithms, basic and advanced models, and applications ranging from social popularity analysis and knowledge graph reasoning to deep learning for solving NP-complete problems.
Logistics
- Class times: Tuesdays and Thursdays 12:30pm - 1:50pm
- Room: NSH 1305
- Course identifier: LTI 11-741/11-641/11-441
- Office hours: See Piazza
Prerequisites
CS courses on data structures, algorithms, programming (e.g., 15-213), linear algebra (e.g., 21-241 or 21-341), and introductory probability (e.g., 21-325). Introductory Machine Learning (e.g., 10-701 or 10-601) and neural network courses will be helpful but not required.
Course Materials
No textbook is used in this course. Instead, relevant papers/readings are listed as references. Course slides and reading material are available online for registered students who will be given the user ID and password.
Exams
Open-book midterm and final exams, with a set of questions (about 10) and a list of possible answers to choose from per question. Mid-term exam will cover the lecture contents in the 1st half of the semester, and the final exam will cover the lecture contents in the 2nd half. The exams will not focus on the contents of the HW assignments.
Homework (Programming Assignments)
- HW1. Implementing neural networks (CNN and RNN) for binary classification with word embedding on the Yelp review dataset and using software like TensorFlow or Keras.
- HW2. Implementing soft-max logistic regression for multi-class classification of Yelp reviews, with the derivation of the gradients of the loss functions.
- HW3. Implementing PageRank, Personalized PageRank and Query Sensitive PageRank methods for web-page popularity analysis and evaluating their retrieval performance on the CiteEval dataset.
- HW4. Implementing Graph Neural Network (GNN) models for simi-supervised node classification, link prediction, and graph classification.
- HW5. Reasoning with Knowledge Graphs; Node Embedding with TransE.
Schedule (tentative)
-
ClassTypeTopicResources
-
# 1 01/16/2024Lecture
slidesOverview
Course overview and introduction -
# 2 01/18/2024Lecture
slidesDL1
Word Embedding -
# 3 01/23/2024Lecture
slidesDL2
Recurrent Neural Network -
# 4 01/25/2024Lecture
slidesDL3
Convolutional Neural NetworksMain readings: Homework:- HW1. RNN & CNN classifiers.
- Due 2/8 11:59PM
- HW1. RNN & CNN classifiers.
-
# 5 01/30/2024Lecture
slidesDL4
Neural Attention Models -
# 6 02/01/2024Guest speaker
slidesDL5
Language Model Architectures (Invited Lecture by Ruohong Zhang)Main readings: -
# 7 02/06/2024Lecture
slidesCLS1
Binary Logistic Regression & ConvexityMain readings: -
# 8 02/08/2024Lecture
slidesCLS2
Multi-class Logistic Regression & Decision BoundariesHomework:- HW2. Softmax with SGD
- Due 2/27 11:59PM
- HW2. Softmax with SGD
-
# 9 02/13/2024Lecture
slidesCLS3
Stochastic Gradient Descent (SGD), Evaluation MetricsMain readings: -
# 10 02/15/2024Lecture
slidesCLS4
Extreme-scale Neural Classifiers (XTransformer, AttentionXML) -
# 11 02/20/2024Lecture
slidesGraph 1
Social Popularity Analysis I: HITS & PageRank -
# 12 02/22/2024Lecture
slidesGraph 2
Social Popularity Analysis II: Personalized & Topic-sensitive PageRank -
# 13 02/27/2024Lecture
slidesGraph 3
Matrix Factorization (Eigendecompostion and SVD) -
# 02/29/2024Exam
Midterm Exam on Lectures 1-13
Note:- in the same classroom and time slot as a regular class
- in the same classroom and time slot as a regular class
-
# 03/05/2024Spring break
Spring break
Spring break -
# 03/07/2024Spring break
Spring break
Spring break -
# 14 03/12/2024Lecture
slidesGraph 4
Node Embedding -
# 15 03/14/2024Lecture
slidesGraph 5
Graph Neural Networks (I)Main readings: Homework:- HW4. Graph-based prediction tasks.
- Due 4/9 11:59PM
- HW4. Graph-based prediction tasks.
-
# 16 03/19/2024Lecture
slidesGraph 6
Graph Neural Networks (II) -
# 17 03/21/2024Guest Speaker
slidesGraph 7
Knowledge Graph Embedding (I): TransE, RotatE (Invited Lectured by Zhiqing Sun) -
# 18 03/26/2024Lecture
slidesGraph 8
Knowledge Graph Embedding (II): AnalogyMain readings: -
# 19 03/28/2024Lecture
slidesGraph 9
ML for NP-Complete Problems (I): Autoregressive Neural Solvers -
# 20 04/02/2024Lecture
slidesGraph 10
ML for NP-Complete Problems (II): Non-autoregressive Neural Solvers -
# 21 04/04/2024Lecture
slidesGraph 11
ML for NP-Complete Problems (III): Other Neural CO Solvers (LLMs)Main readings: Homework:- HW5. Node Embedding with TransE.
- Due 4/25 11:59PM
- HW5. Node Embedding with TransE.
-
# 22 04/09/2024Guest Speaker
slidesGraph 12
Improving the Scalability of Graph Neural Networks (by Dr. Neil Shah at Snap Research) -
# 04/11/2024No class
Spring carnival (No class)
Spring carnival (No class) -
# 04/13/2024No class
Spring carnival (No class)
Spring carnival (No class) -
# 23 04/16/2024Guest Speaker
slidesGraph 13
Machine Learning on Graph for Recommendation: User Coldstart, Exploration, and Efficiency (invited lecture by Dr. Yinglong Xia from Meta) -
# 24 04/18/2024Lecture
slidesGraph 14
Reasoning with Heterogeneous Graphs (I) -
# 25 04/23/2024Lecture
slidesGraph 15
Reasoning with Heterogeneous Graphs (II)Main readings: -
# 04/25/2024Exam
Final Exam on Lectures 14 - 25
Note:- in the same classroom and time slot as a regular class
- in the same classroom and time slot as a regular class
Grading policies
- We have merged the previous 11-741 (PhD level) and 11-641 (Master Level) sections into one (11-741, 12 units) for graduate students (PhD or Master without distinction). Undergraduate students should take the 11-441 section (9 units), which is the same as before.
- Graduate students (in 11-741) are required to do all the 5 homework (HW) assignments, and all the questions in the midterm and final exams.
- Undergraduate students (in 11-441) are required to do 4 out of the 5 HW assignments, by their own choices, and 70% of the exam questions (e.g., 7 out of the total of 10 questions), again by their own choices. If an undergraduate chooses to do more HW assignments, we will use the best-4 scores in the final HW grading. Similarly, if an undergraduate chooses to do more exam questions, we will use the scores of the 70% best answered questions in the Exam grading.
- The table below shows the grading policies explicitly.
11-741/641 (Grad Level) | 11-441 (UG Level) | |
Midterm Exam | 15% | 14% |
Final Exam | 15% | 14% |
HWs | 14% x 5 = 70% | 18% x 4 = 72% |
Late policies
- Homework is due by 11:59pm of the due date. It must be submitted by Gradescope. If Gradescope is down, it must be submitted by email to the TA.
- A 10% penalty is applied for each day that the homework is late.
- Cheating (form to sign)
Grace days
- There are 5 grace days for the homework submissions.
- Grace days will be automatically and greedily applied when you submit a late homework.
- 5 grace days are for ALL of your homework, NOT EACH INDIVIDUAL homework, so if you use 5 days for HW1, then you no longer have any grace days for later homeworks.
- For each individual homework, the code and report are submitted separately for autograding purposes. The penalty will be computed based on the submission time of which ever was submitted last. So if you submit the report before deadline but didn't submit your code on time, it is still considered late.
- No penalty is applied if you use grace days.
- Grace days cannot be applied to the last homework (i.e., HW5).
Covid Teaching Strategies
- If lecturers or students cannot come to the in-person classes due to illness or exposure to COVID, videos of live recordings from this semester or a past semester will be offered through piazza. A notification will be sent out in advance by the instructors via piazza if they cannot deliver the lectures in person.
- All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.