Part of Advances in Neural Information Processing Systems 21 (NIPS 2008)
Mark Herbster, Massimiliano Pontil, Sergio Galeano
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×m Gram matrix of the pseudoinverse of the graph Laplacian in O(n+m2+mS) 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. To this end we present experiments on two web-spam classification tasks, one of which includes a graph with 400,000 nodes and more than 10,000,000 edges. The results indicate that the accuracy of our technique is competitive with previous methods using the full graph information.