Timezone: »

 
Poster
Fast Prediction on a Tree
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano

Tue Dec 09 07:30 PM -- 12:00 AM (PST) @
in Posters »
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.
[ PDF] 

Author Information

Mark Herbster (University College London)
Massimiliano Pontil (IIT & UCL)
Sergio Rojas Galeano

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors