Faithful Relational Reasoning with Region-based Embeddings: Expressivity of Convex Coordinate-wise Models

Embedding methods are among the most efficient approaches for learning to reason about relational knowledge. In this paper, we focus on the framework of region-based embeddings, where relations are encoded as geometric regions. The spatial arrangement of these regions allows such models to capture symbolic rules, enabling them to simulate some forms of symbolic reasoning. A crucial consideration is how the regions are parameterized, as this affects which rule bases can be captured. Most methods use convex regions which are defined in terms of coordinate-wise comparisons. This makes them highly efficient, but the implications of this choice have thus far remained unclear. We present a series of results that shed light on this issue, showing that convex coordinate-wise models indeed have important limitations, while at the same time showing that there is still room for pushing the expressivity of existing coordinate-wise models.

Knowledge graphs (KGs) encode relationships between entities (e.g. people, places and companies). For instance, a KG could encode that Paris is the capital of France and that Albert Einstein invented the theory of general relativity. This paper builds on geometric approaches that represent KG entities as vectors, such that the spatial relationship between two vectors encodes the semantic relationships between the corresponding entities. The motivation for learning such representations is that they often reveal information that can be plausibly inferred from the KG with low computational effort. In this paper, we show theoretical limitations of a class of geometric approaches in which relationships are modelled as “decomposable” convex regions. We also complement our study with an empirical analysis, which shows that the performance of current methods remains below their theoretical upper bound, meaning that there is still clear scope for improving them.