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. 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.

Authors

• Mark Herbster
• Massimiliano Pontil
• Sergio Galeano

Keywords

No keywords are indexed for this paper.