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 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. 


University of Notre Dame

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.

Learn Before

Related

Learn After