Helene Beloeil
email: helene.beloeil@chu-rennes.fr

Opioid-free anesthesia

Keywords: opioid-free anesthesia, opioid, ketamine, lidocaine, alpha 2 agonists Practice

Opioid Free Anesthesia (OFA) is emerging as a new stimulating research perspective. The rationale to propose OFA is based on the aim to avoid the negative impact of intraoperative opioid on patient's postoperative outcomes and also on the physiology of pathways involved in intraoperative nociception. It is based on the concept of multimodal anesthesia. OFA has been shown to be feasible but the literature is still scarce on the clinically meaningful benefits for patients as well as on the side effects and / or complications that might be associated with it. This review focused first on the physiology of nociception, the reasons for using or not opioids during anesthesia, and then on the literature reporting evidence-based proofs of benefits / risks associated with OFA.

Introduction

Opioid-free anesthesia (OFA) has become more and more popular amongst anesthesiologists around the world. It is an emerging technique and a recent research perspective based on the idea that avoiding intraoperative opioids would be associated with better postoperative outcomes. Indeed, opioids have shown their limits, and reducing opioids administration ered, at any time during the perioperative period, has been proposed for many years in the literature. Thus, multimodal postoperative analgesia has been the gold standard for more than 25 years [START_REF] Dahl | Prevention of postoperative pain by balanced analgesia[END_REF]. It allows opioid-sparing and better outcomes than morphine administered as a sole analgesic agent after surgery. OFA is based on the same concept, as one drug will not replace opioids. It is the association of drugs and/or techniques that allows a good quality general anesthesia with no need for opioids. The association can combine NMDA antagonists (ketamine, lidocaine, magnesium sulfate), sodium channel blockers (local anesthetics (LA)), anti-inflammatory drugs (NSAID, dexamethasone, LA) and alpha-2 agonists (dexmetedomidine, clonidine). Of course, for toxicity reasons all these drugs / techniques will not be administered simultaneously to the same patient. Moreover, all these drugs have documented side effects. The idea of OFA is very exciting! However, the literature remains scare on the subject. Many retrospective, case reports or single-physician experience, are available today but only few well-designed studies bringing evidence-based proofs of the benefits of OFA for the patients, have been published so far. This is why this review will first focus on the principles and physiology on which OFA is based on, then it will detail what is known so far on how to perform OFA and finally report the evidence-based proofs of benefits / risks associated with it.

Why do we use intraoperative opioids?

Anesthesia textbooks published in the last 50 years have an identical first paragraph on the concerning the use of opioids during anesthesia with a double objective: the objective is twofold: 1) to reduce the need for hypnotic agents and 2) to ensure effective analgesia. The introduction of synthetic morphine in the 1960s revolutionized changed anesthesia's practice by allowing savings in hypnotic agents consumption and inhibiting on of the sympathetic system without cardiovascular collapse or histamine release. With regard to analgesia, the aim is to limit the reaction to nociceptive stimuli and in particular to ensure the control of the resulting cardiovascular reactions [START_REF] Van Aken | The influence of fentanyl and tracheal intubation on the hemodynamic effects of anesthesia induction with propofol/N2O in humans[END_REF]. Synthetic opioids were therefore widely adopted as soon as they appeared to limit the effects of hypnotic agents available at the time, by reducing their doses, facilitatinge hemodynamic stability, reducinge cardiac output without reducing coronary perfusion, blocking spontaneous breathing and facilitatinge mechanical ventilation. By blocking the ascending nociceptive stimuli, opioids are indeed very effective.

However, pain and nociception are two different things! Pain is indeed a conscious unpleasant perception of a noxious stimulus and nociception is the stimulation of noxious receptors. Anti-nociception is then the suppression of the consequences of the stimulation of the noxious receptors. Nociception without pain is possible, i.e. under general anesthesia.

What we routinely call "intraoperative analgesia" should indeed be called "intraoperative control of the consequences of the stimulation of noxious receptors" or "control of the autonomous nervous system response to nociception" [START_REF] Egan | Are opioids indispensable for general anesthesia?[END_REF]. Looking at the physiology, various mediators are involved in nociception pathways: serotonin, norepinephrine, enkephalin, peptides…etc. Anti-nociception can then be obtained by interfering with various neuromediators not only by interfering with enkephalins with opioids [START_REF] Cividjian | Do we feel pain during anesthesia? A critical review on surgery-evoked circulatory changes and pain perception[END_REF]. Then, opioids are not indispensable essential for general anesthesia [START_REF] Egan | Are opioids indispensable for general anesthesia?[END_REF]. However, we are currently lacking accurate and validated monitoring to measure of intra-operative nociception [START_REF] Cividjian | Do we feel pain during anesthesia? A critical review on surgery-evoked circulatory changes and pain perception[END_REF].

Why reducing or avoiding opioids perioperatively?

After decades of under-treatment of pain, the most recent audits have shown a clear progress over the last 20 years [START_REF] Gerbershagen | Pain intensity on the first day after surgery. A prospective cohort study comparing 179 surgical procedures[END_REF]. The systematic use of opioids contributed to this advance.

However, this broad and high-dose use of opioids has revealed its limits: less efficacy on pain during movement, dose-dependent side effects, which can be very disabling for the patient and delay postoperative rehabilitation, dose-dependent hyperalgesia paradoxical source of acute and chronic pain, immunomodulation that may have a negative impact on infectious or cancerous pathologies [START_REF] Sacerdote | Non-analgesic effects of opioids: mechanisms and potential clinical relevance of opioid-induced immunodepression[END_REF] and finally, doubt about possible neurotoxicity [START_REF] Kofke | The neuropathologic effects in rats and neurometabolic effects in humans of large-dose remifentanil[END_REF].

Moreover, anesthesiologists and perioperative opioids over prescriptions are part of the current so called 'opioid crisis' currently happening in North America [START_REF] Lancet | The opioid crisis in the USA: a public health emergency[END_REF][START_REF] Yaster | Houston, we have a problem!": The role of the anesthesiologist in the current opioid epidemic[END_REF]. Patients who were initially prescribed opioids to treat acute pain including pain after surgery transitioned to acquire their substance of abuse on the black market and often move on to use more affordable and available (but also more deadly) related street drugs [START_REF] Krausz | Noth american opiod crisis: decline and fall of the war on drugs[END_REF]. Perioperative prescriptions have been incriminated [START_REF] Brat | Postsurgical prescriptions for opioid naïve patients and association with overdose and misuse: retrospective cohort study[END_REF] as well as opioid treatment for chronic pain.

Anesthesiologists are also part of the problem [START_REF] Yaster | Houston, we have a problem!": The role of the anesthesiologist in the current opioid epidemic[END_REF]. The consequences are devastating with more than 60 000 US adult alleged to be dead from drug overdose in 2017 [START_REF] Lirk | Opioid-free anaesthesia: Con: it is too eraly to adopt opioid-free anaesthesia today[END_REF]. All these reasons explain the motivation to move away from opioids administration in the postoperative period but also during general anesthesia. Indeed, modern postoperative analgesia is based on opioid sparing. The principle of balanced analgesia described by Kehlet [START_REF] Dahl | Prevention of postoperative pain by balanced analgesia[END_REF] has been prevailing for more than 25 years. The prescriptions of combinations of analgesics of different classes and / or techniques of regional anesthesia are recommended to optimize analgesia pain control while limiting the adverse undesirable effects attributable to the different of each analgesic agents. The evolution of intraoperative anesthesia is comparable similar. Indeed, it evolved from single agent anesthesia to opioid-based anesthesia and then multimodal or balanced anesthesia. Nowadays, balanced anesthesia without opioids (opioidfree anesthesia (OFA)) is feasible [START_REF] Lavand | Opioid-free anesthesia: Pro: damned if you don't use opioids during surgery[END_REF]. While there are evidences evidence-based proofs are showing that OFA is associated with benefits for the patients (cf. below), proofs are lacking concerning "opioid-free anesthesia and analgesia (OFAA)" which includes the total perioperative period. OFAA is still a challenge today. Indeed, a dramatic reduction of intraoperative opioids is not always associated with a reduction of postoperative opioids [START_REF] Brandal | Impact of enhanced recovery after surgery and opioid-free anesthesia on opioid prescriptions at discharge from the hospital: a historical-prospective study[END_REF].

However, according to Susan et al' [START_REF] Suzan | A crucial administration timing separates between beneficial and counterproductive effects of opioids on postoperative pain[END_REF] hypothesis, the timing of administration of opioids is crucial: when administered during surgery (= tissue injury), opioids aggravate acute postoperative (= post-injury) pain, in contrast to their analgesic effect when given after surgery (= after tissue injury). The concept of OFA; i.e. no opioids during surgery, fits well with this theory.

How to perform anesthesia without opioids?

Opioid-free anesthesia is a multimodal anesthesia combining different drugs and / or techniques. Regional anesthesia/ analgesia is, of course, the best technique to reduce or avoid intraoperative opioids. Indeed, the blockage of nociceptive afferences is perfectly ensured by regional anesthesia/ analgesia and benefits have been long proven in the literature [START_REF] Lavand'homme | Intraoperative epidural analgesia combined with ketamine provides effective preventive analgesia in patients undergoing major digestive surgery[END_REF].

When regional anesthesia is not applicable, many other anesthetic drugs inhibit the sympathetic system and reduce the consumption of opioids perioperatively:

-Intravenous lidocaine administered intravenously blocks sodium channels and discharges of peripheral neurons excited by nociceptive stimuli, inhibits NMDA receptors and has antiinflammatory properties. All these effects are clinically translated into an analgesic benefit, morphine sparing, a decrease in length of stay, an earlier resumption of transit, a reduction in the incidence of nausea and vomiting and a faster postoperative rehabilitation [START_REF] Sun | Perioperative systemic lidocaine for postoperative analgesia and recovery after abdominal surgery: a meta-analysis of randomized controlled trials[END_REF]. This has been shown in different types of surgery (abdominal but also spine surgery) [START_REF] Farag | Effect of periopertaive intravenous lidocaine administration on pain, opioid consumption and quality of life after complex spine surgery[END_REF].

-By antagonizing NMDA receptors, ketamine prevents postoperative hyperalgesia. Several meta-analyzes have reported a beneficial effect of ketamine on the intensity of postoperative pain, the reduction of opioid consumption per and postoperatively and the reduction of chronic pain after surgery [START_REF] Bell | Perioperative ketamine for acute postoperative pain[END_REF]. Ketamine is also helpful in reducing intraoperative blood pressure variability [START_REF] Forget | Stable anesthesia with altrenative to opioids: are ketamine and magnesium helpful in stabilizing hemodynamics during surgery? A systematic review and meta-anamysis of randomized controlled trials[END_REF].

-Magnesium sulfate is a noncompetitive antagonist of NMDA receptors by inhibition of intracellular calcium flow. Evidences are lacking, but some studies have shown morphine sparing when magnesium is administered intraoperatively [START_REF] Murphy | Analgesic efficacy of continuous intravenous magnesium infusion as an adjuvant to morphine for postoperative analgesia: a systematic review and meta-analysis[END_REF]. Moreover, a recent metaanalysis reported that magnesium significantly reduces intraoperative heart rate variability [START_REF] Forget | Stable anesthesia with altrenative to opioids: are ketamine and magnesium helpful in stabilizing hemodynamics during surgery? A systematic review and meta-anamysis of randomized controlled trials[END_REF].

-Anti-inflammatory drugs (dexamethasone and NSAIDs) are also helpful when avoiding opioids. NSAIDs allow a savings of spare about 50% in morphine, which results resulting in a reduction in PONV, sedation and duration of postoperative ileus, as well as an improvement in pain scores compared with morphine alone. This morphine savings is the most interesting when compared to other non-morphine analgesics used in current practice (nefopam, paracetamol) Morphine sparing effect of NSAIDs is more important than the one of paracetamol and nefopam [START_REF] Martinez | Non-opioid analgesics in adults after major surgery: systematic review with network meta-analysis of randomized trials[END_REF]. With regard to dexamethasone, there are now numerous studies showing morphine savings associated with a reduction in PONV and fatigue and better postoperative rehabilitation with the doses recommended for the prevention of nausea and vomiting; i.e. 8 mg. The single dose administered at the beginning of the procedure (0.1 mg / kg) thus allows both a prevention of PONV and an analgesic benefit [START_REF] Oliveira | Perioperative Single Dose Systemic Dexamethasone for Postoperative Pain: A Meta-analysis of Randomized Controlled Trials[END_REF].

-Drugs ensuring hemodynamic stability:

Opioids have been used because they provide a good hemodynamic stability. It has been shown several times that intraoperative hemodynamic instability is associated with increased postoperative morbidity. Therefore, as P Forget stated [START_REF] Forget | Stable anesthesia with altrenative to opioids: are ketamine and magnesium helpful in stabilizing hemodynamics during surgery? A systematic review and meta-anamysis of randomized controlled trials[END_REF], any strategy oriented to reduce the use of opioids should also minimize the sympathetic response triggered by surgery. Alpha-2 agonists (clonidine, dexmedetomidine (Dex)) have been proposed to ensure this stability. They allow a direct sympathetic blockade. Thanks to their pharmacological characteristics (sedation, hypnosis, anxiolysis, sympatholysis and analgesia), they are interesting adjuvants to multimodal analgesia / anesthesia. Their antinociceptive effects are attributed to the stimulation of alpha-2 adrenergic receptors located in the central nervous system. The analgesic, anti-emetic and anxiolytic properties of clonidine are well known [START_REF] Kock | Intraoperative and postoperative analgesia using intravenous opioid, clonidine and lignocaine[END_REF].

Its use could be limited because of a long delay of action (20 minutes) and a prolonged halflife (15 hours). Dexmedetomidine is a more selective agonist of alpha-2 receptors. Its delay of action is shorter (6 minutes) and its half-life shorter (2 hours) are shorter than those of clonidine. In terms of side effects, both drugs are associated with risks of hypotension and bradycardia [START_REF] Devereaux | Clonidine in patients undergoing noncardiac surgery[END_REF]. Meta-analysis have shown that clonidine and dexmedetomidine Dex provide induce morphine sparing, analgesia with and PONV reduction [START_REF] Blaudszun | Effect of perioperative systemic alpha2 agonists on postoperative morphine consumption and pain intensity: systematic review and meta-analysis of randomized controlled trials[END_REF][START_REF] Schnabel | Is intraoperative dexmedetomidine a new option for postoperative pain treatment? A meta-analysis of randomized controlled trials[END_REF]. The morphine savings of dexmedetomidine Dex were 3 times greater than that of clonidine [START_REF] Blaudszun | Effect of perioperative systemic alpha2 agonists on postoperative morphine consumption and pain intensity: systematic review and meta-analysis of randomized controlled trials[END_REF]. This was not associated with sedative effects delaying postoperative rehabilitation. However, the use of dexmedetomidine Dex was associated with a higher risk of postoperative bradycardia. The clinical relevance and consequences of this side effect are hardly appreciable because none of the studies included in the meta-analysis reported major adverse events. In addition, the definition of bradycardia is unclear in all studies. When comparing intravenous anesthesia with propofol -dexmedetomidine -lidocaine with propofol -remifentanil, in laparoscopic cholecystectomies, patients receiving remifentanil were experiencing experienced more bradycardia than those in the dexmedetomidine Dex group [START_REF] Bakan | Opioid-free total intrvenous anesthesia ith propofol, dexmedetomidine and lidocaine infusions for laparoscopic cholecystectomy: a prospecive, randomized, double-blind study[END_REF]. However, some studies have chosen to study OFA with dexmedetomidine Dex with the objective of hemodynamic stability and controlled hypotension [START_REF] Hamid | Intravenous dexmedetomidine infusion compared with that of fentanyl in patients udergoing arthrospcopic shouder surgery under general anesthesia[END_REF][START_REF] Neil | effect of dexmedetomidine versus fentanyl on haemodynaic response to patients undergoing elective lapascopic surgery : a double-blind randomized controlled study[END_REF]. While some studies were negative [START_REF] Lee | Comparison between dexmedetomidine and remifentanil for controlled hypotension and recovery in endoscopic sinus surgery[END_REF], most studies reported a good hemodynamic stability with often bradycardia and hypotension with dexmedetomidine Dex (which were the objectives in these studies) [START_REF] Goyal | A comparative evaluation of intravenous dexmedetomidine and fentanyl in Breast Cancer surgery: a prospective, randomized and controlled trial[END_REF][START_REF] Vaswani | Comparative study of the effect of dexmedetomidine vs fentanyl on haemodynamic response in patients undergoing elective laparoscopic surgery[END_REF]. This limitation to the systematic use of dexmedetomidine Dex requires further studies whose main objective will be the evaluation of side effects and their clinical consequences.

Beta blockers (BB) have also been proposed to ensure hemodynamic stability during OFA [START_REF] Collard | Intraoperative esmolol infusion in the absence of opioids spares postoperative fentanyl in patients undergoing ambulatory laparoscopic cholecystectomy[END_REF][START_REF] Gelineau | Intraoperative esmolol as an adjunct for perioperative opioid and postoperative pain reduction: a systematic review, metaanalysis and meta-regression[END_REF]. Studies and meta-analysis have reported benefits in reducing intraoperative and postoperative opioids and PONV. However, the literature is scarce on the subject (BB used during an OFA) and perioperative administration of beta blockers is associated with specific side effects including a doubt in increasing the risk of stroke [START_REF] Group | Effects of extended-release metoprolol succinate in patients undergoing non-cardiac surgery (POISE trial): a randomised controlled trial[END_REF].

What are the benefits of OFA?

The isolated administration of the previously presented drugs does not allow to perform anesthesia without opioids. None of the drugs introduced before allows by one-self performing anesthesia without opioids. However, their association with modern techniques of anesthesia and surgery is an alternative to the use of opioids. Hanci et al [START_REF] Hanci | Effects of fentanyl-lidocaine-propofol and dexmedetomidine-lidocaine-propofol on tracheal intubation without use of muscle relaxants[END_REF] compared intubation conditions during lidocaine and propofol-associated anesthesia with dexmedetomidine Dex or fentanyl. The intubation conditions were better in the dexmedetomidine Dex group. They reported more bradycardia (lower low limit: 60 bpm) in the dexmedetomidine Dex group and more hypotension in the fentanyl group, with no major adverse effects events reported. Another older study compared dexmedetomidine Dex and fentanyl during an inhaled desflurane anesthesia for bariatric surgery [START_REF] Feld | Fentanyl or dexmedetomidine combined with desflurane for bariatric surgery[END_REF]. For a comparable depth of anesthesia monitored by BIS, dexmedetomidine The Dex allowed desflurane savings for an identical depth of anesthesia measured by BIS, a morphine saving and better analgesia. OFA has been shown Morphic sparing with OFA was shown to result in a significant reduction in PONV: Ziemann-Gimmel et al [START_REF] Ziemann-Gimmel | Opioid-free total intravenous anaesthesia reduces postoperative nausea and vomiting in bariatric surgery beyond triple prophylaxis[END_REF] demonstrated a 17% reduction in the risk of PONV by comparing an intravenous anesthesia combining propofoldexmedetomidine Dex -ketamine with an inhaled anesthesia with opioids. More recently, Mulier et al reported, in a small randomized controlled trial RCT (n = 50) the benefits of modern OFA (propofol, rocuronium, dexmedetomidine Dex, lidocaine, ketamine) when compared with OBA (propofol, rocuronium, sufentanil) during bariatric surgery [START_REF] Mulier | A randomized controlled, double-blind trial evaluating the effect of opioid-free versus opioid general anesthesia on postoperative pain and discomfort measured by the QoR40[END_REF]. OFA was associated with a better recovery, better comfort (QoR-40 score), reduced postoperative pain while consuming less postoperative morphine, reduced PONV and less postoperative oxygen desaturation. In a second publication study [START_REF] Mulier | Anesthetic factors affecting outcome after bariatric surgery, a retrospective levelled regression analysis[END_REF], performed in they retrospectively reported in 9246 patients who underwent bariatric surgery, they retrospectively reported that OFA was associated with less postoperative complications. Meta-analysis have also reported benefits with OFA [START_REF] Frauenknecht | Analgesic impact of intraoperative opioids vs. opioid-free anaesthesia: a systematic review and metaanalysis[END_REF][START_REF] Singh | Perioperative analgesic profile of dexmedetomidine infusions in morbidly obese undergoing bariatric surgery: a metaanalysis and trial sequential analysis[END_REF][START_REF] Tsaousi | Dexmedetomidine as a sedative and analgesic adjuvant in spine surgery: a systematic review and meta-analysis of randomized controlled trials[END_REF]. However, results have to be analyzed with caution as the heterogeneity of the studies included was high (i.e. 83 % in Frauenknecht et al [START_REF] Frauenknecht | Analgesic impact of intraoperative opioids vs. opioid-free anaesthesia: a systematic review and metaanalysis[END_REF]). In addition, and all these meta-analysis included some studies in which dexmedetomidine Dex was administered as the same time as opioids. More well-designed large-scale studies are definitely needed required to further document show the benefits of OAF for the patients.

There are currently 14 on going trials registered on clinical trial.gov on this topic.

Are there specific indications for OFA?

Patients who can benefit from this type of anesthesia OFA are those who are most sensitive to deleterious side effects of opioids. Obese patients and patients suffering from respiratory insufficiency are, of course, crossing mind firstly the first to come to mind. Morphine administration is associated with an abnormal respiratory cycle (alternating respiratory depression with airway obstruction) [START_REF] Drummond | Characterization of breathing patterns during patient-controlled opioid analgesia[END_REF]. This is accentuated and aggravated in obese patients with sleep apnea syndrome [START_REF] Drummond | Characterization of breathing patterns during patient-controlled opioid analgesia[END_REF]. Thus, part of the studies showing the interest of dexmedetomidine Dex perioperatively, were made performed in obese patients [START_REF] Singh | Perioperative analgesic profile of dexmedetomidine infusions in morbidly obese undergoing bariatric surgery: a metaanalysis and trial sequential analysis[END_REF]. Several clinical cases and studies have described the benefit of morphine-free anesthesia with dexmedetomidine Dex in super-obese patients (BMI> 50 kg / m2) [START_REF] Martinez | Non-opioid analgesics in adults after major surgery: systematic review with network meta-analysis of randomized trials[END_REF][START_REF] Oliveira | Perioperative Single Dose Systemic Dexamethasone for Postoperative Pain: A Meta-analysis of Randomized Controlled Trials[END_REF]. Other studies are obviously needed to evaluate the real benefit of opioid-free anesthesia in these patients. It can also be assumed that OFA would be beneficial in patients with respiratory insufficiency or obstructive bronchopneumopathy. Data are missing to date to validate these indications.

Another subgroup of patients suffering from chronic pain and / or consuming opioids before surgery, would be another subpopulation that could benefit the most from OFA. These patients are at higher risk of more intense severe postoperative acute pain while consuming more postoperative opioids [START_REF] Montes | Genetic and Clinical Factors Associated with Chronic Postsurgical Pain after Hernia Repair, Hysterectomy, and Thoracotomy: A Two-year Multicenter Cohort Study[END_REF]. It has been shown that all this increases the risk of postsurgical pain chronicization [START_REF] Montes | Genetic and Clinical Factors Associated with Chronic Postsurgical Pain after Hernia Repair, Hysterectomy, and Thoracotomy: A Two-year Multicenter Cohort Study[END_REF]. One could hypothesize that reducing the activation of NMDA receptors and therefore opioid-induced hyperalgesia by avoiding intraoperative opioids could reduce postoperative acute and chronic pain and opioid needs in these patients. However, no data are currently available to confirm this hypothesis.

The question also arises for oncological cancer surgery (see chapter on postoperative pain after cancer). The Opioids impair cell proliferation, inflammation, angiogenesis and the immune response. This could participate in the evolution of the tumor. However, the interactions and cellular mechanisms involved in the role played by opioids in cancer recurrence are complex and far from fully understood, as the pain itself is immunosuppressive [START_REF] Afsharimani | Morphine use in cancer surgery[END_REF]. Clinical data on the potential implication of opioids on cancer recurrence are contradictory. No evidence-based proofs are available today to formally suggest that opioids should be avoided during surgery for cancer.

Finally, intuitively, one could suggest that the more painful and the longer the surgery, the bigger greater the impact of opioid-sparing strategies would be. However, well-designed RCTs are needed to confirm this suggestion.

Unanswered questions and future research agenda

OFA is a multimodal anesthesia and therefore consist of a combination of multiple drugs.

Many institutions have their own 'cocktail', some of them are even published [START_REF] Mauermann | Different protocols used today to achieve total opioid-free general anesthesia without locoregional blocks[END_REF]. However, as presented above, the proofs of the benefits of such combinations of multiple drugs are still scarce in the literature [START_REF] Lirk | Opioid-free anaesthesia: Con: it is too eraly to adopt opioid-free anaesthesia today[END_REF]. 'Cocktails' published without any evidence-based proof of a positive balance of benefits over risks should not be recommended. Moreover, the doses of each of the drugs included in the 'cocktail' are also not clearly defined especially for dexmedetomidine Dex. As presented shown in table 1, doses vary from one study to another, and no formal recommendation can be formulated. The optimal dose of dexmedetomidine Dex allowing benefits with acceptable risks of bradycardia and hypotension has not been determined yet.

As stated by P Lavand'homme in a recent editorial [START_REF] Lavand | Opioid-free anesthesia: Pro: damned if you don't use opioids during surgery[END_REF], there is an urgent need to develop accurate monitoring of intraoperative nociception.

Finally, most publications on OFA involved patients undergoing bariatric surgery. There is a lack of studies showing benefits in other types of surgery. Procedure-specific studies and protocols are needed.

Conclusion

Some authors present opioid-free anesthesia as a new paradigm that will revolutionize and change our practices in the years to come. While it is true that multimodal anesthesia like multimodal analgesia has shown benefits, studies and data are lacking. In terms of benefits, OFA has never been studied with modern monitoring of intraoperative analgesia. Evidencebased proofs of short and long-term benefits of OFA as well as well documented intraoperative protocols are still yet to come.

Conflict of interest:

Helene Beloeil has received honoraria from Orion, BBraun and Abbvie.

Legends of the tables: Table 1:

Randomized controlled trials comparing opioid-free anesthesia using dexmetedomidine vs opioid-based anesthesia. LOS: length of stay; HR: heart rate; MBP: mean blood pressure Dex: dexmetedomidine; NS: non-statistically significant; NA: non-applicable.


Maksim Koptelov
email: maksim.koptelov@unicaen.fr

Albrecht Zimmermann
email: albrecht.zimmermann@unicaen.fr

Bruno Crémilleux
email: bruno.cremilleux@unicaen.fr

Lina Soualmia
email: lina.soualmia@chu-rouen.fr

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

Keywords: • Mathematics of computing → Graph algorithms, • Information systems → Data mining, Recommender systems, Decision support systems, • Applied computing → Bioinformatics, multi-layer graphs, bipartite graphs, graph mining, link prediction, community detection

The growing number of multi-relational networks pose new challenges concerning the development of methods for solving classical graph problems in a multi-layer framework, such as link prediction. In this work, we combine an existing bipartite local models method with approaches for link prediction from communities to address the link prediction problem in multi-layer graphs. To this end, we extend existing community detection-based link prediction measures to the bipartite multi-layer network setting. We obtain a new generic framework for link prediction in bipartite multi-layer graphs, which can integrate any community detection approach, is capable of handling an arbitrary number of networks, rather inexpensive (depending on the community detection technique), and able to automatically tune its parameters. We test our framework using two of the most common community detection methods, the Louvain algorithm and spectral partitioning, which can be easily applied to bipartite multi-layer graphs. We evaluate our approach on benchmark data sets for solving a common drug-target interaction prediction task in computational drug design and demonstrate experimentally that our approach is competitive with the state-of-the-art.

INTRODUCTION

Many real world applications can be modeled as bipartite graphs, vertices of which are divided into two distinct groups [START_REF] Sun | Neighborhood formation and anomaly detection in bipartite graphs[END_REF]. The problem setting that motivates our work is the prediction of links between drug candidates and biological targets, an essential step of computational drug design. But there are other link prediction settings that fall into the same category, for instance user-product recommendation.

The available data on drug-target interaction prediction are of heterogeneous structure, i.e. represented by networks the edges of which have different origins. This makes the straightforward use of most existing link prediction methods impossible. Current solutions are limited by the number or type of networks, often referred to as layers, e.g. three layers, with two assumed to be similarity networks [START_REF] Buza | ALADIN: A New Approach for Drug-Target Interaction Prediction[END_REF][START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF][START_REF] Lim | Improved genomescale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem[END_REF].

To address these restrictions, we take inspiration from existing methods that use community detection to perform link prediction [START_REF] Guimerà | Missing and spurious interactions and the reconstruction of complex networks[END_REF][START_REF] Soundarajan | Using community information to improve the precision of link prediction methods[END_REF][START_REF] Valverde-Rebaza | Link prediction in online social networks using group information[END_REF][START_REF] Yan | Finding missing edges in networks based on their community structure[END_REF]. While this decouples the problem into how to find communities in multi-layer graphs, and how to exploit them for prediction, existing link prediction measures [START_REF] Cannistraci | From linkprediction in brain connectomes and protein interactomes to the localcommunity-paradigm in complex networks[END_REF][START_REF] Ding | Prediction of missing links based on community relevance and ruler inference[END_REF][START_REF] Xie | Potential links by neighbor communities[END_REF] are not directly applicable to the bipartite setting. To address this restriction, we extend several of those measures to our problem setting. In addition, we go a step further by proposing alternatives to those measures based on an existing bipartite local model. While we evaluate two concrete approaches for community detection, spectral partitioning and the Louvain algorithm, both of which can be easily applied to multi-layer graphs, we do not require any particular community detection approach. Our long-term contribution is the adaptation of existing link-prediction-bycommunity-detection measures to the bipartite multi-layer setting, which we evaluate experimentally, and the selection of the best measure and community detection approach combination. In addition, we demonstrate that the parameter settings of the community detection methods can be effectively set via internal cross-validation.

The rest of the paper is organized as follows. Section 2 discusses related work on link prediction and community detection in multi-layer networks. Section 3 provides basic notations and definitions. Section 4 explains how we adapt existing measures for our framework. Section 5 describes the data used for evaluation, the experimental setup and presents the results. Finally, Section 6 concludes and outlines future work.

RELATED WORK

Existing methods for link prediction in bipartite multi-layer networks for addressing the drug-target interaction problem can be grouped into three classes: similarity, random-walker, and latent models based. The first group assumes 2 out of 3 possible layers to be similarity networks for drugs and targets respectively, and exploits similarity information to perform link prediction on the third bipartite layer [START_REF] Buza | ALADIN: A New Approach for Drug-Target Interaction Prediction[END_REF][START_REF] Ding | Similarity-based machine learning methods for predicting drug-target interactions: a brief review[END_REF]. The second models the behavior of a random-walker to perform link prediction in multi-layer graph using PageRank adaptations [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF][START_REF] Cheng | Prediction of chemical-protein interactions network with weighted network-based inference method[END_REF][START_REF] Koptelov | Link Prediction in Multi-layer Networks and Its Application to Drug Design[END_REF]. Such methods are dependent on fixing the similarity networks and while the approach was extended to any number of networks in [START_REF] Koptelov | Link Prediction in Multi-layer Networks and Its Application to Drug Design[END_REF], it pays for this flexibility with high computational cost. The last group of methods maps drugs, targets and their interactions into a combined feature space, and performs drug-target interaction prediction using distance functions or regression analysis [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF][START_REF] Zheng | Collaborative matrix factorization with multiple similarities for predicting drugtarget interactions[END_REF]. The most recent family of methods in this mold is often referred to as graph embeddings [START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF]. The main disadvantage of this group of methods is a certain lack of interpretability.

The idea to use community information to predict links in graphs is not novel. Clauset et al. [START_REF] Clauset | Hierarchical structure and the prediction of missing links in networks[END_REF] proposed to exploit a learned hierarchical generative community model to estimate the probabilities of missing links in partially known networks. The authors of [START_REF] Guimerà | Missing and spurious interactions and the reconstruction of complex networks[END_REF][START_REF] Valverde-Rebaza | Link prediction in online social networks using group information[END_REF][START_REF] Yan | Finding missing edges in networks based on their community structure[END_REF] combine community detection with existing edge prediction methods to improve prediction accuracy. These methods are based on the hypothesis that vertices in the same community have similar properties, and missing edges are more likely to be found within communities. Missing edges are predicted by node similarity using nearest-neighbor measures [START_REF] Yan | Finding missing edges in networks based on their community structure[END_REF], Stochastic Block Models [START_REF] Guimerà | Missing and spurious interactions and the reconstruction of complex networks[END_REF], or in-group/out-group neighbor similarity measures [START_REF] Valverde-Rebaza | Link prediction in online social networks using group information[END_REF]. Edges can be predicted for vertices belonging to the same community even if there is no path between them within the community [START_REF] Jalili | Link prediction in multiplex online social networks[END_REF]. The density of links in a particular community or between two communities can be exploited in a naïve Bayes model [START_REF] Liu | Correlations between community structure and link formation in complex networks[END_REF]. The authors of [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF] reimagine communities as groups of edges rather than vertices, and [START_REF] Soundarajan | Using community information to improve the precision of link prediction methods[END_REF] use community detection to modify similarity measures. Finally, there is a set of methods which extend the concept of shared neighborhoods [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF] to community neighborhoods [START_REF] Cannistraci | From linkprediction in brain connectomes and protein interactomes to the localcommunity-paradigm in complex networks[END_REF][START_REF] Ding | Prediction of missing links based on community relevance and ruler inference[END_REF][START_REF] Xie | Potential links by neighbor communities[END_REF]. In addition, in [START_REF] Hristova | A multilayer approach to multiplexity and link prediction in online geo-social networks[END_REF] neighborhood measures have been extended to multiple layers.

Community detection in multi-graphs can also be performed in different ways: directly, by ensemble-based methods, or by graph flattening. The direct methods perform discovery of communities on the multi-layer network directly, e.g. by adapting objective functions for community detection to the multi-layer setting [START_REF] Bacco | Community detection, link prediction, and layer interdependence in multilayer networks[END_REF][START_REF] Kuncheva | Community detection in multiplex networks using locally adaptive random walks[END_REF][START_REF] Tagarelli | Ensemble-based community detection in multilayer networks[END_REF]. Ensemble-based methods perform community detection on each layer separately, and aggregate discovered communities afterwards [START_REF] Tagarelli | Ensemble-based community detection in multilayer networks[END_REF]. Flattening approaches, finally, summarize multiple edges into single ones and use the resulting single-layer network to discover communities by using one of the common community detection approaches such as spectral partitioning [START_REF] Leskovec | Mining of massive datasets[END_REF] or Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. In this work, we use the last type of approach due to their ease of use and potentially low computational complexity.

DEFINITIONS AND PROBLEM SETTING 3.1 Basic notations

A graph is a tuple G =< V , E >, where V = {v 1 , v 2 , ..., v n } denotes a set of vertices or nodes, and E ⊆ V × V a set of edges defined by distinct vertex pairs (u, v) ∈ V × V with u v (without self-loops). We also use the notion of a bipartite graph, which we define as a graph whose vertices can be divided into two classes V 1 and V 2 such that there is no edge between vertices of the same class:

G =< V 1 ∪ V 2 , E >, E ⊂ V 1 × V 2 .
We address weighted and unweighted graphs in the same manner. We define a weighted graph as one with a labeling function for edges E → A e with A e ∈ [0, 1], where 0 denotes that there is no interaction between vertices, 1 confirmed interaction, and an intermediate value represents an interaction probability. An unweighted graph is one where every edge is labeled by 1. To exploit different sources of information in one single structure, we employ multi-layer networks. We define a multi-layer network as a weighted graph where more than one edge (u, v) can exist for a pair of vertices u, v. Multi-layer networks can be decomposed into disjunct set of graphs G l that contain at most a single edge for each pair of vertices, called layers or just networks. As we wrote above, our original setting is a bipartite one. To combine it with the multilayer framework, we define a bipartite multi-layer graph as a multi-layer network whose vertices can be divided into two classes, and where exactly one of the layers is a bipartite graph (see Fig. 1 for an example). Note, following Kivelä et al. [START_REF] Kivelä | Multilayer networks[END_REF], the multi-layer networks used in this work are not node-aligned 1 , not layer-disjoint 2 , have diagonal couplings 3 which are categorical 4 , and the number of layers can be any.

We represent graphs as matrices. The adjacency matrix A has size n × n, n = |V |, and A i j represents the weight of the edge (v i , v j ). In the case of multi-layer networks, we aggregate the weights of multiple edges between v i and v j by summing them up. Note that A has zeros on the main 1 All nodes are shared between all layers 2 Each node is present only in a single layer 3 Inter-layer edges, that cross layers, are only between nodes and their counterparts 4 Diagonal couplings for which all possible inter-layer edges are present diagonal, because graphs as used in this work have no selfloops. The degree matrix D is the diagonal matrix

D =        deд(v 1 ) 0 . . . 0 . . . 0 0 deд(v n )        , deд(v i ) = n j=1 A i j
of same size as A, where deд(v i ) represents the degree of vertex v i . The degree of a vertex is the sum of the weights of the edges adjacent to v i [START_REF] Gallier | Notes on Elementary Spectral Graph Theory[END_REF].

The last, and arguably most important, matrix used in this paper is the Laplacian matrix. The Laplacian matrix, denoted by L, is a matrix of the same dimensionality as A and D, defined as the difference between the degree matrix and the adjacency matrix: L = D -A. L has the same values as D on the diagonal, and off the diagonal L i j is equal to -A i j .

Problem setting

We define the problem of link prediction in bipartite multilayer graph addressed in this paper as follows.

For a given bipartite multi-layer graph

G = G V 1 V 2 ∪ G (n) V 1 ∪ G (m)
V 2 with 1 + n + m layers, where:

• G V 1 V 2 = ⟨V 1 ∪V 2 , E i , λ v , λ e V 1 V 2 ⟩ is a bipartite layer with u ∈ V 1 labeled with identifiers of type V 1 , v ∈ V 2 labeled with identifiers of type V 2 , ∀(u, v) ∈ E, u ∈ V 1 , v ∈ V 2 and λ e V 1 V 2 : E V 1 V 2 → {0, 1}, • G i V 1 = ⟨V 1 , E i V 1 , λ v , λ e i V 1 ⟩, λ e i V 1 : E i V 1 → [0, 1] are layers of type V 1 , • G i V 2 = ⟨V 2 , E i V 2 , λ v , λ e i V 2 ⟩, λ e i V 2 : E i V 2 → [0, 1] are layers of type V 2 , Predict, whether for a given (u, v) E, u ∈ V 1 , v ∈ V 2 λ e ((u, v)) = 1.
We limit ourselves to predict whether there is an activity or not, leaving the prediction of its strength as future work.

OUR APPROACH

In our problem setting, we want to predict links between two distinct types of nodes, e.g. drugs and targets in our experiments (see Fig. 1). To achieve this, we perform community discovery using an existing community detection approach, then exploit the discovered communities to solve the link prediction task.

Link prediction by community detection in a bipartite setting

To be able to use existing link-prediction-by-communitydetection measures, we have to adapt them to the bipartite setting. Due to the construction of the networks we use and the community detection methods we evaluate, resulting communities can be mixed, i.e. containing both types of nodes, drugs and targets, as well as pure, of either type, drugs or targets only. Also, the community detection methods we use produce non-overlapping communities only. Mixed communities can be exploited directly with existing measures for link prediction via community detection (see Section 2), but pure communities cannot, ignoring a large number of drug-target pairs. To overcome this, we treat all communities as non-mixed and split mixed communities into pure ones. Notably, this split does not have to be done explicitly, but a mixed community can be treated as two pure ones with links between them. We exploit discovered communities in one of two proposed ways: by matching "community to community" or "node to community".

4.1.1 Community to community. In this case, each drug community is paired with each target community, then an adapted measure is used to perform link prediction between paired communities. Each non-interacting drug-target pair between paired communities is assigned the same link probability score. At the end of the matching, each non-interacting drug-target pair from the network will have been assigned a single score, which can be used to rank predictions. We refer to this approach as community to community (or CC).

In the example shown in Figure (Fig. 2), for instance, community C1 is twice connected to community C3 and twice to community C4. C2, on the other hand, is connected once to C3 and once to C4. This matching therefore implicitly assumes that all ligands in C1 have a connection of strength two to all targets in C3 etc. The big advantage of this matching is that even vertices that have no bipartite connection at all can receive a positive score.

4.1.2 Node to community. Another way of exploiting communities is to pair each node of one type with communities of the other type. The advantage of that method is that for a selected drug d i and target t j , the prediction can be made twice: once analyzing connections of a drug with target communities and second analyzing target connections with drug communities, providing a more reliable estimate. This approach is also referred to as Bipartite Local Models [START_REF] Bleakley | Supervised prediction of drugtarget interactions using bipartite local models[END_REF].

Figure 3 illustrates an NC matching that is equivalent to the CC matching in Figure 2: l1 is connected twice to C3 and once to C4, and l2 once to C3, while t1 is connected twice to C1 and once to C2, and t2 once to C1, for instance. For the rest of the figure: l3 is connected once to C4, l4 once to C3 and once to C4, l5 neither to C3 nor C4. t3 is connected once to C1, once to C2, t4 is connected once C1, once to C2.

Vertices belonging to the same community will therefore not necessarily receive the same score but a vertex such as l5 will be strongly punished because it is not connected with a bipartite edge. The link probability score between d i and t j is computed by aggregating the two results [START_REF] Buza | ALADIN: A New Approach for Drug-Target Interaction Prediction[END_REF]. We report results using mean as an aggregation function. Our experiments showed that the difference between max and mean is negligible, and we use mean to get a more reliable result. We do not consider min as aggregator, because in the case of no evidence for existence of the link in one of the independent predictions the combined probability is also 0. We refer to this approach as node to community (or NC).

Adapting existing link prediction measures

We divide all existing link prediction measures into two broad categories: neighborhood measures and others, which we refer as community-based. The first group of measures are based on the notion of neighborhood, i.e. the set of vertices directly connected to the examined vertices. The semantic similarity between neighborhood and community, i.e. sets of vertices in both cases, allows us to use neighborhood measures in our setting. The other measures are not based on a notion of neighborhood, but on other metrics, and thus are grouped into a separate group in our work.

Neighborhood measures.

Many existing link prediction measures exploit the neighborhoods of vertices e.g. in the form of common neighbors (CN), the Jaccard coefficient (JC), preferential attachment (PA), or SimRank (SR) [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF]: Γ denotes the weight of a neighborhood of a vertex, which for the individual vertices is equivalent to their degree. Due to the nature of communities we obtain, there is little overlap between vertices' neighborhoods, preventing the direct use of neighborhood-based measures. To overcome this, we adapt neighborhood measures for use with our communities, treating them like neighborhoods: the CN measure turns the number of common neighbors of communities d i and t j into the number of connections, JC represents the fraction of all possible connections of d i and t j that are connected to both, PA is defined by a product of degrees of communities d i and t j , finally SR is equal to the number of connections of communities d i and t j normalized by the product of their degrees. Using the CC and NC formulations, our bipartite adaptations take the form:

CN (d i , t j ) = |{v | (d i , v) ∈ E} ∩ {u | (t j , u) ∈ E}|, (1) JC(d i , t j ) = CN (d i , t j ) |{v | (d i , v) ∈ E} ∪ {u | (t j , u) ∈ E}| , (2)
PA(d i , t j ) = Γ(d i )•Γ(t j ), with Γ(d i ) = |V | k =1 A ik , Γ(t j ) = |V | k =1 A jk , (3)
SR(d i , t j ) = CN (d i , t j ) PA(d i , t j ) . (4)
(1) Instead of the measures from Eq. 1-4 we define CN CC , JC CC , PA CC and SR CC versions corresponding to CC matching:

CN CC (d i , t j ) = |{(d, t) ∈ E | d ∈ C(d i ), t ∈ C(t j )}|, (5)
JC CC (d i , t j ) = CN CC (d i , t j ) |C(d i )| • |C(t j )| , (6)
PA CC (d i , t j ) = Γ(C(d i )) • Γ(C(t j )), (7)
SR CC (d i , t j ) = CN CC (d i , t j ) PA CC (d i , t j ) , (8)
where C(d i ), C(t j ) represent communities of a drug d i and a target t j respectively. We overload Γ for communities as

Γ(C(v)) = v ∈C(v),u C(v) w(v, u).
(2) The NC version of CN is defined as the average of the two independent predictions,

CN N C (d i ) = |{t | (d i , t) ∈ E, t ∈ C(t j )}|, CN N C (t j ) = |{d | (t j , d) ∈ E, d ∈ C(d i )
}|, for d i , and t j respectively:

CN N C (d i , t j ) = 1 2 CN N C (d i ) + CN N C (t j ) . (9)
In the same manner, we can define NC versions for other measures from [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF], the JC (Eq. 10), PA (Eq. 11) and SR (Eq. 12), taking into account that

PA N C (d i ) = Γ(d i ) • Γ(C(t j )) and PA N C (t j ) = Γ(t j ) • Γ(C(d i )): JC N C (d i , t j ) = 1 2 CN N C (d i ) |C(t j )| + CN N C (t j ) |C(d i )| , (10)
PA N C (d i , t j ) = 1 2 (PA N C (d i ) + PA N C (t j )), (11)
SR N C (d i , t j ) = 1 2 CN N C (d i ) PA N C (d i ) + CN N C (t j ) PA N C (t j ) . ( 12
)
4.2.2 Community-based measures. Other measures proposed in the literature are based on one or several of the following assumptions: all vertices have the same semantic, all edges have the same semantic, edges are unweighted, or vertices whose link is to be predicted find themselves in the same community. We therefore cannot use most of the measures proposed in the literature but we can adapt some to our bipartite setting.

(1) Cannistraci et al. [START_REF] Cannistraci | From linkprediction in brain connectomes and protein interactomes to the localcommunity-paradigm in complex networks[END_REF] in their CAR-based measures propose to exploit the density of communities to reward (or penalize) densely (sparsely) connected neighbors of the vertices whose link is to be predicted. Our adapted CAR-based common neighbors (CCN) will be defined as CN regularized by community local degree, in turn defined as the sum of weights of all edges inside community. The NC formulation of CCN takes the form:

CCN N C (d i , t j ) = 1 2 CCN N C (d i ) + CCN N C (t j ) , (13)
with CCN N C (d i ) and CCN N C (t j ) in turn defined as:

CCN N C (d i ) = |{t | (d i , t) ∈ E, t ∈ C(t j )}|• t l ,t k ∈C(t j )
A(t l , t k ) and

CCN N C (t j ) = |{t | (t j , d) ∈ E, d ∈ C(d i )}|• d l ,d k ∈C(d i ) A(d l , d k ).
In the same manner, the CAR-based Jaccard coefficient (CJC) is redefined as CCN normalized by the size of the community:

C JC N C (d i , t j ) = 1 2 C JC N C (d i ) + C JC N C (t j ) , (14)
with

C JC N C (d i ) = CCN N C (d i ) |C(t j )| and C JC N C (t j ) = CCN N C (t j ) |C(d i )| .
(2) Xie et al. [START_REF] Xie | Potential links by neighbor communities[END_REF] propose to exploit the connection of vertices to communities, summing over all communities.

Our adaptation of their measure, which we refer to as Neighboring community-based (NCB) is defined as the normalized sum of all CN regularized by the size of the respective community. The NC formulation of this measure will take the form:

NCB N C (d i , t j ) = 1 2 NCB N C (d i ) + NCB N C (t j ) , (15)
with NCB N C (d i ) and NCB N C (t j ) in turn:

NCB N C (d i ) = c t k =1 |{t | (d i , t) ∈ E, t ∈ C k }| |C k | • |{t | t ∈ C k }| |T | and NCB N C (t j ) = c d k =1 |{d | (t j , d) ∈ E, d ∈ C k }| |C k | • |{d | d ∈ C k }| |D| .
Moreover, assuming communities are pure, i.e. consisting only of either drugs or targets, these equations can be simplified to the sum of all CN normalized by the number of vertices of one type:

NCB N C (d i ) = 1 |T | c t k =1 |{t | (d i , t) ∈ E, t ∈ C k }|, NCB N C (t j ) = 1 |D| c d k =1 |{d | (t j , d) ∈ E, d ∈ C k }|.
(3) Ding et al. [START_REF] Ding | Prediction of missing links based on community relevance and ruler inference[END_REF], finally, propose to exploit the neighborhoods of communities. Our adaptation of their measure, called Community relevance Jaccard coefficient (CRJC), is defined as the number of common nodes of examined communities and nodes of the opposite type connected to those communities normalized by the total number of nodes in this selection. The adapted measure is better suited to a CC formulation:

CRJC CC (d i , t j ) = |CRJC CC (d i ) ∩ CRJC CC (t j )| |CRJC CC (d i ) ∪ CRJC CC (t j )| , (16)
with CRJC CC (d i ) and CRJC CC (t j ) in turn:

CRJC CC (d i ) = {t | (d, t) ∈ E, d ∈ C(d i )}∪{d | d ∈ C(d i )} and CRJC CC (t j ) = {d | (t, d) ∈ E, t ∈ C(t j )} ∪ {t | t ∈ C(t j )}.

EXPERIMENTAL EVALUATION

To evaluate the two community detection methods, effects of their parameter settings, and prediction measures defined in the preceding section, we performed experiments on several benchmark data sets for drug-target activity prediction.

Experimental setup

We begin by evaluating the different measures described in Section 4 with two common community detection approaches, keeping most of the parameters fixed, and select the best performing measure. Following this, we show how an internal cross-validation can be used to fixed a methods' parameters, and report on their results, which we compare to the state-of-the-art.

We also perform experiments on the larger and more challenging IUPHAR data set and give some scalability results. The results of those experiments can be found in our supplementary material 5 .

Community detection methods.

We test our approach with spectral partitioning [START_REF] Leskovec | Mining of massive datasets[END_REF] and the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] as community detection methods. The first finds the best cut to partition nodes based on eigenvalues of the Laplacian matrix and a threshold method [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Spielman | Spectral partitioning works: Planar graphs and finite element meshes[END_REF], the second greedily optimizes modularity, a generic measure to determine the quality of any partition produced by a community detection method [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. We apply spectral partitioning to multilayer graphs by "flattening" the graph, i.e. summing edge weights to derive the adjacency and degree matrices before performing partitioning. Since Louvain does not employ matrices, we translate the graph into a single-layer graph by summing up the weights of all edges between two vertices. 5.1.2 Parameters to optimize. Spectral partitioning has two parameters: the value of m and the thresholding method. The m parameter represents the number of eigenvectors corresponding to the m smallest non-zero eigenvalues used to partition the graph into at most 2 m groups. As thresholding methods we can use sign cut (or default), which partitions entries based on whether they are greater or less than zero, bisection cut (or median), using the median value of entries in an eigenvector as a threshold, producing two components of approximately equal size [START_REF] Guattery | On the performance of spectral graph partitioning methods[END_REF]. We also evaluate mean, which uses the average, and sum that exploits the fact that there are approximately equally as many positive and negative values in eigenvectors of Laplacian matrix, i.e. in practice they sum to a value close to zero. Moreover, the same threshold can be applied to all eigenvectors, or each individual eigenvector can have its own threshold. We call the former approach global, and the latter individualized. Additionally, the global threshold can be computed by applying the aggregating function (mean, median or sum) to all eigenvectors or only to the m actually used. We refer to this latter type as localized.

To sum up, we evaluate 9 different thresholding methods: global, localized, individualized and their combinations with mean, median and sum. The combination global sum is a special case since taking the first eigenvector, whose entries all have the same, positive value, into account violates the "close to zero" property sum thresholding exploits. We therefore do not evaluate that thresholding method, but add default thresholding to the mix for the experimental evaluation.

The Louvain algorithm has only one parameter -resolution limit -which defines a modularity scale. Practically speaking, at different moments of time t, the difference between optimal partitioning and partitioning produced by the Louvain is various and the resolution parameter represents this change in time [START_REF] Lambiotte | Laplacian dynamics and multiscale modular structure in networks[END_REF].

Data sets.

We perform our experiments on the data sets introduced in [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF]: Enzyme, G-protein coupled receptors (GPCR), Ion Channels (IC) and Nuclear Receptors (NR). In addition, we use the Kinase set [START_REF] Davis | Comprehensive analysis of kinase inhibitor selectivity[END_REF]. These data sets have been used in prior work on drug-target interaction prediction [START_REF] Buza | ALADIN: A New Approach for Drug-Target Interaction Prediction[END_REF][START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF][START_REF] Lim | Improved genomescale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem[END_REF][START_REF] Zheng | Collaborative matrix factorization with multiple similarities for predicting drugtarget interactions[END_REF], and can be considered benchmarks. The data consist of 3 networks: drug similarities, target similarities and drug-target interaction (the bipartite graph). The data sets' basic properties are presented in Table 1.

Evaluation protocol and quality measures.

To perform evaluation of our experiments, we performed a 5×5fold cross-validation, with each fold containing 20% of all drug-target interactions, acting as test set for link prediction once, while community detection is performed on the other 80%. The process is repeated 5 times, the results are averaged among all runs. We evaluate all the predictions by AUC (Area Under ROC Curve) and AUPR (Area Under Precision-Recall Curve), averaging the results. 5.1.5 Implementation. We implemented spectral partitioning and link prediction measures in Python 6 , and we used python-louvain package as implementation of Louvain.

Experimental results

Link prediction measures evaluation.

We first test the different link prediction measures from Section 4 on communities produced by either spectral partitioning or the Louvain algorithm. To reduce computational complexity, we use default parameters for community detection: default as threshold for spectral partitioning and 1.0 as resolution limit for the Louvain algorithm. Note that we optimize m for spectral partitioning on the test data in this experiment, 6 https://zimmermanna.users.greyc.fr/supplementary-material.html because there is no a priori number of eigenvalues that will fit all data. The results are presented in Fig. 4, with community to community formulations on the left, node to community ones on the right of each plot. The best-performing measure for each group is indicated by a + sign over the corresponding bar. We also report on the figure the optimal m value for every measure in spectral partitioning.

The results show that a number of measures, e.g. SR CC , CN N C , SR N C , CCN N C , C JC N C , NCB N C , have acceptable performance in terms of AUC on most of data sets while the Jaccard coefficient usually performs best for both the CC and NC versions. These two, JC CC and JC N C , are therefore the measures we will use going forward. Another result is that for these parameter settings spectral partitioning and the Louvain algorithm give approximately the same AUC, but the latter improves on AUPR. Finally, using node to community predictions requires a lower m, i.e. less fine-grained partitions, for spectral partitioning.

5.2.2

Parameter selection via internal cross-validation and state of the art comparison. In link prediction, as in any other predictive task, the main issue is choosing parameter values, in the case of spectral partition m and the thresholding method, in the case of Louvain the resolution limit. In the absence of other knowledge, one would use cross-validation as a systematic method to optimize parameters. Several-fold cross-validation is also the method of choice to evaluate the performance of a classifier, however, so that we use a double cross-validation in this section: splitting off an external test fold (containing 20% of present edges) to evaluate the model, and using an internal five-fold cross-validation to fix the model's parameters.

During the internal cross-validation, we performed grid search over the different parameter settings, varying m in the interval [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF][START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF], and testing this value with all nine options for thresholding. We report averaged results using mean.

Table 2 presents the results for spectral partitioning. It shows both the results of internal evaluation, i.e. on the validation set used to fix parameter values, and of the external evaluation, i.e. on the unseen training data. The main conclusion to draw is that those values align very closely w.r.t. AUC, i.e. that there is no risk of overfitting when building the model. Concerning AUPR, interestingly enough, the results on the testing folds are in fact higher than for the validation data used in the internal cross-validation. Notably, using NC matching always gives better results than CC matching, often by a large margin.

The only parameter to optimize for Louvain is the resolution parameter, which we vary in the interval [0.1, 1] using steps of 0.1. As in the case of spectral partitioning, the performance of Louvain is rather close in terms of AUC but the differences in AUPR are even more pronounced (Table 3). GPCR is a bit of an outlier for this experiment in that the differences between internal quality estimation and test fold results are larger than for the other data sets. The superior performance of NC matching holds, however.

Concerning comparison with the state-of-the-art, the Louvain using JC N C comes close to the performance of the stateof-the-art methods reported in [START_REF] Buza | ALADIN: A New Approach for Drug-Target Interaction Prediction[END_REF] in terms of AUC: 0.97 compared to 0.96 for our method with Louvain for Enzyme, 0.95 compared to 0.89 for GPCR, 0.98 compared to 0.97 for IC, 0.88 compared to 0.82 for NR, and 0.9 compared to 0.91 for Kinase.

Baseline comparison.

Our problem setting was addressed in [START_REF] Koptelov | Link Prediction in Multi-layer Networks and Its Application to Drug Design[END_REF], using a random walk approach which is basically an extension of PageRank for any number of layers, and thus can be considered as a baseline in this work. JC CC and JC N C in combination with both spectral partitioning and the Louvain clearly outperform that baseline in terms of AUC: 0.84 vs 0.96 (Louvain) and 0.92 (spectral partitioning) for Enzyme, 0.8 vs 0.89 and 0.85 for GPCR, 0.76 vs 0.97 and 0.88 for IC, 0.63 vs 0.82 and 0.77 for NR, and 0.61 vs 0.91 and 0.86 for Kinase, respectively. 5.2.4 Interpretability. Our approach offers a straightforward option for interpretation/explainability of a link prediction: for each of the two vertices, we can show the communities they belong to, the weights of intra-community edges, the number and layout of inter-community edges, and their numerical translation by the measure and matching technique. This is a possibility that is not available for recent, well-performing techniques based on graph embeddings.

CONCLUSION AND PERSPECTIVES

We have presented a framework for link prediction in bipartite multi-layer graphs using graph community structure and link prediction measures adapted from those proposed in the literature. We have found empirically that combining the well-known and relatively straightforward Jaccard coefficient, particularly in a BLM formulation, with the Louvain algorithm for community detection allows us to achieve results that are competitive with the state-of-the-art. We have also demonstrated that it is possible to set the parameter values of the community detection techniques via internal cross-validation and that they transfer well to unseen data.

In our supplementary material 7 , we show the evaluation of our approach on the much larger and sparser IUPHAR data set. Using those data, we have verified predicted interactions in terms of their biological semantics, shown that external validation aligns well with validation using known labels in test data, and assessed scalability.

We have limited ourselves to two easy-to-use community detection methods in this work, and will evaluate the use of other methods in the future. We also intend to perform experiments on non-biological data to test generic side of our approach. As we mentioned in Section 3, so far we have only looked at predicting interaction as a binary setting but the more challenging setting would be to predict the strength of the interaction. Finally, we intend to add layers derived from other information sources to the networks and use our approach to identify possible redundancies among them.

Figure 1 :

 1 Figure 1: Example of a bipartite multi-layer graph with 6 layers for drug-target prediction problem (blue nodes represent drugs or ligands, green nodes represent targets): drug-target network is in deep blue (bipartite layer based on IUPHAR network), drug networks are in light blue and violet, target networks are in green, grey and brown. New possible interactions are represented by dashed edges with question marks.

Figure 2 :

 2 Figure 2: An example of community to community matching (label on edges represent number of existing edges between vertices of matched communities).

Figure 3 :

 3 Figure 3: An example of node to community matching (labels on edges represent number of existing edges between vertices and matched communities, dotted edges represent non-interacting pairing)

Figure 4 :

 4 Figure 4: Link prediction measures evaluation on the benchmark data sets. The symbol + denotes the best performing measure for each group of formulations in each data set.

Table 1 :

 1 Basic properties of Benchmark and IUPHAR data sets and running times (* -for 1 fold in average with Spectral partitioning and JC CC measure)

	Data set Drugs Targets Interactions Layers	|V |	|E|	Sparsity CC Running time*, s
	Enzyme	445	664	2926	3	1109	321832	0.524	1	58.67
		GPCR	223	95	635	3	318	29853	0.592	1	3.99
		IC	210	204	1476	3	414	44127	0.516	1	7.06
		NR	54	26	90	3	80	1846	0.584	1	0.15
		Kinase	68	442	1527	3	510	101266	0.780	1	9.94
	IUPHAR 8137	2502	12456	6	10639 26706838	0.472	1	3477.8
	Table 2: Spectral partitioning parameter optimization
	via internal cross-validation
	Data set Measure	Internal	External
			AUC AUPR	AUC AUPR
	Enzyme	JC CC	0.85	0.14	0.85	0.19
		JC N C	0.91	0.19	0.92	0.26
	GPCR	JC CC	0.79	0.11	0.80	0.15
		JC N C	0.84	0.19	0.85	0.25
	IC	JC CC	0.82	0.31	0.83	0.40
		JC N C	0.87	0.32	0.88	0.41
	NR	JC CC	0.73	0.21	0.72	0.24
		JC N C	0.75	0.19	0.77	0.23
	Kinase	JC CC	0.76	0.17	0.77	0.23
		JC N C	0.85	0.26	0.86	0.35

Table 3 :

 3 Louvain algorithm resolution optimization via internal cross-validation

	Data set Measure	Internal	External
			AUC AUPR	AUC AUPR
	Enzyme	JC CC	0.94	0.52	0.96	0.69
		JC N C	0.95	0.56	0.96	0.71
	GPCR	JC CC	0.73	0.18	0.80	0.31
		JC N C	0.85	0.28	0.89	0.49
	IC	JC CC	0.94	0.50	0.95	0.65
		JC N C	0.96	0.61	0.97	0.78
	NR	JC CC	0.79	0.27	0.82	0.45
		JC N C	0.81	0.30	0.80	0.42
	Kinase	JC CC	0.72	0.15	0.73	0.19
		JC N C	0.90	0.38	0.91	0.50

https://zimmermanna.users.greyc.fr/supplementary-material.html

https://zimmermanna.users.greyc.fr/supplementary-material.html