Jean-Pierre Massat
email: jean-pierre.massat@sncf.fr

Etienne Balmes

Jean-Philippe Bianchi

Guido Van Kalsbeek

François Mitterrand

OSCAR Statement of Methods

OSCAR is the pantograph catenary dynamic software developed by SNCF since 2004. A threedimensional Finite Element mesh allows the modelling of any catenary type: AC or DC designs, conventional or high speed lines. It is representative of the real overhead line geometry, with contact wire irregularities, staggered alignment of the contact wire (CW), dropper spacing, wire tension, etc. Non-linearities, such as slackening of droppers and unilateral contact between the pantograph and the contact wire, are taken into account. Several pantograph models can be used, with a complexity level growing from the three lumped mass model to the multi-body (MB) model. In the second case, a cosimulation between the FEM catenary and the MB pantograph models has been developed. Industrial features for pre and post-treatments were developed to increase robustness of results and optimize computation time. Recent developments include volume meshing of the contact wire for stress computation or statistical analysis and lead to new fields of studies such as fatigue failure or design optimization. OSCAR was fully validated against inline measurements for its different AC and DC catenary models as well as its different pantograph models (with independent strips for instance) and has continuously been certified against EN50318 since 2008.

Introduction

Train operators seek to augment the running speed, increase capacity and improve regularity. Infrastructure managers have to guarantee installations reliability and drastically reduce maintenance costs. Rolling stock has to become interoperable in order to enable railway development, while fulfilling European laws. Inline tests are mandatory to reduce the number of incidents, to assess a new pantograph design, or to optimize operational conditions. But besides accounting for a major risk in projects because of the lateness with which they can be carried out, they also become very costly and are in conflict with commercial use of railway network. Simulation tools can support and shorten these processes by anticipating and complementing inline tests as well as by studying a possible compromise between different above mentioned challenges and are therefore increasingly used. OSCAR (Outil de Simulation du CAptage pour la Reconnaissance des défauts) is the fulfilment of almost 30 years of research and development activities on pantograph-catenary interaction simulation carried out at SNCF. The first model, developed in 1984, was simply based on 2D FEM catenary and linear three lumped-mass models of pantograph. Then, a first multibody pantograph model was included in 1998 [START_REF] Labergri | Modélisation du comportement dynamique du système pantographe-caténaire[END_REF]. In 2004, totally new software named OSCAR was written. A generic 3D finite element model, where any element can be used, allows the representation of a wide variety of catenaries: AC or DC design, with one or more contact wires, with different carrying structures (rigid, from zero to several messenger cables, with or without stitch wire), with a fixed or suspended registration tube, etc. The only constraint is that the contact wire should use prestressed Euler-Bernoulli beams [START_REF] Collina | Numerical simulation of pantograph-overhead equipment interaction[END_REF] [START_REF] Massat | Modélisation du comportement dynamique du couple pantographe-caténaire. Application à la détection de défauts dans la caténaire[END_REF]. In practice the messenger wire is modelled using the same type of elements. The main non-linearities considered in the catenary are contact with the pantograph contact strips and dropper slackening [START_REF] Bobillot | Design of pantograph-catenary systems by simulation[END_REF]. The minimum requirement on contact wire, lets the software go beyond basic simulations by taking into account perturbed situations and singularities. Applications consequently range from design optimizationin plain line track, to the study of specific arrangements like overlap sections or road over-bridges.

Many pantograph types are available based on linear and non-linear lumped-mass models. In 2010, a new feature was introduced to increase accuracy of rolling stock description. Built from CAD, the multi-body pantograph models [START_REF] Labergri | Modélisation du comportement dynamique du système pantographe-caténaire[END_REF][5] open new application fields such as the assessment of geometrical compatibility between pantograph and catenary.

A new plug-in is currently under development for the evaluation of 3D stress fields in the contact wire. Coupled with an iterative contact wire wear procedure, maintenance issues such as fatigue can be addressed.

A special effort was paid in the development of OSCAR to optimize performance and allow industrial use. SNCF takes advantage of this powerful and accurate software to carry out studies and develop its expertise in:

 designing catenary and pantograph systems;  preparing the certification of new systems, drastically decreasing costs; and  assessing new maintenance strategies.

OSCAR is regularly used in industrial cases. One illustrative case was the preparation of the world rail speed record where a speed of 574. Finally, a Graphical User Interface (GUI) is available to ease use and reduce input errors.

Methods as applied in the benchmark

Instructions given by the benchmark statement were entirely followed in simulations performed with OSCAR. This section describes how these instructions were implemented.

The catenary model uses a periodic model of 21 spans, representing a total length of 1155 m (see Figure 1), which is two times longer than the 10 central spans required by instructions. It was built to guarantee that dynamic perturbations involved by pantograph start are stabilized before entering the central 10 spans and boundary conditions do not impact dynamics because of wave reflections. 2.1 Catenary Model OSCAR handles a wide variety of overhead line geometries which can only be achieved by the Finite Element Method (FEM). The overhead line model is fully three-dimensional, including stagger. Two different catenary models were built to follow the benchmark instructions: one 2D model and one 3D model as illustrated in Figure 2. The 2D model is a 3D model without stagger. Therefore, steady arms are kept in the 2D model as shown in Figure 2. The CW and MW meshes are refined to reduce numerical discrepancy, especially due to element passing excited by the moving load. The CW mesh is meshed with zero sag.

The contact wire and the messenger wire use pre-tensioned beam finite elements. These elements are loaded through their modes with three forces (axial and two orthogonal) and three moments (torsion and two bending) and use Hermite shape functions. The element combines a classical Euler-Bernoulli beam formulation with an additional geometric stiffening associated with the axial tension which is necessary to obtain the proper catenary geometry and local stiffness.

Two kinds of catenary non-linearities are considered in OSCAR for this benchmark: dropper slackening and a non-linear static state. Dropper slackening is one of the most important features of pantograph-catenary dynamics software. Bar elements used to model droppers are not refined and only one element links the contact wire to the messenger wire. Specific loads are computed and added to dynamic loads in order to compensate the compressive stress of each dropper.

The calculation of the catenary static state is highly non-linear because of large displacements provoked by gravity and cable elongation. As a consequence, the stiffness of the structure varies according to the mechanical tension applied at the cable ends.

Pantograph model

The pantograph model used in OSCAR is a three lumped mass model as described in the benchmark instructions. It is a linear description of three first vertical dynamic modes of the pantograph. This simplified model is built with mass elements, springs (stiffness) and dampers. A constant speed is applied during the whole simulation case. In the same way, a constant static load is applied during the whole simulation. The distance between the pantograph mass and the catenary contact wire is defined by = -where CWRadius depends on the wear (zero value in the benchmark) and is computed using Hermite shape functions and the corresponding modal displacement and rotation

The contact force follows a non-linear law allowing contact losses to occur:

2D 3D Front view Top view 3D isometric view = - • + _ • ̇ < 0 = 0 > 0
This load is distributed on the two nodes of the finite element in contact with the upper pantograph mass using appropriate shape functions.

2.4 Numerical integration procedure The numerical integration procedure is an implicit Newmark scheme [3][6]. This solver uses a classical prediction followed by correction loops on displacement, velocity and acceleration with exit based on a threshold on the norm of the residual error on the equilibrium. The main benefit of the implicit method is that computation time step can be relatively high (up to 10 -3 s) thus giving a good efficiency.

Initialisation of the problem (steady state configuration of the catenary)

The steady state configuration of the catenary is a key factor in the quality of pantograph-catenary dynamic interaction especially for comparison with inline measurements. Indeed, the pantograph is a moving load running on a flexible discretized geometry that is highly dependent on the gravity and mechanical tension. In OSCAR two methods were developed to compute this static state:

 The mesh is built using geometrical description of each component: dropper lengths, dropper and mast positions, claw masses, etc. Gravity and mechanical tension are applied iteratively to obtain the static state. This method aims at assessing the sag of the catenary.  The contact wire position at each dropper location is imposed, either from external data like the benchmark or from inline measurements of contact wire height. The dropper lengths are adjusted with an iterative method to obtain the equilibrium state of the catenary system. This method is used to identify the dropper length by minimizing the dropper tension error The static computation problem is non-linear because of possible dropper slackening and more importantly because of the relation between geometry and the exact tension in each wire, which is important for fully 3D geometries. An iterative solver is thus set up, where the stiffness matrix based on actual tension is reassembled at each loading step. The second method was used to obtain the contact wire height at each dropper position imposed in the benchmark instructions. The static position is used to initialize the dynamic computation. The stiffness matrix used in dynamics comes from the converged static state and remains constant during the time simulation because of the small displacement hypothesis.

Finally, the initialization process is not realistic because the pantograph speed increases from 0 km/h to the assessed running speed between time steps t 0 and t 1 , contrary to the real conditions which are more progressive. This abrupt starting is damped along the first catenary spans. Nevertheless, this transitional area has to be identified and removed from final analyses. In OSCAR, this study is systematically carried out and post-processing is only applied in an area where dynamics are stabilized.

Additional methods available

OSCAR was initially developed to assess pantograph-catenary dynamics. Pantograph models are lumped mass models, including non-linearities like bump-stops or friction for instance, with one or multiple flexible and tilting contact strips, as shown on Figure 4. Any kind of transition in the catenary can be taken into account. Examples that have been considered are section overlaps, where the pantograph switches between two contact wires within a short period where it is in contact with both wires, level crossings, over-bridges, neutral section systems and so on. One of the major issues for the algorithms is to detect the contact on each wire, taking into account the wire staggers. In the same way, OSCAR manages DC catenaries (compound or not) including several contact and several messenger wires. One of the first uses of OSCAR was a study of the effect of catenary defects on current collection, in order to optimize maintenance by understanding their consequences. An identification of the signatures of each defect allowed their automatic detection by an instrumented pantograph. For that purpose, missing droppers, junction claws, tension variations were introduced in simulation cases [START_REF] Massat | Robust Methods for Detecting Defects in Overhead Contact Line Based on Simulation Results[END_REF].

Simulation expectations have evolved over the past five years especially to address maintenance and interoperability topics. These objectives led to three main developments: a cosimulation process with a multibody pantograph, a volume mesh of the contact wire to compute 3D stress fields and a probabilistic approach to introduce variability and uncertainties in simulation studies.

A cosimulation was designed between the well validated catenary model and a multibody pantograph model [START_REF] Massat | Pantograph catenary dynamic optimisation based on advanced multibody and finite element co-simulation tools[END_REF] which is built from a CAD file (see Figure 5). This detailed geometrical description of the pantograph is necessary to study compatibility with infrastructure or to design new components. The model can be either rigid, partially or fully flexible. Impact of the flexibility of each body can separately be evaluated. In the same way, bushing joints are used to take into account clearance and flexibility in joints. Laboratory tests are used to adjust the model through an experimental modal analysis (EMA). Moreover, the multibody model can be actuated by a pneumatic system including its control system. To do so, data is exchanged between the mechanical workspace and the pneumatic one at each time step. The French pantograph illustrated on Figure 5 is deployed by an air spring whose pressure supply is controlled as a function of the train speed with an open and a closed loop. The cosimulation procedure was optimized to guarantee the efficiency of the simulation tool. The multibody software computes the contact force between the contact wire and the pantograph head. This data is then sent to the FE catenary through the random access memory, which computes the contact wire displacements and so on.

Figure 5 illustrates a typical use of pantograph multibody model in an overhead crossing. A contact wire coming from a side track enters in contact with the pantograph horns. These horns are designed to guide the contact wire on the top of the contact strips, but in some critical conditions the contact wire may slide under the bow and break the pantograph. This detailed pantograph geometry makes it possible to identify these critical cases and propose enhancements of the system. Fracture by fatigue is one of the most critical failures which may occur on the railway network because it is almost unpredictable and induces huge traffic disruptions [START_REF] Sugahara | Preventing Fatigue Breakage of Contact Wires[END_REF]. A plug-in was developed in OSCAR to include a volume model of a part of the contact wire (typically 2 or 3 meters long) and connected elements (such as claws, as illustrated in the right of Figure 6) in a beam catenary mesh. The volume mesh is used in static computations but its use in dynamic computations would lead to prohibitive times as well as irregularities in the contact force around the 1D-3D transition. Therefore dynamics are obtained through an adapted beam model. A static expansion [START_REF] Balmes | Sensors, Degrees of Freedom, and Generalized Modeshape Expansion Methods, International Modal Analysis Conference[END_REF] is used to recover 3D motion and stress fields in order to study fatigue failure of the contact wire through the Dang Van criteria [START_REF]High-Cycle Metal Fatigue in the Context of Mechanical Design[END_REF] and estimate lifetime before crack initiation. In parallel, as shown on Figure 6, an iterative wear model is used to identify the first failure mode [START_REF] Nguyen-Tajan | Fatigue crack initiation risk analysis and crack propagation modelling in the catenary contact wire of high speed lines[END_REF]. Finally, a probabilistic approach is under implementation. Until recently, only a deterministic approach was considered, but the lack of reproducibility of inline measurements was not correctly represented in simulation tools. Considering a perturbed catenary geometry with a non-constant wear along it and with external forces like aerodynamics, OSCAR outputs can be used to optimize either the design or the maintenance tolerance because a wide range of operational conditions are covered. This functionality will be particularly meaningful for virtual certification process: the PantoTRAIN project [START_REF]Proposals for integrations to existing standards and homologation processes and their assessment for safety, quality and practical feasibility[END_REF] shows that variability and uncertainties have to be considered to be representative from inline tests. It was validated against another software which consists in a mono-dimensional analytical model (not presented in this benchmark) which uses displacement decomposition in sine series [START_REF] Massat | Modélisation du comportement dynamique du couple pantographe-caténaire. Application à la détection de défauts dans la caténaire[END_REF]. This method being continuous, it is very useful to validate results from Finite Element simulations which can present numerical discontinuities [START_REF] Bobillot | Design of pantograph-catenary systems by simulation[END_REF] [15][16]. This comparison permitted to define the optimal FE number for instance.

It was validated against inline measurements, at high speeds [START_REF] Massat | Simulation tools for virtual homologation of Pantograph[END_REF] and at conventional speeds, for different catenary designs (light and compound catenaries) and for several pantograph models. It was also validated with catenary defects. The very good agreement allows generating numerical dynamic signatures of catenary defects [START_REF] Massat | Robust Methods for Detecting Defects in Overhead Contact Line Based on Simulation Results[END_REF]. OSCAR was used in two European Projects EUROPAC and PantoTRAIN. In PantoTRAIN, simulation results were compared to inline measurements [START_REF] Massat | Simulation tools for virtual homologation of Pantograph[END_REF]. Several European high speed pantograph-catenary couples were modelled. For each one, the results showed a very good agreement with inline measurements, below 1% of error in the best cases and less than 10% in the worst cases [START_REF]Proposals for integrations to existing standards and homologation processes and their assessment for safety, quality and practical feasibility[END_REF] against EN50367 standard criteria [14] when the EN50318 standard requires a maximum error of ±20%. These good results were obtained either with or without overlap sections (transitions). Finally, it was validated against measurement for single and multiple unit configurations. Recently a blind test was performed against measurements. Simulations were performed before tests and were compared at the end. OSCAR simulation results were again found to be very predictive.

Considerations about results

The numerical stage of the benchmark was defined to assess the spread between existing pantograph-catenary software. The benchmark case is fully defined, addresses problems encountered in pantograph catenary simulation and allows all software to perform the simulation by defining progressive complexity levels. Nevertheless, three remarks can be made on the results.

First, the distance between the starting point of the pantograph and the central spans area defined for analysis can explain some differences between results, especially for the vertical displacement of the steady arm. Indeed, movements observed before the pantograph arrival are due to wave propagation.

Second, the transition period corresponding to the brutal start of the pantograph should be assessed, because it is highly dependent on the initialization procedure of each software. A model including two sections and an overlap area could solve this problem, with a first catenary section dedicated to this transition period and a second catenary section used for analyses. Nevertheless some software may not be able to follow this procedure.

Third, the catenary damping model is a key factor in the dynamic behaviour. Differences of results may be partially explained by the damping model which differs from one software to another. For example, in OSCAR alone, there are four different damping models: proportional (used in this benchmark to follow instructions), piecewise proportional (the most commonly used in studies), modal (the most physical model) and localised (generally coupled with one of the first two models) [START_REF] Bianchi | Using modal damping for full model transient analysis[END_REF].

Conclusions

The benchmark instructions defined a purely numerical case to study the spread between software simulating dynamic pantograph-catenary interaction. The FE software OSCAR was used to follow these instructions, using successively a 2D and 3D model. Static and dynamic results were performed. In both cases, it shows behaviour similar to that of other software. OSCAR is used to capitalize more than 30 years of experience at SNCF. It has been validated against measurement during all development stages and been certified against the EN50318 standard. More complex cases than those defined in the benchmark are more representative of real operation conditions. For instance, overlap areas generally need to be considered. In the last five year, major OSCAR developments were related to multibody pantographs, volume models of the contact wire for fatigue failure studies.

Figure 1 -

 1 Figure 1 -Benchmark simulation case in OSCAR

Figure 2 -

 2 Figure 2 -2D and 3D catenary models used for benchmark.

2. 3

 3 Model of pantograph-catenary contact OSCAR uses a penalty method for pantograph-catenary contact model. It consists in introducing a contact stiffness K Contact and a possible damper C Contact between the pantograph and the contact wire.

Figure 3 -

 3 Figure 3 -Contact scheme used by OSCAR

Figure 4 -

 4 Figure 4 -Three lumped mass model of pantograph and overlap section

Figure 5 -

 5 Figure 5 -Multibody pantograph: overhead crossing simulation

Figure 6 -

 6 Figure 6 -3D model of contact wire for fatigue study (left: CW mesh, middle: worn CW with axial stress colour map, right: 1D-3D mesh connection).

4 .

 4 Validation of the software OSCAR has been certified by an independent body since 2008 with respect to the EN50318 standards [13]. This certification was renewed in 2013 for the latest version of OSCAR.

Table 1 -Figures about catenary model used for the benchmark.

 1

		Finite element type	Number of elements
	Contact wire	Pre-tensioned beam	4240
	Messenger wire Pre-tensioned beam	1266
	Droppers	Bar	189
	Steady arms	Bar	20
	claws	Mass	398
	Pantograph	Mass	3
	Full model		6116


Hatem Baloudi

Gol Sylvain

AND Aref Énia

Jeribi

THE ADJACENCY MATRIX AND THE DISCRETE LAPLACIAN ACTING ON FORMS

Keywords: 2010 Mathematics Subject Classification. 81Q35, 47B25, 05C63 discrete Laplacian, locally finite graphs, self-adjoint extension, adjacency matrix, forms

We study the relationship between the adjacency matrix and the discrete Laplacian acting on 1-forms. We also prove that if the adjacency matrix is bounded from below it is not necessarily essentially self-adjoint. We discuss the question of essential self-adjointness and the notion of completeness.

Introduction

Given a simple graph, the adjacency matrix A is unbounded from above if and only if the degree of the graph is unbounded. It is more complicated to characterize the fact that it is unbounded from below. In [Go] one gives an optimal and necessary. The examples provided in [Go] satisfy : 1) A is not bounded from above, 2) A is bounded from below, 3) A is essentially self-adjoint.

In [Go], one asks the question. Can we have 1 and 2 without having 3? In Corollary 5.3 we answer positively to this question. Moreover, relying on different ideas than in [Go], we provide a large class of graphs satisfying 1 and 2. Our approach is based on establishing a link between the adjacency matrices and the discrete Laplacian ∆ 1 acting on 1-forms.

The article is organized as follows: In Section 2, we present general definitions about graphs. Then we define five different types of discrete operator associated to a locally finite graphs (the adjacency matrix, two discrete Laplacians acting on vertices, two discrete Laplacians acting on edges). The link between these definitions is made in Section 3.2. In Section 4, we start with the question of unboundedness and give a upper bound on the infimum of the essential spectrum. In Section 5.1 we provide a counter example to essential self-adjointness for the Laplacian acting on 1-forms. In Section 5.2 we present the notion of χ-completeness which was introduced in [AnTo] and develop it through optimal examples. Then in Section 5.3 we confront this criterion to other type of approaches. Finally in Section 5.4 we provide a new criterion of essential self-adjointness for the adjacency matrix.

Graph structures

2.1. Generalities about graphs. We recall some standard definitions of graph theory. A graph is a triple G := (E, V, m), where V is countable set (the vertices), E : V × V → R + (the edges) is symmetric, and m : V → (0, ∞) is a weight. When m = 1, we simply write G = (E, V). We say that G is simple if m = 1 and E : V × V → {0, 1}.

Given x, y ∈ V, we say that x and y are neighbors if E(x, y) > 0. We denote this relationship by x ∼ y and the set of neighbors of x by N G (x). We say there is a loop in x ∈ V if E(x, x) > 0. A graph is connected if for all x, y ∈ V, there exists a path γ joining x and y. Here, γ is a sequence x 0 , x 1 , ..., x n ∈ V such that x = x 0 , y = x n , and x j ∼ x j+1 for all 0 ≤ j ≤ n -1. In this case, we endow V with the metric ρ G defined by ρ G (x, y) := inf{|γ|, γ is a path joining x and y}.

(1) A x-triangle given by (x, y, z, x) is different form the one given by (x, z, y, x).

A graph G is locally finite if d G (x) is finite for all x ∈ V. In the sequel, we assume that:

All graphs are locally finite, connected with no loops.

A graph G = (E, V, m) is bi-partite if there are V 1 and V 2 such that V 1 ∩ V 2 = ∅, V 1 ∪ V 2 = V, and such that E(x, y) = 0 for all (x, y) ∈ V 2 1 ∪ V 2 2 .
Definition 2.1. Given a graph G = (E, V, m), we define the line graph of G the graph G := ( E, V) where V is the set of edges of G and

E (x 0 , y 0 ), (x, y) = E(x 0 , y 0 )E(x, y) m(x) 1 x=x0 + E(x 0 , y 0 )E(x, y) m(y) 1 y=y0 ,
if (x 0 , y 0 ) = (x, y) and 0 otherwise.

The choice of the weight Ẽ seems a bit arbitrary but is motivated by Proposition 3.1. We stress that m = 1. Others choices can be made, e.g., [EvLa]. We refer to [Ha][Chapter 8] for a presentation of this class in the setting of simple graphs.

A bipartite graph G

The line-graph of G

A graph K 1,8 K 1,8 is the complete graph K 8
As we see on this example, the line-graph is obtained by gluing together some complete graphs. This is not true in general. The classification of the line-graphs of a finite graph is well-known, see [Ha][Theorem 8.4].

We present the relationship between bipartite graphs and line graphs. We recall that C n denotes the n-cycle graph, i.e., V := Z/nZ, where E(x, y) = 1 if and only if |x -y| = 1.

Proposition 2.2. Let G = (E, V) be a bipartite graph. Then the two following assertions are equivalent:

1) G ≃ G, 2) G ∈ {Z, N, C 2n : n ∈ N}. Proof. It clear that (2) ⇒ (1). Now, suppose that G ≃ G. Then G not contain x-triangles. If d G (x) ≥ 3, for all x ∈ V, then there exist a x-triangle of G. So, d G (x) ≤ 2 ∀x ∈ V. This proof is complete.
2.2. The adjacency matrix. Set G = (E, V, m) a weighted graph. We define the set of 0-cochains C(V) := {f : V → C}. We denote by C c (V) the 0-cochains with finite support in V. We associate a Hilbert space to V.

ℓ 2 (V) := f ∈ C(V) such that f 2 := x∈V m(x)|f (x)| 2 < ∞ .
The associated scalar product is given by

f, g := x∈V m(x)f (x)g(x), for f, g ∈ ℓ 2 (V).
We define the adjacency matrix :

A G (f )(x) := 1 m(x) y∈V E(x, y)f (y) for f ∈ C c (V).
It is symmetric and thus closable. We denote its closure by the same symbol. We denote the degree by

deg G (x) := 1 m(x) y∈V E(x, y).
When m = 1, we have that A G is unbounded if and only it is unbounded from above and if and only if the degree is unbounded. The fact that A G is unbounded from below or not is a delicate question, see [Go]. We refer to [GoSc] for the description of some self-adjoint extensions.

3. The laplacians acting on edges 3.1. The symmetric and anti-symmetric spaces. In the previous section we defined a Hilbert structure on the set of vertices. We can endow two different Hilbert structures on the set of edges. Both have their own interest. Given a weighted graph G = (E, V, m), the set of 1-cochains (or 1-forms) is given by:

C anti (E) := {f : V × V → C, f (x, y) = -f (y, x) for all x, y ∈ V},
where anti stands for anti-symmetric. This corresponds to fermionic statistics. Concerning bosonic statistics, we define:

C sym (E) := {f : V × V → C, f (x, y) = f (y, x) for all x, y ∈ V}.
The sets of functions with finite support are denoted by C c anti (E) and C c sym (E), respectively.

We turn to the Hilbert structures.

ℓ 2 anti (E) :=    f ∈ C anti (E) such that f 2 := 1 2 x,y∈V E(x, y)|f (x, y)| 2 < ∞    and ℓ 2 sym (E) :=    f ∈ C sym (E) such that f 2 := 1 2 x,y∈V E(x, y)|f (x, y)| 2 < ∞    .
The associated scalar product is given by f, g := 1 2 x,y∈V E(x, y)f (x, y)g(x, y), when f and g are both in ℓ 2 anti (E) or in ℓ 2 sym (E). We start by defining operator in the anti-symmetric case. The difference operator is defined as

d := d anti : C c (V) -→ C c anti (E), d(f )(x, y) := f (y) -f (x)
. The coboundary operator is the formal adjoint of d. We set:

d * := d * anti : C c anti (E) -→ C c (V), d * (f )(x) := 1 m(x) y∈V E(y, x)f (y, x).
We denote by the same symbols their closures. The Gauß-Bonnet operator is defined on C c (V) ⊕ C c anti (E) by

D := d + d * ∼ = 0 d * d 0 .
This operator is motivated by geometry, see [AnTo]. It is also a Dirac-like operator.

The associated Laplacian is defined as ∆ := D 2 = ∆ 0 ⊕ ∆ 1 where ∆ 0 is the discrete Laplacian acting on 0-forms given by

(2) ∆ 0 (f )(x) := (d * d)(f )(x) = 1 m(x) y E(x, y)(f (x) -f (y)), with f ∈ C c (V)
, and where the discrete Laplacian acting on 1-forms is given by

∆ 1 (f )(x, y) := (dd * )(f )(x, y) = 1 m(x) z∈V E(x, z)f (x, z) + 1 m(y) z∈V E(z, y)f (z, y), (3) with f ∈ C c
anti (E). Both operator are symmetric and thus closable. We denote the closure by ∆ 0 (resp. ∆ 1 ), its domain by D(∆ 0 ) (resp. D(∆ 1 )), and its adjoint by ∆ * 0 (resp. ∆ * 1 ). In [Wo], one proves that ∆ 0 is essentially self-adjoint on C c (V) when the graph is simple. The literature on the subject is large and refer to [START_REF] Golénia | Hardy inequality and asymptotic eigenvalue distribution for discrete Laplacians[END_REF] for historical purposes. In [AnTo], they prove that

D is essentially self-adjoint on C c (V)⊕C c anti (E) if and only if ∆ 0 ⊕ ∆ 1 is essentially self-adjoint on C c (V) ⊕ C c
anti (E). Moreover they provide a criterion based on the completeness of a metric. In Section 5.1 we provide a counter example to essential self-adjointness for the Laplacian acting of 1-forms. Then in Section 5.2 we discuss the notion of χ-completeness that was introduced in [AnTo]. This notion is related to the one of intrinsic metric, e.g., [HKMW] and references therein.

We turn to the symmetric choice. We set :

d sym : C c (V) -→ C c sym (E), d sym (f )(x, y) := f (y) + f (x). It is interesting to note that d sym is in fact the incidence matrix of G. Indeed d sym (δ x0 )(x, y) = 1, if x 0 ∈ {x, y}, 0, otherwise.
The formal adjoint of the incidence matrix is given by:

d * sym : C c sym (E) -→ C c (V), d * sym (f )(x) := 1 m(x) y∈V E(y, x)f (y, x).
A direct computation gives that :

∆ 0,sym f (x) := (d * sym d sym )f (x) = 1 m(x) y E(x, y)(f (x) + f (y)), for all f ∈ C c (V) and ∆ 1,sym f (x, y) := (d sym d * sym )f (x, y) = 1 m(x) z∈V E(x, z)f (x, z) + 1 m(y) z∈V E(z, y)f (z, y), (4)
for all f ∈ C c sym (E). We denote by the same symbol the closure of these operators. We turn to this central observation.

Proposition 3.1. Set G = (E, V, m). The operator ∆ 1,sym is unitarily equivalent to A G + V (•, •), where V (x, y) := E(x, y) 1 m(x) + 1 m(y)
and G denotes the line-graph of G, see Definition 2.1.

It is important to note that ℓ 2 sym (E) is a weighted space, whereas ℓ 2 ( Ṽ) is not one. This proposition is part of the folklore in the case of finite and unweighted graphs.

Proof. We set U : ℓ 2 sym (E) → ℓ 2 ( Ṽ, 1) as being the unitary transformation given by U f (x, y) := E(x, y)f (x, y). We have

(U ∆ 1,sym U -1 )f (x, y) = z∈V E(x, y)E(x, z) m(x) f (x, z) + E(x, y)E(z, y) m(y) f (z, y) , for all f ∈ C c ( V).
Remembering the definition of the weights for a line-graph, we obtain the result.

Corollary 3.2. Let G = (E, V, m) be a weighted graph. If c := sup x,y∈V E(x, y) 1 m(x) + 1 m(y) < ∞ then A G ≥ -c. In particular, A G ≥ -2 when G is simple.
In the setting of simple graphs, in [Go], one gives a necessary condition for the semi-boundedness of the adjacency matrix. The lower local complexity of a graph G is defined by

C loc (G) := inf N G (x) d 2 G (x) , x ∈ V and d G (x) ≥ n , n ∈ N ,
where N G (x) := ♯{x -triangles}. The sub-lower local complexity of a graph G is defined by

C sub loc (G) = inf {G ′ ⊂G, sup d G ′ =∞} C loc (G ′ ),
where G ′ is a sub-graph of G, i.e., G ′ is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset.

We recall [START_REF] Golénia | Unboundedness of adjacency matrices of locally finite graphs[END_REF]Theorem 1.1]:

Theorem 3.3. Let G = (E, V) be a locally finite graph of unbounded class. Let ÂG be a self-adjoint realization of the A G . Suppose that E is bounded. Then, one has:

1) ÂG is unbounded from above. 2) If C sub loc (G) = 0, then ÂG is unbounded from below. 3) For all ε > 0, there is a connected simple graph G such that C loc (G) ∈ (0, ε), A G is essentially self-adjoint on C c (V)
and is bounded from below.

The line-graph do not lead to the optimality that is obtained in third point. Indeed, by repeating the proof of [START_REF] Golénia | Unboundedness of adjacency matrices of locally finite graphs[END_REF]Proposition 3.2] we obtain that given G = (E, V) be a locally finite simple bipartite graph, then

C sub loc ( G) > 1 10 .
3.2. Breaking symmetry. We have that (3) and ( 4) have the same expression. However they do not act on the same spaces. When G is bi-partite, we shall prove that the two operators are unitarily equivalent. We now fix an orientation of a graph G = (E, V, m). For each edge there are two possible choices. For x, y ∈ V such that E(x, y) = 0, we write x → y or y → x, following the choice of the orientation.

Let U : ℓ 2 anti (E) -→ ℓ 2 sym (E) be the unitary map given by

(U f )(x, y) = sign(x, y)f (x, y), where sign(x, y) := 1, if x → y, -1, if y → x.
Note that (U -1 f )(x, y) = sign(x, y)f (x, y). Therefore, for x 0 , y 0 ∈ V and f ∈ ℓ 2 sym (E) we have

U ∆ 1 U -1 f (x 0 , y 0 ) = sign(x 0 , y 0 ) 1 m(y 0 ) x∈V E(x, y 0 )sign(x, y 0 )f (x, y 0 ) + 1 m(x 0 ) y∈V E(x 0 , y)sign(x 0 , y)f (x 0 , y) . (5)
In order to take advantage of this transformation, one has to choose the orientation in a good way. We have : Proposition 3.4. Assume that G = (E, V, m) is a bi-partite weighted space, then ∆ 1 and ∆ 1,sym are unitarily equivalent. In particular, if we also have that G is simple, ∆ 1 is unitarily equivalent to A G + 2id.

Proof. We consider the bi-partite decomposition {V 1 , V 2 } of the graph G. For x ∈ V 1 and y ∈ V 2 , we set x → y. From (5), we see that all the products of the signs are being 1. This gives the first part. For the rest, apply Proposition 3.1.

Since the line-graph of Z is itself and it is also bi-partite, we can make a different choice of orientation.

Example 3.5. We consider on Z the orientation n → n + 1, for all n ∈ Z.

Note that Z ≃ Z. Moreover, we have:

(U ∆ 1 U -1 )f (n, n + 1) = 2f (n, n + 1) -A G f (n, n + 1).
Therefore, ∆ 1 and 2I -A G are unitarily equivalent.

On the spectral properties of the Laplacian acting on forms

We start with the question of unboundedness.

Proposition 4.1. Let G = (E, V, m) be a weighted graph. Then ∆ 1 is bounded if and only if ∆ 1,sym is bounded if and only if ∆ 0 is bounded if and only if sup x∈V deg G (x) < ∞.
Proof. The last equivalence is well-known, e.g., [START_REF] Keller | Unbounded Laplacians on graphs: basic spectral properties and the heat equation[END_REF]. On one side we have

0 ≤ f, ∆ 0 f ≤ f, 2 deg G (•)f ,
for all f ∈ C c (V) and on the other side δ x , ∆ 0 δ x = deg G (x). The same statements hold true for ∆ 0,sym .

We turn to ∆ 1 . We denote by F the Friedrichs extension.

∆ 1 is bounded ⇔ ∆ F 1 is bounded ⇔ d * is bounded ⇔ d is bounded ⇔ ∆ 0 is bounded.
The second equivalence comes from the fact that (∆ F 1 )

1/2 f = d * f , for all f ∈ C c
anti (E) and by construction of the Friedrichs extension (e.g., [ReSi]). The last one is of the same type. The equivalence with ∆ 1,sym is similar.

Using the Persson's Lemma we give the following result:

Proposition 4.2. Let G = (E, V, m) be an infinite and ∆ F 1 be a Friedrichs extension of ∆ 1 . Then

inf σ(∆ F 1 ) ≤ inf x,y∈V,x∼y 1 m(x) + 1 m(y) E(x, y)
and

inf σ ess (∆ F 1 ) ≤ inf K⊂E,Kfinite inf (x,y)∈K c ,x∼y 1 m(x) + 1 m(y) E(x, y).
In particular, ∆ F 1 is not with compact resolvent when G is simple and infinite. The last statement really differs from the situation case of ∆ 0 . Indeed, in the case of a simple sparse graph (a planar graph for instance), one has that D(∆ [BGK] and also [START_REF] Golénia | Hardy inequality and asymptotic eigenvalue distribution for discrete Laplacians[END_REF]. In particular we have that ∆ 0 is with compact resolvent if and only if lim |x|→∞ deg G (x) = ∞.

1/2 0 ) = D deg 1/2 G (•) , see
Proof. Let x 0 , y 0 ∈ V such that E(x 0 , y 0 ) = 0. Then,

δ x0,y0 -δ y0,x0 E(x 0 , y 0 ) , ∆ F 1 δ x0,y0 -δ y0,x0 E(x 0 , y 0 ) = 1 m(x 0 ) + 1 m(y 0 ) E(x 0 , y 0 ). Recalling δ x0,y0 -δ y0,x0 E(x 0 , y 0 ) = 1. (6)
and the Persson's Lemma, e.g., [START_REF] Keller | Unbounded Laplacians on graphs: basic spectral properties and the heat equation[END_REF][Proposition 18], the result follows.

Remark 4.3. The same result holds true for the operator ∆ 1,sym by changing the into + in (6).

Essential self-adjointness

From now on, we concentrate on the analysis of ∆ 1 . The results for ∆ 1,sym are the same and the proofs need only minor changes. 5.1. A counter example. First it is important to notice that unlike ∆ 0 ∆ 1 , define as the closure of (3), is not necessarily self-adjoint on simple graphs.

Let G = (E, V) be radial simple tree. We denote the origin by ν and the spheres by

S n := {x ∈ V, ρ G (ν, x) = n}. Let off(n) := |S n+1 |/|S n |
be the offspring of the n-th generation.

Theorem 5.1. Let G = (E, V) be a radial simple tree. Suppose that

n → off 2 (n) off(n + 1) ∈ ℓ 1 (N). (7)
Then, ∆ 1 does not essentially self-adjoint on C c anti (E) and the deficiency indices are infinite.

Proof. Set f ∈ ℓ 2 anti (E) \ {0} such that f ∈ ker(∆ * 1 + i) and such that f is constant on S n × S n+1 . We denote the constant value by C n . So, we have the following equation

(off(n) + 1 + i)C n -C n+1 off(n + 1) -C n-1 = 0. Therefore, f | Sn+1×Sn+2 2 = |C n+1 | 2 n+1 i=0 off(i) ≤ 2 |off(n) + 1 -i| 2 off 2 (n + 1) n+1 i=0 off(i)|C n | 2 + 2 1 off 2 (n + 1) n+1 i=0 off(i)|C n-1 | 2 . = 2 |off(n) + 1 -i| 2 off(n + 1) f | Sn×Sn+1 2 + 2 off(n) off(n + 1) f | Sn-1×Sn 2 . Since off 2 (n) off(n + 1)
tends to 0 as n goes to infinity, we get by induction:

C := sup n∈N f | Sn×Sn+1 2 < ∞.
Then, we have

f | Sn+1×Sn+2 2 ≤ 2C |off(n) + 1 -i| 2 off(n + 1) + off(n) off(n + 1)
.

By ( 7), we conclude that f ∈ ℓ 2 (E) and that dim ker(∆ * 1 + i) ≥ 1. Using [START_REF] Reed | Methods of modern mathematical physics tome I-IV[END_REF]Theorem X.36] we derive that ∆ 1 is not essentially self-adjoint.

Finally, since the deficiency indices are stable under bounded perturbation, by cutting off the graph large enough, we reproduce the same proof with an arbitrary large number of identical and disjoint trees, we see that dim ker(∆ * 1 + i) = ∞.

Remark 5.2. For the adjacency matrix, we are able to construct an example of simple graph where the deficiency indices are equal to 1, see [START_REF] Golénia | Comment on "The problem of deficiency indices for discrete Schrödinger operators on locally finite graphs[END_REF]. The case of ∆ 1 is more complicated and we were not able to find an example where the deficiency indices are finite. We leave this question open.

We can answer a problem which was left open in [GoSc].

Corollary 5.3. There exists a locally finite simple graph G = (E, V) such that A G is bounded from below by -2 and such that A G is not essentially self-adjoint on C c (V).

Proof. Combine Theorem 5.1 with Proposition 3.4.

Completeness.

We first recall a criterion obtained in [AnTo]. They introduce the following definition (see references therein for historical purposes).

Definition 5.4. The graph G = (E, V, m) is χ-complete if there exists a increasing sequence of finite set (O n ) n such that V = ∪ n O n and there exist related functions χ n satisfying the following three conditions:

1) χ n ∈ C c (V), 0 ≤ χ n ≤ 1, 2) χ n (x) = 1 if x ∈ O n , 3) ∃C > 0, ∀n ∈ N, x ∈ V, such that 1 m(x) y E(x, y)|χ n (x) -χ n (y)| 2 ≤ C.
The result of [AnTo], can be reformulate as follows:

Theorem 5.5. Take G = (E, V, m) to be χ-complete. Then ∆ 1 is essentially self-adjoint on C c anti (E). Remark 5.6. The converse is an open problem. The aim of the next sections is to tackle it.

5.2.1.

A sharp example. Theorem 5.5 is abstract and may be difficult to check in concrete settings. In [AnTo], they provide only one example. Moreover, they do not give a concrete way to prove that a graph is not χ-complete. To start-off we provide a sharp example.

Proposition 5.7. Let G = (E, V) be a locally finite simple tree, endowed with an origin such that off(n) := off(x) for all x ∈ S n . Then the graph G is χ-complete is and only if

∞ n=1 1 off(n) = ∞.
Example 5.8. Set α > 0. Let G = (E, V) be a locally finite simple tree, endowed with an origin such that off(x) = ⌊n α ⌋ for all x ∈ S n . Then the graph G is χ-complete is and only if α ≤ 2.

Proof. Suppose that the series converges and that G is χ-complete. Let (χ n ) n∈N be as in the definition. Using 3), we get:

|χ n (m) -χ n (m + 1)| ≤ √ C off(m)
.

Moreover, by convergence of the series, there is

N ∈ N such that ∞ k=N 1 ⌊n α ⌋ < 1 2 √ C .
Then, by 2), there is

n 0 ∈ N such that χ n0 (x) = 1 for all |x| ≤ N . Since χ n0 is with finite support, there is M ∈ N such that χ n0 (x) = 0 for all |x| ≥ N + M . Therefore, 1 = |χ n0 (N ) -χ n0 (N + M )| ≤ |χ n0 (N ) -χ n0 (N + 1)| + . . . + |χ n0 (N + M -1) -χ n0 (N + M )| ≤ √ C N +M-1 n=N 1 ⌊n α ⌋ < 1 2 .
Contradiction. Therefore if the series converges, then G is not χ-complete. Suppose now that the series diverges. Set

χ n (x) :=        1, if |x| ≤ n, max   0, 1 - |x|-1 k=n 1 off(k)   , if |x| > n.
Since the series diverges, χ n is with compact support and satisfies the definition of χ-completeness.

5.2.2. 1-dimensional decomposition. We now strengthen the previous example and follow ideas of [BG].

Definition 5.9. A 1-dimensional decomposition of the graph G := (V, E) is a family of finite sets (S n ) n≥0 which forms a partition of V, that is V = ⊔ n≥0 S n , and such that for all x ∈ S n , y ∈ S m ,

E(x, y) > 0 =⇒ |n -m| ≤ 1.
Given such a 1-dimensional decomposition, we write |x| := n if x ∈ S n . We also write B N := ∪ 0≤i≤N S i .

We stress that S 0 is not asked to be a single point.

Example 5.10. Typical examples of such a 1-dimensional decomposition are given by level sets of the graph distance function to a finite set S 0 that is

(8) S n := {x ∈ V, ρ G (x, S 0 ) = n},
where the graph distance function ρ G is defined by (1). Note that for a general 1-dimensional decomposition, one has solely ρ G (x, S 0 ) ≥ n, for x ∈ S n .

We define the inner boundary of S n by S - n := {x ∈ S n , ∃y ∈ S n-1 , E(x, y) > 0} and the outer boundary by S + n := {x ∈ S n , ∃y ∈ S n+1 , E(x, y) > 0}. We now divide the degree with respect to the 1-dimensional decomposition. Given x ∈ S n , we set

deg ± (x) := 1 m(x) y∈Sn±1 E(x, y), deg 0 (x) := 1 m(x) y∈Sn E(x, y),
with the convention that S -1 = ∅. Note that deg = deg

+ + deg -+ deg 0 is inde- pendent of the choice of a 1-dimensional decomposition.
We now give a criterion of essential self-adjointness.

Theorem 5.11. Let G = (E, V, m) be a weighted graph and (S n ) n≥0 be a 1dimensional decomposition. Assume that

∞ n=1 1 a + n + a - n+1 = ∞,
where a ± n := sup x∈S ± n deg ± (x). Then G is χ-complete and in particular, ∆ 1 is essentially self-adjoint on C c anti (E).

S 0 S 1 S 2 S 3 S 4 S 5 S 6
Figure 1. An antitree with spheres S 0 , . . . , S 6 of sizes 1, 7, 13, 5, 9, 20, 3.

Proof. It is enough to check the hypothesis of Theorem 5.5. We set

χ n (x) :=        1, if |x| ≤ n, max   0, 1 - |x|-1 k=n 1 a + k + a - k+1   , if |x| > n.
Since the series diverges, χ n is with compact support. Note that χ n is constant on S n . If x ∈ S m with m > n, we have :

1 m(x) y∈Sm+1 E(x, y)|χ n (x) -χ n (y)| 2 ≤ deg + (x) 1 a + m + a - m+1 . 1 m(x) y∈Sm E(x, y)|χ n (x) -χ n (y)| 2 = 0 1 m(x) y∈Sm-1 E(x, y)|χ n (x) -χ n (y)| 2 ≤ deg -(x) 1 a + m-1 + a - m .
It satisfies the definition of χ-completeness. 5.2.3. Application to the class of antitrees. We focus on antitrees, see also [START_REF] Wojciechowski | Stochastically Incomplete Manifolds and Graphs[END_REF] and [BK]. The sphere of radius n ∈ N around a vertex v ∈ V is the set S n (v) := {w ∈ V, ρ G (v, w) = n}. A graph is an antitree, if there exists a vertex v ∈ V such that for all other vertices w ∈ V \ {v}

N G (w) = S n-1 (v) ∪ S n+1 (v),
where n = ρ G (v, w) ≥ 1. See Figure 1 for an example. The distinguished vertex v is the root of the antitree. Antitrees are bipartite and enjoy radial symmetry.

Proposition 5.12. Let G : (E, V) be a simple antitree whose root is v. Set

s n := ♯S n (v). Assume that n∈N 1 √ s n + s n+1 = ∞
then G is χ-complete and in particular, ∆ 1 is essentially self-adjoint on C c anti (E). Proof. Use Theorem 5.11 with S n := S n (v). 5.3. Other approaches. We present some techniques that ensure essential selfadjointness.

Theorem 5.13. Let G = (E, V, m) be a locally finite graph. Set

M(x, y) := 1 + z∈V 1 m(x) E(x, z) + 1 m(y) E(z, y) . Suppose that sup x,y∈V z∈V 1 m(x) E(x, z)|M(x, y) -M(x, z)| 2 < ∞. Then ∆ 1 is essentially self-adjoint on C c anti (E). Proof. Take f ∈ C c anti (E). We have ∆ 1 f 2 ≤ (x,y)∈V 2 E(x, y) 1 m 2 (x) z∈V E(x, z)f (x, z) 2 + 1 m 2 (y) z∈V E(z, y)f (z, y) 2 = 2 (x,y)∈V 2 E(x, y) 1 m 2 (x) z∈V E(x, z)f (x, z) 2 ≤ 2 (x,y)∈V 2 E(x, y) 1 m 2 (x) t∈V E(x, t) z∈V E(x, z)|f (x, z)| 2 = 2 (x,y)∈V 2 E(x, y) 1 m(x) z∈V E(x, z) f (x, y) 2 ≤ 2 M(•, •)f 2 .
Moreover, noting that M c(x, y) = M c(y, x) and that f (x, y) = -f (y, x) we get:

2| f, [∆ 1 , M(•, •)]f | ≤ f 2 + (x,y)∈V 2 E(x, y) z∈V 1 m(x) E(x, z) M(x, z) -M(x, y) f (x, z) 2 ≤ M(•, •) 1 2 f 2 + (x,y)∈V 2 E(x, y) 1 m(x) t∈V E(x, t) × z∈V E(x, z) 1 m(x) M(x, z) -M(x, y) 2 f (x, z) 2 = M(•, •) 1 2 f 2 + (x,y)∈V 2 E(x, y) t∈V 1 m(x) E(x, t) z∈V E(x, z) 1 m(x) M(x, y) -M(x, z) 2 ≤C f (x, y) 2 ≤ (1 + 2C) M(•, •) 1 2 f 2 .
Applying [START_REF] Reed | Methods of modern mathematical physics tome I-IV[END_REF]Theorem X.37], the result follows.

Example 5.14. Take G = (E, V) to be a simple radial tree such that

sup n∈N |off(n) -off(n + 2)| < ∞,
then ∆ 1 is essentially self-adjoint on C c anti (E). This example can be reached by Theorem 5.5, however for weighted graphs the hypotheses do not seem to fully overlap from one side or from the other.

We now give a more powerful way to check that ∆ 1 is essentially self-adjoint. It seems that this approach is new in the setting of graphs.

Theorem 5.15. Let G = (E, V, m) be a weighted graph. Fix x 0 ∈ V and set

B n := {x ∈ V, ρ G (x 0 , x) ≤ n}. If ∞ n=1   i≤n sup x∈Bi (deg G (x))   -1/2n = ∞ (9) then ∆ 1 is essentially self-adjoint on C c
anti (E). Proof. Since ∆ 1 is non-negative, by [MaMc] or [Nu], it is enough to prove that for all f ∈ C c anti (E):

∞ n=0 ∆ n 1 f -1/2n = ∞.
Set f ∈ C c anti (E). There is n 0 such that supp f ⊂ B 2 n0 , where B 2 n0 := B n0 × B n0 . Note that supp (∆ 1 ) n f ⊂ B 2 n0+n . Therefore

(∆ 1 ) n+1 f ≤ 1 B 2 n 0 +n+1 ∆ 1 1 B 2 n 0 +n+1 • (∆ 1 ) n f ≤ sup x∈Bn 0 +n+1 deg G (x) • (∆ 1 ) n f
since, for all g ∈ C c anti (E) and k ∈ N, we have:

0 ≤ 1 B 2 k g, ∆ 1 1 B 2 k g = x 1 m(x) y E(x, y)1 B 2 k (x, y)g(x, y) 2 ≤ x 1 m(x) y E(x, y) z E(x, z)|1 B 2 k (x, z)g(x, z)| 2 ≤ sup x∈B k deg(x) • 1 B 2 k g 2 .
This concludes the proof.

Remark 5.16. The example of Proposition 5.7 is also covered by Theorem 5.15.

Remark 5.17. A computation shows that the condition (9) is equivalent to

∞ n=1 1 sup x∈Bn (deg G (x)) = ∞,
when sup x∈Bn (deg G (x)) is equivalent to n α ln β (n), as n goes to infinity.

5.4. The case of the Adjacency matrix. We take the opportunity to apply this technique for the adjacency matrix. This improves the results obtained in [GoSc].

Theorem 5.18. Let G = (E, V, m) be a weighted graph. Fix x 0 ∈ V and set B n := {x ∈ V, ρ G (x 0 , x) ≤ n}. If Proof. Since A G is not necessary non-negative, by [MaMc] or [Nu], it is enough to prove that for all f ∈ C c (V)

∞ n=0 A n G f -1/n = ∞.
Set f ∈ C c (V). There is n 0 such that supp f ⊂ B n0 . Note that supp A n G f ⊂ B n0+n . Therefore

A n+1 G f ≤ 1 Bn 0 +n+1 A G 1 Bn 0 +n+1 • A n G f ≤ sup x∈Bn 0 +n+1 deg G (x) • A n G f
since, for all g ∈ C c (V), we have | g, A G g | ≤ g, deg G (•)g .

Corollary 5.19. Let G = (E, V) be a radial simple tree, endowed with an origin such that off(n) := off(x) for all x ∈ S n . Assume that

∞ n=1 1 off(n) = ∞.
Then A G is essentially self-adjoint.

Remark 5.20. Note that the condition (10) is not optimal for the question of selfadjointness in the case of a radial simple tree, see [GoSc][Proposition 1.2] but is optimal in the case of anti-trees, see [START_REF] Golénia | Comment on "The problem of deficiency indices for discrete Schrödinger operators on locally finite graphs[END_REF].

To finish denote by G the line graph of a bipartite graph G. Then, thanks to Proposition 3.1, all the criteria of Sections 5.2 and 5.3 implies that A G is essentially self-adjoint on C c ( Ṽ).

  then A G is essentially self-adjoint on C c (V).

Acknowledgment. SG was partially supported by the ANR project GeRaSic (ANR-13-BS01-0007-01) and SQFT (ANR-12-JS01-0008-01). HB enjoyed the hospitality of Bordeaux University when this work started. We would like to thank Michel Bonnefont for useful discussions.


Tommaso Caselli
email: t.caselli@trentorise.eu

Laure Vieu
email: vieu@irit.fr

Strapparava Carlo

Guido Vetere
email: gvetere@it.ibm.com

P Zza Manci

Aligning Verb Senses in Two Italian Lexical Semantic Resources

This work describes the evaluations of three different approaches, Lexical Match, Sense Similarity based on Personalized Page Rank, and Semantic Match based on Shallow Frame Structures, for word sense alignment of verbs between two Italian lexical-semantic resources, MultiWordNet and the Senso Comune Lexicon. The results obtained are quite satisfying with a final F1 score of 0.47 when merging together Lexical Match and Sense Similarity.

Introduction

Lexical-semantic resources play a key role in many Natural Language Processing tasks, such as Word Sense Disambiguation, Information Extraction, and Question-Answering, among others. The creation of lexical-sematic resources is costly in terms of manual efforts and time, and often important information is scattered in different lexica and difficult to use. Semantic interoperability between resources could represent the viable solution to allow reusability and develop more robust and powerful resources. Word sense alignment (WSA), a research area which has seen an increasing interest in recent years, qualifies as the preliminary requirement for achieving this goal [START_REF] Matuschek | Dijkstra-wsa: A graph-based approach to word sense alignment[END_REF].

The purpose of this work is to merge two Italian lexical-semantic resources, namely Multi-WordNet (Pianta et al., 2002) (MWN) and Senso Comune Lexicon (SCL) [START_REF] Oltramari | Senso Comune: A collaborative knowledge resource for italian[END_REF], by automatically linking their entries. The final result will be two-folded. On the MWN side, this will provide Italian with a more complete and robust version of this lexicon. On the SCL side, the linking with MWN entries will introduce lexical-semantic relations, thus facilitating its use for NLP tasks in Italian, and it will make SCL a structurally and semantically interoperable resource for Italian, allowing its connection to other lexical-semantic resources, sense annotated corpora (e.g. the MultiSemCor corpus [START_REF] Bentivogli | Exploiting parallel texts in the creation of multilingual semantically annotated resources: the MultiSemCor Corpus[END_REF]), and Web-based encyclopedia (e.g. Wikipedia).

This work will focus on our experience on the alignment of verb senses. The remaining of this paper is organized as follows. Section 2 will state the task and describe the characteristics of the two lexica. In Section 3 some related works and the perculiarities of our work are discussed. The approaches we have adopted are described in Section 4. The evaluation is carried out in Section 5. Finally, in Section 6 conclusions and future work are reported.

Task and Resources

Following [START_REF] Matuschek | Dijkstra-wsa: A graph-based approach to word sense alignment[END_REF], WSA can be defined as the identification of pairs of senses from two lexical-semantic resources which denote the same meaning. For instance, the two senses of the verb "love", "feel love or affection for someone" and "have a great affection or liking for" (taken from translated SCL and MWN, respectively), must be aligned as they are clearly equivalent in meaning.

MultiWordNet

MWN is a multilingual lexicon perfectly aligned to Princeton WN 1.6. As in WN, concepts are organized in synonym sets (synsets) which are hierarchically connected by means of hypernym relations (is a). Additional semantic relations such as meronymy, troponymy, nearest synonym and others are encoded as well. The Italian section of MWN is composed of 38,653 synsets, with 4,985 synsets for verbs. Each synset is accompanied by a gloss describing its meaning and, when present, one or more examples of use. Overall 3,177 glosses (8,21%) are in Italian and, in particular, 402 for verbs.

Senso Comune Lexicon

SCL is part of a larger research initiative [START_REF] Oltramari | Senso Comune: A collaborative knowledge resource for italian[END_REF]) which aims at building an open knowledge base for the Italian language. The lexicon entries have been obtained from the De Mauro GRADIT dictionary and consist in the 2,071 most frequent Italian words, for a total of 11,939 fundamental senses. As for verbs we have 3,827 senses, corresponding to 643 lemmas, with an average polysemy of 5.9 senses per lemma. In SCL, word senses are encoded following lexicographic principles and are associated with lexicographic examples of usage. SCL comprises three modules: i.) a module for basic ontological concepts; ii.) a lexical module for linguistic and lexicographic structures; and iii.) a frame module for modeling the predicative structure of verbs and nouns. The top level ontology is inspired by DOLCE (Descriptive Ontology for Linguistic and Cognitive Engineering) [START_REF] Masolo | Wonderweb deliverable D17: the wonderweb library of foundational ontologies[END_REF]. Ontological classification of verb entries will start in the near future. With respect to MWN, word senses are not hierarchically structured and no semantic relation has been encoded yet. Senses of polysemous entries have a flat representation, one following the other.

Related Works

Previous works in WSA can be divided into two main groups: a.) approaches and frameworks which aim at linking entries to WN from lexica based on different models (Rigau and Agirre (1995); [START_REF] Navigli | Meaningful clustering of senses helps boost word sense disambiguation performance[END_REF]; Roventini et al. ( 2007)) or language resources, such as Wikipedia (Ruiz-Casado et al. (2005); [START_REF] Mihalcea | Using Wikipedia for automatic word sense disambiguation[END_REF]; Niemann and Gurevych (2011)), and b.) approaches towards the merging of different language resources (Navigli and Ponzetto (2012)). Our work clearly fits into the first group. While different methods are employed (similarity-based approaches vs. graphbased approaches), common elements of these works are: i.) the extensive use of the lexical knowledge of the sense descriptions; e.g. the WN glosses or an article first paragraph as in the case of Wikipedia; and ii.) the extension of the basic sense descriptions with additional information such as hypernyms for WN entries, domains labels or categories for dictionaries or Wikipedia entries to expand the set of available information, thus improving the quality of the alignments. The large of these works focuses on aligning noun senses. The only work which also tackles verb sense alignment is [START_REF] Navigli | Meaningful clustering of senses helps boost word sense disambiguation performance[END_REF] where entries from the Oxford English Dictionary (OED) are mapped to WN. The author explores two methods: a.) a pure lexical matching function based on the notion of lexical overlap [START_REF] Lesk | Automatic sense disambiguation using machine readable dictionaries: how to tell a pine code from an ice cream cone[END_REF] of the lemmas in the sense descriptions; and b.) a semantic matching based on a knowledge-based WSD system, Structural Semantic Interconnections (SSI), built upon WN and enriched with collocation information representing semantic relatedness between sense pairs. Both approaches are evaluated with respect to a manually created gold standard. The author reports an overall F1 measure of 73.84% for lexical matching (accuracy 66.08%), and of 83.11% for semantic matching (accuracy 77.94%). Alignment performances on single parts of speech are not reported.

With respect to the SCL, the OED has some advantages, namely i.) the distinction between core senses and subsenses for polysemous entries; ii.) the presence of hypernyms explicitly signalled; and iii.) domain labels associated with word senses. Such kind of information is not present in the SCL where senses are presented as a flat list and no enrichment of the sense descriptions with additional information is available. Moreover, the low number of MWN glosses in Italian prevents a straightforward application of state-ofthe-art methods for sense alignment. MWN sense descriptions must be built up in different ways. Summing up, the main issue we are facing is related to data sparseness, that is how to tackle sense alignment when we have few descriptions in Italian (MWN side) and few meta-data and no structuration over senses (SCL side).

Methodology

The automatic alignment of senses has been conducted by applying three approaches Lexical Match, Sense Similarity and Semantic Match.

Lexical Match

In the first approach, Lexical Match, for each word w and for each sense s in the given resources R ∈ {MWN, SCL} we constructed a sense description d R (s) as a bag of words in Italian. Provided the different characteristics of the two resources, two different types of bag of words have been built. As for the SCL, the bag of words is represented by the lexical items in the textual definition of s w , automatically lemmatized and part-of-speech analyzed with the TextPro tool suite (Pianta et al., 2008) with standard stopword removal. On the other hand, for each synset, S, the sense description of each MWN synset was built by optionally exploiting:

• the set of synset words in a synset excluding w;

• the set of direct hypernyms of s in the taxonomy hierarchy in MWN (if available);

• the set of synset words in MWN standing in the relation of nearest synonyms with s (if available);

• the set of synset words in MWN composing the manually disambiguated glosses of s from the "Princeton Annotated Gloss Corpus"1 . To extract the corresponding Italian synset(s), we have ported MWN to WN 3.0;

• the set of synset words in MWN composing the gloss of s in Italian (when available);

• the set of synset words in MWN standing in the relations of entailment/is entailed, causes/is caused with s;

The alignment of senses is based on the notion of lexical overlap.

We used the Text::Similarity v.0.09 module2 to obtain the overlap value between two bags of words. Text similarity is based on counting the number of overlapping tokens between the two strings, normalized by the length of the strings.

Sense Similarity

In the second approach, Sense Similarity, the basis for sense alignment is the Personalized Page Rank (PPR) algorithm [START_REF] Eneko | Personalizing PageRank for Word Sense Disambiguation[END_REF] relying on a lexical-semantic knowledge base model as a graph G = (V, E) as available in the UKB tool suite3 . As knowledge base we have used WN 3.0 extended with the "Princeton Annotated Gloss Corpus". Each vertex v of the graph is a synset, and the edges represent semantic relations between synsets (e.g. hyperonymy, hyponymy, etc.). The PPR algorithm ranks the vertices in a graph according to their importance within the set and assigns stronger initial probabilities to certain kinds of vertices in the graph. The result of the PPR algorithm is a vector whose elements denote the probability for the corresponding vertex that a jumper ends on that vertex if randomly following the edges of the graph.

To obtain the PPR vector for a sense s of the SCL, we translated the Italian textual definitions in English by means of a state-of-the-art Machine Translation system4 , automatically lemmatized and part-of-speech analyzed with the TextPro tool suite, removed standard stopwords, and applied the UKB tool suite. The PPR vector is, thus, a semantic representation overall the entire WN synsets of the textual definition of s in SCL.

As for the MWN synsets, instead of building the PPR vector by means of the lexical items composing the sense description, we have passed to the UKB tool suite the WN synset id, thus assuming that the MWN synset is already disambiguated. Given two PPR vectors, namely ppr mwn and ppr scdm for the MWN synset w syn and for the SCL sense w scdm , we calculated their cosine similarity. On the basis of the similarity score, the sense pair is considered as aligned or not.

Semantic Match: Exploiting Shallow Frames Structures

On the basis of (Roland and Jurafsky, 2002) and current research activities in Senso Comune [START_REF] Chiari | An open knowledge base for italian language in a collaborative perspective[END_REF], we assume as working hypothesis that different verb senses tend to correlate with different shallow frame patterns. Thus, we consider two verb senses to be aligned if the shallow frames structures (SFS) of their examples of use are the same. We assume as a SF structure the syntactic complements of the verb, with no distinction between arguments and adjuncts, and the semantic type of the complement filler(s). An example of an SFS is reported in example 1. • for each verb, we have automatically extracted all syntactic complements standing in a dependency relation of argument or complement, together with the lemma of the slot filler;

• nominal lemmas of syntactic complements have been automatically assigned with one of the 26 semantic types composing the WN supersenses (i.e. noun.artifact; noun.object etc. [START_REF] Ciaramita | Supersense tagging of unknown nouns in WordNet[END_REF])) on the line of [START_REF] Lenci | Lexit: A computational resource on italian argument structure[END_REF]. For each nominal filler, we selected the most frequent WN supersense. Sense frequency had been computed on the basis of MultiSemCor. In case a polysemous noun lemma was not present in the MultiSemCor data or its senses have the same frequency, all associated WN supersenses were assigned. As for verbal fillers, we assigned the generic semantic type of "verb.eventuality". Finally, in case a lemma filler of a syntactic complement is not attested in MWN such as a pronoun or a missing synset word, no values is assigned and the SFS is excluded from the possible matches.

Optionally, when the noun filler was annotated with a synset in MultiSemCor, we have associated it to its corresponding WN supersense.

To clarify how this type of sense alignment works, consider the data in example 2. In 2a., we report the SFSs for the examples of use associated with the sense "vivere abitualmente in un luogo" [to live habitually in a place] of the verb "abitare' [to live] in the SCL. In 2b., we report the SFSs extracted from the MultiSem-Cor corpus for the MWN synset v#01809405, with gloss "make one's home or live in"5 .

Experiments and Evaluation

Gold Standard

To evaluate the reliability of the approaches with respect to our data, we developed a gold standard. The gold standard is composed by 44 lemmas selected according to frequency and patterns in terms of semantic and syntactic features6 . It is composed by 350 sense pairs obtained by manually mapping the MWN synsets to their corresponding senses in the SC lexicon. These verbs correspond to 279 synsets and 424 senses in the SCL. Overall, 211 of the 279 MWN synsets have a corresponding sense in the SCL (i.e. SCL covers 84.22% of the MWN senses in the data set), while 235 out of 424 SCL senses have a correspondence in MWN (i.e MWN covers 49.76% of the SCL senses). Average degree of polysemy for MWN entries is 6.34, while for the SCL is 9.63.

Results

The evaluation is based on Precision (the ratio of the correct alignment with respect to all proposed alignments), Recall (the ratio of extracted correct alignment with respect to the alignments in the gold standard), and F-measure (the harmonic mean of Precision and Recall calculated as 2P R/P +R). As baseline, we implemented a random match algorithm, rand, which for the same word w in SCL and in MWN assigns a random SCL sense to each synset with w as synset word, returning a one-to-one alignment. For the Lexical Match and Sense Similarity approaches, the selection of the correct alignments has been obtained by applying two types of thresholds with respect to all proposed alignments (the "no threshold" row in the tables): i.) a simple cut-off at specified values (0.1; 0.2); ii.) the selection of the maximum score (either overlap measure or cosine; row "max score" in the tables) between each synset S and the proposed aligned senses of the SCL. For the maximum score threshold, we retained as good alignments also instances of a tie, allowing the possibility of having one MWN synset aligned to more than one SCL sense.

Lexical Match Results

We have analyzed different combinations of the sense representation of a synset. We developed two basic representations: SYN, which is composed by the set of synset words excluding the target word w to be aligned, all of its direct hypernyms, the set of synset words in MWN standing in the relation of nearest synonyms and the synset words obtained from the "Princeton Annotated Gloss Corpus"; and SREL, which contains all the items of SYN plus the synset words included in the selected set of semantic relations. The results are reported in Table 1. Both sense configurations, SYN and SREL, outperform the baseline rand. However, the Recall with no filtering (no threshold) has extremely low levels, ranging from 0.32 for SREL to 0.29 for SYN, pointing out that the two resources use different ways to encode the verb senses. Globally, the SREL sense representation does not perform better than SYN. When no filtering is applied the SREL configuration has an improvement in the Recall (+0.03) but not in Precision (-0.03), signal-ing that the semantic relations have a limited role in the description of verb senses and for identifying key information encoded in the SCL glosses. The difference in performance of the SREL configuration is not statistically significant with respect to the SYN configuration (p > 0.05). Provided this limited effect of the extended semantic relations, we have decided to select the SYN configuration as the best since it is simpler and with better values for Precision.

To improve the results, we have extended the SYN basic representations with the lexical items of the MWN Italian glosses (+IT) 7 . The results are illustrated in Table 2. The extension of the basic sense representations with additional data is positive. In particular, it improves the alignment (for the no-threshold results, F1=0.37 vs. F=0.35 for SREL and F1=0.34 for SYN) as they introduce information which better represents the sense definition than the synset words in the bag of words and overcomes missing information in the WN 3.0 annotated glosses. The positive effect of the original Italian data points out a further issue for our task, namely that the derivation of sense representations of MWN synsets by means of synset words (including the sense annotated glosses of WN 3.0) is not equivalent to having at disposal the original glosses.

Concerning the filtering methods, the maximum score filter provides the best results for Precision at a low cost in terms of Recall, with F1 scores ranging between 0.34 (SYN+IT) to 0.29 (SYN).

Sense Similarity Results

The results for the Sense Similarity obtained from the Personalized Page Rank algorithm are illustrated in Table 3.

Similarly to the Lexical Match, the Sense Similarity approach outperforms the baseline rand.

Overall, the differences in performance with the 7 The Italian MWN glosses for the items in the Golds are present for 24% senses of the verbs By observing the figures, we can notice that the simple cut-off thresholds provide better results with respect to the maximum score. The best F1 score (F1=0.32) is obtained when setting the cosine similarity to 0.1, though Precision is less than 0.50 (namely, 0.47). When compared with threshold value of 0.1 of the Lexical Match, Sense Similarity yields the best Precision (P=0.47 vs. P=0.42 for Verb SYN, P=0.38 for Verb SYN+IT, and P=0.40 for Verb SREL). Similar observations can be done when the threshold is set to 0.2. In this latter case, Sense Similarity yields the best Precision score with respect to all other filtering methods and the Lexical Match results obtained with maximum score (P=0.66 vs. P=0.59 for Verb SYN, P=0.63 for Verb SYN+IT, and P=0.60 for Verb SREL). The better performance of the simple cut-off thresholds with respect to the maximum score is due to the fact that aligning senses by means of semantic similarity provides a larger set of alignment pairs and facilitates the identification of multiple alignments, i.e. one-to-many.

Semantic Match Results

In Semantic Match we ran three different experiments, namely Most Frequent Sense, where the assignment of the semantic type of the SF slot fillers is based on the most frequent sense; Most Frequent + Correct Sense, where the assignment of the semantic type of the SF slot fillers is based on the most frequent sense and on the annotated sense for the MultiSemCor data, where available, and, finally, Most Frequent + Correct + Vector Similarity, where the assignment of the semantic type of the SF slot fillers is the same as in Most Frequent + Correct Sense plus an additional filtering for nominal SF fillers based on the vector pair WN similarity measure implemented in the WordNet::Similarity package8 . The results obtained are disappointing. With the exception of Precision, all experiment configurations obtain Recall values lower than the baseline rand, suggesting that this approach, though linguistically and theoretically sound, suffers from serious flaws. Both Lexical Match and Sense Similarity outperforms this methods even when no filtering is applied.

For this approach, the low levels for Precision and Recall cannot be explained by means of "lexical gaps" or filtering methods. On the basis of manual analysis of the false negative and false positive data, we could claim that the main reasons for these results are due to:

• the reduced number of examples of in the SCL and their nature as "lexicographic" examples of use;

• the high variability in the syntactic realizations of the complements;

• missing annotated senses in the MultiSemCor corpus;

• parsing errors; and

• the difficulty in acquiring complete SFSs from the MultiSemCor data due to the pres-ence of SF slot fillers realized by pronouns whose assigment of the semantic type depends on their (anaphoric) resolutions.

In addition to this, the low levels of Precision are also due to the coarse-grained categories of the semantic types of the nominal slot fillers. For instance, the SCL examples of use of two different fundamental senses of the verb "aprire" [to open], namely "aprire il rubinetto" [to open the tap] and "aprire la porta" [to open the door] were all wrongly mapped to the same MWN synset, i.e. v#00920424 "cause to open or to become open; "Mary opened the car door"". To keep these senses separated, finer-grained semantic features for describing the semantic types of their nominal fillers, here both "noun.artifact", should be employed. The use of vector pairs WN similarity is an attempt into this direction which, however, resulted unsuccesful.

Merging the Approaches

As the three approaches are different in nature both with respect to the creation of the sense descriptions (simple bag of words vs. semantic representation vs. frame structures) and to the methods with which the alignment pairs are extracted, we have developed a further set of experiments by merging together the results obtained from the Lexical Match, Sense Similarity, and Semantic Match. As parameters for the identification of the best results we have taken into account the Precision and F1 values. We have excluded the presence of Italian data from the sense descriptions of the Lexical Match approach due to their sparseness. As for the Sense Similarity approach, we have selected the cut-off threshold at 0.2. For the Semantic Match we have selected the Most Frequent + Correct configuration. As for the merging we obtained four data sets: SYN+ppr02, which meges the Lexical Match and Sense Similarity methods, SYN+SM, which merges Lexical Match and Semantic Match, ppr02+SM, which merges Sense Similarity and Semantic Match, and SYN+ppr02+SM, which merges all three methods. The results are reported in Table 4.

The combination of the best result yields the best performance with respect to the stand-alone approaches. In particular, we obtain an F1=0.47 for SYN-ppr02, with an improvement of 18 points with respect to SYN, of 21 points with respect to Sense Similarity with threshold 0.2, and of 38 points with respect to Semantic Match. Furthermore, it is interesting to observe that the F1 score for SYN+SM (F1=0.33) and ppr02+SM (F1=0.31) are higher that those of SYN with maximum score filter (F1=0.29) and PPR -0.2 (F1=0.26), suggesting that there is a kind of complementarity among the three alingment methods. However, the alignments from the Semantic Match method are noisy with respect to those obtained from Sense Similarity and Lexical Match. When merging the three methods together, SYN+ppr02+SM, we do not register any improvement but a lowering of the performances with the exception of Recall. This calls for a careful use of such data in this task, suggesting that simpler aligning methods are more robust.

Conclusion and Future Work

This paper reported on experiments on the automatic alignment of verb senses from two different resources when few data are available. In particular, the lack of Italian glosses in MWN and the absence of any kind of structured information in the SC lexicon posed a serious issue for the straightforward application of state-of-the-art techniques for sense alignment.

We explored three different methods for achieving sense alignment: Lexical Match, Sense Similarity, and Semantic Match. In all cases, we are facing low scores for Recall which point out issues related to data sparseness in our lexica. By comparing the results of the three approaches, we can observe that i.) the Sense Similarity yields the best Precision; ii.) Lexical Match, including minimal semantically related items (i.e. SYN) is a dumb but powerful approach for this kind of tasks; iii.) Semantic Match suffers from data sparseness and also from a certain mismatch between corpus data and lexicographic examples. This latter aspect impacts on the application of more complex approaches grounded on linguist theories to automatic methods for sense alignment. It also calls for an extension of the amount of manually annotated data and better methods of semantic typing of the SF slot fillers, as the poor results of Most Frequent + Correct + Vector Similarity show. Furthermore, lexicographic examples of use from SCL, and probably most of the other lexicographic dictionaries, are rather simple and not always prototypical with respect to the actual sense realization in real corpus data. Distributional approaches on SFS acquisition could be helpful to improve this method, provided that reliable ways for assigning SFSs to verb senses encoded in existing resources are developed.

Finally, Sense Similarity based on PPR and Lexical Match qualify as real complementary methods for achieving reliable sense alignments in a simple way and when dealing with few data. Our merged approach provides satisfying results with an overall F1=0.47. The alignment of verb senses is not a simple task as verbs tend to have more abstract definitions than nouns and rely on semantic relations such as entailment which are still poorly encoded in existing resources. Future work will concentrate on the aligned sense pairs obtained by SYN+ppr02 to experiment techniques to reduce the sense descriptions in MWN and in SCL to boostrap better sense alignments, and on the exploitation of crowdsourcing on pre-aligned data to collect additional information on SF structures.

1.

  Marco ha comprato un libro. [Marco bought a book.] Verb: comprare [to buy] SFS: SUBJ[person] OBJ[artifact] To obtain the SFSs, two different strategies have been used. For the SCL, we have extracted all the lexicographic examples of use associated to each verb sense. For MWN, to recover a larger number of examples of use in Italian, we have exploited the data in the MultiSemCor corpus v1.0, a parallel corpus of English and Italian annotated with WN senses. For each sense annotated verb in the Italian section of MultiSemCor, we extracted all available corpus-based examples and obtain the SFS to be compared with the SCL instances. The acquisition of the SFSs has been obtained as follows: • the SCL examples and the MultiSemCor data have been parsed with a state-of-the-art dependency parser (Attardi and Dell'Orletta, 2009);

  2a. COMP-PREP I N [noun.location]. COMP-PREP C ON [noun.group] COMP-PREP A [noun.location] By comparing the SFSs, the COMP-PREP I N [noun.location] structure is the same in both senses, thus pointing to the alignment of the two entries.

	2b. COMP-PREP DA [noun.person]
	SUBJ[noun.person]	COMP-
	PREP DA [noun.group]
	COMP-PREP I N [noun.location]

Table 1 :

 1 Results for Lexical Match alignment for SYN and SREL sense representations.

	Lexical Match	P	R	F1
	SYN -no threshold	0.41 0.29 0.34
	SYN -≥ 0.1 SYN -≥ 0.2 SYN -max score	0.42 0.26 0.32 0.54 0.11 0.18 0.59 0.19 0.29
	SREL -no threshold 0.38 0.32 0.35
	SREL -≥ 0.1 SREL -≥ 0.2 SREL -max score	0.40 0.27 0.32 0.53 0.11 0.18 0.60 0.20 0.30
	rand	0.15 0.06 0.08

Table 2 :

 2 Results for Lexical Match alignment adding the Italian MWN glosses.

	Lexical Match	P	R	F1
	SYN+IT -no threshold 0.36 0.38 0.37
	SYN+IT -≥ 0.1 SYN+IT -≥ 0.2 SYN+IT -max score	0.38 0.31 0.34 0.51 0.13 0.20 0.63 0.23 0.34
	rand	0.15 0.06 0.08

Table 4 :

 4 Results for Semantic Match experiments.

	Semantic Match		P	R	F1
	Most Frequent Sense		0.21 0.05 0.08
	Most Frequent + Correct Sense	0.33 0.05 0.09
	Most Frequent + Correct + Vector Similarity 0.34 0.02 0.04
	rand				0.15 0.06 0.08
	Similarity Measure	P	R	F1
	PPR -no threshold	0.10 0.9 0.19
	PPR -≥ 0.1 PPR -≥ 0.2 PPR -max score	0.47 0.25 0.32 0.66 0.16 0.26 0.42 0.20 0.27
	rand	0.15 0.06 0.08

Table 3 :

 3 Results for automatic alignment based on Similarity Score. Lexical Match results are not immediate. In general, as the Recall value for no threshold filtering shows, almost all aligned sense pairs of the gold are retrieved, outperforming the Lexical Match approach. This difference is related to the different nature of the sense descriptions, i.e. a semantic representation based on a lexical knowledge graph, which is able to catch semantically related items out of the scope for the Lexical Match approach.

Table 4 :

 4 Results for automatic alignment merging the best results from the three approaches.

	Merged	P	R	F1
	SYN+ppr02	0.61 0.38 0.47
	SYN+SM	0.48 0.25 0.33
	ppr02+SM	0.52 0.22 0.31
	SYN+ppr02+SM 0.50 0.38 0.43

http://wordnet.princeton.edu/glosstag.shtml

http://www.d.umn.edu/∼tpederse/text-similarity.html

http://ixa2.si.ehu.es/ukb/

We use Google Translate API.

No Italian gloss available for this synset.

A subset of these verbs have been taken from[START_REF] Jezek | Capturing coercions in texts: a first annotation exercise[END_REF]

http://wn-similarity.sourceforge.net/

E. Pianta, L. Bentivogli, and C. Girardi. 2002. MultiWordNet: developing an aligned multilingual database. In First International Conference on Global WordNet, Mysore, India.


Aurore Payen

Ludovic Journaux

Clément Delion

Lucile Sautot

Bruno Faivre

Efficient unsupervised clustering for spatial bird population analysis along the Loire river

come   L'archive ouverte pluridisciplinaire

The longitudinal distribution pattern of organisms along rivers is a major research topic in ecology, initiates for invertebrates by Illies, for fishes by Huet and on bird population by Frochot & al. [START_REF] Frochot | Nesting birds assemblages along the river loire: result from a 12 years-study[END_REF]. In these works, ornithologists want to analyze spatiotemporal distribution of bird communities in order to study river zonation by detecting ecological discontinuities due to geomorphology of landscapes (discontinuities resulting from birds species assemblage). Biologists usually use Principal Component Analysis (PCA) in order to explain the longitudinal distribution pattern and find discontinuities along the upstream-downstream gradient of the river. Unfortunately, despite the robust reputation of PCA analysis on real-life data, it appears that this method is not able, with 19.82% of contribution on the two first factorial axis, to account these discontinuities which are nevertheless forebode by specialists. So, PCA shows a strong limitation in this case. To overcome this problem, it is interesting to use Non Linear Dimensionality Reduction (NLDR) methods to transform high-dimensional data into a meaningful low dimension representation. Numerous studies have aimed to compare NLDR algorithms, usually using synthetic data such as a swissroll [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF], but less for natural data. So, this paper explore and compare recent NLDR methods with different data transformations in order to find out the best approach in this ecological context. This paper is organized as follows. Section 2 presents the real-life dataset used on this context, the data transformations and an NLDR methods overview with a comparison based on a quality assessment. Section 3 presents and discusses experimental results. Section 4 draws the conclusions.

Materials and methods

Real-life dataset and transformation

Our dataset comes from the census birds STORI 1 program for nesting birds along the Loire River (France) [START_REF] Frochot | Nesting birds assemblages along the river loire: result from a 12 years-study[END_REF]. STORI aims to observe spatiotemporal changes into bird populations along rivers.198 census points were defined along the Loire. At each point birds are identified with the PAI (Punctual Abundance Index) method [START_REF] Frochot | Nesting birds assemblages along the river loire: result from a 12 years-study[END_REF] during four census campaigns. Bird abundances were described by a semiquantitative abundance index. One of the main objective is to study global/local factors that explain bird abundances changes. Finally, we consider 140 birds species along the 198 census points. In practice, ornithologists capped PAI to 5 even if there is more than 5 couples of birds. Unfortunately, this approximation is not relevant because variables are expected to have a Gaussian distribution. Distribution of the variables are centered on the value of two couples. The number of couples should decrease, passed the center of the distribution. So the number of 4 couples should be superior than the number of 5 couples. 23 species among 140 have more PAI of 5 than 4, which means the census is over estimated. So in order to preserve or improve the gaussian distribution and corrects the dat we propose to apply transformation that correct skewness and kurtosis of distribution. Skewness and kurtosis are two measures that are zero when a variable is gaussian. We retain three transformations to correct Skewness and kurtosis: the square, the square root and the Anscombe transformation (AT). To select data transformation, we refere in section 3.1 to a quality criterion that check the impacts of the transformation: the transformation that gets the best quality criterion result has the best trade-off between Gaussian distribution and underestimate of bird couples.

Overview of different methods of dimensional reduction

NLDR methods can be classified according to different characteristics: Scale analysis (local/global/multiscale). This reflects the kind of properties the transformation does preserve. Distance metrics/similarity. This shows the distance used to estimate if two data points are close. We retained 7 NLDR methods completed with to 2 linear methods: the Classical Multidimensional Scaling (CMDS) and the Non-metric Multidimensional Scaling (NMDS) [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF]. Non linear Mapping (NLM) (Sammon's mapping) [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF] tries to preserve the neigborhood topology of data by preserving distances between points according to the following stress function: andd p ij are the distances between points i th and j th , in R m and R p . Curvilinear Component Analysis (CCA) [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF] is an evolution of NLM. Instead of the optimization of a reconstruction error, CCA aims to preserve the distance matrix while projecting data onto R p dimension, giving priority to low distances. The use of similarities in NLDR is recent [START_REF] Lee | Multiscale stochastic neighbor embedding: Towards parameter-free dimensionality reduction[END_REF].These approaches are based on sparse matrices of similarities defined in R m , such as in Stochastic Neighbor Embedding (SNE) [START_REF] Bunte | Stochastic neighbor embedding (sne) for dimension reduction and visualization using arbitrary divergences[END_REF] where distances are converted into probabilities which represent similarities. SNE aims to preserve similarities in R m and R p . In this context t-distributed Stochastic Neighbor Embedding (t-SNE) [START_REF] Van Der Maaten | Visualizing data using t-sne[END_REF] and Neighbor Retrieval Visualizer (NeRV) [START_REF] Venna | Information retrieval perspective to nonlinear dimensionality reduction for data visualization[END_REF] are SNE evolutions. The first is based on Student t-distribution to calculate similarities while a Gaussian distribution is used in SNE. Both SNE and t-SNE try to reduce the Kullback-Leibler divergence (KLD) as a cost function. The second uses two dual KLD, that are more precise than a single KLD. Coming from this KLD approach, different refinement have been proposed. First by replacing KLD by Jensen-Shannon divergence in the Jensen-Shannon Embedding (JSE) [START_REF] John A Lee | Type 1 and 2 mixtures of kullback-leibler divergences as cost functions in dimensionality reduction based on similarity preservation[END_REF].

J N LM = 1 n i,j=1 d m i,j   n i,j=1 (d m i,j -d p i,j ) 2 d m i,j   With d m ij
Secondly, to overcome one of the major drawback fixed size of neigborhood, [START_REF] Lee | Multiscale stochastic neighbor embedding: Towards parameter-free dimensionality reduction[END_REF] proposed in Multiscale Jensen-Shannon Embedding (Ms JSE) to take into account different sizes of neigborhood, thanks to a log scale.

Objective comparison based on quality assessment

Several quantitative evaluation measures for NLDR have been proposed including techniques which rely on neighborhood ranking. We based our quality criterion on the intrusion/extrusion diagram proposed by Lee & Verleysen. Fore more details on quality assessment see on [START_REF] Aldo | Quality assessment of dimensionality reduction: rank-based criteria[END_REF]. This criterion is the Area Under Curve (AUC), a scale-independent criterion got by calculating the area under the curve of R N X function, which gives the percentage of improvement of neighborhood preservation compared to a random projection, depending on the size of the neighborhood.

Results and discussions

The choice of a transformation

The table 2 shows AUC results for each transformation in order to measure their impacts on data. Results show for every NLDR methods that the square root gets better results than the data without transformation or AT. Moreover, the best result is obtain with MS JSE with 57,2%. Finally, we select the square root which correspond to the best trade-off between correcting the underestimate of bird couples and the Gaussian distribution.

Without transformation

Square root

Transformation of Anscombe Table 1: AUC results for data transformation Figure 1: Quality curves of R N X function on the square root of the data 3.2 The choice of the more efficient NLDR method Figure 1 presents the quality curves coming from the differents methods. At lower scale, Ms JSE reaches 75% of improvement of neighborhood conservation compared to a random projection, and clearly outperforms other methods. At high scale, Ms JSE gets more than 70%, but is in the average compared to other methods. NMDS seems to be the best method for high neighborhoods (85% of iprovement for100 neighbors). NMDS R N X function reaches faster than the other curves high results for high neighborhoods. But all the methods present good results for high neighborhoods, while Ms JSE, t-SNE and JSE are the only ones to get good results at small neighborhoods. For instance, NMDS result is very low, about 10%.Ms JSE has better results than t-SNE and JSE at large neighborhoods, that's why Ms JSE has better AUC result than any other method, with 57,2%. Finally, Ms JSE seems to be the best trade-off for this ecological application.

Resulting projection of the data with NLDR methods

Census points are projected with methods (Figure 2). The projection comparison shows that NLDR based on similarity outperform over methods in clustering context. Focusing on Ms JSE (Figure 2). we can see that global/local organization of data is respected. At global scale we observe the upstream-downstream gradient relationship between census points. At local scale, Ms JSE is able to give an efficient clustering, grouping the data which have the same characteristics in terms of birds species assemblage. In the context of river zonation, each cluster represents a different birds species assemblage depending on environmental features and each distance between clusters represent an ecological discontinuity which is not detectable with linear approach. Moreover, Ms JSE has the characteristic of preserving outliers. In fact, the five last census points are distinct from the others: they are the five last census points, located in the downstream of the Loire River (next to the Atlantic Ocean). These census points are indeed very different from the others considering their bird population. This distinguish with the other census points isn't clear with local NLDR methods, such as NLM, CCA, SNE and t-SNE.

Conclusion

This paper explores and compares recent NLDR methods with data transformations in order to find the best method on a real-life ornithological application. Results highlight that Ms JSE with square root transformation is the most efficient method. The global organization of census points reveals the upstreamdownstream gradient and the local clustering highlights discontinuities. These results outperform traditional PCA in this context. In order to generalise results, more tests on another nonlinear natural dataset should be made to validate if Ms JSE confirms its ability to make efficient projections in ecological context.

  Efficient unsupervised clustering for spatial bird population analysis along the Loire river Aurore Payen 1 , Ludovic Journaux 1.2 , Clément Delion 1 , Lucile Sautot 1,3 , Bruno Faivre 3 * 1-AgroSup Dijon 26 Boulevard Docteur Petitjean, 21000 Dijon 2-Université de Bourgogne -LE2I Avenue Alain Savary 21000 Dijon -France 3-Université de Bourgogne -Biogéosciences 6 Boulevard Gabriel 21000 Dijon -France 1 Introduction

Figure 2 :

 2 Figure 2: Projection of the square root of the data, with all the methods (blue: upstream of Loire river, red brown: downstream)

Figure 3 :

 3 Figure 3: Census points gradient with Ms JSE and square root transformation

* Data acquisition received financial support from the FEDER Loire, Etablissement Public Loire, DREAL de Bassin Centre (Etude des oiseaux nicheurs de la Loire et de l'Allier sur l'ensemble de leurs cours) to BF, and from the Région Bourgogne (PARI, Projet Agrale 5) to BF. Data analysis received support from the French Ministry of Agriculture (Bourse FCPR to LS).