Léa Guizol

Madalina Croitoru

Michel Leclère

On Link Validity and entity resolution Research report RR-11010

The Entity Resolution problem has been widely addressed in the literature. In its simplest version, the problem takes as input a knowledge base composed of records describing real world entities and outputs the sets of records judged to correspond to the same real world entity. More elaborated versions take into account links amongst records representing relationships between the entities which represent. However, none of the approaches in the literature question the validity of certain links between records. In this paper we highlight this new aspect of "link validity" in knowledge bases and show how Entity Resolution approaches should take this aspect into consideration.

Introduction

Knowledge base systems (KBs) allow to store and query an abstract model of the real world using a representation and reasoning language based on formal logic. One of the main problem when managing such a system is to ensure that the users of the system share the same "representation/interpretation" relationship between the conceptual primitives of the language and their corresponding notions in the real world. The development of domain ontologies which fix the vocabulary for classes and properties and specify, by axioms (some specific formulas), their semantics establishes a first solution to this problem. For individual entities, this solution is not applicable. Indeed, we have to continually reference new individuals, and the number of individual references to manage can reach several thousand (or million) individuals. To tackle this problem, a record is associated with each individual reference that specifies the characteristics of the referred individual entity. At least, this record contains, generally a name attribute which indicates the names which are used in the real world to designate the corresponding entity and a type attribute which indicates its class in addition to the reference which identifies the record. For instance, a record corresponding to a literary text contains the "work" class as type and a title as name.

Often, users of the knowledge base own very little information about an individual entity and this information is rather contextual. For instance, when a user inserts a new book in a bibliographic base, often the only information (s)he has about author, the author's name on the cover. Unfortunately names don't identify a real world entity, neither its corresponding record. This is due to abusive use of abbreviations, variants, homonyms, etc. As a matter of consequence, many records (and thus references) in the knowledge base represent the same individual entity (real world).

For this purpose, the Entity Resolution problem has been widely addressed in the literature. The problem takes as input a knowledge base composed of records (identified by references which represent a real world entity) usually implemented using relational inspired models such as relational databases or data warehouses (semi-structured approaches as in graphs, triple representations etc. have also been investigated ). The output of an Entity Resolution problem is, in this case, the knowledge base references corresponding to the same real world entity. Some approaches go further and propose repairs to the knowledge base (see for instance [START_REF] Benjelloun | Swoosh: a generic approach to entity resolution[END_REF] for merge approaches).

Since the paper of Newcombe [START_REF] Newcombe | Automatic linkage of vital records[END_REF], there have been hundreds of approaches addressing the problem [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. Ironically, the Entity Resolution (ER) problem is encountered under several different names: Record Linkage (e.g. [START_REF] Winkler | Overview of record linkage and current research directions[END_REF]), Record Matching (e.g. [START_REF] Kan | Record matching in digital library metadata[END_REF]), Reference Reconciliation (e.g. [START_REF] Saïs | Reconciliation de references : une approche logique adaptee aux grands volumes de donnees[END_REF]), Entity Resolution (e.g. [START_REF] Bhattacharya | Entity Resolution in Graphs[END_REF]), Entity Matching (e.g. [START_REF] Bouquet | An entity name system (ens) for the semantic web[END_REF]), Name Disambiguation (e.g. [START_REF] Smalheiser | Annual Review of Information Science and Technology (ARIST)[END_REF]), Data Interlinking (e.g. [START_REF] Wölger | Interlinking dataapproaches and tools[END_REF]).

As a common denominator of the ER approaches above, the KB references to be resolved are either [START_REF] Arasu | Large-scale deduplication with constraints using dedupalog[END_REF] linked with other knowledge base references considered to be correct (from an ER view point) or, (2) linked amongst themselves. Special approaches dedicated to the first case have already been proposed in the literature (see for instance [START_REF] Chaudhuri | Robust and efficient fuzzy match for online data cleaning[END_REF]). Similarly, when the references to be resolved are interlinked (cf. second case) special propagation techniques were developed [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. Getoor and colleagues [START_REF] Bhattacharya | Entity Resolution in Graphs[END_REF], investigate link based Entity Resolution. Partially using techniques above, the ER problem is translated into the link mining problem between references.

However, all of these techniques rely on the fundamental assumption that the references within the knowledge base are correctly linked amongst themselves. In this paper we investigate the link validation problem (whether references are correctly linked amongst themselves). This is different from the Entity Reference problem since we do not aim to say two references point to the same entity. What we aim to do, is to decide if one reference correctly points to another reference (under certain assumptions). In the light of the aspects mentioned above, this paper:

Highlights the problem of knowledge base link validity Proposes a framework allowing for both:

Checking the knowledge base link validity and,

Repairing erroneous links

To this end, we:

→ Address the link validation problem using Entity Resolution on enriched entities. → Lay down current and future work directions improving the accuracy of the previous point where criteria used for ER are given using a preference order.

Documentary Bases Link Validation

As a motivating example, we present a real world example from a documentary base manipulation use case within a joint project with ABES. Since 2001, ABES (French Bibliographic Agency for Higher Education) has been managing SUDOC 1 (University System of Documentation), a French collective catalog containing over 10 million bibliographic records. In addition to bibliographic records that describe the documents of the collections of the French university and higher education and research libraries, it contains nearly 2.4 million authority records that describe individual entities (or named entities) useful for the description of documents (persons, families, corporate bodies, events etc.). Bibliographic records contain links to authority records that identify individuals with a specific role (author, editor etc.) wrt the document described.

A typical entry of a book in SUDOC takes place as follows. The librarian has a new book to enter in the system. (S)he types in and enters the title of the book ("The Cocktail Party"), the ISBN, the number of pages and so forth. Then the librarian needs to indicate the authors of the book from the author names (s)he sees on the cover of the book (in our case "T.S. Eliot"). (S)he cannot directly type this in the author field of his entry. What (s)he needs to do it to search in the SUDOC base the person authority references that could be a good candidate for each author of the book (based on the name and surname), decide if one of the authors existing is suitable, and make the link from the bibliographic record to the authority record by indicating in the author field the reference of the selected authority. If none of the authors in the base is suitable, then the librarian will create a new authority record in the system and link the book to this new record. To continue the example of the "Cocktail Party", the librarian searches the SUDOC for "T. S. Eliot". The system, let's assume, will give three candidates: "Eliot", "T. Eliot (1958-....)" and "G. Eliot". The librarian, at this stage, can make several mistakes. Either choose"Eliot" to be linked from the "Cocktail Party" (and not consider suspicious the fact that this "Eliot" in question published both novels and mathematics books). Either choose "T. Eliot (1958-....)" (surprised that the author has been published so young, the book dating from 1974). Either, mistakenly (it is a human domain expert, after all), choose "G. Eliot". The librarian can also, if in doubt, choose to create his / her own "T.S. Elliot" person authority record. The lack of distinguishing characteristics in the authority records and the lack of knowledge about the identity of the book's author imply that the librarian's decision is mainly based of consultation of previous bibliographic records linked to each candidates (s)he considers. So any linkage error will entail new linkage errors.

When validating a knowledge base we need to distinguish between information which we are sure of, and information which is unreliable. This distinction, which is fundamental in link validation has been considered for the SUDOC scenario as follows. We consider certain the information in the authority records, the information in the bibliographic records but not the link information between bibliographic records and authority records. Therefore, what we aim for is link validation between authority records and bibliographic records. The existing links in the knowledge base (the links we question) induce a partition of bibliographic records according to authority records.

We propose to obtain other partition(s) of such bibliographic notices based on, as much as possible, certain information. This three step process is described in the following. We (1) create contextual authorities that represent the contributors in context of the documents they supposedly wrote. These contextual authorities will be clustered according to different criteria. Once (2) we obtain (one of) the "best" partition(s) (based on combining different criteria clusterings and the according order on the partitions), we (3) compare its classes with the initial classes given by the authority -bibliographic links. If there is a complete match then the knowledge base links are deemed valid. This decision is heavily relying upon the hypothesis that very similar bibliographic records (cf. different criteria) should be linked to the same authority record. This strong work hypothesis is taken given the (1) workflow librarians use for linking records and (2) the specificity of documentary bases where certain information is reliable (basic author information) and other unreliable(correctness of links towards bibliographic records). Please note that, with this hypothesis, if a person has written very different books (comics and graph theory), we will not be able to detect that both kinds of work pointing to the same person. Fig. 1. Two tables with links to be validated Let us consider the example depicted in Figure 1. The documentary base in question contains two tables: Person and Book. Each of the tables contains some records which might be erroneously linked up. For convenience of intuitive representation, on the right hand side of the picture each of the records in the person table is shown by the means of a man icon and each of books by the means of a book icon. The arrow from a "book" to a "man" aims to represent the uncertain link between the records from two tables. Also, we represent the initial partition classes given by the bibliographic -authority links. Even if links are unreliable, they bring some reliable information. We can assume, that once a bibliographic record was entered in the system, the librarian had the real name of the contributor and thus chose the appropriate authority record willingly. As explained above, the first step is to create a new table containing the joint information from the Person and Book (see Figure 2). This new table will contain records corre-sponding to the contributor-book information as given by the knowledge base links. We represent this, alternatively, as authors enriched with the book information on the right hand side of the picture. The second step would be to cluster these contextual contributor-book records with respect to different criteria (name closeness, domain closeness, publication language etc.) and once (one of the) "best" clustering obtained, to deduce that they correspond to the same real world entity. Such clustering is shown in Figure 3.

We then compare this partition to the initial partition given in Figure 1. As we can see the only link which is validated is the link from book 4 to person 2. For the other links we propose in Section 5 different ways of repair.

3 Link validation in SUDOC base

Sudoc base

The Sudoc base gathers two kinds of semi-structured records : authority records and bibliographic records. There exists different types of authority records (person, family, corporate body, work etc.). In this paper we focus on person authority records.

A (person) authority record is used to represent a person in the SUDOC knowledge base. In addition to an identifier, it contains at least a set of names used to designate the person and, possibly, dates of birth/death, sex, nationality, titles and any comments in plain text. All the other information regarding its contribution to some works (what he wrote, what domains he has contributed to etc.) are only available from the bibliographic records of the documents (s)he has (co-)authored.

A bibliographic record is used to represent a certain document in the SUDOC knowledge base. The record was created at the moment when the domain expert had a real world document exemplar in front of his eyes. Most the information (such as title, publication date, language, domain) is reliable. The contributor2 information is added by searching the system for (person) authority records corresponding to each of the names indicated as contributing of the document. If, for each candidate contributor, the existing documents (contributions) look coherent (for the human eye) with the newly entered record then the reference of the authority record is added in the "contributor" field. The role of the contributor is also added (author, supervisor, editor etc.).

Definition 1 (Authority record).

Let A a = {idP, names, lif eSpan} be the semistrutured schema for a person record. In the following, A x a denotes the domain of the attributes x. A idP a corresponds to a Sudoc internal identifier, A names a corresponds to lists of strings (the used names for this person), and A lif eSpan a correspond to the person's life period. An authority record is a tuple N a = (idP Na , names Na , lif eSpan Na ) according to this schema. The set of all authority records is denoted by N a . We also denote by N i a the authority record such as idP N i a = i. Example 1 (Authority record). Lets describe one of the authority records represented in figure 1. For N 31 a :

-idP N 31 a = 31 -names N 31 a = {Eliot, T. S. Eliot} -lif eSpan N 31 a =
= {(idP, role)|idP ∈ A idP a } and role ∈ R a fi- nite set of encoded roles). A bibliographic record is a tuple N b = (IdB N b , title N b , pubDate N b , lang N b , domain N b , contributors N b ).
The set of all bibliographic records is denoted by N b . We also denote by N i b the bibliography record such as idB N i b = i. Example 2 (Bibliographical record). Let describe one of the bibliography records represented in figure 1. For the example we took a recent edition of the book, which explain the late publication date. For N 2 b :

-idB N 2 b = 2 -title N 2 b = Romola -pubDate N 2 b = 1997 -lang N 2 b = {English} -domain N 2 b = {"English literature of XIX e "} -contributors N 2 b = {(31, author)} contributors N b = {(31,
author)} means that the person described by the authority record N 31 a (described in example 1) must had contribute to this book as the author.

Definition 3 (Link). Let N a and N b an authority, respectively bibliographic record. We say there is a contributor link from N b to N a typed r (denoted by

N b → r N a ) if and only if ∃ a role r such that (idP Na , r) ∈ contributors N b . We denote R(N a , N b )
the set of roles which links N b to N a . For a given N a , the set of all bibliographic records linked to N a , is denoted by bibliography(N a ).

Cf. the above definition, bibliography(N a ) represents all the documents the person represented by N a has contributed to, according to the SUDOC knowledge base.

Example 3 (Bibliography). According to the figure 1, bibliography(N

31 a ) = {N 2 b , N 3 b }.
We have few information in authority records, but a lot of information in bibliography records. So, when a librarian would like to link a new bibliographic record N new b to an existing authority record N a , (s)he look first at names Na , and second at the closeness between N new b and all of the bibliographic records N i b as N i b ∈ bibliography(N a ). Furthermore, links between them are uncertain, but we assume than at least one of the authority record N a name is the one of the bibliographic record

N b contributor if N b → r N a . Then, if there is not a single ({name of person}, N new b ) looks like any (names Na , N i b )|N i b ∈ bibliography(N a ), N new b
could not be linked to N a . In order to validate links, we would like to compare the initial partition of links to the best partition of links, according to the closeness of them.

Definition 4. (Initial partition) Let

A a = {N 1 a , ..., N k a } ⊆ N a a set of k author- ity records.
The initial partition of contributor links induced by A a is defined as:

P initial (A a ) = {P 1 , ..., P k } such that ∀i = 1, k, P i = {N b |N b ∈ bibliography(N i a )}.
Example 4 (Initial partition). According to the figure 1,

P initial ({N 12 a , N 31 a , N 2 a }) = {{N 12 a }, {N 31 a , N 31 a }, {N 2 a }}
We define in section 4 what we would like to partitioning (e.g. contextual authority and information in it), and how to do it.

Partitioning method

In the subsection 4.1, we will define the objets to partition for Link Validation problem in the SUDOC case. To decide wether two objects looks like each other, we will use criteria (e.g. subsection 4.3) and, because some criteria are more significant than others, we will use preference relations between them (e.g. subsection 4.5).

Contextualization of authorities

In order to implement the methodology previously introduced for addressing link validation problem, we need to compute for each document a contextual description of each of its contributors. Such a description, we call a contextual authority, will contain a set of selected informations extracted from the bibliographic record and the reliable information about the contributor from the linked authority record. We choose to select from the bibliographic record the title, the publication date, the domain, the language, the co-contributors and the role. Given the plethora of different types of considered attributes, the domain values considered are symbolic (with a total order) in order to accommodate both numerical and discrete values. From the authority record, we consider that only the names as reliable information (up to abbreviations -such as G. for Georges -or involuntary typos) since, at the time of their entry in the system, they were copied from the real world cover of the document.

-idB N 2 b = 2 -idP N 31 a = 31 -r = author -names N 31 a = {Eliot, T. S. Eliot} -title N 2 b = Romola -pubDate N 2 b = 1997 -lang N 2 b = {English} -domain N 2 b = {"English literature of XIX e "} -contributors N 2 b = {(31, author)}

Clustering of contextual authorities

All contextual authorities will be then clustered according to different criteria (at least a common name, closeness of domains, dates of publication, languages of publication, others contributors in common or a same title). There is a wide choice of Entity Resolution approaches for solving this problem [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. The result is a partition of compared objects based on closeness criteria. Please note that given our discrete value approach (as well as a preference order between criteria, explained in 4.3, we can obtain several best partitions. We choose to implement a clustering method which simulates the librarian decisions when choosing an authority. We only perform the validation on potentially erroneous links rather than on the entire base. The clustering phase is applied on contextual authorities build from a set of authorities sharing at least a common name. Definition 6 (Partition on contextual authorities). Let A a ⊆ N a a set of authority records. The set of all contextual authorities build from A a is denoted as:

CA(A a ) = ∪ Na∈Aa N b ∈bibliography(Na) r∈R(Na,N b ) {N (r,Na) b }
The set of all partitions of CA(A a ) is denoted by B(CA(A a )).

Example 6 (Set of all contextual authorities related to a set au authority records).

Let A a = {N 2 a , N 31 a } a set of authority records described on figure 1. CA(A a ) = {N The initial partition given by authority -bibliographic records can be naturally extended to contextual authorities, denoted as P initial (CA(A a )). This contextual initial partition, chosen wrt criteria described in subsection 4.3, will be used in section 5 for validation.

Criteria

Criteria used for partitioning are given by librarians. A particularity of our work is the use (cf. librarian needs) of an ordered (≻ c ) discrete value set as V = {always, V close , neutral, V f ar , never} where V close and V f ar are two totally ordered sets of closeness (respectively farness) values. The bigger (wrt the order ≻ c ) an element in V close , the closer the contextual authorities are (in terms of potentially being the same person). The bigger (wrt the order ≻ c ) an element in V f ar the farther the contextual authorities are. The value set above was chosen taking in consideration the following reasons:

the bipolarity closeness -farness; the uncertainty in V close and V f ar and the certainty of "always" and "never" and the lack of information in "neutral".

For the next examples, we denote :

-V close = {..., ⊕ ⊕ ⊕, ⊕⊕, ⊕}, with ⊕ ⊕ ⊕ ≻ c ⊕⊕ ≻ c ⊕, and -V f ar = {⊖, ⊖⊖, ⊖ ⊖ ⊖, ...}, with ⊖ ≻ c ⊖⊖ ≻ c ⊖ ⊖ ⊖. Definition 7 (Criterion). Let V C ⊆ V and x a given attribute type. A criterion C is a function C : A x × A x → V C .

We denote by C all criteria defined on A × A, C x all criteria defined on A

x × A x .
Example 7 (A criterion). We consider CloseByN ame a criterion ∈ C as V CloseByN ame = {⊕⊕, ⊕, neutral, ⊖}. For a, b, two contextual authority names, CloseByN ame(a, b) = ⊕⊕ means that two a and b are very closed, ⊕ that they are close enought and ⊖ that they are further. The more a and b are close, the more we prefer to say that the two contextual authority might represent the same person, wrt CloseByN ame criterion.

Let us consider a criterion on domain closeness (with the assumption that is more likely that the same person wrote books in the same domain). According to the domain values of the contextual authorities, a clustering algorithm will output several partitions of such authorities. Each class of each partition contains contextual authorities with a same / close domain. Let us now consider another criterion on title closeness. This criterion, at its turn, will output a set of partitions on the contextual authorities. How to make sense of all the partitions? Given that the elements inside each class of partition are supposed to refer to the same real world entity, we take the following approach. First, we only consider valid partitions (partitions that do not have either inside a class "impossible" closeness values or between two elements of two different classes "always" closeness values). Then, for each criterion, the partition will have as its value a tuple containing the (1) value -wrt element comparison -inside partition classes (how well it gets elements together) and (2) value -wrt element comparison -between two different classes (how well it splits far elements). Based on the values in this tuple we define a partial order between partitions. The partition partial order, on one criterion, is then extended to two (or more criteria).

For the SUDOC example, we could use several criteria as CloseByN ame, Role, and CommonContributors. However, for the rest of this question, we will use an abstract example with two criteria a and b (represented figure 4) for develop examples on partition choice wrt several criteria.

Partition wrt a criterion

We consider partitions value wrt a criterion only for valid partitions wrt a set of criteria C a , because, if a partition is not valid, it is not an acceptable solution.

Definition 8 (Valid partition). Let P = {P 1 , ..., P n } ∈ B(CA(A a )) a partition of contextual authorities build from A a . P is said a valid partition for the criteria set C a ⊆ C if and only if:

-∀ x 1 , x 2 ∈ CA(A a ), with x 1 ∈ P i , x 2 ∈ P j , i ̸ = j and ∀ x ∈ A, C ∈ (C x ∩ C a ) such that C(x[x 1 ], x[x 2 ]) = always, where x[x i ]
represents the value of the attribute of type x for the contextual authority Please note that if two contextual authorities that should be grouped together (because they might point to the same entity) have a big value returned by a criterion, we are more in agreement with the class of partition containing them both than otherwise. This "agreement" notion will be used in the following definition where the value of the partition is introduced. If elements in the same class have a bigger closeness value over V the more we agree. If elements in two different classes have a smaller farness value over V the more we agree. Therefore, we define ≻ a , an agreement partial order on V such that always ≻ a V close ≻ a neutral and never ≻ a V f ar ≻ a neutral (the order on V close is the same as ≻ c and on V f ar is the reverse order as ≻ c ). Definition 9 (Partition value wrt to a criterion). Let P = {P 1 , ..., P n } ∈ B(CA(A a )) a partition of contextual authorities build from A a and C ∈ C x a criterion. The value V al C (P) of the partition P wrt to criterion C, is the tuple (intra, inter) where:

x i . -∀ x 1 , x 2 ∈ CA(A a ), with x 1 , x 2 ∈ P i , and ∀ x ∈ A, C ∈ (C x ∩ C a ) such that C(x[x 1 ], x[x 2 ]) = never.
-intra = max ≻a {V close ∪ {neutral} ∩ {C(x[x 1 ], x[x 2 ])}}, ∀ i, j ∈ {1, ..n}, i ̸ = j, ∀ x 1 ∈ P i and x 2 ∈ P j . -inter = max ≻a {V f ar ∪ {neutral} ∩ {C(x[x 1 ], x[x 2 ])}}, ∀ i ∈ {1, ..n} ∀ x 1 , x 2 ∈ P i .
Example 9 (Partition value wrt to a criterion). For the example figure 4, let's have four partitions P all , P 1 , P 2 , P none . We introduce a partial order between two partitions with respect to one criterion. This order will privilege the the fact that we separate contextual authorities who have "reasons" to be apart: We can choose a better partition wrt a criterion C ∈ C. According to the order better C we denote the chosen best partition with respect to criterion C by Best Aa {C} . But librarians using several criteria to decide wether a bibliographical record must be linked to the same authority record than an other one (as name, others common contributors, language, domains...). Furthermore, a criterion could be more significant than an other (as name is more significant than language), or complementary with an other one (as common contributors and domain3 ). That's why we need several criteria and preferences relations between criteria to modeling how a librarian decide wether two bibliographic records are close.

Let's define relation between them and how to choose a better partition wrt to two criteria.

Preferences between criteria

In order to modeling how a librarian decide wether two bibliographic records must belong to the same person because they are very close (according to several criteria), we need to say how we consider a criterion compared with an other criterion.

Definition 11 (Complementary, Priority, Paribus Ceteris Priority).

On C × C we define the following relations:

-⋄ c ⊆ C × C, reflexive, symmetrical and transitive -> c ⊆ C × C, anti-symmetrical and transitive -≫ c ⊆ C × C, anti-

symmetrical and transitive

The first relation is the complementary relation (⋄ c ). Intuitively this relation will be used for representing the "help" one criterium can give to the other for better entity distinguishing. It is enough for ER to use one criterium or the other but having them both will result in a better ER process. It is enough we have satisfied either the same domain criterium or the co-author criterium. Either (or both) of criteria is enough for deduplication.

The second is the priority relation (> c ). For the same values we consider first the priority criterium. SameName and domain. Ideally the authors should have the same name AND the same domain but the name is a better criteria than the domain.

The third is the Paribus Ceteris priority relation (≫ c ). If same values for C i then we look for C j . Language and contributors. The contributors is a good criterion to deduplicate. If we have doubts (several partitions with equal values wrt contributor criterion) we can use the language criterion. But the language criterion is useless if the co-author criteria prefer one partition on the other ones.

-⋄ c ∩ > c = ∅; ⋄ c ∩ ≫ c = ∅ -A > c B et B ≫ c C, then A ≫ c C; -A ≫ c B et B > c C, then A ≫ c C; -A > c B et A ⋄ c C, then C > c B; -A > c B et B ⋄ c C, then A > c C; -A ≫ c B et A ⋄ c C, then C ≫ c B; -A ≫ c B et B ⋄ c C, then A ≫ c C.
Let a set of criteria C a ⊆ C and a partition P ∈ B(CA(A a )). If P is not valid (e.g. definition 8) for C j ∈ C a , P is not valid for C a , and we are not interested by is value wrt several criteria because P cannot be a solution. In the following subsection, we will compare the value of several valid partitions wrt to two criteria.

Partition Evaluation wrt Preference Enriched Criteria

Please notice that the partition order wrt to a criterion, better nr relation is not reflexive according to the definition 10. However, for the following we will need better to be reflexive. We define then ∀i, better = better nr ∪ (P i , P i ).

Definition 13 (The best partition wrt to two Independent Criteria).

Let Please note that since (1) the discrete values are used for criterion values and (2) the different criteria used for comparison are in a partial preference order, we can obtain several best partitions. In the next section, the chosen overall best partition for a set of authorities records A a and a set of criteria C a is denoted by Best Aa Ca ∈ B(CA(A a )).

Best Aa

Ca is valid for C a .

Link Validation Repair

If the classes of partitions correspond to the initial partition corresponding to the contributor links then the these links are deemed valid (it means all the contributors picked by the librarians are exactly the ones chosen by the clustering algorithm). If not, repairing options for certain cases are proposed. For this section, we will use Best(A a , C a ), the best partition of bibliography records deduced from Best Aa Ca such as :

-Best Aa Ca = {P 1 , ..., P k } -Best(A a , C a ) = {P ′ 1 , ..., P ′ k } -N i b , N j b ∈ P ′ m ∈ Best(A a , C a ) if and only if ∃N i(r,Na) b , N j(r ′ ,N ′ a ) b ∈ P m ∈ Best Aa Ca Definition 17 (Link valid). Let A a ⊆ N a be a set of authority records. A class P ∈ P initial (A a ) is link valid for a set of criteria C a ⊆ C if and only if ∃P ′ ∈ Best(A a , C a ) such that P ′ = P .
If a class of partition is link valid, then, consequently, all the links underlying this class are deemed valid. Furthermore, if all the classes of the initial partition are link valid then the knowledge base is deemed link valid.

Example 15 (Class Linked valid). Let A a = {N 12 a , N 31 a , N 2 a } be a set of authority records, and C a ⊆ C, be a set of criteria. From figures 1 and 3, we have : If the knowledge base is not link valid, we give three straightforward repair possibilities. More repair scenarios are investigated and are an inherent part of current / future work. All of the below reparation heuristics are based on the following two librarian inspired assumptions:

-P initial (A a ) = {{N 1 b }, {N 2 b , N 3 b }, {N
we only redirect bibliography -authority links within the same class of partition or to a newly created authority and we cannot redirect all bibliographic records from an authority record.

The first repair heuristic is fusion. We do this when a class P is linked to two authority records, where this two authority record are only linked to P . We fusion authority records in a joint authority record and the links will point to the newly created authority record. Some authority records will thus disappear.

Example 16 (Fusion).

Let A a = {N 12 a , N 31 a , N 2 a } be a set of authority records, and C a ⊆ C, be a set of criteria. We consider :

-P initial (A a ) = {{N 1 b }, {N 2 b , N 3 b }, {N 4
b }} (e.g. example 4), and The second repair is when two classes P 1 and P 2 of our best partition point to the same authority record N a . In this case we create two new authority records that replace the initial one and redirect links to the two authority records (in order to characterize this newly created authority records certain techniques such as the Generation of Referring Expressions can be used [START_REF] Moreau | Distinguishing answers in conceptual graph knowledge bases[END_REF]): N new1 Please note that the techniques described above are the simple intuitive cases for repair. Further scenarios can be envisaged and are currently pursued by our work.

-Best(A a , C a ) = {{N 1 b , N 2 b , N 3 b }, {N 4 b }}. P = {N 1 b , N 2 b , N

Conclusion

In this paper we investigated the link validation problem, inspired by a joint project with ABES. We pointed out the fundamental difference with the Entity Resolution problem and proposed a partitioning based approach for addressing it.

There are a number of interesting features of presented work. First, the criteria used for partitioning have the value set a totally ordered discrete set. Therefore certain numerical operations (addition, etc.) are not straightforward applicable (while very common in clustering). Thus, our "real world relatedness" intuitive semantics should be transformed into certain syntactic operations on these partitions. Certain numerical measures currently used in clustering (such as Rand's measure [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF]) where intra and inter class values are considered should be adapted to our semantic needs. Also, approaches such as Dedupalog [START_REF] Arasu | Large-scale deduplication with constraints using dedupalog[END_REF] consider clustering symbolical values. However, they do not consider different levels of closeness and farness (only considering one positive value and one negative value). Second, the (multi criteria) partitioning problem can easily be seen as a (colored) clique problem on the graph representing enriched bibliographic records as nodes. This could pave the way to interesting graph theoretic optimisations of finding the best partitions. Third, the different preference relation amongst criteria are to be investigated for further optimisation.

Last and not least, this approach needs implemented and tested. While, on the implementation end optimisation is essential (given the large number of possible partitions a naive approach takes into account), the evaluation should be thoroughly thought out in close contact with librarians.

Fig. 3 .

 3 Fig. 3. Partition of contextual contributor-book

  1888-1965 Definition 2 (Bibliographic record). Let A b = {idB, title, pubDate, lang, domain, contributors} be the semi-structured schema for a bibliographic record. In the following, A x a denotes the domain of the attribute x. A idB b corresponds to a Sudoc internal identifier; A title b corresponds to a string; A pubDate b , to a publication date; A lang b , to a subset of a finite set of encoded publication languages; A domain b , to a subset of a finite set of encoded publication domains. Please note that the contributors attribute corresponds to lists of authority's idP s coupled with their respective roles in the publication (A contributors b

Definition 5 (Example 5 (

 55 Contextual authority). Let N a an authority record and N b a bibliographic record such that N b → r N a . We define the contextual authority of N b according to N a (denoted N (r,Na) b ): N (r,Na) b = (idB N b , idP Na , r, names Na , title N b , pubDate N b , lang N b , domain N b , contributors N b ). We denote by N i(r,N j a ) b the contextual authority of N i b according to N j a . Contextual authority). Let N 31 a an authority record and N 2 b a bibliographic record respectively described in examples 1 and 2. We have N 2 b → author N 31 a , then, we can construct the contextual authority N 2(author,N 31 a ) b such as :

Example 8 (

 8 Valid partition). Let a, b be two criterium, and A, B, C, D, E be contextual authorities. We present the comparison values of criteria a and b on the graph 1 respectively 2 on figure 4. In this example, any partition of {A, B, C, D, E} is valid for C a = {a, b} because there is no ′ never ′ or ′ always ′ values of comparison for a and b criteria.

Fig. 4 .

 4 Fig. 4. Criteria graphs

Definition 10 (

 10 Partition order wrt to a criterion). Let P 1 , P 2 ∈ B(CA(A a )) two valid partitions of contextual authorities build from A a and C ∈ C x a criterion. Given V al C (P 1 ) = (intra 1 , inter 1 ) and V al C (P 2 ) = (intra 2 , inter 2 ), we define better nr C ⊆ B(CA(A a )) × B(CA(A a )) such that P 1 better nr C P 2 if and only if: -inter 1 ≻ a inter 2 or if inter 1 and inter 2 have the same value then intra 1 ≻ a intra 2 . Example 10 (Partition order wrt to a criterion). Let a set of contextual notices CA(A a ) = {A, B, C, D, E}, and a, b ∈ C, two criteria. The comparaisons values on {A, B, C, D, E} wrt a and b are shown on graph 1 and respectively graph 2 on figure 4. Let P 1 , P 2 partitions ∈ B(CA(A a )) described on example 9. We have P 1 better nr a P 2 and P 2 better nr b P 1 .

Definition 12 .

 12 Let A, B, C ∈ C. The relations ⋄ c , > c , ≫ c satisfy the following :

  Let a set of contextual notices CA(A a ) = {A, B, C, D, E}, and a, b ∈ C, two criteria. The comparaisons values on {A, B, C, D, E} wrt a and b are shown on graph 1 and respectvely graph 2 on figure 4. We consider than a ⋄ c b. The graph 3 on figure 4 shows the comparison values of {A, B, C, D, E} we use to obtain the value of a partition P wrt the complementary relations. Let P 1 = {{A, B, C}, {D, E}}, a partition ∈ B(CA(A a )) described on example 9. -V al b (P 1 ) = (⊕⊕, ⊖) (without complementary relations) -V al b (P 1 ) = V al b (P ⋄ 1 ) = (⊕⊕, neutral) (with a ⋄ c b)

  f usion(N i a , N j a ) = N new a and bibliography(N new a ) = bibliography(N i a ) ∪ bibliography(N j a ).

∈ P 1 }

 1 and bibliography(N new2 a ) = {N b |N (r,Na) b ∈ P 2 }.Example 17 (Deduplication of a authority record). Let A a = {N12 a , N 31 a , N 2 a } be a set of authority records, and C a ⊆ C, be a set of criteria. We consider :-P initial (A a ) = {{N 1 b }, {N 2 b , N 3 b }, {N 4b }} (e.g. example 4), and-Best(A a , C a ) = {{N 1 b }, {N 2 b }, {N 3 b }, {N 4 b }}. P 1 = {N 2 b }, P 2 = {N 3 b } are classes ∈ Best(A a , C a )and P 1 , P 2 are linked to the same authority record N 31 a (e.g. example 4). According to our best partition, we create two new authority records, N 31new1a and N 31new2 a as bibliography(N 31new1 a ) = P 1 and bibliography(N 31new2 a ) = P 2 . We erase N 31 a . Last, let P , a class of the best partition and N a , an authority record such as bibliography(N a ) ⊆ P . We also have a bibliographical record N b pointing to an other authority record N ′ a such as bibliography(N ′ a ) ̸ ⊆ P and N b ∈ P . Then we redirect N b towards N ′ a :bibliography(N a ) = bibliography(N a ) ∪ {N b |N b ∈ (P ∩ bibliography(N ′ a ))}, and bibliography(N ′ a ) = bibliography(N ′ a ) \ {N b |N b ∈ P } Example 18 (Link redirection). Let A a = {N 12 a , N 31 a , N 2a } be a set of authority records. We consider :-P initial (A a ) = {{N 1 b }, {N 2 b , N 3 b }, {N 4b }} (e.g. example 4), and-Best(A a , C a ) = {{N 1 b , N 2 b }, {N 3 b }, {N 4b }} (e.g. example 3).P 1 = {N 1 b , N 2 b } is a classe ∈ Best(A a ,C a ). P 1 = bibliography(N 12 a ) ∪ {N 2 b } and N 2 b ∈ bibliography(N 31 a ). So, we link N 2 b to N 12 a instead of N 31 a .

  C 1 , C 2 ∈ C two independent criteria and P 1 , P 2 , two partitions such as P 1 , P 2 ∈ B(CA(A a )). P 1 better C1,C2 P 2 if and only if: -P 1 better C1 P 2 and P 1 better C2 P 2 , or -V al Ci (P 1 ) = (inter, "neutral") ∀ i=1,2 and ∃ i=1,2 such that V al Ci (P 2 ) = (inter, intra) where intra ∈ V f ar . Example 11 (Criteria independency effect on partitioning). Let a set of contextual notices CA(A a ) = {A, B, C, D, E}, and a, b ∈ C, two criteria. The comparaisons values on {A, B, C, D, E} wrt a and b are shown on graph 1 and respectvely graph 2 on figure 4. Let P 1 , P 2 partitions ∈ B(CA(A a )) described on example 9. We consider a and b independents of each other. Then, P 2 better a,b P 1 . Definition 14 (The best partition wrt to two complementary Criteria). Let C 1 , C 2 ∈ C two complementary criteria and P 1 , P 2 defined as above two partitions in P(bibliography 1,...,i ). We compute P ⋄ i , i = 1, 2 as follows: ∀ o 1 , o 2 ∈ bibliography 1,...,i if C 1 (o 1 , o 2 ) ∈ V f ar 4 and C 2 (o 1 , o 2 ) ∈ V close then C 1 (o 1 , o 2 ) = "neutral".

	Then, P 1 better C1,C2 P 2 if and only if P ⋄ 1 better C1,C2 P ⋄ 2 .
	Example 12 (Criteria complementarity effect on partitioning).

  Definition 15 (The best partition wrt to two priority Criteria). Let C 1 , C 2 ∈ C two priority criteria such that C 1 > C 2 and P 1 , P 2 defined as above two partitions. P 1 better C1,C2 P 2 if and only if: -V al Ci (P 1 ) = (inter, "neutral") ∀ i=1,2 and ∃ i=1,2 such that V al Ci (P 2 ) = (inter, intra) where intra ∈ V f ar . -P 1 better nr C1 P 2 or, if equal, P 1 better C2 P 2 . Example 13 (Priority between criteria effect on partitioning). Let a set of contextual notices CA(A a ) = {A, B, C, D, E}, and a, b ∈ C, two criteria. The comparaisons values on {A, B, C, D, E} wrt a and b are shown on graph 1 and respectvely graph 2 on figure 4. Let P 1 , P 2 partitions ∈ B(CA(A a )) described on example 9. We consider a > b. Then, P 2 better a,b P 1 . Definition 16 (The best partition wrt to two Paribus Ceteris priority Criteria). Let C 1 , C 2 ∈ C two Paribus Ceteris priority criteria such that C 1 > C 2 and P 1 , P 2 defined as above two partitions. P 1 better C1,C2 P 2 if and only if: -P 1 better nr C1 P 2 or, if equal, P 1 better C2 P 2 . Example 14 (Paribus ceteris priority between criteria effect on partitioning). Let a set of contextual notices CA(A a ) = {A, B, C, D, E}, and a, b ∈ C, two criteria. The comparaisons values on {A, B, C, D, E} wrt a and b are shown on graph 1 and respectively graph 2 on figure 4. Let P 1 , P 2 partitions ∈ B(CA(A a )) described on example 9. We consider a ≫ b. Then, P 1 better a,b P 2 .

  {N 4 b } is a class as P ∈ P initial (A a ) and P ∈ Best(A a , C a ). So, P is linked valid, and confirm that N 4 b points to N 2 a .

	4 b }} (e.g. example 4), and b }, {N 4 b }, {N 3 b , N 2 -Best(A a , C a ) = {{N 1 b }} (e.g. example 3).
	P =

http://en.abes.fr/Sudoc/The-Sudoc-catalog

In this paper we use the term contributor to designate the person who contributed to a document. Author is seen as a specific role of such contributor.

Common contributors and domain criteria give information on publication context. The satisfaction of one of these criteria is enough to consider than the publication context is close between two contextual authorities.

The notation C1(o1, o2) ∈ V f ar corresponds to ∃A1, A2 ∈ A x , two values of the common attribute of type bibliographical notices o1 and o2, where C1(A1, A2) ∈ V f ar

Acknowledgements

We acknowledge the support of ABES for this work.