MAT 6495 - Spectral Graph Theory - Fall 2021 UdeM
UdeM MAT 6493

MAT 6495

Spectral Graph Theory

Fall 2021

Guy Wolf (guy.wolf@umontreal.ca)


While graphs are intuitively and naturally represented by vertices and edges, such representations are limited in terms of their analysis, both theoretically and practically (e.g., when implementing graph algorithms). A more powerful approach is yielded by representing them via appropriate matrices (e.g., adjacency, diffusion kernels, or graph Laplacians) that capture intrinsic relations between vertices over the "geometry" represented by the graph structure. Spectral graph theory leverages such matrices, and in particular their spectral and eigendecompositions, to study the properties of graphs and their underlying intrinsic structure. This study leads to surprising and elegant results, not only from a mathematical standpoint, but also in practice with tractable implementations used, e.g., in clustering, visualization, dimensionality reduction, manifold learning, and geometric deep learning. Finally, since nearly any modern data nowadays can be modelled as a graph, either naturally (e.g., social networks) or via appropriate affinity measures, the notions and tools studied in this course provide a powerful framework for capturing and understanding data geometry in general.

This is a graduate-level 4 credit course at UdeM, available also via the ISM. It is suitable for CS, statistics, and applied math students interested in data science and machine learning.


Meetings

Lectures:

Mondays 14h00-17h00 (AA-5183) & Tuesdays 12h00-13h00 (AA-5448)

Textbooks

No required textbook, but the following book is recommended and should cover a large portion of the materials in the coures:

Topics (tentative list):


Final grade composition:

The final grade in this class will be based on two components:

Literature review:


Project:

Details will be announced soon (first in class, then posted here).

Homework:

While discussion between students is not discouraged, homework are meant to be done & submitted individually.