Stochastic Relational Models for Discriminative Link Prediction

Kai Yu, Wei Chu, Shipeng Yu, Volker Tresp, Zhao XuNeurIPS 2006 · OpenReview

Introduction

Most traditional machine learning models assume data is "flat"—meaning each data point is an independent vector of attributes. However, the real world is inherently relational: users rate movies, proteins interact with each other, and webpages link to one another.

This paper introduces Stochastic Relational Models (SRM), a framework that uses Gaussian Processes (GPs) to predict relationships (links) between entities. By modeling links as a "tensor interaction" of multiple GPs, the authors create a powerful discriminative model that outperforms traditional matrix factorization while remaining computationally feasible for medium-sized relational datasets.

The challenge in predicting the existence or strength of relationships is twofold:

  1. Structural Dependency: A user’s preference for a movie isn't just about their age or the movie's genre; it depends heavily on how similar users liked similar movies.
  2. Scalability: The number of potential links grows quadratically with the number of entities. Standard "Tensor Gaussian Processes" (TGP) provide a mathematically sound way to model these dependencies but suffer from a staggering $O(N^3M^3)$ computational complexity (where $N$ and $M$ are the number of entities in each set), making them unusable for even small datasets.

Methods: Stochastic Relational Processes

To approximate the ideal but slow TGP, the authors propose Stochastic Relational Processes (SRP).

The Key Innovation: Tensor Interaction

Instead of treating a link as a single GP output, SRM models the latent relational function $t(u, v)$ as a sum of products of independent GPs: $$t(u, v) = \frac{1}{\sqrt{d}} \sum_{k=1}^{d} f_k(u)g_k(v)$$ Where $f_k$ are GPs acting on the first set of entities (e.g., users) and $g_k$ are GPs acting on the second (e.g., movies).

This "constructive" definition reduces complexity from $O(N^3M^3)$ to $O(d(N^3 + M^3))$. While still cubic, it decouples the two entity sets, making it significantly more scalable. Furthermore, it is highly flexible, capable of handling binary classification (link existence), regression (link strength/rating), and even "one-class" problems (like web hyperlinks where only positive links are observed).

The model uses an EM-like algorithm to adapt the GP kernels. This means the model can "learn" the similarity between entities based purely on the observed links, even if no explicit entity attributes are provided.

Key Insights and Structural Discovery

In SRM, information is "messaged" through the entire relational network. By maximizing the marginalized likelihood, the dependency structure of the links informs the dependency structure (kernels) of the entities.

Unlike many Probabilistic Relational Models (PRMs) that try to model the entire joint distribution of attributes and links, SRM is discriminative. It focuses strictly on the conditional model of links, which typically leads to better predictive accuracy.

One of the most striking capabilities of SRM is that it can learn informative kernels purely from link data. If two users consistently rate movies similarly, the model learns they are "close" in the GP kernel space, effectively discovering hidden structures.

Experimental Results

The authors evaluated SRM on both synthetic data and real-world benchmarks, demonstrating strong performance in both accuracy and structural recovery.

Structural Recovery on Synthetic Data: In a controlled environment with 20 "user" entities and 30 "movie" entities designed with hidden cluster structures, SRM successfully recovered the underlying relational geometry. Qualitative results showed that the learned kernels effectively captured the block-cluster structures of the entities.

Learned structural recovery on synthetic data

Collaborative Filtering on EachMovie: The model was tested on a subset of the EachMovie dataset (1,000 users, 1,623 movies, ~63,000 ratings). SRM significantly outperformed Maximum-Margin Matrix Factorization (MMMF), reducing the prediction error by over 12%.

Comparison of prediction error between MMMF and SRM

On the synthetic classification task, SRM also achieved a superior classification rate of up to 0.965, beating MMMF's 0.906.

Limitations and Future Work

While SRM represents a significant step forward, several challenges remain:

  • The "Big Data" Challenge: Even with the SRP approximation, $O(N^3)$ is still too slow for massive datasets like the full Netflix prize (480,000 users). Further sparsification or approximation techniques are needed.
  • Multi-way Relations: The current model focuses on pairwise links. Extending this to ternary or higher-order relations (e.g., User A bought Product B at Store C) is a logical next step.
  • Joint Tasks: The authors suggest that SRM could be extended to solve entity classification and link prediction simultaneously, allowing the two tasks to mutually inform each other.

Summary updated

Abstract

We introduce a Gaussian process (GP) framework, stochastic relational models (SRM), for learning social, physical, and other relational phenomena where interactions between entities are observed. The key idea is to model the stochastic structure of entity relationships (i.e., links) via a tensor interaction of multiple GPs, each defined on one type of entities. These models in fact define a set of nonparametric priors on infinite dimensional tensor matrices, where each element represents a relationship between a tuple of entities. By maximizing the marginalized likelihood, information is exchanged between the participating GPs through the entire relational network, so that the dependency structure of links is messaged to the dependency of entities, reflected by the adapted GP kernels. The framework offers a discriminative approach to link prediction, namely, predicting the existences, strengths, or types of relationships based on the partially observed linkage network as well as the attributes of entities (if given). We discuss properties and variants of SRM and derive an efficient learning algorithm. Very encouraging experimental results are achieved on a toy problem and a user-movie preference link prediction task. In the end we discuss extensions of SRM to general relational learning tasks.
BibTeX
@inproceedings{yu2006stochastic,
  author = {Kai Yu and Wei Chu and Shipeng Yu and Volker Tresp and Zhao Xu},
  title = {{Stochastic Relational Models for Discriminative Link Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=B1-uOuWd-r},
}
Figure