– tags: Graph Signal Processing
Intro
- The kernel is defined in Fourier space and graph Fourier transforms are notoriously expensive to compute.
- O(N²) operation for a graph with N nodes: the multiplication operation for i/p nodes and eigenvec of graph’s laplacian.
- Thus as a solution to the computational complexity introduced by it, Monte Carlo (biased random sampling method) approaches to consistently estimate the integrals, which allowed for batch training, reducing the overall training time.
- We hypothesize that the nonlinearity between GCN layers is not critical — but that the majority of the benefit arises from the local averaging. –IBM paper on Fast GCN
- The project removed the nonlinear transition functions between each convolutional layer. The final softmax activation allowed for probabilistic outputs that can be optimized with stochastic gradient descent.