Relational Learning

• Focus on dyadic multi-relational data, i.e. (subject, predicate, object) triples
• Important relational learning tasks include
• Link Prediction: Prediction of relationships between entities
• Collective Classification: Classification of entities based on their relationships
• Link-Based Clustering: Clustering of entities based on their relationships
• Entity Resolution: Deduplication of entities

Why Tensor Factorization?

• Problem: Existing relational learning methods
  • do not scale (easily) to large data
  • often require extensive prior information about the problem
  • can be complex and difficult to implement
• Tensor factorization in general:
  • Modeling simplicity: Multi-relational data has an efficient tensor represenation
  • No structure learning: Tensor factorization does not require structure learning or extensive prior knowledge
  • Weak collective learning: Most tensor factorizations show no or only a very reduced collective learning effect or show unreasonable constraints
• Our approach:
  • Strong collective learning via unique latent representation of entities
  • $\Rightarrow$ State-of-the-art results on benchmark data
  • High scalability as algorithm scales linearly with the data size

Tensor Representation
of Relational Data

• RDF, or any other dyadic relationaldata, has a natural and efficient representation as a sparse third-order tensor
• Two modes refer to the entities, one mode to the relation types
  \begin{align} \Rightarrow & |Mode\ 1| = |Mode\ 2| = |Entities| = n\\ & |Mode\ 3| = |Predicates| = m \end{align}
• We also require that the ordering of the entities on both modes is identical

RESCAL

• $\color{orangered}{A} \in \R^{n \times r}$ represents the entity-latent-component space
• $\color{orangered}{R_k} \in \R^{r \times r}$ is an asymmetric matrix that specifies the interaction of the latent components for the $k$-th predicate
• $\color{orangered}{r}$ denotes the number of latent components of the factorization
• $\color{orangered}{\approx}$ means best approximation under some loss function
• To compute the factorization, we solve the optimization problem \[\min_{A,R_k} \sum_k \text{loss}(X_k; A_{\vphantom{k}} R_k A^T) + \lambda_A \|A\|^2 + \lambda_{\ten{R}} \|\ten{R}\|^2 \]

Probabilistic Interpretation

Link Prediction using RESCAL

• Basic procedure of link prediction with RESCAL
  • Compute "rank-reduced" factorization ($\triangleq$ latent-variable representations)
  • Entries after reconstruction (i.e. $\pred{x}_{ijk} = \re{i}{j}{k}$) can be regarded as confidence values of the model that the corresponding triple exists
• Allows for very fast prediction of unknown triples, since it is equivalent to simple matrix-vector products

Similarity of Entities in RESCAL

• $A$ can be regarded as an embedding of the entities into a vector space representation
• Similarity of entities in the latent-space $A$ corresponds to similarity of entities in the relational domain
• $\Rightarrow$ Any feature-based machine-learning method (e.g. for clustering, classification etc.) can instantly be applied to $A$
• Due to the collective learning effect of RESCAL, the latent-variable representation also contains information about distant relations

Collective Learning - U.S. Presidents

• Data on party memberships of U.S. presidents extracted from DBpedia
• Task: Predict party-membership for persons in dataset (link prediction)
• Relations: partyOf, presidentOf, vicePresidentOf
• Experimental setting: 10-fold cross-validation over all persons
• Evaluation measure: Area under precision-recall curve (AUC-PR)

Link Prediction Benchmarks

• RESCAL shows state-of-the-art results, compared to MLN, IRM, BCTF
• RESCAL shows very fast training times, i.e. under one minute on these datasets

Learning Taxonomies on IIMB Benchmark

• Taxonomies are an integral part of ontologies, consist of
  • a list of concepts
  • a concept hierarchy
  • an assignment of entities to concepts
• Task: Unsupervised taxonomy learning via hierarchical clustering of entities
• Method: Hierarchical clustering on $A$ using the OPTICS method
• Data: Instance matching benchmark from movie domain, consisting of $\approx$ 1400 entities, organized in 80 concepts
  • Top Level Concepts: Film, Language, Budget, Creature, Location
  • The concepts Creature, Film and Location are again subdivided into concepts like Person, Character, Country or Action Movie

RESCAL-ALS Algorithm

RESCAL-ALS is an alternating-least squares algorithm to compute the RESCAL factorization, i.e. it optimizes

Scalability Experiments

Factorizing YAGO2 (core)

• Scalability allowed us to factorize the YAGO 2 core ontology with approximately
  • 3 million entities
  • 38 relations
  • 41 million known facts
• Runtime for a rank-20 factorization on commodity hardware ~3 hours
• Successfully predicted typeOf relationships for various higher-level classes in the ontology

Concluding Remarks & Future Work

• RESCAL offers a flexible and scalable way to machine learning on multi-relational data in the size of complete knowledge bases
• RESCAL shows state-of-the-art results in link prediction and entity resolution due to a strong collective learning effect
• Scalability and state-of-the-art relational learning combined within a single model
• Future work with regard to tensor factorizations for structured and relational data
  • Scalable Logistic Model
  • Handling scale-free nature of many multigraphs $\rightarrow$ Regularization
  • Reduce cubic complexity for $r$ by including prior knowledge in the factorization

Code & Tools

• Python and Matlab code for RESCAL available from my website and Github

  
    from rescal import rescal
    
    # compute rank-20 factorization of tensor X
    A, R = rescal(X, 20, init='nvecs')
  				

• Easy to use tools to convert from N-Triples to Python and Matlab tensors available from my website and Github

References

References

References

Linked Data & Semantic Web