Semantic Link Prediction through Probabilistic Description Logics

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

Introduction

Link prediction—the task of identifying likely future or missing connections between nodes in a network—is a cornerstone of social network analysis and bioinformatics. While traditional approaches rely heavily on graph topology (e.g., common neighbors), they often fail to capture the underlying "semantic" reasons why two entities might connect. This paper presents a framework that bridges this gap by integrating graph-based features with formal knowledge encoded in probabilistic description logics ($cr\mathcal{ALC}$). By modeling the inherent uncertainty of real-world relationships, the authors demonstrate how we can predict missing connections more accurately than by looking at network structure alone.

In many domains, such as academic collaboration, graph structure doesn't tell the whole story. Two researchers might not share any co-authors (no graph-based link), but they might teach the same course and publish in the same niche journal. This "semantic" information suggests a high potential for collaboration. The challenge is that semantic data is often incomplete or uncertain. One cannot say for certain they will collaborate; one can only say it is probable. This paper tackles how to formally model that uncertainty to improve prediction.

Methodology: $cr\mathcal{ALC}$ and Relational Bayesian Networks

The authors propose an algorithm that utilizes $cr\mathcal{ALC}$, a probabilistic extension of Description Logics (DL), to represent and reason with uncertain domain knowledge.

1. Probabilistic Ontology

Instead of rigid logical inclusions, $cr\mathcal{ALC}$ allows for "probabilistic inclusions," such as $P(Professor|Researcher) = 0.4$. This enables the system to reason about the likelihood of roles and concepts within a specific domain.

Probabilistic inclusions and concept definitions within the researcher domain ontology

2. Relational Bayesian Networks (RBNs)

To perform actual calculations, the ontology is transformed into a Relational Bayesian Network. This grounding process maps abstract concepts to specific individuals in the dataset, allowing the system to take specific "evidence" (e.g., Researcher A and Researcher B both work at the same institution) and output a probability for a specific link (e.g., sharePublication).

Grounding of the probabilistic ontology into a Relational Bayesian Network for specific individuals

3. The Prediction Algorithm

The system identifies pairs of unconnected nodes and gathers semantic evidence from the ontology. It then calculates the probability of a link. If the probability exceeds a certain threshold, a new connection is suggested.

Experimental Evaluation: The Lattes Platform

The authors evaluated their approach using an academic domain dataset from the Lattes Platform, a public repository of Brazilian researcher curricula.

  • Ontology Learning: Data from approximately 1,200 researchers was collected to learn the probabilistic weights of the ontology.
  • Collaboration Graph: The link prediction capabilities were tested on a network of 303 researchers, specifically focusing on "shared publication" as the primary link type.

Key Insights and Results

  • Beyond Topology: Semantic features (who the people are and what they do) act as a powerful proxy for missing links when the graph is sparse.
  • Evidence Accumulation: The paper illustrates that as more layers of evidence are added (e.g., not just shared institutions, but shared indirect collaborators), the probability of a link shifts. In one example, a link's probability jumped from 0.57 to 0.65 just by accounting for indirect connections, potentially pushing it over a decision threshold.
  • Hybrid Efficiency: While probabilistic inference is computationally expensive, the authors suggest using graph adjacency as a "filter" to identify promising nodes for deep semantic analysis, preventing the need to check every possible pair in a massive network.

Conclusion and Future Work

This research provides a compelling proof-of-concept for semantic link prediction. However, scalability remains a hurdle, as probabilistic inference in RBNs is computationally intensive for massive social networks. Future work will focus on automating the learning of probabilistic weights from raw data and conducting large-scale benchmarks against state-of-the-art machine learning predictors like Graph Neural Networks.

Summary updated

BibTeX
@inproceedings{revoredo2011semantic,
  author = {Kate Revoredo and José Eduardo Ochoa Luna and Fábio Gagliardi Cozman},
  title = {{Semantic Link Prediction through Probabilistic Description Logics}},
  booktitle = {URSW},
  year = {2011},
  url = {https://openreview.net/forum?id=uUaasVv0eU},
}
Figure