Alongside neural networks, kernel methods are a leading tool for machine learning on graphs. For graph-level learning tasks, kernel methods rely on various properties, ranging from node neighbourhoods to shortest paths between randomly selected nodes, and can also use the diffusion kernel of the graph's Laplacian matrix. However, for large graphs, exact computation of the diffusion kernel becomes computationally infeasible. In this work, we address the acceleration of this computation using Krylov subspace methods, which enable efficient approximations of the kernel for different diffusion times. These approximations form an approximation of the NetLSD method, which represents each graph with a vector that is invariant to permutation, scale, and size. The use of Krylov subspaces enables a trade-off between speed and accuracy, even for very large graphs, for which computation is typically not possible.
|
