A Comparative Study of Pairwise Learning Methods Based on Kernel Ridge Regression

Michiel Stock, Tapio Pahikkala, Antti Airola, Bernard De Baets, Willem Waegeman

Abstract

This paper provides a theoretical unification of popular kernel-based methods for pairwise learning, such as predicting drug-target interactions or user-item recommendations. By mathematically framing independent-task, two-step, and linear filtering methods as special cases of Kronecker Kernel Ridge Regression (KRR), the authors demonstrate that these methods share fundamental properties like universality and statistical consistency. This work explains the empirical success of computationally efficient shortcuts and establishes a rigorous foundation for dyadic prediction.

Introduction: The Pairwise Learning Problem

In machine learning, many problems involve predicting a relationship or label for a pair of objects, such as a user and a movie or a drug and a protein. This is known as pairwise learning or dyadic prediction. The difficulty of these tasks depends heavily on whether the objects in the pair were seen during training. The authors categorize these scenarios into four distinct settings:

  • Setting A (Matrix Completion): Both objects are known from training, but their specific pairing is unobserved.
  • Setting B & C (Multi-task/Cold-start): One object is known, but the other is entirely new.
  • Setting D (Zero-shot): Both objects are entirely new to the model.
The four settings of pairwise learning based on the presence of objects in the training sample.

While kernel methods are effective across these settings, their theoretical relationships—specifically how different algorithmic shortcuts relate to one another—have been underexplored. This paper bridges that gap by unifying four common KRR-based pairwise methods.

Methods and Theoretical Unification

The authors analyze four existing methods, focusing on scenarios with "complete" training datasets (where the training matrix has no missing labels):

  1. Independent-task KRR: A baseline that treats every target as a separate regression problem, ignoring relationships between tasks.
  2. Kronecker KRR: A powerful method using a pairwise kernel (the Kronecker product of instance and task kernels) to learn joint representations.
  3. Two-step KRR (TS KRR): A computationally efficient shortcut that chains two standard KRRs together—first predicting across instances, then across tasks.
  4. Linear Matrix Filtering: A feature-free method that predicts missing values using a weighted average of row, column, and global averages.
Theoretical relationships and equivalences between different KRR-based pairwise learning methods.

The core novelty is a series of mathematical proofs demonstrating that methods 1, 3, and 4 are actually special cases of Kronecker KRR under specific conditions or kernel choices. For example, the "Linear Filter" is shown to be equivalent to Kronecker KRR when using "smoother kernels" that blend identity and all-ones matrices.

Key Insights

Two-step KRR as a Valid Proxy

Two-step KRR is favored in practice because it is significantly faster than standard Kronecker KRR. Instead of scaling with the number of pairs, it scales with the number of individual objects $O(m^3 + q^3)$. The authors prove that for Setting A (matrix completion) and Setting D (zero-shot learning), Two-step KRR is mathematically equivalent to Kronecker KRR with a specific pairwise kernel.

Decoupled Regularization

Framing Two-step KRR as a spectral filter reveals a major advantage: it allows for different regularization parameters for instances ($\lambda_u$) and tasks ($\lambda_v$). This allows the model to account for different degrees of freedom required for users versus items, such as a book's global popularity versus a user's niche taste.

Universality and Consistency

The authors prove that the Kronecker product pairwise kernel is a "universal" kernel. Furthermore, they establish that Two-step KRR is statistically consistent, meaning that as more data is provided, the learned hypothesis is guaranteed to converge to the true underlying data-generating function.

Key Results

The paper's primary contributions are formal proofs establishing these connections:

  • Theorem 1: Proves Two-step KRR and Independent-task KRR yield identical predictions for known training tasks when the task Gram matrix is full rank and task regularization is zero.
  • Theorems 2 & 3: Derives the exact closed-form pairwise kernel matrices that make Kronecker KRR identical to Two-step KRR for Setting A and Setting D.
  • Corollary 1: Establishes the convergence rate for Two-step KRR, proving the risk converges at a rate proportional to $O(\min(m, q)^{-\frac{\nu}{2\nu+1}})$.

Limitations and Future Work

The elegant algebraic equivalences and eigenvalue decomposition shortcuts rely on the assumption of "complete datasets." In cases of incomplete data, practitioners must use slower gradient-descent methods, where these exact equivalences become approximations. The authors suggest these mathematical foundations can serve as building blocks for understanding newer, more complex algorithms, such as deep zero-shot learning models.

Summary updated

Abstract

Many machine learning problems can be formulated as predicting labels for a pair of objects. Problems of that kind are often referred to as pairwise learning, dyadic prediction, or network inference problems. During the past decade, kernel methods have played a dominant role in pairwise learning. They still obtain a state-of-the-art predictive performance, but a theoretical analysis of their behavior has been underexplored in the machine learning literature. In this work we review and unify kernel-based algorithms that are commonly used in different pairwise learning settings, ranging from matrix filtering to zero-shot learning. To this end, we focus on closed-form efficient instantiations of Kronecker kernel ridge regression. We show that independent task kernel ridge regression, two-step kernel ridge regression, and a linear matrix filter arise naturally as a special case of Kronecker kernel ridge regression, implying that all these methods implicitly minimize a squared loss. In addition, we analyze universality, consistency, and spectral filtering properties. Our theoretical results provide valuable insights into assessing the advantages and limitations of existing pairwise learning methods.
BibTeX
@article{stock2018comparative,
  author = {Michiel Stock and Tapio Pahikkala and Antti Airola and Bernard De Baets and Willem Waegeman},
  title = {{A Comparative Study of Pairwise Learning Methods Based on Kernel Ridge Regression}},
  journal = {Neural Computation},
  year = {2018},
  doi = {10.1162/neco\_a\_01096},
}
Figure