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.

University of Notre Dame

The first draw back is that it’s computational expensive because of the calculation of eigenvalue decomposition, which is $O(N^3)$ in time complexity, and the matrix multiplication, which is $O(N^2)$ in time complexity. 

The second drawback is that the transformation based on graph Laplacian matrix, so the parameters can’t be shared across different graphs. 


Drawbacks of fundamental Spectral Convolutional methods

Zhang, Z., Cui, P., & Zhu, W. (2020). Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering.

Deep Learning on Graphs: A Survey

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.

Learn Before

Related