Graph Transduction as a Noncooperative Game

Creative Commons License

Erdem A., Pelillo M.

NEURAL COMPUTATION, vol.24, no.3, pp.700-723, 2012 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 24 Issue: 3
  • Publication Date: 2012
  • Doi Number: 10.1162/neco_a_00233
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.700-723
  • Hacettepe University Affiliated: Yes


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.