Tensor factorization has become a popular method for learning from multi-relational data. In this context, the rank of the factorization is an important parameter that determines runtime as well as generalization ability. To identify conditions under which factorization is an efficient approach for learning from relational data,we derive upper and lower bounds on the rank required to recover adjacency tensors.Based on our findings, we propose a novel additive tensor factorization modelto learn from latent and observable patterns on multi-relational data and present

a scalable algorithm for computing the factorization. We show experimentallyboth that the proposed additive model does improve the predictive performanceover pure latent variable methods and that it also reduces the required rank — andtherefore runtime and memory complexity — significantly.