Graph Transduction as a Noncooperative Game

Graph transduction is a popular class of semisupervised learning techniques that aims to estimate a classification function defined over a graph of labeled and unlabeled data points. The general idea is to propagate the provided label information to unlabeled nodes in a consistent way. In contrast to the traditional view, in which the process of label propagation is defined as a graph Laplacian regularization, this article proposes a radically different perspective, based on game-theoretic notions. Within the proposed framework, the transduction problem is formulated in terms of a noncooperative multiplayer game whereby equilibria correspond to consistent labelings of the data. An attractive feature of this formulation is that it is inherently a multiclass approach and imposes no constraint whatsoever on the structure of the pairwise similarity matrix, being able to naturally deal with asymmetric and negative similarities alike. Experiments on a number of real-world problems demonstrate that the proposed approach performs well compared with state-of-the-art algorithms, and it can deal effectively with various types of similarity relations.