Nicolas Locatelli

R Lebrun

V V Naletov

A Hamadeh

G De Loubens

O Klein

J Grollier

V Cros

Improved spectral stability in spin transfer nano-oscillators: single vortex versus coupled vortices dynamics

Keywords: Spin transfer nano-oscillators, Spin transfer torque, Vortex, Gyrotropic mode, Coupled oscillators, Selfsustained magnetic oscillations, Radio frequency, Microwave

We perform a comparative study of spin transfer induced excitation of the gyrotropic motion of a vortex core with either uniform or vortex spin polarizers. The microwave output voltage associated with the vortex dynamics, detected in both cases, displays a strong reduction of phase fluctuations in the case of the vortex polarizer, with a decrease of the peak linewidth by one order of magnitude down to 200kHz at zero field. A thorough study of rf emission features for the different accessible vortex configurations shows that this improvement is related to the excitation of coupled vortex dynamics by spin transfer torques.

I. INTRODUCTION

The spin transfer torque (STT) phenomenon [START_REF] Berger | Emission of spin waves by a magnetic multilayer traversed by a current[END_REF], [START_REF] Slonczewski | Current-driven excitation of magnetic multilayers[END_REF], that has been an intense research topic in the last decade, has allowed a crucial breakthrough for low energy writing in STT-MRAM [START_REF] Khvalkovskiy | Basic principles of STT-MRAM cell operation in memory arrays[END_REF]. Besides being an efficient tool for magnetization reversal, spin torque can also allow the generation of selfsustained magnetization oscillations in the GHz range. Thanks to the magneto-resistance (MR) effect, such magnetization dynamics is converted into an emitted voltage at the same frequency. This led to the proposal of new spintronics microwave devices called spin-transfer nano-oscillators (STNOs) [START_REF] Kiselev | Microwave oscillations of a nanomagnet driven by a spin-polarized current[END_REF]. The recent implementation of spin transfer dynamics in magnetic tunnel junctions (MTJ) has allowed to increase the output power of such oscillators close to the requirement for applications [START_REF] Villard | A GHz Spintronic-Based RF oscillator[END_REF], [START_REF] Dussaux | Large microwave generation from current-driven magnetic vortex oscillators in magnetic tunnel junctions[END_REF]. Concurrently, the introduction of vortexbased spin transfer oscillators (STVOs) has allowed to significantly improve the spectral purity of the oscillation [START_REF] Dussaux | Large microwave generation from current-driven magnetic vortex oscillators in magnetic tunnel junctions[END_REF]- [START_REF] Grimaldi | Response to noise of a vortex based spin transfer nano-oscillator[END_REF]. However further advances regarding these two issues are still required to eventually allow the use of STNOs in future telecommunication devices. Several applications are already Present address of N. Locatelli is : Institut d' Électronique Fondamentale, Univ Paris-Sud, UMR CNRS 8622, Orsay, France. Corresponding authors: N. Locatelli (email: nicolas.locatelli@u-psud.fr) & V. Cros (email: vincent.cros@thalesgroup.com). considered today, among which their integration as nanosized reference oscillators for FM signal modulation [START_REF] Locatelli | Spin-torque building blocks[END_REF]- [START_REF] Muduli | Nonlinear frequency and amplitude modulation of a nanocontact-based spin-torque oscillator[END_REF], sensors for HDD read-heads [START_REF] Suto | Real-Time measurement of temporal response of a Spin-Torque oscillator to magnetic pulses[END_REF], [START_REF] Nagasawa | Delay detection of frequency modulation signal from a spin-torque oscillator under a nanosecond-pulsed magnetic field[END_REF], or the design of interacting oscillators network in neuro-inspired processor architectures [START_REF] Csaba | Spin torque oscillator models for applications in associative memories[END_REF], [START_REF] Levitan | Non-Boolean associative architectures based on nano-oscillators[END_REF].

A magnetic vortex is a magnetic state appearing in magnetic dots with a magnetization curling in the film plane and popping out-of-plane in a small region in its center called the "vortex core", which size is comparable to the exchange length [START_REF] Feldtkeller | Struktur und energie von blochlinien in dnnen ferromagnetischen schichten[END_REF]. A vortex is characterized by two parameters: its chirality C = ±1 giving the direction of the curling magnetization, and its core polarity P = ±1 giving the direction of the out-of plane core magnetization [START_REF] Guslienko | Magnetic vortex state stability, reversal and dynamics in restricted geometries[END_REF]. In this study, we are interested in the microwave signal generated by the spin-transfer induced excitation of the vortex gyrotropic mode. This latter mode, the lowest in energy, corresponds to a gyration of the vortex core around its equilibrium position. Despite its small size, the vortex core has a crucial impact as it defines the frequency and direction of the gyrotropic oscillations. Because of the particular topology of the vortex ground state, one expects that the excitation of the gyrotropic mode by a dc current in a nanopillar depends also on the magnetic configuration adopted by the polarizing layer. Several cases have been theoretically proposed to achieve self-sustained gyrotropic oscillations of the vortex core. The spin-current -and thus the polarizing layer -might be uniformly polarized, in the layer's plane [START_REF] Sluka | Spin-transfer torque induced vortex dynamics in Fe/Ag/Fe nanopillars[END_REF] or perpendicularly [START_REF] Ivanov | Excitation of spin dynamics by Spin-Polarized current in vortex state magnetic disks[END_REF]- [START_REF] Gaididei | Magnetic vortex dynamics induced by an electrical current[END_REF], or circularly-polarized, possibly with a vortex-like distribution [START_REF] Khvalkovskiy | Nonuniformity of a planar polarizer for spin-transferinduced vortex oscillations at zero field[END_REF], [START_REF] Sluka | Quenched slonczewski windmill in spin-torque vortex oscillators[END_REF].

Our main objective is to compare, for given device dimensions, the output rf signal characteristics of vortex oscillations for two different magnetic configurations of the polarizing magnetic layer, either (i) in plane magnetized or (ii) vortex structure, that provides the spin polarization being the source of spin torque acting on the gyrating vortex. After discussing the accessible magnetic configurations, we show that the spectral quality of the output signal strongly depends on the actual magnetization distribution of the polarizer. Notably, we demonstrate that the spectral quality is improved by one order of magnitude when a second vortex is nucleated in the arXiv:1501.07839v1 [cond-mat.mes-hall] 30 Jan 2015 Resistance evolution versus dc-current for a positive current I dc > 0, measured at zero external magnetic. Schematics represent the magnetic configuration in thin Py(4nm) and thick Py(15nm) layers, big arrows correspond to vortices polarities. The two curves represent two possible path measured in repeated experiments. The red continuous line is associated with the observation of two-vortices state with opposite polarities, whereas the black dashed curve is associated with the observation of two-vortices state with identical polarities. For clarity, the increase of resistance associated with Joule heating was substracted. Insert : Sample geometry and positive current definition.

polarizing layer rather than uniform magnetization. Then, we explore the possibilities offered by vortex polarity switching. The critical influence of the relative polarities of the free and polarizer vortices is raised. This study demonstrates the importance of considering coupled mode in order to reduce noiseinduced phase-fluctuations in STT-induced dynamics [START_REF] Lebrun | Nonlinear behavior and mode coupling in spin-transfer nano-oscillators[END_REF].

II. DETERMINATION OF THE MAGNETIC CONFIGURATION BY TRANSPORT STUDY

The spin valve based STNO under study is composed of a Cu(60nm)/Py(15nm)/Cu(10nm)/Py(4nm)/Au(25nm) (Py=Ni 80 Fe 20 ) stack patterned in a 150nm circular nanopillar by standard e-beam and ion etching lithography process (see inset in Fig. 1). The pillar dimensions and the thickness of the magnetic layers are chosen so that, in each layer, it will be possible to change the magnetic configuration between two stable states, namely in-plane uniform and vortex. The stability of the vortex configuration can be increased through the amplitude of the Oersted-field while the current flowing through the pillar is increased [START_REF] Urazhdin | Effects of current on the magnetic states of permalloy nanodiscs[END_REF]. We recall that the thicker the layer, the more stable the vortex state. In our convention, a positive current is flowing through the pillar, corresponding to electrons flowing from the thick Py(15nm) to the thin Py(4nm).

We first study the modification of the magnetic state in each layer by monitoring the nano-pillar resistance as the current is swept from 0 to 15mA and back to 2mA. The averaged resistance versus dc current I dc measured at zero external magnetic is shown in figure 1. At zero field and low I dc , the stable state corresponds to anti-parallel uniform magnetizations, due to the dipolar interaction between the two magnetic layers in the nanopillar. As usual in GMR devices, such AP state is the higher resistance state. As the current is increased, a first resistance drop is observed at I dc = 2mA, approximately equal to half the full magnetoresistance (∆R), associated with a vortex nucleation in the thicker layer while the magnetization in the Py(4nm) layer remains quasi-uniform. This intermediate resistance state is then conserved up to about I dc = 6mA, when a second drop of resistance corresponding to the nucleation of a second vortex in the thin layer is observed. As they are both formed under the influence of the Oersted field, the chiralities of both vortices are identical and have an orthoradial symmetry similarly to the Oersted field : C 15nm = C 4nm . This is consistent with the lower resistance value observed associated with parallel magnetizations. Note that as the current is then swept back, both vortices remain stable even below their nucleation current.

Repeating such R(I) measurement, we found as shown in Fig 1, that the resistance level associated with the 2-Vortices (2V) state can indeed take two different values. Because these measurements are performed at zero field, the core polarity during the nucleation process is random (or influenced only by local defects). Thus the core polarity of the vortex in each layer can be oriented either "up" or "down". In the regime with a single vortex (1V), we see in Fig 1 that the resistance level is independent of the core orientation. However, we have to account for the possible configurations of the relative core polarities in order to understand that two resistance levels are observed in the range of current corresponding to the 2V state. Indeed, two distinct configurations can be obtained, corresponding to identical (up-up or down-down) or opposite (up-down or down-up) polarities.

To discriminate between these two configurations, we use the following procedure: we apply a large perpendicular field that favors identical polarities while injecting a large dc current of 10 mA that favors identical chiralities, then bring back the field to zero. In that case, we always observe the lower resistance state (black dashed curve in Fig. 1). Therefore, the lower resistance two-vortices state is associated with identical polarities, whereas the higher resistance state is associated with opposite polarities (red continuous curve). Our recent study of the evolution of the switching of core polarity with current, corroborating these results, is presented elsewhere [START_REF] Locatelli | Dynamics of two coupled vortices in a spin valve nanopillar excited by spin transfer torque[END_REF], [START_REF] Locatelli | Reversal process of a magnetic vortex core under the combined action of a perpendicular field and spin transfer torque[END_REF].

Note finally on Fig. 1 that when we sweep back the current towards zero we find that the resistance corresponding to opposite polarities drops at I dc = 4mA and reaches the same level as the one for two vortices having identical polarities. We will see in next section that the resistance difference between these two 2V states is linked to differences in their dynamics.

III. CHARACTERISTICS OF RF EMISSION FOR THE DIFFERENT MAGNETIC CONFIGURATION

A. In-plane polarizer versus vortex polarizer

While sweeping I dc , we also record the power spectrum of the nano-pillar voltage to compare the microwave spectra in the different configurations. For a positive current, it is expected to observe a STT-induced gyrotropic motion of the vortex in the Py(15nm) layer, with the Py(4nm) acting as the polarizing layer [START_REF] Khvalkovskiy | Nonuniformity of a planar polarizer for spin-transferinduced vortex oscillations at zero field[END_REF]. Here, an external in-plane field B = 34mT is applied to offset the 1V to 2V transition to higher current, ensuring to observe auto-oscillations under uniform polarizer well above the corresponding critical current. This field has shown no significant effect on the observed gyrotropic dynamics, as similar results could be obtained for smaller in-plane field values. We present the spectra measured while the injected current is increased, and focus and the transition from 1V to 2V with opposite polarities which occurs at 12 mA for the applied field value. We clearly observe two distinct regions on this map, which correspond to the 1V and 2V states. A striking modification of the microwave emission characteristics is then observed when the polarizing layer (thin layer) goes from inplane magnetization to vortex magnetization.

In figure 3(a), we present the evolution of the signal frequency as a function of I dc . The frequency is consistent with self-sustained gyrotropic oscillations of the vortex core in the thick Py(15nm) layer, with a frequency close to the evaluated gyrotropic eigen frequency (µ 0 M S = 0.96T and aspect ratio β = L/R = 0.2 gives f = 5 18π γµ 0 M S β = 952MHz [START_REF] Naletov | Identification and selection rules of the spin-wave eigenmodes in a normally magnetized nanopillar[END_REF], [START_REF] Guslienko | Eigenfrequencies of vortex state excitations in magnetic submicron-size disks[END_REF]), augmented by Oersted-field confinement and spin-transfer action. Figure 3(b) shows the corresponding evolution of the peak linewidth.

For I dc < 11.5mA, corresponding to the quasi-uniform polarizer condition, the frequency has a complex dependence versus I dc . Moreover, we measure a correlation between between the df /dI dc (see Fig. 3(c)) and the linewidth depen-dences [START_REF] Grimaldi | Response to noise of a vortex based spin transfer nano-oscillator[END_REF], [START_REF] Kim | Generation linewidth of an Auto-Oscillator with a nonlinear frequency shift: Spin-Torque Nano-Oscillator[END_REF]- [START_REF] Muduli | Decoherence and mode hopping in a magnetic tunnel junction based spin torque oscillator[END_REF]. These observations are consistent with a significant contribution of the non-linear frequency shift to the increase of the linewidth in this configuration. Note that in this regime, the linewidth never goes below 1 MHz, similarly to the other results published in the literature for spin transfer vortex excitations [START_REF] Dussaux | Large microwave generation from current-driven magnetic vortex oscillators in magnetic tunnel junctions[END_REF], [START_REF] Pribiag | Magnetic vortex oscillator driven by d.c. spin-polarized current[END_REF], [START_REF] Sluka | Spin-transfer torque induced vortex dynamics in Fe/Ag/Fe nanopillars[END_REF], [START_REF] Mistral | Current-Driven vortex oscillations in metallic nanocontacts[END_REF].

Upon the nucleation of the second vortex occurring around I dc = 11.5mA, we observe a sudden 50MHz jump of the frequency and the frequency dependence versus I dc becomes highly linear. Concurrently, we observe a drastic decrease of the spectral linewidth, which now reaches values down to 200kHz. The measured df /dI dc = 13.3MHz/mA linear increase of the frequency would then be dominated by the Oersted-field contribution to the vortex confinement [START_REF] Khvalkovskiy | Vortex oscillations induced by spin-polarized current in a magnetic nanopillar: Analytical versus micromagnetic calculations[END_REF], and a strong decrease of the non-linear frequency shift under the new spin-transfer action could be consistent with the strong increase of spectral purity.

It should be noticed that the linear dependence of the frequency with current in the 2V configuration is also a major asset for frequency modulation applications [START_REF] Iacocca | Analytical investigation of modulated spintorque oscillators in the framework of coupled differential equations with variable coefficients[END_REF]- [START_REF] Muduli | Nonlinear frequency and amplitude modulation of a nanocontact-based spin-torque oscillator[END_REF]. These features are not modified by the in-plane external field application, and were also observed in the absence of any external field. Finally we emphasize that these measurements yield the lowest linewidth, 200kHz, measured at zero field and room temperature so far for any type of STNOs.

B. Two-vortices (2V): parallel vs opposite core polarities

As already mentioned, two different states (resistance levels) depending on the relative core polarities -identical or opposite polarities -of the two vortex configuration can be found at zero field. Interestingly, these two configurations yield very different microwave output signals. As demonstrated in figure 4, contrary to the case of opposite polarities we do not detect any rf signal for the parallel core configuration.

This observation is consistent with the difference in average resistance measured between the two configurations shown in Fig. 1. Indeed, the low average resistance of the parallel core configuration is consistent with the absence of dynamics since in that case the two vortices are perfectly centered and superimposed. On the contrary, the appearance of large amplitude vortex dynamics in the opposite core configuration increases the average resistance as the gyrotropic trajectory offsets the core from the center. Below the critical current I dc = 4mA, the oscillations in the opposite polarities configuration stop and the average resistance goes back to the lowest level. Between I c = 4mA and 15mA, the resistance difference between the two configurations is constant, suggesting that the STT-induced amplitude of the gyrotropic oscillations does not change when the current amplitude increases.

The latter experimental results demonstrate the importance of the relative polarities of the polarizer vortex and free vortex for spin torque induced dynamics. Several arguments can be proposed to explain these observations.

The main contribution to the STT action comes from the circular in-plane polarization [START_REF] Khvalkovskiy | Nonuniformity of a planar polarizer for spin-transferinduced vortex oscillations at zero field[END_REF]. However, when the moving core is oscillating with low amplitude in a region close to the core of the vortex polarizer, the perpendicular contribution of the latter to the STT will be increasing or decreasing the total efficiency of the torque depending on its polarity [START_REF] Sluka | Quenched slonczewski windmill in spin-torque vortex oscillators[END_REF]. Second, the core-core dipolar interaction can also have a significant contribution when the two cores are close, changing sign depending on the respective core polarities. As illustrated in Fig. 4, adopting a configuration where the two cores are opposite produce a dipolar repulsion of the 2 cores, hereby breaking the axial symmetry of the system. These two contributions have a significant influence on the determination of the critical current density necessary to start the gyrotropic oscillations, potentially explaining the strong differences between the two configurations. It should finally be noticed that the strong magnetization gradient associated with the vortex distribution in the core also strongly impacts the spin transport [START_REF] Urazhdin | Effects of current on the magnetic states of permalloy nanodiscs[END_REF] through the spin-valve, questioning the assumption of uniform spin polarization amplitude made in any theoretical study so far.

C. Two-vortices (2V): Excitation of a coupled vortex mode

Recent studies demonstrated that linewidth reduction can be obtained by STT-excitation of a coupled mode of the two magnetic layers [START_REF] Hamadeh | Origin of spectral purity and tuning sensitivity in a spin transfer vortex nano-oscillator[END_REF], [START_REF] Gusakova | Linewidth reduction in a spin-torque nano-oscillator caused by nonconservative current-induced coupling between magnetic layers[END_REF]- [START_REF] Lee | Current driven magnetic damping in Dipolar-Coupled spin system[END_REF], the polarizing layer being also involved in the STT-induced dynamics. Several features that we observed, such as the importance of relative core polarities, the frequency jump and the drastic linewidth reduction at the transition from 1 to 2 vortex configuration, suggests that the dynamics observed with two vortices of opposite core polarities corresponds to a spin transfer driven oscillations of a coupled gyrotropic motion of the two vortices [START_REF] Sluka | Quenched slonczewski windmill in spin-torque vortex oscillators[END_REF], [START_REF] Lebrun | Nonlinear behavior and mode coupling in spin-transfer nano-oscillators[END_REF].

Considering the existing dipolar coupling between the two vortices, their gyrotropic modes hybridize to produce two coupled eigen modes [START_REF] Guslienko | Dynamics of coupled vortices in layered magnetic nanodots[END_REF]. Given the symmetry of the spin transfer action, one of these modes is self-sustained (here the mode dominated by the thick layer's vortex) while the second one (dominated by the thin layer's vortex) is over-damped [START_REF] Sluka | Quenched slonczewski windmill in spin-torque vortex oscillators[END_REF]. Under appropriate conditions energy transfer between the two modes can occur and help absorbing magnetic fluctuations around the self-sustained trajectory, artificially increasing the effective damping rate for amplitude fluctuations [START_REF] Lebrun | Nonlinear behavior and mode coupling in spin-transfer nano-oscillators[END_REF]. Thus, we note that whatever is the system geometry (diameter, thicknesses), relative vortices polarities then reveals to be a crucial parameter defining the symmetry of the excited mode.

Let us finally note that in the presented spin valve case the improved spectral quality of this coupled vortex mode is accessible only for opposite core polarities, thus at the cost of an efficient control of the magnetic configuration. However, we recently demonstrated that an easy and efficient control on the polarities can be done through the combined application of current and field in two vortices systems [START_REF] Locatelli | Reversal process of a magnetic vortex core under the combined action of a perpendicular field and spin transfer torque[END_REF]. The stated issue could then be turned into benefit by taking advantage of the possibility to switch on and off the oscillations, and the ac-voltage thereof, by switching one of the two polarities. This could be used as a calculation media in oscillator based transistor operations, or in oscillators based processors architectures, such as the recently proposed associative memories [START_REF] Csaba | Spin torque oscillator models for applications in associative memories[END_REF], [START_REF] Levitan | Non-Boolean associative architectures based on nano-oscillators[END_REF].

IV. CONCLUSION

In conclusion, we demonstrate the advantage of having the opportunity to tune a magnetic transition between single and double-vortex states in a spin-valve STNO to observe the evolution of the spectral quality obtained for both configurations. We show a one order of magnitude reduction of the peak linewidth. The evolution of frequency and linewidth with current are compatible with reduced non-linear frequency shift for the coupled vortex mode, concurrent with an increase of the effective damping rate for amplitude fluctuations. This results in a strongly improved stability, with an effective quality factor raising up to f /∆f = 6000 without the need for external magnetic field. Interestingly, the rf characteristics associated with the 2V case present a frequency tunability that is almost linear and mainly associated with the change of the vortex confinement due to the Oersted field, with high potentiality for frequency control and modulation. Both features strengthen the potential applicability of vortex-based spin transfer oscillators in the near future.

Fig. 1 .

 1 Fig. 1.Resistance evolution versus dc-current for a positive current I dc > 0, measured at zero external magnetic. Schematics represent the magnetic configuration in thin Py(4nm) and thick Py(15nm) layers, big arrows correspond to vortices polarities. The two curves represent two possible path measured in repeated experiments. The red continuous line is associated with the observation of two-vortices state with opposite polarities, whereas the black dashed curve is associated with the observation of two-vortices state with identical polarities. For clarity, the increase of resistance associated with Joule heating was substracted. Insert : Sample geometry and positive current definition.

Fig. 2 .

 2 Fig. 2. Power spectrum map measured for our spin valve STNO for increasing I dc in the case of a transition from a single vortex configuration to a two-vortices configuration with opposite polarities. The measurement is made under in-plane external field B = 34mT . For this field value, the transition between the two configurations happens at I dc = 11.5mA. Peaks observed at harmonics of the fundamental frequency are not presented on this graph.

Fig. 3 .

 3 Fig. 3. (a) Fundamental peak frequency, (b) linewidth and (c) tunability df /dI dc as a function of the injected dc current measured under B = 34 mT and at room temperature.

Fig. 4 .

 4 Fig. 4. Spin-valve voltage spectrum measured in the two-vortices configuration in the case of (a) identical and (b) opposite polarities, both measured at I dc = 15mA and zero magnetic field.

ACKNOWLEDGMENTS

The authors acknowleges C. Deranlot, C. Ulysse and G. Faini for film growth and sample fabrication. This research was partly funded by the French ANR (grant SPINNOVA ANR-11-NANO-0016) and the EU (FP7 grant MOSAIC ICT-FP7-317950). The work of V.V. Naletov is performed according to the Russian Government Program of Competitive Growth of Kazan Federal University.


Emma Barme

Julien Bensmail

Jakub Przybyło

Mariusz Woźniak

On a directed variation of the 1-2-3 and 1-2 Conjectures $

In this paper, we consider the following question, which stands as a directed analogue of the well-known 1-2-3 Conjecture: Given any digraph D with no arc -→ uv verifying d + (u) = d -(v) = 1, is it possible to weight the arcs of D with weights among {1, 2, 3} so that, for every arc -→ uv of D, the sum of incident weights out-going from u is different from the sum of incident weights in-coming to v? We answer positively to this question, and investigate digraphs for which even the weights among {1, 2} are sufficient. In relation with the socalled 1-2 Conjecture, we also consider a total version of the problem, which we prove to be false. Our investigations turn to have interesting relations with open questions related to the 1-2-3 Conjecture.

Introduction

We here focus on vertex-distinguishing weightings, a graph theory notion that attracted more and more attention in the last decade. Basically, given an undirected graph G, the goal is to weight some elements of G so that some well-identified vertices of G get distinguished relatively to some aggregate computed from the weighting. As emphasized in the previous sentence, the such problems of correctly weighting a graph are hence made of three main parameters. For any of these variants, the main goal is, given a graph, to deduce the smallest number of consecutive weights 1, ..., k necessary to obtain a correct distinguishing weighting.

In this paper, we focus on those such problems where edges (among maybe other elements) have to be weighted, and the distinguishing aggregate is the sum of weights incident to the vertices. More formally, given an edge-weighting w of some graph G, for every vertex v one may compute1 σ w (v) := u∈N (v) w(vu), that is, the sum of the weights incident to v. In case w is a total-weighting, every vertex v also has its own weight, which must be involved when computing σ w (v), that is

σ w (v) := w(v) + u∈N (v) w(vu)
in such a situation. In the setting where σ w is the distinguishing parameter, three main notions have been studied in literature:

(1) If edge-weightings are considered and all vertices of G must be distinguished by σ, the least number of necessary consecutive edge weights is denoted s(G) (and is called the irregularity strength of G in literature).

(2) If edge-weightings are considered and only the adjacent vertices of G must be distinguished, the least number of necessary consecutive weights is denoted χ e Σ (G).

(3) If total-weightings are considered and only the adjacent vertices of G must be distinguished, the least number of necessary consecutive weights is denoted χ t Σ (G).

As we only focus on Items (2) and (3) (that is, on sum-colouring edge-weighting and sum-colouring total-weighting) in this paper, we will below recall some of their associated backgrounds. For more general details on this wide area (and on the upcoming introductory details), we refer the interested reader to the recent survey by Seamone on this topic [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF].

The parameter χ e Σ is related to the well-known 1-2-3 Conjecture raised by Karoński, Łuczak and Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF], which reads as follows (where a nice graph refers to a graph with no component isomorphic to K 2 ).

1-2-3 Conjecture (Karoński, Łuczak, Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF]). For every nice graph G, we have χ e Σ (G) ≤ 3.

Several constant upper bounds on χ e Σ were given towards the 1-2-3 Conjecture, the best one of which being due to Kalkowski, Karoński and Pfender, who proved that χ e Σ (G) ≤ 5 whenever G is nice [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3 Conjecture[END_REF]. Concerning the parameter χ t Σ , the following so-called 1-2 Conjecture was raised by Przybyło and Woźniak [START_REF] Przybyło | On a 1,2 Conjecture[END_REF].

1-2 Conjecture (Przybyło, Woźniak [START_REF] Przybyło | On a 1,2 Conjecture[END_REF]). For every graph G, we have

χ t Σ (G) ≤ 2.
Towards the 1-2 Conjecture, the best known result so far is due to Kalkowski [START_REF] Kalkowski | A note on the 1,2-Conjecture[END_REF], who proved that every graph G verifies χ t Σ (G) ≤ 3.

There have been a few attempts for bringing the 1-2-3 and 1-2 Conjectures to directed graphs, see e.g. [START_REF] Baudon | On the 1-2 Conjecture in digraphs[END_REF][START_REF] Baudon | An oriented version of the 1-2-3 Conjecture[END_REF][START_REF] Borowiecki | Coloring chip configurations on graphs and digraphs[END_REF][START_REF] Khatirinejad | Digraphs are 2-weight choosable[END_REF]. Most of all these different directed versions of the 1-2-3 and 1-2 Conjectures were shown to hold, even under strong additional constraints such as list requirements. This results from the fact that these versions, though seemingly close to the 1-2-3 and 1-2 Conjectures in essence, were based on several behaviours that are not so comparable to the ones we have to deal with when considering the original conjectures. Notably, the definitions of some of these versions make the use of induction arguments possible, while such are generally not applicable in the undirected context. This makes us wonder what should be the directed analogues to the 1-2-3 and 1-2 Conjectures that would mimic their behaviours and inherent hardness the best, while fitting to the particularities of the directed context.

In that spirit, we introduce and study new directed analogues of the 1-2-3 and 1-2 Conjectures. Our directed analogue of the 1-2-3 Conjecture is introduced in Section 2, while our analogue of the 1-2 Conjecture is studied in Section 3. We more precisely show our directed analogue of the 1-2-3 Conjecture to be equivalent to solved cases of the 1-2-3 Conjecture, hence giving a positive answer to a question addressed by Łuczak [12]. Using that equivalence, we point out that our directed analogue of the 1-2 Conjecture, though true in specific contexts, is false in general. Unexpected implications of our investigations on the 1-2-3 Conjecture are discussed in Section 4.

A directed 1-2-3 Conjecture

Let D be a simple digraph, and w be an arc-weighting of D. For every vertex v, one can compute two sums incident to v, namely

σ - w (v) := u∈N -(v) w( -→ uv),
i.e. the incident in-coming sum, and

σ + w (v) := u∈N + (v) w( -→ vu),
i.e. the incident out-going sum. We call w sum-colouring if, for every arc -→ uv of D, we have

σ + w (u) = σ - w (v).
The least number of weights in a sum-colouring k-arc-weighting (if any) of D is denoted χ e Ł (D).

Before starting investigating the parameter χ e Ł , let us, reusing the notions and terminology above, describe the previously introduced directed versions of the 1-2-3 Conjecture mentioned in Section 1. In [START_REF] Borowiecki | Coloring chip configurations on graphs and digraphs[END_REF][START_REF] Khatirinejad | Digraphs are 2-weight choosable[END_REF] was introduced the variant where, for every arc -→ uv, we require the relative sums of u and v, i.e. σ -(u) -σ + (u) and σ -(v) -σ + (v), to be different. In [START_REF] Baudon | On the 1-2 Conjecture in digraphs[END_REF][START_REF] Baudon | An oriented version of the 1-2-3 Conjecture[END_REF] was studied the variant where every two adjacent vertices must have different outsums (or, equivalently, in-sums), that is we require σ

+ (u) = σ + (v) (resp. σ -(u) = σ -(v))
for every arc -→ uv. The notion of sum-colouring arc-weighting above is hence different in the sense that, among the three directed variants, it is the only one where the distinction between two vertices connected by an arc depends on the direction of that arc.

As a very first observation, it is worth mentioning that not all digraphs admit a sumcolouring arc-weighting. To be convinced of this statement, just consider a digraph D having an arc -→ uv such that d

+ (u) = d -(v) = 1.
Then, no matter what weight x is assigned to -→ uv, clearly we will get σ + (u) = σ -(v) = x; so there is no hope to find a sum-colouring arc-weighting. However, one can easily convince themselves that if D is nice, in the sense Having a weight (here, 1) on some arc (here, the topmost arc) forces two incident arcs to be weighted differently.

that it does not admit this configuration, then D admits a sum-colouring arc-weighting (just consider sufficiently fast increasing weights).

Experimentations on some nice digraphs suggest that the following conjecture, which stands as a directed analogue of the 1-2-3 Conjecture, should be true. It is worth mentioning that the value 3 in our conjecture would be best possible as there exist nice digraphs admitting no sum-colouring 2-arc-weighting. One easy family of digraphs whose χ e Ł is 3 is squares of odd cycles in which the two underlying cycles are directed to form two directed cycles (see Figure 1). Assume indeed we use weights 1 and 2 only on such a digraph. Such a digraph is 2-regular and weighting, say, 1 an arc, say, --→ v 1 v 2 forces the weights on the second arc out-going from v 1 and the second arc in-coming to v 2 to be different (so that σ + (v 1 ) = σ -(v 2 )). Repeating this argument until all arcs are weighted following successive deductions, eventually we easily reach a contradiction. So such a digraph can only be weighted with at least three weights. In upcoming Section 2.2, we will point out that actually many other such digraphs exist. This section is organized as follows. We start by giving a direct proof of the Directed 1-2-3 Conjecture in Section 2.1. Our proof relies on an equivalence between the Directed 1-2-3 Conjecture and the 1-2-3 Conjecture for particular undirected graphs. Then we investigate, in Section 2.2, digraphs D verifying χ e Ł (D) ≤ 2. In particular, we show that some families of digraphs have this property, and point out that some other do not (hence providing more examples of nice digraphs needing all weights among {1, 2, 3}).

A proof of the Directed 1-2-3 Conjecture

Let G be a bipartite graph with bipartition A ∪ B. In the following, we say that G is anti-matchable if G is balanced, i.e. |A| = |B|, and the complement of G admits a perfect matching joining A and B. Said differently, G is anti-matchable if it is balanced and has a set of disjoint non-edges between A and B covering all its vertices. Assuming the vertices in A and B are explicitly ordered, i.e. from first to last, we call G anti-matched if, for every i ∈ {1, ..., |A|}, the ith vertex of A is not adjacent to the ith vertex of B. Note that a perfect matching in the complement of G can be directly deduced when G is anti-matched.

We below prove the Directed 1-2-3 Conjecture by essentially proving an equivalence between this conjecture and the 1-2-3 Conjecture for nice bipartite graphs.

Theorem 1. The following two problems are equivalent:

(1) The Directed 1-2-3 Conjecture for nice digraphs.

(2) The 1-2-3 Conjecture for nice bipartite graphs.

Proof. (2) ⇒ (1) Let D be a nice digraph. We describe below how to deduce a sumcolouring 3-arc-weighting w of D. Let v 1 , v 2 , ..., v n denote the vertices of D following an arbitrary ordering. Now consider the bipartite graph G(D) with bipartition V + ∪ V - constructed from D as follows:

• For every vertex v i of D, add a vertex v + i to V + , as well as a vertex v - i to V -. • For every arc --→ v i v j of D, add the edge v + i v - j to G(D).
Clearly G(D) is nice since otherwise D would not be nice. Furthermore, G(D) is anti-matched. Assume now we give some edge-weighting w of G(D), and let w be the arc-weighting of D where, for every arc --→

v i v j of D, we put w ( --→ v i v j ) = w(v + i v - j )
. Note that w is well-defined since every arc of D is associated with exactly one edge in G(D). Furthermore, by the way G(D) was constructed and w was obtained, for every vertex

v i we have σ + w (v i ) = σ w (v + i ) and σ - w (v i ) = σ w (v - i ). So if w is sum-colouring in G(D), then in particular w is sum-colouring in D.
The result then follows immediately since every nice bipartite graph admits a sum-colouring 3-edge-weighting according to our initial hypothesis.

(1) ⇒ (2) Let G be a nice bipartite graph with bipartition A ∪ B. In case G is not balanced or anti-matchable, just add some isolated vertices to A and B until G fulfils these two properties. Note that this operation preserves niceness of G. Assuming |A| = |B| = n, relabel the vertices of A and B so that

A = {v + 1 , v + 2 , ..., v + n } and B = {v - 1 , v - 2 , ..., v - n }
, and every two vertices of the form v + i and v - i are not adjacent, which is possible since G was made anti-matchable. So G is now anti-matched. Now just perform the construction converse to the one described in the proof of ( 2) ⇒ (1) to get a digraph D(G). More precisely, for every pair

{v + i , v - i } of vertices of G, add a vertex v i to D(G). Now, for every edge v + i v - j of G, add the arc --→ v i v j to D(G)
. Clearly this operation is valid since i = j by the labelling of the vertices of G. Besides, D(G) is nice since otherwise G would not be nice. It should be now clear that, similarly as in the previous case, from a sum-colouring 3-arc-weighting of D(G), which exists by the initial hypothesis, we can just copy the arc weights onto the edges of G to get a sum-colouring 3-edge-weighting of G. This concludes the proof.

The Directed 1-2-3 Conjecture now follows directly from Theorem 1 since the 1-2-3 Conjecture holds for all nice bipartite graphs (as proved by Karoński, Łuczak and Thomason in [START_REF] Karoński | Edge weights and vertex colours[END_REF]).

Theorem 2 (Karoński, Łuczak, Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF]). For every nice bipartite graph G, we have χ e Σ (G) ≤ 3.

Corollary 3. The Directed 1-2-3 Conjecture is true.

Theorem 1 in particular gives another explanation why the directed squares of odd cycles mentioned in Section 2 have their value of χ e Ł being 3. Note indeed that for every such digraph D, the graph G(D) we obtain is a cycle of the form C 4k+2 , which is known to be non sum-colouring 2-edge-weightable.

Using weights 1 and 2 only

We have seen in the previous section that every nice digraph can be arc-weighted in a sum-colouring way with weights among {1, 2, 3}. In this section, we study situations in which all weights among {1, 2, 3} are necessary, and situations where only the weights among {1, 2} are needed.

Bipartite digraphs

Our upcoming arguments and remarks rely on the following alternative proof of the Directed 1-2-3 Conjecture for nice bipartite digraphs. Let w be an arc-weighting of D obtained as follows. Consider D ↑↑ first. Since und(D ↑↑ ) is nice and bipartite, it admits a sum-colouring 3-edge-weighting w (according to Theorem 2) which we directly transfer to D ↑↑ (i.e. if uv and -→ uv are corresponding edge and arc of und(D ↑↑ ) and D ↑↑ , we give them the same weight, that is w (uv)). Note that if -→ uv is an arc of D ↑↑ then, because σ w (u) = σ w (v), and u has in-degree 0 and v has out-degree 0 in D ↑↑ , clearly we have

σ + w (u) = σ - w (v) in D ↑↑ . So w is sum-colouring in D ↑↑ .
Analogously, D ↓↓ admits such an arc-weighting w as well, according to the same arguments.

To obtain w, it now suffices to directly copy the weights by w and w of D ↑↑ and D ↓↓ , respectively, to D (that is, if -→ uv belongs to D ↑↑ , just set w( -→ uv) = w ( -→ uv), or w( -→ uv) = w ( -→ uv) otherwise). Then w retains the property of being sum-colouring, since, for every vertex v in A (resp. B), the in-degree of v in D is exactly its in-degree in D ↓↓ (resp. D ↑↑ ), while the out-degree of v in D is exactly its out-degree in D ↑↑ (resp. D ↓↓ ). So if w were not sum-colouring, then one of w and w would not be sum-colouring.

Following the proof of Theorem 4, we get that, for any nice bipartite digraph D, we have χ e Ł (D) = max {χ e Σ (und(D ↓↓ )), χ e Σ (und(D ↑↑ ))} , where D ↑↑ and D ↓↓ have the same meaning as in the proof above. This in particular means that if one of D ↑↑ and D ↓↓ has its value of χ e Σ being equal to 3, then χ e Ł (D) = 3. Since many bipartite graphs have their value of χ e Σ being exactly 3 (refer to [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] for a summary of all known such families), we get that a wide bunch of nice bipartite digraphs have their χ e Ł being exactly 3. On the other hand, we get that if a nice bipartite digraph with bipartition A ∪ B is the combination of two nice bipartite graphs G 1 and G 2 such that:

• χ e Σ (G 1 ) ≤ 2 and χ e Σ (G 2 ) ≤ 2,
• all edges of G 1 are directed from, say, A to B, in D, and

• all edges of G 2 are directed from B to A in D,
then χ e Ł (D) ≤ 2. We also note that the proof of Theorem 4 gives something more general. Namely, if a nice digraph D has a partition V 1 , ..., V k of its vertex set such that:

1. every V i is a stable set, 2. all vertices in a given V i have all of their in-neighbours in a same V j , and 3. all vertices in a given V i have all of their out-neighbours in a same V j , then a sum-colouring arc-weighting of D can be obtained by independently edge-weighting all of its underlying nice bipartite graphs of the form und(D[V i ∪ V j ]) for every i = j (some of which may have no edge). In the next result, we call such a partition of V (D) a circular vertex-colouring of D.

Corollary 5. For every nice digraph D with a circular vertex-colouring V 1 , ..., V k , we have

χ e Ł (D) = max {χ e Σ (und(D[V i ∪ V j ]
)) : i, j ∈ {1, 2, ..., k}} . From Corollary 5, we can deduce many digraphs that need all weights among {1, 2, 3} to be weighted, and, conversely, many digraphs for which the weights among {1, 2} suffice.

Acyclic tournaments

We here consider acyclic digraphs, i.e. digraphs with no directed cycles. Using three weights on nice acyclic digraphs is actually best possible. To illustrate this, just take any nice bipartite graph G with χ e Σ (G) = 3 and direct all arcs towards the same part. In doing so, as explained in previous Section 2.2, we obtain an acyclic oriented bipartite graph

- → G with χ e Ł ( - → G ) = 3.
We can however show that, in particular situations, such as for acyclic tournaments, acyclic digraphs may have their χ e Ł being at most 2. Theorem 6. For every nice acyclic tournament

- → T , we have χ e Ł ( - → T ) ≤ 2.
Proof. Since -→ T is acyclic, it admits a vertex ordering v 1 , v 2 , ..., v n such that for all i and j with i < j, the arc between v i and v j is directed "to the right", that is towards j. Ideally, we would like to produce a 2-arc-weighting w of -→ T with the following properties:

(1) For all i ∈ {1, 2, ..., n -1}, we have σ + w (v i ) odd. (2) For all i ∈ {2, 3, ..., n}, we have σ - w (v i ) even.

Assuming w satisfies Properties (1) and ( 2) above, clearly it is sum-colouring. Unfortunately, such a w cannot always be obtained but, in that case, we can nevertheless make sure that w is sum-colouring according to other arguments.

The main idea to obtain such a w consists in picking pairs of vertices v i and v j , and one of their common out-neighbours v k , then setting w( --→

v i v k ) = w( --→ v j v k ) = 1
, and setting all other arcs out-going from v i and v j to 2. In doing so, note that Property (1) will be met for v i and v j , while the parity of σ - w (v k ) will remain unchanged. Assume first n is odd. Starting from v 1 , consider disjoint pairs of consecutive vertices until v n-1 is reached (that is, {v 1 , v 2 }, then {v 3 , v 4 }, and so on). For every such pair

{v i , v i+1 }, set w( --→ v i v n ) = w( ----→ v i+1 v n ) = 1.
At the end of the process, assign 2 to all nonweighted arcs. Clearly w directly respects Properties (1) and ( 2) above, so it is sumcolouring.

If n is even, then we proceed as follows. We repeat the same procedure as in the previous case but with the pairs {v 1 , v 2 }, {v 3 , v 4 }, ..., {v n-3 , v n-2 } only, choosing the arcs from their members towards v n-1 to be weighted 1. Once the 1's are attributed, put 2 on all remaining arcs, including ----→ v n-1 v n . Note that Property (1) is violated by σ + w (v n-1 ) only, which is equal exactly to 2. But since n > 2 (since otherwise -→ T would not be nice), we have σ

- w (v n ) > 2 = σ + w (v n-1
). So w is sum-colouring.

A directed 1-2 Conjecture

We now investigate how helpful it is to be granted the possibility to locally modify σ -and σ + at every vertex of a given digraph. Let us define this formally. Let w be a total-weighting of some digraph D. For every vertex v of D, we define:

σ - w (v) := w(v) + u∈N -(v) w( -→ uv) and σ + w (v) := w(v) + u∈N + (v) w( -→ vu)
that is, the local weight by w is counted in both σ - w (v) and σ + w (v) (as if we were weighting a loop at v). Once more, we call w sum-colouring if σ + w (u) = σ - w (v) for every arc -→ uv of D. This time, it should be clear that all digraphs admit a sum-colouring total-weighting (if D is not nice, in the sense defined for the arc version, just use vertex weights to "destroy" its bad configurations). For every digraph D, the chromatic parameter χ t Ł (D), denoting the least number of consecutive weights in a sum-colouring k-total-weighting of D, is hence well-defined.

As a consequence of a remark above, we have the following.

Observation 7. For every nice digraph D, we have χ t Ł (D) ≤ χ e Ł (D).

Corollary 3 then implies that χ t Ł (D) ≤ 3 holds for every nice digraph D. It can also be proved that this inequality holds when D is not nice. Theorem 8. For every digraph D, we have χ t Ł (D) ≤ 3.

Proof. Let D be the digraph obtained from D by adding a loop at every vertex, and let G(D ) be the bipartite graph constructed from D as described in the proof of Theorem 1. Note that, by construction, every loop --→ v i v i of D becomes an edge v + i v - i in G(D ). Since G(D ) is clearly nice, it admits a sum-colouring 3-edge-weighting according to Theorem 2. Now just transfer the edge weights from G(D ) to D as described in the proof of Theorem 1 to obtain a 3-arc-weighting of D which is sum-colouring (unless σ + (v i ) = σ -(v i ) for some vertex v i , but this is not a problem). To now get a sum-colouring 3-total-weighting of D, just transfer the arc weights from D to D, with the exception that the weight of every loop --→ v i v i in D becomes the weight of v i in D.

Since the possibility of locally modifying both σ -and σ + is very handy, one could conjecture that the following, which is a direct analogue of the 1-2 Conjecture, should be true.

Directed 1-2 Conjecture. For every digraph D, we have

χ t Ł (D) ≤ 2.
This section is organized as follows. We first show, in Section 3.1, that the Directed 1-2 Conjecture, as currently stated, is actually false. So we propose, in the same section, a refined conjecture. We then prove in Section 3.2 that both versions of the Directed 1-2 Conjecture are true in some contexts.

Counterexamples to the Directed 1-2 Conjecture

As seen in the proof of Theorem 1, there is an equivalence between edge-weighting nice bipartite graphs and arc-weighting nice digraphs in a sum-colouring way. Some kind of similar relation can also be pointed out for our definition of sum-colouring total-weighting.

Let us introduce some more terminology. Given a digraph D, the balanced anti-matched bipartite graph G(D) obtained from D as described in the first part of the proof of Theorem 1 is called the bipartite anti-matched-representation of D. Conversely, assuming G is an anti-matched bipartite graph, we call the digraph D(G), as obtained in the second part of the proof of Theorem 1, the directed representation of G.

v 1 v 2 v 3 v 4 2 1 2 3 1 2 1 3 v 1 v 2 v 3 v 4 2 1 2 3 1 2 1 3 v + 1 v + 2 v + 3 v + 4 v - 1 v - 2 v - 3 v -
As seen in the proof of Theorem 8, note that, in the bipartite representation G(D) of a digraph D, having an edge v + i v - i in G(D) corresponds, in D, to an arc from v i to itself. Furthermore, as within an arc-weighting, in D, a loop at v i contributes to both σ -(v i ) and σ + (v i ), then weighting the edge v + i v - i in G(D) can actually be seen as attributing the personal weight to v i in the corresponding total-weighting of D. So an edge-weighting of G(D) under the assumption that G(D) is matched, i.e. its two partite sets can be ordered so that we have a perfect matching joining its every pair of ith vertices, is quite similar to a total-weighting of D (basically, for every vertex v i , the weight of v i in D is represented by the weight on v + i v - i in G(D)). Adding edges joining the first vertices, the second vertices, and so on, of the bipartite anti-matched representation of D, we obtain a bipartite graph which we call the bipartite matched-representation of D (see Figure 2 for an illustration). Assuming G is a matched bipartite graph with bipartition {a 1 , a 2 , ..., a n } ∪ {b 1 , b 2 , ..., b n }, we call every edge a i b i a matched edge of G.

There is an important point one should be careful with. By the remarks above, the following is true. Observation 9. Let D be a digraph, and G(D) be the bipartite matched-representation of D. Then, we have

χ t Ł (D) ≤ χ e Σ (G(D)).
However, the converse of Observation 9 is not true, in the sense that a sum-colouring totalweighting of D does not necessarily yield a sum-colouring edge-weighting of G(D). This comes from the fact that, for every matched edge

v + i v - i of G(D), we require σ(v + i ) = σ(v - i ), while the equivalent requirement in D would be to have σ + (v i ) = σ -(v i ), which we do not impose.
Due to this remark, if we have a matched bipartite graph G which is not sum-colouring 2-edge-weightable, then we cannot directly deduce that D(G) is not sum-colouring 2-totalweightable. We can nevertheless obtain non sum-colouring 2-total-weightable digraphs via the following observation.

Observation 10. Let D be a non-nice digraph having a directed cycle -------→ v 1 v 2 ...v k v 1 such that all arcs --→ v 1 v 2 , --→ v 2 v 3 , ..., --→ v k v 1 are bad, i.e. we have d + (v i ) = d -(v i+1 ) = 1 for every such arc ---→ v i v i+1 . If k is odd, then χ t Ł (D) > 2.
Observation 10 notably shows that χ t Ł (D) > 2 whenever D is a directed odd cycle. It is not so surprising that directed odd cycles are counterexamples to the Directed 1-2 Conjecture, as, since they are not nice, the vertex weights are really necessary here. This makes us wonder whether the following refined conjecture is true.

Refined Directed 1-2 Conjecture. For every nice digraph D, we have χ t Ł (D) ≤ 2.

Towards that refined conjecture, recall that already Theorem 8 implies that we have χ t Ł (D) ≤ 3 for every nice digraph D. Using Observation 9, we can also confirm the Refined Directed 1-2-3 Conjecture for digraphs D whose bipartite matched-representation G(D) verifies χ e Σ (G(D)) ≤ 2. Many nice bipartite graphs are known to have this property, see [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF], one of the most interesting results for our purpose being the following.

Theorem 11 (Chang, Lu, Wu, Yu [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]). Let G be a nice connected bipartite graph with bipartition A ∪ B. If at least one of |A| and |B| is even, then χ e Σ (G) ≤ 2.

We say that a digraph is connected if its underlying undirected graph is connected.

Corollary 12. Every connected digraph with even order agrees with the Refined Directed 1-2 Conjecture.

Proof. Let D be a connected digraph with even order, and let G(D) be the bipartite matched-representation of D. Since D has even order, both parts of G(D) are of even size. Besides, G(D) is necessarily nice since otherwise, as G(D) is matched, it would mean that D has isolated vertices. So that we can apply Theorem 11 directly on G(D) and get our conclusion, we just have to make sure that G(D) is connected. Since D is connected, for every two vertices u and v, there exists a path P from u to v in und(D). We need to prove that there is a path from u + (or u -, but this is equivalent as u + u -is an edge of G(D)) to v + (or v -, for the same reason) in G(D). Assuming u is the vertex succeeding u in P , we actually just need to prove that u + or u -is adjacent to u + or u -in G(D). But this is necessarily the case: since uu is an edge of und(D), either the arc -→ uu or -→ u u belongs to D. So u + u -is an edge of G(D) in the first situation, while u + u -is an edge in the second situation. Repeating this argument for every two subsequent vertices of P , we get that G(D) indeed has the claimed path.

Since the arguments above apply whatever u and v are, we get that G(D) is connected. So G(D) admits a sum-colouring 2-edge-weighting according to Theorem 11, which we can directly turn into a sum-colouring 2-total-weighting of D.

As going to be discussed in concluding Section 4, proving the counterpart of Corollary 12 for connected digraphs with odd order does not seem as easy. This problem is in particular connected to other problems concerning nice bipartite graphs and the 1-2-3 Conjecture.

Digraphs verifying the (Refined) Directed 1-2 Conjecture

In this section, we prove that some classes of digraphs agree with the (Refined) Directed 1-2 Conjecture. We in particular consider acyclic digraphs, and bipartite digraphs. Proof. Start by mimicking the beginning (i.e. the pairing part) of the proof of Theorem 6 as long as possible to get a 2-arc-weighting w of D such that all σ - w (v i )'s are even and some σ + w (v i )'s (but maybe not all) are odd. Put w(v i ) = 2 for every vertex v i of D. From now on we will use notation w to deal with the resulting 2-total-weighting. In case there is no arc --→ v i v j such that σ + w (v i ) = σ - w (v j ), we are done. Otherwise, there are some such arcs --→

v i v j such that σ + w (v i ) = σ - w (v j ) with σ + w (v i
) being even while it should be odd. From the point of view of --→ v i v j , we call v i bad, while we call v j good. Note that all sinks are necessarily good for all arcs.

To fix the conflicts, we prove that, starting from the rightmost conflicting arc (i.e. the one --→ v i v j with v i having the largest index), we can make v i good by considering another arc --→ v k v i and possibly making v k bad. This means that we can basically "push" the conflicts towards the left, i.e. towards the sources, which we can handle easily (since we do not care about their value of σ - w ). Consider a conflicting arc --→ v i v j . By definition, we have:

• σ - w (v j ) even and σ + w (v j ) odd or null (good), and

• σ - w (v i ) even and σ + w (v i ) even (bad).
If v i is a source, then we can solve the problem by just switching w(v i ), i.e. set this weight to 3 -w(v i ). Now, if v i is not a source, then there is an arc --→ v k v i with k < i. Then by just switching the weight w(v i ), as well as the weight w( --→ v k v i ), note that v i becomes good. By just repeating this argument until only sources of D are bad, we eventually can solve all conflicts and make w sum-colouring.

Conclusion

In this paper, we have introduced new directed analogues of the 1-2 and 1-2-3 Conjectures. Although the Directed 1-2-3 Conjecture admits an easy proof, the unexpected equivalence between the Directed 1-2-3 (and 1-2) Conjecture and the 1-2-3 Conjecture we have exhibited in Theorem 1 is of interest. This is mainly because the status of the 1-2-3 Conjecture for nice bipartite graphs is not entirely understood. Indeed, apart from completely proving the 1-2-3 Conjecture, perhaps the most important open question related to the 1-2-3 Conjecture is the existence of an easy characterization of nice bipartite graphs G verifying χ e Σ (G) ≤ 2.

Question 15. Which nice bipartite graphs G verify χ e Σ (G) ≤ 2?

As summarized in [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF], only a few classes of nice bipartite graphs G having χ e Σ (G) = 3 are known at the moment; so studying the Directed 1-2-3 and 1-2 Conjectures may be a new way to attack Question 15. In particular, let us mention the following potential directions for future work. For that purpose, we recall that G should be anti-matched, and hence balanced. In case G is not balanced, we can get an equivalent nice balanced bipartite graph by adding isolated vertices to G. However, if G is already balanced, we note that the number of vertices of D(G) will be |V (G)|/2 (while the size is preserved). So considering D(G) may be simpler in some situations. More generally, if we could prove that it is NP-complete to decide whether χ e Ł (D) ≤ 2 for a given nice digraph D, then we would prove that no easy characterization answering Question 15 exists. This is of interest as the complexity of deciding whether χ e Σ (G) ≤ 2 is still unknown under the restriction that G is a given nice bipartite graph.

3. Towards the Refined Directed 1-2-3 Conjecture, if we could prove that some nice digraph D refute it, then we would get another example of nice bipartite graph G(D) not in the class mentioned in Question 15. Such a graph would more likely be a new graph not mentioned in the summary [START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF], as it can be easily checked that all such known graphs, when matched (i.e. have their vertices ordered as explained in Section 3.1), form a representation of digraphs which are not nice.

4. Conversely, to prove the counterpart of Corollary 12 for connected digraphs with odd order, it would be sufficient to prove that we have χ e Σ (G) ≤ 2 for every nice matched bipartite graph G. Actually it would be sufficient to prove that this result holds if we allow the two ends of every matched edge to have the same value of σ.

5.

During previous investigations, it was noted that, in particular contexts, finding a correct weighting of some graph is similar to finding a decomposition into irregular subgraphs. This was notably considered in [START_REF] Baudon | On decomposing regular graphs into locally irregular subgraphs[END_REF], where the authors study decompositions into locally irregular subgraphs, i.e. graphs with no adjacent vertices with the same degree, which are related to sum-colouring edge-weightings in regular graphs. This approach was further considered in [START_REF] Bensmail | Decomposing oriented graphs into six locally irregular oriented graphs[END_REF], where, in the context of another directed variant of the 1-2-3 Conjecture, the authors consider decompositions of digraphs into locally irregular subgraphs (for some definition of irregularity in digraphs). We could consider this question as well in the context of our current investigations. Namely, one could define a locally irregular digraph as a digraph in which, for every arc -→ uv, we have d + (u) = d -(v), and then study decompositions of digraphs into locally irregular subdigraphs.

1 2 1 Figure 1 :

 111 Figure 1: Illustration of the argument why -→ C 2 7 admits no sum-colouring 2-arc-weighting.Having a weight (here, 1) on some arc (here, the topmost arc) forces two incident arcs to be weighted differently.

Directed 1 - 2 - 3

 123 Conjecture. For every nice digraph D, we have χ e Ł (D) ≤ 3.

Theorem 4 .

 4 For every nice bipartite digraph D, we have χ e Ł (D) ≤ 3.Proof. Assume A ∪ B is a bipartition of V (und(D)), where und(D) denotes the underlying undirected graph of D. Let D ↑↑ and D ↓↓ be the subdigraphs of D induced by the arcs going from, say, A to B, and from B to A, respectively. We note that both D ↑↑ and D ↓↓ are nice, since otherwise D itself would not be nice. Of course, since D is bipartite, so are D ↑↑ and D ↓↓ .

Figure 2 :

 2 Figure 2: A digraph D (left), the same digraph D with a loop at every vertex (middle), and the bipartite matched-representation G(D) of D (right). From a sum-colouring edge-weighting of G(D), one can deduce a sum-colouring arc-weighting of D , from which is deduced a sum-colouring total-weighting of D.

Theorem 13 .

 13 For every acyclic digraph D, we have χ t Ł (D) ≤ 2.

Theorem 14 .

 14 For every bipartite digraph D, we have χ t Ł (D) ≤ 2. Proof. Let A ∪ B denote the bipartition of D. Start with assigning weight 2 to all arcs of D so that σ -and σ + are even for all vertices. Now assign weight 1 on all vertices of A, and assign weight 2 on all vertices in B. The result is that, • for every a ∈ A, both σ -(a) and σ + (a) are odd, and • for every b ∈ B, both σ -(b) and σ + (b) are even. It then follows that, for every arc -→ uv of D, the parities of σ + (u) and σ -(v) are different, so the two values are different.

1 .

 1 When checking what is the value of χ e Σ (G) for a nice bipartite graph G, one may equivalently check the value of χ e Ł (D(G)) of a directed representation D(G) of G.

2 .

 2 If we have χ e Ł (D) = 3 for some nice digraph D, by Theorem 1 we get an equivalent nice bipartite graph G(D) verifying χ e Σ (G(D)) = 3.

In case no ambiguity is possible, we will sometimes voluntarily omit the subscript w (e.g. write σ for σw) to lighten the notations.

Acknowledgement

The authors would like to thank two anonymous referees for their careful reading of a previous version of the current article, and for raising constructive comments.

The second author was supported by ERC Advanced Grant GRACOL, project no. 320812, and by ANR grant no. ANR-13-BS02-0007 "STINT". The third author was supported by the National Science Centre, Poland, grant no. 2014/13/B/ST1/01855. The third and fourth authors were partly supported by the Polish Ministry of Science and Higher Education. The fourth author was supported by the National Science Centre, Poland, grant no. DEC-2013/09/B/ST1/01772.


Arthur Guillon
email: arthur.guillon@lip6.fr

Marie-Jeanne Lesot
email: marie-jeanne.lesot@lip6.fr

Christophe Marsala
email: christophe.marsala@lip6.fr

Nikhil R Pal
email: nikhil@isical.ac.in

Proximal Optimization for Fuzzy Subspace Clustering

Keywords: Fuzzy partitioning clustering, subspace clustering, proximal descent

This paper proposes a fuzzy partitioning subspace clustering algorithm that minimizes a variant of the FCM cost function with a weighted Euclidean distance and a penalty term. To this aim it considers the framework of proximal optimization. It establishes the expression of the proximal operator for the considered cost function and derives PFSCM, an algorithm combining proximal descent and alternate optimization. Experiments show the relevance of the proposed approach.

Introduction

Subspace clustering [START_REF] Agrawal | Automatic subspace clustering of high dimensional data for data mining applications[END_REF] is an unsupervised machine learning task that aims at partitioning data into groups with strong internal similarity and external dissimilarity (just as clustering) while also discovering the best subspaces to represent these clusters. The identified subspaces are required to be minimal, yet sufficient to describe the clusters they contain.

The definition of subspace clustering requires the identification of the clusters and of their subspaces to be simultaneous: indeed, if either clusters or their subspaces are known beforehand, the problem reduces to finding the subspaces or correct description of the clusters, respectively. In addition, as opposed to feature selection, different clusters are most of the time discovered in different subspaces.

As briefly sketched in Section 2, there exist several families of techniques and algorithms to solve the subspace clustering problem, as well as various representations of the subspaces, depending on the intended application of the subspace clustering.

This paper places itself in the partitioning paradigm in a fuzzy setting and produces clusters identified by a center. Moreover, it discovers axis-parallel subspaces, which are thus identified by weights on the original data features. An original cost function formalises these concepts and adds, to a FCM cost function [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF] with weighted Euclidean distance, a penalty term expressing constraints to identify the relevant subspaces.

As this penalty term is not differentiable, standard optimization techniques such as alternate optimization are not available. This paper introduces a novel optimization scheme, exploiting tools from the proximal descent theory [START_REF] Moreau | Fonctions convexes duales et points proximaux dans un espace hilbertien[END_REF]. The utilisation of such techniques is still relatively new in machine learning and in clustering in particular [START_REF] Parikh | Proximal algorithms[END_REF].

This paper proposes an innovative implementation of this theoretical paradigm in the fuzzy subspace clustering framework. It establishes a theorem giving the expression of the proximal operator allowing the optimization of the considered cost function. Finally, it proposes an algorithm, called PFSCM, standing for Proximal Fuzzy Subspace C-Means, using this result to solve the subspace clustering problem through the combination of proximal descent and alternate optimization.

This paper is structured as follows: in Section 2, related works and the scientific context of subspace clustering are summed up. A new cost function is presented and studied in Section 3. In Section 4, the implementation of proximal descent is studied to optimize the proposed function, leading to the update equation from which the PFSCM algorithm is derived. This algorithm is then experimentally validated in Section 5.

Related Works

Subspace clustering [START_REF] Agrawal | Automatic subspace clustering of high dimensional data for data mining applications[END_REF] can be seen as a combination of clustering and feature selection tasks, the latter being performed locally for each cluster. It aims at identifying both a data decomposition into homogeneous and distinct subgroups and the subspaces in which these clusters are defined. Figure 1 gives an example of such clusters, contained in axis-parallel subspaces: although the data are 3dimensional, cluster c 1 actually lives in the plane z = 0 and cluster c 2 in the plane y = 0.

A large number of approaches to the subspace clustering problem have been explored in machine learning as well as in data mining or computer vision. A list can be found in [START_REF] Vidal | A tutorial on subspace clustering[END_REF]. This paper focuses on iterative partitioning techniques. The k-subspace algorithm [START_REF] Wang | K-subspace clustering[END_REF] generalises the k-means approach, alternating between the assignation of points to the clusters and the estimation of subspaces to fit these clusters. Witten & Tibshirani [START_REF] Witten | A framework for feature selection in clustering[END_REF] propose a reformulation of the k-means minimization problem into a maximization problem with a weighted distance. An 1 -based constraint is added in order to produce sparse weight vectors and identify the subspaces. Qiu et al. [START_REF] Qiu | A sparse fuzzy c-means algorithm based on sparse clustering framework[END_REF] adapt this framework to fuzzy clustering and compare it to some usual subspace clustering algorithms. Both the crisp and fuzzy variants of these algorithms heavily modify the original k-means function to formulate a maximization problem with a 1 -regularization term, in order to identify minimal subspaces.

Closer to the original k-means paradigm, the fuzzy c-means clustering algorithm [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF] has been adapted to the context of subspace clustering. Keller & Klawonn [START_REF] Keller | Fuzzy clustering with weighting of data variables[END_REF] adapt the FCM cost function to use a weighted Euclidean distance. Denoting (x i ) n i=1 ∈ R d the datapoints of dimension d, c the number of clusters, (u ri ) ∈ [0,1] for i ∈ {1, . . . , n} and r ∈ {1, . . . , c} the fuzzy membership degree of x i to cluster C r , µ r ∈ R d the center of cluster C r and (w rj ) ∈ [0,1] the weight of dimension j for cluster C r , they study the following cost function:

J K&K (C, U, W ) = c r=1 n i=1 u m ri d j=1 w v rj (x ij -µ rj ) 2 (1)
where m, v ∈ R are fuzzifiers which can be tuned by the user to specify the level of fuzziness of the corresponding parameters and C, U, W are respectively the matrices containing the centers (µ r ), the memberships (u ri ) and the weights (w rj ).

The function is minimized under the following constraints:

- The first two constraints (C1) and (C2) are similar to the FCM ones. Constraint (C3) on the weights (w rj ), where a is a user-defined parameter, is specific to the subspace clustering problem and prevents the trivial solution such that ∀r, ∀j, w rj = 0. The minimization of Equation (1) under these constraints produces a solution to the fuzzy subspace clustering problem. The computed weights (w rj ) indicate how close the points assigned to C r are in dimension j.

Figure 1 illustrates the relation between Equation (1) and subspace clustering: cluster c 1 lies in the (x, y) plane. In the z dimension, its points are very close to its center; therefore, minimizing J K&K amounts to maximizing w 1z rather than w 1x and w 1y . Borgelt [START_REF] Borgelt | Fuzzy subspace clustering[END_REF] generalises Keller and Klawonn's work and proposes to slightly change the weights, so that the algorithm completely selects dimensions by attributing a null weight to others. He introduces the following cost function, where the terms u m ri and w v rj are replaced with general fuzzification functions g and h [START_REF] Klawonn | What is fuzzy about fuzzy clustering? understanding and improving the concept of the fuzzifier[END_REF], which are supposed to be convex and differentiable on the [0,1] interval:

J B (C, U, W ) = c r=1 n i=1 h(u ri ) d j=1 g(w rj )(x ij -µ rj ) 2 (2)
This function is optimized under the same constraints as J K&K . Experimental results on artificial data show that Borgelt's algorithm better selects subspaces. Both Keller & Klawonn and Borgelt functions are differentiable in each parameter on the considered domains, which allows to retain the technical framework of fuzzy c-means alternate optimization. They derive their algorithms from the corresponding cost function through the usual Lagrangian technique and obtain three update equations for parameters C, U and W .

Proposed Cost Function for Fuzzy Subspace Clustering

In this section, a new cost function is introduced to model the subspace clustering problem and a study of its properties is conducted.

A Weighted Fuzzy c-Means Function

Using the same notations as in Section 2, we propose the following cost function:

J(C, U, W ) = c r=1 n i=1 u m ri d j=1 w 2 rj (x ij -µ rj ) 2 + γ c r=1 d j=1 (w rj ) -α (3)
under the classic FCM constraints (C1) and (C2). The first term is the same as Keller & Klawonn's cost function, except for the weight fuzzifier v which is set to 2, in order to simplify further mathematical analysis of the function: it corresponds to a FCM cost function with a locally weighted Euclidean distance.

The second term adds a cost to the function which prevents the sum of the weights of each cluster C r from being too far from the user-defined parameter α which plays the same role as a in Keller & Klawonn's (C3) constraint: for α = 0, it prevents the trivial solution W = 0. The user-defined parameter γ ∈ R is used to balance out the two terms: it only needs to be large enough to penalize trivial solutions. This term can also be interpreted as an "inlined" constraint that incorporates constraint (C3), which does not need to be optimized through the particular Lagrangian method, but rather allows the use of new optimization techniques.

The cost function J in Equation (3) thus conveys the idea of finding a solution to the subspace clustering problem with a relaxed constraint, inspired by 1regularization [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF].

Minimization of the Cost Function

Using the cost function J, solving the subspace clustering problem amounts to finding the parameters (C * , U * , W * ) that minimize J. This function can be decomposed as follows:

J(C, U, W ) = F (C, U, W ) + γG(W ) where F (C, U, W ) = c r=1 n i=1 u m ri d j=1 w 2 rj (x ij -µ rj ) 2 G(W ) = c r=1 G r (W r ) = c r=1 d j=1 (w rj ) -α
The function J verifies several properties of interest, which motivate and validate the technique used in the next section. First, J is a convex function of W , as it is the sum of convex functions.

F is differentiable in all three parameters and it can be shown that its gradient is Lipschitz-continuous for fixed C and U . These properties guarantee good performances of well-known optimization algorithms, such as gradient descent.

For fixed W , minimizing J under constraints is equivalent to minimizing F . As for fuzzy c-means, this can be done through alternate optimization. From the above function and constraints, the two classic update equations for membership degree and cluster centers are derived:

u ri = d 2 1-m ri c s=1 d 2 1-m si where d 2 ri = d j=1 w 2 rj (x ij -µ rj ) 2 (4)
and

µ rj = n i=1 u m ri • x ij n i=1 u m ri (5)
These two equations are used in the PFSCM algorithm described in Section 4 to update the terms u ri and µ r in order to find the minimum of J.

Function G is convex but not differentiable in the variable W , which prevents the derivation of an update term for weight optimization and motivates the use of proximal descent, proposed in the next section.

Proximal Descent for Weight Optimization

As it is not differentiable everywhere, the function J previously defined cannot be optimized by classic alternate optimization. This section proposes a new algorithm, PFSCM (which stands for Proximal Fuzzy Subspace C-Means), based on an advanced technique of convex optimization: proximal descent [START_REF] Parikh | Proximal algorithms[END_REF].

In this section, the parameter of interest is the matrix of weights W , while C and U are fixed. Therefore, J(C, U, W ) is noted J(W ) for the sake of simplicity.

Proximal Descent

The cost function has the form J(W ) = F (W ) + γG(W ), where both functions are convex but only F is differentiable and classic optimization techniques thus cannot be applied. As this general form of function has gained interest in the machine learning community (for example, when the second function G is a regularization term), proximal descent has been studied as an alternative to these techniques [START_REF] Bach | Convex optimization with sparsity-inducing norms[END_REF].

When γ = 0, usual optimization techniques would suggest to seek for the minimum of F (0 in the particular case of Equation ( 3)) by iterating some update equation. For example, gradient descent considers a general equation of the form

W t+1 = W t -η • ∇F (W t
), where t is the iteration index and η is a descent step size. This simple optimization scheme provides an iterative algorithm in order to minimize any convex function F , starting from any W 0 and iterating until convergence.

As the function G is not differentiable, its gradient ∇G does not exist for each W t . Proximal descent enriches gradient descent in the following way:

W t+1 = prox γ L G W t - 1 L ∇F (W t ) (6)
where

prox γ L G (W ) = argmin W 1 2 W -W 2 + γ L G(W ) (7)
where L > 0 is a descent step size, similar to η. That is, in order to solve a global minimization problem, proximal descent solves a minimization problem as defined by Equation ( 7) at each step of the iteration. Proximal descent can be understood as a technique of separating the descent in two phases: first for the function F , then for G. Such a descent scheme is also known as the "forward-backward" algorithm. In order to solve Equation [START_REF] Klawonn | What is fuzzy about fuzzy clustering? understanding and improving the concept of the fuzzifier[END_REF], proximal descent approximates F around the current point of the iterative descent, W t :

argmin W F (W t ) + ∇F (W t ), W -W t + γG(W ) + L 2 W -W t 2 = argmin W 1 2 W -(W t - 1 L ∇F (W t )) 2 + γ L G(W )
Here again, if γ = 0, this problem has a simple solution: gradient descent scheme W t+1 = W t -1 L ∇F (W t ), hence the scheme given in Equation ( 6). The key ingredient to efficiently implement the descent scheme defined by Equation ( 6) is the notion of proximal operator: it provides a closed-form expression to the optimization problem defined by Equation [START_REF] Klawonn | What is fuzzy about fuzzy clustering? understanding and improving the concept of the fuzzifier[END_REF], which is often counter-intuitive, yet simple to implement.

Efficient Weight Optimization with Proximal Operators

We establish in the following theorem a proximal operator for the penalty term

G(W ) = γ c r=1 d j=1 (w rj ) -α . Let K be the vector (1, 1, . . . 1) ∈ R 1×d , such that K • K = d. Theorem 1. Let G r (W r ) = | d j=1 (w rj ) -α| and L ∈ R. prox γ L Gr (W r ) = W r + 1 d K • α + prox γd L |•| (K • W r -α) -K • W r (8)
where

prox λ|•| (x) = sign(x) max(|x| -λ, 0). Moreover, prox γ L G (W ) = prox γ L Gr (W r ) r=1...c ∈ R d×c .
Proof. The proof uses results from [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF] and [START_REF] Parikh | Proximal algorithms[END_REF]. First, G r (W r ) = φ(K • W r ) where φ(x) = |x -α|. Using the translation and semi-orthogonal linear transform properties [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF]:

prox Gr (W r ) = W r + 1 d K • prox φ (K • W r ) -K • W r ) = W r + 1 d K • α + prox d|•| (K • W r -α) -K • W r )
Hence the expression of prox γ L Gr by the postcomposition property [START_REF] Parikh | Proximal algorithms[END_REF]. Finally, prox γ L G is computed using the separable sum property of proximal operators [START_REF] Parikh | Proximal algorithms[END_REF].

Equation [START_REF] Moreau | Fonctions convexes duales et points proximaux dans un espace hilbertien[END_REF] gives the expression of a proximal operator for the G function which can be used to efficiently implement the scheme defined in Equation ( 6) to update the current estimation of W .

As for gradient descent, the choice of L matters for the actual convergence of the descent, as well as for its speed. We observe that setting L = trace(H -1 ) yields good results, where H is the Hessian matrix of F (as a function of W ). As F is simple enough, H is a diagonal matrix and does not depend on W .

A Fuzzy Subspace Algorithm: PFSCM

Using the previous mathematical results, we propose the PFSCM algorithm for fuzzy subspace clustering (see Algorithm 1). PFSCM combines alternate optimization of k-means-style algorithms for differentiable parameters with proximal descent for the optimization of the weights.

Initialization is a typical issue of k-means-like algorithms. In this paper, initial centers are randomly chosen and each cluster receives uniform weights for all dimension. As most partitioning algorithms, the number c of clusters to identify must be set by the user, as well as constants γ > 0 and α > 0.

Algorithm 1: The proximal fuzzy subspace clustering PFSCM algorithm

The algorithm then iterates the update of all three parameters U , µ and W , much like alternate optimization in k-means algorithm. It consists of two alternate inner loops: the regular parameters µ and U are optimized separately from W , which requires the special optimization procedure described in the previous subsection. Parameters µ and U are optimized one last time at the end of the algorithm, in order to guarantee that the result takes the final computed weights into account.

The convergence criteria are defined as the distance between the current and the previous values of the parameters being optimized. In particular, convergence for (µ, U ) is defined as

µ t -µ t+1 2 < ε ∨ U t -U t+1 2 < ε.
PFSCM outputs U , C and W . In order to exploit the result of the algorithm, it may be of interest to extract the dimension associated to each cluster. To that aim we propose to post-process the matrix W using an additional parameter cut to cut out the irrelevant dimensions in a simple fashion: a dimension j for a cluster C r is considered relevant if w rj > cut.

Experimental Study

The proposed PFSCM algorithm has been tested on artificial data in order to study its ability to correctly identify centers of non-circular clusters, as well as the dimensions that are relevant to describe the clusters. The results show the effectiveness of PFSCM in detecting the clusters and their subspaces. Moreover, PFSCM is compared to Keller & Klawonn's algorithm [START_REF] Keller | Fuzzy clustering with weighting of data variables[END_REF] and shows to provide a better estimation of the dimensionality of the subspaces. 1. Computed weights for the example given in Figure 2. Column w1 (resp. w2) denotes the weight associated to the x-axis (resp. y-axis).

Illustrative Example

This subsection presents an illustrative experiment in d = 2 dimensions, similar to the example given in Keller & Klawonn [START_REF] Keller | Fuzzy clustering with weighting of data variables[END_REF] and graphically represented in Figure 2: four clusters are generated, one of them (the top red one in Figure 2) being circular while the others have a very low variance in one dimension. PFSCM is run with c = 4, m = 2, α = 1 and γ = 1000.

In Figure 2 the points are colored according to the cluster C r for which u ri is maximum and Table 1 presents the weights computed for each dimension and cluster. It can be observed that PFSCM correctly identifies the desired clusters and their dimensions: the two weights (w 1 , w 2 ) found for the circular cluster are similar, whereas the horizontal (respectively vertical) clusters verify w 2 w 1 (respectively w 1 w 2 ). It is worth noting that, for this specific instance, some points close to the blue cluster are assigned to one of the horizontal clusters, as it minimizes the cost function. This kind of inliers is frequent in subspace clustering problems, and naturally leads to the use of fuzzy membership values (u ri ). In a similar fashion, moving the vertical cluster towards the center of the whole figure leads to the "stealing" of some points of the red cluster by the blue one. However, it can be observed that the identified dimensions for the circular cluster stay relatively stable (both w rj > cut = 0.2), failing to recognize a non-flat cluster only 4 times out of 100 in the specific situation where all generated centers are vertically aligned.

Experimental Protocol

Considered Data In order to validate PFSCM, the previous experiment is generalized to higher dimensions, more precisely to artificial data of dimension d ∈ {5, 7, 9, 11, 13, 15}. For each experiment, k = 4 centers c 1 , . . . , c 4 are generated randomly in the hypercube [-3,3] d with a minimum (Euclidean) distance of 0.3 between the centers. Then, d r dimensions j 1 , . . . j dr are randomly picked, with d r randomly chosen between 1 and d -3. Dimensions j 1 , • • • , j dr are thereafter called the "relevant dimensions" for cluster C r .

For each cluster, 100 points are generated according to a Gaussian distribution, with variance v < 0.1 for dimensions j 1 , . . . , j dr and v ∈ [0.5,0.9] for other dimensions. The generated points in cluster r in dimension j thus follow X r ∼ N (c r , v j ). The parameter cut is set to 1 2d , which is a simple rule of thumb to identify the dimensions selected as relevant by the algorithms in each considered dimension d.

Algorithm

Quality Criteria Both algorithms are evaluated on three metrics in order to qualify their results and their ability to discover the desired clusters and subspaces, and their dimensions.

First, let δ = 4 r=1 µ r -c r 2 be the sum of the Euclidean distances between the generated centers and the computed ones (µ r ): this metric is a standard quality criterion for evaluating the produced clusters. A low value means that the computed centers are close to the original ones.

We also consider θ defined as the percentage of clusters for which all relevant dimensions are correctly identified by the algorithm: the relevant dimensions are correctly identified if

w rj > cut ⇔ j ∈ {j 1 , • • • j dr }.
Finally, for the clusters for which the relevant dimensions have been correctly identified, let the weight ratio φ = ω1 ωj dr where ω 1 is the largest computed weight and ω j dr the smallest computed weight for the relevant dimensions. This metric computes the distortion of the cluster between the relevant dimensions, as estimated by both algorithms.

Experimental Results

The results of the experiment are presented in Table 2 in the form of the means and standard deviations of the three criteria, computed over 100 runs of each It can be observed that PFSCM correctly identifies the generated centers (as shown by δ), and produces stable results in each dimension, as shown by the low standard deviation. Moreover the algorithm, along with the proposed cut ratio cut = 1 2d , performs well in selecting the relevant dimensions of the subspaces (as shown by θ). Finally, the weights ratio φ is relatively stable when the number of dimensions increases.

Keller & Klawonn's algorithm correctly identifies the centers (c r ) and the difference with PFSCM is not meaningful. However it appears to miss out some relevant dimensions of the generated subspaces. This is a general feature of the algorithm, which can be seen in [START_REF] Keller | Fuzzy clustering with weighting of data variables[END_REF] as well: although the most relevant dimension is almost always identified, Keller & Klawonn's algorithm gives a much smaller weight to the other relevant dimensions, which is also shown by the larger mean for φ. This feature can be modulated by tuning the value of the fuzzifier v, but then this modification affects the weights of each dimension, including the most relevant one.

In summary, PFSCM identifies the same clusters as Keller & Klawonn's algorithm, but produces a better estimation of the dimensions of the subspaces. It is also more regular when the dimension d increases.

Conclusion and Future Works

This paper introduces a new approach to solve the fuzzy subspace clustering problem with a cost function involving non-differentiable terms. Advanced optimization techniques are explored, which replace the standard update equations of fuzzy c-means-like algorithms.

Experiments on synthetic data show the relevance of the proposed approach, that appears to correctly identify all the relevant dimensions and not more, whereas Keller & Klawonn's algorithm tends to underestimate the number of relevant dimensions. This provides more information about the importance of each dimension for the subspaces and clusters.

Future works will aim at generalizing this approach around the same key ideas: a differentiable function matching the specification of the problem and one or several penalty functions, expressing constraints on the shape of the solution. The introduction of regularization terms for parameters other than W will also be studied. Finally, more efficient descent schemes will be considered, in order to speed up the descent.

Fig. 1 .

 1 Fig. 1. Two clusters, contained in two different planes: c1 in (x, y) and c2 in (x, z).

  C1) ∀i ∈ {1, . . . , n}, c r=1 u ri = 1 and (C2) ∀r ∈ {1, . . . , c}, n i=1 u ri > 0; -(C3) ∀r ∈ {1, . . . , c}, d j=1 w rj = a = 0.

Fig. 2 .

 2 Fig. 2. Clustering example in two dimensions

  Parameters Keller & Klawonn's algorithm is initialized with FCM centers and uses m = v = 2, a = 1 and c = 4. PFSCM is ran with m = 2, α = 1, γ = 1000 and c = 4. Both algorithms use the same convergence criterion, with ε = 10 -4 .

Table 2 .

 2 Comparison between PFSCM and Keller & Klawonn's algorithm algorithm. Both algorithms sometimes produce bad results, identifying centers too far from the generated ones, which distort the means and standard deviations of the previous metrics. Such outliers (less than 2% of the runs) have been cleaned out of the results.

		d	δ		φ		θ
			Mean	SD	Mean	SD	%
		5	0.90	0.67	2.51	1.41	76
		7	0.98	0.81	3.08	1.72	79
	PFSCM	9 11	0.90 0.88	0.50 0.33	3.96 4.35	2.09 2.01	80 83
		13	0.97	0.40	4.78	1.99	83
		15	0.90	0.10	5.22	1.84	91
		5	1.27	1.03	2.61	1.78	43
		7	1.55	1.38	3.12	2.29	39
	K&K	9 11	1.39 1.26	1.18 0.90	4.05 4.50	3.01 3.48	31 28
		13	1.42	1.29	4.68	3.60	25
		15	1.21	1.06	8.05	3.27	10