An Experimental Evaluation of a Scalable Probabilistic Description Logic Approach for Semantic Link Prediction

José Eduardo Ochoa Luna, Kate Revoredo, Fábio Gagliardi CozmanURSW 2012 · OpenReview

Abstract

Link prediction in complex networks often involves a trade-off between the richness of semantic modeling and computational scalability. This paper evaluates a novel approach using the probabilistic description logic CR$\mathcal{ALC}$ combined with a path-restricted inference strategy. By localizing evidence to target nodes and their connecting paths, the method achieves high predictive accuracy and millisecond-level performance on large-scale networks. Experimental results on the Lattes Platform dataset demonstrate that the CR$\mathcal{ALC}$ feature outperforms traditional topological and semantic baselines, scaling effectively to networks with up to one million nodes.

Introduction

Link prediction—the task of identifying likely future or missing connections between nodes—is a critical problem in network analysis, with applications ranging from social network analysis to academic collaboration discovery. Traditional methods typically rely on topological features (e.g., Katz index, Adamic-Adar) or basic semantic similarities. While useful, these features often fail to capture the nuanced, uncertain relationships inherent in structured domain knowledge.

Probabilistic description logics (PDLs) offer a powerful alternative by combining formal ontologies with probabilistic reasoning. However, the computational complexity of PDLs has historically limited their application to small, toy datasets. This study investigates a scalable inference strategy for CR$\mathcal{ALC}$ to bridge the gap between expressive logic and large-scale practical application.

Methodology

The authors build upon CR$\mathcal{ALC}$, a probabilistic description logic that extends standard ontologies with probabilistic inclusions (e.g., defining a specific probability that a 'Researcher' is a 'Professor'). To overcome the scalability limits of traditional Relational Bayesian Networks (RBNs), which typically require modeling the entire population, the authors introduce a path-restricted inference strategy.

Mapping of CR$\mathcal{ALC}$ concepts to a Relational Bayesian Network

As illustrated in Figure 1, the approach maps description logic concepts to an RBN structure. To predict a link between two specific nodes, the algorithm retrieves evidence only for those nodes and the individuals residing on the paths connecting them. This localization bypasses the memory constraints of global inference. The probabilistic ontology used for the experimental evaluation includes complex definitions for researchers, publications, and institutional relationships.

Probabilistic ontology definitions and inclusions for the Lattes dataset

The probability of a link—calculated via a lifted variational method—is then used as a primary numerical feature in a Logistic Regression classifier, alongside standard topological and semantic baselines.

Experimental Results

The approach was evaluated using the Lattes Platform dataset, a real-world repository of Brazilian scientific curricula. The study focused on a subset of ~1,100 researchers and 1,400 true co-authorship links.

Predictive Performance

The CR$\mathcal{ALC}$ feature proved to be the single most predictive element in the model:

  • Topological Baselines: 76.44% accuracy.
  • Semantic + Topological Features: 85.63% accuracy.
  • CR$\mathcal{ALC}$ Feature Alone: 87.72% accuracy.
  • Combined Model (All Features): 89.48% accuracy.

Scalability

The path-restricted inference strategy demonstrated exceptional efficiency. On the 1,100-node network, inference time averaged 135 milliseconds. More importantly, the method scaled gracefully to a simulated network of 1,000,000 nodes, requiring only 185 milliseconds. In contrast, standard propositionalized RBN methods failed due to out-of-memory errors on significantly smaller populations.

Conclusion

This research demonstrates that localizing evidence through path-restricted inference allows for efficient, high-quality probabilistic reasoning in large-scale networks. The integration of structured domain knowledge via CR$\mathcal{ALC}$ significantly enhances link prediction accuracy over traditional graph-based methods. Future work will focus on testing the generalizability of this approach across more diverse network domains and exploring automated methods for learning the underlying probabilistic ontologies.

Summary updated

BibTeX
@inproceedings{luna2012experimental,
  author = {José Eduardo Ochoa Luna and Kate Revoredo and Fábio Gagliardi Cozman},
  title = {{An Experimental Evaluation of a Scalable Probabilistic Description Logic Approach for Semantic Link Prediction}},
  booktitle = {URSW},
  year = {2012},
  url = {https://openreview.net/forum?id=qDVS7B4f8AT},
}
Figure