How do we learn in linear time O(n) (w.r.t. graph size nn)? The O(n2) complexity is a direct result of using Laplacian eigenvectors. We need to avoid eigen-decomposition, which can be achieved by directly learning a function of the Laplacian. The spectral function will be a monomial of the Laplacian as shown here.
Comment apprenons-nous en temps linéaire O(n) (taille du graphe par rapport à n) ? La complexité O(n2) est le résultat direct de l’utilisation de vecteurs propres laplaciens. Nous devons éviter la décomposition propre, qui peut être réalisée en apprenant directement une fonction du Laplacien. La fonction spectrale est un monôme du Laplacien comme montré ici :