# Spectral graph convolutions What is the 'shift' in graphs? What is the equivalent of fourier basis for graphs? Solution: Eigen vectors of [[Graphs#Graph Laplacian]] used as analogy to [[Fourier Transform]]. Equivalent on grids, but not on graph. For undirected graphs, symmetric adjacency matric and graph Laplacian. For directed graph, we have generalized eigenvectors/Jordan decomposition. Compute (Graph) Fourier Transform $ \widehat{x}=\Phi^{*} x $ Where $\Phi^{*}$ are the eigenvectors (conjugate transpose) of graph Laplacian. Apply filter in Fourier space $ \hat{x} \odot \widehat{w}=\left[\begin{array}{ccc} \widehat{w}_{1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \hat{w}_{n} \end{array}\right] \hat{x} $ Compute Inverse (Graph) Fourier Transform $ x * y=\Phi \cdot(\widehat{x} \odot \widehat{w}) $ ## Some drawbacks - Complexity - Computational complexity of at least $O\left(n^{2}\right)$ - Parameter complexity of $O(n)$ - Isotropic filters - In a graph there is no sense of "up", "down", "left", "right" We cannot assign an order on edges, so all weights must be shared We don't even have same size neighborhoods per node -> Isotropic filters - Filters that depend on choice of basis and do not generalize across graphs. - Filters are dependant on the basis --- ## References 1. Lecture 7.4, UvA DL course 2020