There’re lots of methods that improve the efficiency of spectral convolutional methods. For example, ChebNet used Chebyshev polynomial to approximate the spectral convolution, and improve the time complexity to $O(KM)$, where $K$ is polynomial  order and $M$ is number of edges.

Modification of Spectral Convolutional Methods to improve efficiency.

There are s series of methods that generalize spectral convolution methods to multiple graphs. For example, Neural FPs proposed a first-order based spectral convolution method, so different graphs can share the same parameters. PATCHY-SAN assigned an unique nodes order for each graph, and define a neighbor nodes set of fixed size for each node in the graph, and apply 1-D convolutional neural network to each node in the graphs.

 Modification of Spectral Convolutional Methods to Adapt to Multiple Graphs

The first drawback of fundamental spectral convolutional methods is that they are computationally expensive because of the calculation of eigenvalue decomposition, which is $$O(N^3)$$ in time complexity, and matrix multiplication, which is $$O(N^2)$$ in time complexity. The second drawback is that the transformation is based on the graph Laplacian matrix, so the parameters cannot be shared across different graphs.

University of Notre Dame

Google

Spectral convolution methods perform graph Fourier transformation on nodes and map to spectral domain, which involved conducting eigenvalue decomposition of graph Laplacian matrix.

Spectral Convolution Methods

Zhang, Z., Cui, P., & Zhu, W. (2020). Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering. https://doi.org/10.1109/tkde.2020.2981333

Learn Before

Related

Learn After