TL;DR
This paper introduces the Relational Gaussian Process (RGP), a framework that combines traditional feature-based learning with relational "link" data (like citations or protein interactions). By treating observed relationships as a likelihood constraint, the authors derive a data-dependent covariance function that "warps" the kernel to respect the global geometry of the data. This significantly boosts performance in semi-supervised tasks where labels are scarce.
The Challenge of Relational Data
In many real-world domains, data isn't just a collection of independent points; it forms a network. For example, web pages have hyperlinks, and research papers have citations. Standard machine learning often treats these as "flat" datasets, looking only at the attributes of individual instances (e.g., the words on a page).
While graph-based methods exist to handle these relationships, they are often transductive (meaning they can't easily handle new, unseen points) or lack a principled probabilistic foundation. The authors aim to bridge this gap by integrating relational information directly into the Gaussian Process (GP) framework, allowing for non-parametric Bayesian inference that accounts for both what an object is (its features) and who it knows (its links).
The Relational Gaussian Process (RGP)
The core innovation is the Relational Gaussian Process. Here is how the methodology unfolds:
- Likelihood for Linkages: The authors propose a novel likelihood function for undirected edges. If two points $x_i$ and $x_j$ are "positively tied" (linked), the model enforces that their latent variables $f_{x_i}$ and $f_{x_j}$ should have the same sign. They add Gaussian noise to this "ideal" case to handle real-world uncertainty.
- Approximate Inference via EP: The resulting posterior distribution is non-Gaussian and multi-modal (creating a "saddle point" at the origin). To make this tractable, they use Expectation Propagation (EP) to approximate the posterior as a zero-mean Gaussian.
- Data-Dependent Covariance: The EP process yields a modified kernel $\tilde{K}(x, z)$ that incorporates the graph structure. Essentially, the prior belief about how two points correlate is updated based on the network of links, effectively "warping" the feature space.
- Semi-Supervised Learning: For datasets without explicit links, they construct a K-nearest neighbor (KNN) graph from the input attributes. This graph acts as a proxy for the data manifold, and the RGP uses it to "spread" information from a few labeled points to many unlabeled ones.
Key Insights
- The "Warped" Kernel: Points that are nearby on the graph (even if far apart in raw feature space) become more highly correlated in the posterior.
- Bayesian Model Selection: Unlike many graph-based methods (like Laplacian SVMs) that require manual tuning of regularization parameters, the RGP allows for hyperparameter tuning by maximizing the joint evidence of labels and links.
- Inductive Power: Because the RGP results in a functional form for the covariance, it is naturally inductive. It can provide probabilistic predictions for unseen test points, a major advantage over purely transductive graph methods.
- Symmetry in Correlation: The model captures that reciprocal relations update the correlation between examples but do not change the individual mean (which remains at zero until labels are introduced).
Experimental Results
The authors evaluated the RGP on four distinct types of data: synthetic data, WebKB (university web pages), PCMAC (newsgroup posts), and USPS (handwritten digits).
Geometry Awareness on Synthetic Data
On a synthetic 1D Gaussian mixture model, the RGP successfully shifted the decision boundary to low-density regions of the data distribution, a hallmark of effective semi-supervised learning.
Superiority in Label Scarcity
On the PCMAC and USPS datasets, the RGP significantly outperformed standard Gaussian Process Classification (GPC) and Laplacian SVMs (LapSVM), particularly when labeled data was extremely scarce (less than 5% of the training set).
WebKB Performance
In the "Student vs. Not" and "Other vs. Not" classification tasks, RGP consistently yielded higher Area Under Curve (AUC) scores than standard GPC, proving that hyperlinks provide vital signal that text alone misses.
Limitations and Future Work
- Undirected Only: The current formulation focuses on undirected, reciprocal relations. The authors note that directionality (e.g., Page A links to Page B, but not vice versa) is an important aspect of many datasets not yet captured.
- Computational Complexity: While EP is efficient, the matrix inversions involved in GP scale with the number of instances ($O(n^3)$), which could be a bottleneck for massive graphs.
- Inference Stability: The authors mention that EP convergence isn't guaranteed and suggest investigating Expectation Consistent (EC) inference as a more robust alternative in the future.
- Weighted Edges: The paper primarily deals with unweighted edges; extending this to weighted relational data is left for future research.
Summary updated