Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities

Tianbao Yang, Rong JinNeurIPS 2014 · OpenReview

TL;DR

This paper introduces a two-step algorithm to solve transductive pairwise classification—determining if two items belong to the same category using a noisy similarity matrix and a handful of known labels. By combining matrix completion with the spectral properties of the similarity matrix, the authors show they can accurately recover the full "label matrix" even when the initial similarity data is highly uncertain.

What Problem Does This Paper Address?

In many real-world tasks, we need to know if two objects are "the same": Are these two protein sequences from the same family? Are these two faces the same person? Does a link exist between two nodes in a social network?

Usually, we have two pieces of information:

  1. A Similarity Matrix: A noisy, "uncertain" set of scores (e.g., cosine similarity) between all pairs.
  2. A Few Ground-Truth Labels: A small, "certain" set of known relationships (e.g., "we know for sure these 10 pairs are the same class").

The challenge is that simply thresholding the similarity matrix (e.g., "if similarity > 0.8, they are the same") performs poorly because the similarity scores are often an imperfect reflection of the true categories. The authors aim to bridge this gap, "extracting certainty" (the true labels) from "uncertainty" (the similarity scores).

Methods

The authors propose a surprisingly simple two-step algorithm called TPCMC (Transductive Pairwise Classification by Matrix Completion):

  1. Sub-matrix Completion: They take the small subset of data for which some pairwise labels are known. They treat this as a matrix completion problem, using nuclear norm minimization to fill in the missing labels within this small "labeled" group. This works because the underlying label matrix is naturally low-rank (since there are only a few hidden classes).
  2. Full Matrix Reconstruction: They then "project" this completed sub-matrix onto the top eigen-vectors of the global similarity matrix. Essentially, they use the broad patterns found in the similarity matrix to "spread" the certain labels from the small sub-matrix to the entire dataset.

The beauty of this approach is that it doesn't require the similarity matrix to be perfect; it only requires that the similarity matrix's top "eigen-space" aligns well with the true class structure.

Matrix recovery process showing the transition from a noisy similarity matrix to a clean label matrix.

Datasets

The researchers evaluated their method on one synthetic dataset and three diverse real-world benchmarks:

  • Synthetic Data: 1,000 examples across 4 classes with added uniform noise.
  • Splice: A DNA sequence dataset used for recognizing gene boundaries.
  • Gisette: A handwritten digit recognition dataset (originally from a NIPS feature selection challenge).
  • Citeseer: A paper citation network used for link prediction.

Key Insights and Ideas

  • The Power of Low Rank: The core "aha" moment is that while the similarity matrix is messy, the true label matrix is mathematically "clean" (low-rank). By enforcing this low-rank structure during the completion step, they filter out noise.
  • Similarity as a Guide, Not a Rule: Unlike previous methods that might try to force the similarity matrix to match the labels, this method uses the similarity matrix's eigenvectors as a coordinate system to reconstruct the labels.
  • Coherence is Key: The paper provides a theoretical guarantee for success based on "matrix coherence." If the information in the eigenvectors is spread out (low coherence) rather than concentrated in a few rows, the reconstruction is much more stable.
  • Sample Efficiency: The authors show that they can recover the label matrix with a small error even when observing only a tiny fraction (e.g., 0.5% in synthetic tests) of the total pairwise labels.

Key Results

  • Superior Accuracy: TPCMC consistently outperformed state-of-the-art methods like Spectral Clustering (SC) and Spectral Kernel Learning (SKL) across all three real-world datasets.
  • Noise Reduction: In synthetic tests, the error of the estimated label matrix was reduced by 50% compared to the raw, noisy similarity matrix.
  • Reliability: The performance of TPCMC improved steadily as the number of labeled examples ($m$) increased, confirming the theoretical predictions that more data leads to better "coverage" of the underlying class space.
Performance comparison of TPCMC against SC and SKL.

Limitations and Future Work

  • Eigen-space Alignment: The method's success relies on the assumption that the top eigenvectors of the similarity matrix "cover" the column space of the true label matrix. If the similarity measure is completely irrelevant to the actual classes, the second step of the algorithm will fail.
  • Computational Complexity: While the steps are "simple," matrix completion and eigenvector decomposition can be computationally expensive for extremely large datasets (e.g., millions of nodes), suggesting a need for more scalable approximations in the future.
  • Symmetry Assumption: The current model assumes pairwise relationships are symmetric ($A$ is like $B$ means $B$ is like $A$). The authors note that this wouldn't apply directly to "preference learning," where relationships can be directional.

Summary updated

Abstract

In this work, we study the problem of transductive pairwise classification from pairwise similarities~\footnote{The pairwise similarities are usually derived from some side information instead of the underlying class labels.}. The goal of transductive pairwise classification from pairwise similarities is to infer the pairwise class relationships, to which we refer as pairwise labels, between all examples given a subset of class relationships for a small set of examples, to which we refer as labeled examples. We propose a very simple yet effective algorithm that consists of two simple steps: the first step is to complete the sub-matrix corresponding to the labeled examples and the second step is to reconstruct the label matrix from the completed sub-matrix and the provided similarity matrix. Our analysis exhibits that under several mild preconditions we can recover the label matrix with a small error, if the top eigen-space that corresponds to the largest eigenvalues of the similarity matrix covers well the column space of label matrix and is subject to a low coherence, and the number of observed pairwise labels is sufficiently enough. We demonstrate the effectiveness of the proposed algorithm by several experiments.
BibTeX
@inproceedings{yang2014extracting,
  author = {Tianbao Yang and Rong Jin},
  title = {{Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=ryZF-t-ObB},
}
Figure