Most learning and mining problems can be reformulated as Constraint Satisfaction Problems (CSPs) or Optimization Problems (OPs). So, problem solving in this context could in principle take advantage of generic solvers, by exclusively using a description of the relevant domain knowledge and the conditions imposed by the problem to be solved. However, in spite of focusing on problem specification, research in this area has traditionally focused on designing effective specific algorithms for solving the problem in hand. As stressed by De Raedt [7], there is an increasing interest in providing the user with languages for learning and mining. This change of perspective claims for a model+solver approach to learning and mining problems, in which the user specifies the problem by means of a declarative modeling language and the system automatically transforms such models into a format that can be used by a solver to efficiently generate a solution. For instance, constraint programming has been successfully applied to itemset mining problems (see, e.g., [12] for a comprehensive account). Another notable example is the framework of Meta-Interpretive Learning (MIL) [26]. MIL uses descriptions in the form of meta-rules (expressed in a higher-order dyadic Datalog fragment) with procedural constraints incorporated within a metainterpreter, which could be eventually implemented by relying on Answer Set Programming (ASP) solvers (see [10] for an updated overview).
Machine Learning (ML) and Data Mining (DM) algorithms both look for regularities in data, by means of some inductive reasoning mechanism such as generalization. However, it is conventional to distinguish between the two classes of algorithms as for the scope of induction. In particular, learning algorithms usually aim at prediction on unseen data, whereas mining algorithms have typically the scope of mere description of the given data.
Structure is inherent to data and knowledge in complex domains, and needs appropriate means for representation. Among the many formalisms used for representing structured knowledge, one of the most popular is the family of Description Logics (DLs) [1], which has been the starting point for the definition of the ontology language OWL.1 A DL knowledge base (or equivalently, an OWL ontology) is a collection of logical axioms and assertions. RDF2 is another popular formalism for structured knowledge, which however is less expressive than OWL. A knowledge graph (KG) is a huge collection of RDF triples. KGs can be interlinked and overall they implement the so-called Web of Data, i.e., the vision of the World Wide Web (WWW) as a distributed database system.
Structured knowledge poses several challenges to learning and mining algorithms. In the following subsections I will briefly introduce the two cases of interest for this work, namely Concept Learning and Knowledge Graph Mining.
Concept Learning deals with inferring the general definition of a category based on members (positive examples) and nonmembers (negative examples) of this category. In Concept Learning, the key inferential mechanism for induction is generalization as search through a partially ordered space of inductive hypotheses [23]. A popular form of Concept Learning is the one known under the name of Inductive Logic Programming (ILP) [25] where the hypotheses are typically expressed in the form of first-order Horn clauses (or other fragments of firstorder logic). A distinguishing feature of ILP with respect to other forms of Concept Learning is the use of prior knowledge of the domain of interest, called background knowledge (BK), during the search for hypotheses. In ILP it is also common practice to exploit some declarative bias to, e.g., constrain the language of hypotheses. Concept Learning in DLs has been paid increasing attention since the 90s. Early work essentially focused on demonstrating the PAC-learnability for various terminological languages derived from the Classic DL (see, e.g., [3]). Later works such as [2,14] have followed the generalization as search approach by extending the methodological apparatus of ILP to DL languages. More recently there has been a renewed interest in more theoretical work (see, e.g., [13]).
There are several variants of the Concept Learning problem in the DL context. The variant I consider as a showcase in this paper is the supervised one. In the following, the set of all individuals occurring in A and the set of all individuals occurring in A that are instances of a given concept C w.r.t. K are denoted by Ind(A) and Retr K (C), respectively. Example 1. For illustrative purposes of the CI-CSP problem, let us consider a very popular classification problem proposed 40 years ago by Ryszard Michalski [22] and illustrated in Figure 1. Here, 10 trains are described, out of which 5 are eastbound and 5 are westbound. The aim of this problem is to find the discriminating features between these two classes referred to as EastTrain and WestTrain (or, more briefly, as ET and WT) from now on.
For the purpose of this case study, let us consider an ALCO ontology, trains2, encoding the original Trains data set. 3 With reference to trains2 (which therefore will play the role of K as in Def. 1), we might want to induce a SROIQ concept definition for the target concept name ET (i.e., the language of hypotheses is some SROIQ H based on SROIQ) from the following positive and negative examples: Fig. 2. Fragment of a knowledge graph (taken from [30]).
-
The analysis of data contained in a KG (referred to as KG Mining) is preliminary to several crucial maintenance tasks, notably the automated completion of the graph (aka link prediction), which pose several challenges due to the open and distributed environment of the WWW infrastructure. In the KG community approaches for link prediction are divided into statistics-based (see [27] for an overview), and logic-based (e.g., [9,30]). The latter, which are the closest to the work reported in this paper, basically extend and adapt previous work in ILP on relational association rule mining. However, they differ in the expressiveness of the mined rules. AMIE+ [9] can mine only Horn rules, whereas the methodology presented in [30] can address the case of nonmonotonic rules.
Example 2. In the context of link prediction, the following rule
can be mined from the KG in Fig. 2 and applied to derive new facts such as livesIn(alice, berlin), livesIn(dave, chicago) and livesIn(lucy, amsterdam) to be used for completing the graph.
In several applications there is a need for modeling and reasoning about metaconcepts, i.e., concepts whose instances are themselves concepts, and metaproperties, i.e., relationships between meta-concepts. Metamodeling addresses this need. Indeed, it allows one to treat concepts and properties as first-order citizens, and to see them as individuals whose properties can be asserted and reasoned upon. A common feature to metamodeling approaches is the use of logical languages with higher-order constructs for a correct representation of concepts and properties at the meta-level. Metaquerying is a special case of domain metamodeling. This is the case where the knowledge base does not contain any axiom regarding meta-concepts or meta-properties, but the query language allows for using meta-concepts and meta-properties, so that concepts and properties in the knowledge base can match the variables in the query, and may thus be returned as answers to the query. This mechanism allows to express queries that are beyond first-order logic.
Metamodeling (and metaquerying) has recently attracted an increasing interest in the Knowledge Representation (KR) community, thus giving rise to a stream of research aimed at extending DLs with higher-order features (see, e.g., [28,24,4,5,15]). In particular, Colucci et al. [4] introduce second-order features in DLs under the Henkin semantics for modeling several forms of non-standard reasoning. The Henkin style shows a desirable feature, i.e., the expressive power of the language actually remains first-order.
In the following two subsections I briefly report the main achievements of my research on metamodeling and metaquerying by means of higher-order DLs in the context of Concept Learning and Knowledge Graph Mining.
In [16], I have extended Colucci et al.'s work on non-standard reasoning in DLs [4] to several variants of Concept Learning, thus being the first to propose higherorder DLs under Henkin semantics as a means for metamodeling in ML. The idea is that each of these variants, besides being considered as non-standard reasoning tasks, can be reformulated as a CSP or even as an OP. For the sake of illustration I will focus on the case of CI-CSP.
Following Def. 1, let us assume that Ind + C (A) = {a 1 , . . . , a m } and Ind − C (A) = {b 1 , . . . , b n }. A concept D ∈ DL H is a correct concept definition for the target concept name C w.r.t. Ind + C (A) and Ind − C (A) iff it is a solution for the following second-order concept expression:
that is, iff D can be a valid assignment for the concept variable X. The CI-CSP problem can be modeled with the following second-order formula
The solvability of a CI-CSP problem is therefore based on the satisfiability of the second-order formula being used for modeling the problem.
In [19,20], the proposed model+solver approach combines the efficacy of higher-order DLs in metamodeling (as shown in [16]) with the efficiency of ASP solvers in dealing with CSPs and OPs. The encoding into ASP is possible under the fixed-domain semantics [8], a non-standard model-theoretic semantics for DLs which has been proposed in order to correctly address CSPs in OWL.
The problem is then solvable if the following second-order formula:
is true in SROIQ H , i.e., if there exists a solution to γ ET CI-CSP in SROIQ H . Let us now assume that SROIQ H is the set of all SROIQ concept expressions that can be generated starting from the atomic concept and role names occurring in trains2 (except, of course, for the target concept name). Among the concepts belonging to SROIQ H and satisfying γ ET CI-CSP , there is
which describes the set of trains composed of at least one closed short car. It provides a correct concept definition for ET w.r.t. the given examples, i.e., the following concept equivalence axiom
is a solution for the CI-CSP problem in hand.
In [21] it has been observed that an interesting alternative to language bias (i.e., the declarative bias used in, e.g., [30] to learn rules of a predefined form) is the use of a meta-querying language that could take advantage of some useful metainformation about the data to be analyzed, for instance, the schema of the KG when available. In [17,18] I have proposed a new approach to KG Mining which adapts the notion of metaquery introduced by [29] for DM in relational databases to the novel context of KGs. In particular, a metaquery for KG Mining is a second-order DL conjunctive query under the Henkin semantics. However, the resulting metaquery language can be implemented with standard technologies of the Web of Data such as SPARQL. 4Example 4. An example of a metaquery in this context is the following
which looks for the properties (Q) holding for the individuals Y . Note that P, Q are higher-order variables whereas X, Y, Z are first-order variables.
Metaqueries can be extended into implications, called metaquery extensions, of the form
which are actually a compact representation of two metaqueries, M Q 1 and M Q 2 , where M Q 2 is longer than -we say extends -M Q 1 . A shorter notation for (9) is the following which stresses how
The left-hand side and the right-hand side of ( 10) are called the body and the head of the metaquery extension, respectively. Note that in the case of query extensions, the head does not correspond to the conclusion (as with clauses). Following the standard terminology, one should rather bear in mind the unshortened notation, and call M Q 2 the conclusion of the metaquery extension. Metaquery extensions serve as a template for rules we are interested in when applying rule mining algorithms to a given KG.
Example 5. Let us consider the following metaquery
which looks for the properties (Q) holding for the individuals Y and shared with the individuals X to which Y is related by some P . From ( 8) and ( 11) we can build a metaquery extension as shown below
with reference to the KG depicted in Fig. 2, (1) is an instantiation of (12) obtained by substituting the variables P and Q with the role names isM arriedT o and livesIn, respectively.
The work summarized in this paper pursues an interesting direction of research at the intersection of ML/DM and KR. [8]. Interestingly, the former two works pursue a unified view on the inferential problems of interest to the respective fields of research. This match of research efforts in the two fields has motivated the work presented in [16] with the aim of bridging the gap between KR and ML/DM in areas such as the maintenance of knowledge bases (or graphs) where the two fields have already produced promising results though mostly independently from each other. New questions and challenges have then been raised by the cross-fertilization of these results. Notably, the choice of a solver is a critical issue, which was more recently addressed in [19,20]. Finally, and from a broader perspective, the work here summarized contributes to the current shift in AI from programming to solving as recently argued by Geffner [11]. However, much work is still to be done. As for the use of metamodeling in Concept Learning, I plan to implement and test the approach by relying on available tools. Besides empirical evaluation, I intend also to investigate how to express optimality criteria such as the information gain function within the second-order concept expressions. Linking the approach to existing work on ontologies for ML/DM problems is another interesting direction of future research.
As for the use of metaquerying in Knowledge Graph Mining, several aspects of the proposed approach should to be clarified before an implementation. First, I plan to better define the semantics for the proposed metaquery language, also concerning the link with SPARQL. Second, I intend to design algorithms for the instantiation stage and choose the most appropriate evaluation measures for the intended application.
Acknowledgements This work was partially funded by the INdAM -GNCS Project 2019 "Metodi per il trattamento di incertezza ed imprecisione nella rappresentazione e revisione di conoscenza".