TL;DR
This paper introduces TRACTOR, a novel framework that unifies probabilistic databases (PDBs) with relational embedding models. TRACTOR allows for complex querying of incomplete and uncertain data by providing a principled probabilistic semantics for relational embeddings, enabling efficient and tractable query answering where previous methods struggled.
What Problem Does This Paper Address?
Traditional relational databases excel at structured data querying but falter when faced with uncertainty and incompleteness. Machine learning techniques, particularly relational embedding models, are adept at handling such data and predicting missing information (link prediction). However, these embedding models often lack a clear probabilistic foundation, making it difficult to perform complex probabilistic reasoning or answer queries beyond simple link prediction. On the other hand, probabilistic databases offer a robust probabilistic semantics but struggle with efficiently populating data and can face tractability issues with certain complex queries. This paper bridges this gap by developing a unified framework that leverages the strengths of both approaches.
Methods
The core innovation is the development of TRACTOR, a relational embedding model designed to be a "tractable probabilistic database." Instead of treating relational embeddings as a black box, TRACTOR explicitly incorporates their underlying factorization assumptions into the probabilistic framework.
- Probabilistic Database Formalism: The paper starts by defining a probabilistic database (PDB) model and its query evaluation mechanisms, particularly focusing on Union of Conjunctive Queries (UCQs).
- Relational Embeddings as PDBs: The initial attempt to interpret relational embeddings as PDBs involves mapping their scoring functions to probabilities and assuming independence between triples. This approach, however, leads to problematic independence assumptions and tractability issues.
- TRACTOR's Factorization: TRACTOR addresses this by rewriting binary relations into unary relations based on latent entity and relation variables. This factorization, inspired by techniques in probabilistic logic, allows for a probabilistic interpretation where the independence assumptions are shifted to these latent variables.
- Mixture Model: To increase expressiveness, TRACTOR employs a mixture model, combining multiple simple factorization models. This allows it to approximate more complex distributions.
- Efficient Query Evaluation: TRACTOR leverages the PDB query evaluation algorithms (specifically Algorithm 1) to efficiently answer queries. A key theoretical result is that by transforming queries to only involve unary relations, they become "safe" and efficiently computable, even those that would be #P-hard in a standard PDB.
Datasets
The paper uses the "bio" dataset, which consists of knowledge from public biomedical databases. This dataset includes nodes representing drugs, diseases, proteins, side effects, and biological processes, with 42 different relations and millions of edges. The authors followed the query generation procedure from Hamilton et al. [20] to create evaluation queries, ensuring that test queries rely on edges not present in the training data.
Key Insights and Ideas
- Bridging the Semantic Gap: The paper successfully bridges the semantic gap between the predictive power of relational embeddings and the rigorous probabilistic reasoning of PDBs.
- Factorization is Key: Explicitly incorporating the factorization assumptions of relational embeddings into the PDB framework is crucial for achieving tractability and avoiding problematic independence assumptions.
- Latent Variables for Tractability: Shifting independence assumptions from observed triples to latent entity and relation variables is the key to making complex queries efficiently computable.
- Mixtures for Expressiveness: Using a mixture of simple factored models allows TRACTOR to achieve a balance between expressiveness and computational efficiency.
- TRACTOR as a General Probabilistic Model: TRACTOR is not just for link prediction; it represents a full probability distribution, from which query predictions naturally emerge.
Key Results
- Tractable Query Answering: TRACTOR can efficiently answer a wide range of queries, including those that are #P-hard in standard tuple-independent PDBs, by transforming them into a form amenable to efficient inference.
- Competitive Link Prediction: TRACTOR (and its variants) performs competitively with established relational embedding models like DistMult on link prediction tasks, demonstrating its effectiveness as a general model.
- Empirical Performance: On the bio dataset, TRACTOR achieved strong AUC and APR scores, outperforming some baselines and being competitive with others, despite its more general probabilistic semantics. For example, TRACTOR achieved an AUC of 82.8 and APR of 86.3.
Limitations and Future Work
- Symmetric Relations: Similar to models like DistMult and TransE, TRACTOR currently struggles with asymmetric relations. The authors suggest extending it by using complex numbers for embeddings or inverse relations.
- Probabilistic Training: TRACTOR is currently trained using standard relational embedding techniques (max-margin with negative sampling), not directly from its PDB semantics. An open question is whether it can be trained using a likelihood derived from its PDB semantics.
- Model Complexity: TRACTOR uses simple models as building blocks. Future work could explore increasing the complexity of these individual models (e.g., using disjunctions of conjunctions) to potentially improve accuracy.
- Beyond Query Probability: The paper focuses on computing the probability of a query. Future directions include exploring other types of queries, such as finding the most probable world given a PDB or identifying the most probable explanations for a query.
Summary updated