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

Victor Charpenay, Steven Schockaert
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:13023-13065, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-charpenay26a, title = {Faithful Relational Reasoning with Region-based Embeddings: Expressivity of Convex Coordinate-wise Models}, author = {Charpenay, Victor and Schockaert, Steven}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {13023--13065}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/charpenay26a/charpenay26a.pdf}, url = {https://proceedings.mlr.press/v306/charpenay26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Faithful Relational Reasoning with Region-based Embeddings: Expressivity of Convex Coordinate-wise Models %A Victor Charpenay %A Steven Schockaert %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-charpenay26a %I PMLR %P 13023--13065 %U https://proceedings.mlr.press/v306/charpenay26a.html %V 306 %X 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.
APA
Charpenay, V. & Schockaert, S.. (2026). Faithful Relational Reasoning with Region-based Embeddings: Expressivity of Convex Coordinate-wise Models. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:13023-13065 Available from https://proceedings.mlr.press/v306/charpenay26a.html.

Related Material