Coarse-and-Learn: Efficient Online Node Labeling

We consider online node classification over a very large undirected graph, where a key step is the inverse of a large, sparse Laplacian matrix. We explore the benefits and limitations of graph coarsening, in which nodes not currently being labeled are summarized into supernodes, producing an informative compressed Laplacian at each step. This results in a computationally scalable method for very large graphs. We give kernel-dependent learning bounds of O(tr(M)+ϵ) where M is the inverse regularized kernel matrix, which can reduce to O(n+ϵ) for the appropriate choice of kernel. Here, ϵ is the spectral error between the coarsened and uncoarsened matrix M. Our large-scale numerical experiments suggest comparable learning performance, for considerable computational cost reduction.