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 of Link Prediction
The challenge in predicting the existence or strength of relationships is twofold:
- 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.
- 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.
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%.
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