Graph Transduction as a Noncooperative Game

Erdem A. , Pelillo M.

NEURAL COMPUTATION, cilt.24, ss.700-723, 2012 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 24 Konu: 3
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1162/neco_a_00233
  • Sayfa Sayıları: ss.700-723


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.