Fast Prediction on a Tree

Given an n -vertex weighted tree with structural diameter S and a subset of m vertices, we present a technique to compute a corresponding m \times m Gram matrix of the pseudoinverse of the graph Laplacian in O(n m 2 m S) time. We discuss the application of this technique to fast label prediction on a generic graph. We approximate the graph with a spanning tree and then we predict with the kernel perceptron. We address the approximation of the graph with either a minimum spanning tree or a shortest path tree. The fast computation of the pseudoinverse enables us to address prediction problems on large graphs.