There are several methods designed to improve the efficiency of spectral convolutional methods. For example, ChebNet uses Chebyshev polynomials to approximate the spectral convolution, improving the time complexity to $$O(KM)$$, where $$K$$ is the polynomial order and $$M$$ is the number of edges.

University of Notre Dame

Google

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.

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. https://doi.org/10.1109/tkde.2020.2981333

Deep Learning on Graphs: A Survey

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