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.
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.
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