Sandeep Kumar - Graph Machine Learning ELL 888 Advanced Machine Learning

Graph Machine Learning AIL 723 and Advanced Machine Learning ELL88

ELL 88 3 credits (3-0-0) AIL 723 4 credits(3-0-1) Pre-requisites: Linear Algebra, Probability, Introductory Machine Learning, and OptimizationSemester II: 2023-2024
Course Objective: This course will assume a background in the basics of linear algebra, machine learning, and optimization. The goal of this course is to train students with foundational mathematical concepts and skills in Machine Learning for high-dimensional, big-data, non-Euclidean, irregular, and geometric data problems. We delve deeply into the methodologies of graph learning and graph mining, emphasizing on theoretical tools to get insights from structured data presented in the form of graphs. The theory will go in conjunction with hands-on analysis of real-world applications with state-of-the-art methods, including ML, networks, learning, computer vision, bioinformatics, controls, etc.

Research-Based Course:

The course is interdisciplinary, it would welcome advanced undergraduate, master's, and Ph.D. students from various disciplines interested in the mathematical foundations and applications of machine learning for high-dimensional, big data, non-Euclidean, and geometric data.

Project: The students could pick topics from their domain, the project will aim to expose students to the state-of-the-art literature in the area and will be helpful for their research.

Module and Lecture Plan

[M1] Basics of graphs & graph learning (4 Weeks/ 8 lectures)

[L1] Introduction: Motivation for Graphs in Machine Learning
[L2 L3] Graph Matrices and Spectral Graph Theory:
- Incidence matrix, adjacency matrix, Laplacian matrix, and eigenspectrum
[L4] Graph Matrix and Graph Features: Conditional Independence, Smoothness, and Dirichlet Energy
[L5] Probabilistic Graphical Models: MRF, GMRF, ISING MODEL, EXPONENTIAL FAMILY OF DISTRIBUTION, Hammersely Clifford Factorizability theorem, Partition matrix, etc.
[L6] Graph Learning from data: Pairwise graph K-nn, epsilon graph, correlation-based graph,
[L7] Smoothness-based problem formulation and optimization algorithm
[ L8] Probabilistic Model-based Graph Learning from Data: Likelihood Estimation of Precision Matrix, problem formulation and Optimization Algorithm

[M2] Basics of Differential Geometry (3 Weeks/ 6 lectures)

[L1] Introduction to Differential Geometry: Basics of the geometry of curves and surfaces
[L2] Review of differential geometry: topological manifold, smooth manifold, coordinates, charts, and atlases
[L3] Review of Riemannian geometry: Riemannian metric, geodesics, examples of constant curvature spaces
[L4] Matrix Manifolds: Stiefel, Grassmannian manifolds
[L5] Optimization Methods for Manifolds
[L6] Algorithms on Riemannian manifolds (PCA, Karcher mean, PGA,, etc.)

[M3] Manifolds to Graphs: Graphs to Approximate Manifold Geodesics

(3 Weeks/ 6 lectures)

[L1] Geodesics and Manifold Learning: Convergence of Graph Geodesics
[L2] IsoMap, MDS and Dimensionality Reduction,
[L3] Laplacian Beltrami operator, the convergence of the graph Laplacian
[L4] Foundation in Graph-based Semi(un)-Supervised Learning, Supervised,
[L5 L6] Graph Regularization and Label Propagation: Manifold SVM and Spectral Clustering

[M4] Graphs to Manifold: Graph Representation Learning (4 weeks/ 8 lectures)

[L1] From Graphs to Manifolds Basics: Shallow Graph Embeddings: Deep Walk, Random Walk, MDS, etc.
[L2] From Graphs to Manifolds: Graph Neural Networks
[L3] Spectral and Spatial Graph Convolution and their theoretical properties
[L4] Graph Attention Network and Graph Transformers

[L5] Expressive power of graph neural networks
[L6] Robustifying Approaches for Graph Neural Network: Graph relearning, signal denoising, etc.
[L7] Geometric Graph Neural Networks: Hyperbolic Graph Neural Networks
[L8] GNN and it’s Applications

Evaluation Plan

ELL 888

Scribing and slides (10%),
Project (25%) Individually or in pairs: outstanding performance in a project will be appropriately rewarded.
Mid-sem exam (20%)
End-sem exam (45%)

AIL 723

Scribing and slides (10%),
Assignment (15%)
Project (10 %) Individually or in pairs: outstanding performance in a project will be appropriately rewarded.
Mid-sem exam (20%)
End-sem exam (45%)

Readings:

Murphy, Kevin P. Machine Learning: A Probabilistic Perspective. MIT Press, 2021.
Koller, Daphne, and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009.
Boumal, Nicolas. "An Introduction to Optimization on Smooth Manifolds." Available online, Aug (2020).
Research Papers from JMLR, NeurIPS, ICML, IEEE TIT, IEEE TSP, IEEE TPAMI, etc.