H Ambre Ayats

Peggy Cellier
email: peggy.cellier@irisa.fr

Sébastien Ferré
email: ferre@irisa.fr

Concepts of Neighbors and their Application to Instance-based Learning on Relational Data

Keywords: Relational Data, Knowledge Graph, Instance-Based Learning, Formal Concept Analysis, Graph-FCA, Concepts of Neighbors

Knowledge graphs and other forms of relational data have become a widespread kind of data, and powerful methods to analyze and learn from them are needed. Formal Concept Analysis (FCA) is a mathematical framework for the analysis of symbolic datasets, which has been extended to graphs and relational data, like Graph-FCA. It encompasses various tasks such as pattern mining or machine learning, but its application generally relies on the computation of a concept lattice whose size can be exponential with the number of instances. We propose to follow an instance-based approach where the learning effort is delayed until a new instance comes in, and an inference task is set. This is the approach adopted in k-Nearest Neighbors, and this relies on a distance between instances. We define a conceptual distance based on FCA concepts, and from there the notion of concepts of neighbors, which can be used as a basis for instance-based reasoning. Those definitions are given for both classical FCA and Graph-FCA. We provide efficient algorithms for computing concepts of neighbors, and we demonstrate their inference capabilities by presenting three different applications: query relaxation, knowledge graph completion, and relation extraction.

Introduction

Nowadays, a lot of information is available in the form of relational data, such as relational databases [START_REF] Codd | A relational model of data for large shared data banks[END_REF], graph databases [START_REF] Angles | Survey of graph database models[END_REF], or knowledge graphs [START_REF] Gutierrez | Knowledge graphs[END_REF]. In a relational dataset, the information is represented in terms of entities and relationships between those entities. Graphs are a common representation of relational data, using nodes for entities and edges for relationships. The different existing formalisms differ in the kind of nodes and edges they support or not: e.g., labelled edges, n-ary edges, literal values as nodes. The major advantage of relational data is their versatility and representation power. All kinds of structured data can be represented accurately as entityrelation graphs, including tabular data, XML trees, JSON objects, biological sequences or linguistic parse trees. The growing amount of relational data calls for powerful methods to analyze them and learn from them.

Formal Concept Analysis (FCA) [START_REF] Wille | Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[END_REF][START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a mathematical framework for the analysis of symbolic datasets. The strength of FCA is to encompass in one framework various tasks such as pattern mining, rule mining, machine learning, hierarchical clustering, and information retrieval [START_REF] Ferré | Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing[END_REF]. In its simplest setting, an FCA dataset is a binary relation between objects and attributes. However, a number of extensions have been proposed to cope with more complex data and settings. Fuzzy Concept Analysis [START_REF] Yang | Fuzzy Concept Mining based on Formal Concept Analysis[END_REF] adds truth degrees to the relations between objects and attributes, Temporal Concept Analysis (TCA) [START_REF] Wolff | Temporal Concept Analysis[END_REF] adds a temporal dimension to the description of objects, and Pattern Structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF] allows for custom descriptions instead of sets of attributes. More specifically, several extensions have been proposed for relational data: Relational Concept Analysis (RCA) [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF], concept lattices of relational structures [START_REF] Kötters | Concept Lattices of a Relational Structure[END_REF], and more recently Graph-FCA [START_REF] Ferré | Graph-FCA in Practice[END_REF]. A major issue in FCA is that the computation cost of the concept lattice can grow exponentially with the size of the data, and becomes even worse with relational extensions of FCA. However, depending on the task, it may not be necessary to compute all concepts and their lattice. Therefore, methods that compute only the relevant concepts w.r.t. the current task have to be developed.

The computation of the whole concept lattice can be compared to the learning of a model from training data in machine learning (model-based learning), where the model is then applied to new instances in order to make inferences about them. An alternative paradigm is instance-based learning, also known as lazy learning. It avoids the costly computation of a global model by delaying the learning effort until a new instance -called the query instance -comes in. In this way, only a specialized local model needs to be built in order to perform the desired inference on the query instance. Another advantage of this paradigm is that it supports frequent updates in the training dataset. Indeed, there is no training phase, which is usually long and energyconsuming. The most famous example of instance-based learning algorithm is the k-Nearest-Neighbors (kNN) algorithm [START_REF] Aha | Lazy Learning[END_REF]. It represents both training instances and query instances as points in a vector space. The class of a query instance is predicted from the class of the training instances that are the nearest neighbors of the query instance in the vector space. This involves the definition of a distance between instances that reflects their similarity. The research question we address in this paper is the following: What is a relevant definition of distance (or similarity) in the FCA context? and How such a distance can be used for different tasks by instance-based learning?

In this paper, we propose an instance-based learning method based on FCA that can be applied to various inference tasks. We first define a conceptual distance between instances in terms of formal concepts, and then the concepts of neighbors of a query instance as a basis for various inference tasks. Those definitions are given for classical FCA and also for the Graph-FCA extension in order to address relational data. The choice of Graph-FCA among the relational extensions is motivated by several advantages of Graph-FCA: (a) it supports n-ary relations; and (b) it can form n-ary concepts, which enables to reason on tuples of objects as instances (not only singleton objects). In addition to a theoretical framework, we provide efficient algorithms for computing concepts of neighbors. We also describe in detail three applications with different kinds of data and different kinds of inferences: approximate query answering, knowledge graph completion, and relation extraction from texts.

This paper brings together work published in several papers, both applied [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF][START_REF] Ayats | CONNOR: Exploring Similarities in Graphs with Concepts of Neighbors[END_REF][START_REF] Ferré | Application of Concepts of Neighbours to Knowledge Graph Completion[END_REF][START_REF] Ayats | Extracting Relations in Texts with Concepts of Neighbours[END_REF][START_REF] Ayats | A Two-Step Approach for Explainable Relation Extraction[END_REF] and theoretical [START_REF] Ferré | Concepts de plus proches voisins dans des graphes de connaissances[END_REF], with different notations. These contributions are here presented in a single formalism, giving them coherence and readability. In addition, this paper presents a novel formalization of the notion of Concepts of Neighbors in the general FCA framework, making it available to classical FCA and transferable to other FCA extensions.

The paper is organized as follows. Section 2 presents the related work. Section 3 gives the theoretical background on FCA and Graph-FCA. Section 4 defines the notions of conceptual distance and concepts of neighbors. Section 5 details the algorithms and implementation for the efficient computation of concepts of neighbors. Section 6 presents three applications of concepts of neighbors. Finally, Section 7 concludes the paper and presents some perspectives.

Related Work

The notion of concepts of neighbors and its computation methods can be seen under three aspects. First, it is a machine learning approach on relational data for tasks such as classification. More precisely, it is an instancebased learning approach, conceptually similar to kNN algorithms. Second, this method is part of the FCA theory, and especially of Graph-FCA, a generalized framework for handling relational data under the FCA theory. Third, concepts of neighbors can be seen as a graph pattern mining method, searching for similarities in the form of graph patterns in graph datasets. This section presents successively existing work related to those three aspects, highlighting the main similarities and differences with concepts of neighbors.

Instance-based learning. As far as we know, instance-based learning on relational data has rarely been studied. The most known approach on this subject is Relational Instance-Based Learning (RIBL) [START_REF] Horváth | Relational Instance-Based Learning with Lists and Terms[END_REF]: it consists in defining a numerical distance between items in a relational dataset and then applying an algorithm similar to the kNN algorithm to classify query instances. A similar approach has been used in [START_REF] Hermann | An Interactive Guidance Process Supporting Consistent Updates of RDFS Graphs[END_REF], this time in the context of the instance-based guided edition of RDF graphs. However, as far as we know, all existing approaches use a numerical distance between objects, whereas Concepts of Neighbors use a symbolic distance based on formal concepts.

Formal concept analysis. Because of its relatively low computational cost, the idea of using instance-based learning to perform classification has been considered in FCA-based machine learning [START_REF] Kuznetsov | Machine Learning and Formal Concept Analysis[END_REF]: instead of computing the whole concept lattice of a context, it consists into computing only the concepts related to the object to be classified. Therefore, for a single classification, the number of concepts to compute is reduced from exponential to linear. This idea has been applied to relation classification in biomedical texts [START_REF] Leeuwenberg | Exploring Pattern Structures of Syntactic Trees for Relation Extraction[END_REF]. This principle has been extended with other techniques such as approximation, random sampling and parallelization to be applied to big data [START_REF] Kuznetsov | Fitting Pattern Structures to Knowledge Discovery in Big Data[END_REF][START_REF] Kuznetsov | Scalable Knowledge Discovery in Complex Data with Pattern Structures[END_REF]. On a different task, information retrieval, the user query is considered as the query instance, and a notion of cousin concepts enables to find approximate answers to the user query and to rank them by increasing distance [START_REF] Codocedo | A semantic approach to concept lattice-based information retrieval[END_REF]. However, the cousin concepts are found by navigating the concept lattice, which therefore has to be computed beforehand. Our concepts of neighbors can be seen as a generalization of cousin concepts, and we provide a lazy algorithm for their computation. Approximate query answering is one of the applications of concepts of neighbors (see Section 6.1).

Graph pattern mining. The domain of graph pattern mining has been largely explored these last decades, and several types of approaches can be distinguished. The most classic ones, such as AGM [START_REF] Inokuchi | An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data[END_REF], FFSM [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF] or gSpan [START_REF] Yan | gSpan: graph-based substructure pattern mining[END_REF], are complete approaches, mining all patterns over a given frequency. However, these methods encounter the pattern explosion problem: either the frequency threshold is too high and the approaches return almost no pattern, or the frequency threshold is too low, and an intractable number of patterns (millions or more) is returned. This problem led to more parsimonious graph mining approaches. Some of them such as Gprune [START_REF] Zhu | gPrune: A Constraint Pushing Framework for Graph Pattern Mining[END_REF] rely on the user for specifying constraints on the patterns, others choose to select specific subsets of the frequent patterns, such as SPIN [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF] for the maximal patterns and CloseGraph [START_REF] Yan | CloseGraph: mining closed frequent graph patterns[END_REF] for the closed patterns. More recently, ideas from information theory have been used to drastically reduce the amount of mined patterns: e.g., the Minimum Description Length (MDL) principle (e.g., GraphMDL+ [START_REF] Bariatti | GraphMDL+: interleaving the generation and MDL-based selection of graph patterns[END_REF]) or the maximum entropy [START_REF] Van Leeuwen | Subjective interestingness of subgraph patterns[END_REF]. Concerning knowledge graph mining, specific approaches have been developed, such as SWApriori [START_REF] Ramezani | Mining Association Rules from Semantic Web Data without User Intervention[END_REF] for complete pattern mining, or rule mining approaches such as AMIE 3 [START_REF] Lajus | Fast and Exact Rule Mining with AMIE 3[END_REF] that aims to generate useful rules for tasks such as knowledge graph completion. Unlike all above approaches that generate a global set of patterns, concepts of neighbors are a local set of patterns that are relevant to a query instance. Moreover, the generated patterns are rooted patterns, i.e. they have a distinguished node that corresponds to the query instance. All this make them fit for downstream inference tasks.

Preliminary Definitions

In this section, we give the preliminary definitions used in the rest of the paper. We first present the main notions of Formal Concept Analysis (FCA). Then the adaptation of those notions in the framework of Graph-FCA, an extension of FCA for multi-relational data, is given as defined in [START_REF] Ferré | A Proposal for Extending Formal Concept Analysis to Knowledge Graphs[END_REF].

In the following, for any set X, we note X * = ∞ i=0 X i the set of tuples of elements in X of any length.

man woman adult kid married Charles × × × Charlotte × × Diana × × × George × × Harry × × × Kate × × × William × × ×

Formal Concept Analysis (FCA)

In this section, we present the basic notions of FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. Table 1 gives an example of a formal context. The set of objects is an excerpt of the British royal family and the attributes are some human characteristics, here to be a man, a woman, an adult, a kid, and married. The incidence relation associates each person to his/her characteristics. For instance, in this context, Charles is a man, an adult and married.

Definition 1. A formal context is a triple K = (O, A, I)
Definition 2. We define the instances of a set of attributes as the function

int : P(A) → P(O) Y → {o ∈ O | Y ⊆ I(o)}
that maps a set of attributes to the set of the objects that have all the attributes in their description.

Definition 3. We define the properties of a set of objects as the function

prop : P(O) → P(A) X → o∈X I(o)
that maps a set of objects to the set of their common attributes. For instance, in Table 1, inst({woman, adult}) = {Diana, Kate} and prop({Charles, W illiam}) = {man, married, adult}. The pair of functions (inst, prop) forms a Galois connection between sets of objects and sets of attributes, which leads to the definition of formal concepts. For example, in Table 1, ({Charles, W illiam}, {man, married}) is not a concept whereas ({Charles, W illiam, Harry}, {man, married}) is a concept.

The main theorem of FCA says that the set of all concepts of a context, when partially ordered by

(X 1 , Y 1 ) ≤ (X 2 , Y 2 ) ⇐⇒ X 1 ⊆ X 2 ⇐⇒ Y 2 ⊆ Y 1 ,
forms a complete lattice. This implies that for every pair of concepts C 1 , C 2 , there is an infimum concept C 1 ∧ C 2 (concept intersection) and a supremum concept C 1 ∨ C 2 (concept union). There are also a most general concept ⊤ (top concept) and a most specific concept ⊥ (bottom concept).

Graph-FCA

Graph-FCA [START_REF] Ferré | A Proposal for Extending Formal Concept Analysis to Knowledge Graphs[END_REF][START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF] is an extension of FCA for knowledge graphs, and more generally for relational data. Indeed, in FCA, objects can be described individually but not the relationships between objects. The equivalent of a formal context for Graph-FCA is called a graph context. The unary incidence ((Kate), woman) ∈ I says that Kate is a woman; we call it a node label and also write it woman(Kate) for readability and by analogy to predicate logic. The binary incidence ((George, Kate), parent) ∈ I says that Kate is a parent of George; we call it a labeled edge and also write it parent(George, Kate).

Most models of knowledge graphs can be translated accurately to graph contexts: e.g., the RDF graphs of the Semantic Web [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF], conceptual graphs [START_REF] Sowa | Conceptual structures: Information processing in mind and machine[END_REF], RCA contexts [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF]. For simple entity-relation KGs, entities translate to objects, relations to binary attributes, and triples to binary incidences. For translating RDF graphs to graph contexts, we abstract each URI and blank node x into an object o x , and we add the following incidences to the context:

• incidence c(o x ) for each triple (x, rdf:type, c),

• incidence p(o x , o y ) for each triple (x, p, y) where y is not a literal,

• incidence p(o x , o l ) for each triple (x, p, l) where l is a literal and o l is an object representing its occurrence in this specific triple,

• incidence u(o u ) for each URI u,

• incidence l(o l ) for each occurrence o l of a literal l.

The sets of objects and attributes can be deduced from this set of incidences. In particular, the set of attributes is made of classes as unary attributes, properties as binary attributes, and URIs and literals as unary attributes. In this representation, each RDF node is represented by an object labeled by its URI or literal -or unlabeled in the case of a blank node. More details can be found in [START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF].

The purpose of FCA is to discover patterns shared by objects. Whereas in classical FCA a pattern is a subset of attributes, in Graph-FCA a pattern is a projected graph pattern, which expresses a common graph structure rooted in one or several nodes. Definition 6. Let V be an infinite set of variables. A graph pattern P ⊆ V * × A is a set of pairs (y, a), with y a tuple of variables and a an attribute. Each of those pairs can be seen as a n-ary directed incidence (with n = |y|) labelled by attribute a.

A projected graph pattern (PGP) is a pair Q = (x, P ) where x ∈ V * a tuple of variables -called projected variables -and P is a graph pattern, such that each incidence of P is transitively connected to at least one element of x. The arity of a PGP is the length of x. A PGP of arity k is also called a k-PGP. The set of PGPs of arity k over a set of attributes A is denoted by P GP k (A).

Compared to previously published work, we here make it explicit that PGPs should be connected. Indeed, disconnected incidences would not contribute to PGPs' meaning. This has no incidence on Graph-FCA results.

Figure 1 (b) represents a 2-PGP defining the "sibling" binary relation, i.e. two persons with the same parents. Projected variables are in double boxes. In practice, PGPs can be seen as queries on the graph context, and we reuse the notation of such queries for the textual representation of PGPs:

[x, y ← man(u), woman(v), parent(x, u), parent(x, v), parent(y, u), parent(y, v), spouse(u, v), spouse(v, u)]

For any set of attributes A and arity k, the set of k-PGPs P GP k (A) forms a bounded lattice, with a partial ordering ⊆ P GP and an infimum ∩ P GP : Definition 7. We define the set of answers of a PGP Q as the set of answers of Q seen as a query.

Q 1 ⊆ P GP Q 2 means that Q 1 is a more general query than Q 2 ; and Q 1 ∩ P GP Q 2 is
ans : P GP k (A) → P(O k ) Q → {o | Q ⊆ P GP Q(o)}
In the example PGP of Figure 1 (b), the set of answers over the example graph context is made of the pairs (Harry, W illiam) and (George, Charlotte), and also their inverse because of the pattern symmetry, and also the identity pairs like (Harry, Harry) and (Charlotte, Charlotte) because there is no inequality constraints between variables x and y. The answers of Q(o) is the set of all tuples of objects that match everything that is known about o. Definition 8. We define the most specific query of a set of k-tuples of objects as the largest k-PGP according to ⊆ P GP whose set of answers contains R.

msq : P(O k ) → P GP k (A) R → o∈R Q(o)
In the example graph context, the most specific query of Charlotte and Kate is that they are women: msq({Charlotte, Kate}) = [x ← woman(x)]. The most specific query of Charlotte and William is [x ← P sibling , man(y)], where P sibling is the pattern of the above example PGP. It says that Charlotte and William have in common married parents and a brother. As proven in [START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF], the pair of functions (ans, msq) forms a Galois connection between P(O k ) and P GP k (A), for any k. This leads to the definition of graph concepts.

Definition 9. Let K = (O, A, I) be a graph context. A graph concept of arity k (also called a k-concept) is a pair C = (R, Q) ∈ P(O k ) × P GP k (A) such that R = ans(Q) and Q = msq(R).
R is called the extension of the concept, and Q is called the intension.

For each arity k, the set of all k-concepts forms a complete lattice where two concepts are ordered, (R

1 , Q 1 ) ≤ (R 2 , Q 2 ), iff R 1 ⊆ R 2 , and iff Q 2 ⊆ P GP Q 1 .
FCA is the special case of Graph-FCA where only unary attributes are used in the graph context, and only 1-concepts are considered. A more extensive presentation of Graph-FCA can be found in the reference journal paper [START_REF] Ferré | Application of Concepts of Neighbours to Knowledge Graph Completion[END_REF]. An implementation1 is available for the computation of graph concepts and their visualization [START_REF] Ferré | Modeling Complex Structures in Graph-FCA: Illustration on Natural Language Syntax[END_REF].

Concepts of Neighbors

Concepts of neighbors define a distance/similarity scheme in terms of FCA concepts, in a literal way because concepts are used directly as a measure of the distance/similarity between two objects. This is in contrast with the usual definitions of distance or similarity that use numerical values, even when applied to discrete structures. Concepts of neighbors also offer a local instance-based view of concepts -with FCA objects playing the role of instances -compared to the global view of concept lattices that is common with FCA.

In this section, we first define concepts of neighbors on standard FCA in order to explain the key ideas on a simple and well known formalism (Section 4.1). We then generalize the definitions to the richer Graph-FCA case in order to accommodate more complex relational data.

The FCA Case

We first define the conceptual distance between two objects as the most specific concept that contains both of them. Definition 10. Let K = (O, A, I) be a formal context, and u, v ∈ O be two objects in this context. The conceptual distance between objects u and v is the concept δ(u, v) = (X, Y ) s.t. Y = prop({u, v}) = I(u) ∩ I(v), and

X = inst(Y ).
Intuitively, the more similar the two objects are, the more specific the conceptual distance is. A more specific concept has fewer objects and more attributes. Having more attributes means having more similarities. The objects in the concept extent can be seen as in between the two objects, and hence fewer objects means a smaller distance. For example, in the formal context presented in Section 3.1, the conceptual distance between Charles and Charlotte has an empty intension and an extension containing all the objects, while the conceptual distance between Charles and Harry has for intension {man, adult, married} and for extension {Charles, Harry, W illiam}. It can be seen that the conceptual distance between Charles and Harry has three attributes in its intension while the conceptual distance between Charles and Charlotte has none. Therefore, Charles is more similar to Harry than to Charlotte. Reciprocally, the conceptual distance between Charles and Charlotte has seven objects in its extension, while the conceptual distance between Charles and Harry has only three objects. Therefore, Charles is more distant to Charlotte than to Harry.

The duality between distance and similarity is here embodied in the duality between the extension and intension of a concept. Actually, the conceptual distance between two objects is at the same time their conceptual similarity. The above definition satisfies the properties of a distance if we take the partial order ≤ on concepts as distance order, and concept supremum ∨ as addition: i.e., for all objects u, v, w ∈ O,

1. (positivity) δ(u, u) ≤ δ(u, v), (δ(u, u) represents distance zero) 2. (symmetry) δ(u, v) = δ(v, u), 3. (triangular inequality) δ(u, v) ≤ δ(u, w) ∨ δ(w, v).
Because of the ordering being partial, it is common to have objects, say v and w, that are at incomparable distances from u: i.e., δ(u, v) ̸ ≤ δ(u, w) and δ(u, w) ̸ ≤ δ(u, v).

Numerical versions of distance and similarity can be derived from the conceptual distance by using the cardinal of the extension or intension. Given the conceptual distance δ(u, v) = (X, Y ):

• the extensional distance d(u, v) = |X| is the cardinal of the exten- sion,
• the intensional similarity sim(u, v) = |Y | is the cardinal of the intension.

Note that those numerical versions are degraded versions, as they flatten the partial ordering over conceptual distances to a total ordering. This can lead to consider two objects as being at the same distance, whereas the conceptual distances are completely different.

Definition 11. Let K = (O, A, I) be a formal context, and u ∈ O be an object. The concepts of neighbors of u is the set of all conceptual distances from u to any other object in the context:

C -N (u) = {δ(u, v) | v ∈ O}.
For example, in the formal context defined in 3.1, C -N (Charlotte) contains four concepts. The first one has for intension {woman, kid} and for extension {Charlotte}. Then there are two more general concepts: ({Charlotte, Diana, Kate}, {woman}) and ({Charlotte, George}, {kid}). Finally, there is the most general concept, with an empty intension and the whole set of objects as extension.

Concepts of Neighbors C -N (u) provide an instance-based view over the context, by partitioning the set of objects according to their conceptual distance with u. Each concept of neighbors δ ∈ C -N (u) induces the subset of objects δ.proper := {o ∈ O | δ(u, o) = δ}, i.e. the objects that are exactly at distance δ from u. This is a subset of the extension of δ, called the proper extension of δ.

The Graph-FCA Case

Concepts of neighbors are naturally extended to Graph-FCA, as the latter inherits the definitions and theorems of FCA. Conceptual distances and concepts of neighbors are here graph concepts. A first benefit in Graph-FCA is that the similarity between two objects is not only expressed in terms of common properties but also in terms of common relationships to similar objects, which in turn can have common properties and common relationships to farther objects, and so on. For instance, the conceptual distance between France and Spain could be the concept of countries that speak a Romance language, with PGP [x ← country(x), speaks(x, y), language(y), romanceLanguage(y)], with Italy and Portugal in the extension. A second benefit is that there are not only concepts for individual objects but also for k-tuples of objects. This implies that it becomes possible to compare such tuples of objects. For instance, the conceptual distance between pairs (F rance, P aris) and (U kraine, Kyiv) is the concept whose intent states the "has capital" relationship among other things, with PGP [x, y ← hasCapital(x, y), country(x), city(y)...], and whose extent contains more (country, city) pairs, e.g. (Italy, Roma). Definition 12. Let K = (O, A, I) be a graph context, and u, v ∈ O k , for some arity k. The conceptual distance between the two k-tuples of objects

u and v is the k-concept δ(u, v) = (R, Q) s.t. Q = msq({u, v) = Q(u) ∩ P GP Q(v), and R = ans(Q).
Like in FCA, this definition satisfies the properties of a distance, and numerical versions of distance and similarity can be derived likewise.

C -N (u) = {δ(u, v) | v ∈ O k }.
This again induces a partition over the set of k-tuples of objects, where each part is the proper extension δ.proper of the corresponding conceptual distance δ.

Figure 2 presents the five concepts of neighbors of Charlotte in the graph context presented in Figure 1 (a). On the right, the extensions are presented as a Venn diagram, and on the left the intensions are expressed in plain English for simplicity. The first concept has for intension the whole graph centered on Charlotte and has only Charlotte in its extension. Then there are two larger concepts, one containing the children of Kate and William (Charlotte and George), and another one containing the women. Then there is an even larger concept containing the people having a father, a mother and a sibling (Harry, William, Charlotte, and George). Finally, there is the top concept, having an empty intension and all objects as extension. For each concept of neighbors, the objects of the proper extension are displayed in the same color as the concept ellipse. It can be seen that the proper extension of a concept is made of the objects in the extension that are not in subconcepts. This color-coding materializes the partition of objects by concepts of neighbors. When two objects are in the same proper extension, e.g. Harry and William, this means that they are indistinguishable relative to the chosen object. The Venn diagram shows well the fact that the concepts of neighbors are only partially ordered. For instance, Concept (3) is a sub-concept of Concept (4) but is incomparable with Concept (2). The inclusion of (3) in ( 4) means that George from Concept (3) is closer to Charlotte than Harry from Concept (4) is: he has a father, a mother and a sibling, like Harry, but he also has the same parents as Charlotte, unlike Harry. The incomparability of ( 3) and ( 2) means that George and Diana are similar to Charlotte for incomparable reasons: George has the same parents as Charlotte, while Diana has the same gender as Charlotte. Such distinctions cannot be made with totally ordered distances like numerical ones.

Algorithms

We here describe an efficient and anytime algorithm for the computation of concepts of neighbors. The algorithm inputs are a graph context K = (O, A, I), and a k-tuple of objects u ∈ O k , called the query instance. The algorithm output is the collection of concepts of neighbors C -N (u), with for each conceptual distance δ ∈ C -N (u) the concept intension δ.int, the concept extension δ.ext, and the proper extension δ.proper. The three types of information play an important role in applications of Concepts of Neighbors (see Section 6). For practical reasons, the algorithm can also take as input a subset of the k-tuples of objects V ⊆ O k , called candidate instances, to restrict the set of considered neighbors of the query instance. The extensions and proper extensions of concepts of neighbors are therefore subsets of V .

A first approach to compute concepts of neighbors would be to follow their definition, i.e. to compute the conceptual distance from the query instance u to every candidate instance v ∈ V . This is the approach followed by work using distance measures on symbolic data [START_REF] Horváth | Relational Instance-Based Learning with Lists and Terms[END_REF]. It here requires performing two complex operations for each candidate instance: to compute the most specific query Q between them, and to compute the set of answers R of that most specific query Q. This does not scale to large sets of candidate instances. This is also inefficient because in general each concept of neighbor will be computed many times, |δ.proper| times to be exact. A second approach would be to start with the concept δ(u, u) whose intension is the graph description Q(u) of the query instance, and to explore the space of more general concepts by generalizing the intension. This is the approach followed by query relaxation [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF]. It here requires to repeatedly apply minimal generalizations to PGPs, e.g. removing an edge, and to compute the set of answers of the generalized PGPs. If the generalized PGP covers additional instances, then a new conceptual distance has been found, and the additional instances make for its proper extension. The first problem is that the gener-alization space is combinatorial in the size of the initial PGP, and in the case of knowledge graphs, the initial PGP often contains the whole graph context. Moreover, the set of answers has to be computed for each generalized PGP, and it cannot be derived from previous PGPs as their extension is smaller.

We propose a third approach to compute concepts of neighbors, an approach that factorizes the computation of the most specific queries across the instances, and that factorizes the computation of sets of answers across generalized PGPs. The general idea is to explore the generalization space top-down, starting with the empty PGP, and to massively prune it by maintaining and refining a partition of the instances that converges towards the proper extensions. By exploring the generalization space top-down, i.e. by specializing PGPs, the answers of a specialized PGP Q 2 can be computed incrementally from the answers of its parent PGP Q 1 . Indeed, the answers of Q 2 are a subset of the answers of Q 1 because of the Galois connection between PGPs and sets of object tuples. Moreover, for every concept of neighbors, there is a single path in the top-down exploration that leads to its intension, so that the most specific queries are computed only once, whatever the size of the proper extension.

In this section, we first describe the partitioning algorithm that explores the generalization space top-down to compute concepts of neighbors (Section 5.1). We then introduce an essential optimization in the computation of sets of answers by introducing the lazy join algorithm (Section 5.2). Those two algorithms have been previously published in [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF], in the context of query relaxation. We also present CONNOR, an implementation as a Java library (Section 5.3).

Iterative Partitioning of Instances into Concepts of Neighbors

At any stage of the algorithm, the set of candidate instances is partitioned in a set of pre-concepts of neighbors (pre-concepts in short), where each preconcept is made of a PGP Q l and its answers R l like a concept, except that the PGP is not necessarily the most specific query for those answers. Each preconcept also comes with a subset of answers V l such that the collection {V l } l defines a partition of the set of candidate instances, a match-set M l that is the set of answers extended to all variables occurring in the PGP graph pattern, and a set of incidences I l to be used as PGP specializations. The match-set is useful for the incremental computation of sets of answers of specialized PGPs, and the incidences are useful to control the specialization of PGPs. We define match-sets before formally defining pre-concepts. Definition 14. Let K = (O, A, I) be a graph context, and V an infinite set of variables. A match-set is a pair M = (x, R) ∈ V k × P(O k ), for some arity k. It defines a set of mappings from the k variables in x to objects of the context: x = dom(M ) is called the domain of the match-set, and R = rel (M ) is called the relation of the match-set. Match-sets are equipped with two operations from relational algebra [START_REF] Codd | A relational model of data for large shared data banks[END_REF]:

• the projection π y M of a match-set on a sub-tuple y of the match-set variables;

• the(natural) join M 1 ▷◁ M 2 of two match-sets.

Definition 15. Let K be a graph concept, u be the query instance with arity k, and V ⊆ O k be the set of candidate instances. A partition of the set of candidate instances is a collection {C l } l of pre-concepts (of neighbors), where each pre-concept is a structure

C l = (Q l , R l , V l , M l , H l ), s.t.: • Q l = [u ← P l ] is a k-PGP that is a generalization of Q(u)
, with x l being the tuple of all variables occurring in u or in P l ;

• R l = ans(Q l ) ∩ V is the set of answers of Q l in V ;

• V l ⊆ R l is a subset of answers such that the collection {V l } l forms a partition of V ;

• M l = (x l , ans((x l , P l ))) is the match-set containing all matchings of the pattern P l on the graph context;

• I l ⊆ I is a set of incidences from the description of the query instance that remain available for specializing Q l .

As we explore the generalization space of the description of u, we simply use objects from that description as variables in the PGPs. A pre-concept becomes a concept of neighbors when I l gets empty, i.e. when the preconcept cannot be specialized further. In this case, the pair (Q l , R l ) is a concept of neighbors (filtered by V ), and V l is its proper extension. When I l is not empty, V l may be a union of proper extensions (lack of discrimination), and Q l is not necessarily the most specific query of instances in V l (lack of precision in the conceptual similarity). This implies an overestimate of the distance, and an underestimate of the similarity, for some instances in V l .

The specialization process aims at making pre-concepts converge to concepts of neighbors, going through increasingly precise estimates of distance and similarity.

Initially, there is a single pre-concept, the initial pre-concept that uses the empty PGP and that contains all candidate instances. Definition 16. The initial pre-concept is the pre-concept C init s.t.:

• Q init = [u ← ∅] is the empty PGP (x init = u); • R init = ans(Q init ) ∩ V = V is the set of all candidate instances; • V init = V is the set of all candidate instances; • M init = (u, V );
• I init = I is the set of all incidences from the graph context.

Each pre-concept C l s.t. I l ̸ = ∅ may be split in two pre-concepts C i and C j by using an incidence (w, a) ∈ I l to discriminate among instances V l those that match the incidence from those that do not. Definition 17. The specialization of a pre-concept C l by an incidence (w, a) ∈ I l leads to two new pre-concepts C i and C j that replace C l in the partition, and that are defined as follows (the definitions of R and M follow from the definition of Q):

Q i = [u ← P l ∪ {(w, a)}] Q j = Q l V i = V l ∩ R i V j = V l \ R i = V l \ V i I i = I l \ {(w, a)} I j = I l \ {(w, a)} Pre-concept C i is a specialization of C l ,
by the addition of an incidence to the query pattern. This leads in general to a smaller set of answers R i , and hence a smaller subset of candidate instances V i . Pre-concept C j is an update of concept C l , where the candidate instances V j is the part of V l that is not selected by V i . In both pre-concepts, the chosen incidence is discarded so that it is not considered any more for the specialization of the new pre-concepts. After a specialization, we still have a partition of V because {V i , V j } is a partition of V l . In general, we get a finer partition with two smaller parts, but it is also possible that one of the parts is empty, in which case the partition is unchanged. For instance, if the chosen incidence is disconnected from u in Q l , then it has no effect on answers and V i = V l . Therefore, only connected incidences should be chosen for effective specialization. However, even connected incidences can lead to V i = V l , depending on regularities in data.

According to the above definition, the cost of specializing a pre-concept looks very small. It amounts to add an incidence to a PGP, to perform basic set operations on sets of instances, and to remove an element from the set of incidences. However, the computation of V i and V j requires the set of answers R i = ans(Q i ) of the specialized PGP. This computation can be made incremental by relying on the match-set of pre-concepts. The match-set M of a graph pattern P is equal to the join of the match-sets of all incidences (w, a) ∈ P :

M = ▷◁ (w,a)∈P M (w,a) where M (w,a) = (w, ans([w ← a(w)]))
As the join operator is associative and commutative, the match-set of the specialized PGP can be computed incrementally from the parent PGP.

M i = M l ▷◁ M (w,a)
Finally, the set of answers is simply the projection of the match-set on the projected variables.

R i = rel (π u M i )
Algorithm 1 details the partitioning algorithm. Given a graph context, a query instance, and a set of candidate instances, it starts with a single preconcept, the initial pre-concept (Definition 16). It then iteratively applies specialization steps (Definition 17) to pre-concepts in order to refine the partition. The process runs until no specialization is possible or a timeout has been attained. This timeout is optional, but it has the advantage to make the algorithm anytime (more on this below). Figure 3 shows an execution trace as a binary tree of pre-concepts. It represents the computation of the concepts of neighbors of Charlotte (see Figure 2 pick some (w, a) ∈ I l that is connected to u in Q l 4:

Q i ← [u ← P l ∪ {(w, a)}] 5: M i ← M l ▷◁ M (w,a) 6: R i ← rel (π u M i ) 7: V i ← V l ∩ R i 8: V j ← V l \ V i 9: I ij = I l \ {(w, a)} 10: C ← C \ {C l } 11: C ← C ∪ {C i }, if V i ̸ = ∅, where C i = (Q i , R i , V i , M i , I ij ) 12: C ← C ∪ {C j }, if V j ̸ = ∅, where C j = (Q l , R l , V j , M l , I ij )
13: end while the left from the men on the right. Those women remain in the extension of the concept on the right but no more in the proper extent. The concept on the left is further split in two pre-concepts: woman with a parent on the left (A), and woman without a parent on the right (DK). Pre-concept (A) cannot be split further, although incidences can still be added to it. From pre-concept (DK), all remaining incidences lead to an empty extension because Diana and Kate have nothing else in common with Charlotte. The boxed pre-concepts at the leaves are the results of the algorithm. Their intent is the set of incidences that label the path from the root to this pre-concept. They coincide with the concepts of neighbors shown in Figure 2.

Discussion. The algorithm may be incomplete in the sense that some concepts of neighbors may be missed, hence moving some instances at a greater conceptual distance than they are actually. The cause is that the generated graph patterns P l are constrained to be subsets of I, they cannot be arbitrary graph patterns that have a matching occurrence in I. Suppose u is the ] ("has a p that is a a, and has a p -the same or another -that is a b"). Note that Q * is more general than Q ab and more specific than Q a and Q b . If some candidate instance v matches Q * but not Q ab , then it will belong to the concept of either Q a or Q b , depending on which of a(w) or b(w) is chosen first. In order to recover completeness, we should allow for the duplication of a variable in a graph pattern (e.g., w ⇝ w 1 , w 2 ), which would actually make the search space infinite. This simplification only entails an approximation in the computation of the conceptual distances, and it brings not only a benefit in terms of tractability, but also a benefit in terms of interpretability because the intensions of concepts of neighbors are subgraphs of the description of the query instance.

The partitioning algorithm always terminates because the set I l decreases at each split in both concepts C i and C j . Moreover, the number of preconcepts is bounded by the number of candidate instances at any step because every candidate instance belongs to the proper extension of a single pre-concept, by construction. This is remarkable because the search space is exponential in the number of incidences. Each candidate instance v ∈ V is forced to move down along only one path, so that among the many paths that goes from Q init to δ(u, v), only one path is actually followed. Despite those good properties, the full partitioning can still take a lot of time in the case of large graph contexts. This is why we make our algorithm anytime by adding a timeout parameter. This is justified because a valid partition of candidate instances by a collection of pre-concepts is available at all time. If the algorithm is stopped before its completion, one simply get a coarser partition, and an overestimate of the conceptual distances to each instance. Previous experiments [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF] have shown that the algorithm has the good property to output more than half of the concepts in a small proportion of the total runtime.

Lazy Join of Match-Sets

The partitioning algorithm of the previous section has good properties w.r.t. the exploration of the search space, but it hides a bottleneck in the computation of match-sets. Suppose the current pre-concept C 0 where Q 0 = [u ← f ilm(u)] ("is a film"), and where the match-set M 0 has a matching for each unique film. Specializing C 0 by adding an actor to the film (incidence actor(u, w 1 )) leads to the PGP Q 1 = [u ← f ilm(u), actor(u, w 1 )] and to the match-set M 1 = M 0 ▷◁ M actor(u,w 1 ) , which has a matching for each (film, actor) pair. The bottleneck comes when adding an incidence actor(u, w i ) for all actors of the query instance, as this entails the successive joins M 0 ▷◁ M actor(u,w 1 ) . . . ▷◁ M actor(u,wn) . Assuming there are N films and n actors per film, each join results in a n-fold increase of the match-set, and the join chain results in a n n -fold increase. For 1000 films related to 10 actors each, it amounts to 10 13 matchings in M n ! The bottleneck lies in the exponential growth of the size of match-sets and their computation time. It is actually possible to do better because the expected end result is the set of answers R = π u M , whose size is bounded by the number of candidate instances.

We here describe a compact representation of a match-set M , called a match-tree, that is made of several local joins instead of the global join. It supports the incremental computation of match-sets assumed by the partitioning algorithm, and it performs joins in a local and lazy way to keep the representation as compact as possible.

A match-set M l results from the set of incidences P l . A match-tree is based on a tree structure over those incidences. Definition 18. A match-tree is a rooted n-ary tree T where each node is an incidence i = (w, a) and is labeled by a tuple (D, M, ∆) where2 :

• D ⊆ w is a subset of the variables used by incidence i;

• M is the local match-set s.t. w ⊆ dom(M );

• ∆ ⊆ dom(M ) is the subdomain that is useful to the node's ancestors.

For each incidence, D is the set of variables defined by the incidence when added to a pre-concept. For example, starting from [u ← f ilm(u)], incidence actor(u, w 1 ) defines the variable w 1 . The local match-set M is a local join, i.e. a join over a subset of the incidences inserted so far. Joining all local match-sets would result in the global join. In the example, for incidence actor(u, w 1 ), M is M actor(u,w 1 ) alone, i.e. a primitive match-set. Finally, ∆ tells on which variables the local match-set can be projected without loosing information for the computation of the set of answers R. In the example, ∆ = {u}, only the films having an actor matter, not the particular actors.

In order to use match-trees in place of match-sets in the partitioning algorithm, we have to define the following operations on them: (a) the initial match-tree T init to be used in the initial pre-concept, (b) the join between a match-tree T l and a new incidence whose result must be a match-tree T i , and (c) the projection of a match-tree on variables u to get the set of answers R i .

The initial match-tree T init is used in the initial pre-concept in place of the initial match-set. It has a single root node that is a pseudo-incidence i = ⊤(u) and that is labeled with (u, M init , u).

Algorithm 2 LazyJoin(T, i, i * , D * , M * , ∆ * ) Require: a match-tree T , a current incidence i in T labeled with (D, M, ∆),

and a new incidence i * labeled with (D * , M * , ∆ * ) Ensure: two sets of variables ∆ + , ∆ - 1:

∆ + ← ∅; ∆ -← ∅ 2: for all i c ∈ children(i), labeled with (D c , M c , ∆ c ) do 3: ∆ + c , ∆ - c ← LazyJoin(T, i c , i * , D * , M * , ∆ * ) //
∆ + ← ∆ + ∪ ∆ + c ; ∆ -← ∆ -∪ ∆ - c 5: M ← M ⋊ ⋉ π ∆c M c , if ∆ c or M c was
∆ -← ∆ -∪ (∆ * \ D); M ← M ⋊ ⋉ ∆ * M * ; parent(i * ) ← i 10:
∆ + ← ∆ + ∪ (∆ * ∩ D) 12: end if 13: end if 14: ∆ + ← ∆ + \ ∆ - 15: ∆ -← ∆ -\ ∆ + 16: ∆ ← ∆ ∪ ∆ + ∪ ∆ -// update ∆ 17: return ∆ + , ∆ -
The line M i ← M l ▷◁ M (w,a) doing the incremental join in Algorithm 1 is replaced by

T i ← LazyJoin(T l , ⊤(u), (w, a), D * , M * , ∆ * )
where LazyJoin is defined by Algorithm 2. It is based on a recursive traversal of the match-tree (lines 2-3) starting at the root ⊤(u), inserting the new incidence i * = (w, a) at an appropriate place (line 9), and updating local match-sets accordingly (line 5). The new incidence is labeled as follows, where for recall x l is the tuple of all variables in the current pattern P l :

D * = w \ x l , ∆ * = w ∩ x l , M * = M (w,a) .
Considering the variables ∆ * of the new incidence that are already in the match-set, the new incidence i * is inserted as a child of the first visited node whose defined variables D contains at least one variable in ∆ * (lines 7-9).

The common variables between D and ∆ * provide a connection between the current pattern and the new incidence. If some variables in ∆ * are not defined at the insertion node, they are returned and propagated through ∆ - as missing variables for join (line 4, 9, 17), and they are propagated from the incidences that define them through ∆ + as available variables for join (line [START_REF] Wille | Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[END_REF][START_REF] Kötters | Concept Lattices of a Relational Structure[END_REF][START_REF] Ayats | Extracting Relations in Texts with Concepts of Neighbours[END_REF]. Those missing and available variables are added to the ∆ + /∆ -of incidences upward (line 16), except when they meet each other (lines 14-15). Finally, the set of answers R corresponding to a match-tree T is rel (π u M ⊤ ), where M ⊤ is the local match-set of the root.

Figure 4 shows the effect of the lazy join of the new incidence i * = parent(g, k) at the pre-concept with proper extension WHG in Figure 3. The input match-tree is on the left, and the output match-tree is on the right. The input match-tree corresponds to the PGP [a ← man(w), woman(k), parent(a, w), parent(a, k), parent(g, w)],

and it is hence the result of 5 successive lazy joins, each introducing an incidence. Changes (shown in bold on the right side) are propagated from the two incidences that define g and k (see D), and the new leaf is inserted under one of the two nodes as a child (here, under the node defining k). The insertion of other incidences, which led to the match-tree on the left, change only one path in the match-tree because they do not introduce a cycle. In Algorithm 2, the computation of ∆ + , ∆ -is used to correctly handle cycles. They are sets of variables of the new incidence i * that are not in the matchset of its parent (g in the example), and hence need to be joined with distant nodes in the match-tree. ∆ -propagates up the tree branch of the parent (incidence parent(a, k) in Figure 4), and ∆ + propagates up the tree branch of distant incidences (incidence parent(g, w)). When they meet at their common ancestor (incidence ⊤(a) here), the distant join can be done, and their propagation stops. Discussion. In the example on films, we observe that each new element i * = actor(u, w i ) only entails the computation M ⋊ ⋉ π u M i * , i.e. the intersection between the current set of films, and the set of films having an actor. The final match-tree therefore contains a match-set at the root whose size is N , and n match-sets at the leaves whose size is N n (one for each actor). The total size is therefore in the order of N n 2 matchings instead of N n n . For 1000 films related to 10 actors each, it amounts to 10 5 instead of 10 13 ! Moreover, the match-sets have 1 or 2 variables in their domain instead of (n + 1) for the global join.

Implementation

The main implementation of those algorithms is CONNOR, a Java library for the computation of concepts of neighbors. This library is a free and open-source software3 , based on Apache Jena4 , a well-known Java library for representing and reasoning on the RDF graphs of the Semantic Web. As presented in Section 3.2, there is a correspondence between RDF graphs and Graph-FCA contexts with only unary and binary relations. This is the case handled by CONNOR: graph contexts are represented as RDF graphs and handled with the Jena library. This library gives a comprehensive interface for the handling of graph contexts (with the class ConnorModel) and concepts of neighbors (class ConceptOfNeighbour), and provides classes encapsulating the algorithms for the efficient computation of concepts of neighbors (classes ConnorPartition and ConnorThread). A full presentation of CONNOR with usage examples can be found in [START_REF] Ayats | CONNOR: Exploring Similarities in Graphs with Concepts of Neighbors[END_REF].

This implementation takes into account the domain knowledge expressed as RDF Schema (RDFS) axioms [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF], by applying the algorithms on the saturated version of the RDF graph. For instance, if there is an incidence c(o) where c is an RDFS class, and d is known as a superclass of c in the RDF Schema axioms, then d(o) is also considered as an incidence. This is possible because RDFS can only entail a finite set of facts [START_REF] Goasdoué | Efficient query answering against dynamic rdf databases[END_REF].

Applications

This section presents different applications of Concepts of Neighbors. As shown above, the computation of concepts of neighbors is a generic method for computing distances between entities in relational datasets. The potential applications are therefore numerous and varied. As of today, three different applications have been developed and are detailed in this section: (1) query relaxation to find approximate answering in KGs, (2) knowledge graph completion to infer missing facts in KGs, and (3) relation extraction to populate KGs from text.

Query Relaxation

Query relaxation has been proposed as a way to find approximate answers to user queries [START_REF] Gaasterland | Cooperative answering through controlled query relaxation[END_REF]. Approximate answers are useful when the user query has too few answers or no answers at all. The lack of answers can have various reasons. Either the user has insufficient knowledge about the data schema, or the data is incomplete or noisy, or the query is too stringent. Query relaxation consists in applying transformations to the user query in order to relax constraints, and make it more general so that it produces more answers. A major issue in query relaxation is that the number of relaxed queries grows in a combinatorial way with the number of relaxation steps and the size of the query.

This section is a summary of a previous work [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF], with formal notations made consistent with the previous sections. We first give a specific related work on the query relaxation task. Then we show how Concepts of Neighbors can be applied to improve the efficiency of query relaxation. Finally, we present experiments showing that, despite the higher efficiency, our approach does not trade quality for efficiency as it produces the same results as query relaxation.

Related Work

The existing approaches for query relaxation consist in enumerating relaxed queries up to some edit distance, and to evaluate each relaxed query, from the more specific to the more general, in order to get new approximate answers [START_REF] Hurtado | Query Relaxation in RDF[END_REF][START_REF] Huang | Approximating query answering on RDF databases[END_REF][START_REF] Frosini | Flexible query processing for SPARQL[END_REF]. The main issue with such an enumeration-based approach is that the number of relaxed queries grows in a combinatorial way with the edit distance, and the size of the query. Moreover, many relaxed queries do not yield any new answer because they have the same answers as more specific relaxed queries. Huang et al. [START_REF] Huang | Approximating query answering on RDF databases[END_REF] use a similarity score in order to have a better ranking for the evaluation of relaxed queries. Hurtado et al. [START_REF] Hurtado | Query Relaxation in RDF[END_REF] optimize the evaluation of relaxed queries by directly computing their proper answers. New SPARQL clauses, RELAX and APPROX [START_REF] Frosini | Flexible query processing for SPARQL[END_REF], have also been proposed to restrict relaxation to a small subset of the query, and hence reduce the number of relaxed queries. However, this requires from the user to anticipate where relaxation can be useful. The above approaches [START_REF] Hurtado | Query Relaxation in RDF[END_REF][START_REF] Huang | Approximating query answering on RDF databases[END_REF] put some limitations on the relaxation steps that can be applied. Triple patterns can be generalized by relaxation according to RDFS inference but generally can not be removed from the query. URIs and literals cannot always be replaced by variables, which limits the generalization capabilities. Other approaches [START_REF] Dolog | Relaxing RDF queries based on user and domain preferences[END_REF][START_REF] Elbassuoni | Query Relaxation for Entity-Relationship Search[END_REF] present powerful relaxation frameworks, but they do not evaluate their efficiency or only generate a few relaxed queries.

Application of Concepts of Neighbors to Query Relaxation

Query relaxation takes as input an RDF graph and a query Q, and returns a (partially) ranked list of approximate answers. We have seen above how an RDF graph can be mapped to a graph context, mapping RDF nodes to objects, classes and properties to attributes, and triples to incidences. Existing work on query relaxation almost exclusively consider conjunctive queries, which are equivalent to our projected graph patterns (PGP). The problem of query relaxation can therefore be formulated in the framework of Graph-FCA. Given a graph context K = (O, A, I) and a PGP Q = [x ← P ], an approximate answer of Q in K is a tuple of objects v that is an answer of a generalized query Q ′ , i.e.

Q ′ ⊆ P GP Q ∧ v ∈ ans(Q ′ ). By Definition 7 of ans, this is equivalent to say Q ′ ⊆ P GP Q ∧ Q ′ ⊆ P GP Q(v), which implies that Q ′ ⊆ P GP Q ∩ P GP Q(v).
Among the many possible relaxed queries Q ′ , one prefers the least relaxed query, hence the most specific relaxed query

Q ′ = Q ∩ P GP Q(v).
We can make a concrete instance out of the query Q = [x ← P ] by making a new object out of each variable, and a new incidence out of each pattern element, so that we get an augmented graph context where the projected variables x become a new instance u. Now, the relationship between the query, the relaxed query and the approximate answer becomes that of a conceptual distance: u is the query instance that represents the relaxed query, v is a candidate instance that represents an approximate answer, and the intension of the conceptual distance int(δ(u, v)) = Q(u)∩ P GP Q(v) represents the relaxed query (the most specific one for that approximate answer). As a consequence, by computing the concepts of neighbors of the instantiation u of the query, we obtain the approximate answers as their proper extensions. The partial ordering on concepts of neighbors provides a pre-order on approximate answers. Approximate answers coming from the same proper extension are considered as equally good, and approximate answers coming from more specific concepts are considered as better. A total ordering can be obtained by combining extensional or intensional numerical similarity on concepts and a global ranking on instances. For each approximate answer, the concept intension tells us which relaxations have been applied to the query.

Compared to existing approaches of query relaxation where the time delay before finding the first approximate answers is not bounded, the partitioning algorithm computing concepts of neighbors can provide a ranking of approximate answers from the beginning. This ranking simply gets more and more accurate with runtime. Another advantage is that the number of considered relaxed queries is bounded by the number of instances -and in general much lower -rather than exponential in the size of the query. Moreover, the computation of their sets of answers is shared in part between the relaxed queries.

Experiments

We here report experiments that compare the efficiency of Concepts of Neighbors to existing approaches for query relaxation. All details can be found in [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF]. We compare four algorithms: two baseline algorithms, Relax-Enum and NodeEnum, and two variants of our algorithm, Partition and PartitionLJ. RelaxEnum is the classical approach of query relaxation, that enumerates relaxed queries and computes their answers. NodeEnum does the opposite by enumerating RDF nodes, and computing the least common subsumer between the query and the node description [START_REF] Colucci | Common Subsumbers in RDF[END_REF]. Partition and PartitionLJ are our two variants, and differ in that only the latter uses lazy joins for computing concept extensions. We consider two execution modes: NoLimit for complete computations; and MaxRelax for a limit to relaxation distance (not applicable to NodeEnum). For experiments, we use sets of queries on a few datasets of different size: 7 queries having 5 to 21 elements in their pattern on a geographical dataset (MONDIAL [START_REF] May | Information Extraction and Integration with Florid: The Mondial Case Study[END_REF], 12k triples), 7 queries having 3 to 7 elements in their pattern [START_REF] Huang | Approximating query answering on RDF databases[END_REF] on two synthetic datasets about universities (LUBM10, 1.3M triples; LUBM100, 13M triples [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF]). Results in NoLimit mode. Figure 5 compares the runtime (log scale) of all algorithms on all queries of Mondial and lubm10 in NoLimit mode. A few runtimes are missing for NodeEnum on lubm10, and for RelaxEnum and Partition on Q6 of Mondial because they are much higher than other runtimes. RelaxEnum is sensitive to the query complexity, in particular to multivalued properties. NodeEnum looks insensitive to the query complexity, but does not scale well with the number of nodes. Partition and PartitionLJ are always more efficient -or equally efficient -and the use of lazy joins generally makes it even more efficient. On lubm10, PartitionLJ is typically one order of magnitude more efficient than RelaxEnum. It can also be observed that PartitionLJ scales well with data size because from Mondial to lubm10, a 100-fold increase in number of triples, the median runtime also follows a 100-fold increase, from 0.01-0.1s to 1-10s. This linear scaling is verified on lubm100 (not shown) where the runtimes are all 10 times higher. We want to emphasize that it is encouraging that the full relaxation of a query over a 1.3M-triples dataset can be done in 4s on average.

Results in MaxRelax mode. In practice, one is generally interested in the most similar approximate answers, and therefore in the relaxed queries with the smaller relaxation distances. It is therefore interesting to compare algorithms when the relaxation distance is bounded. Figure 6 compares RelaxEnum and PartitionLJ on lubm10 queries for increasing values of maximal relaxation distance, here from 1 to 7 relaxations. As expected, the runtime of Relax-Enum grows in a combinatorial way, like the number of relaxed queries, with the relaxation distance. On the contrary, the runtime of PartitionLJ grows more quickly for 1-4 relaxations, and then almost flattens in most cases. The flattening can be explained by several factors. The main factor is that most relaxed queries are redundant and are pruned by the partitioning algorithm. Another factor is that query evaluation is partially shared between different queries. That sharing is also the cause for the higher cost with 1-4 relaxations. In summary, PartitionLJ scales very well with the number of relaxations, while RelaxEnum does not. This is a crucial property for similarity search where many relaxation steps are necessary.

Number of relaxed queries. The efficiency of Partition and PartitionLJ is better understood when comparing the number of concepts of neighbors (C-N) to the number of relaxed queries (RQ). Over the 7 lubm10 queries, there are in total 59 C-Ns out of 2899 RQs, hence a 50-fold decrease.

Knowledge Graph Completion

The open nature of KGs often implies that they are incomplete, and a lot of work have studied the use of machine learning techniques to complete them. The task of knowledge graph completion, aka. link prediction [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF], consists in predicting a missing edge between two entities: e.g., predicting that the director of the film Avatar is James Cameron. In Graph-FCA term, given a graph context K = (O, A, I) representing a knowledge graph, a binary attribute r ∈ A representing a relation, and an object u ∈ O representing an entity, the objective is to predict the missing entity in an incomplete incidence r(u, ?) or r(?, u). Because of the symmetry between the two cases, we only consider in the following the case r(u, ?) where the head entity u is fixed and the tail entity v is to be predicted.

This section is a summary of a previous work [START_REF] Ferré | Application of Concepts of Neighbours to Knowledge Graph Completion[END_REF] on the exploitation of Concepts of Neighbors for knowledge graph completion. Indeed, the partitioning of the KG entities into concepts of neighbors provides a valuable basis for different kinds of inferences, like the inference of the missing node of an incomplete edge. One advantage is that inference can be performed without training a model beforehand, so that the proposed approach can easily cope with dynamic knowledge graphs. Another advantage is that explanations can be provided for each inference, based on the intent of concepts of neighbors. Finally, the experimental results show competitive performance w.r.t. state-of-the-art approaches in link prediction.

Related Work

Nickel et al. [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF] have identified two kinds of approaches that differ by the kind of model they use: latent feature models, and graph feature models. The former is by far the most studied one. Latent feature models learn embeddings of entities and relations into low-dimensional vector spaces, and then compute the truthfulness score of edges r(u, v) by combining the embeddings of the two entities and the embedding of the relation: e.g., TransE [START_REF] Bordes | Translating Embeddings for Modeling Multi-relational Data[END_REF], RGNN [START_REF] Schlichtkrull | Modeling Relational Data with Graph Convolutional Networks[END_REF], ConvE [START_REF] Dettmers | Convolutional 2D Knowledge Graph Embeddings[END_REF]. Graph feature models, also called observed feature models, make inferences directly from the observed edges in the KG: e.g., Random walk inference [START_REF] Lao | Random Walk Inference and Learning in A Large Scale Knowledge Base[END_REF], Horn clauses AMIE 3 [START_REF] Lajus | Fast and Exact Rule Mining with AMIE 3[END_REF], AnyBURL [START_REF] Meilicke | Anytime Bottom-Up Rule Learning for Knowledge Graph Completion[END_REF]. Latent feature models have the best performance, but they do not provide explanations for their inferences, unlike graph feature models. The key novelty of Concepts of Neighbors is that they offer an instance-based approach rather than a modelbased approach. This implies that there is no need for a training phase, and that all the learning effort is done at inference time.

Application of Concepts of Neighbors to Link Prediction

Given an incomplete incidence r(u, ?), we compute the concepts of neighbors (C-Ns) of head entity u. From there, we infer a ranking of candidate entities for the tail entity v. In fact, as r is not involved in the computation of C-Ns, many target relations can be inferred at nearly the same cost as a single relation. Indeed, the main cost is in the computation of C-Ns. Moreover, the latter is easily controlled because the computation algorithm is any-time (see Section 2).

The principle of C-N-based inference is to generate a ruleset for each concept of neighbors δ l ∈ C -N (u). Those rules are similar in nature to those of AMIE+ or AnyBURL except that only rules that are matched by the head entity u are generated. Indeed, the bodies of generated rules are intensions of C-Ns, which are subsets of u's description (int(δ l ) ⊆ P GP Q(u)). From the concept intension int(δ l ) = Q l = [x ← P l ], with x l the tuple of variables in P l , we generate two kinds of inference rules ρ:

1. by-copy rules: ρ := P l → r(x, v), for each v ∈ O; 2. by-analogy rules: ρ := P l → r(x, y), for each y ∈ x l , y ̸ = x.

Inference by copy. The first kind of rules (by-copy rules) predicts that when an entity matches P l as x, it is related to the entity v through the relation r. As u matches P l as x by definition of concepts of neighbors, the rule infers that u is related to v. In formula, the set of inferred entities is simply V ρ = {v}. Of course, the strength of the inference depends on the support and confidence of the rule ρ, which are defined as follows.

supp(ρ) = |ans([x ← P l , r(x, v)])| conf (ρ) = |ans([x ← P l , r(x, v)])| |ans([x ← P l ])| + λ
Like this is done in AnyBURL [START_REF] Meilicke | Anytime Bottom-Up Rule Learning for Knowledge Graph Completion[END_REF], we use a constant λ ≥ 0 as an additive Laplace smoothing, in order to favor rules with larger support. The principle of inference by copy is that the tail entities v to be predicted for u can be copied from the tail entities of u's neighbors. For example, if incidence parent(Charlotte, Kate) is missing in the example graph of Figure 1, it can be inferred from some of her closest neighbors: "From one hand, George is similar to Charlotte because he has William as a father; from the other hand George's mother is Kate; so Charlotte's mother is expected to be Kate too" (support=1, confidence=1/(2 + λ)).

Inference by analogy. The second kind of rules (by-analogy rules) predicts that when a pair of entities match P l as x and y, they are related through r.

As u matches P l as x by definition of concepts of neighbors, the rule infers that u is related through r to any entity v that matches P l as y when x = u. In formula, the set of inferred entities is V ρ = {v | (u, v) ∈ ans([x, y ← P l ])}. Like above, the strength of the inference depends on the support and confidence of the rule, whose definitions are similar to by-copy rules except that they involve pairs of entities instead of entities. The principle of inference by analogy here relies on the observation that "u is to v as x is to y". By observing that pairs (x, y) that match pattern P l often satisfy r(x, y), one can predict the missing entity in r(u, ?) to be any entity v such that pattern P l is matched for x = u and y = v. For example, assume in the example graph that George and Charlotte are only known to have for father William, and that Kate is only known to be William's spouse, i.e. incidences parent(George, Kate) and parent(Charlotte, Kate) are missing. Here, inference by copy for the parents of Charlotte would only produce Charles and Diana, using William and Harry as similar entities (see C-N 4 in Figure 2). The intension of the conceptual similarity of Charlotte with William and Harry is

Q W H = [x ← P W H ]
P W H = parent(x, y), man(y), spouse(y, z), spouse(z, y), woman(z), saying that "they have a father married to a woman". From there, the following by-analogy rule can be generated: P W H → parent(x, z). This rule states that "any female spouse (wife) of a male parent (father) is a parent". Applying this rule to Charlotte (and equivalently to George) leads to the inference of parent(Charlotte, Kate) because Kate is indeed the wife of William, who is the father of Charlotte. It is noteworthy here that Kate is predicted to be a parent, although she never appears as a parent in the incomplete graph. This is not possible with inference by copy.

Aggregation of inferences. Given an incomplete triple r(u, ?), the output of a link prediction system is a ranking of entities v. Rankings of entities are evaluated with measures such as Hits@N (defined as 1 if the correct entity is among the first N entities, 0 otherwise), and MRR (Mean Reciprocal Rank, the average of the inverse of the rank of the correct entity, in range [0, 1]).

The question that remains to be addressed is how to aggregate inferences from all above rules into a global ranking. Indeed, the known entity u leads to multiple concepts of neighbors, each concept of neighbors δ l generates multiple rules, and each rule ρ infers a set V ρ of candidate entities v. The same candidate v may be inferred by several rules, possibly generated from different concepts. The idea is to combine the measures of rules to give a score to each candidate v, in order to get a global ranking. We reuse the Maximum Confidence (MC) score introduced in AnyBURL [START_REF] Meilicke | Anytime Bottom-Up Rule Learning for Knowledge Graph Completion[END_REF]. In short, the score of an entity v is the list of the confidences of the rules that inferred it, in decreasing order.

Experiments

The approach based on Concepts of Neighbors has been compared to state-of-the-art approaches -both latent-based and rule-based -on classical benchmarks for link prediction: WN18, WN18RR, FB15k, FB15k-237.

The main results are shown in Table 2, and all details about the experiments are available in [START_REF] Ferré | Application of Concepts of Neighbours to Knowledge Graph Completion[END_REF]. ComplEx-N3 (latent-based) clearly outperforms other approaches on all datasets except WN18 where C-N outperforms other approaches on the three measures (MRR, Hits@1, Hits@10). C-N comes second on FB15k, and remains close to the best approaches on WN18RR. On FB15k-237, the MRR delta is -0.074 with ComplEx-N3, but only -0.004 with AnyBURL, the best rule-based approach. It is noteworthy that C-N is competitive with AnyBURL because, whereas AnyBURL rules are computed in a supervised manner (knowing the target relation r), C-N concepts are computed in an unsupervised manner (i.e, only knowing the head entity u). This implies that the concepts of neighbors of an entity can be computed once, and used for many different inference tasks, e.g. predicting links for several target relations.

The MONDIAL geographical dataset [START_REF] May | Information Extraction and Integration with Florid: The Mondial Case Study[END_REF] was used to evaluate how complementary by-copy and by-analogy rules are. Although by-analogy rules appear more powerful than by-copy rules with an MRR equal to 0.424 vs 0.286, it is beneficial to combine the two as this raises the MRR to 0.455. We report on an example of inference in the MONDIAL geographical dataset [START_REF] May | Information Extraction and Integration with Florid: The Mondial Case Study[END_REF]. The Islay island is correctly predicted to belong to Inner Hebrides (score=0.34 0.34 0.31) by two by-analogy rules (supp=54, conf=0.34) and one by-copy rule (supp=11, conf=0.31). The five subsequent predictions are other UK islands that were inferred by the same first and second byanalogy rules, and by another third rule with lower confidence. The top-1 rule is the following one. locatedIn(x, u), locatedIn(z, u), belongT oIslands(z, y), locatedInW ater(x, v), (v = AtlanticOcean) → belongT oIslands(x, y)

It is a by-analogy rule that says that an island x belongs to islands y if x shares a location u (here, UK) with another island z that belongs to y, and x is located in the Atlantic Ocean. Apart from the specialization to the Atlantic Ocean, this rules makes sense because if two islands are located in a same place, e.g. a same country, there is a good chance that they belong to the same islands.

Relation Extraction

Relation extraction is a classical task in machine learning for natural language processing (NLP). This task consists into predicting which type of relation -if any -links two given entities (a subject and an object) in a natural language text. For example, in the sentence "The University of Rennes is French", with University of Rennes tagged as subject and French as object, the objective is to identify that the relation nationality links the subject to the object.

This section gathers the results of two previous studies [START_REF] Ayats | Extracting Relations in Texts with Concepts of Neighbours[END_REF][START_REF] Ayats | A Two-Step Approach for Explainable Relation Extraction[END_REF]. It presents a method based on concepts of neighbors for relation extraction, and shows positive results of this approach, being competitive with the state of the art and presenting interesting interpretability properties. First, the related work about the relation extraction task is presented. Second, we explain how concepts of neighbors can be used for relation extraction. Finally, we summarize the experiments conducted and the results obtained, pointing its results both on the quantitative aspect and the advantages in terms of interpretability. Note that the dataset used in the experimental part is in English, but this work is relatively independent of the language, and could be applied to other languages, as long as the language structure allows for tools similar to those used to exist, and as long as those tools have been developed.

Related Works

Initially, as for many NLP tasks, the first approaches proposed for relation extraction used handmade rules applied to sentences parsed thanks to handmade grammars. As the design of those rules and grammars were time-consuming for a hardly reliable result, those methods were abandoned to the profit of supervised machine learning approaches, using annotated corpora. For more details, see the review [START_REF] Grishman | Twenty-five years of information extraction[END_REF]. During the last decade, with the important progresses in deep learning, neural network-based approaches appeared: convolutional neural networks [START_REF] Nguyen | Relation Extraction: Perspective from Convolutional Neural Networks[END_REF], then LSTM [START_REF] Xu | Classifying Relations via Long Short Term Memory Networks along Shortest Dependency Paths[END_REF], and graph convolution networks [START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF][START_REF] Wu | Simplifying Graph Convolutional Networks[END_REF]. Today, the state of the art is dominated by transformer-based pre-trained language models, such as BERT and its variations [START_REF] Wang | Open Information Extraction with Meta-pattern Discovery in Biomedical Literature[END_REF][START_REF] Yamada | LUKE: Deep Contextualized Entity Representations with Entity-aware Self-attention[END_REF][START_REF] Lyu | Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021[END_REF]. Despite their impressive results, those approaches, as most deep-learning approaches, act as black boxes and lack interpretability.

Most relation extraction datasets and approaches use a negative class, or no_relation class, collecting all the task instances (i.e., pairs of named entities) for which no relation exists between the subject and the object. Therefore, the relation extraction task can be divided in two steps: a relation detection step, charged to determine if a given instance expresses a relation, and a relation classification step, in which the instances expressing a relation are classified among different relation types. Such a two-step approach is introduced in [START_REF] Mallart | Active Learning for Interactive Relation Extraction in a French Newspaper's Articles[END_REF]. As the Concepts of Neighbors approach is based on the computation of similarities between instances, and as the instances of the negative class have no reason to be similar one to each other, the method developed below is suited for relation classification, and should be coupled with a relation detection module to perform proper relation extraction, as presented in [START_REF] Ayats | A Two-Step Approach for Explainable Relation Extraction[END_REF].

Application of Concepts of Neighbors to Relation Classification

The task of performing relation classification on natural text sentences with concepts of neighbors can be divided into three steps. First, the textual data have to be transformed into relational data. Then, Concepts of Neighbors have to be computed for each instance to be classified. Finally, a ranking method has to be defined to infer a prediction from the set of concepts of neighbors.

Sentence Modeling. The first step is to model each instance of the relation extraction dataset as a graph. An instance is a sentence that is annotated with the position and type of two entities (subject and object), and that is labeled with the expected relation type between the two entities. The modeling presented in this section has both syntactic and semantic features, and relies on an NLP toolkit (such as Stanford CoreNLP [START_REF] Manning | The Stanford CoreNLP Natural Language Processing Toolkit[END_REF]) and on WordNet [START_REF] Miller | WordNet: An Electronic Lexical Database[END_REF], a hierarchical lexical database for English. The modeling is made as an RDF graph, because this formalism is flexible, permits type relaxation, and the CONNOR library (see 5.3) has been developed for computing concepts of neighbors in RDF graphs.

The sentence is first processed with an NLP pipeline (composed of a tokenizer, a lemmatizer, a part-of-speech tagger, a dependency tree parser and a named entity recognizer) in order to extract linguistic knowledge. Then, the result of this processing is used to create a syntactic modeling of the sentence. An RDF entity with a unique id is created for each token and each named entity of the sentence. Then the dependency relations between those tokens and named entities are added in order to represent the syntactic tree of the sentence. Finally, RDF types are added to the model for representing the part-of-speech tags, the lemmas, the named entity positions and types. Figure 7 shows the syntactic modeling of the sentence "The University of Rennes is French".

To this syntactic modeling, we add a semantic layer, using WordNet. To do so, an RDF ontology is built on the lemmas of the verbs and nouns: for each lemma, a supertype is created for each synset containing this lemma, and for each synset, a supertype is created for each of its hypernym synsets. This allows for type relaxation over the lemmas, and therefore identification of semantically-close lemmas. Figure 8 represents an extract of the type hierarchy that is generated by the lemmas university, school, religion and faith. It can be seen that the lemmas university and school can both be relaxed into the synset educational institution, and that those four lemmas can all be relaxed into the synset institution.

By combining the syntactic modeling of sentences and the semantic relaxation mechanism over the lemmas, we obtain a syntactic and semantic modeling of natural language sentences as RDF graphs in which each token and named entity is identified by a unique RDF entity for which the computation of concepts of neighbors is possible.

Use of Concepts of Neighbors. For a given instance, the objective is to discover which are the other instances of the training dataset that are the more similar, and then predict a relation type from them. As an instance is a (subject, object) couple, we use binary concepts of neighbors, whose extensions are sets of similar (subject, object) couples.

In addition, a mechanism similar to the RECENT paradigm presented in [START_REF] Lyu | Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021[END_REF] is used: before computing the concepts of neighbors of a (subject, object) couple, we deduce from its subject and object types the relation types that are compatible with this query instance. Then we simply limit the set of candidate instances to the training instances labelled with a compatible relation type.

Scoring Method for Relation Classification. For each instance, a set of rules predicting the different relation types is constructed from its set of concepts of neighbors: for each relation type r and for each concept of neighbors δ, we consider a rule R r,δ having for head the relation type and for body the intension of the concept, and we compute its confidence in the classical way: Then, similarly to Section 6.2, the MC scoring method is used on those confidences to sort the possible predictions.

From Relation Classification to Relation Extraction. As explained before, the method presented above is suited for relation classification but not for relation extraction, and therefore it must be combined with a relation detection module to perform full relation extraction. In [START_REF] Ayats | A Two-Step Approach for Explainable Relation Extraction[END_REF], this method is combined with LUKE [START_REF] Yamada | LUKE: Deep Contextualized Entity Representations with Entity-aware Self-attention[END_REF], a transformer-based pre-trained language model fine-tuned on the relation detection task in order to obtain a two-step relation extraction method.

Experiments

This section successively presents the dataset used to evaluate this approach, the comparison points used during those evaluations, and the results of these evaluations. Comparison Points. For relation classification, as the experiments are made on a subset of TACRED, the comparison is made with a naive baseline. For a given example, this baseline simply predicts the most probable relation type in the dataset according to the types of the subject and object.

For relation extraction, the comparison is made with pre-existing deeplearning relation extraction systems. Two of them use transformer-based pre-trained language models (LUKE [START_REF] Yamada | LUKE: Deep Contextualized Entity Representations with Entity-aware Self-attention[END_REF] and BERT-LSTM-Base [START_REF] Shi | Simple BERT Models for Relation Extraction and Semantic Role Labeling[END_REF]), while GCN and C-GCN use graph convolution networks over the dependency tree [START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF].

Results. On the relation classification task, several experiments were conducted. As explained in Section 5.1, our algorithm is anytime, and therefore experiments were made using different timeouts. Table 3 presents the accuracy scores for both our approach (with a timeout range from 10 seconds to 20 minutes) and the baseline. It can be seen that, whatever is the timeout, [START_REF] Yamada | LUKE: Deep Contextualized Entity Representations with Entity-aware Self-attention[END_REF] 72.7 BERT-LSTM-Base [START_REF] Shi | Simple BERT Models for Relation Extraction and Semantic Role Labeling[END_REF] 67.8 Ours 66.9 C-GCN [START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF] 66.4 GCN [START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF] 64.0 our approach outperforms the baseline. In addition, this shows that for a timeout over 120 seconds, the accuracy saturates: the score of 83.6% seems to be the best achievable score here, whatever the timeout.

On the relation extraction task, experiments were conducted by combining our relation classification method with a relation detection module, as presented previously. The results obtained are presented in Table 4. It can be seen that, even if our approach cannot compete with state-of-the-art transformer-based deep learning approaches, it outperforms approaches such as GCN or C-GCN, which rely on a similar representation of the text.

However, the main asset of this approach for relation extraction is not quantitative but qualitative, and rely on interpretability: for each positive prediction, we can obtain the list of rules from which this prediction was made, and use it as an explanation of the prediction. Let us take for example the sentence "Sollecito has said he was at his own apartment in Perugia, working at his computer." Our system predicts that between the subject his and the object Perugia, a relation is detected and is of type per:city_of_residence. If we look to the rules of high confidence that predicted this relation type, we find a rule of body presented Figure 9. This rule body can be interpreted as:

• The subject has lemma he and is the possessor of an apartment;

• The object is the name of a city in which there is something.

We can effectively claim that such a rule seems reasonable to predict with a good confidence relation per:city_of_residence.

Conclusion

In this article we have presented the Concepts of Neighbors, an FCAbased approach for instance-based learning on relational data. This approach, based on Graph-FCA (an extension of FCA for relational data), provides a symbolic notion of distance between entities (or tuples of entities), and therefore allows for inference tasks similarly to k-Nearest-Neighbors. An efficient anytime algorithm has been developed for the computation of concepts of neighbors, based on the progressive partitioning of the set of potential neighbors into concepts and on a lazy version of the join operator. CONNOR, a Java implementation of this method on RDF graphs, has been presented, and is available as open-source code. Finally, we have shown the versatility of concepts of neighbors by presenting three applications on three different tasks. Two applications work on knowledge graphs, while the other works on graph representations of texts.

In future works, other kinds of applications of Concepts of Neighbors on Graph-FCA can be considered. For instance, in the semantic web field, Concepts of Neighbors can be used on knowledge graph entities for knowledge graph alignment or entity clustering. In the NLP domain, the syntacticsemantic modeling of text as RDF graphs, combined to the Concepts of Neighbors, could be used for other tasks such as semantic similarity. More generally, this method could be extended to other relational data types, such as molecular graphs. In addition, the concepts of neighbors approach can be adapted to other extensions of FCA, and therefore this instance-based learning approach could be applied to any data that could be formalized in an FCA framework.

  where O is a set of objects, A a set of attributes and I ⊆ O × A is an incidence relation between objects and attributes. For each object o ∈ O, we define I(o) = {a ∈ A | (o, a) ∈ I} as the description of o.

Figure 1 :

 1 Figure 1: (a) Graph context representing the British royal family (b) PGP representing the sibling relationship between x and y

Definition 4 .

 4 Let K = (O, A, I) be a formal context, X ⊆ O a set of objects, and Y ⊆ A a set of attributes. The pair (X, Y ) is a formal concept if and only if inst(Y ) = X and prop(X) = Y . X is called the extension of the concept and Y the intension.

Definition 5 .

 5 A graph context is a triple K = (O, A, I) where O is a set of objects, A a set of attributes and I ⊆ O * × A is an incidence relation between tuples of objects and attributes.

Figure 1 (

 1 Figure1(a) is a graphical representation of a graph context. It represents an excerpt of the British royal family. The boxes are the objects (e.g. Charlotte or Harry), the labels next to boxes are unary attributes (e.g. man, woman), and the arrow labels are binary attributes (e.g. parent or spouse). It is also possible to have n-ary attributes with n > 2 in Graph-FCA, although they are not used in what follows. The unary incidence ((Kate), woman) ∈ I says that Kate is a woman; we call it a node label and also write it woman(Kate) for readability and by analogy to predicate logic. The binary incidence ((George, Kate), parent) ∈ I says that Kate is a parent of George; we call it a labeled edge and also write it parent(George, Kate).Most models of knowledge graphs can be translated accurately to graph contexts: e.g., the RDF graphs of the Semantic Web[START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF], conceptual graphs[START_REF] Sowa | Conceptual structures: Information processing in mind and machine[END_REF], RCA contexts[START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF]. For simple entity-relation KGs, entities translate to objects, relations to binary attributes, and triples to binary incidences. For translating RDF graphs to graph contexts, we abstract each URI and blank node x into an object o x , and we add the following incidences to the context:

  the least general generalization of the two queries. Besides, we define the description of the tuple of objects o as the PGP Q(o) = (o, P (o)), where P (o) ⊆ I is the subset of incidences that are transitively connected to any element of o. It is the union of the connected components of the graph context containing the elements of o, rooted in those elements. It plays the same role as I(o) in FCA.

Figure 2 :

 2 Figure 2: Concepts of Neighbors of Charlotte

  ): u = Charlotte and V = O. The initial pre-concept contains the seven persons in the context, from Charles (C) to Charlotte (A). The first specialization uses the incidence woman(Charlotte), separating the women (Diana, Kate and Charlotte) on Algorithm 1 P artition(K, u, V ) Require: A graph context K = (O, A, I) Require: An arity k > 0, a query instance u ∈ O k , and candidate instances V ⊆ O k Require: An optional timeout Ensure: A collection of pre-concepts C partitioning V w.r.t conceptual distance to u 1: C ← {C init } 2: while no timeout and there is a pre-concept C l ∈ C such that I l ̸ = ∅ do 3:

Figure 3 :

 3 Figure 3: Trace of the partition algorithm applied on the graph context in Figure 1 with u = Charlotte and V = O. Pre-concepts are shown via their extension, with the proper extension on the left and the remainder on the right, if any. Objects are abbreviated by their initial, except for Charlotte (A). The same abbreviations in lowercase are used as variables in the incidences used for pre-concept specialization. Boxed pre-concepts at the leaves are the concepts of neighbors, and the number at their right is the extensional numerical distance.

Figure 4 :

 4 Figure 4: Match-tree before and after lazy join with incidence i * = parent(g, k).

Figure 5 :

 5 Figure 5: Runtime (seconds, log scale) per algorithm and per query for Mondial (left) and lubm10 (right).

Figure 6 :

 6 Figure 6: Runtime (seconds) per algorithm and per lubm10 query for increasing maximum relaxation distance (1 to 7). Full height bars represent runtimes over 20 seconds.

  supp(ρ) = |ans([x, y ← P l , r(x, y)])| conf (ρ) = |ans([x, y ← P l , r(x, y)])| |ans([x, y ← P l ])| + λ

Figure 7 :Figure 8 :

 78 Figure 7: Syntactic modeling of the sentence "The University of Rennes is French"

  conf (R r,δ ) = |{(s, o) ∈ δ.ext | r(s, o)}| |δ.ext|

  Dataset.The following experiments were conducted on TACRED[START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF], a standard widely-used dataset for Relation Extraction proposed by Stanford University and composed of 100,000 instances (split between train, development and test instances) classified among 41 relation types and a no_relation negative class. Issued from the TAC KBP challenge, those instances consist into sentences in English, mainly issued from newspaper, annotated by crowdsourcing. In order to reflect real-world usage, this dataset contains 79.5% negative examples. For evaluation on the relation classification subtask, only the positive examples are considered, while the whole dataset is used for experiments on the relation extraction task.

Figure 9 :

 9 Figure 9: An explanation for the inference of relation per:city_of_residence

Table 1 :

 1 Example of a formal context where the set of objects is an excerpt of the British royal family.

  modified // update of local join 6: end for 7: if D ∩∆ * ̸ = ∅ then // if this node defines a variable of the new element 8: if i * not yet inserted in T then // insert new node, if not yet inserted

	9:

Table 2 :

 2 MRR performance of representative approaches on link prediction benchmarks

		WN18 WN18RR FB15k FB15k-237
	#triples	151k	95k	592k	310k
	ConvE	0.942	0.460	0.745	0.316
	ComplEx-N3 0.950	0.480	0.860	0.370
	AnyBURL	0.950	0.480	0.830	0.300
	C-N	0.969	0.469	0.849	0.296

Table 3 :

 3 Accuracy on the relation classification task, compared to baseline.

	Timeout (s)	10	20	30	60	120 300	600 1200
	Ours	82.0 82.1 82.7 82.9 83.4 83.6 83.6 83.6
	Baseline					80.4

Table 4 :

 4 F-score for several Relation Extraction methods on TACRED

	Method	F1 score
	LUKE

https://bitbucket.org/sebferre/graph-fca/

By abuse of notation, we allow tuples of variables to be used as sets of variables.

Accessible here: https://gitlab.inria.fr/hayats/CONNOR

https://jena.apache.org/

Acknowledgements

The authors wish to thank Nicolas Fouqué (CNRS) for his work on the first Java implementation of the algorithms for the computation of Concepts of Neighbors, as well as Pierre Nunn (ENS Rennes) for his experimental and development work on enhancing these algorithms.

The authors are listed in alphabetical order. This research is supported by ANR projects SmartFCA (ANR-21-CE23-0023) and AI4SDA (ANR-20-THIA-0018).