On Approximate Reasoning Capabilities of Low-Rank Vector Spaces

In relational databases, relations between objects, represented by binary matrices or tensors, may be arbitrarily complex. In practice however, there are recurring relational patterns such as transitive, permutation and sequential relationships, that seem to have a regular structure not captured by the classical notion of matrix rank or tensor rank. In this paper, we show that factorizing the relational tensor using a logistic or hinge loss instead of the more standard squared loss is more appropriate because it can accurately model many common relations with a fixed-size embedding that depends sub-linearly on the number of entities in the knowledge base. We illustrate this fact empirically by being able to efficiently predict missing links in several synthetic and real-world experiments. Further, we provide theoretical justification for logistic loss by studying its connection to a complexity measure from the field of information complexity called the sign rank. Sign rank is a more appropriate complexity measure as it has a low value for transitive, permutation, or sequential relationships, while being large for uniformly sampled binary matrices/tensors with a high probability.