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 NPcomplete problems.
Logistics
 Class times: Tuesdays and Thursdays 12:30pm  1:50pm
 Room: NSH 1305
 Course identifier: LTI 11741/11641/11441
 Office hours: See Piazza
Prerequisites
CS courses on data structures, algorithms, programming (e.g., 15213), linear algebra (e.g., 21241 or 21341), and introductory probability (e.g., 21325). Introductory Machine Learning (e.g., 10701 or 10601) 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
Openbook midterm and final exams, with a set of questions (about 10) and a list of possible answers to choose from per question. Midterm 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 softmax logistic regression for multiclass 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 webpage popularity analysis and evaluating their retrieval performance on the CiteEval dataset.
 HW4. Implementing Graph Neural Network (GNN) models for simisupervised 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
Multiclass 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
Extremescale 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 & Topicsensitive PageRank 
# 13 02/27/2024Lecture
slidesGraph 3
Matrix Factorization (Eigendecompostion and SVD) 
# 02/29/2024Exam
Midterm Exam on Lectures 113
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. Graphbased prediction tasks.
 Due 4/2 11:59PM
 HW4. Graphbased 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 NPComplete Problems (I): Fundamentals (Invited Lecture by Shengyu Feng)Main readings: 
# 20 04/02/2024Guest Speaker
slidesGraph 10
ML for NPComplete Problems (II): with RNN, Transformer, Active Search 
# 21 04/04/2024Lecture
slidesGraph 11
ML for NPComplete Problems (III): with DRL, Diffusion Models, LLMsMain readings: DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
 DIFUSCO: Graphbased Diffusion Solvers for Combinatorial Optimization
 HW5. Node Embedding with TransE.
 Due 4/18 11:59PM
 DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems

# 22 04/09/2024Guest Speaker
slidesGraph 12
Improving the Scalability of Graph Neural Networks (by Dr. Neil Shah at Snap Research)Main readings: 
# 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)Main readings: 
# 24 04/18/2024Lecture
slidesGraph 14
Reasoning with Heterogeneous Graphs (I)Main readings: 
# 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 11741 (PhD level) and 11641 (Master Level) sections into one (11741, 12 units) for graduate students (PhD or Master without distinction). Undergraduate students should take the 11441 section (9 units), which is the same as before.
 Graduate students (in 11741) are required to do all the 5 homework (HW) assignments, and all the questions in the midterm and final exams.
 Undergraduate students (in 11441) 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 best4 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.
11741/641 (Grad Level)  11441 (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 inperson 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.