Unsupervised Domain Adaptation using Graph Transduction Games

Sebastiano Vascon, Sinem Aslan, Alessandro Torcinovich, Twan van Laarhoven, Elena Marchiori, Marcello Pelillo

Abstract

Unsupervised domain adaptation (UDA) amounts to assigning class labels to the unlabeled instances of a dataset from a target domain, using labeled instances of a dataset from a related source domain. In this paper, we propose to cast this problem in a game-theoretic setting as a non-cooperative game and introduce a fully automatized iterative algorithm for UDA based on graph transduction games (GTG). The main advantages of this approach are its principled foundation, guaranteed termination of the iterative algorithms to a Nash equilibrium (which corresponds to a consistent labeling condition) and soft labels quantifying the uncertainty of the label assignment process. We also investigate the beneficial effect of using pseudo-labels from linear classifiers to initialize the iterative process. The performance of the resulting methods is assessed on publicly available object recognition benchmark datasets involving both shallow and deep features. Results of experiments demonstrate the suitability of the proposed game-theoretic approach for solving UDA tasks.

Introduction

Deep learning models typically require vast amounts of labeled data to generalize effectively. However, when a model trained on a source domain is applied to a related but different target domain, performance often degrades due to "domain shift." Unsupervised Domain Adaptation (UDA) seeks to mitigate this by labeling target data using source knowledge without requiring manual target labels.

While current state-of-the-art UDA methods often rely on complex deep neural networks that are computationally expensive and sensitive to hyperparameters, this paper introduces Graph Transduction Games (GTG). This framework offers a principled, parameter-free alternative that treats label assignment as a non-cooperative game, seeking a state of maximum consistency across the dataset.

Methodology: The GTG Framework

The proposed approach casts UDA as a game played among data points. The process follows a structured pipeline from feature normalization to the final game-theoretic adaptation.

Figure 1: Flowchart of the proposed UDA framework using Graph Transduction Games (GTG).

Game-Theoretic Formulation

  1. Players and Strategies: Every data point (source and target) is a "player." The available "strategies" for these players are the possible class labels.
  2. Payoff Function: Players earn a payoff by choosing labels consistent with their neighbors. If two similar data points (defined by an affinity matrix) choose the same label, they receive a high payoff.
  3. Replicator Dynamics: The game is played iteratively using Replicator Dynamics from evolutionary game theory. Labels that yield higher payoffs spread through the population, while "unfit" labels go extinct.
  4. Nash Equilibrium: The process terminates when it reaches a Nash Equilibrium, representing a consistent labeling where no player can improve their payoff by unilaterally changing their label.

Initialization and Priors

While the game can begin with a uniform distribution, the authors found that initializing target strategies using "pseudo-labels" from a simple Logistic Regression (LR) classifier significantly boosts performance. This "prior knowledge" provides a starting point that the game then refines through local geometric consistency.

Figure 3: Evolution of the strategy distribution (soft labels) for a target instance over iterations, converging toward a single class (Bike).

Experiments and Results

The researchers evaluated GTG on two standard benchmarks: Office-31 and Office-Caltech 10, using both shallow (SURF) and deep (ResNet-50) features.

Key Findings

  • Performance: GTG consistently outperformed traditional shallow methods like CORAL and Subspace Alignment by 2-4%. When paired with deep features and LR priors (GTDA+LR), it achieved an average accuracy of 83.4% on Office-31, rivaling complex end-to-end deep models like Joint Adaptation Networks (JAN, 84.6%).
  • Soft Labels: Unlike hard classifiers, GTG produces soft labels (probability distributions), naturally quantifying uncertainty during the adaptation process.
  • Stability: The method proved more stable across diverse adaptation tasks (e.g., DSLR → Amazon) compared to other graph-based techniques like Label Propagation.

Conclusion

Graph Transduction Games provide a robust, theoretically grounded framework for UDA. By framing consistency as a Nash Equilibrium, the method achieves competitive results without intensive hyperparameter tuning. Future work will explore larger-scale datasets and extensions to semi-supervised scenarios where limited target labels are available.

Summary updated

Abstract

Unsupervised domain adaptation (UDA) amounts to assigning class labels to the unlabeled instances of a dataset from a target domain, using labeled instances of a dataset from a related source domain. In this paper, we propose to cast this problem in a game-theoretic setting as a non-cooperative game and introduce a fully automatized iterative algorithm for UDA based on graph transduction games (GTG). The main advantages of this approach are its principled foundation, guaranteed termination of the iterative algorithms to a Nash equilibrium (which corresponds to a consistent labeling condition) and soft labels quantifying the uncertainty of the label assignment process. We also investigate the beneficial effect of using pseudo-labels from linear classifiers to initialize the iterative process. The performance of the resulting methods is assessed on publicly available object recognition benchmark datasets involving both shallow and deep features. Results of experiments demonstrate the suitability of the proposed game-theoretic approach for solving UDA tasks.
BibTeX
@inproceedings{vascon2019unsupervised,
  author = {Sebastiano Vascon and Sinem Aslan and Alessandro Torcinovich and Twan van Laarhoven and Elena Marchiori and Marcello Pelillo},
  title = {{Unsupervised Domain Adaptation using Graph Transduction Games}},
  booktitle = {IJCNN},
  year = {2019},
  url = {https://openreview.net/forum?id=z9PR2BrOcS3},
}
Figure