A Scalable Multiclass Algorithm for Node Classification
  We introduce a scalable algorithm, MUCCA, for multiclass node classification
in weighted graphs. Unlike previously proposed methods for the same task, MUCCA
works in time linear in the number of nodes. Our approach is based on a
game-theoretic formulation of the problem in which the test labels are
expressed as a Nash Equilibrium of a certain game. However, in order to achieve
scalability, we find the equilibrium on a spanning tree of the original graph.
Experiments on real-world data reveal that MUCCA is much faster than its
competitors while achieving a similar predictive performance.
