Romain Duroux

Marouan Rami

Elodie Landagaray

Mohamed Ettaoussi
email: m.ettaoussi@yahoo.fr

Daniel- Henri Caignard

Philippe Delagrange

Patricia Melnyk

Saïd Yous
email: said.yous@univ-lille2.fr

Daniel-Henri Caignard

X = Ch

R = Oh

R = Otf

Synthesis and biological evaluation of new naphtho-and quinolinocyclopentane derivatives as potent melatoninergic (MT 1 /MT 2 ) and serotoninergic (5-HT 2C ) dual ligands

Keywords: Melatonin, serotonin, agomelatine, levogyre, dextrogyre

Ki (MT 1 ) = 0.1 nM Ki (MT 1 ) = 0.3 nM Ki (MT 1 ) = 0.4 nM Ki (MT 2 ) = 0.2 nM Ki (MT 2 ) = 0.2 nM Ki (MT 2 ) = 0.2 nM

Introduction

Since its discovery [START_REF] Lerner | Isolation of melatonin, the pineal gland factor that lightens melanocytes[END_REF], melatonin remains one of the most studied neurohormones by the scientific community due to its therapeutic perspectives and physio-pathological implications. In fact, during the last half century, melatonin has attracted an extensive campaign of research to fully study its physiological and pathological processes. Overall, however, it is clear that the melatoninergic system still haven't delivered all its secrets! To date, the available evidences indicate that this neurohormone, that is mainly synthesized by the pineal gland following a circadian rhythm [START_REF] Vanecek | Cellular mechanisms of melatonin action[END_REF], is one of the most promising therapeutic targets considering its physiological implications. Interestingly, and consistent with reported findings, melatonin is a key player in several physiological processes such as hormonal secretion, core body temperature regulation and immune system control [3][4][5] but also participates in several pathological processes including depression and anxiety [6][7].

Although, despite the consented efforts, the melatonin mechanisms of action have not yet been fully resolved. Moreover, it has been demonstrated that, through its signalling pathways, melatonin contributes to the control of replication and survival of many parasites such as Plasmodium falciparum, Plasmodium knowlesi, Trypanosoma cruzi, Toxoplasma gondii, and Leishmania infantum [START_REF] Koyama | Ubiquitin proteasome system and the atypical kinase PfPK7 are involved in melatonin signaling in Plasmodium falciparum[END_REF][9]. In this context, several in vitro and in vivo studies have shown that melatonin receptor antagonists such as luzindole were able to inhibit the Plasmodium falciparum growth [10][11]. These findings may constitute a new promising approach to research and development of new efficient anti-parasitic agents with rapid action and low toxicity.

The aforementioned physiological and pathological effects of melatonin are attributed to the activation of its binding sites, two major receptors (MT 1 and MT 2 ) belonging to the superfamily of high-affinity G protein-coupled receptors (GPCRs) [12], and the enzyme quinone reductase 2 (QR2 previousely known as MT 3 ) [6a]. The design and synthesis of

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

melatoninergic ligands has led to a large number of derivatives with different pharmacological profiles. However, only very few melatoninergic ligands (ramelteon, tasimelteon and agomelatine) are commercialized up to now [13][START_REF] Bodinat | Agomelatine, the first melatonergic antidepressant: Discovery, characterization and development[END_REF].

Agomelatine marketed nowadays for the treatment of major depression behaves as a dual ligand acting as a full agonist at melatonin MT 1 and MT 2 receptor subtypes and an antagonist for serotonin 5-HT 2C receptor subtype [START_REF] Mcallister-Williams | The use of antidepressants in clinical practice: focus on agomelatine[END_REF]. The mechanism of action of this new antidepressant is not yet fully elucidated but appears to be caused by the synergy between this combination MT 1 /MT 2 activation and 5-HT 2C deactivation [START_REF] Guardiola-Lemaitre | Agomelatine: mechanism of action and pharmacological profile in relation to antidepressant properties[END_REF]. Research for new successors has led our lab to perform a number of pharmacomodulations of agomelatine. Besides, different positions of the aromatic nucleus, the lateral acetamide chain and the methoxy group were targeted. One of the strategies adopted for the agomelatine analogues was based on the blockade of its major metabolic sites [17][START_REF] Ettaoussi | Synthesis and pharmacological evaluation of a series of the agomelatine analogues as melatonin MT 1 /MT 2 agonist and 5-HT 2C antagonist[END_REF]. Recently, we also described compounds issued from constrained naphthalenic-like structures especially the (8,9-dihydro-7H-furo[3,2-f]chromen-1-yl) derivatives [START_REF] Landagaray | MANUSCRIPT ligands: design and synthesis of (8,9-dihydro-7H-furo[3,2-f] chromen-1-yl) derivatives[END_REF] and naphthofuranic ligands [START_REF] Landagaray | Melatonergic ligands: Design, synthesis and pharmacological evaluation of novel series of naphthofuranic derivatives[END_REF]. This later modulation has led to compounds with an interesting pharmacological profile and a sub-nanomolar binding affinity especially at melatonin receptors. Insofar, we chose to extent this successful concept into a new conformationally restricted structure. Subsequently, herein we describe the synthesis and pharmacological evaluation of a new series of naphthocyclopentane derivatives as new dual ligands analogues of agomelatine.

Results and discussion

Chemistry

Synthetic routes to the designed compounds are depicted in Schemes 1-5. The synthesis of key intermediate ketones 10 and 11 was accomplished as shown in Scheme 1. Compound 10 was prepared from commercially available 2-hydroxy-7-methoxy-naphthalene [START_REF] Lerner | Isolation of melatonin, the pineal gland factor that lightens melanocytes[END_REF], which was converted to the triflate 2 by action of triflic anhydride. Heck reaction [START_REF] Miyamoto | Discovery of a 3-Pyridylacetic Acid Derivative (TAK-100) as a Potent, Selective and Orally Active Dipeptidyl Peptidase IV (DPP-4) Inhibitor[END_REF] was then realized using ethyl acrylate in the presence of bis(triphenylphosphine)palladium(II) dichloride to give compound (4). Catalytic hydrogenation and subsequent basic hydrolysis gave propionic acid 8. Finally, intramolecular Friedel-Crafts acylation with methanesulfonic acid [START_REF] Bauta | Formal Synthesis of Angiogenesis Inhibitor NM-3[END_REF] afforded ketone 10. The same procedure was used starting from commercial 2methoxy-8-bromo-quinoline (3) to get compound 9. Intramolecular Friedel-Crafts acylation on the latter was then realized using chlorosulfonic acid [START_REF] Sharma Amutha | Efficient synthesis of halo indanone via chlorosulfonic acid mediated Friedel-Craft cyclisation of aryl propionic acids and their use in alkylation reactions[END_REF] to obtain compound 11.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

96% for 6 and 80% for 7; (d) (i) 6M NaOH, EtOH, rt, (ii) 6M HCl, 93% for 8 and 73% for 9;

(e) CH 3 SO 2 H, 90°C, 70%; (f) ClSO 3 H, 0°C to rt, 84%.

Naphthocyclopentane derivatives 17-19 were synthesized according to the general route outlined in Scheme 2. On one hand, ketone 10 was first cyanated using trimethylsilyl cyanide [START_REF] Fukatsu | Synthesis of a Novel Series of Benzocycloalkene Derivatives as Melatonin Receptor Agonists[END_REF] followed by a dehydration reaction to afford cyanoindene 12. Alkene was then selectively reduced under H 2 atmosphere to give compound 13. The later was C-methylated by action of methyl iodide in the presence of sodium hydride afforded compound 14. On the other hand, a Horner-Emmons olefination [START_REF] Koike | 1,6-Dihydro-2H-indeno[5,4-b]furan derivatives: design, synthesis, and pharmacological characterization of a novel class of highly potent MT₂-selective agonists[END_REF] on ketone 10 with diethyl cyanomethylphosphonate was realized to afford cyanomethylenated compound 15 which was selectively hydrogenated to afford its saturated analogue [START_REF] Guardiola-Lemaitre | Agomelatine: mechanism of action and pharmacological profile in relation to antidepressant properties[END_REF]. Finally, catalytic hydrogenation of cyano derivatives 13, [START_REF] Bodinat | Agomelatine, the first melatonergic antidepressant: Discovery, characterization and development[END_REF]

Pharmacology

Biological Results. Synthesized compounds were assayed at human MT 1 and MT 2 receptors stably transfected in Chinese Hamster Ovarian (CHO) cells, using 2-[ 125 I]iodomelatonin as radioligand [START_REF] Lindberg | Potential local anaesthetics. I. Basic N-(alpha-cycloalkylbenzyl)-acylamides and some related compounds[END_REF]. Serotoninergic 5-HT 2C binding affinity was performed using Chinese

Hamster Ovarian (CHO) cell lines stably expressing the human 5-HT 2C receptors. In Tables 12are depicted the chemical structures, binding affinities and intrinsic activity of the synthesized ligands.

The actual reported work focuses on the design and synthesis of new constrained naphtho-and and quinolinocyclopentane derivatives as dual ligands for melatonin MT 1 /MT 2 and serotonin 5-HT 2C receptor subtypes as successors of agomelatine. This new modulation of the agomelatine structure concerned the inclusion of carbon C2 of the amide lateral chain into a cyclopentane moiety (Chart 1). This free movement restriction of the lateral chain has already been performed as naphthofuranic derivatives and had shown no marked effect at melatonin binding affinity at both MT 1 and MT 2 in comparison with agomelatine [START_REF] Landagaray | Melatonergic ligands: Design, synthesis and pharmacological evaluation of novel series of naphthofuranic derivatives[END_REF]. The same effect was actually observed with synthesized acetamide 17a, however this modulation exhibited a noticeable improvement of the serotoninergic 5-HT 2C binding affinity by a factor 10 (Table 1). This pharmacological effect confirms our previous findings. At this point, we

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT
have no confirmed explanations for such effect and further investigations are in course in order to find out the basis of these results.

Chart 1: Rigidification of Agomelatine

To further investigate the effect of the acetamide function modulation, 17a was considered as a lead compound. Thus, different amides, ureas, thioureas known for their positive effect at both melatonin and serotonin binding affinities were introduced (compounds 17b-17m). The resulted compounds were then tested for their binding affinities at MT 1 , MT 2 and 5-HT 2C . The obtained results are shown in Table 1 and reveal that these modulations had no or a slight effect at both MT 1 and MT 2 receptor subtypes (compare to 17a) except for thioureas 17l and 17m. Indeed, substitution of the acetamide group of 17a with ethyl (17l) or propyl (17m) thiourea led to a loss of two logs at the MT 1 affinity and one log at MT 2 ,

showing a slight MT 2 selectivity. This effect was already reported but we haven't been able to explain the reason yet. In light of the results obtained with acetamide 17a, we also extended the length of the ethyl amide lateral chain from two to three carbons (18a). This extension was

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT
performed to further investigate the role of this lateral chain on the binding affinities especially at 5-HT 2C . However, resulting compound 18a had shown the same profile as 17a with a slight decrease of the binding affinities at both melatonin and serotonin 5-HT 2C receptor subtypes.

To block one of the metabolic site caused by the oxidation of the lateral amide chain observed with agomelatine derivatives, we introduced an angular methyl group attached to carbon-C1 of the naphthocyclopentane ring (19a-g). Indeed, angular methyl groups are known for their resistance to metabolic oxidation, probably due to local steric hindrance. Interestingly, this modulation led to a same good binding affinities at both MT 1 and MT 2 and a loss of the serotoninergic 5-HT 2C binding affinity. Additional investigations are necessary to understand such an effect with this constrained structure. Concerning the introduction of a nitrogen atom through the bioisosteric replacement of naphthalene with quinoline (compound 24a), a similar melatoninergic binding affinity to 17a with a very slight decrease at the at 5-HT 2C binding affinity is observed. Instead, 25a showed an increase in MT 2 binding affinity and a decrease towards 5-HT 2C compared to its quinolic analogue (18a).

Moreover, a pronounced decrease in both MT1 and 5-HT 2C receptors is observed comparing 25a and its inferior homologue (24a).

Table 1. MT 1 and MT 2 binding affinity data of synthesized analogues of melatonin

Compound K i (nM) [I95 ] (n) h-MT 1 h-MT 2 h-5HT 2c
M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT
Finally, replacement of the amide function of 17a by a methylurea (17g) and a methylthiourea (17k) led to the most interesting compounds profiles that we are looking for with a good balance between the melatoninergic and serotoninergic binding affinities.

Compounds 17g and 17k were then submitted to enantiomeric resolution leading to two pairs of compounds: (+)-17g, (-)-17g, (+)-17k and (-)-17k. Evaluation of these four compounds revealed that binding to melatoninergic MT 17m, 19a, 19e, 19f, 19g, 24b and 24c. Evaluation of intrinsic activity of these compounds at 5-HT 2C showed an antagonist activity profile (data not shown).

Table 2. Intrinsic activity of most interesting synthesized compounds. 16 [0.9;2.4] (2) 32 ± 3 (2) 5 [2.9;6.2] (2) 39 ± 3 (2) 17k 8 [6.3;10.5] (2) 52 ± 4 (2) 6 [4.3;8.8] (2) 98 ± 2 (2) (-)-17k 10 [7. 2;9.2] (2) 44 ± 1 (2) 3 [1.4;5.2] (2) 84 ± 5 (2

Cpd. h-MT

1 h-MT 2 EC 50 (nM) [I95] (n) E max (%) ± ESM (n) EC 50 (nM) [I95] (n) E max (%) ± ESM (n) I 1.4 [0.7;2.5] (4) 99 ± 6 (4) 0.18 [0.1;0.39] (3) 91 ± 7 (3) 17a 0.9 [0.9;2.4] (2) 78 ± 1 (2) 0.2 [0.1;0.5] (2) 118 ± 37 (2) 19a 0.2 [0.1;0.4] (2) 79 ± 3 (2) 0.2 [0.09;0.42] (2) 87 ± 3 (2) 17b 5 [3.1;6.4] (2) 81 ± 3 (2) 0.4 [0.1;0.8] (2) 99 ± 2 (2) 24a 0.05 [0.02;0.08] (2) 53 ± 4 (2) - - 17d 4 [2.2;6.8] (2) 30± 1 (2) 1 [0.4;2.8] (2) 63 ± 2 (2) 17e 10000 - 1000 - 17c - - 5 [2.3;7.9] (2) 71 ± 2 (2) 17f 2 [0.7;4.1] (2) 53 ± 3 (2) 0.9 [0.5;1.8] (2) 56 ± 1 (2) 17g 5 [2.9;8.4] (2) 66 ± 4 (2) 3 [1.7;5.4] (2) 95 ± 5 (2) (-)-17g 3
M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 19d 9 [5.3;11.7] (2) 74 ± 1 (2) 0.7 [0.4;1.1] (2) 116 ± 2 (2) 24b 0.2 [0.08;0.5] (2) 42 ± 4 (2) - - 24c 0.9 [0.7;1.4] (2) 35 ± 1 (2) - - 17j

Conclusions

The present work deals with the optimization of a new series of constrained agomelatine analogues. Indeed, constrained structures revealed to be of interest in our case and the inclusion of the ethyl amide side chain into a naphthocyclopentane structure seems to confirm our actual strategy. Obtained acetamide 17a exhibited a very interesting pharmacological profile in comparison to agomelatine. Modulation of the acetamide group of 17a revealed once again that the nature of this group is important to the melatonin binding affinity but critical to the serotonin 5-HT 2C receptor. Among prepared derivatives, methyl urea 17g and methyl thiourea 17k exhibited the most interesting profiles and showed the enantioselective character of the binding affinity at these three receptors. Thus, this enantiomeric separation allows us to describe the levogyre enantiomers (-)-17g and (-)-17k as the highest (MT 1 , MT 2 )/5HT 2C dual ligands found nowadays.

(7-Methoxy-2-naphthyl)trifluoromethanesulfonate (2).

A solution of trifluoromethane sulfonic anhydride (19.92 mL, 120 mmol) in methylene chloride (20 mL) was added dropwise to a stirred solution of 7-methoxy-2-naphthol 1 (17.42 g, 100 mmol) and triethylamine (20.85 mL, 150 mmol) in methylene chloride (320 mL) at -70 °C. The reaction mixture was stirred for 20 min at room temperature, hydrolyzed with water and extracted with methylene chloride. The combined organic layers were washed with water, brine, dried over MgSO 4 , filtered and concentrated under vacuum. The product was obtained quantitatively without further purification as a yellow oil; 1 H NMR (300 MHz, CDCl 3 ) δ: 7.84 1H,9.0 Hz),7.78 (d,1H,9.0 Hz),7.65 (d,1H,2.4 Hz),2H),7.15 (d,1H,2.7 Hz), 3.94 (s, 3H); LC-MS: m/z = 275 (MH + ).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT (d,

Ethyl (E)-3-(7-methoxynaphtalen-2-yl)prop-2-enoate (4).

To a solution of 2 (30.63 g, 100 mmol) in DMF (150 mL) under an inert atmosphere, were added ethyl acrylate (11.97 mL, 110 mmol), bis(triphenylphosphine) palladium chloride (7.72 g, 11 mmol) and triethylamine (15.29 mL, 110 mmol). The reaction mixture was refluxed at 120 °C for 15 h, cooled to room temperature, hydrolyzed with water and then extracted twice with ethyl acetate. The combined organic layers were washed with a 1 M solution of HCl, water and brine, dried over MgSO 4 , filtered and evaporated under reduced pressure. The residue was purified by column chromatography (SiO 2 , cyclohexane/ EtOAc: 7/3) to give 4 (77%) as a white solid; mp 90-92 °C;

Ethyl 3-(7-methoxynaphtalen-2-yl)propanoate (6).

A solution of 4 (10 g, 40 mmol) in 60 mL of ethanol/ methylene chloride (1/1) with palladium 10% on charcoal was stirred under hydrogen atmosphere at room temperature for 6h. The mixture was then filtered and concentrated under reduced pressure. The crude product was recrystallized from petroleum ether to give 6 (96%) as a white solid; mp 82-84 °C; 1 H NMR (300 MHz, CDCl 3 ) δ: 7.72-7.69 (m, 2H), 7.56 (s, 1H), 7.21 (dd, 1H, 8.4 Hz and 1.5

Hz), 7.12-7.09 (m, 2H), 4.15 (q, 2H, 6.9 Hz), 3.93 (s, 3H), 3.10 (t, 2H, 7.5 Hz), 2.71 (t, 2H, 7.5 Hz), 1.24 (t, 3H, 6.9 Hz); IR (υ, cm -1 ): 1720 (CO); LC-MS: m/z = 259 (MH + ).

3-(7-Methoxynaphtalen-2-yl)propionic acid (8).

Compound 6 (9 g, 34.85 mmol) was dissolved in ethanol (40 mL), followed by the addition of 6M solution of NaOH (40 mL). The reaction mixture was stirred at room

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

(8-Methoxy-3H-cyclopenta[a]naphthalen-1-yl)carbonitrile (12).

Step

(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)carbonitrile (13).

A solution of 12 (1.10 g, 5 mmol) in 60 mL of ethanol/dichloromethane (1/2) with palladium 10% on charcoal was stirred under hydrogen atmosphere at room temperature for 6 h. The mixture was filtered, concentrated under reduced pressure. The crude product was recrystallized from toluene to give 13 (72%) as a white solid; mp 103-105 °C;

(8-Methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphtalen-1-yl)carbonitrile (14).

To a solution of 13 (0.86 g, 3.85 mmol) in DMF (30 mL) under argon atmosphere was added at 0 °C sodium hydride (185 mg, 7.7 mmol). The mixture was stirred at 0 °C during 15 min, then methyl iodide (820 mg, 5.78 mmol) was added and stirring was continued for additional 45 min. The mixture was hydrolyzed with water and extracted with ethyl acetate.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

The organic layer was washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure. The residue was purified by flash chromatography (SiO 2 , cyclohexane/EtOAc: 5/5) and recrystallized from cyclohexane to afford 14 (91%) as a white solid; mp 95-97 °C;

(E)-Ethyl-3-(2-methoxyquinolin-7-yl)prop-2-enoate (5).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

This product was obtained from commercially 7-bromo-2-methoxyquinoline (3) as described for compound (4). The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) to afford 5 (93%) as a white solid; mp 105-107 °C; 144.3, 138.2, 135.5, 128.1, 128.0, 126.1, 122.3, 119.4, 114.1, 60.6, 53.5, 14.3; IR (υ, cm -1 ) : 1700 (C=O); LC-MS : m/z = 258 (MH + ).

Ethyl 3-(2-methoxyquinolin-7-yl)propanoate (7).

This product was obtained from 5 as described for compound 6. 8, 146.2, 140.3, 137.2, 128.8, 128.1, 126.3, 122.3, 113.4, 61.6, 53.6, 34.1, 30.5, 14.3; IR (υ, cm -1 ): 1715 (CO); LC-MS: m/z = 260 (MH + ).

3-(2-Methoxyquinolin-7-yl)propanoic acid (9).

This product was obtained from 7 as described for compound (8). The crude product was purified by flash chromatography (DCM/MeOH : 9/1) to afford 9 (73%) as a white solid; mp 185-187 °C; 162.2, 146.1, 139.3, 136.2, 128.8, 127.5, 126.7, 121.6, 112.4, 53.2, 35.1, 30.4; IR (υ, cm -1 ): 1695 (C=O); LC-MS : m/z = 232 (MH + ).

4. quinolin-9-one (11).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

Chlorosulfonic acid (20 mL) was added dropwise at 0 °C to acid 9 (2.31 g, 1 mmol).

Stirring was maintained for 24 h at room temperature, and then the mixture was poured into ice and extracted twice with diethyl ether. The combined organic layers were washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure.

2-(2-Methoxy-8,9-dihydro-7H-cyclopenta[h]quinolin-9-yl)acetonitrile (21).

Dry THF (5 mL) was added at -10 °C to sodium hydride 60% (0.88 g, 22 mmol) under argon. A solution of diethyl cyanomethylphosphonate (7.1 mL, 44 mmol) in dry THF (10 mL)

was then added dropwise. The mixture was stirred under argon until precipitation of the ylure and the solution of compound 11 (2.13 g, 10.0 mmol) in THF (10 mL) was added dropwise.

The mixture was stirred for 16 h, and then hydrolyzed with water. The formed solid was filtered, dried and used without further purification for the next step. A solution of this crude product in 60 mL of ethanol/dichloromethane (1/2) was stirred with palladium 10% on charcoal under hydrogen atmosphere at room temperature for 6 h. The mixture was filtered and concentrated under reduced pressure. The crude product was purified by flash chromatography (cyclohexane/EtOAc: 9/1) to afford 21 (55%) as a white solid; mp 66-67 °C; 1, 155.4, 138.5, 137.2, 132.7, 127.6, 125.2, 122.1, 117.1, 111.2, 53.8, 36.1, 31.2, 30.7, 24.6; IR (υ, cm -1 ): 2225 (CN); LC-MS: m/z = 239 (MH + ).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

2-(2-Methoxy-8,9-dihydro-7H-cyclopenta[h]quinolin-9-yl)acetic acid (22).

Compound 21 (1.2 g, 5 mmol) was dissolved in ethanol (20 mL), followed by the addition of 6M solution of NaOH (10 mL). The reaction mixture was refluxed during 24 h.

After cooling to room temperature, water was added and the solution was extracted twice with diethyl ether. The aqueous solution was acidified with a 6M solution of HCl. 145.6, 143.2, 139.8, 139.3, 127.0, 124. 0, 121.3, 111.6, 53.5 40.64, 38.8, 32.1, 31.5; IR (υ, cm - 1 ): 1680 (C=O); LC-MS: m/z = 258 (MH + ).

(2-Methoxy-8,9-dihydro-7H-cyclopenta[h]quinolin-9-yl)methylamine hydrochloride (24).

To a solution of 22 (0.5 g, 2 mmol) in THF (20 mL) was added at 0 °C triethylamine (0.42 mL, 3 mmol) and ethyl chloroformate (0.28 mL, 3 mmol). After 1 h stirring, sodium azide (195 mg, 3 mmol) was added at 0 °C and the reaction mixture was stirred for an additional 2 h. The mixture was hydrolyzed with water and extracted with CH 2 Cl 2 . The organic layer was washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure at cold condition. The crude product [START_REF] Sharma Amutha | Efficient synthesis of halo indanone via chlorosulfonic acid mediated Friedel-Craft cyclisation of aryl propionic acids and their use in alkylation reactions[END_REF] was dissolved in THF (10 mL), followed by the addition of 1 M solution of NaOH (5 mL). The reaction mixture was refluxed during 2 h. A solution of 1 M HCl was added and the reaction mixture was extracted twice with diethyl ether. The aqueous phase was then basified with 2 M solution of NaOH and extracted with diethyl ether. The organic layer was dried over MgSO 4 , filtered and treated with gaseous HCl. The obtained solid was filtered to give 24 (66%) as a white solid; mp 218-220 °C; 2, 145.4, 143.2, 139.9, 139.3, 127.0, 124.1, 121.0, 111.0, 52.5 40.6, 38.4, 32.1, 31.6, 30.9; IR (υ, cm -1 ) : 3200-2820 (NH 3+ Cl -); LC-MS : m/z = 243 (MH + ).

4.23.

General procedure for synthesis of amides 17a-b, 18a, 19a, 24a, 25a and carbamate 17c.

To a solution of corresponding amine 17, 19, 24, 25 (2 mmol) in EtOAc (30 mL) and water (10 mL) were added K 2 CO 3 (4 mmol) and the corresponding acid chloride (2.2 mmol) at 0 °C. The mixture was stirred at room temperature during 2 h and the layers were separated. The organic layer was washed with 1 M solution of HCl, water, dried over MgSO 4 , filtered and concentrated under reduced pressure.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

4. naphthalen-1-yl)methyl]acetamide (17a).

The crude product was recrystallized from toluene to afford 17a (86%) as a white solid; mp 130-132 °C; 1, 158.0, 141.5, 139.2, 131.4, 130.4, 128.2, 127.5, 121.3, 117.6, 103.3, 55.7, 44.7, 42.0, 31.5, 29.3, 23.2 naphthalen-1-yl)ethyl]acetamide (18a).

The crude product was recrystallized from toluene to afford 18a (76%) as a white solid; mp 141-142 °C; 141.5, 139.2, 131.4, 130.4, 128.2, 127.5, 121.3, 117.6, 103.3, 54.0, 46.2, 43.0, 33.5, 32.5, 30.8, 23.4

N-[(8-Methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl] acetamide (19a).

The crude product was recrystallized from cyclohexane to afford 19a (80%) as a white solid; mp 84-86 °C; 157.6, 142.1, 140.2, 131.4, 129.5, 128.2, 128.0, 121.3, 117.3, 102.9, 55.6, 47.0, 45.2, 38.5, 29.8, 24.9, 23.2 quinolin-9-yl)methyl]acetamide (24a).

The crude product was recrystallized from toluene to afford 24a (85%) as a white solid; mp 110-111 °C; 1, 162.4, 146.6, 143.5, 139.9, 139.8, 127.2, 124.0, 121.8, 111.7, 53.5, 45.0, 42.4, 32.2, 30.6, 23.2 quinolin-9-yl)ethyl]acetamide (25a).

The crude product was recrystallized from toluene to afford 25a (84%) as a white solid; mp 119-120 °C; 170.5, 161.4, 145.6, 142.5, 139.8, 139.2, 127.2, 124.2, 122.4, 111.5, 53.5, 45.0, 42.4, 32.2, 31.5, 30.6, 23.2 4. naphtalen-1-yl)methyl] acetamide (17b).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

The crude product was purified by flash chromatography (cyclohexane / EtOAc : 5/5) and recrystallized from toluene to afford 17b (73%) as a white solid; mp 103-104 °C; 1 H NMR (300 MHz, CDCl 3 ) δ: 7.72 (d,1H,8.9 Hz),7.66 (d,1H,8.5 Hz),7.40 (d,1H,2.4 Hz),7.26 (d,1H,8.5 Hz),7.11 (dd,1H,[START_REF] Koyama | Ubiquitin proteasome system and the atypical kinase PfPK7 are involved in melatonin signaling in Plasmodium falciparum[END_REF].9 Hz and 2.4 Hz), 6.76 (br s, 1H), 4.00 (s, 3H), 3.94-3.86 (m, 4H), 3.38 (s, 3H), 3. 24-3.15 (m, 2H), 3.00 (m, 1H), 2.35 (m, 1H), 2.13 (m, 1H); 13 C NMR (75 MHz, CDCl 3 ) δ: 169.9, 158. 1, 141.6, 138.0, 131.3, 130.0, 128.2, 127.6, 120.8, 117.5, 102.5, 72.0, 59.1, 55.4, 44.0, 41.8, 31.7, 29.3 naphthalen-1-yl)methyl] carbamate (17c).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 17c (88%) as a white solid; mp 76-78 °C; 157.6, 141.6, 139.0, 131.4, 130.4, 128.2, 127.6, 121.3, 117.5, 103.1, 55.6, 51.8, 44.9, 43.4, 31.4, 29.0 were added at 0 °C triethylamine (0.70 mL, 5 mmol) and the corresponding alkyl sulfonyl chloride (2.6 mmol). The mixture was stirred at room temperature for 2 h and hydrolyzed with

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT
water. The organic layer was washed with 1 M solution of HCl, water, dried over MgSO 4 , filtered and concentrated under reduced pressure.

4.32.

N-[ naphthalen-1-yl)methyl]methansulfonamide (17d).

The crude product was treated with diisopropyl ether and recrystallized from cyclohexane to afford 17d (70%) as a white solid; mp 110-112 °C; 142.0, 138.5, 131.2, 130.5, 128.2, 127.8, 121.4, 117.6, 103.0, 55.6, 45.4, 45.3, 40.1, 31.5, 28.9; IR (υ, cm -

N-[(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]ethansulfonamide (17e).

The crude product was recrystallized from cyclohexane to afford 17e (70%) as a white solid; mp 109-110 °C; 142.0, 138.5, 131.2, 130.5, 128.2, 127.8, 121.4, 117.6, 103.0, 55.6, 46.1, 45.6, 45.3, 31.4, 28.8, 8.6; IR (υ, cm -1 ): 3298 naphtalen-1-yl)methyl]methane sulfonamide (19b).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

The crude product was recrystallized from cyclohexane to afford 19b (50%) as a white solid; mp 98-100 °C; 1 H NMR (300 MHz, DMSO-d 6 ) δ: 7.82 (d,1H,9.0 Hz),7.68 (d,1H,8.1 Hz),7.39 (d,1H,1.8 Hz),7.21 (d,1H,8.1 Hz),7.11 (dd,1H,9.0 Hz and 1.8 Hz),7.03 (t, 1H, 6.9 Hz), 3.88 (s, 3H), 3.42 (dd, 1H, 13.2 Hz and 6.9 Hz),3.26 (dd, 1H, 13.2 Hz and 6.9 Hz), 157.4, 142.7, 140.8, 131.3, 131.0, 129.0, 128.3, 121.6, 116.9, 103.1, 55.4, 50.5, 50.2, 39.8, 38.1, 30.6, 25.0; IR (υ, cm -1 ) : 3297 (NH); MS (APCI, pos. 30 V) m/z: [M+H] + , 320.24. HRMS (ESI + ): m/z = calcd. for C 17 H 22 NO 3 S [M+H] + 320.12328 found: 320.12247.

4.35

. N 1 -[(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]urea (17f).

To a solution of amine 17 (0.45 g, 2 mmol) in water (10 mL) and 1 M solution of HCl (1 mL) was added potassium cyanate (0.2 g, 2.5 mmol). The mixture was stirred at room temperature during 24 h). The solid was filtered, washed with water and recrystallized from acetonitrile to afford 17f (84%) as a white solid; mp 173-175 °C; 160.5, 155.7, 141.1, 138.5, 130.5, 130.0, 127.1, 128.5, 121.4, 118.2, 102.5, 55.8, 46.2, 44.2, 31.4, 29.1; IR (υ, cm - 4.36. N 1 -[(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]-N 3 -methyl-urea (17g).

To a solution of amine 17 (1.93 g, 8.49 mmol) in DMSO (50 mL) were added triethylamine (1.77 mL, 12.74 mmol) and then N-methylphenylcarbamate (1.92 g, 12.74 mmol). The mixture was stirred at 60 °C during 3 h then, hydrolyzed and extracted with ethyl 159.5, 157.9, 141.6, 139.5, 131.5, 130.3, 128.2, 127.4, 121.3, 117.5, 103.5, 55.6, 45.3, 42.8, 31.6, 29.2, 26.9; IR (υ, cm

M A N U S C R I P T A C C E P T E D

4.38.

N 1 -Ethyl-N 3 -[(8-methoxy-2,3-dihydro-1H-cyclopenta[a]naphtalen-1-yl)methyl]urea (17h).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 17h (57%) as a white solid; mp 148-150 °C; 141.6, 139.5, 131.5, 130.3, 128.2, 127.4, 121.3, 117.5, 103.6, 55.6, 45.3, 42.7, 34.6, 31.6, 29.2, 16.2

4.39.

N 1 -[(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphtalen-1-yl)methyl]-N 3 -propylurea (17i).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 17i (77%) as a white solid; mp 139-141 °C; 158.8, 158.0, 141.8, 139.3, 131.7, 130.3, 128.2, 127.5, 121.3, 117.8, 103.8, 56.0, 46.2, 45.6, 44.0, 31.4, 28.8, 22.5, 11.9; IR (υ, cm -

4.40.

N 1 -Ethyl-N 3 -[(8-methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl) methyl]urea (19c).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 19c (67%) as a white solid; mp 143-145 °C; 8, 157.4, 142.6, 141.2, 131.4, 131.0, 129.0, 128.0, 121.6, 116.9, 102.9, 55.5, 47.1, 45.9, 38.2, 34.5, 30.7, 24.9, 16.1; IR (υ, cm -1

4.41.

N 1 -[(8-Methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]-N 3 propylurea (19d).

The crude product was recrystallized from toluene to afford 19d (70%) as a white solid; mp 115-117 °C; 158.9, 157.4, 142.6, 141.1, 131.3, 131.0, 129.0, 128.0, 121.6, 116.9, 102.9, 55.5, 51.4, 47.2, 41.5, 38.1, 30.7, 24.9, 23.6, 16.1; IR (υ, cm -1 4.42. N 1 -[(8-methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]-N 3 -methyl-thiourea (17k).

The crude product was purified by flash chromatography(cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 17k (87%) as a white solid; mp 159-161 °C; 183.6, 158.0, 141.8, 139.3, 131.7, 130.3, 128.2, 127.5, 121.3, 117.8, 103.9, 56.0, 46.4, 44.0, 31.4, 30.8, 28.8 N 1 -Ethyl-N 3 -[(8-methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]thiourea (17l).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 17l (64%) as a white solid; mp 200-202 °C; 182.6, 158.0, 141.8, 139.3, 131.7, 130.3, 128.2, 127.5, 121.3, 117.8, 103.8, 56.0, 46.2, 44.0, 38.5, 31.4, 28.8, 14.9; IR (υ, cm 1, 158.0, 141.8, 139.3, 131.7, 130.3, 128.2, 127.5, 121.3, 117.8, 103.8, 56.0, 46.2, 45.6, 44.0, 31.4, 28.8, 22.5, 11.9

4.45.

N 1 -Methyl-N 3 -[(8-methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl) methyl]thiourea (19e).

The crude product was recrystallized from toluene to afford 19e (57%) as a white solid; mp 144-146 °C; 142.5, 140.9, 131.3, 131.0, 129.0, 128.2, 121.6, 117.2, 102.8, 55.6, 51.3, 51.1, 38.2, 31.0, 30.6, 24.7 183.7, 157.5, 142.6, 140.8, 131.3, 131.0, 129.0, 128.2, 121.6, 117.2, 102.7, 55.6, 51.2, 51.0, 38.8, 38.2, 30.7, 24.8, 14.8

4.47.

N 1 -[(8-Methoxy-1-methyl-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methyl]-N 3propylthiourea (19g).

The crude product was recrystallized from toluene to afford 19g (41%) as a white solid; mp 109-111 °C; 182.6, 157.5, 142.6, 140.8, 131.3, 131.0, 129.0, 128.3, 121.6, 117.2, 102.7, 55.6, 51.2, 51.1, 45.4, 38.2, 30.7, 24. naphthalen-1-yl)methylthiourea (17j).

To a solution of 17 (0.50 g, 2,20 mmol) in a mixture of dioxane/THF (6/1) (35 mL) was added 12 M HCl (0. 157.7, 141.6, 139.5, 131.7, 130.0, 128.1, 127.5, 121.3, 118.0, 102.1, 55.9, 46.3, 44.1, 31.3, 28.8

4.49.

N 1 -[(2-Methoxy-8,9-dihydro-7H-cyclopenta[h]quinolin-9-yl)methyl]-N 3 -methylurea (24b).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 24b (55%) as a white solid; mp 142-143 °C; 2, 146.6, 143.5, 139.67, 139.5, 127.2, 123.9, 121.6, 111.7, 53.6, 45.2, 43.6, 42.2, 32.3, 30.2, 27

4.50.

N 1 -[(2-Methoxy-8,9-dihydro-7H-cyclopenta[h]quinolin-9-yl)methyl]-N 3 -propylurea (24c).

The crude product was purified by flash chromatography (cyclohexane/EtOAc : 5/5) and recrystallized from toluene to afford 24c (78%) as a white solid; mp 167-168 °C; 162.4, 158.5, 146.6, 143.6, 139.5 (2C), 127.2, 123.9, 121.6, 111.7, 53.6, 45.2, 43.6, 42.2, 32.3, 30.2, 23.4, 11.2; IR (υ, cm - Aliquots of membrane preparations were stored at -80 °C until use.

Binding Assays.

2-[ 125 I]iodomelatonin binding assay conditions were essentially as previously described [27]. Briefly, binding was initiated by addition of membrane preparations from stable , where [L] is the concentration of radioligand used in the assay and K D , the dissociation constant of the radioligand characterising the membrane preparation [START_REF] Cheng | Relationship between the inhibition constant (K1) and the concentration of inhibitor which causes 50 per cent inhibition (I50) of an enzymatic reaction[END_REF].

[ 35 S] GTPγS binding assay was performed according to published methodology [27].

Briefly, membranes from transfected CHO cells expressing MT 1 or MT 2 receptor subtype and compounds were diluted in binding buffer (20 mM HEPES,pH 7.4, 100 mM NaCl, 3 µM GDP, 3 mM MgCl 2, and 20 µg/mL saponin). Incubation was started by the addition of 0.2 nM Serotonin 5-HT 2C binding assay was determined according to reported tests [START_REF] Westphal | Reciprocal binding properties of 5hydroxytryptamine type 2C receptor agonists and inverse agonists[END_REF]. First

Figure 1 .

 1 Figure 1. Melatonin, Agomelatine and its quinolinic analogue.

  Scheme 2 a . Synthesis of primary amines 17-19. a Reagents and conditions: a) (i) Trimethylsilyl cyanide, zinc iodide, CH 2 Cl 2 , rt (ii) Acetyl chloride, acetic acid, rt, 83%; b) Pd/C, H 2 , CH 2 Cl 2 /EtOH, rt, 72%; c) CH 3 I, NaH, DMF, 0 °C to rt, 91%; d) NaH, diethyl cyanomethylphosphonate, THF, -10 °C to rt, 50%; e) Raney Ni, H 2 , EtOH, 50 bars, 60°C, 79% for 17, 93% for 18 and 30% for 19.

  were obtained from commercial sources, and used without further purification unless otherwise noted. Reactions were monitored by TLC performed on Macherey-Nagel Alugram ® Sil 60/UV 254 sheets (thickness 0.2 mm). Purification of products was carried out by recrystallization or column chromatography. Column chromatography was carried out using Macherey-Nagel silica gel (230-400 mesh). Melting points were determined on a Büchi SMP-20 capillary apparatus and are uncorrected. FT-IR spectra were recorded on a Thermo Nicolet Avatar 320 FT-IR spectrometer. NMR spectra were recorded on a Bruker DRX 300 spectrometer (operating at 300 MHz for 1 H and 75 MHz for 13 C). Chemical shifts are expressed in ppm relative to either tetramethylsilane (TMS). Chemical shifts are reported as position (δ in ppm), multiplicity (s = singlet, d = doublet, t = triplet, q = quartet, p = pentet, dd = double doublet, br = broad and m = multiplet), coupling constant (J in Hz), relative integral and assignment. Mass spectra were recorded on a Varian triple quadrupole 1200W mass spectrometer equipped with a non-polar C18 TSK-gel Super ODS (4.6 × 50 mm) column, using electrospray ionization and a UV detector (diode array). HRMS-ESI spectra were recorded on a Thermo Scientific Exactive spectrometer.

  1 ) : 3294 (NH); LC-MS : m/z = 306 (MH + ). MS (APCI, pos. 30 V) m/z: [M+H] + , 306.27. HRMS (ESI + ): m/z = calcd. for C 16 H 20 NO 3 S [M+H] + 306.14312 found: 306.14372.

(

  NH); MS (APCI, pos. 30 V) m/z: [M+H] + , 320.27. HRMS (ESI + ): m/z = calcd. for C 17 H 22 NO 3 S [M+H] + 320.15232 found: 320.15254.

  1 ): 3425 (NH 2 ), 3340 (NH), 1625 (C=O); MS (APCI, pos. 30 V) m/z: [M+H] + , 271.23. HRMS (ESI + ): m/z = calcd. for C 16 H 19 N 2 O 2 [M+H] + 271.12418 found: 320.12357.

  1 ) : 3294 (NH), 1623 (C=O); MS (APCI, pos. 30 V) m/z: [M+H] + , 313.25. HRMS (ESI + ): m/z = calcd. for C 19 H 25 N 2 O 2 [M+H] + 313.18377 found: 313.18334.

  1 ): 3325 (NH), 1613 (C=O); MS (APCI, pos. 30 V) m/z: [M+H] + , 314.35. HRMS (ESI + ): m/z = calcd. for C 18 H 24 N 3 O 2 [M+H] + 313.17902 found 313.17743.5. Pharmacological methods5.1. Reagents and Chemicals.2-[ 125 I]-Iodomelatonin (2200 Ci/mmol) was purchased from NEN (Boston, MA). Other drugs and chemicals were purchased from Sigma-Aldrich (Saint Quentin, France).5.2. Cell Culture.HEK (provided by A.D. Strosberg, Paris, France) and CHO cell lines stably expressing the human melatonin MT 1 or MT 2 receptors were grown in DMEM medium supplemented with 10% fetal calf serum, 2 mM glutamine, 100 IU/mL penicillin and 100 µg/ml streptomycin. Grown at confluence at 37 °C (95%O 2 /5%CO 2 ), they were harvested in PBS containing EDTA 2 mM and centrifuged at 1000 x g for 5 min (4 °C). The resulting pellet was suspended in TRIS 5 mM (pH 7.5), containing EDTA 2 mM and homogenized using a The homogenate was then centrifuged (95 000g, 30 min, 4 °C) and the resulting pellet suspended in 75 mM TRIS (pH 7.5), 12.5 mM MgCl 2 and 2 mM EDTA.

  transfected HEK or CHO cells diluted in binding buffer (50 mM Tris-HCl buffer, pH 7.4 containing 5 mM MgCl 2 ) to 2-[ 125 I]-iodomelatonin (25 or 200 pM for MT 1 and MT 2 receptors, respectively, expressed in HEK cells or 20 pM for MT 1 and MT 2 receptors expressed in CHO cells) and the tested drug. Nonspecific binding was defined in the presence of 1 µM melatonin. After 120 min incubation at 37 °C, reaction was stopped by rapid filtration through GF/B filters presoaked in 0.5% (v/v) polyethylenimine. Filters were washed three times with 1 ml of ice-cold 50 mM Tris-HCl buffer, pH 7.4. Data from the dose-response curves (7 concentrations in duplicate) were analysed using PRISM program (Graph Pad Software Inc., San Diego, CA) to yield IC 50 (inhibitory concentration 50). Results are expressed as K i = IC 50 / 1 + ([L]/K D )

[

  35 S]GTPγS to membranes (20 µg/ml) and drugs, and further followed for 1 h at room temperature. For experiments with antagonists, membranes were pre-incubated with both the melatonin (3 nM) and the antagonist for 30 min prior the addition of [ 35 S]GTPγS. Non defined using cold GTPγS (10 µM). Reaction was stopped by rapid filtration through GF/B filters followed by three successive washes with ice cold buffer.Usual levels of [35 S]GTPγs binding (expressed in dpm) were for CHO-MT 1 or MT 2 membranes: 2000 for basal activity, 8000 in the presence of melatonin 1 µM and 180 in the presence of GTPγS 10 µM which defined the non specific binding. Data from the doseresponse curves (7 concentrations in duplicate) were analyzed by using the program PRISM (Graph Pad Software Inc., San Diego, CA) to yield EC 50 (Effective concentration 50 %) and E max (maximal effect) for agonists. Antagonist potencies are expressed as K B = IC 50 / 1 + ([Ago]/EC 50 ago), where IC 50 is the inhibitory concentration of antagonist that gives 50% inhibition of [ 35 S] GTPγS binding in the presence of a fixed concentration of melatonin ([Ago]) and EC 50 ago is the EC 50 of the molecule when tested alone. I max (maximal inhibitory effect) was expressed as a percentage of that observed with melatonin at 3 nM for MT 2 receptor.

  incubation of 200 µl solution from membrane CHO cell lines, stably expressing the human 5-HT 2C receptors, for 60 min at 37 °C in binding buffer (50 mM Tris-HCl buffer, pH 7.4, containing 10 mM MgCl 2 and 0.1% BSA) containing the radioligand [ 3 H]-mesulergine (1 nM). Non-specific binding was defined in the presence of 10 µM mianserine. Dose-response curves are obtained by displacement of the radioligand. Reaction was stopped by rapid filtration through GF/B filters presoaked in 0.1% (v/v) polyethylenimine. Filters were washed three times with 1 mL of ice-cold 50 mM Tris-HCl buffer, pH 7.4. Residual radioactivity was revealed by addition of Microscint 20 and measured by using TopCount calculator (Packard).IC 50 was determined from dose-response curves and results are expressed as K i = IC 50 /1 + ([L]/KD), where[L] is the concentration of radioligand used in the assay and KD, the dissociation constant of the radioligand characterising the membrane preparation.

17b, 17h, 17g, 17i, 17k, 19c, 19d and (-)-17g. A

  second group with an MT 1 /MT 2 partial agonist profile was reported and includes compounds

			ACCEPTED MANUSCRIPT
	25a enantioselective. Indeed, levogyre enantiomers (-)-17g and (-)-17k were more potent than 5 [4.3 ; 6.2] (2) 0.8 [0.65; 1.1] (2) 1600
	Carbamate their dextrogyre counterpart and their mixtures (Table 1). These two compounds represent the 17c 2 [0.9 ; 2.3] (2) 0.4 [0.1; 0.7] (2) 100 [83 ; 133] (2)
	Sulfon-	17d	0.8 [0.2 ; 1.3] (2)	0.1 [0.07; 0.4] (2)	580 [437 ; 723] (2)
	19b most interesting dual ligands for described nowadays. However, further investigations are 0.6 [0.3 ; 1.1] (2) 0.2 [0.09; 0.4] (2) >10000 amides 17e 7 [4.3 ; 9.2] (2) 0.4 [0.1; 0.6] (2) 400 [277 ; 578] (2) needed in order to determine the enantioselectivity effect on the ADME properties. Intrinsic
	Ureas activity evaluation for all compounds towards melatonin MT 1 and MT 2 receptors was 17f 0.3 [0.1 ; 0.5] (2) 0.1 [0.08; 0.4] (2) 145 [97 ; 223] (2) 17g 0.6 [0.5 ; 0.8] (2) 0.2 [0.07; 0.5] (2) 170 [135 ; 217] (2) (+)-17g 32 [28 ; 41] (2) 970 [734; 1120] (2) >10000 (-)-17g 0.4 [0.1 ; 0.9] (2) 0.07 [0.02; 0.1] (2) 15 [7 ; 26] (2) 17h 2 [1 ; 2.7] (2) 0.1 [0.07; 0.3] (2) 60 [53; 69] (2) 17i 5 [3.5 ; 6.2] (2) 0.2 [0.1; 0.5] (2) 190 [123 ; 218] (2) 19c 0.8 [0.6 ; 1.3] (2) 0.3 [0.1; 0.5] (2) >10000 19d 2 [1.1 ; 3.7] (2) 0.2 [0.09; 0.4] (2) >10000 24b 1 [0.7 ; 1.6] (2) 0.2 [0.11; 0.3] (2) 340 [297 ; 394] (2) 24c 7 [5.2 ; 9.3] (2) 0.4 [0.2; 0.7] (2) 285 [207 ; 410] (2) 17j 6 [4.7 ; 8.3] (2) 0.4 [0.1; 0.9] (2) 72 [43 ; 117] (2) 17k 4 [2.7 ; 7.1] (2) 0.3 [0.1; 0.7] (2) 30 [18 ; 54] (2) (+)-17k 99 [43 ; 127] (2) 9 [2; 14] (2) >10000 M performed and the results are depicted in Table 2. In general, two intrinsic activity profiles were observed. A first group with MT 1 /MT 2 partial agonist/full agonist profile including A N U S C R I P T compounds 17a,
	Thioureas A C C E P T E D (-)-17k 3 [1.6 ; 4.2] (2) 17l 29 [15 ; 47] (2) 17m 63 [48 ; 79] (2) 19e 1 [0.3 ; 2.5] (2) 19f 4 [2.1 ; 6.2] (2) 19g 9 [6.2 ; 13] (2)	0.1 [0.08; 0.17] (2) 2 [1.1; 3.1] (2) 3 [1.6; 5.1] (2) 0.2 [0.1; 0.4] (2) 3 [1.3; 5.7] (2) 0.3 [0.1; 0.7] (2)	9 [3 ; 11] (2) 8 [3 ; 16] (2) 42 [23 ; 75] (2) >10000 >10000 >10000
			1 , MT 2 and serotoninergic 5-HT 2C receptors is

17c, 17d, 17f, 17j, 17l,

  temperature, for 3 h, hydrolyzed with a 2 M solution of HCl and extracted twice with methylene chloride. The combined organic layers were washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure. The crude product was

	recrystallized from methanol to afford 8 (93%) as a white solid; mp 175-177 °C; 1 H NMR
	(300 MHz, CDCl 3 ) δ: 10.2 (br s, 1H), 7.73-7.70 (m, 2H), 7.57 (s, 1H), 7.21 (dd, 1H, 8.4 Hz
	and 1.8 Hz), 7.13-7.10 (m, 2H), 3.93 (s, 3H), 3.12 (t, 2H, 7.5 Hz), 2.79 (t, 2H, 7.5 Hz); IR (υ,
	cm -1 ): 2833 (OH), 1694 (CO); LC-MS: m/z = 231 (MH + ).
	4.6. 8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-one (10).

Methanesulfonic acid

(20 mL)

was added dropwise to the acid 8 (6.20 g, 26.90 mmol).

Stirring was maintained for 2 h at 90 °C, and then the mixture was poured into water and extracted twice with diethyl ether. The combined organic phases were washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure. The residue was recrystallized from acetonitrile to afford 10 (70%) as a white solid; mp 122-124 °C; 1 H NMR (300 MHz, CDCl 3 ) δ:

8.60 (d, 1H, 2.4 Hz), 7.97 (d, 1H, 8.4 Hz), 7.79 (d, 1H, 9.0 Hz), 7.38 (d, 1H, 8.4 Hz), 7.20 (dd, 1H, 9

.0 Hz and 2.4 Hz), 4.00 (s, 3H), 3.

23-3.20 (m, 2H), 2.83-2.79 (m, 2H)

; IR (υ, cm -1 ): 1681 (CO); LC-MS: m/z = 213 (MH + ).

  An NH 3 -saturated solution of 13 (1.12 g, 5 mmol) in 60 mL of ethanol was hydrogenated over Raney nickel under pressure (50 bars) at 60 °C for 16 h. After filtration and evaporation of ethanol, the oil was dissolved in ether, washed with water, dried over MgSO 4 and treated with gaseous HCl. The obtained solid was filtered to give 17 (79%) as a

	ACCEPTED MANUSCRIPT
	4.12. 8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)methylamine hydrochloride
	(17).
	1 H NMR (300 MHz, CDCl 3 ) δ: 7.79 (d, 1H, 9.0 Hz),7.74 (d, 1H, 8.1
	Hz),7.54 (d, 1H, 2.4 Hz), 7.22 (d, 1H, 8.1 Hz), 7.15 (dd, 1H, 9.0 Hz and 2.4 Hz), 3.99 (s, 3H), 3.22-3.10 (m, 2H), 2.85 (m, 1H), 2.45 (m, 1H), 1.78 (s, 3H); IR (υ, cm -1 ): 2231 (CN); LC-MS: m/z = 238 (MH + ). 4.10. 2-(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-ylidene)acetonitrile (15). This compound was obtained from 15 in 75% yield as described for 13; mp 82-84 °C (methanol); 1 H NMR (300 MHz, CDCl 3 ) δ: 7.79 (d, 1H, 9.0 Hz), 7.69 (d, 1H, 8.1 Hz), 7.27 M white solid; mp 247-248 °C; 1 H NMR (300 MHz, CDCl 3 ) δ: 8.42 (br s, 3H), 7.82 (d, 1H, 9.0 Hz), 7.70 (d, 1H, 8.20 Hz), 7.25 (d, 1H, 8.20 Hz), 7.18 (d, 1H, 2.4 Hz), 7.10 (dd, 1H, 9.0 Hz and 2.4 Hz), 3.99 (m, 1H), 3.93 (s, 3H), 3.15-3.06 (m, 2H), 2.92 (m, 1H), 2.72 (m, 1H) , 2.39 A N U S C R I P T (m, 1H) , 2.18 (m, 1H); IR (υ, cm -1 ) : 3200-2800 (NH 3 + Cl Amine 18 was obtained from 16 in 65% yield as described for compound 17; 1 H NMR (300 MHz, CDCl 3 ) δ: 8.52 (br s, 2H), 7.75 (d, 1H, 8.7 Hz), 7.61 (d, 1H, 8.1 Hz), 7.24 (d, 1H, 8.1 Hz), 7.20 (d, 1H, 2.4 Hz), 7.08 (dd, 1H, 8.7 Hz and 2.4 Hz), 3.93 (s, 3H), 3.76 (m, 1H), 3.41-2.85 (m, 6H), 2.42-2.07 (m, 2H); LC-MS: m/z = 242 (MH + ). Amine 19 was obtained from 14 in 93% yield as described for compound 17; mp 70-72 °C; 1 H NMR (300 MHz, CDCl 3 ) δ: 8.42 (br s, 2H), 7.76 (d, 1H, 9.0 Hz),7.62 (d, 1H, 8.2 Hz), A C C E P T E D 7.40 (d, 1H, 2.4 Hz), 7.21 (d, 1H, 8.2 Hz), 7.09 (dd, 1H, 9.0 Hz and 2.4 Hz), 3.93 (s, 3H),
	(d, 1H, 8.1 Hz), 7.13 (dd, 1H, 9.0 Hz and 2.4 Hz), 7.02 (d, 1H, 2.4 Hz), 4.01 (m, 1H), 3.96 (s, 3.11-2.98 (m, 4H), 2.34 (m, 1H), 1.97 (m, 1H), 1.54 (s, 3H); IR (υ, cm -1 ): 3290 (NH 2 ); LC-
	3H), 3.29 (m, 1H), 3.06 (m, 1H), 2.83 (m, 1H), 2.61-2.45 (m, 2H), 2.31 (m, 1H); IR (υ, cm -1 ): MS: m/z = 242 (MH + ).

Dry THF (5 mL) was added at -10 °C to sodium hydride 60%

(1.8 g, 4.

4 mmol) under argon. A solution of diethyl cyanomethylphosphonate (7.1 mL, 44 mmol) in dry THF (10 mL) was then added dropwise. The mixture was stirred under argon until precipitation of the ylure and the solution of compound 10 (2.13 g, 10.04 mmol) in THF (10 mL) was added dropwise.

The mixture was stirred for 16 h, and then hydrolyzed. The formed solid was filtered, dissolved in diethyl ether, dried over MgSO 4 , filtered and concentrated under reduced pressure. Recrystallization from toluene afford 15 (50%) as a white solid; mp 135-137 °C; 1 H NMR (300 MHz, CDCl 3 ) δ: 7.83 (d, 1H, 9.0 Hz), 7.81

(d, 1H, 8.1 Hz), 7.49 (d, 1H, 2.4 Hz), 7.32 (d, 1H, 8.1 Hz), 7.20 (dd, 1H, 9.0 Hz and 2.4 Hz), 6.02 (m, 1H), 3.98 (s, 3H), 4H)

; IR (υ, cm -1 ): 2228 (CN); LC-MS: m/z = 236 (MH + ).

4.11. 2-(8-Methoxy-2,3-dihydro-1H-cyclopenta[a]naphthalen-1-yl)acetonitrile (16).

2241 (CN)

; LC-MS: m/z = 238 (MH + ). -); 13 C NMR (75 MHz, DMSO-d 6 ) δ : 163.

1, 146.8, 142.2, 135.8, 135.4, 133.0 (2C), 126.0, 122.5, 107.8, 61.1, 46.7, 46.0, 36.1, 33.5

; LC-MS: m/z = 228 (MH + ). 4.

naphthalen-1-yl) ethylamine (18). 4.

naphthalen-1-yl)methylamine (19).

  1 H NMR (300 MHz, DMSO-d 6 ) δ: 8.28 (br t, 1H), 7.79 (d, 1H, 9.0 Hz), 7.64

	(d, 1H, 8.4 Hz), 7.56 (d, 1H, 2.1 Hz), 7.22 (d, 1H, 8.4 Hz), 7.08 (dd, 1H, 9.0 Hz and 2.1 Hz),
	3.92 (s, 3H), 3.68-3.59 (m, 2H), 3.12 (m, 1H), 2.90 (m, 1H), 2.73 (m, 1H), 2.19-2.13 (m, 2H),
	1.88 (s, 3H); 13 C NMR (75 MHz, DMSO-d 6 ) δ: 170.

  . The organic layer was washed with 1 M solution of HCl, water, dried over MgSO 4 , filtered and concentrated under reduced pressure. The crude product was recrystallized from toluene to afford 17g (68%) as a white solid; mp 160-161 °C; 1 H NMR (300 MHz, DMSO-d 6 )

	δ: 7.79 (d, 1H, 9.0 Hz), 7.64 (d, 1H, 8.1 Hz), 7.53 (d, 1H, 2.1 Hz), 7.22 (d, 1H, 8.1 Hz), 7.07
	(dd, 1H, 9.0 Hz and 2.1 Hz), 6.23 (br t, 1H), 5.79 (q, 1H, 5.4 Hz), 3.91 (s, 3H), 3.69 (m, 1H),
	3.52 (m, 1H), 3.11 (m, 1H), 2.91-2.74 (m, 2H), 2.59 (d, 3H, 4.5 Hz), 2.14-2.10 (m, 2H);
	13 C NMR (75 MHz, DMSO-d 6 ) δ:

ACCEPTED MANUSCRIPT

acetate

  -1 ): 3333 (NH), 1624 (C=O); LC-MS : m/z = 285 (MH + ). MS (APCI, pos. 30 V) m/z: [M+H] + , 285.23. HRMS (ESI + ): m/z = calcd. for C 17 H 21 N 2 O 2 [M+H] + 285.12416 found: 285.12346.

	To a solution of corresponding amine 17, 18, 19 or 24 (1 mmol) in CH 2 Cl 2 (10 mL)
	were added triethylamine (2 mmol) and the corresponding alkyl isocyanate or isothiocyanate
	(1.2 mmol) at 0 °C. The mixture was stirred at room temperature during 2 h and hydrolyzed.
	CH 2 Cl 2 was added and the organic layer was washed with a 1 M solution of HCl and water,
	dried over MgSO 4 , filtered and concentrated under reduced pressure.

4.37. General procedure for synthesis of alkyl urea 17h-i, 19c-d, 24b-c and thiourea 17k-m, 19e-g and 24b.

  ; IR (υ, cm -1 ): 3317 (NH), 1622 (C=O); MS (APCI, pos. 30 V) m/z: [M+H] + , 300.21. HRMS (ESI + ): m/z = calcd. for C 18 H 23 N 2 O 2 [M+H] + 300.16812 found: 300.16734.

  MS (APCI, pos. 30 V) m/z: [M+H] + , 313.26. HRMS (ESI + ): m/z = calcd. for C 19 H 25 N 2 O 2 [M+H] + 313.18377 found: 313.18344.

	ACCEPTED MANUSCRIPT
	1623 (C=O);
	M A N U S C R I P T
	A C C E P T E D
	): 3279 (NH),

  ): 3313 (NH), 1624 (C=O); LC-MS : m/z = 327 (MH + ). MS (APCI, pos. 30 V) m/z: [M+H] + , 327.26. HRMS (ESI + ): m/z = calcd. for C 20 H 27 N 2 O 2 [M+H] + 327.19942

	found: 327.19834.

  ESI + ): m/z = calcd. for C 20 H 27 N 2 OS [M+H] + 342.17658 found: 342.176223.

	ACCEPTED MANUSCRIPT
	22.5, 11.8; IR (υ, cm -1 ): 3213 (NH), 1223 (C=S); MS (APCI, pos. 30 V) m/z: [M+H] + ,
	342.32. HRMS (
	M A N U S C R I P T
	A C C E P T E D
	8,

  2 mL) and potassium thiocyanate (427 mg, 4,40 mmol). The mixture was stirred at 60 °C during 16 h then hydrolyzed and extracted with EtOAc. The organic layer was washed with water, dried over MgSO 4 , filtered and concentrated under reduced pressure. The

	crude product was purified by flash chromatography (cyclohexane/ EtOAc : 5/5) to afford 17j
	(25%) as a white solid; mp 86-87 °C; 1 H NMR (300 MHz, DMSO-d 6 ) δ: 7.94 (br s, 1H), 7.79
	(d, 1H, 9.0 Hz), 7.75 (d, 1H, 2.4 Hz), 7.66 (d, 1H, 8.1 Hz), 7.24 (d, 1H, 8.1 Hz), 7.09 (dd, 1H,
	9.0 Hz and 2.4 Hz), 7.04 (br s, 2H), 4.00 (m, 1H), 3.91 (s, 3H), 3.60 (m, 1H), 3.20-2.86 (m,
	3H), 2.13-2.08 (m, 2H);

13

C NMR (75 MHz, DMSO-d 6 ) δ: 183.0,

  M+H] + , 286.25. HRMS (ESI + ): m/z = calcd. for C 16 H 20 N 3 O 2 [M+H] + 286.155 found: 286.15461.

	ACCEPTED MANUSCRIPT
	V) m/z: [
	M A N U S C R I P T
	A C C E P T E D

.1; IR (υ, cm -1 ): 3290 (NH), 1626 (C=O); MS

(APCI, pos. 30

  1 H NMR (300 MHz, CDCl 3 ) δ: 8.00(d, 1H, 8.8 Hz), 7.59 (d, 1H, 8.3 Hz), 7.31 (d, 1H, 8.3 Hz), 6.87 (d, 1H, 8.8 Hz), 5.75 (br t, 1H), 4.19 (br t, 1H), 4.13 (s, 3H), 4.0 (m, 1H), 3.63 (m, 2H), 3.35 (m, 1H), 3.10-2.95 (m, 3H), 2.40 (m, 1H), 2.12 (m, 1H), 1.41 (q, 2H, 7.5 Hz), 0.85 (t, 3H, 7.53 Hz); 13 C NMR (75 MHz, CDCl 3 ) δ:

Acknowledgement

The authors would like to acknowledge the Region Hauts de France (France), the Ministère de la Jeunesse, de l'Education Nationale et de la Recherche (MJENR) and the Fonds Européens de Développement Régional (FEDER) for funds allowed for NMR facilities.


Anes Bendimerad

Ahmad Mel
email: ahmad.mel@ugent.be

Jefrey Lijffijt
email: jefrey.lijffijt@ugent.be

Marc Plantevit
email: marc.plantevit@liris.cnrs.fr

Céline Robardet
email: celine.robardet@liris.cnrs.fr

Tijl De Bie
email: tijl.debie@ugent.be

Mining Subjectively Interesting Attributed Subgraphs

Keywords: Graphs, Networks, Subjective Interestingness, Subgraph Mining

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The availability of network data has surged both due to the success of social media and ground-breaking discoveries in experimental sciences. Consequently, graph mining is one of the most studied tasks for the data mining community. The value of graphs stems from the presence of meaningful relationships among the data objects (the vertices). These can be explored by approaches as different as graph embeddings [START_REF] Cai | A Comprehensive Survey of Graph Embedding[END_REF]-which map the nodes of a graph into a low dimensional space while preserving the local and global graph * The first two authors contributed equally to the paper. structure as well as possible-, community detection [START_REF] Fortunato | Community detection in graphs[END_REF]-the discovery of groups of vertices that somehow 'belong together'-, or subgraph mining-the identification of informative subgraphs.

Besides the relational structure, graphs may carry information in the form of attribute-value pairs on vertices and/or edges. Such graphs are called attributed graphs [START_REF] Moser | Mining Cohesive Patterns from Graphs with Feature Vectors[END_REF][START_REF] Prado | Mining Graph Topological Patterns[END_REF][START_REF] Silva | Mining Attribute-structure Correlated Patterns in Large Attributed Graphs[END_REF]. We focus here on graphs with attribute-value pairs on vertices (vertex-attributed graphs). Mining interesting subgraphs in attributed graphs is challenging, both conceptually and computationally. A prominent problem is defining the interestingness of a subgraph. Desirable properties of subgraph would be that it is cohesive (the attribute values of the vertices are similar) and that the vertices form an easy to describe pattern in the graph (e.g., vertices should be close to each other). A specific form of subgraph mining is to look for exceptional subgraphs, i.e., subgraphs whose attribute values are cohesive within the subgraph but exceptional in the full graph.

Few works in this direction exist. For example Atzmueller et al. [START_REF] Atzmueller | Description-oriented community detection using exhaustive subgroup discovery[END_REF] study mining communities (densely connected subgraphs) that can also be described well in terms of attribute values, while Bendimerad et al. [START_REF] Bendimerad | Mining exceptional closed patterns in attributed graphs[END_REF] look for exceptional subgraphs that are connected. Various quality measures are used in the first work and the second relies on Weighted Relative Accuracy. We introduce a new generically applicable interestingness measure for exceptional subgraph patterns based on Information Theory which is more flexible and can incorporate prior knowledge about the graph to steer the scoring of subgraph patterns. Besides, while previous works use certain hard constraints to arrive at subgraphs that are somehow interpretable, we integrate the interpretability into the interestingness measure. Hence, the trade-off between informativeness and interpretability can be made in a principled manner.

More specifically, we consider the problem to identify informative subgraphs that can be concisely described. The informativeness of a subgraph depends on the number of vertices it covers (more is better) and how surprising the statistics (attribute values) of those vertices are. Surprise is important because showing the user statistics they expect to see does not teach them anything. Vertices that are spread out over the graph, or that share no statistics cannot be summarized well, so the end-user cannot generalize over the structure of the vertices in a pattern and hence the graph structure is effectively transmitted to a user without any compression. Here instead, we look for subgraphs that are both homogeneous and there are 'surprisingly' many food establishments, except in the centre of that area (which is average). P 2 : in the City several types of venues are consistently overrepresented. P 3 : around Hackney there is a strip of blocks with lots of nightlife and food venues but limited educational venues.

localized, hence possess shared properties which can be exploited to produce concise descriptions. Fig. 1 shows example patterns from our method, applied to a setting where we want to explore the district structure of cities. The patterns should be interpreted as follows: certain attributes have surprisingly high/low values (marked +/respectively) in the given neighbourhoods as compared to a background model. We ensure the regions are localized by forcing them to have a description of the form "all vertices that are within distance d 1 of vertex x AND within distance d 2 of vertex y AND etc."; e.g., in pattern P 3 of Fig. 1, the covered areas (green blocks) are the intersection of blocks within distance two of either purple block.

Contributions. We present a pattern syntax for cohesive subgraphs with exceptional attributes (Sec. 2). We formalize their subjective interestingness in a principled manner using information theory, accounting for both the information they provide, as well as their interpretability (Sec. 3). We study how to mine such subgraphs efficiently (Sec. 4). We provide a thorough empirical study on real data that evaluates (1) the relevance of the subjective interestingness measure compared to state-of-the-art methods, and (2) the efficiency of the algorithms (Sec. 5). We discuss related work in Sec. 6 and the conclusions are presented in Sec. 7.

COHESIVE SUBGRAPHS WITH EXCEPTIONAL ATTRIBUTES

Before formally introducing the pattern language we are interested in, let us establish some notation. Notation An attributed graph is denoted G = (V , E, Â), where V is a set of n vertices, E ⊆ V × V is a set of m edges, and  is a set of p numerical attributes on vertices (formally, functions mapping a vertex onto an attribute value), with â(v) ∈ Dom a denoting the value of attribute â ∈  on v ∈ V . We use hats in â and  to signify the empirical values of the attributes, whereas a and A denote (possibly random) variables over the same domains. We also define the function N d (v) to denote the neighborhood of range d of a vertex v, i.e., the set of vertices whose geodesic distance to v is at most d:

N d (v) = {u ∈ V | dist (v, u) ≤ d}.
Cohesive Subgraphs with Exceptional Attributes (CSEA) As described in the introduction, we are interested in patterns that inform the user that a given set of attributes has exceptional values throughout a set of vertices in the graph.

Thus, and more formally, a CSEA pattern is defined as a tuple (U , S ), where U ⊆ V is a set of vertices in the graph, and S is a set of restrictions on the value domains of the attributes of A, or more specifically,

S = {[k a , ℓ a ] | a ∈ A}. A pattern (U , S ) is said to be contained in G iff ∀[k a , ℓ a ] ∈ S and ∀u ∈ U , k a ≤ â(u) ≤ ℓ a . (1)
Informally speaking, a CSEA pattern will be more informative if the ranges in S are smaller, as then it conveys more information to the data analyst. We will make this more formal in Section 3.1.

At the same time, a CSEA pattern (U , S ) will be more interesting if its description is more concise in some natural easier-to-interpret definition. Thus, along with the pattern language, we must also specify how a pattern from this language will be intuitively described.

To this end, we propose to describe the set of vertices U as a neighborhood of a specified range from a given specified vertex, or more generally as the intersection of a set of such neighborhoods. For enhanced expressive power, we additionally allow for the description to specify some exceptions on the above: vertices that do fall within this (intersection of) neighborhood(s), but which are to be excluded from U . Exceptions are a detriment to the interestingness of a pattern, but we can discount these naturally.

A premise of this paper is that this way of describing the set U is intuitive for human analysts, such that the length of the description of a pattern, as discussed in detail in Sec. 3.2, is a good measure of the complexity to assimilate or understand it. Our qualitative experiments in Sec. 5 do indeed confirm this is the case.

THE SUBJECTIVE INTERESTINGNESS OF A CSEA PATTERN

The previous sections already hinted at the fact that we will formalize the interestingness of a CSEA pattern (U , S ) by trading off its information content with its description length. Here we show how the FORSIED framework for formalizing subjective interestingness of patterns, introduced in [START_REF] De | An information theoretic framework for data mining[END_REF][START_REF] De | Maximum entropy models and subjective interestingness[END_REF], can be used for this purpose. The information content depends on both U and S. It is larger when more vertices are involved, when the intervals are narrower, and when they are more extreme. We will henceforth denote the information content as IC(U , S ). The description length depends on U only (as the attribute ranges require a fixed description length), and will be denoted as DL(U ). The subjective interestingness of a CSEA pattern (U , S ) is then expressed as:

SI(U , S ) = IC(U , S ) DL(U )
.

One of the core capabilities of the FORSIED framework is that it quantifies the information content of a pattern against a prior belief state about the data. It rigorously models the fact that the more plausible the data is (subjectively) according to a user or (objectively) under a specified model, the less information a user receives, and thus the smaller the information content ought to be. This is achieved by modeling the prior beliefs of the user as the Maximum Entropy (MaxEnt) distribution subject to any stated prior beliefs the user may hold about the data. This distribution is referred to as the background distribution. The information content IC(U , S ) of a CSEA pattern (U , S ) is then formalized as minus the logarithm of the probability that the pattern is present under the background distribution (also called the self-information or surprisal) [START_REF] Thomas | Entropy, relative entropy and mutual information[END_REF]:

IC(U , S ) = -log(Pr(U , S )).
In Sec. 3.1, we first discuss in greater detail which prior beliefs could be appropriate for CSEA patterns, and how to infer the corresponding background distribution. Then, in Sec. 3.2, we discuss in detail how the description length DL(U ) can be computed.

The information content of a CSEA pattern

Positive integers as attributes For concreteness, let us consider the situation where the attributes are positive integers (a : V → N, ∀a ∈ A), as will be our main focus throughout this paper. 1 For example, if the vertices are geographical regions (with edges connecting vertices of neighboring regions), then the attributes could be counts of particular types of places in the region (e.g. one attribute could be the number of shops). It is clear that it is less informative to know that an attribute value is large in a large region than it would be in a small region. Similarly, a large value for an attribute that is generally large is less informative than if it were generally small. The above is only true, however, if the user knows (or believes) a priori at least approximately what these averages are for each attribute, and what the 'size' of each region is. Such prior beliefs can be formalized as equality constraints on the values of the attributes A on all vertices, or mathematically:

A Pr(A) a ∈A a(v) = â ∈ Â â(v), ∀v ∈ V , A Pr(A) v ∈V a(v) = v ∈V â(v), ∀a ∈ A.
The MaxEnt background distribution can then be found as the probability distribution Pr maximizing the entropy -A Pr(A) log Pr(A), subject to these constraints and the normalization A Pr(A) = 1.

As shown in [START_REF] De | Maximum entropy models and subjective interestingness[END_REF], the optimal solution of this optimization problem is a product of independent Geometric distributions, one for each vertex attribute-value a(v). Each of these Geometric distributions is of the form Pr(a(v) = z) = p av •(1-p av ) z , z ∈ N, where p av is the success probability and it is given by: p av = 1exp(λ r a + λ c v ), with λ r a and λ c v the Lagrange multipliers corresponding to the two 1 The presented results can be extended relatively straighforwardly for other cases.

constraint types. The optimal values of these multipliers can be found by solving the convex Lagrange dual optimization problem. Given these Geometric distributions for the attribute values under the background distribution, we can now compute the probability of a pattern (U , S ) as follows:

Pr(U , S ) = v ∈U [k a , ℓ a ]∈S Pr(a(v) ∈ [k a , ℓ a ]), = v ∈U [k a , ℓ a ]∈S (1 -p av ) k a -(1 -p av ) ℓ a +1 .
This can be used directly to compute the information content of a pattern on given data, as the negative log of this probability. However, the pattern syntax is not directly suited to be applied to count data, when different vertices have strongly differing total counts. The reason is that the interval of each attribute is the same across vertices, which is desirable to keep the syntax understandable. Yet, if neighboring regions have very different total counts, it is less likely to find any patterns, and, even if we do, end-users would still need to know the total counts to interpret the patterns properly, as the same interval is not equally surprising for each region.

p-values as attributes To address this problem, we propose to search for the patterns not on the counts themselves, but rather on their significance (i.e., p-value or tail probability), computed with the background distribution as null hypothesis in a one-sided test.

More specifically, we define the quantities ĉa (v) as

ĉa (v) ≜ Pr(a(v) ≥ â(v)), = (1 -p av ) â (v ) ,
and use this instead of the original attributes â(v). This transformation of â(v) to ĉa (v) can be regarded as a principled normalization of the attribute values to make them comparable across vertices.

To compute the IC of a pattern with the transformed attributes ĉa , we must be able to evaluate the probability that c a (v) falls within a specified interval [k c a , ℓ c a ] under the background distribution for a(v). This is given by:

Pr(c a (v) ∈ [k c a , ℓ c a ]) = Pr (1 -p av ) a (v ) ∈ [k c a , ℓ c a ] , = Pr a(v) ≤ log(k c a ) log(1 -p av ) ∧ a(v) ≥ log(ℓ c a ) log(1 -p av ) , = (1 -p av ) log 1-pav (ℓ ca ) -(1 -p av ) log 1-pv a (k ca )+1 , = ℓ c a -(1 -p av ) • k c a , = ℓ c a -k c a + p av k c a .
Thus, the IC of a pattern on the transformed attributes ĉ can be calculated as:

IC(U , S ) = -log(Pr(U , S )), = - [k ca , ℓ ca ]∈S v ∈U log(ℓ c a -k c a + p av k c a ). (2)
In this paper, we focus on intervals [k c a , ℓ c a ] where either k c a = 0 (the minimal value) or ℓ c a = 1 (the maximal value). Such intervals state that the values of an attribute are all significantly large2 or significantly small respectively, for all vertices in U . We argue such

Algorithm 1: SIAS-Miner-Enum(G = (V , E, Â), D)
Input: G the input graph, D the maximum threshold of d for used neighbourhoods N d (v). Output: Result, the set of CSEAs, and minDesc, which stores the minimum description for each pattern.

Description length

As mentioned above, we describe the vertex set U in the pattern as (the intersection of) a set of neighborhoods In general, there are multiple ways of describing a given set of nodes U , by using a various combinations of neighborhoods. The best one is thus the one that minimizes f . This finally leads us to the definition of the description length of a pattern as:

N d (v), v ∈ V ,
DL(U ) = min X ⊆N (U ) f (X , U ).

AN ENUMERATION APPROACH TO MINING INTERESTING CSEA PATTERNS

SIAS-Miner-Enum mines interesting patterns using an enumerateand-rank approach. First, it enumerates all CSEA patterns (U , S ) that are closed simultaneously wrt. U , S, and the neighbourhood description. Second, it ranks patterns according to their SI values. An overview of the method is given in Algorithm 1 and explained further below.

Pattern enumeration

In the first step, we enumerate candidate tuples (U , S ) where the vertices U can be concisely described as an intersection of neighborhoods X ⊆ N (U ). Disregarding the description for a moment, since the pattern syntax is chosen such that each interval [k a , l a ] ∈ S should cover every vertex u ∈ U (Eq. 1), the IC of a tuple (U , S ) increases monotonically by adding vertices to U and intervals to S. Hence, to decrease the number of candidate patterns and increase computational efficiency we focus on closed patterns, i.e., tuples (U , S ) where no vertex can be added without enlarging intervals and where no interval can be reduced without omitting vertices. However, in Section 2 we additionally argued that a pattern (U , S ) where the vertices u ∈ U are unrelated will be difficult to understand and remember, which we expressed in the DL. Since computing DL(U ) is NP-Complete, it is not clear that enumeration of closed patterns wrt. the SI can be done. Nonetheless, enumeration of all closed (U , S ) appears wasteful because most sets U will have a high DL. What appears feasible is to restrict enumeration of sets U that are exactly intersections of neighborhoods, i.e., a description without any exceptions 3 .

While closed sets (U , S ) may be most efficiently enumerated by an itemset mining algorithm, if we want (U , S ) to additionally be closed with respect to intersections of neighbourhoods this yields a relational schema with two relations: (1) vertices are connected to all intervals that cover their attribute values, and (2) vertices are connected to every neighborhood that they are contained in. A tool that would indeed enumerate precisely the required closed patterns and no other is RMiner [START_REF] Spyropoulou | Interesting pattern mining in multi-relational data[END_REF].

More formally, the mapping from a graph to the required relational format is depicted in Fig. 2. Any vertex-attributed graph G can be mapped to an entity-relational model D through (1) creation of an entity type E v containing all vertices in G, (2) creation of | Â| entity types E a1 , E a2 , . . . E a | Â | , one per attribute, and (3) creation of an entity type E N containing all neighborhoods. Fig. 2 shows how intervals and neighborhoods form a hierarchy. For neighborhoods, the relationship holds that if a vertex v i is contained in a neighborhood N k (v j ), then it is also contained in all neighborhoods with larger hop-size:

v i ∈ N k (v j ) ⇒ v i ∈ N l (v j ) ∀l ≥ k.
A similar statement holds for intervals. P-N-RMiner [START_REF] Lijffijt | P-N-RMiner: a generic framework for mining interesting structured relational patterns[END_REF] is an extension of RMiner that exploits such hierarchies for efficiency. Firstly, fewer connections (edges) are needed between the entity types hence there is a smaller memory requirement. Secondly, there may be computational gains: P-N-RMiner is based on fixpoint-enumeration [START_REF] Boley | Listing closed sets of strongly accessible set systems with applications to data mining[END_REF], whose theory states that efficient enumeration of closed sets is possible if and only if the problem can be cast as a strongly accessible set system (E, F ).

The efficiency gain over plain enumeration comes from a closure operator, which can skip non-closed candidate patterns. For P-N-RMiner, this closure works outside-in, i.e., closed patterns are found by considering whether any entity (vertex in the relational representation) can be added without reducing the set of entities that are currently valid extensions to form a pattern under the pattern syntax. Patterns in (P-N-)RMiner are called complete connected subsets (CCSs) because all possible edges must exist and the vertices in the relational representation must be connected, see Fig. 2, right for an example. In the relational context, a pattern is called a maximal CCS (MCCS) if no entity can be added, i.e., patterns we referred to as closed in the discussion above. It is worth to notice that an MCCS provides, in addition to a tuple (U , S ), the set N (U ) of neighborhoods that contain U , from which DL(U ) is computed.

Notice P-N-RMiner also ranks patterns based on interestingness under a known-degree background model, but that is not useful in our setting as the IC and the DL are very different here. Hence, we only use it to enumerate all candidates. The computational complexity is clearly exponential as the number of outputs may be exponential in the size of the input, plus in this setting no fixpointenumeration-based algorithm may have polynomial-time delay [START_REF] Lijffijt | P-N-RMiner: a generic framework for mining interesting structured relational patterns[END_REF]. Scalability experiments are presented in Sec. 5.

Computing DL(U )

The calculation of DL(U ) is NP-Complete and equivalent to Set Cover: it consists in finding the optimal cover of the set U based on unions of complements N i (v) and exceptions {v} such that x ∈ U . Nevertheless, we propose a branch-and-bound approach that takes benefit from several optimisation techniques.

In order to find the optimal description of a pattern (U , S ), we explore the search space 2 N (U ) with a branch-and-bound approach described in Algorithm 2. Let X and Cand be subsets of N (U ) that are respectively the current enumerated description and the potential candidates that can be used to describe U . Initially, DL-Optimise is called with X = ∅ and Cand = N (U ). In each call, a neighbourhood e ∈ Cand is chosen and used to recursively explore two branches: one made of the descriptions that contain e (by adding e to X ), and the other one made of descriptions that do not contain e (by removing e from Cand). Several pruning techniques are used in order to reduce the search space and are detailed below.

Function LB (line 1) lower bounds the lengths of the descriptions that can be generated in the subsequent recursive calls of DL-Optimise. If LB is higher or equal than the length of the current best description of U f (bestDesc, U ), there is no need to carry on the exploration of the search subspace as no further description can improve f . The principle of LB is to evaluate the maximum reduction in exceptions that can be obtained when description X is extended with neighbourhoods of Y :

дain Y (X , U ) = |exc(X , U )| -|exc(X ∪ Y , U )|, with Y ⊆ Cand. (3)
Algorithm 2: DL-Optimise(U , X , Cand, bestDesc)

Input: U the set of vertices to describe, X the current enumerated description, Cand the set of candidates, bestDesc the current best description found. Output: bestDesc the best description found while exploring the current search sub-space.

1 if LB(X , U , Cand) < f (bestDesc, U ) then 2 if Cand ∅ then 3 pruneUseless(U , X , Cand) 4 pruneLowerBounded(U , X , Cand) 5 e ← argmin e ′ ∈Cand f (X ∪ {e ′ }, U ) 6 DL-Optimise(U , X ∪ {e}, Cand \ {e}, bestDesc) 7 DL-Optimise(U , X , Cand \ {e}, bestDesc) 8 else if f (X , U ) < f (bestDesc, U ) then 9 bestDesc ← X
This function can be rewritten using neighbourhood complements as дain Y (X , U ) = |∪ y ∈Y (y ∩ exc(X , U )) |4 . We can obtain an upper bound of the gain function using the ordered set {д 1 , . . . ,

д |Cand | } of {дain {e } (X , U ) | e ∈ Cand} such that д i ≥ д j if i ≤ j: Property 1. дain Y (X , U ) ≤ |Y | i=1 д i , for Y ⊆ Cand.
Proof. Since the size of the union of sets is lower than the sum of the set sizes, we have дain

Y (X , U ) ≤ y ∈Y |y ∩ exc(X , U )| ≤ y ∈Y дain {y } (X , U ) ≤ |Y | i=1 д i . □
This is the foundation of the function LB defined as |) and it concludes the proof. □ Algorithm 3: pruneUseless(U , X , Cand)

LB(X , U , Cand) = min i ∈⟦0, |Cand |⟧ {(|X | + i + 1) × log(|N |) + 1 + max 0, |exc(X , U )| -i j=1 д i × log(|V |)} (4) Property 2. f (X ∪ Y , U ) ≥ LB(X , U , Cand), for all Y ⊆ Cand. Proof. Based on Property 1, we have |exc(X ∪ Y , U )| ≥ max(0, |exc(X , U )|-|Y | i=1 д i ). This means that f (X ∪Y , U ) ≥ (|X |+|Y |+1)× log(|N |) + 1 + max{0, |exc(X , U )| -|Y | j=1 д i } ×loд(|V |) and thus, LB(X , U , Cand) ≤ (|X |+|Y |+1) ×log(|N |) + (1+max{0, |exc(X , U )| -|Y | j=1 д i }) × log(|V
1 Cand ← {e ∈ Cand | gain( {e }, X, U ) > 0}
Algorithm 4: pruneLowerBounded(U , X ,Cand)

1 Cand ← {e i ∈ Cand | ∀e j ∈ Cand \ {e i } : (exc(X ∪ {e j }, U ) ⊈ exc(X ∪ {e i }, U ))) ∨ (exc(X ∪ {e j }, U ) = exc(X ∪ {e i }, U ) ∧i < j ) }
In other terms, in the recursive calls, a description length will never be lower than LB(X , U , Cand).

Function pruneUseless line 3 removes candidate elements that can not improve the description length, that is candidates e ∈ Cand for which дain({e}, X , U ) = 0. Such element does not have the ability to reduce the number of exceptions in X . This also implies that e will not reduce the number of exceptions for descriptions X ∪ Y , with Y ⊆ Cand. Thus, such elements will not decrease the description length of X ∪ Y .

Function pruneLowerBounded line 4 removes a candidate e ∈ Cand if there is a candidate e ′ ∈ Cand that is always better than e for all descriptions produced in subsequent recursive calls.

Property 3. Let e, e ′ ∈ Cand such that exc(X ∪{e}, U ) ⊆ exc(X ∪ {e ′ }, U ). Then, for all Y ⊆ Cand\ {e, e ′ }, we have f (X ∪Y ∪ {e}, U ) ≤ f (X ∪ Y ∪ {e ′ }, U ) Proof. The set of exceptions in X ∪ Y ∪ {e} is equal to exc(X ∪ Y ∪ {e}, U ) = exc(X ∪ {e}, U ) ∩ exc(Y , U ). Since exc(X ∪ {e}, U ) ⊆ exc(X ∪ {e ′ }, U ), then exc(X ∪Y ∪ {e}, U ) ⊆ exc(X ∪Y ∪ {e ′ }, U ). As |X ∪Y ∪{e}| = |X ∪Y ∪{e ′ }|, we can conclude that f (X ∪Y ∪{e}, U ) ≤ f (X ∪ Y ∪ {e ′ }, U ). □
Based on Property 3, pruneLowerBounded removes elements e ′ ∈ Cand such that exc(X ∪ {e}, U ) ⊆ exc(X ∪ {e ′ }, U ). Notice that even if an element e ′′ has been removed due to the lower bound of e ′ , the procedure is still correct since e ′′ is lower bound by e by the transitivity of inclusion. The last optimisation consists in choosing e ∈ Cand that minimises f (X ∪{e}, U ) (line 5 of Algorithm 2). This makes it possible to quickly reach descriptions with low DL, and subsequently provide effective pruning when used in combination with LB.

EXPERIMENTS

In this section, we report our experimental results. We start by describing the real-world dataset we used, as well as the questions we aim to answer. Then, we provide a thorough comparison with the state-of-the-art algorithm Cenergetics [START_REF] Bendimerad | Mining exceptional closed patterns in attributed graphs[END_REF]. Eventually, we provide a qualitative analysis that demonstrates the ability of our approach to achieve the desired goal. For reproducibility purposes, the source code and the data are made available here. 5Experimental setting. Experiments are performed on the realworld dataset of the London graph. The London graph (|V | = 289, |E| = 544, | Â| = 10) is based on the social network Foursquare 6 . Each vertex represents a district in London, and edges link adjacent districts. Each attribute stands for the number of places of a given type (e.g. outdoors, colleges, residences, restaurants, etc.) in each district. Considering all the numerical values of attributes is computationally expensive and would lead to redundant results, we pre-process the graph so that for each attribute, the values ĉa (v) are binned into five quantiles. Aims. As stated in Section 6, there is no approach that supports the discovery of subjectively interesting attributed subgraphs in the literature. The closest method to SIAS-Miner-Enum is Cenergetics [START_REF] Bendimerad | Mining exceptional closed patterns in attributed graphs[END_REF] that aims at discovering closed exceptional attributed subgraphs involving overrepresented and/or underrepresented attributes, and which mined the London graph used here in the experiments (and on similar graphs of other cities). It assesses exceptionality with the weighted relative accuracy (WRAcc) measure that accounts for margins but cannot account for other prior knowledge. The computational problem we tackle is more complex than Cenergetics, but how much is this overhead? Is it worth it in terms of pattern quality? This empirical study aims to answer to these questions. Quantitative experiments. Fig. 3 reports the execution time per pattern, the number of discovered patterns, and the average quality of the top 500 patterns (i.e., DL and SI) of SIAS-Miner-Enum and Cenergetics according to the number of vertices, the number of attributes and the minimum number of vertices of searched patterns. We post-processed the results of Cenergetics in order to obtain similar redescriptions of the vertices as in SIAS-Miner-Enum, but we do not consider this post-processing step in the reported execution times. These tests reveal that the computational overhead of SIAS-Miner-Enum is important: the discovery of a pattern by SIAS-Miner-Enum is generally one to two orders of magnitude more costly than Cenergetics. However, SIAS-Miner-Enum provides patterns of better quality. Indeed, the average description length of the top 500 patterns discovered by SIAS-Miner-Enum is smaller than those of Cenergetics and the SI of CSEA patterns is greater than the one of the patterns extracted by Cenergetics. Qualitative experiments. Finally, we show some examples of patterns (with at least 5 vertices) discovered by both SIAS-Miner-Enum and Cenergetics on London graph. The top 4 CSEA patterns discovered by SIAS-Miner-Enum are given in Tab. 1 and displayed in Fig. 4. Green cells represent vertices covered by a CSEA pattern while blue cells are the centers, purples cells are the centers that do not belong to the pattern, orange cells are centers that are also exception (i.e., behave differently from the pattern but covered by the description) and the red cells are normal exceptions. We also report the top 4 patterns discovered by Cenergetics in Fig. 5. Interestingly, CSEA patterns are more cohesive than Cenergetics ones, described by at most two Neighborhoods, which eases the assimilation by an analyst. Unexpectedly, the second best patterns of SIAS-Miner-Enum and Cenergetics are somewhat similar: the CSEA pattern covers two additional vertices and the two patterns are in agreement on some overrepresented types of venues (e.g., nightlife, shops). Surprisingly, outdoor venues are consistently overrepresented in the CSEA pattern while such venues are considered as limited by Cenergetics. This inconsistency may be due to some extreme values in some regions that impact the mean and then the value of the WRacc measure by Cenergetics. Summary. Even if our approach has an obvious computational overhead compared to Cenergetics (the problem tackled is more complex), these experiments show the ability of SIAS-Miner-Enum to discover CSEA patterns that are more intuitive and informative. 4).

RELATED WORK

Several approaches have been designed to discover new insights in vertex attributed graphs. The pioneering work of Moser et al. [START_REF] Moser | Mining Cohesive Patterns from Graphs with Feature Vectors[END_REF] presents a method to mine dense homogeneous subgraphs, i.e., subgraphs whose vertices share a large set of attributes. Similarly, Günnemann et al. [START_REF] Günnemann | Subspace Clustering Meets Dense Subgraph Mining[END_REF] introduce a method based on subspace clustering and dense subgraph mining to extract non redundant subgraphs that are homogeneous with respect to the vertex attributes. Silva et al. [START_REF] Silva | Mining Attribute-structure Correlated Patterns in Large Attributed Graphs[END_REF] extract pairs made of a dense subgraph and a Boolean attribute set such that the Boolean attributes are strongly associated with the dense subgraphs. In [START_REF] Prado | Mining Graph Topological Patterns[END_REF], the authors propose to mine the graph topology of a large attributed graph by finding regularities among numerical vertex descriptors. The main objective of all these approaches is to find regularities instead of peculiarities within a large graph, whereas Exceptional Subgraph Mining mines subgraphs with distinguishing characteristics. Interestingly, a recent work [START_REF] Atzmueller | Description-oriented community detection using exhaustive subgroup discovery[END_REF] proposes to mine descriptions of communities from vertex attributes, with a Subgroup Discovery approach. In this supervised setting, each community is treated as a target that can be assessed by well-established measures, like WRAcc. In [START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF], the authors aim at discovering contextualized subgraphs that are exceptional with respect to a model of the data. Restrictions on the attributes, that are associated to edges, are used to generate subgraphs. Such patterns are of interest if they pass a statistical test and have high value on an adapted WRAcc measure. Similarly, [START_REF] Lemmerich | Mining Subgroups with Exceptional Transition Behavior[END_REF] proposes to discover subgroups with exceptional transition behavior as assessed by a first-order Markov chain model. The problem of exceptional subgraph mining in attributed graphs was introduced in [START_REF] Bendimerad | Mining exceptional closed patterns in attributed graphs[END_REF]. Based on an adaptation of WRAcc, the method aims to discover subgraphs with homogeneous and exceptional characteristics. In Section 5, we demonstrate that CSEA patterns discovered by SIAS-Miner-Enum are more informative and less complex than patterns discovered by the algorithm devised in [START_REF] Bendimerad | Mining exceptional closed patterns in attributed graphs[END_REF].

More generally, Subgroup Discovery [START_REF] Lavrac | Subgroup Discovery with CN2-SD[END_REF][START_REF] Novak | Supervised Descriptive Rule Discovery[END_REF] aims to find descriptions of sub-populations for which the distribution of a predefined target value is significantly different from the distribution in the whole data. Several quality measures have been defined to assess the interest of a subgroup. The WRAcc is the most commonly used. However, these measures do not take any prior knowledge into account. Therefore, we can expect identified subgroups are less informative. The problem of taking subjective interestingness into account in pattern mining was already identified in [START_REF] Silberschatz | On Subjective Measures of Interestingness in Knowledge Discovery[END_REF] and has seen a renewed interest in the last decade.

The interestingness measure employed here is inspired by the FORSIED framework [START_REF] De | An information theoretic framework for data mining[END_REF][START_REF] De | Subjective Interestingness in Exploratory Data Mining[END_REF], which defines the SI of a pattern as the ratio between the IC and the DL. The IC is the amount of information specified by showing a pattern to the user. The measure is based on the gain from a Maximum Entropy background model that delineates the current knowledge of a user, hence it is subjective, i.e., particular to the modeled belief state. P-N-RMiner [START_REF] Lijffijt | P-N-RMiner: a generic framework for mining interesting structured relational patterns[END_REF], the tool used here for pattern enumeration, has also been developed under FORSIED. However, the interestingness measure in this paper is very different, because the information contained in the patterns shown to the user does not align with the output of P-N-RMiner. FORSIED has been applied to mine dense subgraphs [START_REF] Matthijs Van Leeuwen | Subjective interestingness of subgraph patterns[END_REF], but not to Exceptional Subgraph Mining, where we also need to account for attribute values. A much faster CP-based implementation of RMiner exists that directly searches for the top-1 most interesting pattern [START_REF] Guns | Direct Mining of Subjectively Interesting Relational Patterns[END_REF]. However, this tool does not support structured attributes and the interestingness measure is different, hence it could not be used directly in our problem setting.

CONCLUSION

We have introduced a new pattern language in attributed graphs. A so-called CSEA pattern provides to the user a set of attributes that have exceptional values throughout a subset of vertices. The strength of the proposed pattern language lies in its independence to a notion of support to assess the interestingness of a pattern. Instead, the interestingness is defined based on information theory, as the ratio of the information content (IC) over the description length DL. The IC is the amount of information provided by showing the user a pattern. The quantification is based on the gain from a Maximum Entropy background model that delineates the current knowledge of a user. Using a generically applicable prior as background knowledge, we provide a quantification of exceptionality that (subjectively) appears to match our intuition. The DL assesses the complexity of reading a pattern, the user being interested in concise and intuitive descriptions. To this end, we proposed to describe a set of vertices as an intersection of neighborhoods within a chosen distane of selected vertices, the distance and vertices making up the description of the subgraph. We have shown how an effective and principled algorithm can enumerate patterns of this language. Extensive empirical results on two real-world datasets confirm that CSEA patterns are intuitive, and the interestingness measure aligns well with actual subjective interestingness. This paper opens up several avenues for further research such as the development of speed-ups of SIAS-Miner-Enum and how to incorporate non-ordinal attribute types in the pattern syntax and interestingness measure.

P 1 :

 1 {food} + P 2 : {professional, nightlife, outdoors, college} + P 3 : {nightlife, food} + {college} -

Figure 1 :

 1 Figure 1: Example results on a graph based on Foursquare data covering the presence of various types of venues in London. P 1 : around the orange block (west/south of Hyde Park)there are 'surprisingly' many food establishments, except in the centre of that area (which is average). P 2 : in the City several types of venues are consistently overrepresented. P 3 : around Hackney there is a strip of blocks with lots of nightlife and food venues but limited educational venues.

1 8 bestDesc← ∅ 9 DL

 89 // transformation to entity-relation model 2 D ← transformToER(G,D) 3 // enumeration of the patterns 4 Result ←P-N-RMiner(D) 5 // computation of the minimum description for each found pattern 6 minDesc ← { } 7 for ⟨(U , S ), N (U )⟩ ∈ Result do -Optimise(U , ∅,N (U ), bestDesc) 10 minDesc[(U,S)] ← bestDesc intervals are easiest to interpret. The logarithmic terms in Eq. (2) then simplify to log(ℓ c a ) and log(1 -k c a + p av k c a ) respectively.

  with a set of exceptions: vertices are in the intersection but not part of U . The length of such a description is the sum of the description lengths of the neighborhoods and the exceptions. More formally, let us define the set of all neighborhoods N = {N d (v) | v ∈ V ∧d ∈ ⟦0, D⟧}, (with D a positive integer representing the radius of the neighborhood), and let N (U ) = {N d (v) ∈ N | U ⊆ N d (v)} be the subset of neighborhoods that contain U . The length of a description of U as the intersection of all neighborhoods in a subset X ⊆ N (U ), along with the set of exceptions exc(X , U ) ≜ ∩ N d (v ) ∈X N d (v) \ U , is then quantified by the function f : 2 N (U ) × U -→ R: f (X , U ) = (|X | + 1) • log(|N |) + (|exc(X , U )| + 1) • log(|V |). Indeed, the first term accounts for the description of the number of neighborhoods (log(|N |), as there can be no more than |N | neighborhoods in X , and for describing which neighborhoods are involved (|X | log(|N |)). The second term accounts for the description of the number of exceptions (log(|V |)), and for describing the exceptions themselves (|exc(X , U ) log(|V |)).

Figure 2 :

 2 Figure 2: Transformation from (1) a graph structure to (2) an entity-relation model with D = 1, and (3) an example of a maximal complete connected subset (MCCS) pattern from P-N-RMiner.

Figure 3 :

 3 Figure 3: SIAS-Miner-Enum vs Cenergetics: runtime per pattern (first column), #patterns (second column), average description length (third column) and subjective interestingness (fourth column) of the top 500 patterns for varying |V | (1st row), |A| (2nd row) and a threshold on the minimum number of vertices in searched patterns (3rd row) for London graph (D = 3).

Figure 4 :

 4 Figure 4: Top 4 patterns discovered in London graph by SIAS-Miner-Enum (minV ertices = 5, D = 3). Details are provided in Tab. 1

P 1 :P 2 :

 12 {professional} + {shop} - {shop, nightlife, food } + {outdoors, travel, residence} - P 3 : {professional} - P 4 : {professional} + , {shop, food} -

Figure 5 :

 5 Figure 5: Top 4 patterns discovered in London graph by Cenergetics (minV ertices = 5).

Table 1 :

 1 Detailed characteristics of the top 6 patterns discovered in London dataset by SIAS-Miner-Enum (see Fig.

Note empty regions have tail probabilities ĉa (v ) = 1 for any attribute and thus fall within any upper interval, but also IC = 0 for any attribute of that region as both l ca = 1 and p av = 1.

Notice that such a description does not necessarily minimize the description length of a vertex set U .

= |exc(X, U ) | -|exc(X ∪ Y, U ) | = |(∩ x ∈X x ) \ U | -|(∩ e ∈X ∪Y e ) \ U | = |(∩ x ∈X x ) ∩ U | -|((∩ x ∈X x ) ∩ U ) ∩ (∩ y ∈Y y ) | = |(∩ x ∈X x ) ∩ U ) \ (∩ y ∈Y y ) | = |(∩ x ∈X x ) \ U ) ∩ (∩ y ∈Y y ) | = |exc(X, U ) ∩ (∪ y ∈Y y ) | = | ∪ y ∈Y (y ∩ exc(X, U )) |

https://goo.gl/2jvE8j

https://foursquare.com

Acknowledgements. This work was supported by the ERC under the EU's Seventh Framework Programme (FP7/2007-2013) / ERC Grant Agreement no. 615517, FWO (project no. G091017N, G0F9816N), the EU's Horizon 2020 research and innovation programme and the FWO under the Marie Sklodowska-Curie Grant Agreement no. 665501 and Group Image Mining (GIM) which joins researchers of THALES Group and LIRIS Lab. This work is also partially supported by the CNRS project APRC Conf Pap.