Spectral Methods for Graph Neural Networks: A Linear Algebra Perspective

Abstract

The powerful tools like Graph Neural Networks (GNNs) have been helpful for learning graph-based architectures. There are various fields which employ GNNs in their applications such as social networks, computational biology, molecular chemistry and recommendation systems. The GNNs include spatial approaches and spectral methods. Spectral methods are basically the mathematical models with a disciplined framework. Such methods and approaches provide a optimal implementation of the machine and deep learning algorithms to produce state of the art applications in the field of artificial intelligence. In this study, GNNs are analyzed based on spectral methods in the context of linear algebra. This study mainly focusses on examining the eigen-structures of graph Laplacians and analyzing the graph convolutions. This mathematical study is comprised of finding out relationships between spectral filters and other topics such as properties of localization and polynomial approximations. A few considerations we have explored as the new contributions to this study. These include a comprehensive analysis of ChebNet approximations, spectral bounds on expressiveness using Weisfeiler-Leman theory, computational complexity, and the stability analysis under graph perturbations. We prove that k-order spectral filters achieve O(1/K^2 ) approximation error for smooth signals and work on related conditions. This study with new contributions provide further strong mathematical foundations for developing grounded GNN architectures.