Steven Schockaert

KR Conference 2025 Conference Paper

Faithful Differentiable Reasoning with Reshuffled Region-based Embeddings

• Aleksandar Pavlovic
• Emanuel Sallinger
• Steven Schockaert

Knowledge graph (KG) embedding methods learn geometric representations of entities and relations to predict plausible missing knowledge. These representations are typically assumed to capture rule-like inference patterns. However, our theoretical understanding of which inference patterns can be captured remains limited. Ideally, KG embedding methods should be expressive enough such that for any set of rules, there exist relation embeddings that exactly capture these rules. This principle has been studied within the framework of region-based embeddings, but existing models are severely limited in the kinds of rule bases that can be captured. We argue that this stems from the fact that entity embeddings are only compared in a coordinate-wise fashion. As an alternative, we propose \modelName, a simple model based on ordering constraints that can faithfully capture a much larger class of rule bases than existing approaches. Most notably, RESHUFFLE can capture bounded inference w. r. t. arbitrary sets of closed path rules. The entity embeddings in our framework can be learned by a Graph Neural Network (GNN), which effectively acts as a differentiable rule base.

AIJ Journal 2025 Journal Article

RelBERT: Embedding relations with language models

• Asahi Ushio
• Jose Camacho-Collados
• Steven Schockaert

Many applications need access to background knowledge about how different concepts and entities are related. Although Knowledge Graphs (KG) and Large Language Models (LLM) can address this need to some extent, KGs are inevitably incomplete and their relational schema is often too coarse-grained, while LLMs are inefficient and difficult to control. As an alternative, we propose to extract relation embeddings from relatively small language models. In particular, we show that masked language models such as RoBERTa can be straightforwardly fine-tuned for this purpose, using only a small amount of training data. The resulting model, which we call RelBERT, captures relational similarity in a surprisingly fine-grained way, allowing us to set a new state-of-the-art in analogy benchmarks. Crucially, RelBERT is capable of modelling relations that go well beyond what the model has seen during training. For instance, we obtained strong results on relations between named entities with a model that was only trained on lexical relations between concepts, and we observed that RelBERT can recognise morphological analogies despite not being trained on such examples. Overall, we find that RelBERT significantly outperforms strategies based on prompting language models that are several orders of magnitude larger, including recent GPT-based models and open source models.

ICLR Conference 2025 Conference Paper

Systematic Relational Reasoning With Epistemic Graph Neural Networks

• Irtaza Khalid
• Steven Schockaert

Developing models that can learn to reason is a notoriously challenging problem. We focus on reasoning in relational domains, where the use of Graph Neural Networks (GNNs) seems like a natural choice. However, previous work has shown that regular GNNs lack the ability to systematically generalize from training examples on test graphs requiring longer inference chains, which fundamentally limits their reasoning abilities. A common solution relies on neuro-symbolic methods that systematically reason by learning rules, but their scalability is often limited and they tend to make unrealistically strong assumptions, e.g.\ that the answer can always be inferred from a single relational path. We propose the Epistemic GNN (EpiGNN), a novel parameter-efficient and scalable GNN architecture with an epistemic inductive bias for systematic reasoning. Node embeddings in EpiGNNs are treated as epistemic states, and message passing is implemented accordingly. We show that EpiGNNs achieve state-of-the-art results on link prediction tasks that require systematic reasoning. Furthermore, for inductive knowledge graph completion, EpiGNNs rival the performance of state-of-the-art specialized approaches. Finally, we introduce two new benchmarks that go beyond standard relational reasoning by requiring the aggregation of information from multiple paths. Here, existing neuro-symbolic approaches fail, yet EpiGNNs learn to reason accurately. Code and datasets are available at https://github.com/erg0dic/gnn-sg.

NeurIPS Conference 2025 Conference Paper

When No Paths Lead to Rome: Benchmarking Systematic Neural Relational Reasoning

• Anirban Das
• Muhammad Irtaza Khalid
• Rafael Peñaloza
• Steven Schockaert

Designing models that can learn to reason in a systematic way is an important and long-standing challenge. In recent years, a wide range of solutions have been proposed for the specific case of systematic relational reasoning, including Neuro-Symbolic approaches, variants of the Transformer architecture, and specialized Graph Neural Networks. However, existing benchmarks for systematic relational reasoning focus on an overly simplified setting, based on the assumption that reasoning can be reduced to composing relational paths. In fact, this assumption is hard-baked into the architecture of several recent models, leading to approaches that can perform well on existing benchmarks but are difficult to generalize to other settings. To support further progress in the field of systematic relational reasoning with neural networks, we introduce a new benchmark that adds several levels of difficulty, requiring models to go beyond path-based reasoning.

IJCAI Conference 2024 Conference Paper

Capturing Knowledge Graphs and Rules with Octagon Embeddings

• Victor Charpenay
• Steven Schockaert

Region based knowledge graph embeddings represent relations as geometric regions. This has the advantage that the rules which are captured by the model are made explicit, making it straightforward to incorporate prior knowledge and to inspect learned models. Unfortunately, existing approaches are severely restricted in their ability to model relational composition, and hence also their ability to model rules, thus failing to deliver on the main promise of region based models. With the aim of addressing these limitations, we investigate regions which are composed of axis-aligned octagons. Such octagons are particularly easy to work with, as intersections and compositions can be straightforwardly computed, while they are still sufficiently expressive to model arbitrary knowledge graphs. Among others, we also show that our octagon embeddings can properly capture a non-trivial class of rule bases. Finally, we show that our model achieves competitive experimental results.

AAAI Conference 2022 Conference Paper

Inferring Prototypes for Multi-Label Few-Shot Image Classification with Word Vector Guided Attention

• Kun Yan
• Chenbin Zhang
• Jun Hou
• Ping Wang
• Zied Bouraoui
• Shoaib Jameel
• Steven Schockaert

Multi-label few-shot image classification (ML-FSIC) is the task of assigning descriptive labels to previously unseen images, based on a small number of training examples. A key feature of the multi-label setting is that images often have multiple labels, which typically refer to different regions of the image. When estimating prototypes, in a metric-based setting, it is thus important to determine which regions are relevant for which labels, but the limited amount of training data makes this highly challenging. As a solution, in this paper, we propose to use word embeddings as a form of prior knowledge about the meaning of the labels. In particular, visual prototypes are obtained by aggregating the local feature maps of the support images, using an attention mechanism that relies on the label embeddings. As an important advantage, our model can infer prototypes for unseen labels without the need for fine-tuning any model parameters, which demonstrates its strong generalization abilities. Experiments on COCO and PASCAL VOC furthermore show that our model substantially improves the current state-of-the-art.

IJCAI Conference 2021 Conference Paper

A Description Logic for Analogical Reasoning

• Steven Schockaert
• Yazmin Ibanez-Garcia
• Victor Gutierrez-Basulto

Ontologies formalise how the concepts from a given domain are interrelated. Despite their clear potential as a backbone for explainable AI, existing ontologies tend to be highly incomplete, which acts as a significant barrier to their more widespread adoption. To mitigate this issue, we present a mechanism to infer plausible missing knowledge, which relies on reasoning by analogy. To the best of our knowledge, this is the first paper that studies analogical reasoning within the setting of description logic ontologies. After showing that the standard formalisation of analogical proportion has important limitations in this setting, we introduce an alternative semantics based on bijective mappings between sets of features. We then analyse the properties of analogies under the proposed semantics, and show among others how it enables two plausible inference patterns: rule translation and rule extrapolation.

IJCAI Conference 2021 Conference Paper

Modelling General Properties of Nouns by Selectively Averaging Contextualised Embeddings

• Na Li
• Zied Bouraoui
• Jose Camacho-Collados
• Luis Espinosa-Anke
• Qing Gu
• Steven Schockaert

While the success of pre-trained language models has largely eliminated the need for high-quality static word vectors in many NLP applications, static word vectors continue to play an important role in tasks where word meaning needs to be modelled in the absence of linguistic context. In this paper, we explore how the contextualised embeddings predicted by BERT can be used to produce high-quality word vectors for such domains, in particular related to knowledge base completion, where our focus is on capturing the semantic properties of nouns. We find that a simple strategy of averaging the contextualised embeddings of masked word mentions leads to vectors that outperform the static word vectors learned by BERT, as well as those from standard word embedding models, in property induction tasks. We notice in particular that masking target words is critical to achieve this strong performance, as the resulting vectors focus less on idiosyncratic properties and more on general semantic properties. Inspired by this view, we propose a filtering strategy which is aimed at removing the most idiosyncratic mention vectors, allowing us to obtain further performance gains in property induction.

ECAI Conference 2020 Conference Paper

Capturing Word Order in Averaging Based Sentence Embeddings

• Jae Hee Lee 0001
• José Camacho-Collados
• Luis Espinosa Anke
• Steven Schockaert

One of the most remarkable findings in the literature on sentence embeddings has been that simple word vector averaging can compete with state-of-the-art models in many tasks. While counter-intuitive, a convincing explanation has been provided by Arora et al. , who showed that the bag-of-words representation of a sentence can be recovered from its word vector average with almost perfect accuracy. Beyond word vector averaging, however, most sentence embedding models are essentially black boxes: while there is abundant empirical evidence about their strengths and weaknesses, it is not clear why and how different embedding strategies are able to capture particular properties of sentences. In this paper, we focus in particular on how sentence embedding models are able to capture word order. For instance, it seems intuitively puzzling that simple LSTM autoencoders are able to learn sentence vectors from which the original sentence can be reconstructed almost perfectly. With the aim of elucidating this phenomenon, we show that to capture word order, it is in fact sufficient to supplement standard word vector averages with averages of bigram and trigram vectors. To this end, we first study the problem of reconstructing bags-of-bigrams, focusing in particular on how suitable bigram vectors should be encoded. We then show that LSTMs are capable, in principle, of learning our proposed sentence embeddings. Empirically, we find that our embeddings outperform those learned by LSTM autoencoders on the task of sentence reconstruction, while needing almost no training data.

IJCAI Conference 2020 Conference Paper

Hierarchical Linear Disentanglement of Data-Driven Conceptual Spaces

• Rana Alshaikh
• Zied Bouraoui
• Steven Schockaert

Conceptual spaces are geometric meaning representations in which similar entities are represented by similar vectors. They are widely used in cognitive science, but there has been relatively little work on learning such representations from data. In particular, while standard representation learning methods can be used to induce vector space embeddings from text corpora, these differ from conceptual spaces in two crucial ways. First, the dimensions of a conceptual space correspond to salient semantic features, known as quality dimensions, whereas the dimensions of learned vector space embeddings typically lack any clear interpretation. This has been partially addressed in previous work, which has shown that it is possible to identify directions in learned vector spaces which capture semantic features. Second, conceptual spaces are normally organised into a set of domains, each of which is associated with a separate vector space. In contrast, learned embeddings represent all entities in a single vector space. Our hypothesis in this paper is that such single-space representations are sub-optimal for learning quality dimensions, due to the fact that semantic features are often only relevant to a subset of the entities. We show that this issue can be mitigated by identifying features in a hierarchical fashion. Intuitively, the top-level features split the vector space into different domains, making it possible to subsequently identify domain-specific quality dimensions.

AAAI Conference 2020 Conference Paper

Inducing Relational Knowledge from BERT

• Zied Bouraoui
• Jose Camacho-Collados
• Steven Schockaert

One of the most remarkable properties of word embeddings is the fact that they capture certain types of semantic and syntactic relationships. Recently, pre-trained language models such as BERT have achieved groundbreaking results across a wide range of Natural Language Processing tasks. However, it is unclear to what extent such models capture relational knowledge beyond what is already captured by standard word embeddings. To explore this question, we propose a methodology for distilling relational knowledge from a pre-trained language model. Starting from a few seed instances of a given relation, we first use a large text corpus to find sentences that are likely to express this relation. We then use a subset of these extracted sentences as templates. Finally, we fine-tune a language model to predict whether a given word pair is likely to be an instance of some relation, when given an instantiated template for that relation as input.

AAAI Conference 2020 Conference Paper

Modelling Semantic Categories Using Conceptual Neighborhood

• Zied Bouraoui
• Jose Camacho-Collados
• Luis Espinosa-Anke
• Steven Schockaert

While many methods for learning vector space embeddings have been proposed in the field of Natural Language Processing, these methods typically do not distinguish between categories and individuals. Intuitively, if individuals are represented as vectors, we can think of categories as (soft) regions in the embedding space. Unfortunately, meaningful regions can be difficult to estimate, especially since we often have few examples of individuals that belong to a given category. To address this issue, we rely on the fact that different categories are often highly interdependent. In particular, categories often have conceptual neighbors, which are disjoint from but closely related to the given category (e. g. fruit and vegetable). Our hypothesis is that more accurate category representations can be learned by relying on the assumption that the regions representing such conceptual neighbors should be adjacent in the embedding space. We propose a simple method for identifying conceptual neighbors and then show that incorporating these conceptual neighbors indeed leads to more accurate region based representations.

KR Conference 2020 Conference Paper

Plausible Reasoning about EL-Ontologies using Concept Interpolation

• Yazmín Ibáñez-García
• Víctor Gutiérrez-Basulto
• Steven Schockaert

Description logics (DLs) are standard knowledge representation languages for modelling ontologies, i. e. knowledge about concepts and the relations between them. Unfortunately, DL ontologies are difficult to learn from data and time-consuming to encode manually. As a result, ontologies for broad domains are almost inevitably incomplete. In recent years, several data-driven approaches have been proposed for automatically extending such ontologies. One family of methods rely on characterizations of concepts that are derived from text descriptions. While such characterizations do not capture ontological knowledge directly, they encode information about the similarity between different concepts that can be exploited for filling in the gaps in existing ontologies. To this end, several inductive inference mechanisms have already been proposed, but these have been defined and used in a heuristic fashion. In this paper, we instead propose an inductive inference mechanism which is based on a clear model-theoretic semantics, and can thus be tightly integrated with standard deductive reasoning. We particularly focus on interpolation, a powerful commonsense reasoning mechanism which is closely related to cognitive models of category-based induction. Apart from the formalization of the underlying semantics, as our main technical contribution we provide computational complexity bounds for reasoning in EL with this interpolation mechanism.

ECAI Conference 2020 Conference Paper

STRiKE: Rule-Driven Relational Learning Using Stratified k-Entailment

• Martin Svatos
• Steven Schockaert
• Jesse Davis
• Ondrej Kuzelka

Relational learning for knowledge base completion has been receiving considerable attention. Intuitively, rule-based strategies are clearly appealing, given their transparency and their ability to capture complex relational dependencies. In practice, however, pure rule-based strategies are currently not competitive with state-of-the-art methods, which is a reflection of the fact that (i) learning high-quality rules is challenging, and (ii) classical entailment is too brittle to cope with the noisy nature of the learned rules and the given knowledge base. In this paper, we introduce STRiKE, a new approach for relational learning in knowledge bases which addresses these concerns. Our contribution is three-fold. First, we introduce a new method for learning stratified rule bases from relational data. Second, to use these rules in a noise-tolerant way, we propose a strategy which extends k-entailment, a recently introduced cautious entailment relation, to stratified rule bases. Finally, we introduce an efficient algorithm for reasoning based on k-entailment.

IJCAI Conference 2019 Conference Paper

A Latent Variable Model for Learning Distributional Relation Vectors

• Jose Camacho-Collados
• Luis Espinosa-Anke
• Shoaib Jameel
• Steven Schockaert

Recently a number of unsupervised approaches have been proposed for learning vectors that capture the relationship between two words. Inspired by word embedding models, these approaches rely on co-occurrence statistics that are obtained from sentences in which the two target words appear. However, the number of such sentences is often quite small, and most of the words that occur in them are not relevant for characterizing the considered relationship. As a result, standard co-occurrence statistics typically lead to noisy relation vectors. To address this issue, we propose a latent variable model that aims to explicitly determine what words from the given sentences best characterize the relationship between the two target words. Relation vectors then correspond to the parameters of a simple unigram language model which is estimated from these words.

AAAI Conference 2019 Conference Paper

Automated Rule Base Completion as Bayesian Concept Induction

• Zied Bouraoui
• Steven Schockaert

Considerable attention has recently been devoted to the problem of automatically extending knowledge bases by applying some form of inductive reasoning. While the vast majority of existing work is centred around so-called knowledge graphs, in this paper we consider a setting where the input consists of a set of (existential) rules. To this end, we exploit a vector space representation of the considered concepts, which is partly induced from the rule base itself and partly from a pre-trained word embedding. Inspired by recent approaches to concept induction, we then model rule templates in this vector space embedding using Gaussian distributions. Unlike many existing approaches, we learn rules by directly exploiting regularities in the given rule base, and do not require that a database with concept and relation instances is given. As a result, our method can be applied to a wide variety of ontologies. We present experimental results that demonstrate the effectiveness of our method.

AAAI Conference 2019 Conference Paper

Word Embedding as Maximum A Posteriori Estimation

• Shoaib Jameel
• Zihao Fu
• Bei Shi
• Wai Lam
• Steven Schockaert

The GloVe word embedding model relies on solving a global optimization problem, which can be reformulated as a maximum likelihood estimation problem. In this paper, we propose to generalize this approach to word embedding by considering parametrized variants of the GloVe model and incorporating priors on these parameters. To demonstrate the usefulness of this approach, we consider a word embedding model in which each context word is associated with a corresponding variance, intuitively encoding how informative it is. Using our framework, we can then learn these variances together with the resulting word vectors in a unified way. We experimentally show that the resulting word embedding models outperform GloVe, as well as many popular alternatives.

KR Conference 2018 Conference Paper

From Knowledge Graph Embedding to Ontology Embedding: Region Based Representations of Relational Structures

• Víctor Gutiérrez Basulto
• Steven Schockaert

IJCAI Conference 2018 Conference Paper

Learning Conceptual Space Representations of Interrelated Concepts

• Zied Bouraoui
• Steven Schockaert

Several recently proposed methods aim to learn conceptual space representations from large text collections. These learned representations associate each object from a given domain of interest with a point in a high-dimensional Euclidean space, but they do not model the concepts from this domain, and can thus not directly be used for categorization and related cognitive tasks. A natural solution is to represent concepts as Gaussians, learned from the representations of their instances, but this can only be reliably done if sufficiently many instances are given, which is often not the case. In this paper, we introduce a Bayesian model which addresses this problem by constructing informative priors from background knowledge about how the concepts of interest are interrelated with each other. We show that this leads to substantially better predictions in a knowledge base completion task.

JAIR Journal 2018 Journal Article

Lifted Relational Neural Networks: Efficient Learning of Latent Relational Structures

• Gustav Sourek
• Vojtech Aschenbrenner
• Filip Zelezny
• Steven Schockaert
• Ondrej Kuzelka

We propose a method to combine the interpretability and expressive power of firstorder logic with the effectiveness of neural network learning. In particular, we introduce a lifted framework in which first-order rules are used to describe the structure of a given problem setting. These rules are then used as a template for constructing a number of neural networks, one for each training and testing example. As the different networks corresponding to different examples share their weights, these weights can be efficiently learned using stochastic gradient descent. Our framework provides a flexible way for implementing and combining a wide variety of modelling constructs. In particular, the use of first-order logic allows for a declarative specification of latent relational structures, which can then be efficiently discovered in a given data set using neural network learning. Experiments on 78 relational learning benchmarks clearly demonstrate the effectiveness of the framework.

UAI Conference 2018 Conference Paper

PAC-Reasoning in Relational Domains

• Ondrej Kuzelka
• Yuyi Wang 0001
• Jesse Davis
• Steven Schockaert

We consider the problem of predicting plausible missing facts in relational data, given a set of imperfect logical rules. In particular, our aim is to provide bounds on the (expected) number of incorrect inferences that are made in this way. Since for classical inference it is in general impossible to bound this number in a non-trivial way, we consider two inference relations that weaken, but remain close in spirit to classical inference.

IJCAI Conference 2018 Conference Paper

Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces

• Steven Schockaert
• Sanjiang Li

Conceptual spaces are a knowledge representation framework in which concepts are represented geometrically, using convex regions. Motivated by the fact that exact conceptual spaces are usually difficult to obtain, we study the problem of spatial reasoning about qualitative abstractions of such representations. In particular, we consider the problem of deciding whether an RCC8 network extended with constraints about betweenness can be realized using bounded and convex regions in a high-dimensional Euclidean space. After showing that this decision problem is PSPACE-hard in general, we introduce an important fragment for which deciding realizability is NP-complete.

AAAI Conference 2018 Conference Paper

Relational Marginal Problems: Theory and Estimation

• Ondřej Kuželka
• Yuyi Wang
• Jesse Davis
• Steven Schockaert

In the propositional setting, the marginal problem is to find a (maximum-entropy) distribution that has some given marginals. We study this problem in a relational setting and make the following contributions. First, we compare two different notions of relational marginals. Second, we show a duality between the resulting relational marginal problems and the maximum likelihood estimation of the parameters of relational models, which generalizes a well-known duality from the propositional setting. Third, by exploiting the relational marginal formulation, we present a statistically sound method to learn the parameters of relational models that will be applied in settings where the number of constants differs between the training and test data. Furthermore, based on a relational generalization of marginal polytopes, we characterize cases where the standard estimators based on feature’s number of true groundings needs to be adjusted and we quantitatively characterize the consequences of these adjustments. Fourth, we prove bounds on expected errors of the estimated parameters, which allows us to lower-bound, among other things, the effective sample size of relational training data.

AIJ Journal 2017 Journal Article

Generalized possibilistic logic: Foundations and applications to qualitative reasoning about uncertainty

• Didier Dubois
• Henri Prade
• Steven Schockaert

This paper introduces generalized possibilistic logic (GPL), a logic for epistemic reasoning based on possibility theory. Formulas in GPL correspond to propositional combinations of assertions such as “it is certain to degree λ that the propositional formula α is true”. As its name suggests, the logic generalizes possibilistic logic (PL), which at the syntactic level only allows conjunctions of the aforementioned type of assertions. At the semantic level, PL can only encode sets of epistemic states encompassed by a single least informed one, whereas GPL can encode any set of epistemic states. This feature makes GPL particularly suitable for reasoning about what an agent knows about the beliefs of another agent, e. g. , allowing the former to draw conclusions about what the other agent does not know. We introduce an axiomatization for GPL and show its soundness and completeness w. r. t. possibilistic semantics. Subsequently, we highlight the usefulness of GPL as a powerful unifying framework for various knowledge representation formalisms. Among others, we show how comparative uncertainty and ignorance can be modelled in GPL. We also exhibit a close connection between GPL and various existing formalisms, including possibilistic logic with partially ordered formulas, a logic of conditional assertions in the style of Kraus, Lehmann and Magidor, answer set programming and a fragment of the logic of minimal belief and negation as failure. Finally, we analyse the computational complexity of reasoning in GPL, identifying decision problems at the first, second, third and fourth level of the polynomial hierarchy.

IJCAI Conference 2017 Conference Paper

Induction of Interpretable Possibilistic Logic Theories from Relational Data

• Ondrej Kuzelka
• Jesse Davis
• Steven Schockaert

The field of statistical relational learning (SRL) is concerned with learning probabilistic models from relational data. Learned SRL models are typically represented using some kind of weighted logical formulas, which makes them considerably more interpretable than those obtained by e. g. neural networks. In practice, however, these models are often still difficult to interpret correctly, as they can contain many formulas that interact in non-trivial ways and weights do not always have an intuitive meaning. To address this, we propose a new SRL method which uses possibilistic logic to encode relational models. Learned models are then essentially stratified classical theories, which explicitly encode what can be derived with a given level of certainty. Compared to Markov Logic Networks (MLNs), our method is faster and produces considerably more interpretable models.

AAAI Conference 2017 Conference Paper

Inductive Reasoning about Ontologies Using Conceptual Spaces

• Zied Bouraoui
• Shoaib Jameel
• Steven Schockaert

Structured knowledge about concepts plays an increasingly important role in areas such as information retrieval. The available ontologies and knowledge graphs that encode such conceptual knowledge, however, are inevitably incomplete. This observation has led to a number of methods that aim to automatically complete existing knowledge bases. Unfortunately, most existing approaches rely on black box models, e. g. formulated as global optimization problems, which makes it difficult to support the underlying reasoning process with intuitive explanations. In this paper, we propose a new method for knowledge base completion, which uses interpretable conceptual space representations and an explicit model for inductive inference that is closer to human forms of commonsense reasoning. Moreover, by separating the task of representation learning from inductive reasoning, our method is easier to apply in a wider variety of contexts. Finally, unlike optimization based approaches, our method can naturally be applied in settings where various logical constraints between the extensions of concepts need to be taken into account.

KR Conference 2016 Conference Paper

Encoding Large RCC8 Scenarios Using Rectangular Pseudo-Solutions

• Zhiguo Long
• Steven Schockaert
• Sanjiang Li

Most approaches in the field of qualitative spatial reasoning (QSR) use constraint networks to encode spatial scenarios. The size of these networks is quadratic in the number of variables, which has severely limited the real-world application of QSR. In this paper, we propose another representation of spatial scenarios, in which each variable is associated with one or more rectangles. Instead of requiring these rectangles to define a solution of the corresponding constraint network, we construct sequences of rectangles that define partial solutions to progressively weaker constraint networks. We present experimental results that illustrate the effectiveness of this strategy.

ECAI Conference 2016 Conference Paper

Entity Embeddings with Conceptual Subspaces as a Basis for Plausible Reasoning

• Shoaib Jameel
• Steven Schockaert

Conceptual spaces are geometric representations of conceptual knowledge in which entities correspond to points, natural properties correspond to convex regions, and the dimensions of the space correspond to salient features. While conceptual spaces enable elegant models of various cognitive phenomena, the lack of automated methods for constructing such representations have so far limited their application in artificial intelligence. To address this issue, we propose a method which learns a vector-space embedding of entities from Wikipedia and constrains this embedding such that entities of the same semantic type are located in some lower-dimensional subspace. We experimentally demonstrate the usefulness of these subspaces as approximate conceptual space representations by showing, among others, that important features can be modelled as directions and that natural properties tend to correspond to convex regions.

ECAI Conference 2016 Conference Paper

Formalizing Commitment-Based Deals in Boolean Games

• Sofie De Clercq
• Steven Schockaert
• Ann Nowé
• Martine De Cock

Boolean games (BGs) are a strategic framework in which agents' goals are described using propositional logic. Despite the popularity of BGs, the problem of how agents can coordinate with others to (at least partially) achieve their goals has hardly received any attention. However, negotiation protocols that have been developed outside the setting of BGs can be adopted for this purpose, provided that we can formalize (i) how agents can make commitments and (ii) how deals between coalitions of agents can be identified given a set of active commitments. In this paper, we focus on these two aims. First, we show how agents can formulate commitments that are in accordance with their goals, and what it means for the commitments of an agent to be consistent. Second, we formalize deals in terms of coalitions who can achieve their goals without help from others. We show that verifying the consistency of a set of commitments of one agent is Π P2-complete while checking the existence of a deal in a set of mutual commitments is Σ p2

NeSy Conference 2016 Conference Paper

Inducing Symbolic Rules from Entity Embeddings using Auto-encoders

• Thomas Ager
• Ondrej Kuzelka
• Steven Schockaert

Vector space embeddings can be used as a tool for learning semantic relationships from unstructured text documents. Among others, earlier work has shown how in a vector space of entities (e. g. different movies) fine-grained semantic relationships can be identified with directions (e. g. more violent than). In this paper, we use stacked denoising auto-encoders to obtain a sequence of entity embeddings that model increasingly abstract relationships. After identifying directions that model salient properties of entities in each of these vector spaces, we induce symbolic rules that relate specific properties to more general ones. We provide illustrative examples to demonstrate the potential of this approach.

ECAI Conference 2016 Conference Paper

Interpretable Encoding of Densities Using Possibilistic Logic

• Ondrej Kuzelka
• Jesse Davis
• Steven Schockaert

Probability density estimation from data is a widely studied problem. Often, the primary goal is to faithfully mimic the underlying empirical density. Having an interpretable model that allows insight into why certain predictions were made is often of secondary importance. Using logic-based formalisms, such as Markov logic, can help with interpretability, but even in Markov logic it can be difficult to gain insight into a model's behavior due to interactions between the logical formulas used to specific the model. This paper explores an alternative approach to representing densities that makes use of possibilistic logic. Concretely, we propose a novel way to transform a learned density tree into a possibilistic logic theory. An advantage of our transformation is that it permits performing both MAP and, surprisingly, marginal inference, with the converted possibilistic logic theory. At the same time, we still retain the benefits conferred by using possibilistic logic, such as the ability to compact the theory and the interpretability of the model.

IJCAI Conference 2016 Conference Paper

Learning Possibilistic Logic Theories from Default Rules

• Ondřej Kuželka
• Jesse Davis
• Steven Schockaert

We introduce a setting for learning possibilistic logic theories from defaults of the form "if alpha then typically beta". We first analyse this problem from the point of view of machine learning theory, determining the VC dimension of possibilistic stratifications as well as the complexity of the associated learning problems, after which we present a heuristic learning algorithm that can easily scale to thousands of defaults. An important property of our approach is that it is inherently able to handle noisy and conflicting sets of defaults. Among others, this allows us to learn possibilistic logic theories from crowdsourced data and to approximate propositional Markov logic networks using heuristic MAP solvers. We present experimental results that demonstrate the effectiveness of this approach.

IJCAI Conference 2016 Conference Paper

Plausible Reasoning Based on Qualitative Entity Embeddings

• Steven Schockaert
• Shoaib Jameel

Formalizing and automating aspects of human plausible reasoning is an important challenge for the field of artificial intelligence. Practical advances, however, are hampered by the fact that most forms of plausible reasoning rely on background knowledge that is often not available in a structured form. In this paper, we first discuss how an important class of background knowledge can be induced from vector space representations that have been learned from (mostly) unstructured data. Subsequently, we advocate the use of qualitative abstractions of these vector spaces, as they are easier to obtain and manipulate, among others, while still supporting various forms of plausible reasoning.

UAI Conference 2015 Conference Paper

Encoding Markov logic networks in Possibilistic Logic

• Ondrej Kuzelka
• Jesse Davis
• Steven Schockaert

Markov logic uses weighted formulas to compactly encode a probability distribution over possible worlds. Despite the use of logical formulas, Markov logic networks (MLNs) can be difficult to interpret, due to the often counter-intuitive meaning of their weights. To address this issue, we propose a method to construct a possibilistic logic theory that exactly captures what can be derived from a given MLN using maximum a posteriori (MAP) inference. Unfortunately, the size of this theory is exponential in general. We therefore also propose two methods which can derive compact theories that still capture MAP inference, but only for specific types of evidence. These theories can be used, among others, to make explicit the hidden assumptions underlying an MLN or to explain the predictions it makes.

AIJ Journal 2015 Journal Article

Inducing semantic relations from conceptual spaces: A data-driven approach to plausible reasoning

• Joaquín Derrac
• Steven Schockaert

Commonsense reasoning patterns such as interpolation and a fortiori inference have proven useful for dealing with gaps in structured knowledge bases. An important difficulty in applying these reasoning patterns in practice is that they rely on fine-grained knowledge of how different concepts and entities are semantically related. In this paper, we show how the required semantic relations can be learned from a large collection of text documents. To this end, we first induce a conceptual space from the text documents, using multi-dimensional scaling. We then rely on the key insight that the required semantic relations correspond to qualitative spatial relations in this conceptual space. Among others, in an entirely unsupervised way, we identify salient directions in the conceptual space which correspond to interpretable relative properties such as ‘more fruity than’ (in a space of wines), resulting in a symbolic and interpretable representation of the conceptual space. To evaluate the quality of our semantic relations, we show how they can be exploited by a number of commonsense reasoning based classifiers. We experimentally show that these classifiers can outperform standard approaches, while being able to provide intuitive explanations of classification decisions. A number of crowdsourcing experiments provide further insights into the nature of the extracted semantic relations.

IJCAI Conference 2015 Conference Paper

Multilateral Negotiation in Boolean Games with Incomplete Information Using Generalized Possibilistic Logic

• Sofie De Clercq
• Steven Schockaert
• Ann Now
• eacute;
• Martine de Cock

Boolean games are a game-theoretic framework in which propositional logic is used to describe agents’ goals. In this paper we investigate how agents in Boolean games can reach an efficient and fair outcome through a simple negotiation protocol. We are particularly interested in settings where agents only have incomplete knowledge about the preferences of others. After explaining how generalized possibilistic logic can be used to compactly encode such knowledge, we analyze how a lack of knowledge affects the agreement outcome. In particular, we show how knowledgeable agents can obtain a more desirable outcome than others.

IJCAI Conference 2015 Conference Paper

Qualitative Reasoning about Directions in Semantic Spaces

• Steven Schockaert
• Jae Hee Lee

We introduce a framework for qualitative reasoning about directions in high-dimensional spaces, called EER, where our main motivation is to develop a form of commonsense reasoning about semantic spaces. The proposed framework is, however, more general; we show how qualitative spatial reasoning about points with several existing calculi can be reduced to the realisability problem for EER (or REER for short), including LR and calculi for reasoning about betweenness, collinearity and parallelism. Finally, we propose an efficient but incomplete inference method, and show its effectiveness for reasoning with EER as well as reasoning with some of the aforementioned calculi.

AIJ Journal 2015 Journal Article

Realizing RCC8 networks using convex regions

• Steven Schockaert
• Sanjiang Li

RCC8 is a popular fragment of the region connection calculus, in which qualitative spatial relations between regions, such as adjacency, overlap and parthood, can be expressed. While RCC8 is essentially dimensionless, most current applications are confined to reasoning about two-dimensional or three-dimensional physical space. In this paper, however, we are mainly interested in conceptual spaces, which typically are high-dimensional Euclidean spaces in which the meaning of natural language concepts can be represented using convex regions. The aim of this paper is to analyze how the restriction to convex regions constrains the realizability of networks of RCC8 relations. First, we identify all ways in which the set of RCC8 base relations can be restricted to guarantee that consistent networks can be convexly realized in respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the relation ‘partially overlaps’ is disallowed, all consistent atomic RCC8 networks can be convexly realized in 4D. If instead refinements of the relation ‘part of’ are disallowed, all consistent atomic RCC8 relations can be convexly realized in 3D. We furthermore show, among others, that any consistent RCC8 network with 2 n + 1 variables can be realized using convex regions in the n-dimensional Euclidean space.

ECAI Conference 2014 Conference Paper

A finite-valued solver for disjunctive fuzzy answer set programs

• Mushthofa Mushthofa
• Steven Schockaert
• Martine De Cock

Fuzzy Answer Set Programming (FASP) is a declarative programming paradigm which extends the flexibility and expressiveness of classical Answer Set Programming (ASP), with the aim of modeling continuous application domains. In contrast to the availability of efficient ASP solvers, there have been few attempts at implementing FASP solvers. In this paper, we propose an implementation of FASP based on a reduction to classical ASP. We also develop a prototype implementation of this method. To the best of our knowledge, this is the first solver for disjunctive FASP programs. Moreover, we experimentally show that our solver performs well in comparison to an existing solver (under reasonable assumptions) for the more restrictive class of normal FASP programs.

ECAI Conference 2014 Conference Paper

Characterising Semantic Relatedness using Interpretable Directions in Conceptual Spaces

• Joaquín Derrac
• Steven Schockaert

Various applications, such as critique-based recommendation systems and analogical classifiers, rely on knowledge of how different entities relate. In this paper, we present a methodology for identifying such semantic relationships, by interpreting them as qualitative spatial relations in a conceptual space. In particular, we use multi-dimensional scaling to induce a conceptual space from a relevant text corpus and then identify directions that correspond to relative properties such as "more violent than" in an entirely unsupervised way. We also show how a variant of FOIL is able to learn natural categories from such qualitative representations, by simulating a fortiori inference, an important pattern of commonsense reasoning.

JELIA Conference 2014 Conference Paper

Possibilistic Boolean Games: Strategic Reasoning under Incomplete Information

• Sofie De Clercq
• Steven Schockaert
• Martine De Cock
• Ann Nowé

Abstract Boolean games offer a compact alternative to normal-form games, by encoding the goal of each agent as a propositional formula. In this paper, we show how this framework can be naturally extended to model situations in which agents are uncertain about other agents’ goals. We first use uncertainty measures from possibility theory to semantically define (solution concepts to) Boolean games with incomplete information. Then we present a syntactic characterization of these semantics, which can readily be implemented, and we characterize the computational complexity.

ECAI Conference 2014 Conference Paper

Reasoning about Uncertainty and Explicit Ignorance in Generalized Possibilistic Logic

• Didier Dubois
• Henri Prade
• Steven Schockaert

Generalized possibilistic logic (GPL) is a logic for reasoning about the revealed beliefs of another agent. It is a two-tier propositional logic, in which propositional formulas are encapsulated by modal operators that are interpreted in terms of uncertainty measures from possibility theory. Models of a GPL theory represent weighted epistemic states and are encoded as possibility distributions. One of the main features of GPL is that it allows us to explicitly reason about the ignorance of another agent. In this paper, we study two types of approaches for reasoning about ignorance in GPL, based on the idea of minimal specificity and on the notion of guaranteed possibility, respectively. We show how these approaches naturally lead to different flavours of the language of GPL and a number of decision problems, whose complexity ranges from the first to the third level of the polynomial hierarchy.

KR Conference 2014 Short Paper

Using Answer Set Programming for Solving Boolean Games

• Sofie De Clercq
• Kim Bauters
• Steven Schockaert
• Martine de Cock
• Ann Nowé

Boolean games are a framework for reasoning about the rational behaviour of agents, whose goals are formalized using propositional formulas. They offer an attractive alternative to normal-form games, because they allow for a more intuitive and more compact encoding. Unfortunately, however, there is currently no general, tailor-made method available to compute the equilibria of Boolean games. In this paper, we introduce a method for finding the pure Nash equilibria based on disjunctive answer set programming. Our method is furthermore capable of finding the core elements and the Pareto optimal equilibria, and can easily be modified to support other forms of optimality, thanks to the declarative nature of disjunctive answer set programming. Experimental results clearly demonstrate the effectiveness of the proposed method.

IJCAI Conference 2013 Conference Paper

Combining RCC5 Relations with Betweenness Information

• Steven Schockaert
• Sanjiang Li

RCC5 is an important and well-known calculus for representing and reasoning about mereological relations. Among many other applications, it is pivotal in the formalization of commonsense reasoning about natural categories. In particular, it allows for a qualitative representation of conceptual spaces in the sense of Gärdenfors. To further the role of RCC5 as a vehicle for conceptual reasoning, in this paper we combine RCC5 relations with information about betweenness of regions. The resulting calculus allows us to express, for instance, that some part (but not all) of region B is between regions A and C. We show how consistency can be decided in polynomial time for atomic networks, even when regions are required to be convex. From an application perspective, the ability to express betweenness information allows us to use RCC5 as a basis for interpolative reasoning, while the restriction to convex regions ensures that all consistent networks can be faithfully represented as a conceptual space.

AIJ Journal 2013 Journal Article

Interpolative and extrapolative reasoning in propositional theories using qualitative knowledge about conceptual spaces

• Steven Schockaert
• Henri Prade

Many logical theories are incomplete, in the sense that non-trivial conclusions about particular situations cannot be derived from them using classical deduction. In this paper, we show how the ideas of interpolation and extrapolation, which are of crucial importance in many numerical domains, can be applied in symbolic settings to alleviate this issue in the case of propositional categorization rules. Our method is based on (mainly) qualitative descriptions of how different properties are conceptually related, where we identify conceptual relations between properties with spatial relations between regions in Gärdenfors conceptual spaces. The approach is centred around the view that categorization rules can often be seen as approximations of linear (or at least monotonic) mappings between conceptual spaces. We use this assumption to justify that whenever the antecedents of a number of rules stand in a relationship that is invariant under linear (or monotonic) transformations, their consequents should also stand in that relationship. A form of interpolative and extrapolative reasoning can then be obtained by applying this idea to the relations of betweenness and parallelism respectively. After discussing these ideas at the semantic level, we introduce a number of inference rules to characterize interpolative and extrapolative reasoning at the syntactic level, and show their soundness and completeness w. r. t. the proposed semantics. Finally, we show that the considered inference problems are PSPACE-hard in general, while implementations in polynomial time are possible under some relatively mild assumptions.

IJCAI Conference 2013 Conference Paper

Interpolative Reasoning with Default Rules

• Steven Schockaert
• Henri Prade

Default reasoning and interpolation are two important forms of commonsense rule-based reasoning. The former allows us to draw conclusions from incompletely specified states, by making assumptions on normality, whereas the latter allows us to draw conclusions from states that are not explicitly covered by any of the available rules. Although both approaches have received considerable attention in the literature, it is at present not well understood how they can be combined to draw reasonable conclusions from incompletely specified states and incomplete rule bases. In this paper, we introduce an inference system for interpolating default rules, based on a geometric semantics in which normality is related to spatial density and interpolation is related to geometric betweenness. We view default rules and information on the betweenness of natural categories as particular types of constraints on qualitative representations of Gärdenfors conceptual spaces. We propose an axiomatization, extending the well-known System P, and show its soundness and completeness w. r. t. the proposed semantics. Subsequently, we explore how our extension of preferential reasoning can be further refined by adapting two classical approaches for handling the irrelevance problem in default reasoning: rational closure and conditional entailment.

IJCAI Conference 2013 Conference Paper

Towards a Deeper Understanding of Nonmonotonic Reasoning with Degrees

• Marjon Blondeel
• Steven Schockaert
• Dirk Vermeir
• Martine de Cock

ECAI Conference 2012 Conference Paper

Convex Solutions of RCC8 Networks

• Steven Schockaert
• Sanjiang Li

RCC8 is one of the most widely used calculi for qualitative spatial reasoning. Although many applications have been explored where RCC8 relations refer to geographical or physical regions in two- or three-dimensional spaces, their use for conceptual reasoning is still at a rather preliminary stage. One of the core obstacles with using RCC8 to reason about conceptual spaces is that regions are required to be convex in this context. We investigate in this paper how the latter requirement impacts the realizability of RCC8 networks. Specifically, we show that consistent RCC8 networks over 2n + 1 variables are guaranteed to have a convex solution in Euclidean spaces of n dimensions and higher. We furthermore prove that our bound is optimal for 2- and 3-dimensional spaces, and that for any number of dimensions n ≥ 4, there exists a network of RCC8 relations over 3n variables which is consistent, but does not allow a convex solution in the n-dimensional Euclidean space.

KR Conference 2012 Conference Paper

Stable models in generalized possibilistic logic

• Didier Dubois
• Henri Prade
• Steven Schockaert

An important aspect of possibilistic logic is that models correspond to epistemic states, rather than to propositional interpretations, which forms a natural basis for epistemic reasoning. However, possibilistic logic only takes sets of formulas of the form (α, λ) into account, which we could interpret as conjunctions of assertions of the form N (α) ≥ λ. In some applications, on the other hand, we may want to link such assertions using different propositional connectives. In logic programming, for instance, a (negation-free) rule such as α → β intuitively means that whenever α is known to be true, we should accept β to be true as well. This could be expressed using necessity measures and material implication as N (α) ≥ 1 ⇒ N (β) ≥ 1. This implication, however, cannot be expressed in possibilistic logic, an observation which stands in stark contrast to the expressivity of modal logics for epistemic reasoning. In (Banerjee and Dubois 2009), a so-called Meta-Epistemic Logic (MEL) was introduced as a first step to bridge this gap, in the form of a simple modal logic with a semantics in terms of Boolean possibility distributions (i. e. possibility distributions π such that π(ω) ∈ {0, 1} for every ω ∈ Ω). Essentially, MEL is a fragment of the modal logic KD, in which neither the nesting of modalities nor the occurrence of nonmodal propositional formulas is allowed. Recently, generalized possibilistic logic (GPL) was introduced as a graded version of MEL (Dubois, Prade, and Schockaert 2011; Dubois and Prade 2011), developing an original proposal of (Dubois and Prade 2007). Possibilistic logic is a well-known logic for reasoning under uncertainty, which is based on the idea that the epistemic state of an agent can be modeled by assigning to each possible world a degree of possibility, taken from a totally ordered, but essentially qualitative scale. Recently, a generalization has been proposed that extends possibilistic logic to a meta-epistemic logic, endowing it with the capability of reasoning about epistemic states, rather than merely constraining them. In this paper, we further develop this generalized possibilistic logic (GPL). We introduce an axiomatization showing that GPL is a fragment of a graded version of the modal logic KD, and we prove soundness and completeness w. r. t. a semantics in terms of possibility distributions. Next, we reveal a close link between the wellknown stable model semantics for logic programming and the notion of minimally specific models in GPL. More generally, we analyze the relationship between the equilibrium logic of Pearce and GPL, showing that GPL can essentially be seen as a generalization of equilibrium logic, although its notion of minimal specificity is slightly more demanding than the notion of minimality underlying equilibrium logic.

AIJ Journal 2011 Journal Article

Solving conflicts in information merging by a flexible interpretation of atomic propositions

• Steven Schockaert
• Henri Prade

Although many techniques for merging conflicting propositional knowledge bases have already been proposed, most existing work is based on the idea that inconsistency results from the presence of incorrect pieces of information, which should be identified and removed. In contrast, we take the view in this paper that conflicts are often caused by statements that are inaccurate rather than completely false, suggesting to restore consistency by interpreting certain statements in a flexible way, rather than ignoring them completely. In accordance with this view, we propose a novel approach to merging which exploits extra-logical background information about the semantic relatedness of atomic propositions. Several merging operators are presented, which are based on different formalizations of this background knowledge, ranging from purely qualitative approaches, related to possibilistic logic, to quantitative approaches with a probabilistic flavor. Both syntactic and semantic characterizations are provided for each merging operator, and the computational complexity is analyzed.

AAAI Conference 2010 Conference Paper

An Inconsistency-Tolerant Approach to Information Merging Based on Proposition Relaxation

• Steven Schockaert
• Henri Prade

Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i. e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.

UAI Conference 2010 Conference Paper

Possibilistic Answer Set Programming Revisited

• Kim Bauters
• Steven Schockaert
• Martine De Cock
• Dirk Vermeir

Possibilistic answer set programming (PASP) extends answer set programming (ASP) by attaching to each rule a degree of certainty. While such an extension is important from an application point of view, existing semantics are not well-motivated, and do not always yield intuitive results. To develop a more suitable semantics, we first introduce a characterization of answer sets of classical ASP programs in terms of possibilistic logic where an ASP program specifies a set of constraints on possibility distributions. This characterization is then naturally generalized to define answer sets of PASP programs. We furthermore provide a syntactic counterpart, leading to a possibilistic generalization of the well-known Gelfond-Lifschitz reduct, and we show how our framework can readily be implemented using standard ASP solvers.

AIJ Journal 2009 Journal Article

Spatial reasoning in a fuzzy region connection calculus

• Steven Schockaert
• Martine de Cock
• Etienne E. Kerre

Although the region connection calculus (RCC) offers an appealing framework for modelling topological relations, its application in real-world scenarios is hampered when spatial phenomena are affected by vagueness. To cope with this, we present a generalization of the RCC based on fuzzy set theory, and discuss how reasoning tasks such as satisfiability and entailment checking can be cast into linear programming problems. We furthermore reveal that reasoning in our fuzzy RCC is NP-complete, thus preserving the computational complexity of reasoning in the RCC, and we identify an important tractable subfragment. Moreover, we show how reasoning tasks in our fuzzy RCC can also be reduced to reasoning tasks in the original RCC. While this link with the RCC could be exploited in practical reasoning algorithms, we mainly focus on the theoretical consequences. In particular, using this link we establish a close relationship with the Egg–Yolk calculus, and we demonstrate that satisfiable knowledge bases can be realized by fuzzy regions in any dimension.

AIJ Journal 2008 Journal Article

Temporal reasoning about fuzzy intervals

• Steven Schockaert
• Martine de Cock

Traditional approaches to temporal reasoning assume that time periods and time spans of events can be accurately represented as intervals. Real-world time periods and events, on the other hand, are often characterized by vague temporal boundaries, requiring appropriate generalizations of existing formalisms. This paper presents a framework for reasoning about qualitative and metric temporal relations between vague time periods. In particular, we show how several interesting problems, like consistency and entailment checking, can be reduced to reasoning tasks in existing temporal reasoning frameworks. We furthermore demonstrate that all reasoning tasks of interest are NP-complete, which reveals that adding vagueness to temporal reasoning does not increase its computational complexity. To support efficient reasoning, a large tractable subfragment is identified, among others, generalizing the well-known ORD Horn subfragment of the Interval Algebra (extended with metric constraints).

IJCAI Conference 2007 Conference Paper

• Steven Schockaert
• Martine de Cock
• Etienne E. Kerre

The temporal boundaries of many real-world events are inherently vague. In this paper, we discuss the problem of qualitative temporal reasoning about such vague events. We show that several interesting reasoning tasks, such as checking satisfiability, checking entailment, and calculating the best truth value bound, can be reduced to reasoning tasks in a well-known point algebra with disjunctions. Furthermore, we identify a maximal tractable subset of qualitative relations to support efficient reasoning.