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.