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