Fall 2024: Machine Learning with Graphs – CS 7332 (CRN 20227) & NETS 7332 (CRN 17372)

 

General Information

Time: Tuesdays & Fridays 1:35 – 3:15 PM Eastern	Place: 177 Huntington Ave, 2nd Floor Conference Room (#207)
Instructor: Tina Eliassi-Rad Course website on Canvas: https://northeastern.instructure.com/courses/194307	Office hours: Available by appointment. Email eliassi [at] ccs [dot] neu [dot] edu to setup an appointment; begin the subject line with [fa24 nets]. TA: Ayan Chatterjee. Available by appointment. Email chatterjee [dot] ay [at] northeastern [dot] edu to setup an appointment; begin the subject line with [fa24 nets].

 

Overview

This 4-credit PhD-level course covers state-of-the-art research on mining and learning with graphs. Topics include, but are not limited to, vertex classification, graph clustering, link prediction and analysis, graph distances, graph embedding and network representation learning, deep learning on graphs, anomaly detection on graphs, graph summarization, network inference, adversarial learning on networks, and notions of fairness in social networks.

 

Prerequisites

Students are expected to have taken courses on or have knowledge of the following:

o   Calculus and linear algebra

o   Basic statistics, probability, machine learning, or data mining

o   Algorithms and programming skills (e.g., Python, Julia, C, C++, Java, Ruby, Matlab, or any programming language of their preference)

 

Textbooks

This course does not have a designated textbook. The readings are assigned in the syllabus (see below).

 

Here are some textbooks (all optional) on machine learning and data mining:

• Deep Learning and Graph Representation Learning
• Charu C. Aggarwal. Neural Networks and Deep Learning: A Textbook. Springer, 2018.
• Michael Bronstein, Joan Bruna, Taco Cohen and Petar Veličković. Geometric Deep Learning: Grids, Graphs, Groups, Geodesics, and Gauges. arXiv:2104.13478, April 2021.
• Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning. MIT Press, 2016.
• William L. Hamilton. Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Vol. 14, No. 3, Pages 1-159, 2020.
• Jure Leskovec. Machine Learning with Graphs Video Lectures, Stanford Online, 2021.
• Michael M. Bronstein, Joan Bruna, Taco Cohen, Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, 2021.
• Xavier Bresson. Graph Machine Learning, 2022-23.
• Data Mining and Graph Mining
• Charu C. Aggarwal. Data Mining, The Textbook. Springer 2015.
• Christos Faloutsos, Deepayan Chakrabarti. Graph Mining: Laws, Tools, and Case Studies. Morgan & Claypool Publishers, 2012.
• Jiawei Han, Micheline Kamber, Jian Pei. Data Mining: Concepts and Techniques. Morgan Kaufmann, 3rd edition, 2011.
• David J. Hand, Heikki Mannila, Padhraic Smyth. Principles of Data Mining. A Bradford Book, 2001
• Anand Rajaraman, Jurij Leskovec, and Jeffrey Ullman. Mining of Massive Datasets. Cambridge University Press, v2.1, 2014. (free online) (Errata)
• Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining. Pearson, 2nd edition, 2018.
• Machine Learning
• Charu C. Aggarwal. Linear Algebra and Optimization for Machine Learning: A Textbook. Springer, 2020.
• Christopher Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
• Peter Flach. Machine Learning: The Art and Science of Algorithms that Make Sense of Data. Cambridge University Press, 2012.
• Tom Mitchell. Machine Learning. McGraw Hill, 1997.
• Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, 2012.
• Statistics
• Trevor Hastie, Robert Tibshirani, Jerome Friedman. Elements of Statistical Learning. Springer, 2nd edition, 2009. (free online)

 

Resources

• Probability Review (David Blei, Princeton)
• Probability Theory Review (Arian Maleki and Tom Do, Stanford)
• Linear Algebra Review and Reference (Zico Kolter and Chuong Do, Stanford)
• Theoretical CS Cheat Sheet (Princeton)
• Encyclopedia of Distances (Michel Marie Deza and Elena Deza)

 

Grading

o   Class presentations (40%)

o   I will team up students into groups.

o   Each week will have an assigned team. That team is responsible for presenting the readings for that week.

o   Besides the readings, each paper is likely to have additional materials on the Web. Examples include supplemental materials, video, code, data, etc. These are helpful for presentations and class projects.

o   Your slides for the lecture presentations are due at 12:00 PM Eastern on the day assigned to your team.

o   Class project (50%)

o   Each team will choose (by Tuesday October 8, 2024 at 11:59 PM Eastern) one of the papers in the syllabus to replicate.

o   In addition to replication, each team will propose extension(s) to the chosen paper and implement those extension(s).

o   Each team will write a report (maximum 6 pages) detailing what was learned. Use the style files at https://paperswithcode.com/static/rc2020/ML-Reproducibility-Challenge-2020-Template.zip.

o   Reports are due on Tuesday December 10, 2024 at 11:59 PM Eastern.

o   Project Presentations (10%)

o   Each team will have ~15 minutes to present what they learned when they tried to reproduce their chosen paper, followed by 5 minutes of Q&A.

o   The slides for the presentations are due on Friday December 6, 2024 at 12:00 PM Eastern.

 

Schedule/Syllabus (Subject to Change)

Date	Lecturer	Readings
Fri Sep 6	Tina Eliassi-Rad	Overview ·      The Why, How, and When of Representations for Complex Systems
Tue Sep 10	Tina Eliassi-Rad	Homophily ·      Distribution of Node Characteristics in Complex Networks ·      Combinatorial Characterizations and Impossibilities for Higher-order Homophily ·      Higher-order Homophily on Simplicial Complexes Axiomatic Approaches ·      Measuring Tie Strength in Implicit Social Networks
Fri Sep 13	Tina Eliassi-Rad	Network Comparison and Graph Distances ·      A Guide to Selecting a Network Similarity Method  ·      Network Comparison and the Within-ensemble Graph Distance ·      Non-backtracking Cycles: Length Spectrum Theory and Graph Mining Applications ·      [reference] netrd: A library for Network Reconstruction and Graph Distances
Tue Sep 17	Tina Eliassi-Rad	Role Discovery ·      It's Who You Know: Graph Mining Using Recursive Structural Features ·      RolX: Structural Role Extraction & Mining in Large Graphs ·      Guided learning for Role Discovery (GLRD): Framework, Algorithms, and Applications
Fri Sep 20	Tina Eliassi-Rad	Graph Representation Learning: Node Embedding ·      Laplacian Eigenmaps for Dimensionality Reduction and Data Representation ·      node2vec: Scalable Feature Learning for Networks ·      Structural Deep Network Embedding ·      STABLE: Identifying and Mitigating Instability in Embeddings of the Degenerate Core ·      [reference] Machine Learning on Graphs: A Model and Comprehensive Taxonomy ·      [reference] Network Representation Learning: From Preprocessing, Feature Extraction to Node Embedding ·      [optional] Next Waves in Veridical Network Embedding
Tue Sep 24	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	Low-rank Representations of Complex Networks ·      The Impossibility of Low-rank Representations for Triangle-Rich Complex Networks ·      Node Embeddings and Exact Low-rank Representations of Complex Networks ·      [optional] Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling ·      [optional] Link Prediction Using Low-dimensional Node Embeddings: The Measurement Problem
Fri Sep 27	Team 2: Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	Graph Neural Networks ·      Semi-Supervised Classification with Graph Convolutional Networks ·      Graph Attention Networks ·      Gated Graph Sequence Neural Networks ·      [reference] Graph Neural Networks: A Review of Methods and Applications ·      [reference] A Comprehensive Survey on Graph Neural Networks ·      [optional] Everything is Connected: Graph Neural Networks
Tue Oct 1	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	This and That ·      Hyperbolic Graph Convolutional Neural Networks ·      Principal Neighbourhood Aggregation for Graph Nets ·      Pitfalls of Graph Neural Network Evaluation ·      [optional] The Numerical Stability of Hyperbolic Representation Learning
Fri Oct 4	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	Collective Classification ·      Collective Classification in Network Data ·      Graph Belief Propagation Networks ·      [optional] Cautious Collective Classification
Tue Oct 8	Team 2: Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	Label Propagation on Graphs ·      Combining Label Propagation and Simple Models Out-performs Graph Neural Networks ·      Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification ·      Design Space for Graph Neural Networks (GitHub page) ·      [optional] Message passing all the way up Class project proposals are due at 11:59 PM Eastern.
Fri Oct 11	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	Graph Transformers ·      Graph Transformer Networks ·      A Generalization of Transformer Networks to Graphs ·      Transformers are Graph Neural Networks ·      [reference] Graph Transformers: A Survey
Tue Oct 15	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	ML on Heterogeneous Graphs ·      Modeling Relational Data with Graph Convolutional Networks ·      Heterogeneous Graph Transformer
Fri Oct 18	Team 2:Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	GNNs for Recommendation Systems ·      Neural Graph Collaborative Filtering ·      Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Tue Oct 22	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	W-L Graph Kernels and Power of GNNs ·      Weisfeiler-Lehman Graph Kernels ·      How Powerful are Graph Neural Networks? ·      [optional] A Reduction of a Graph to a Canonical Form and an Algebra arising during this Reduction ·      [reference] Theory of Graph Neural Networks: Representation and Learning
Fri Oct 25	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	Stability and Counting in GNNs ·      Tree Mover’s Distance: Bridging Graph Metrics and Stability of Graph Neural Networks ·      Can Graph Neural Networks Count Substructures?
Tue Oct 29	Team 2: Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	Invariance and Equivariance ·      E(n) Equivariant Graph Neural Networks ·      Invariant and Equivariant Graph Networks
Fri Nov 1	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	Hypergraphs and Higher-order Models ·      Random Walks on Hypergraphs with Edge-Dependent Vertex Weights ·      Hypergraph Neural Networks ·      [reference] A Survey on Hypergraph Mining: Patterns, Tools, and Generators ·      [optional] Simplicial Attention Networks
Tue Nov 5	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	Graph ML for Optimization ·      Assigning Entities to Teams as a Hypergraph Discovery Problem ·      Distributed constrained combinatorial optimization leveraging hypergraph neural networks
Fri Nov 8	Guest Lecturer: Alesia Chernikova	Cyber networks and ML ·      Cyber Network Resilience against Self-Propagating Malware Attacks ·      Modeling Self-Propagating Malware with Epidemiological Models
Tue Nov 12	Team 2: Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	Explainability in GNNs ·      Explainability in Graph Neural Networks: A Taxonomic Survey ·      GNNExplainer: Generating Explanations for Graph Neural Networks
Fri Nov 15	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	Explainability and Trustworthiness of GNNs ·      GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks ·      Trustworthy Graph Neural Networks: Aspects, Methods and Trends
Tue Nov 19	Team 1: Sharaj Kunjar, Tamanna Urmi, Xiyu Yang	Fairness and Equality ·      FAIRGEN: Towards Fair Graph Generation ·      Information Access Equality on Generative Models of Complex Networks
Fri Nov 22	Team 2: Amanuel Tesfaye, Narayan Sabhahit, Yiyuan Zhang	Oversmooting and Oversquashing ·      A Survey on Oversmoothing in Graph Neural Networks ·      How does over-squashing affect the power of GNNs? ·      Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
Tue Nov 26	Team 3: Jesseba Fernando, Joshua “Josh” Rosen, Yicheng “Andy” Zhang	ICML 2024 Position Papers ·      Future Directions in the Theory of Graph Machine Learning ·      Why We Must Rethink Empirical Research in Machine Learning
Fri Nov 29	No class – Thanksgiving break
Tue Dec 3	Guest lecturer: Germans Savcisens	ML for Computational Social Science ·      Using Sequences of Life-events to Predict Human Lives (Website: https://www.life2vec.dk)
Fri Dec 6	In-class project presentations	Your slides are due at 12pm Eastern.
Tue Dec 10	No class – Project reports are due on Tue Dec 10 at 11:59pm Eastern.
Fri Dec 13	No class

 

Notes, Policies, and Guidelines

o   You are expected to have read the assigned material before each lecture.

o   We will use Northeastern’s Canvas for announcements, assignments, and your contributions.

o   When emailing me, begin the subject line with [fa24 nets].

o   For your class project, you can use whatever programming language that you like.

o   Refresh your knowledge of the university's academic integrity policy and plagiarism. There is zero-tolerance for cheating!