Paul Demay-Drouhard

Lise-Marie Chamoreau

Régis Guillot

Clotilde Policar
email: clotilde.policar@ens.fr

Hélène C Bertrand
email: helene.bertrand@ens.fr

Synthesis of Homoditopic Ligands with an Incrementable Rodlike Backbone

Keywords: Ligand design, N ligands, Synthetic methods, Rigid spacers, Supramolecular chemistry

We describe the synthesis of architectures that consist of a symmetrical rodlike oligo(phenylene-ethynylene) (OPE) backbone of incrementable length connected to a pair of classical ligands for metal coordination. OPE spacers decorated with various end groups and incorporating up to seven phenylene- [a]

Introduction

Ditopic ligands, that is, ligands that possess two distinct coordination sites, [1] are widely employed building blocks as they can lead to well-ordered supramolecular assemblies when coordinated to metal cations. [2] Starting from very simple molecules, complex and aesthetic architectures that display unusual properties can be easily obtained through coordination-driven selfassembly. [3] Hence, an impressive number of discrete metallacycles or cages have been prepared since the pioneering work of Lehn [4] and Sauvage. [5] In these molecular edifices, the ditopic ligands often consist of two coordinating moieties connected to a rigid rodlike backbone. These "struts" can play the role of pillars in host-guest coordination cages [6] or organic linkers in metal-organic frameworks (MOFs), [7] but they have numerous applications. For instance, metal complexes of bis-terpyridines can form discrete dyads that can act as molecular devices. [START_REF] Schubert | Modern Terpyridine Chemistry[END_REF] Dinuclear lanthanide or Mn II complexes of 1,4,7,10-tetraazacyclododecane-1,4,7,10-tetraacetic acid (DOTA) and its counterpart missing an acetate arm (DO3A) linked through an aromatic spacer have also proved useful as contrast agents in magnetic acetylene repeat units were quickly obtained through a bidirectional approach. Efficient further functionalization with useful coordinating groups were achieved. The resulting homoditopic platforms are of interest in numerous fields ranging from supramolecular chemistry to materials science. resonance imaging (MRI) [START_REF] Rudovský | [END_REF][10][11] and molecular recognition [12,13] due to their luminescent properties [14,15] as well as in model systems in which the spin-spin distances were measured by using pulsed electron paramagnetic resonance (EPR) methods. [16][17][18][19] The generation of ditopic platforms incorporating two ligands connected to a central rigid molecular wire of incrementing length is needed for diverse applications. This has been achieved with bis-terpyridine (bis-Tpy) oligomers with ethynylthiophene, [20] ethynylnaphthalene [21] or phenylene-ethynylene [22][23][24] repeat units. Oligo(phenylene-ethynylene) (OPE) spacers [25][26][27][28][29] of incrementing length spin-labelled with Gd III complexes of the ligand PyMTA (pyridine methylenediamine tetraacetate), a derivative of dipicolinic acid (DPA), have also been synthesized to act as molecular rulers for EPR-based distance measurements. [30,31] Such systems, in which the ligand-ligand distance can be easily tailored, are also very useful for controlling the size of host-guest cavities or the porosity of MOFs. [32] In this paper we describe an efficient strategy for building systems incorporating a central incrementable OPE rod connected at both ends to a Tpy, PyMTA, DPA, DO3A or DOTA ligand. First, we present a method to rapidly generate OPE linkers with various end groups and then describe efficient techniques to graft the aforementioned ligands. Discrete OPE oligomers with up to 16 phenylene-acetylene repeat units, equipped with diverse solubilizing moieties, have been prepared by using different strategies that have been recently reviewed. [33] We have chosen the so-called bidirectional approach, [34,35] which is well suited to the synthesis of symmetrical OPE linkers. To improve its efficiency, we decided to derivatize only one phenyl ring out of two with small poly(ethylene glycol) (PEG) chains so that the OPE spacer can be quickly elongated (four repeat units added in one step) while maintaining good solubility in organic solvents. This methodology is very convergent as all the building blocks can be obtained in only a few synthetic steps and OPE linkers with five or seven repeat units (i.e., up to 4.7 nm) are generated with the longest linear sequence of five or six steps, respectively.

Results and Discussion

The central diethynyl building block was synthesized starting from commercially available p-bromobenzaldehyde (1), which was converted into the monoprotected diethynylbenzene 2 in three steps (global yield: 81 %) according to a Sonogashira/ Corey-Fuchs sequence described by Nierengarten et al. with slight modifications. [36] Indeed, under the conditions described, a mixture of the desired alkyne 2 and the corresponding bromoalkyne was obtained. The use of tBuLi as a stronger base than LDA (for definitions of reagents, see the Experimental Section) was necessary to convert the remaining bromoalkyne into compound 2. This intermediate was then engaged in a Sonogashira reaction with the diiodo building block 3, synthesized in three steps under conditions previously described, [18] to afford the expected coupling product 4. Compound 4 was deprotected with TBAF to give the OPE linker 5 equipped with ethynyl end groups in gram amounts (Scheme 1). Its structure was confirmed by X-ray crystallography, as yellow needles of OPE 1 -diCCH 5 were obtained by slow evaporation from a 1:1 toluene/ DCM mixture (Figure 1A). This compound crystallizes in the P2 1 space group (monoclinic system), with two molecules per asymmetric unit. Under the same conditions, OPE linkers 6 and 7 were synthesized from compound 3 and 2.0 equiv. of the corresponding pethynylbenzene equipped with an amine (commercially available) or an aldehyde group (synthesized in two steps), as described previously. [18] Similarly, the iodinated coupling partners 8 and 9 were obtained by a mono-Sonogashira reaction be- tween compound 3 and 0.75 equiv. of the corresponding pethynylbenzene, with limited formation of the dicoupled product (between 5 and 10 %). Compounds 8 and 9 were then engaged in a double Sonogashira coupling reaction with either commercially available p-diethynylbenzene or OPE linker 5 to obtain the corresponding linkers 10-13 in moderate-to-good yields (Scheme 2).

Other useful functional groups can be generated. The reactions of compounds 10 and 12 with bromoacetyl bromide in the presence of NEt 3 gave products 14 and 15, respectively, equipped with a CH 2 Br moiety, which can react further with various modules through nucleophilic substitution reactions. [18] Compounds 7, 11 and 13 were oxidized to the corresponding carboxylic acids 16, 17 and 18 in nearly quantitative yields by using Oxone in DMF, as described previously for the corresponding shorter OPE spacer (Scheme 2). [18] OPE linkers 6, 7 and 10-18 were subsequently used for the synthesis of homoditopic platforms. To illustrate the diversity of the possible functionalizations, a selection of the described OPE linkers were chosen to react with selected ligands. Terpyridine 19 equipped with a phosphonate group was synthesized in two steps starting from p-tolyl-terpyridine by a radical bromination with N-bromosuccinimide (NBS) and azobis-isobutyronitrile (AIBN) followed by an Arbuzov reaction with P(OEt) 3 , according to a procedure described by Winter et al. [37] The diethyl ester of DPA 20, incorporating a bromo group in the para position, was obtained from chelidamic acid by esterification and bromination with PBr 5 following a procedure of Takalo et al. [38] According to the same procedure, reduction of the ester moieties with NaBH 4 followed by bromination with PBr 3 gave the corresponding tribrominated product. Reaction with ethyl iminodiacetate and substitution with sodium azide, as described by Tóth and co-workers, afforded the tetraethyl ester of PyMTA 21 equipped with an azido moiety (Scheme 3). [39] A double Horner-Wadsworth-Emmons reaction between terpyridine 19 and OPE 1 -diCOH 7 in the presence of NaH af- forded the corresponding OPE 1 -bisTpy 22 in good yield (80 %; Scheme 4). The use of KOtBu, as recommended by Winter et al., [37] led to the recovery of the reactants. Next, a Sonogashira coupling between the diethyl ester of DPA 20 [38] and OPE 1 -diCCH 5 in NEt 3 /DMF generated the corresponding product 23. Noteworthy, the use of NEt 3 /THF as solvent at reflux led to de-composition, whereas no reaction was observed at room temperature in the same solvent due to the poor solubility of the reactants. The structure of tetraester 23 was confirmed by X-ray crystallography: yellow crystals were grown from a deuteriated chloroform solution. This molecule crystallizes in the P1 ¯space group (triclinic system) with one of the ethyl groups being slightly disordered. In contrast to linker 5, the five aromatic rings are nearly coplanar: parallel sheets form in the packing unit due to a combination of π stacking and hydrogen bonds (Figure 1B).

The OPE 1 -bisDPA platform 24 was then obtained in nearly quantitative yield by ethyl ester hydrolysis with LiOH followed by treatment with ion-exchange resin Amberlite IR-120. Finally, PyMTA tetraester 21 and linker 5 were connected by click chemistry using CuI in MeCN, as proposed by Tóth et al., [39] to give octaester 25, which was deprotected to afford the OPE 1 -bisPyMTA module 26 (Scheme 4).

The dicarboxylic acid terminated OPE linkers can be functionalized through amidation reactions. Compounds 16-18 were treated with commercially available tri-tBu-DO3A in the presence of HOBt and DCC or HATU as coupling agents to afford the protected platforms 27-29. The smallest hexaester 27 was then deprotected with TFA to give the bisDO3A module 30 after HPLC purification. Finally, to illustrate the diversity of the functionalization methods available with these OPE linkers, compounds 14 and 15 were treated with the previously reported tri-Pp-DO3A [18] to give platforms 31 and 32. The 2-phenylisopropyl (Pp) groups were deprotected with 2 % TFA in DCM to afford bisDOTA compounds 33 and 34 after HPLC purification (Scheme 5).

Coordination chemistry studies of the described ditopic ligands will be performed with various transition-metal ions. In preliminary experiments, the reaction of OPE 1 -bisDPA 24 with Mn(ClO 4 ) 2 •6H 2 O (2.5 equiv.) in a mixture of THF and H 2 O (1:1) afforded a yellow precipitate, the very low solubility of which in classical solvents precluded any further investigation. The reaction of OPE 1 -bisPyMTA 26 with MnCl 2 (2.5 equiv.) at controlled pH afforded the expected bis-Mn complex as a yellow solid (as shown by mass spectroscopy, see the Supporting Information), which was soluble in water at pH 8. In the DO3A/DOTA series, the formation of the bis-Mn complex of OPE 1 -bisDOTA compound was also attested by mass spectroscopy. [18]

Conclusions

Various systems consisting of a pair of ligands connected through an OPE wire of incrementing length have been efficiently synthesized. The methodology employed in this work is quick, convergent and provides linkers with various end groups that can be easily further functionalized with useful ligands. Such architectures could easily find applications in numerous domains, from supramolecular chemistry to materials science. The coordination chemistry of the ditopic ligands described herein is currently being explored with various transition-metal ions and the resulting homodinuclear complexes will be studied for their properties in different fields such as pulsed EPRbased distance measurements and coordination-driven self-assembly. Further investigations, such as the characterization of the conductance of the OPE rods and of the electronic communication between metal centres in selected complexes and analysis of their mixed-valence character, would be of high interest. Finally, adaptation of the methodology to the efficient synthesis of disymmetrized heteroditopic ligands is currently being investigated.

Experimental Section

General: Unless otherwise stated, all syntheses were performed under inert atmosphere (argon or nitrogen). Reagents and chemicals were used without further purification. Dry solvents [dichloromethane (DCM), MeCN, THF, dioxane, dimethylformamide (DMF)] were purchased from commercial sources and used without further purification. Triethylamine (TEA) was dried with CaH 2 , distilled under argon and stored over 4 Å molecular sieves under argon. Preparative column chromatography was carried out with silica gel (Si 60, 40-63 μm) unless otherwise stated. Analytical TLC analysis was carried out on silica gel (60F-254) with UV visualization at 254 and 366 nm. Analytical HPLC measurements were performed with a Dionex Ultimate 3000 instrument using C18A ACE columns. Preparative HPLC was performed with a Waters 600 instrument using an XBridgeTM Prep C18 OBDTM column. Gradients of MeCN in H 2 O, both containing 0.1 % TFA, were employed. Products were monitored by UV detection. 1 H and 13 C NMR spectra were recorded with a 300 MHz spectrometer at Ecole Normale Supérieure (ENS) in the Laboratoire des Biomolécules (LBM, UMR 7203) with solvent residuals as internal references [CDCl 3 : 7.26 ppm for 1 H NMR and 77.16 ppm for 13 C NMR; (CD 3 ) 2 SO: 2.50 ppm for 1 H NMR and 39.52 ppm for 13 C NMR]. The following abbreviations are used: singlet (s), doublet (d), triplet (t), multiplet (m) and broad (br.). Chemi-cal shifts (δ) are given in parts per million (ppm) and coupling constants (J) in Hz. HRMS using electrospray ionization (ESI) was performed at the Université Paris Sud in the Service de Spectrométrie de masse of the ICMMO (Institut de Chimie Moléculaire et des Matériaux d'Orsay). ESI-HRMS was also performed at UPMC (IPCM). Tpy ligand 19 and ethyl esters of DPA 20 and PyMTA 21 were synthesized as described previously. [37][38][39] p-Ethynylbenzaldehyde, tri-Pp-DO3A, linkers OPE 1 -diNH 2 6, OPE 1 -diCOH 7 and OPE 1 -diCO 2 H 16 were synthesized as described previously by us. [18] The following abbreviations are used: Cy (cyclohexane), DCC (N,N′-dicyclohexylcarbodiimide), DIPEA (N,N′-diisopropylethylamine), DO3A (1,4,7,10tetraazacyclododecane-1,4,7-triacetic acid), DOTA (1,4,7,10-tetraazacyclododecane-1,4,7,10-tetraacetic acid), EDTA (ethylenediaminetetraacetic acid), HATU {1-[bis(dimethylamino)methylene]-1H-1,2,3triazolo[4,5-b]pyridinium 3-oxide hexafluorophosphate}, HOBt (Nhydroxybenzotriazole), LDA (lithium diisopropylamide), OPEG (diethylene glycol monomethyl ether), TBAF (tetra-n-butylammonium fluoride), TEA (triethylamine), TFA (trifluoroacetic acid).

General Procedure A -Mono-Sonogashira Coupling: Ph(OPEG) 2 I 2 (3; 1.0 equiv.) and p-ethynylaniline or p-ethynylbenzaldehyde (0.75 equiv.) were dissolved in a mixture of dry THF and dry TEA. Argon was bubbled through the solution for 15 min and then [PdCl 2 (PPh 3 ) 2 ] (0.1 equiv.) and CuI (0.2 equiv.) were added. The resulting suspension was stirred at room temp. for 48 h, a sat. aq. solution of NH 4 Cl was added and the mixture was extracted with DCM (3 ×). The combined organic layers were dried with Na 2 SO 4 , filtered and concentrated. Column chromatography afforded the corresponding products 8 and 9.

General Procedure B -Bis-Sonogashira Coupling: Iodide 8 or 9 (1.0 equiv.) and diyne 5 or p-diethynylbenzene (2.0 equiv.) were dissolved in a mixture of dry THF and dry TEA. Argon was bubbled through the solution for 15 min and then [PdCl 2 (PPh 3 ) 2 ] (0.1 equiv.) and CuI (0.2 equiv.) were added. The resulting suspension was stirred for 24 h at room temp., a sat. aq. solution of NH 4 Cl was added and the mixture was extracted with DCM (3 ×). The combined organic layers were dried with Na 2 SO 4 , filtered and concentrated. Column chromatography afforded the corresponding OPE linkers 10-13. General Procedure C -Synthesis of Dibromo OPE Linkers 14 and 15: Linker 10 or 12 (1.0 equiv.) was dissolved in dry DCM. The resulting solution was cooled to 0 °C, and TEA (2.5 equiv.) was added, followed by bromoacetyl bromide (2.5 equiv.) dissolved in dry DCM dropwise. The resulting mixture was warmed to room temp. for 3 h and washed with a sat. aq. solution of NaHCO 3 (1 ×) and a sat. aq. solution of NaCl (1 ×). The organic layer was dried with Na 2 SO 4 , filtered and concentrated. Column chromatography afforded the corresponding dibromo OPE linkers 14 and 15.

General Procedure D -Synthesis of Dicarboxylic OPE Linkers 17 and 18: Linker 11 or 13 (1.0 equiv.) was suspended in dry DMF. KHSO 5 •KHSO 4 •K 2 SO 4 (Oxone®, 2.0 equiv.) was added and the resulting suspension was stirred at room temp. for 15 h. H 2 O was added and the resulting precipitate was filtered, washed with H 2 O, taken up in acetone and dried to afford the corresponding dicarboxylic OPE linkers 17 and 18.

General Procedure E -Synthesis of tBu-Protected Bis-DO3A Compounds 28 and 29: Linker 17 or 18 (1.0 equiv.) and HATU (2.2 equiv.) were dissolved in dry DMF and stirred at room temp. for 10 min. Tri-tBu-DO3A (2.5 equiv.) was added and the resulting mixture was stirred at room temp. for 20 min. DIPEA (6.0 equiv.) was added and the resulting mixture was stirred at room temp. for 48 h and concentrated. The residue was taken up in DCM, washed with H 2 O (1 ×) and a sat. aq. solution of NaCl (1 ×), dried with Na 2 SO 4 , filtered and the solvents evaporated. Column chromatography afforded the corresponding tBu-protected bisDO3A compounds 28 and 29 as yellow sticky solids.

General Procedure F -Synthesis of Pp-Protected BisDOTA Compounds 31 and 32: Linker 14 or 15 (1.0 equiv.) and tri-Pp-DO3A (2.5 equiv.) were mixed in dry MeCN. K 2 CO 3 (10.0 equiv.) was added and the resulting mixture was heated at 60 °C for 15 h and concentrated. DCM was added and the mixture was washed with H 2 O (1 ×) and a sat. aq. solution of NaCl (1 ×), dried with Na 2 SO 4 , filtered and concentrated. Column chromatography afforded the corresponding Pp-protected bisDOTA compounds 31 and 32 as yellow solids.

General Procedure G -Deprotection of Pp-Protected BisDOTA Compounds: Pp-protected bisDOTA compound 31 or 32 was dissolved in a mixture of TFA/TIS/DCM (2:2:96, 10 mg mL -1 ). The resulting solution was stirred at room temp. for 4 h and concentrated. MeOH was added, and the product was precipitated by the slow addition of Et 2 O, filtered and dried. The crude product was purified by preparative HPLC to afford the corresponding OPE-bisDOTA linkers 33 and 34 as yellow solids.

X-ray Crystallography: X-ray diffraction data for compound 5 was collected by using a Kappa X8 APPEX II Bruker diffractometer with graphite-monochromated Mo-K α radiation. A crystal was mounted on a CryoLoop (Hampton Research) with Paratone-N (Hampton Research) as cryoprotectant and then flash frozen in a stream of nitrogen gas at 100 K. The temperature of the crystal was maintained at the selected value (100 K) by means of a 700 series Cryostream cooling device to within an accuracy of ±1 K. The data were corrected for Lorentzian, polarization and absorption effects. The structures were solved by direct methods with SHELXS-97 [40,[START_REF] Sheldrick | SHELXS-97, Program for Crystal Structure Solution[END_REF] and refined against F 2 by full-matrix least-squares techniques with SHELXL-2014 [START_REF] Sheldrick | [END_REF] with anisotropic displacement parameters for all non-hydrogen atoms. Hydrogen atoms were located on a difference Fourier map and introduced into the calculations as a riding model with isotropic thermal parameters. All calculations were performed by using the Crystal Structure crystallographic software package WinGX. [43] Yellow stick-like crystals of compound 23 suitable for X-ray crystallography were obtained from a deuteriated chloroform solution. A single crystal of the compound was selected, mounted onto a CryoLoop and transferred in a cold stream of nitrogen gas. Intensity data were collected with a BRUKER Kappa-APEXII diffractometer with Cu-K α radiation (λ = 1.54178 Å). Data collection was performed with the APEX2 suite (Bruker). [START_REF] Bruker | APEX2 suite and SAINT program[END_REF] Unit cell parameter refinement, integration and data reduction were carried out with the SAINT program (Bruker). [START_REF] Bruker | APEX2 suite and SAINT program[END_REF] SADABS (Bruker) was used for scaling and multi-scan absorption corrections. In the WinGX suite of programs, [43] the structure was solved by using the SHELXT [START_REF] Sheldrick | [END_REF] program and refined by full-matrix least-squares methods with SHELXL-2014. [START_REF] Sheldrick | [END_REF] All non-hydrogen atoms were refined anisotropically. Hydrogen atoms were placed at calculated positions and refined with a riding model. A model of disorder was introduced for a terminal ethyl chain. The crystal data collection and refinement parameters are given in Table S1 in the Supporting Information. CCDC 1484299 (for 5) and 1485975 (for 23) contain the supplementary crystallographic data for this paper. These data can be obtained free of charge from The Cambridge Crystallographic Data Centre.

Scheme 1 .

 1 Scheme 1. Synthesis of OPE-diCCH 5.

Figure 1 .

 1 Figure 1. ORTEP drawings of (A) OPE 1 -diCCH 5 and (B) tetraester 23. Hydrogen atoms have been omitted for clarity; ellipsoids are drawn at probability levels of 50 %.

Scheme 2 .

 2 Scheme 2. Synthesis of compounds 6, 7 and 10-18.

Scheme 4 .

 4 Scheme 4. Synthesis of OPE 1 -bisTpy 22, OPE 1 -bisDPA 24 and OPE 1 -bisPyMTA 26.

Acknowledgments

This work was financially supported by ANR MnHFPELDOR, ANR-Deutsche Forschungsgemeinschaft (DFG) Chemistry (2011-INTB-1010-01, Ph. D. scholarship to P. D.-D.).


F Mauger

C Chandre
email: chandre@cpt.univ-mrs.fr

T Uzer

Strong field double ionization of H 2 : Insights from nonlinear dynamics

Keywords: nonsequential double ionization of molecules, Hamiltonian systems, nonlinear dynamics PACS: 33.80.RV, 05.45.Ac

The uncorrelated ("sequential") and correlated ("nonsequential") double ionization of the H 2 molecule in strong laser pulses is investigated using the tools of nonlinear dynamics. We focus on the phase-space dynamics of this system, specifically by finding the dynamical structures that regulate these ionization processes. The emerging picture complements the recollision scenario by clarifying the distinct roles played by the recolliding and core electrons. Our analysis leads to verifiable predictions of the intensities where qualitative changes in ionization occur. We also show how these findings depend on the internuclear distance.

Introduction

The interaction of strong fields with molecules and their molecular ion and isotopic species have been studied extensively (see Refs. [1,2,3] for reviews).

Among molecular species, the H 2 -laser interaction remains a subject of particular interest because of the attosecond and femtosecond nuclear time scales and the relatively simple decay channels, showing the way to controlling the motion of electrons in molecules [4,5,6]. Nonsequential double ionization of H 2 has been studied in detail with an emphasis on the rescattering dynamics (e.g. [7]).

The strong enhancement of nonsequential (correlated) double ionization over its sequential (uncorrelated) counterpart is one of the most striking surprises in laser-matter interactions. Indeed, at some intensities, double ionization rates can be several orders of magnitude higher than the uncorrelated sequential mechanism leads one to believe. The hallmark of this strong correlation is the so-called knee of the double ionization probability versus the laser intensity.

An example of a knee is provided in Fig. 1 for a model of the H 2 molecule. Similar knees have been observed in experimental data [8,9,10,11,12,13,14,15,16] and successfully reproduced by quantal computations on atoms and molecules [17,18,19,20,21]. Different scenarios have been proposed to explain the mechanism behind this enhancement [8,22,23,10,17,24,25,26,27,28,29,30,31,32,33,34,35,36]. When confronted with experiments [37,12], the recollision scenario [22,23], in which an ionized electron is hurled back at the core and ionizes the second electron, seems in best accord with observations. It is generally agreed that the sequential process stems from the action of the laser pulse, whereas the electron-electron correlation is at the essence of the nonsequential process.

While classical mechanics would, at first sight, seem an inappropriate tool for studying this strong-field process, recent classical models [27,26,38,20,31,32,39,40] have been surprisingly successful in capturing key features of the process because of the dominant role of correlation [31]. Indeed, entirely classical interactions turn out to be adequate to generate the strong two-electron correlation needed for double ionization. These ideas have been put to the test on the helium atom [27,26,38,20,31,32,40]. A purely classical scenario for the double ionization of the Helium atom has been proposed in Ref. [40] based on the identification of the organizing centers of the classical dynamics of an effective Hamiltonian model. In the current manuscript, we explore the generality of this scenario and in particular how these ideas apply to the double ionization of the H 2 molecule driven by a linearly polarized strong laser pulse.

We shall show that the ideas developed fore helium are also applicable here, with some natural variations for the presence of the separated charge centers.

In summary, the emerging classical scenario for nonsequential double ionization is:

• Without the field, the dynamics of H 2 is very chaotic and mainly driven by four weakly hyperbolic periodic orbits. These periodic orbits define an "inner" and an "outer" electron.

• At time t = 0, the laser pulse is switched on and focuses its action on the outer electron by pulling it out of the core region.

• After half a period of the field, the outer electron is hurled back to the core region and interacts with the inner electron for a very short time.

The interaction, defined as a recollision, transfers energy from the outer to the inner electron. Several outcomes are possible and among them are :

A double ionization where both electrons leave the inner region, a single ionization where one of the electron leaves the nucleus and the other one stays in its neighborhood, an exchange of roles between the inner and the outer electron, or the outer electron proceeding for another recollision.

• Between two recollisions, the inner and outer electrons have their own respective dynamics. The inner region is mainly influenced by a periodic orbit which has the same period as the laser field. As long as this periodic orbit exists, it organizes an inner region where all the trajectories of the inner electron remain bounded. This scenario complements the recollision scenario by adding the phase space picture of the inner electron to the one of the outer electron. The mechanism in phase space allows us to formulate some verifiable predictions of two characteristic intensities of the knee : The intensity I (c) where the nonsequential double ionization is expected to be maximum and the intensity I (t) where the double ionization is complete (see Fig. 1). In comparison with the helium case, we highlight the common features but also the differences generated by the two nuclei, and in particular how the predictions depend on the distance between the two nuclei.

Hamiltonian models for H 2

We consider a model for H 2 where the two nuclei are fixed [41,21], motivated by the fact that the time scale of electron motion during the laser pulse is short compared to the one characterizing the motion of the heavy nuclei. More specifically, we consider the following Hamiltonian model of the H 2 molecule (in atomic units) with soft Coulomb potentials [41,21,42,43] :

H (x, y, p x , p y , t) = p x 2 2 + p y 2 2 + 1 R + 1 x -y 2 + 1 + (x + y) • E (t) - 1 R/2 -x 2 + 1 - 1 R/2 + x 2 + 1 - 1 R/2 -y 2 + 1 - 1 R/2 + y 2 + 1 , (1)
where x and y are the positions of the two electrons in a d-dimensional space, and p x , p y are their canonically conjugate momenta, and • denotes the Euclidean scalar product in R d and • its corresponding norm. Here we consider d = 1, 2 and 3 for the computations, but we mainly consider d = 1 for the phase space analysis since we will see below that it reproduces the same characteristic features as the higher dimensional cases. The energy is initially fixed at the ground state E g = -1.16 a.u. [42,43]. The linearly polarized laser field is a sinusoidal pulse modulated by an envelope, i.e. E(t) = e 1 E 0 f (t) sin ωt where e 1 is a unit vector characterizing the direction of the polarization, E 0 is the maximum amplitude and ω the laser frequency chosen at ω = 0.0584 a.u. which corresponds to a wavelength of 780 nm. The pulse envelope f (t) is chosen as a trapezoidal function with 2-4-2 laser pulse shape (the ramp-up lasts two cycles, the plateau four and the ramp-down two). We assume the two nuclei are aligned with the laser field and the distance, denoted R, between them is fixed during the whole range of time we will consider [21], so that R = Re 1 where R = 1.4 a.u. [43].

Typical ionizing trajectories of Hamiltonian (1) show mainly two qualitatively different routes to double ionization (see Fig. We first analyze the dynamics of Hamiltonian (1) without the field (E 0 = 0).

This Hamiltonian system has two degrees of freedom, and therefore lends itself very well to an analysis using Poincaré sections. Here we use a different tool to analyze the dynamics, by considering the linear stability properties such as obtained by the finite-time Lyapunov (FTL) exponents [START_REF] Cvitanović | Chaos: Classical and Quantum[END_REF][START_REF] Shchekinova | [END_REF]. These FTL exponents are obtained by integrating the tangent flow together with the equations of motion for X = (x, y, p x , p y ) :

Ẋ = F(X, t), (2)
J = DF (X, t)J, (3)
where Eq. ( 2) are the equations of motion, and Eq. ( 3) is the tangent flow where DF (X, t) is the matrix of variations of the generalized velocity field F at the point X and time t, i.e. DF ij = ∂F i /∂X j . The initial condition for the inte- and y 1 (continuous red curve) of each pair of electrons are plotted versus time, as well as the positions in the transverse direction x 2 (dashed cyan curve) and y 2 (dashed magenta curve).

The pulse shape function f (t) (black curve) and the laser excitation E(t) (dotted black curve) are also represented. The amplitude of the shape function and of the laser excitation are not representative of the actual conditions. gration of the tangent flow is J 0 = I 4 , the four dimensional identity matrix.

The (maximum) FTL exponent at time t for the initial conditions X 0 is equal to l(t; X 0 ) = log |λ(t; X 0 )|/t where λ(t; X 0 ) is the eigenvalue of the Jacobian matrix J at time t with the largest norm. The way to analyze the dynamics using these exponents is to represent maps of FTL exponents as functions of the initial conditions X 0 at a fixed time t. These maps (called FTL maps) quantify the (linear) instability of some regions and highlight invariant objects. A typical FTL map is depicted in Fig. 3 for Hamiltonian (1) without the field. It clearly displays strong and global chaos by showing fine details of the stretching and folding of trajectories [START_REF] Cvitanović | Chaos: Classical and Quantum[END_REF]. A closer inspection shows some regions associated with a very small FTL exponents (blue regions and lower panel of Fig. 3). A Poincaré section reveals the presence of an elliptic island which surrounds an elliptic periodic orbit O e , represented on Fig. 4 with a black curve. However such regions are too small to play a major role in the dynamics of a typical trajectory. In fact, the motion without the field is guided by four weakly hyperbolic periodic orbits. These four important periodic orbits are denoted O x,1 , O x,2 , O y,1 and O y,2 , and the projections of O x,1 and O y,1 are displayed in Fig. 4. These four periodic orbits are obtained from one single periodic orbit through the symmetries of the equations of motion: (x, y, p x , p y ) → (y, x, p y , p x ) and (x, y, p x , p y ) → (-x, -y, -p x , -p y ). It also means that the representation of these orbits on the plane (y, p y ) can be deduced from the one on the plane (x, p x ) by inverting the coordinates x and y. The two periodic orbits O x,1 and O x,2 (stretched in the x-direction) have an outer projection in the (x, p x ) plane and an inner one in the (y, p y ) plane (see the red curves in Fig. 4). By symmetry, the same holds for O y,1 and O y,2 , swapping the role of x and y. Figure 5 represents the distance of a typical trajectory with the four periodic orbits mentioned above. It shows that at each time, the trajectory is close to one of these orbits with rapid transitions between them. This means that the motion on each of these periodic orbits, and consequently of a typical trajectory, is composed of one electron moving close to the nucleus (the inner electron) and the other one further moving away (the outer electron), with quick exchanges of the roles of each electron.

The reason why these hyperbolic periodic orbits are important is that they are short and weakly hyperbolic periodic orbits (their Greene residue [46] is equal to 1.1). Hence a typical trajectory passing nearby one of these orbits mimics (by continuity) the motion on the periodic orbit and then slowly escapes (depending on its escape rate and hence on its stability properties) from this orbit following its unstable manifold.

Single ionization. By switching on the field, the outer electron is picked up and swept away from the nucleus. Consequently, its effective Hamiltonian is composed of its kinetic energy and the interaction potential of the laser field :

H 1 = p 2 x 2 + E 0 xf (t) sin ωt (4)
We notice that the trajectories of Hamiltonian H 1 can be explicitly computed.

They are composed of a linear escape from the nuclei (at time t 0 ) modulated by the action of the field [22] (see trajectories after collision in Fig. 2).

Sequential double ionization (SDI).

Since the outer electron is far from the core region, the effective Hamiltonian for the inner electron contains the potential of the nuclei and the interaction with the laser field :

H 2 = p 2 y 2 + yE 0 sin ωt - 1 (y -R/2) 2 + 1 - 1 (y + R/2) 2 + 1 (5)
In the absence of the field (I = 0), H 2 is also integrable and the inner electron is confined on a periodic orbit, for almost all the initial conditions. By switching on the field, the dynamics associated with H 2 is significantly affected. A contour plot of y after two laser cycles and a Poincaré section are represented on Fig. 6 for I = 3 × 10 15 W • cm -2 . We notice the following features : First, most of the regular trajectories evolve on invariant tori. Second, most of the inner tori are broken by the field, creating a bounded chaotic region between the two nuclei.

These two types of trajectories (regular and bounded chaotic) do not ionize. Third, the outermost invariant tori are broken since the motion is unbounded sufficiently far away from the nuclei. These are the ionizing trajectories. During a full laser cycle, we expect two types of non-ionizing trajectories represented on Fig. 7 : A typical motion in between the nuclei (upper panel) and another surrounding the two nuclei (lower panel). This is what is observed on typical trajectories like the one represented on the lower panel of Fig. 8.

By varying the intensity, the picture of the phase space of Hamiltonian (5) evolves in the following way : If the laser intensity I is too small, then the phase space is surrounded by invariant tori (with a bounded chaotic region between the two nuclei) and no sequential double ionization can occur. The sequential double ionization probability depends the on the size of the regular region, and hence on I. For large values of the intensity, the regular zone vanishes and after some critical intensity, after which there are no invariant tori bounding the motion of the inner electron. Consequently, only sequential double ionization is observed in this high intensity regime. More specifically, the size of the region where the trajectories are bounded is quantified by y m (defined as the maximum position y of the outermost invariant torus of Hamiltonian (5) on the Poincaré section).

A numerical approximation to y m is obtained by integrating trajectories at p y = 0 (since the domain is approximately symmetric with respect to p y = 0) and monitoring the ones which do not keep a bounded value for the position after the duration of the laser pulse. This numerical estimate of y m versus the intensity I is represented on Fig. 9

(continuous curve).

A rough approximation to y m = y m (E 0 ) is given implicitly by the value where the potential of Hamiltonian ( 5) is locally maximum, i.e. :

E 0 = y m -R/2 (y m -R/2) 2 + 1 3/2 + y m + R/2 (y m + R/2) 2 + 1 3/2 , (6)
independently of the laser frequency. The solution of the above equation is represented as a function of the laser intensity I in Fig. 9 (dashed curve). The observation is that the theoretical prediction captures the right order of magnitude, but for ω = 0.0584, this approximation is quantitatively not accurate for ω = 0.0584 (continuous blue curve). The qualitative approximation of ym given by Eq. (

(dashed curve) and the same qualitative approximation divided by two (thin continuous curve).

since the estimates are about twice the actual values. Of course the quality of the approximation depends on the chosen frequency ω. As the frequency ω is decreased toward zero, the approximation becomes better.

Equation ( 6) has a solution for I ≤ 1.09 × 10 16 W • cm -2 . For higher intensities, we expect complete double ionization. This is the case of Fig. 1. However, this is an upper bound since complete double ionization appears to happen at smaller intensities. This emerges from the numerical computation of y m where the size of the regular zone drops to zero for intensities larger than 7.10

× 10 15 W • cm -2 .
The origin of this phenomenon is explained by looking at the central periodic orbit which organizes the bounded motion. This periodic orbit has the same period as the field (and therefore intersects the Poincaré section at only one point). It is located at y = 0. In order to determine its momentum, we use a Newton-Raphson method for the determination of periodic orbits [START_REF] Cvitanović | Chaos: Classical and Quantum[END_REF]. The results are represented on Fig. 10. We see that for a wide range of intensities the momentum p y of the periodic (on the Poincaré section) does not change significantly. Around I = 7 × 10 15 W • cm -2 it starts decreasing and drops to -∞ at I (t) = 7.10 × 10 15 W • cm -2 . At this value, complete sequential double ionization occurs, in good agreement with Fig. 1.

Nonsequential double ionization (NSDI).

As noted before, when the field is turned on, its action is concentrated on only one electron, the outer one, as a first step. The field drives the outer electron away from the nuclei leaving the inner electron nearly unaffected by the field (or at least bounded if it is between the two nuclei) because its position remains small. From the recollision process [22,21], the outer electron might come back close to the nuclei during the pulse plateau. In this case, it transfers a part of its energy to the inner electron through the electron-electron interaction term (a recollision). From then on, two outcomes are generically possible : If the energy brought in by the outer electron is sufficient for the other electron to escape from the inner region (as in the lower panel of Fig. 2), then it might ionize together with the outer electron.

The maximum energy E x of the outer electron when it returns to the inner region is obtained from Hamiltonian (4) and is E x = κU p where U p = E 2 0 /(4ω 2 ) is the ponderomotive energy and κ = 3.17314 . . . [22,47]. We complement the recollision scenario (which focuses on the outer electron) by providing the phase space picture of the inner electron as accurately described by Hamiltonian (5) :

In order to ionize the inner electron in the most efficient way, the energy brought back by the outer electron has to be of order of the energy between the center (y = 0) and the boundary of the bounded inner region (y = y m ) of the phase space of Hamiltonian H 2 (see Fig. 6). This energy difference is equal to :

∆E y = 2 R 2 /4 + 1 - 1 (y m -R/2) 2 + 1 - 1 (y m + R/2) 2 + 1 . (7)
The equal-sharing relation which links the classical picture of the outer electron x with the one of the inner electron y,

∆E y = E x 2 = κ E 2 0 8ω 2 (8)
defines (through an implicit equation) the expected value of the field E (c) 0 and hence the corresponding intensity I (c) for maximal NSDI because it describes the case when each outer electron brings back enough energy to ionize the innermost electrons, while keeping enough energy to potentially remain ionized itself. However, fulfilling this energy requirement does not guarantee NSDI : The outcome depends on the number and the efficiency of recollisions. In order to estimate I (c) , we first use the qualitative approximation of y m given by Eq. ( 6).

For ω = 0.0584, this intensity is equal to 3.60 × 10 14 W • cm -2 which is in good agreement with the maximum of the knee in Fig. 1 (green dashed curve). Now we consider the numerically determined values for y m (see Fig. 9). By solving Eq. ( 8), the intensity I (c) is found at 2.60 × 10 14 W • cm -2 (green continuous curve in Fig. 1) in qualitative agreement with the above value obtained using the qualitative determination of y m .

Next we investigate how this critical intensity I (c) varies with the laser frequency and highlight how this intensity varies with the distance R between the two nuclei. For that purpose, we expand the equal sharing relation (8) using to small parameters: R 2 /8 and η 0 = 2ω/ √ κ (which are assumed to be of the same order). The leading order of Eq. ( 7) is

∆E y ≈ 2 1 - R 2 8 - 2
y 2 m + 1
, and the corresponding expansion for the approximation y m = y m (E 0 ) given by Eq. ( 6) is

E 0 = 2y m (y 2
m + 1) 3/2 . If we denote η = 1/ y 2 m + 1, then Eq. ( 8) is expanded into

η 4 (1 -η 2 ) = η 4 0 1 -η - R 2 8 .
An expansion of a solution of the above equation is given by

η = η 0 - η 0 4 η 0 + R 2 8 ,
which translates into an expansion for the critical amplitude

E (c) 0 ≈ 4ω √ κ - 2ω √ κ 3/2 - 2ω √ κ R 2 8 . (9)
We notice that the expansion of E (c) 0

at R = 0 is the same as the one found for the helium atom [40] since the Hamiltonian model for the helium atom is the R = 0 limit of Hamiltonian (1) . As the distance R between the two nuclei increases, the location of the knee is displaced toward lower intensities, and this displacement is proportional to R 2 . This is actually what is observed when we compared the values of I (c) for the helium atom [40] (I (c) (R = 0) = 4.60 × 10 14 W • cm -2 for ω = 0.0584) and for the H 2 molecule. For ω = 0.0584, the approximate value of I (c) given by Eq. ( 9) for R = 1.4 is 3.40×10 14 W•cm -2

which is in good agreement the numerical solution of Eq. ( 8).

Conclusion

The classical picture for the sequential and nonsequential double ionization of H 2 is obtained by complementing the recollision scenario for the outer electron with the phase space picture of the inner electron. By finding the organizing principles of the classical dynamics, we arrived at two predictions for the characteristic intensities of the knee-shaped double ionization probability curve : the intensity after which the complete double ionization is expected, and the intensity where the non-sequential double ionization is predicted to be maximum.

Very good agreement is found by comparing our predictions with the direct integration of a large assembly of trajectories. It should be noted that this scenario follows closely the one of the helium atom, implying the existence of a general mechanism for nonsequential double ionization of atoms and molecules.

Based on these findings, we believe that advanced methods of classical mechanics and the diagnostics we use here are worth pursuing further because classical mechanics, with its advantageous scaling with system size, may well become a useful tool for understanding some aspects of molecular systems too complex for a full quantal treatment with contemporary computing resources.

Figure 1 :

 1 Figure 1: Double ionization probability for Hamiltonian (1) for the d = 1 (dots) d = 2 (stars) and d = 3 (triangles) models as a function of the intensity of the field I for ω = 0.0584. The vertical lines indicate the laser intensities (continuous green line) I (c) ≈ 3.60 × 10 14 W • cm -2and (dashed green line) I (c) ≈ 3.60 × 10 14 W• cm -2 where our dynamical analysis predicts the maximum of nonsequential double ionization (related to two different approximations), and (in blue) the intensity I (t) ≈ 7.10 × 10 15 W • cm -2 where the double ionization is expected to be complete.

  2) : nonsequential double ionization (NSDI), where the two electrons leave the core (inner) region at about the same time, and sequential double ionization (SDI), where one electron leaves the inner region long after the other one has ionized.Using a large assembly of initial conditions, we compute the double ionization probability as a function of the laser intensity I (related to E 0 by I(W •cm -2 ) = 3.521 × 10 16 E 0 (a.u.) 2 ) for d = 1, 2 and 3 (see Fig.1). This probability curve has the shape of a knee, a hallmark of double ionization. Even if the probability of double ionization is much lower for the three or the two dimensional model, one can see that characteristic features (the localization of the knee and the intensity where double ionization is complete) happen at about the same intensities. We restrict ourselves to the one-dimensional case in what follows in order to obtain some information on these intensities and the mechanisms behind NSDI and SDI.

Figure 2 :

 2 Figure 2: Example of sequential (upper panel) and nonsequential (lower panel) double ionization trajectories of Hamiltonian (1) (for the d = 2 model) for ω = 0.0584 and I = 3 × 10 15 W • cm -2 . The positions along the polarization axis x 1 (continuous blue curve)

Figure 3 :

 3 Figure 3: Upper panel : FTL map of Hamiltonian (1) without the field at time t = 50 a.u. in the plane (x, px) with y = 0. The full circles indicate (with the same color code) the intersections of the periodic orbits of Fig. 4 with the Poincaré section at y = 0 : The full diamonds indicate the symmetrical orbits from the one of Fig. 4 with the symmetry (x, y, px, py) → (-x, -y, -px, -py). Lower panel : Enlargement of the FTL map around a region indicated by a square in the upper panel, and Poincaré sections of some regular trajectories in the elliptic island.

Figure 4 :

 4 Figure 4: Projections of the periodic orbits Oe (black curves), O x,1 (red curves) and O y,1 (blue curves) in the (x, y) plane (upper left panel), (x, px) plane (upper right panel), (y, py) plane (lower left panel), and (px, py) plane (lower right panel).

Figure 5 :

 5 Figure 5: Upper panel : Positions x (red online) and y (blue online) of the two electrons as a function of time of a typical trajectory of Hamiltonian (1) with d = 1 and without the field. Lower panel : Distance in phase space of the trajectory depicted in the upper panel versus time to the four periodic orbits O x,1 , O x,2 , O y,1 , O y,2 . For each distance, the color code and line style follow the one in Fig. 4, the dashed curves (magenta and cyan) correspond to the distance to the symmetrical periodic orbits O x,2 and O y,2 respectively. The horizontal dashed green lines indicate the positions of the nuclei. Time is in atomic units.

Figure 6 :

 6 Figure 6: Upper panel : Contour plot of the electron location y(t) after two laser cycles in the plane of initial conditions (y 0 , p y,0 ) of Hamiltonian (5) for I = 3 × 10 15 W • cm -2 and ω = 0.0584. The color code is on a logarithmic scale. Lower panel : Poincaré section (stroboscopic plot with a period of one laser cycle) of some trajectories for the same Hamiltonian as the upper panel. The black dots indicate the positions of the nuclei.

Figure 7 :

 7 Figure 7: Two types of trajectories of Hamiltonian (5) for I = 10 15 W • cm -2 and ω = 0.0584 during a laser cycle : One inside the inner chaotic region (upper panel), and one on an outer invariant torus (lower panel). The horizontal dashed lines (green online) indicate the positions of the two nuclei.

Figure 9 :

 9 Figure 9: Numerical estimates of ym as a function of the laser intensity I for Hamiltonian (1)

Figure 10 :

 10 Figure 10: Momentum of the central periodic orbit (on the Poincaré section) of Hamiltonian (5) as a function of the laser intensity. The vertical line on the lower panel indicates the intensity I (t) = 7.10 × 10 15 W • cm -2 such that for I ≥ I (t) , complete unhindered SDI is expected. The black dots indicate the positions of the two nuclei. Inset : Projection of the central periodic orbit at I = 7 × 10 15 W • cm -2 in the (y, py)-plane.

Acknowledgments

CC acknowledges financial support from the PICS program of the CNRS. This work is partially funded by NSF.


Estimation of physical conditions in PDRs Bayesian approach with spatial regularization

Pierre Palud 1,2 , F. Le Petit

Aims and contributions

New large hyper-spectral surveys in radio-astronomy: game changer for study of star formation, feedback mechanisms and chemistry of interstellar gas. =⇒ now possible to observe full molecular clouds (10 pc size) at dense core scale (<0.1 pc) spatial resolution. For instance, the IRAM-30m Large Program «Orion B» [START_REF] Pety | The anatomy of the Orion B Giant Molecular Cloud: A local template for studies of nearby galaxies[END_REF] provides a 10 6 pixel observation map, covering ∼250 pc 2 of the Orion B cloud with emission of dozens of molecules.

Goal

To estimate maps of thermal pressure P th , UV radiation intensity G 0 , visual extinction A V , scaling factor κ and the associated uncertainties.

Challenge Variability of the SNR: the brightest regions can be well constrained, but the regions with low SNR lead to degenerate solutions.

Approach # Mixture of both additive and multiplicative noises + limited detectability =⇒ more realistic observation model # Spatial regularization =⇒ exploitation of the information contained in neighbouring pixels. # Bayesian approach =⇒ access to accurate credibility intervals.

Problem formulation

Meudon PDR code [START_REF] Petit | A model for atomic and molecular interstellar gas the Meudon PDR code[END_REF]: solves radiative transfer, chemistry, thermal balance on stationary 1D plane-parallel model.

y n, = ω if ε (m) n, f (x n ) + ε (a) n, ≤ ω ε (m) n, f (x n ) + ε (a) n, else =⇒ defines a likelihood function π(y | x).

Bayesian approach

State-of-the-art in millimeter/IR astronomy estimations: Maximum Likelihood Estimates (MLE) =⇒ very sensitive to noise For robust estimators: spatial regularization prior π(x) (norm of image gradient or laplacian)

Posterior probability density function:

π(x | y) ∝ π(y | x)π(x)
To derive estimators and credibility intervals from posterior distribution: sample from it with Monte Carlo Markov Chain (MCMC).

Our sampler mixes two kernels: one identifies local minima, one efficiently explores them.

Our ponctual estimator: MMSE (Mininimum Mean Squared Error) = mean of posterior. Estimation from 10 lines of CO and 2 lines of CI. In contrast with [START_REF] Joblin | Structure of photodissociation fronts in star-forming regions revealed by Herschel observations of high-J CO emission lines[END_REF], G 0 and A V estimated along with κ and P th .

Application on toy dataset (100 pixels)

Two regions of acceptable solutions identified.

Summary for main mode

  Assumption: physics in PDR = interpolation of a grid of simulations of Meudon PDR code. Defines function f s.t. for one pixel n:f : x n = (κ, P th , G 0 , A V )

  Synthetic observations: 10 excited lines of CO (from J=4-3 to 13-12) NGC 7023 (1 pixel)

  1 , P. Chainais 2 , E. Bron 1 , P.-A. Thouvenin 2 , ORIONB consortium 1 LERMA, Obs. de Paris, PSL Research Univ., CNRS, Meudon 2 Univ. Lille, CNRS, Centrale Lille, UMR 9189 -CRIStAL, France


Thomas De Groot

Joe Raad

Stefan Schlobach

Analysing Large Inconsistent Knowledge Graphs using Anti-Patterns

Keywords: linked open data, reasoning, inconsistency

A number of Knowledge Graphs (KGs) on the Web of Data contain contradicting statements, and therefore are logically inconsistent. This makes reasoning limited and the knowledge formally useless. Understanding how these contradictions are formed, how often they occur, and how they vary between different KGs is essential for fixing such contradictions, or developing better tools that handle inconsistent KGs. Methods exist to explain a single contradiction, by finding the minimal set of axioms sufficient to produce it, a process known as justification retrieval. In large KGs, these justifications can be frequent and might redundantly refer to the same type of modelling mistake. Furthermore, these justifications are -by definition-domain dependent, and hence difficult to interpret or compare. This paper uses the notion of anti-pattern for generalising these justifications, and presents an approach for detecting almost all anti-patterns from any inconsistent KG. Experiments on KGs of over 28 billion triples show the scalability of this approach, and the benefits of anti-patterns for analysing and comparing logical errors between different KGs.

Introduction

Through the combination of web technologies and a judicious choice of formal expressivity (description logics which are based on decidable 2-variable fragments of first order logic), it has become possible to construct and reason over Knowledge Graphs (KGs) of sizes that were not imaginable only few years ago. Nowadays, KGs of billions of statements are routinely deployed by researchers from various fields and companies. Since most of the large KGs are traditionally built over a longer period of time, by different collaborators, these KGs are highly prone for containing logically contradicting statements. As a consequence, reasoning over these KGs becomes limited and the knowledge formally useless.

Typically, once these contradicting statements in a KG are retrieved, they are either logically explained [START_REF] Schlobach | Non-standard reasoning services for the debugging of description logic terminologies[END_REF] and repaired [START_REF] Plessers | Resolving inconsistencies in evolving ontologies[END_REF], or ignored via non-standard reasoning [START_REF] Huang | Reasoning with inconsistent ontologies[END_REF]. This work falls in the first category of approaches where the focus is to find and explain what has been stated in the KG that causes the inconsistency. Understanding how these contradictions are formed and how often they might occur is essential for fixing and avoiding such contradictions. At least, it is a necessary step for developing better tools that can handle inconsistent KGs. For explaining contradictions, the notion of justification, which is a minimal subset of the KG that is sufficient for the contradiction to hold, plays a key role [START_REF] Horridge | Laconic and precise justifications in owl[END_REF]. In the renowned Pizza ontology1 that serves as a tutorial for OWL and the ontology editor Protégé, we can find two contradictions that were asserted by its developers on purpose. The first contradiction (A) demonstrates the unsatisfiable class CheesyVegetableTopping, that has two disjoint parents Cheese-Topping and VegetableTopping. The second contradiction (B) demonstrates a common mistake made with setting a property's domain, where the class Pizza is asserted as the domain of the property hasTopping. This statement means that the reasoner can infer that all individuals using the hasTopping property must be of type Pizza. On the other hand, we find in the same ontology a property restriction on the class IceCream, stating that all members of this class must use the hasTopping property. However, since it is also specified that the classes Pizza and IceCream are disjoint, now enforcing an unsatisfiable class to have a member leads to an inconsistency in the ontology. As presented in Figure 1, justifications serve to explain such contradictions, by showing the minimal set of axioms from the ontology that causes the contradiction to hold.

Although justifications provide a good basis for debugging data quality and modelling issues in the KG, their specificity in explaining the contradictions increases in some cases the complexity for analysing and dealing with these detected contradictions. Particularly in large KGs, these complexities are amplified and encountered in different dimensions. Firstly, existing methods to retrieve entailment justifications do not scale to KGs with billions of triples. Secondly, these retrieved contradictions with their justifications can be too frequent to manually analyse and understand the modelling mistakes made by the ontology designer. This is especially inconvenient when a significant number of these retrieved justifications actually refer to the same type of mistake, but instantiated in different parts of the KG (e.g. similar misuse of the domain and range properties in multiple cases). Thirdly, since justifications represent a subset of the KG, they are by definition domain dependent, and requires some domain knowledge for understanding the contradiction. This fact is obviously more limiting in complex domains, such as medical KGs, as opposed to the Pizza ontology example above. These various challenges in finding and understanding justifications in their traditional form, poses the following research questions:

Q1: Can we define a more general explanation for contradictions, that categorises the most common mistakes in a KG, independently from its domain? Q2: Can we retrieve these generalised explanations from any KG, independently from its size? Q3: How can these generalised explanations help analysing and comparing certain characteristics between the most commonly used KGs in the Web?

This paper introduces a method for extracting and generalising justifications from any inconsistent KG. We call these generalised justifications anti-patterns, as they can be seen as common mistakes produced either in the modelling or population phases, or possibly stemming from erroneous data linkage. We have developed an open-source tool that can retrieve these anti-patterns from any (inconsistent) KG. We test the scalability and the completeness of the approach on several KGs from the Web, including LOD-a-lot, DBpedia, YAGO, Linked Open Vocabularies, and the Pizza ontology, with a combined size of around 30 billion triples. Despite deploying a number of heuristics to ensure scalability, our experiments show that our method can still detect a large number of antipatterns in a KG, in reasonable runtime and computation capacity. Finally, we publish these detected anti-patterns in an online catalogue encoded as SPARQL queries, and show how these anti-patterns can be put to use for analysing and comparing certain characteristics of these inconsistent KGs.

The rest of the paper is structured as follows. Section 2 presents related works. Section 3 presents the preliminaries and notation. Section 4 introduces our notion of anti-patterns and describes our approach for detecting them. Section 5 presents the evaluation of the approach. Section 6 presents inconsistency analyses conducted on several large inconsistent KGs. Section 7 concludes the paper.

Related Work

Dealing with inconsistent knowledge bases is an old problem, and solutions have been proposed as early as 1958 by Stephen Toulmin [START_REF] Toulmin | The uses of argument[END_REF], where reasoning over consistent subbases was proposed. Explaining why a knowledge base entails a certain logical error (or entailment in general) has taken up traction in the last decade, leading to the most prevalent form of explanation in OWL knowledge bases called justification: minimal subsets of the graphs preserving entailments [START_REF] Kalyanpur | Debugging unsatisfiable classes in owl ontologies[END_REF][START_REF] Schlobach | Non-standard reasoning services for the debugging of description logic terminologies[END_REF]. A number of approaches, described in [START_REF] Bail | The justificatory structure of OWL ontologies[END_REF], aims at supporting users' understanding of single justifications for single entailments. Such approaches focus on reducing the axioms in justifications to their relevant parts and remove superfluous information [START_REF] Horridge | Laconic and precise justifications in owl[END_REF][START_REF] Kalyanpur | Beyond asserted axioms: Fine-grain justifications for owl-dl entailments[END_REF], providing intermediate proof steps to explain subsets of justifications [START_REF] Horridge | From justifications towards proofs for ontology engineering[END_REF], or attempting to improve understandability of an explanation by abstracting from the logical formalism to natural language [START_REF] Nguyen | Measuring the understandability of deduction rules for owl[END_REF].

In this work, we focus on a complementary part of the problem, where the goal is to facilitate the understandability of multiple justifications, of logically incorrect entailments, that share the same structure. For this, we rely on the notion of anti-pattern that represents a generalisation of such justifications. The term 'anti-pattern' appears in the work of [START_REF] Roussey | A catalogue of owl ontology antipatterns[END_REF], where the authors manually classify a set of patterns that are commonly used by domain experts in their DL formalisations, and that normally result in inconsistencies. In addition anti-patterns are also studied in [START_REF] Paulheim | Serving dbpedia with dolce-more than just adding a cherry on top[END_REF], where the authors use a combination of reasoning and clustering methods for extracting common patterns in the detected justifications. However, this approach cannot be applied to any inconsistent KG, as it requires the KG to be mapped to the foundational ontology DOLCE-Zero.

Moreover, the notion of justifications with the same structure has been previously investigated but not formalised by [START_REF] Nguyen | Justification patterns for owl dl ontologies[END_REF], while the more complex notion of justification template has been introduced by [START_REF] Bail | The justificatory structure of OWL ontologies[END_REF], where several equivalence relations over justifications has been explored. In comparison with the mentioned works, this is the first work that relies on a simpler notion of justifications' generalisation, for the goal of analysing common logical errors in KGs, at the scale of the Web. Our method for detecting such anti-patterns reuses part of the work of [START_REF] Noori | Simulation and comparison of efficency in pathfinding algorithms in games[END_REF], where the authors propose the efficient algorithm for path finding that we use in our subgraph generation. Our work can also be compared to an earlier large scale justification retrieval approach that uses MapReduce [START_REF] Wu | Finding all justifications of owl entailments using tms and mapreduce[END_REF] but was mainly evaluated over synthetic data sets, and recent analyses [START_REF] Beek | sameas. cc: The closure of 500m owl: sameas statements[END_REF][START_REF] Debattista | Evaluating the quality of the lod cloud: An empirical investigation[END_REF][START_REF] Färber | Linked data quality of dbpedia, freebase, opencyc, wikidata, and yago[END_REF], that aim at studying general characteristics of large KGs in the Web.

Background

In this section, we give the preliminary background and introduce the notation.

We consider a vocabulary of two disjoint sets of symbols2 : L for literals and I for IRIs (Internationalised Resource Identifiers). The elements of T = L ∪ I are called RDF terms, and those of I × I × T are called RDF triples. An RDF knowledge graph G is a set of RDF triples.

Let V be a set of variable symbols disjoint from T , a triple pattern is a tuple t ∈ (I ∪ V ) × (I ∪ V ) × (T ∪ V ), representing an RDF triple with some positions replaced by variables. Any finite set of triple patterns is a basic graph pattern (BGP) P , and forms the basis of SPARQL for answering queries (matching a BGP to a subgraph of G by substituting variables with RDF terms).

We use var(t) and var(P ) to denote the set of variables occurring in a triple pattern t and a BGP P , respectively 3 . A substitution µ is a total mapping from V to T i.e., µ: V → T . The domain of µ, denoted by dom(µ), is the subset of V where µ is defined. Given a triple pattern t and a mapping µ such that dom(µ) := var(t), µ(t) is the triple obtained by replacing the variables in t according to µ. Similarly, given a BGP P and a substitution µ such that dom(µ) := var(P ), µ(P ) is the set of triples obtained by replacing the variables in the triples of P with respect to µ.

Finally, we use the standard notions of entailment, satisfiability and consistency for RDF(S) and OWL [START_REF] Baader | The description logic handbook: Theory, implementation and applications[END_REF][START_REF] Hitzler | Foundations of semantic web technologies[END_REF]. Most importantly, an inconsistent KG is a graph for which no model exists, i.e. a formal interpretation that satisfies all the triples in the graph given the semantics of the used vocabularies. Let E be some entailment relation, and e a triple such that G |= e. A subgraph J(e) of G is called a justification for the inferred triple e, if J(e) |= e, and J s.t. J ⊂ J(e) and J |= e (i.e. a justification is a minimal subset of the knowledge graph that is responsible for the inferred triple). When e is involved in a contradiction, then naturally, its justification J(e) will play a key role in explaining the contradiction.

Defining and Detecting Anti-Patterns

In this section, we introduce the notion of anti-patterns, and describe our approach for retrieving anti-patterns from any inconsistent KG.

Anti-patterns

As previously defined, a justification is a minimal description of a single entailment (or contradiction), which can be represented as an instantiated BGP. If G is consistent w.r.t. some entailment relation E, one could call a BGP P a pattern for G if there is a substitution µ(P ) such that G |= µ(P ). In other words, if there is a variable assignment such that all instantiated graph patterns are entailed by the knowledge graph.

Suppose now that the knowledge graph G is inconsistent w.r.t E. In that case, trivially not every BGP would be a pattern. Therefore we define, the more interesting syntactic notion of a BGP as an anti-pattern for G w.r.t E, as a minimal set of triple patterns that can be instantiated into an inconsistent subset of G. We define the notion of anti-patterns as follows.

Definition 1 (Anti-Pattern). P is an anti-pattern of a Knowledge Graph G if there is a substitution µ(P ) s.t. µ(P ) ⊆ G, and µ(P ) is minimally inconsistent w.r.t some entailment relation E, i.e. P s.t. P ⊂ P and µ(P ) is inconsistent.

For an anti-pattern P , we denote by |P | the size of this anti-pattern, defined as the number of triple patterns in P . We define also the notion of support sup(P ) for an anti-pattern, as the number of substitutions µ(P ). Intuitively, µ(P ) refers to a particular justification in G, and the support refers to the number of justifications occurring in the KG for a certain anti-pattern.

In order to transform a justification into an anti-pattern, we replace the elements in the subject and object position of the BGP with variables. In order to prevent breaking the contradiction, elements appearing in the predicate position of a justification are not replaced in the anti-pattern, with the exception of one case: elements appearing in the predicate position and also appearing in the subject or object position of the same justification. Going back to Example 1, we presented two explanations of contradictions found in the Pizza ontology. Contradiction A shows an inconsistency in the ontology in which the unsatisfiable class CheesyVegetableTopping, that is a subclass of the two disjoint classes CheeseTopping and VegetableTopping, is instantiated. While this example refers to a specific case of a contradiction entailed from the description of these three classes, it also refers to a common type of modelling or linking mistake that can be present in another (part of the) ontology. For instance, using the same principle, the modeller could have also created the class FruitVegetableTopping as subclass of the two disjoint classes FruitTopping and VegetableTopping. This formalisation of certain types of mistakes is what we refer to as anti-patterns. Figure 2 presents the two anti-patterns generalising the justifications of contradictions A and B. For instance in the anti-pattern of contradiction A, the three classes CheesyVegetableTopping, CheeseTopping and VegetableTopping are replaced with the variables C 1 , C 2 and C 3 , respectively. In this anti-pattern, replacing the predicate owl:disjointWith with a variable p 1 would break the contradiction, since p 1 could potentially be matched in the KG with another predicate such as rdfs:subClassOf. On the other hand, we can see in the anti-pattern of contradiction B that the predicate hasTopping is replaced with the variable p 1 , since it also appears in the subject position of the triple hasTopping, rdfs:domain, Pizza . This allows the same anti-pattern to generalise other justifications in the KG, that follow the same pattern but involve a different property than hasTopping.

Approach

This section describes our approach for finding anti-patterns from any inconsistent KG. Finding anti-patterns from a KG would mainly consist of two steps: retrieving justifications of contradictions, and then generalising these detected justifications into anti-patterns. Such approach is expected to deal with multiple dimensions of complexity, mainly: Knowledge Graphs can be too large to query. Now that KGs with billions of triples have become the norm rather than the exception, such approach must have a low hardware footprint, and must not assume that every KG will always be small enough to fit in memory or to be queried in traditional triple stores. Justification retrieval algorithms do not scale. Finding all contradictions, and computing their justifications is a computationally expensive process, as it typically requires loading the full KG into memory. Therefore, when dealing with KGs of billions of triples, existing justification retrieval methods and tools do not scale [START_REF] Bonte | Evaluation and optimized usage of owl 2 reasoners in an eventbased ehealth context[END_REF].

Theoretically, guaranteeing the retrieval of all anti-patterns given any inconsistent KG requires firstly finding all contradictions with their justifications, and then generalising these justifications into anti-patterns. In practice, and as a way to tackle the above listed challenges, our approach introduces a number of heuristics in various steps of the approach. These heuristics emphasises the scalability of the approach, opposed to guaranteeing its completeness regarding the detection of all anti-patterns. Mainly, an initial step is introduced in the pipeline that consists of splitting the original KG into smaller and overlapping subgraphs. Depending on the splitting strategy, this step can impact the number of retrieved justifications, which in its turn can potentially impact the number of the retrieved anti-patterns. In the following, we describe the mains steps of our approach consisting of (1) splitting the KG, (2) retrieving the contradictions' justifications, and (3) generalising these justifications. Figure 3 summarises these three steps.

1. Splitting the KGs. Due to the large size of most recent KGs, running a justification retrieval algorithm over the complete KG to retrieve all contradictions is impractical. To speed up this process or even make it feasible for some larger KGs, we split the KG into smaller subgraphs. Each subgraph is generated by extending a root node as a starting point, that is retrieved by taking a distinct RDF term that appears in the subject position of at least one triple. As a result, the number of generated subgraphs is always equal to the number of distinct Fig. 3: Diagram that shows the pipeline used to extract subgraphs, find justifications in these subgraphs, and generalise these justifications to anti-patterns. subjects in a KG. Using a breadth-first search, the graph is expanded by finding all the triples that have the root node as the subject, and these triples are added to the subgraph. Next, all the nodes in the object position are expanded, together with the predicates, and the graph is expanded as long as possible, or until the maximum amount of triples G max set by the user is reached 4 . In Section 5, we empirically estimate the optimal G max value for large general domain KGs, based on the trade-off between scalability of the approach and its completeness in terms of the detected anti-patterns.

2. Justification retrieval. Out of these newly formed subgraphs, we are only interested in the ones that are inconsistent. Therefore, we firstly check for the consistency of each of these subgraphs and discard the consistent ones. Then, for each of the inconsistent subgraphs, we run a justification retrieval algorithm to retrieve the detected inconsistencies with their justifications. For this, we use the justification retrieval algorithm in the Openllet reasoner with the OWL 2 EL profile, that walks through the graph and finds the minimal justification for each contradiction. It continues to search for justifications until no more justification can be found in the graph 5 . This step is executed for each subgraph, and all the justifications are then pushed to the final stage of the pipeline.

3. Justification generalisation. While most justifications are different, as each one represents a set of instantiated triple patterns, the underlying noninstantiated BGPs do not have to be. The underlying BGP forms the basis of the anti-patterns. To retrieve all anti-patterns from the detected justifications, we first generalise the justification to an anti-pattern by removing the instantiated subject and object on the nodes (when applicable, also the instantiated 4 Alternatively one can use a neighbourhood radius to limit the size of a subgraph instead of Gmax 5 since justification retrieval algorithms can potentially run for a long time in the search for additional justifications in a KG, we set a runtime limit between 10 and 20 seconds based on the considered subgraph size predicate is removed, such as the case described in Section 4.1). Justifications with the same underlying pattern are grouped together. Therefore, given a justification and its generalisation into anti-pattern, we check whether an anti-pattern with the same structure already exists. Comparing anti-patterns with different variable names consists in checking whether these anti-patterns are isomorphic.

For this, we implement a version of the VF2 algorithm [START_REF] Cordella | A (sub) graph isomorphism algorithm for matching large graphs[END_REF], with the addition of matching the instantiated edges of the anti-patterns (i.e. matching the predicates that do not appear in the subject or object position of the same justification).

If the anti-pattern P of a certain justification is matched to an existing antipattern, we group this justification with the other justifications generalised by this anti-pattern, and increment sup(P ) by 1. Otherwise, a new anti-pattern is formed as a generalisation of this justification. This algorithm continues until all justifications have been matched to their corresponding anti-patterns.

Implementation. The source code of our approach is publicly available online

Experiments

As a way of emphasising scalability over completeness, our approach for finding anti-patterns from any inconsistent KG implements an initial step that consists of splitting the KG into smaller and overlapping subgraphs.

In the first part of these experiments (Section 5.1), we empirically evaluate the impact of the subgraph size limit G max on the efficiency of the approach. Then, based on the G max estimated from the first experiment, we show (in Section 5.2) the scalability of our approach on some of the largest KGs publicly available on the Web.

Completeness Evaluation

In this section, we measure the impact of splitting the KG both on the number of detected anti-patterns, and the runtime of the approach. The goal of this experiment is to ultimately find the optimal subgraph size limit to consider in the first step of the approach. For evaluating completeness, this experiment requires datasets in which Openllet can retrieve (almost) all inconsistencies with their justifications. For this, we rely on the three following datasets:

-Pizza ontology: dataset of 1,944 triples serving as a tutorial for OWL. We choose this dataset based on the fact that its contradictions and anti-patterns are known, and therefore can represent a gold standard for our approach. -Linked Open Vocabularies (LOV): dataset of 888,017 triples representing a high quality catalogue of reusable vocabularies for the description of data on the Web [START_REF] Vandenbussche | Linked open vocabularies (lov): a gateway to reusable semantic vocabularies on the web[END_REF]. We choose this dataset since it is small enough to retrieve almost all of its contradictions and their justifications using Openllet. -YAGO: dataset of more than 158 million triples covering around 10 million entities derived from Wikipedia, WordNet and GeoNames [START_REF] Suchanek | Yago: a core of semantic knowledge[END_REF]. We choose this dataset to observe whether the optimal size limit varies significantly between the previous datasets and this relatively larger one.

In the following experiments, we vary the subgraph size limit G max , and observe the number of detected anti-patterns and the corresponding runtime for each of the three steps of our approach. Table 1 presents the first experiment, conducted on the only considered dataset which all of its contradictions are known and can be computed on the whole graph. These results show that splitting the Pizza dataset into smaller, but overlapping, subgraphs does not impact the coverage of the approach, as both available anti-patterns in this dataset are detected even when small subgraph size limits are considered.

Table 1: Impact of the subgraph size limit G max on the number of detected antipatterns and the runtime of the approach (in seconds) for the Pizza dataset. Table 2 presents the results of the same experiment conducted on the LOV and YAGO datasets. We adapt the considered G max to the size of these datasets. These results show that in both datasets, choosing a subgraph size limit of 5,000 triples provides the optimal trade-off between the runtime of the approach and the number of detected anti-patterns for both these KGs. Moreover, and similarly to the previous experiment, we observe that the justification retrieval step (i.e.

Step 2) is the most time consuming step, accounting in some cases up to 94% of the total runtime. Finally, and as it was not possible to run Openllet on graphs larger than 100K triples, this experiment does not guarantee for both datasets that all possible contradictions and anti-patterns can be detected when splitting the graph. Moreover, it does not guarantee that the optimal subgraph size limit Table 2: Impact of the subgraph size limit G max on the number of detected anti-patterns and the runtime of the approach (in seconds) for LOV and YAGO. for these two datasets can be generalised to other datasets. Therefore, we only consider the 5,000 triples limit as an estimation for an optimal G max when splitting large general domain KGs, for the goal of detecting anti-patterns in any inconsistent dataset.

Scalability Evaluation

In the second part of these experiments, we evaluate the scalability of our approach on some of the largest KGs publicly available on the Web. In addition to the YAGO dataset, we choose the two following datasets:

-LOD-a-lot: dataset of over 28 billion triples based on the graph merge of 650K datasets from the LOD Laundromat crawl in 2015 [START_REF] Fernández | Lod-a-lot[END_REF]. -DBpedia (English): dataset of over 1 billion triples covering 4.58 million entities extracted from Wikipedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF].

Based on the results of the previous experiment, we set the value of G max to 5,000 triples and run our approach for each of these three datasets. Table 3 shows that finding most anti-patterns from some of the largest KGs is feasible, but computationally expensive. Specifically, detecting 135 and 13 different anti-patterns in YAGO and DBpedia takes approximately 4 and 13 hours, respectively. Moreover, detecting 222 different anti-patterns from the LOD-a-lot takes almost a full week. This long runtime is mostly due to our naive implementation, as the most costly step of retrieving justifications could be parallelised, instead of sequentially retrieving these justifications for each subgraph.

KG Inconsistency Analysis

In the previous section, we showed that it is feasible to detect anti-patterns from some of the largest KGs in the Web, when the KG is split into overlapping subgraphs with a maximum size of 5,000 triples. In this section, we further analyse these retrieved anti-patterns and compare the detected logical errors between these three KGs.

6.1 What is the most common size of anti-patterns?

We already saw from Table 3 that the largest anti-patterns in the LOD-a-lot, DBpedia, and YAGO contain respectively 19, 12, and 16 edges. Looking at their size distribution, Figure 4 shows that the most common size of an anti-pattern |P | ranges between 11 and 14 triple patterns for LOD-a-lot and YAGO, and between 6 and 11 triple patterns for DBpedia. This result, in addition to a manual verification of some of these anti-patterns, shows that most inconsistencies in DBpedia stem from direct instantiations of unsatisfiable classes, while the ones in LOD-a-lot and YAGO require following longer transitive chains, such as rdfs:subClassOf chains. Anti-patterns represent a generalised notion of justifications that describe common mistakes in a KG. In our analysis of the detected anti-patterns in these three KGs, we found that a number of the different anti-patterns refer to an even more general type of mistakes, and can be further grouped together. This general type of anti-patterns consists of anti-patterns with the same structure of nodes and edges, but with different size. Based on this principle, we can distinguish between three general types of anti-patterns found in these investigated KGs: kite graphs, cycle graphs, and domain or range-based graphs. In addition to the fact that justifications are domain-dependent and possibly complex, understanding and analysing justifications of contradictions can also be impractical due to their redundancy and frequency. This is particularly true in the three large investigated KGs, as we can see in Figure 6. This plot presents the distribution of the anti-pattern support sup(P ) in these three KGs. It shows that the detected anti-patterns make the millions of retrieved justifications in the LOD-a-lot, DBpedia, and YAGO more manageable, by generalising them into 222, 13, and 135 anti-patterns, respectively. Specifically, Table 5 shows that on average each anti-pattern generalises around 5M, 7.7K, and 133K justifications in the LOD-a-lot, DBpedia, and YAGO, respectively. It also shows that a single anti-pattern in the LOD-a-lot generalises more than 45M retrieved justifications. Interestingly, the LOD-a-lot -a dataset that represents the largest publicly available crawl of the LOD Cloud to date-contains over a billion justifications, while DBpedia and YAGO -two of the most popular available RDF datasets-contain around 100K and 18M justifications, respectively. Thus, indicating that the quality of DBpedia (0.0009%), estimated by the number of detected justifications per triple in G, is significantly higher in comparison with LOD-a-lot (3.9%) and YAGO (11.3%).

Conclusion

In this work, we introduced anti-patterns as minimal sets of (possibly) uninstantiated basic triple patterns that match inconsistent subgraphs in a KG. We can use anti-patterns to locate, generalise, and analyse types of contradictions. Retrieving contradictions from a KG and finding the extent to which a KG is inconsistent can now be formulated as a simple SPARQL query using anti-patterns as BGPs. Our second contribution is a tool that can extract a large number of anti-patterns from any inconsistent KG. For evaluating our approach, we showed on relatively small KGs that our approach can detect in practice all anti-patterns despite splitting the KG, and showed on KGs of billions of triples that our approach can be applied at the scale of the Web. Specifically, we showed on the LOD-a-lot, DBpedia, and YAGO datasets that billions of justifications can be generalised into hundreds of anti-patterns. While these findings prove the spread of billions of logically contradicting statements in the Web of Data, this work also shows that these contradictions can now be easily located in other KGs (e.g. using a SELECT query), and possibly repaired (e.g. using a CONSTRUCT query). The source code, as well as the list of detected anti-patterns from these KGs are publicly available as SPARQL queries, with their support in each dataset. We are aiming to extend this work by [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF] including additional datasets such as Wikidata and additional commonly used domain specific datasets, (2) exploiting the previously computed transitive closure of more than half a billion owl:sameAs links [START_REF] Beek | sameas. cc: The closure of 500m owl: sameas statements[END_REF], 3 billion rdf:type statements with 4 million rdfs:subClassOf in the LODa-lot, for the goal of detecting additional types of anti-patterns, and (3) analysing the origins of these anti-patterns which consists of analysing billions of detected justifications, and in the case of the LOD-a-lot dataset also consists of obtaining the provenance of each statement from the LOD Laundromat crawl.

Fig. 1 :

 1 Fig. 1: Screenshot of the ontology editor Protégé showing the explanations of two contradictions found in the Pizza ontology

Fig. 2 :

 2 Fig. 2: Graphical representation of the anti-patterns of the two contradictions found in the Pizza ontology of Example 1, with circles representing the variables V and rectangles representing the RDF terms T .

Fig. 4 :

 4 Fig. 4: Size distribution of the anti-patterns in these three KGs.

Figure 5 Fig. 5 :

 55 Fig. 5: Sample of three anti-patterns, referring to three general types: kite graph (left), cycle graph (middle), and domain or range-based graph (right).

Fig. 6 :

 6 Fig. 6: Distribution of anti-pattern support.

  6 . It is implemented in JAVA, and relies on a number of open-source libraries, mainly jena 7 , hdt-java 8 , openllet9 , and owlapi10 . All experiments in the following sections have been performed on an Ubuntu server, 8 CPU Intel 2.40 GHz, with 256 GB of memory.

Table 3 :

 3 Results of detecting anti-patterns from three of the largest KGs in the Web: LOD-a-lot, DBpedia and YAGO.

		LOD-a-lot	DBpedia	YAGO
	number of triples	28,362,198,927 1,040,358,853 158,991,568
	number of distinct namespaces	9,619	20	11
	number of distinct anti-patterns	222	13	135
	largest anti-pattern size	19	12	16
	runtime (in hours)	157.56	13.01	3.98

Table 4 :

 4 General types of anti-patterns found in these three KGs.

Table 5 :

 5 Impact of generalising justifications to anti-patterns

	sup(P )	LOD-a-lot	DBpedia	YAGO
	Minimum	2	1	1
	Maximum	45,935,769	32,997	379,546
	Average	4,988,176.9	7,796.07	133,998.31
	Median	23,126	4,469	106,698
	Total	1,107,375,273	101,349	18,089,773
	Total per triple	3.9%	0.009%	11.3%

https://protege.stanford.edu/ontologies/pizza/pizza.owl

We do not consider blank nodes in this work.

Therefore, var(t) ⊆ var(P ) whenever t ∈ P .

https://github.com/thomasdegroot18/kbgenerator

https://jena.apache.org

https://github.com/rdfhdt/hdt-java

https://github.com/Galigator/openllet

https://owlcs.github.io/owlapi

https://thomasdegroot18.github.io/kbgenerator/Webpages/ statisticsOverview.html