Anne-Lise Courbis
email: anne-lise.courbis@mines-ales.fr

Kahune Luu
email: kahune.luu@mines-ales.org

Benjamin Grondin
email: benjamin.grondin@mines-ales.org

Kelly Roussel
email: kelly.roussel@mines-ales.org

A Model Driven Architecture Framework for Robot Design and Automatic Code Generation

Keywords: model driven architecture, embedded system modelling, system engineering process, state machine modelling, LEGO Mindstorms EV3, JAVA programming

This work presents a research and development experiment in software engineering at the IMT Mines Ales, France. The goal is to define a framework allowing a system controller to be graphically designed and its java code to be automatically generated. This framework is expected to be a support for students following the system engineering curriculum, and who have to program LEGO Mindstorms EV3 robots although they have not already been trained to concurrent Java programming. The experimental methodology focuses on learning and implementing the following paradigms: model driven design, software architecture for event driven systems and reactive system programming using JAVA threads. We present the design framework defined during this experiment, and the feedback of students who have been involved in setting up the state of the art and developing the framework.

I. INTRODUCTION

Designing an embedded software for a robot whose mission requires both remote communications and the recognition of its environment requires skills about system engineering, architecture design, behaviour modelling, concurrent programming and safety property verification. Such concepts are difficult to learn for students who are beginners in software or system engineering. The difficulties come from theoretical concepts and practical ones as well. The main theoretical concepts are multi component system engineering, design methods and more precisely the model driven architecture (MDA) approach, concurrency paradigms of the software part and system verification to detect for example deadlocks. Practical difficulties concern the use of appropriate tools to design such systems starting from their requirement until their implementation.

An experiment named research & development mission (R&D Mission) has been conducted at IMT Mines Alès, France. This pedagogical exercise aims at sensitizing students to research activities through two parts: the study of the state of the art and the development of a research issue conducted by members of the laboratory supporting the departement curriculum. The students follow a generalist curriculum of engineering during the first year. They have been involved for six months in a software engineering department named Informatics and Artifical Intelligence.

Until now, their knowledge was focusing on the basis of JAVA programming.

The goal of this experiment is to involve students in defining and implementing:

 a graphical framework called RMA (robot modeldriven architecture) for designing the configuration of a LEGO Mindstorms robot [START_REF] Lego | LegoMindStorm EV3[END_REF] and describing their behaviour from a high level of abstraction and,  a JAVA code module called RMDA2JAVA for generating the architecture of the software that will be embedded in the EV3 module of the robot. In this first experiment, the architecture is a JAVA code skeleton decomposed into packages and classes that has to be completed.

There are several reasons for conducting this experiment on LEGO Mindstorms EV3 robot. First, it is an actual motivation for students to discover robot progamming by using a learn and play method as a means to learn strong concepts. Furthermore, they feel helpful and responsible because the developed framework is expected to be used by other students belonging to System Engineering (SE) Departement. Indeed, students of the SE Departement are following a course about complex system design and are involved in a project consisting in developing and assembling a robot following the methods and concepts of the AFIS (French Association for SE) community [START_REF] Afis | Association Française de l'Ingénierie Système[END_REF], which is the French part of the INCOSE [START_REF]International Council on Systems Engineering Website[END_REF]. Some of them participate to the French contest ROBAFIS [START_REF] Afis | L'Ingénierie Système appliquée à la réalisation d'un robot[END_REF], organized by the AFIS. Students of the SE Department have few skills in programming, and are not motivated by JAVA programming. Using a framework developed by other students may be a real motivation to learn advanced concepts in Java and develop suitable controller to be embedded in their robot.

The paper is divided in five sections, including this introduction. Section two concerns the study of existing works about Lego Mindstorms programming using MDA approach. Section three introduces conceptual requirements that are fundamental for the framework definition and implementation. Furthermore, these concepts are required for students' training in software engineering. Section four concerns the implementation of the framework: it points out how conceptual requirements have been applied by students for developing the RMDA Framework and what are the results of this work. An example will illustrate this part in order to highlight concepts, methods and results. Section five will close the article by a discussion about the feedback of students about this experiment and the strength and weakness of this pedagogical method. We will also present our perspectives about the enhancement of the framework.

II. RELATED WORKS

The first part of the R&D Mission performed by students has consisted in setting up a state of the art of the issue expressed in the previous part. The time of this part being quite short, the subject was precise: the use of model-driven architecture approach for programming LEGO Mindstorms robots (more precisely the controller part, called EV3 brick), or eventually other kind of robots, versus conventional programming techniques such as procedural or objectoriented programming. The graphical environment of programming using preset blocks [START_REF] Griffin | The art of LEGO® Mindstorms EV3 programming[END_REF] proposed by LEGO Mindstorms and powered by LabView has been considered by students, but qualified as irrelevant for applying MDA approach.

Before starting the study, non familiar concepts have been defined. Model-Driven Engineering (MDE) is an approach for software development whereby models are used as the primary source for documenting, analyzing, designing, constructing, deploying and maintaining a system [START_REF] Truyen | The fast guide to Model Driven Architecture[END_REF].

Model-Driven Architecture (MDA): MDA itself is not a new OMG (Object Management Group) specification but rather an approach to software development which is enabled by existing OMG specifications [START_REF] Truyen | The fast guide to Model Driven Architecture[END_REF]. In the MDA approach, models are the key elements for expressing user requirements, designing the target system, documenting its development, testing and deployment, and finally, enhancing and upgrading systems.

First feedback of this state of the art is that the modeldriven architecture approach is not such widespread in robotics controller programming than the object oriented programming. The study began by searching if such approach had ever been used in LEGO Mindstorms Robot programming. LEGO Mindstorms Robots have been considered for several years as a means to support student training [START_REF] Gandy | The use of LEGO Mindstorms NXT Robots in the Teaching of Introductory Java Programming to Undergraduate Students[END_REF], [START_REF] Bradley | A platform for real-time control education with LEGO MINDSTORMS®[END_REF]. In that context, robots are used for education and unfortunately, MDA approach and independence regarding technological evolution is not considered as a priority in tutorials [START_REF] Lego | LegoMindStorm EV3[END_REF]. Different approaches can be considered [START_REF] Passama | Architectures de contrôle pour la robotique -Approches et tendances[END_REF], such as functions, objects, modules, agents or components ones. Despite many works concerning Mindstorms programming for education purpose, we could identify few refererences using any model driven. For example, there is a modelling environment dedicated to EV3 programming [START_REF] Dupont | Mindstorms Robot Tutorial[END_REF] developed by Obeo Designer [START_REF] Designer | Eclipse Sirius -Obeo Designer[END_REF] that offers some facilities to model robot choregraphy and generate JAVA code, but from our point of view, this approach mixes concepts of software engineering that will be explicitely presented in the next section and does not teach to think system. It is a nice way for introducing programming but not enough powerful to learn good practices to future engineers.

Nevertheless, some works are interesting and offer advice for system architecting and programming. For example, [START_REF] Bradley | A platform for real-time control education with LEGO MINDSTORMS®[END_REF] reveals the pros of developing a platform of control for the LEGO Mindstorms Robot. Various types of software architectures are presented in [START_REF] Passama | Architectures de contrôle pour la robotique -Approches et tendances[END_REF], such as deliberative architecture, subsumption architecture [START_REF] Trojanek | Model-driven engineering approach to Design and implementation of robot control system[END_REF] or hybrid architecture. It also presents the principle of an architecture with two layers, used in robotics.

We have also studied some references about MDE. Reference [START_REF] Fabresse | A language to bridge the gap between component-based design and implementation[END_REF] has to be used as a guide considering the details given about the key points for a good functional component-oriented program. In the same way, [START_REF] Thomas | Ingénierie dirigée par les modèles appliquée à la conception d'un contrôleur de robot de service[END_REF] deals with the application of model-driven engineering to service robots step by step from Unified Modelling Language (UML) model to dynamic architecture. The document [START_REF] Schlegel | Model-Driven Software Development in Robotics: Communication Patterns as Key for a Robotics Component Model[END_REF] describes the structure of a component-oriented program and the structure of a model-driven software development. The latter relies on a strong PIM (Platform Independent Model).

Developing a real-time embedded system relies mostly on concurrent programming. The lesson in [START_REF] Oracle | Lesson : Concurrency[END_REF] has been useful for learning the multi-threading concept and controlling concurrency between threads.

We studied also some MDE approach applied to robotics. Both [START_REF] Estévez | A novel model-driven approach to support development cycle of robotic systems[END_REF] and [START_REF] Baumeister | A Component Model for Architectural Programming[END_REF] detail the code-generation from the model established and introduce tools to do so. Compared to the few documents quoted above, [START_REF] Dhouib | RobotML, a Domain-Specific Language to Design , Simulate and Deploy Robotic Applications[END_REF] brings to light a particular model-to-text environment, called RobotML. As suggested in this name, it uses UML diagrams to generate a code. RobotML is the closest related work we have found. Our study differentiates from it since LEGO Mindstorms Robot EV3 is specifically concerned. Another study is presented in [START_REF] Pons | Applying MDA and OMG Robotic Specification for Developing Robotic Systems[END_REF] pointing out the interest of MDA. However, this work does not integrate the architecture design using a specific domain language and its associated graphical framework.

Finally, we inspired our work from [START_REF] Dhouib | RobotML, a Domain-Specific Language to Design , Simulate and Deploy Robotic Applications[END_REF], introducing RobotML as a Domain-Specific language for robotics application as well as the related work of [START_REF] Blanc | Benefits of the MDE approach for the development of embedded and robotic systems Application to Aibo[END_REF] which focused on Aibo robot to develop the same kind of approach we want to implement for Lego MindStorms Robots.

Two previous R&D Missions, developed during the two last years by students of IMT Mines Alès, have also been studied for conducting this experiment: [START_REF] Alessandro | Etude de patterns de systèmes réactifs à l'aide d'un LEGO Mindstorms: Dossier de réalisation[END_REF] is about the definition of robot behavioural patterns expressed in eFFBD (Enhanced Functional Flow Block Diagram) and their transformation in state machines; the other one [START_REF] Fernandes De Oliveira | Report Case Study: State Machine's implementation methodology using Java and LeJos Ev3[END_REF] is about the implementation of a EV3 controller modelled by a state machine in JAVA using the LeJOS library [START_REF] Lejos | LeJOS, Java for Lego Mindstorms / EV3[END_REF].

III. CONCEPTUAL REQUIREMENTS FOR DEFINING AND IMPLEMENTING THE FRAMEWORK RMDA

To develop a component oriented program for coding LEGO Mindstorms robots, we will carefully follow the five requirements stated by [START_REF] Fabresse | A language to bridge the gap between component-based design and implementation[END_REF] to avoid architectural erosion. Moreover, our work will be guided by the work of [START_REF] Thomas | Ingénierie dirigée par les modèles appliquée à la conception d'un contrôleur de robot de service[END_REF] [START_REF] Vogel | Architecture Means[END_REF] to make sure we apply the principle of separation of concerns and use patterns to manage concurrency. As defined in [START_REF] Schlegel | Model-Driven Software Development in Robotics: Communication Patterns as Key for a Robotics Component Model[END_REF], our work focuses on the PIM layer in order to remain independent of the technological platform used for the software implementation. A PIM is a formal specification of the structure and function of a system that abstracts away technical detail [START_REF] Vogel | Architecture Means[END_REF]. Essential goal of MDA is to derive value from models and modelling that helps us deal with the complexity and interdependence of complex systems [START_REF] Omg | OMG Document --ormsc/14-06-01[END_REF].

This approach presents many advantages as flexible adaptation to technological evolution, a larger possibility to reuse parts of the code. This last point is one of the main aim of our work in order to help developers in coding the robot not having to write the whole program each time a change of component is made on the robot. We focus on MDA through the two following paradigms:  The separation of concerns and model abstraction,  The meta modelling and model transformation.

Another paradigm will be presented, since it has been an actual guideline to define the generic architecture of the robot and has implied a generic architecture of the controller:  The Systemic modelling approach [START_REF] Le Moigne | Some physicochemical and mathematical tools for understanding of living systems[END_REF].

Lastly, the choice for representing the controller according to an abstract view has been oriented by work of the research team who has proposed this R&D mission [START_REF] Lambolais | Development and Verification of UML Architectures by Refinement and Extension Techniques[END_REF] [START_REF] Lambolais | IDF: A framework for the incremental development and conformance verification of UML active primitive components[END_REF]. Indeed, the next step of this project will be to verify the robot liveness and safety properties through formal approaches, based on its modelling before statting its implementation. For this reason, one important modelling choice is:

 The representation of the controller by a state machine

We develop these paradigms in the above sections and for each of them, we point out how it has been applied in the project.

Separation of Concerns and Abstraction

A.

MDA helps support separation of concerns by enabling different viewpoints of a system as well as the transformation between levels of abstraction. It is defined as the essential characteristics of quality architecture: when concerns are separated it is possible to deal with, understand and specify one aspect of a system without undue dependencies on other aspects. Separation of concerns enables greater agility, ability to deal with change and a "divide and conquer" approach to realize a system [START_REF] Omg | OMG Document --ormsc/14-06-01[END_REF].

Abstraction deals with the concepts of understanding a system in a more general way; said in more operational terms, with abstraction one eliminates certain elements from the defined scope; this may result in introducing a higher level viewpoint at the expense of removing detail [START_REF] Omg | OMG Document --ormsc/14-06-01[END_REF]. Abstraction is a powerful way of modelling since details are postpone to next steps, allowing designer to concentrate on main finalities of the system. Furthermore, abstraction does not eliminate the possibility to evaluate some fundamental properties such as liveness and safety.

In our project, separation of concerns is achieved by defining an architecture that comes from the SE processes applied by students from the SE Department. Processes implied to define models and verify both their consistency and their traceability all along the project development through the following steps: user requirements, system requirements, functional view of the system, logical view, and finally, the physical view.

In our project, separation of concerns and abstraction are achieved by applying the following design rules:

 The physical view is designed at a high level as a general pattern for any robot design. This view consists in setting up high-level abstraction models corresponding to the main sub-systems of the robot. These sub-systems have been defined by considering Systemic Modelling which is presented in the next sub-section.

 Each part of the system (component, subsystems) is seen by its environement as a black box with provided and required interfaces. Information is accessible via ports which deliver or provide services [START_REF] Lambolais | IDF: A framework for the incremental development and conformance verification of UML active primitive components[END_REF].

 Models are broken down in sub-models. These refinement steps may be validated using formal methods [START_REF] Lambolais | Development and Verification of UML Architectures by Refinement and Extension Techniques[END_REF] that ensures the preservation of liveness and safety properties.

This modelling approach includes concepts to represent services and components as primary elements in the robotics system. As stated in [START_REF] Vogel | Architecture Means[END_REF], main features for quality of architectures are high cohesion and loose coupling which leads to design for change. This is achieved by implementing the principles of abstraction, separation of concerns, and information hiding.

Systemic Modelling B.

Systemic Modelling has been introduced in France by J.L. Le Moigne [START_REF] Le Moigne | Some physicochemical and mathematical tools for understanding of living systems[END_REF] [START_REF] Eriksson | A principal exposition of Jean-Louis Le Moigne's systemic theory[END_REF]. His theory comes from two sources: the structuralism theory from Piaget's and the cybernetic theory of N. Wiener. His initial work focused on Information System, but he developed a so powerful theory, that he applied it to any complex system. He defined a canonical form of systems (see Fig. 1) as an interaction of three subsystems : Decision System, Information System and Operating System. This point of view has been a guide for our work, both for supporting designers to model robots at a high abstraction level, and for architecting the software which will be generated and uploaded in the EV3 bricks. The Decision System plays a fundamental role in our project, since it represents the controller of the robot. So, a special attention has been carried on for its representation.

The Information system is a representation elaborated by the system of its environment, according to its mission. It can be viewed as a memory of its experience and its past events which have been received or sent. This memory, depending on the maturity of the system, may be seen as an experience or an intelligence that may have influence on the Decision System.

Lastly, the Operating System is the lower level system that copes with the environment and represents the operative part of the system allowing actions to be performed, events to be received or sent, and system to act under the Decision System control.

Behavioural Modelling using State Machines C.

State machine formalism belongs to the standard UML. It is suitable for modelling the controller with respect to MDA approach for many reasons. First one is that this formalism is appropriate to model reactive systems that must be aware of their environment and have to permanently listen incoming events and react in a proper way.

State machine formalism allows system finality to be defined at high abstraction level. States represent the system steps that can be associated to activities during its mission, even when details are not yet designed. The transitions point out the evolution of the system triggered by external events (i.e. operator action through a remote interface, events coming from another robot, etc.) or internal ones (a red line has been detected by the color sensor of the robot, the robot has found an obtsacle). Transitions allow also to define events sent back by the controller to its environement (inside the robot or outside). Operating and Decision Systems communicate through the Information System that is in charge to manage and store the events exchanged between the robot and its environment.

Lastly, this formalism allows the abstraction refinement defined in MDA approach, since states may be again represented by sub state-machines. This hierarchical design mechanism is a way to apply refinement of models [START_REF] Lambolais | IDF: A framework for the incremental development and conformance verification of UML active primitive components[END_REF] that can be formally verified to maintain liveness and safety properties.

Meta Modelling and Model Transformation D.

These concepts are key words of MDA. Meta modelling is a way to define the domain concepts, their relations, and rules to manipulate them. It is thus a way to structure a project, and for our project, a support to define requirements of the framework RMDA. The meta model has 2 advantages: it allows a textual or graphical language to be defined with respect to pre-defined domain concepts ; it ensures that user's models will conform to meta model. Furthermore, when the meta model itself conforms to a meta meta model (such as ecore, proposed by Eclipse Foundation), the generic modelling tools of Eclipse Foundation can be reused and applied to specific project, that saves effort and reduces errors.

Model transformation is also a benefit of the MDA approach: new models may be automatically generated from a given meta model to another by highlighting transformation rules between their concepts. For example, model transformation into JAVA code is a way to refine a design model into a low level model, i.e. an executable code suitable for a given OS. This mechanism again saves effort and reduces errors.

We explain in the next section how the concepts of MDA and systemic modelling have been applied to set up the framework MDA.

IV. IMPLEMENTATION OF THE FRAMEWORK RMDA

The framework RMDA focuses on the design of a robot to which a mission has been assigned. The second goal is the generation of the Java code skeleton which, when completed, will be embedded in the EV3 brick. In this section, we will not consider the modelling of the environment that is interacting with the robot. However, its corresponding representation is defined in a same way than the robot by defining at a high abstraction level what kind of interactions may exist between them. The environement may be considered at a high abstraction as an interface with provided and required services. In this section, we present three parts that match with the main steps of our project that are: the meta modelling of the robot concepts, the textual and graphical design environment RMDA, and RMDA2JAVA, the code generator, which again, is based on model transformation.

Meta model associated with LEGO Mindstorms Robots

A.

The first step that has been done concerns the definition of the meta model allowing any robot to be designed taking into account the aforementioned conceptual requirements: separation of concerns, abstraction and systemic points of view. We have thus define the robot as being the assembly of three components corresponding to the Decision System, the Information system and the Operating System (see Fig. 2). Each of this component has its own ports representing the physical point of connexion of the robot sub-components. In order to appreciate the meta model, we first present the physical parts of LEGO Minstorms robot, available in the conventional package for ROBAFIS contest. It includes LEGO pieces allowing the robot to be built up. There are several kinds of sensors: color, touch, gyroscopic and ultrasonic, and motors of two kinds: large and medium. The EV3 brick has a ARM9 CPU with a LINUX system and 64 MB of memory. The Decision System is modeled by a state machine (see Fig. 3). For this first experiment, we do not take into account all features of state machines defined in UML standard [31]. They are restricted to states (including initial and final states), and transitions composed of a trigger and an action. We limit the definion of triggers and actions to event specifications. By this way, the decision system may analyze the incoming event and, depending on the state of the robot, the outcoming transition specifies what event has to be sent, and on which port.

The Operating System is constituted by some subsystems that are usually embedded on robots such as a Moving System, a Grabbing System and a Communication System (Fig. 4). Moving and Grabbing systems include motors that are connected through ports to the Decision System. The communication system is embedded in the EV3 brick and its connexion is not visible by the designer. Several communication systems are available: wifi, bluetooth or by wire. Services offered by the Operating System are modeled by a list of methods belonging to required or offered interfaces. For example, the moving system may offer services such as go right, go back, turn right, turn left. These services will have to be refined according to the number of motors chosen by the designer and their specification. The color sensor may use a required interface to send a signal about a given color recognition.

RMDA, a Graphical Framework for Designing Robots B.

Having defined the meta model, we have to set up the environment allowing the creation of models associated with the defined concepts. We made the choice to develop our framework in the Eclipse environment. By this way, we take benefit of tools such as EMF (Eclipse Modelling Framework) or GMF (Graphical Modellig Framework) [START_REF]The Eclipse Foundation[END_REF]. The first one offers tools that support designers for creating models that will, by construction, conform to a given meta model. The interface allows a modelling class to be selected and instanciated. Its properties may be assigned by the user through a tabular textual interface. This is a first way to create models.

Another way, that is less abstract for the designer is to get a graphical interface. An interesting project named Sirius [START_REF] Designer | Eclipse Sirius -Obeo Designer[END_REF] have been developed by Obeo Designer Company allowing customized graphical editors to be generated. The generation requires the definition of a meta model and a description file setting up graphical parameters (icons for example), construction rules (for linking items for example) and actions associated with the handling of the classes of the meta model (verification for example that the system has no many decision systems). This project has been useful for us in order to produce our framework RMDA. Fig. 6 gives an overview of the process of RMDA generation by Sirius and its use for creating a specific model named MyRobot.

LEGO Mindstorm Robots

This last section is the final step of our project, since its goal is to generate the JAVA code that will be embedded in the controler of the robot. Again, this generation is based on a model transformation supported by the Acceleo tool [START_REF]Eclipse Acceleo[END_REF]. The generation is performed by a set of rules expressed in the Acceleo MTL (Model to Text Language) [START_REF]Eclipse Modeling -M2T[END_REF] .

There are two steps for generating the final embedded code: 1. Getting the JAVA code of the meta model, that corresponds to the pre-defined classes of the project. This part is thus done once, when the meta model is stable. 2. Getting the JAVA code of the robot for a specific mission. This part is thus specific to any designed model.

Fig. 8 shows a part of the Acceleo MTL code allowing the meta model concepts in relation with motor LEGO Minstorms concepts to be transformed into JAVA, taking into account the LeJOS library. As pointed out in Fig. 8, motors are of two types: MediumMotor or LargeMotor. Let us precise that for this kind of items, the port is unique and is automatically created in the generated code.

Fig. 9 points out the JAVA classes that have been generated and the architecture of the project that conforms to the systemic decomposition of the system in three subsystems: decision, information and operation.

The same kind of rules have been defined in order to generate the JAVA skeleton of the controler. An interesting feature of this code is that it offers to the team of design and development a stable well organized architecture with predefined packages that constitute a guide to complete the code. Fig. 10 illustrates the JAVA code automatically generated from the description of MyRobot.

V. CONCLUSION: FEEDBACK AND PERSPECTIVES

In this paper, we have described in detail the steps of an experiment, from conceptual to practical points of view, for training students at the beginning of their Software Engineering curriculum. The goal was to learn the model driven engineering approach and how applying its concepts in the context of programming LEGO Mindstorms robots. Even if the project is yet under development, this experiment is a success from a practical point of view: the RMDA Framework allows user-oriented models to be defined. Some enhancements are planned for the end of this month to complete the graphical modelling of the state machine associated with the controler and complete the JAVA generation of the state machine. Let us note that it is also possible to reuse in the RMDA Framework existing environments (such as Obeo Designer). This option has not been chosen for this first step in order to make students responsible of the entire realization. In the future, we could plan to have an advanced release of the tool and connect it with Obeo Designer. The project was also beneficial to students for learning how programming reactive system using JAVA threads. This task has been their first practical training with their LEGO Mindstorms robot. It was controlled using a remote graphical interface and was autonomous to stop when obstacles were detected.

Another conclusion of this experiment is that the project has been a great experience for students to learn, understand and apply abstract concepts of modelling and meta modelling that are usually difficult to handle and require times and experience. They have been trained to take references in standard specifications such as EMF, GMF and UML. They have learned how to set up a bibliography and write a paper.

Lastly, this experiment has also been a great experience for the instructor of the project. Students have been invested in the project and open to discussion. RMDA Framework can be again improved. Nevertheless, it will be useful for students of the System Engineering Department that focus on the physical architecture design of the robots and behaviour modelling.

The advantages of MDA versus conventionnal software development have been often discussed according to two points of view: reducing the cost of development and increasing the quality of software [START_REF] Picek | Model Driven Development -future or failure of software development[END_REF]. The entire software community does not agree about these benefits. Nevertheless, some studies point out that model driven development yields better quality for softwares having complex problems to be solved (from functional point of view) [START_REF] Panach Navarrete | Evaluating Model-Driven Development Claims with respect to Quality: A Family of Experiments[END_REF]. From our point of view, what has to be expected from MDA is to support designers for both modelling and verifying models before their implementation. Modelling requires to be aware of the precise semantics of modelling languages, that is lacking at the present time. Models have not to be considered as sketches of a system but as formal specifications allowing verifications and code generation.

Future R&D missions will consist at first in completing the generated software to be uploaded on the robot. That is achieved by increasing the level of modelling details, specially in the state machine associated with the Decision System. This part must be also completed by testing the robot behaviour in several situations. The second goal will be to train students in the field of formal verification, which does not usually attract them. The goal is to set up a bridge between the RMDA Framework and our current research on conformance relation verification including liveness and safety analyses [START_REF] Lambolais | Development and Verification of UML Architectures by Refinement and Extension Techniques[END_REF][START_REF] Lambolais | IDF: A framework for the incremental development and conformance verification of UML active primitive components[END_REF]. That means it is better to be sure the model is correct according its specification before generating the code.

Fig. 1 .

 1 Fig. 1. Interaction between Decision, Information and Operating Systems. (reproduced from [28])

Fig. 2 .

 2 Fig. 2. Meta model of a Robot considered as an assembly of three abtract systems.

Fig. 3 .

 3 Fig. 3. Meta model of the Information and Decision Systems. The Information System is the memory of the robot. It keeps trace of incoming events of the Decision System and outgoing events . The link is established in the meta model through the Event Manager that handles Events which are linked with Trigger and Action classes associated with Transitions of the State Machine class.

Fig. 5

 5 Fig. 5 points out in a hierarchical view all concepts of the meta model.

Fig. 4 .

 4 Fig. 4. Meta model of the Operating System.

Fig. 5 .

 5 Fig. 5. Main classes of the meta model of LEGO Mindstorms.

Fig. 6 .

 6 Fig. 6. Process for generating RMDA Framework and generating JAVA code.

Fig. 7 .

 7 Fig. 7. RMDA Framework and MyRobot, a user model.

Fig. 7

 7 Fig.7gives an overview of the first release of the RMDA Framework. On the right part, one can see the control element palette window whose icons are matching the concepts of the meta model. For instance, at the top there are : Colour, Touch, Gyro and Ultrasonic Sensors icons. In the main window, MyRobot has been defined: it is constituted by three sub-systems, as defined in the conceptual requirements of section III B. The Decision System is associated with a state machine, the Operating System is constituted by two Sensors and a Moving System which has two Motors, that is conform to the meta model represented in Fig.4.RMDA2JAVA, the Generator of JAVA code to control C. LEGO Mindstorm RobotsThis last section is the final step of our project, since its goal is to generate the JAVA code that will be embedded in the controler of the robot. Again, this generation is based on a model transformation supported by the Acceleo tool[START_REF]Eclipse Acceleo[END_REF]. The generation is performed by a set of rules expressed in the Acceleo MTL (Model to Text Language)[START_REF]Eclipse Modeling -M2T[END_REF] .

Fig. 8 .

 8 Fig. 8. Accelo MTL code for generating JAVA classes corresponding to RobotMDA meta model (extract)At the present time, R&D mission is not yet achieved. The transformation of state machine has not yet been implemented. However, the pattern of code is defined, since the first task performed by students has been to learn how to program a controler in LeJOS environment when it is modeled by a state machine. They have been trained to thread programming with event handling, and are thus prepared for code generation.

Fig. 9 .

 9 Fig. 9. Architecture of the JAVA classes corresponding to the meta model.

Fig. 10 .

 10 Fig. 10. The main function automatically generated and corresponding to MyRobot description.


Koya Sato

Mizuki Oka
email: mizuki@cs.tsukuba.ac.jp

Alain Barrat
email: alain.barrat@cpt.univ-mrs.fr

Ciro Cattuto
email: ciro.cattuto@isi.it

DyANE: Dynamics-aware node embedding for temporal networks

Keywords:

come

Introduction

The ubiquity of network representations of widely different systems has led to a flourishing of methods aimed at the analysis of their structure. Among those, network node embedding methods has recently gained a lot of popularity (Cai, Zheng, and Chang 2018;Goyal, Chhetri, and Canedo 2019). Node embedding maps each node of a network into a low-dimensional vector, such that the vectors representing different nodes are close if the network nodes share some similarity or are close in the network. Node embedding thus aims at exposing in the low-dimensional space structural features and relevant patterns of the network that are not necessarily evident in the network representation. Most importantly, the embedding vectors can be used as feature vectors in machine learning applications, and have been shown to yield improved performance for tasks such as node classification, link prediction, clustering, or visualization.

While node embeddings have proven successful in achieving low-dimensional encoding of network structures, networks are also the support of important dynamical processes, such as epidemic or rumor spreading, cascading failures, consensus formation, etc. (Barrat, Barthélemy, and Vespignani 2008). Here we introduce and experiment with node embedding methods tailored to the study of dynamical processes on temporal networks, and in particular to the task of predicting the evolution and outcome of one instance of the dynamics (e.g., an epidemic spread) from partial information and without detailed knowledge of the dynamical process itself. A useful embedding should thus yield low-dimensional vectors that encode information relevant to the dynamics of the process occurring over a temporal network -rather than information about the network structure itself. Since dynamical processes unfold over timerespecting paths determined by the underlying network and by its evolution over time, we argue that the sought embeddings should be informative of these paths -the paths along which information can propagate. Driven by this idea, we propose to map the temporal network to a static graph representation, a so-called supra-adjacency representation, whose nodes are (node, time) pairs of the original temporal network [START_REF] Valdano | Analytical computation of the epidemic threshold on temporal networks[END_REF]. We modify the original supra-adjacency representation method to only consider nodes at those times when they interact, and we map the original temporal edges to edges between the corresponding (node,time) pairs, so that the static graph representation preserves the temporal paths of the original temporal network (i.e., the paths supporting and constraining the dynamical process at hand). An example of the supra-adjacency representation we use here is shown in Fig. 1. Since the resulting representation is a static graph, we can then apply standard embedding techniques: we focus on embeddings based on random walks as they provide an efficient way to sample the relevant paths.

We study the usefulness of the proposed embeddings in the context of a paradigmatic dynamical process -epidemic spread over temporal networks -in which network nodes exist in few discrete states and the dynamics consists of transitions between such states (e.g., a "susceptible" node becoming "infectious"). We focus on the task of predicting the nodes' states over time for a single realization of the epidemic process. Specifically, we set up a multi-label super-vised classification problem with a training set obtained by sampling the node states at random times, with no information about the mechanics of state transitions nor on the parameters of the epidemic process. Our contributions are as follows:

• We propose a new method for node embedding tailored to the study of dynamical process on temporal networks, using a modified supra-adjacency representation for temporal networks and building on standard random-walk based embeddings for static graphs.

• We show that in the important case of epidemic spreading, a satisfactory prediction performance of nodes' states can be achieved in a supervised multi-label classification setting informed by the proposed embeddings.

• We show that our method achieves good performance in estimating the temporal evolution of the entire system from sparse observations, consistently across several data sets and across a broad range of parameters of the epidemic model. Our approach requires no fine-tuning of the embedding hyper-parameters and yields consistently superior performance than other embedding methods.

Problem Formulation Temporal Network

We consider a temporal network g in discrete time on the set of timestamps

T = (1, 2, • • • , |T |):
g is defined as the set E of the undirected temporal edges (v i , v j , t), meaning that nodes v i and v j are linked at t ∈ T , possibly with a weight w (for simplicity we consider only positive weights). At each timestamp t, E t denotes the set of temporal edges at t, and V t is the set of nodes which have at least one temporal edge at t:

V t = {v i |∃v j , (v i , v j , t) ∈ E t }.
We define the snapshot network at t as the undirected weighted network G t = (V t , E t ), and the temporal network g can be seen as the succession of snapshot networks

(G 1 , • • • , G |T | ). The overall set of nodes is V = ∪ t∈T V t .
For each node v i ∈ V , we define its set of active times T vi as the set of timestamps t in which it has at least one temporal edge, i.e., such that v i ∈ V t : T vi = {t|∃v j , (v i , v j , t) ∈ E t }. We denote the a-th active time of v i by t vi,a ∈ T vi , with t vi,a < t vi,a+1 . We then define the set of active copies of each node v i , that we call "active nodes", as

V vi = {(v i , t)|t ∈ T vi }. The overall set of active nodes is V = ∪ vi∈V V vi .

Dynamical process

We consider a dynamical process taking place on the temporal network, such that the nodes v i ∈ V can be in one of a finite set of discrete states S. Nodes can change state either spontaneously or through interaction along temporal edges. Our definition is thus very general and encompasses in particular models of epidemic propagation, rumor propagation, opinion formation or cascading processes (Barrat, Barthélemy, and Vespignani 2008;Castellano, Fortunato, and Loreto 2009;[START_REF] Pastor-Satorras | Epidemic processes in complex networks[END_REF].

The mapping f : (v i , t) ∈ V → s ∈ S specifies the state of each node at each of its active times. We assume that a sample of these states is known: we define the set of the corresponding observed active nodes as D ⊂ V. Here, for simplicity, we will assume that D results from a uniform random sampling of V. We also assume that the state of a node can be only be observed when it is active, i.e., in contact with at least another node.

For clarity, here we will focus on a paradigmatic dynamical process taking place on the temporal network, the Susceptible-Infectious-Recovered (SIR) model for epidemic spreading, which has been widely used to model contagious infections such as flu-like diseases [START_REF] Keeling | Modeling Infectious Diseases in Humans and Animals[END_REF]. In this model, each node can be at each time in one of three possible states: susceptible (S), infectious (I), and recovered (R). At the start of the process, all nodes are in state S, except for the epidemic seeds, which are in state I. A contact between an S and an I nodes leads to a contagion event in which the S node becomes infectious with probability β per unit time (recall we work in discrete time). Let us denote by I t the set of infectious nodes at t, and consider a susceptible node v i . We denote its set of neighbours at t as N t (v i ) = {v j |(v i , v j , t) ∈ E t }, and N t (v i ) ∩ I t is the set of its infectious neighbours at t. The probability that none of these infectious neighbours transmits the disease to v i at timestep t is (1β) |Nt(vi)∩It| , and thus the probability that v i becomes infectious at time t, due to its interactions, is 1-(1-β) |Nt(vi)∩It| . Recovery from state I to state R occurs also stochastically: each infectious node becomes recovered (R) at each timestamp with probability µ. Recovered nodes do not change state any more. The parameters of the model are thus the infection and recovery rates β and µ [START_REF] Keeling | Modeling Infectious Diseases in Humans and Animals[END_REF].

Problem statement

Given a known temporal network and a partial observation of the dynamical states of the nodes, the problem consists in predicting the dynamical state of all nodes at all their active times. In other words, knowing the state of the subset D of observed nodes at some active times, we want to predict the state of all the active nodes at all times. Crucially, we seek to achieve this prediction without any detailed information on the dynamical process at hand, except for the set of possible states of each node. In particular, we do not make assumptions on the allowed state transitions, the parameters governing the dynamical process, nor even the reversibility or irreversibility of the process. We also remark that the above problem statement implies that we will be working on single realizations of the dynamical process, with the goal of predicting the state of a given node at a given time, rather than predicting statistical properties averaged over a sample of simulated or observed dynamics.

Notice that the SIR model -in addition to its relevance to many real-world phenomena -is particularly interesting to study in this context: it features both state transitions occurring upon interaction (hence, along the edges of the temporal network) as well as spontaneous state transitions that can occur at any time, and in particular between successive active times of a node (the infectious-recovered transition).

Temporal network

Dynamics-aware supra-adjacency network Our Approach: DyANE

! " ! # ! " , % & ' ," ! # , % & ( ," ! " ! ) ! " , % & ' ,# ! ) , % & * ," ! # ! ) ! # , % & ( ,# ! ) , % & * ,# % % + 1 % + 2
Our approach consists of three steps. First, we map the temporal network to a static network between active nodes through a modified supra-adjacency representation. Second, we apply standard embedding techniques for static graphs to this supra-adjacency network. We will consider embeddings based on random walks as they explore the temporal paths on which transmission between nodes can occur. Finally, we train a classifier to predict the dynamical state of all active nodes based on the vector representation of active nodes and the partially observed states.

Supra-adjacency representation

We first map the temporal network to a supra-adjacency representation, i.e., to a new static network whose nodes are the active nodes of the temporal network. We thus define the supra-adjacency network as G = (V, E), where E are (weighted, undirected) edges joining active nodes. The mapping from the temporal network to the supra-adjacency network consists of the following two procedures (Fig. 1):

• For each node v i , we connect its successive active times: for each active time t vi,a of v i , we draw a "self-coupling" edge between (v i , t vi,a ) and (v i , t vi,a+1 ) (recall that active times are ordered in increasing temporal order).

• For each temporal edge (v i , v j , t), the time t corresponds by definition to an active time for both v i and v j , that we denote respectively by t vi,a and t vj ,b . We then map

(v i , v j , t) ∈ E to two undirected edges ∈ E, namely (v i , t vi,a ), (v j , t vj ,b+1
) and (v j , t vj ,b ), (v i , t vi,a+1 ) . In other words, the active copy of v i at t, (v i , t), is linked to the next active copy of v j , and vice-versa. The first procedure makes each active node adjacent to its adjacent past and future versions (active times), which ensures that a node carrying an information at a certain time can propagate it to its future self along the self-coupling edges, and is useful in an embedding perspective to favor temporal continuity. The second procedure encodes the temporal interactions, and yields the crucial property that any time-respecting path existing on the original temporal network, on which a dynamical process can occur, is also represented in the supra-adjacency representation. Indeed, if an interaction between two nodes v i and v j occurs at time t and potentially modifies their states, e.g., by contagion or opinion exchange or modification, this can be observed and will have consequences only at their next respective active times: for instance, if v i transmits a disease to v j at t, v j can propagate it further to other neighbours only at its next active time, and not immediately at t. This is reflected in the supra-adjacency representation we propose.

The edges in E are thus of two types, joining two active nodes corresponding either to the same original node, or to distinct ones. For each type, we can consider various ways of assigning weights to the edge. We first consider for simplicity that all self-coupling edges carry the same weight ω, which becomes thus a hyperparameter of the procedure. Moreover, we simply report the weight of each original temporal edge (v i , v j , t) on the two supra-adjacency edges (v i , t vi,a ), (v j , t vj ,b+1 ) and

(v j , t vj ,b ), (v i , t vi,a+1 ) (with t = t vi,a = t vj ,b ).
In the following, we will refer to the above supraadjacency representation as dyn-supra. We will moreover consider two variations of this representation. First, we can encode the direction of time of the original temporal network in the supra-adjacency representation by making all links of E directed: an edge ((v i , t), (v j , t )) ∈ E is then oriented according to the direction of increasing time, i.e., pointing from the active node with the earlier time min(t, t ) to the one with the later time max(t, t ). We will refer to this representation as dyn-supra-directed.

Another possible variation consists in encoding the time delay between active nodes into edge weights, with decreasing weights for increasing temporal differences. This decay of edge weights is consistent with the idea that successive active nodes that are temporally far apart are less likely to influence one another (which is the case for many important dynamical processes). In our case, we will consider that the original weight of the edge (v i , t vi,a ), (v j , t vj ,b ) in the dyn-supra representation (i.e., ω if v i = v j , or the original weight w of the temporal edge if v i = v j ) is multiplied by the reciprocal of the time difference between the active nodes if t vi,a = t vj ,b , i.e., 1/(t vi,at vj ,b ) . We will refer to this representation as dyn-supra-decay.

Node embedding

The central idea of the node embedding method we propose for temporal networks, which we call DyANE (Dynamics-Aware Node Embeddings), is to apply to the supraadjacency network G any of the node embedding methods that have been developed for static networks. In particular, here we will use DeepWalk (Perozzi, Al-Rfou, and Skiena 2014), as it is a simple and paradigmatic algorithm, and it is known to yield high performance in node classification tasks [START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF].

DeepWalk is based on an exploration of the neighborhood of a node by truncated random-walks rooted at that node, which makes it particularly appropriate in our framework. Indeed, in the supra-adjacency representation, these random-walks will explore for each active node both the self-coupling edges leading to past and future versions of the same original node, and the edges representing the interactions between nodes. As written above, these edges encode the paths along which dynamical processes occur, meaning that the final embedding will preserve structural similarities relevant to these dynamical processes. Note that DeepWalk does not consider weighted edges, but it can easily be generalized so that the random walks take into account edge weights [START_REF] Grover | Node2vec: Scalable feature learning for networks[END_REF].

Prediction of dynamical states

Once we have obtained an embedding for the supraadjacency representation of the temporal network, we can turn to the task of predicting the dynamical states of active nodes. Since we assume that the set of possible states is known, this is naturally cast as a (supervised) classification task, in which each active node should be classified into one of the possible states. In our specific case, the three possible node states are S, I, and R. Note that the classification task is not informed by the actual dynamical process (except knowing the set of possible node states). In particular, no information is available about the possible transitions nor about the parameters of the actual process. We will use here a one-vs-rest logistic regression classifier, which is customarily used in multi-label node classification tasks based on embedding vectors. Naturally, we could use any other suitable classifier.

We remark that we seek to predict node states for individual realizations of the dynamics. This is relevant to several applications: for example, in the context of epidemic spreading, and given a temporal interaction network, one might use such a predictive capability to infer the state of all nodes from the observed states of few active nodes ("sentinel" nodes).

Experiments

We study the effectiveness of the DyANE, in particular with the dyn-supra+DeepWalk combination, in the context of node classification tasks. For our experiments we use temporal networks built from empirical datasets that describe close-range proximity interactions of persons in a variety of real world environments. We simulate the SIR (Susceptible-Infected-Recovered) dynamical process described above over these temporal networks, generating state labels for all active nodes.

Based on the above temporal networks and node labels, we run DyANE with different combinations of supra-adjacency representations and of embedding methods for the static network, and use the resulting embedding vectors as inputs to a supervised multi-label classifications tasks. We test the sensitivity of our approach with respect to the choice of parameters and to the number of sampled active nodes D. Finally, we also compare classifiers based on DyANE embeddings with methods that directly embed the nodes of a temporal network without relying on a supra-adjacency representation.

Data sets and dynamical process

We used publicly available data sets describing the face-toface proximity of individuals with a temporal resolution of 20 seconds [START_REF] Cattuto | Dynamics of person-to-person interactions from distributed rfid sensor networks[END_REF]). These datasets were collected by the SocioPatterns collaboration1 and we specifically use data sets collected in a variety of contexts, namely in offices ("InVS15"), a hospital ("LH10"), a highschool ("Thiers13"), a conference ("SFHH") and a school ("Lyon-School") [START_REF] Génois | Can co-location be used as a proxy for face-to-face contacts[END_REF]. We built a temporal network from each data set by aggregating the data on 600 seconds time windows. Whenever multiple proximity events were registered between two individuals within a time window, we used the number of such events as the edge weight. Table 1 shows some basic statistics for each data set.

We simulated the SIR model on each data set (with the original temporal resolution of 20 seconds), using the following five combinations of epidemic parameters: (β, µ) = {(0.25, 0.002), (0.125, 0.004), (0.125, 0.002), (0.125, 0.001), (0.0625, 0.002)}. In each case, we consider as initial state a single randomly selected node as seed, setting its state as infectious, with all others susceptible. Given the stochastic nature of the model, in some cases the infectious state barely spreads, with a large majority of the nodes remaining susceptible. The prediction task would then be trivial, and we restrict our study to non-trivial cases in which there is still at least one infectious node when more than half of the total data set time span has elapsed (i.e., |I |T |/2 |≥ 1). We thus run the SIR model up to 100 times for each data set until we obtain a simulation in which this condition is met. If the condition is not met in any of the 100 simulations, we discard the corresponding case (see Table 2). For each selected simulation, we assign as ground truth label to each active node (v i , t a ) the state of node v i at time t a . Table 2 shows the proportion of each label among active nodes for each case.

We select uniformly at random |D|= ρ|V | active nodes, and build our training data using those nodes and the corresponding node states. Unless otherwise noted, ρ = 1. We evaluate the prediction performance on a test data consisting of the remaining active nodes and their states. We report the prediction performance averaged over five realizations of the random choice of training data, for each data set and parameter values.

Evaluation

We quantified the prediction performance of each method by the Macro-F1 and Micro-F1 indices, which are widely used for evaluating multi-label node classification tasks [START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF]. These indices range between 0 and 1, with higher values indicating better performance. Macro-F1 is an unweighted average of the F1 scores of each label, while Micro-F1 gives more importance to the labels which are more represented. When classes are imbalanced, Macro-F1 and Micro-F1 give a measure of the effectiveness of the method on respectively the smaller and the larger classes.

As the number of active nodes in each state might indeed be imbalanced here, we measure both Macro-and Micro-F1 to evaluate models by the prediction performance against both the smaller and the larger classes.

Baseline methods

We considered variations of our method both at the level of the supra-adjacency representation and of the static embedding method. First, as a variation of our proposed supraadjacency representation (dyn-supra), we consider a "baseline" supra-adjacency representation, which we denote by mlayer-supra, in which we simply map each temporal edge (v i , v j , t) to a single edge between active nodes, namely ((v i , t), (v j , t)), similarly to the original supra-adjacency representation developed for multilayer networks [START_REF] Kivelä | [END_REF]). Self-coupling edges are drawn as in dyn-supra.

We also considered two alternative embedding methods for the static networks obtained by each supra-adjacency representation: (i) LINE [START_REF] Tang | Line: Large-scale information network embedding[END_REF], which embeds nodes in a way to preserve both first and second-order proximity;

(ii) Graph Factorization (GF) [START_REF] Ahmed | Distributed large-scale natural graph factorization[END_REF], which considers first-order proximity.

In addition, we considered two methods for temporal network embedding, which thus do not use the intermediate supra-adjacency representation, namely: (i) Dynam-icTriad (DTriad) [START_REF] Zhou | Dynamic network embedding by modeling triadic closure process[END_REF], which embeds the temporal network by modeling triadic closure events; (ii) DynGEM (Goyal et al. 2018), which is based on a deep learning model. It outputs an embedding for the network of each timestamp, initializing the model at timestamp t + 1 with the parameters found at time t, thus transferring knowledge from t to t + 1 and learning about the changes from G t to G t+1 . Overall, we obtain eight methods -six variations of DyANE and two methods that directly embed temporal networks -which we denote respectively dyn-supra+DeepWalk, dyn-supra+LINE, dyn-supra+GF, mlayer-supra+DeepWalk, mlayer-supra+LINE, mlayer-supra+GF, DTriad, and DynGEM.

We used publicly available implementations of all embed-ding methods, namely the implementation of LINE2 , Dy-namicTriad3 , and DynGEM4 by the original authors, and the implementation of GF by GEM5 . As for DeepWalk, we used an implementation of node2vec6 with p = q = 1. Unless otherwise noted, we conducted experiments with embedding dimension d = 128 and self-coupling edge weight ω = 1. We used the default values of each implementation of the embedding methods, except for the number of iterations of LINE and GF, which we took equal to the number of samples of DeepWalk. We used Scikit-Learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] to implement one-vs-rest logistic regression, with the default hyper-parameter setting.

Prediction performance

Figure 2 shows the prediction performance of the eight methods considered, for all data sets and SIR parameters considered. The dyn-supra representation combined with DeepWalk yields almost always the highest value both for Macro-F1 and Micro-F1. While dyn-supra+DeepWalk is consistently the best method for both Macro-F1 and Micro-F1 across all considered data sets and SIR parameters, Dyn-GEM yields a higher Micro-F1 value in a few cases. However, DynGEM's Macro-F1 score is rather low in such cases. We moreover observe that: (i) for a given static embedding method, the dyn-supra supra-adjacency representation gives better results than the baseline (mlayer-supra) one; and (ii) for a given supra-adjacency representation, DeepWalk performs better than LINE, which in turn outperforms GF.

Finally, we show in the supplementary material that the dyn-supra+DeepWalk prediction recovers the overall temporal evolution of the spreading process.

Sensitivity analysis

We first investigate here the effect of the hyper-parameters, of the supra-adjacency representation (the weight ω of self-coupling edges) and of the embedding (the embedding dimension d). We show in Fig. 3 the results obtained for the Macro-F1, for the InVS15 data set and (β, µ) = (0.025, 0.002), but we have confirmed the same tendency for the other data sets, parameters and also for Micro-F1 values (the omitted results are included in the Supplementary Materials). The results show that the performance of dyn-supra+DeepWalk is very stable with respect to changes in ω, while other methods depend weakly on ω. The performance of all methods is stable on a wide range of embedding dimensions, and decrease when it becomes smaller than 32. Overall, dyn-supra+DeepWalk remains the most effective method without the need for fine-tuning ω or d. Figure 3 also shows the effect of increasing the parameter ρ, i.e., of being able to observe a larger number of active nodes. The performance increases with ρ for most methods, and in particular for dyn-supra+DeepWalk, which consistently yields the best result at all values of ρ.

As mentioned above, we moreover considered two variations if the dyn-supra representation: (i) we regard edges as directed towards increasing timestamps (dyn-supradirected); (ii) we let the weight of an edge decay with increasing temporal lag between the active nodes it links, e.g., we modulate the edge weight according to the reciprocal of the lag (dyn-supra-decay). We also consider these variations for mlayer-supra representation, yielding mlayersupra-directed and mlayer-supra-decay, respectively. Notice that, in the mlayer-supra, the supra-adjacency edges representing temporal edges are not affected by both variations. We report in Fig. 4 the results for (β, µ) = (0.1250, 0.002) and for the DeepWalk embedding, as DeepWalk overall yielded the best results. We checked that the results of Fig. 4 hold similarly for the LINE and GF embeddings.

Figure 4 indicates that using directed edges worsens the performance of both dyn-supra and mlayer-supra methods. Introducing weights depending on the time difference between active edges also worsens the performance for mlayer-supra, with little effect on dyn-supra. Overall, the original dyn-supra method with undirected edges and using only the weights of the original temporal edges yields the highest prediction performance.

Related Work

Network node embedding Numerous embedding techniques have been proposed for static networks, and we refer to the recent reviews (Cai, Zheng, and Chang 2018;[START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF] for detailed descriptions. Most techniques encode as proximity or similarity between nodes either a first-order proximity (two nodes are more similar if they are connected by an edge with larger weight) or a second-order proximity (nodes are more similar if their neighborhoods are similar). A popular way of exploring the (structural) similarity of nodes consists in using random walks rooted at the nodes, which thus explore their neighborhoods. Two of the most well-known embedding techniques, DeepWalk and node2vec [START_REF] Grover | Node2vec: Scalable feature learning for networks[END_REF] are indeed based on such random walks.

As temporal network data has become more widely accessible in a range of contexts, the issue of embedding dy- namically evolving networks has emerged and some methods have been put forward. As nodes' relationships evolve with time, the structure of their neighborhoods and the similarity or proximity between nodes indeed evolve as well.

The typical approach consists then (in discrete time, although see [START_REF] Nguyen | Continuoustime dynamic network embeddings[END_REF]) for a case of continuous time embedding) in defining a distinct embedding for each temporal snapshot and to ensure some continuity between the embeddings of successive snapshots [START_REF] Zhou | Dynamic network embedding by modeling triadic closure process[END_REF]Goyal et al. 2018;Goyal, Chhetri, and Canedo 2019). For a comprehensive review of recent embedding methods for dynamically evolving networks see [START_REF] Kazemi | Relational representation learning for dynamic (knowledge) graphs: A survey[END_REF].

None of these methods however consider, as we do here, supra-adjacency representations of the temporal network as a whole in order to then take advantage of static network techniques for the embedding of temporal networks.

Supra-adjacency representation

The supra-adjacency matrix representation has been developed for multilayer networks [START_REF] Gómez | Diffusion dynamics on multiplex networks[END_REF][START_REF] Kivelä | [END_REF], in which nodes interact on different layers (for instance different communication channels in a social network). Using the pairs (node, layer) as elementary entities, this representation builds a graph between these pairs, consisting in (i) the links within each layer, such as (i, α)-(j, α) if nodes i and j are linked in layer α, and (ii) the links between different copies of the same node in different layers, such as (i, α)-(i, β) between layers α and β. The adjacency matrix of this new graph is the supra-adjacency matrix. This representation has proven very convenient in the study of processes on multilayer networks [START_REF] Kivelä | Multilayer networks[END_REF] as it makes it possible to use the methods and theoretical results developed using adjacency matrix of simple graphs.

It has been generalized to temporal networks, seen as special multilayer networks in which every timestamp is a layer: in the supra-adjacency representation, each node is identified by the pair of indices (i, t), corresponding to the node label i and the time frame t, respectively [START_REF] Valdano | Analytical computation of the epidemic threshold on temporal networks[END_REF]. Most importantly, (i) each node (i, t) is linked by a directed edge to its successive copy (i, t + 1), but not to other future timestamps and (ii) intra-layer edges are absent: instead, if i and j are connected at time t, in the supra-adjacency representation this is replaced by two directed edges respectively from (i, t) to (j, t + 1) and from (j, t) to (i, t + 1). This representation was put forward in the context of spreading processes on temporal networks as it indeed preserves the information relevant for the spreading process [START_REF] Valdano | [END_REF]: if a contagion event occurs from i to j at time t, j will be contaminated (and could propagate the disease further) at t + 1, but not yet at t. Note that the nodes (i, t) are in this representation present for all nodes i and timestamps t, even if i is isolated at t, and that the links (i, t) -(j, t + 1) and (j, t) -(i, t + 1) also exist even if i or j have no links at t or t + 1. The modified supraadjacency representation we propose considers instead only the pairs (i, t) such that i is not isolated at t, in order to avoid potentially long chains (i, t) -(i, t + 1) -• • • -if i remains isolated for some time, and draws links only between (i, t) and (j, t ) such that i (resp. j) is not isolated at t (resp. t ).

Recovering dynamics on a network

Given a dynamical process occurring on a network, such that nodes change state over time, only partial knowledge of this evolution can in general be realistically envisioned, as for instance in diffusion processes such as the spread of contagious diseases or rumors. The task of recovering the complete knowledge of a diffusion process from partial observations has thus been addressed in a variety of settings. Some works have put forward methods to recover the state of all nodes and the seeds of a spread from a partial observation of nodes at a given time [START_REF] Sundareisan | Hidden hazards: Finding missing nodes in large graph epidemics[END_REF]Xiao, Aslay, and Gionis 2018), without attempting to recover the process whole temporal evolution. Methods to recover the state evolution of all nodes have also been proposed, using as input snapshots of the whole system, i.e., the knowledge of the state of all the nodes at a certain time [START_REF] Sefer | Diffusion archeology for diffusion progression history reconstruction[END_REF][START_REF] Feizi | Network infusion to infer information sources in networks[END_REF]Chen, Tong, and Ying 2019). Bayesian inference methods from partially observed snapshots have also been proposed [START_REF] Altarelli | The patient-zero problem with noisy observations[END_REF]. These works make use of strong assumptions on the nature of the underlying diffusion model. Some works have also proposed to recover the time evolution of node states without detailed knowledge of the diffusion model [START_REF] Rozenshtein | Reconstructing an epidemic over time[END_REF]Xiao et al. 2018;Xiao, Aslay, and Gionis 2018). In particular, Rozenshtein et al. map the temporal network to a supra-adjacency representation almost identical to the mlayer-supra representation described above, in order to preserve the temporal paths on the network, and solve the recovery of the node states as a Steiner tree problem. This relies on the fact that each node changes state only once, hence on the irreversibility of the process. Finally, we mention a method based on tensor decomposition to recover coexisting information diffusion processes from partial knowledge of the node states, without detailed knowledge of the processes, by exploiting the fact that these processes occur in synergy [START_REF] Sun | Collaborative inference of coexisting information diffusions[END_REF]. The fraction of unknown states is however limited, while we consider a very small fraction of active node states as known.

Conclusion

Here we introduced a method for embedding nodes of temporal networks suited for the task of recovering the dynamical evolution of a single instance of a process occurring on the network, from partial observations and without information on the nature of the process itself except from the set of possible states of the nodes. Our method first maps the temporal network to a modified supra-adjacency representation, which preserves the paths on which the process unfolds. As this representation yields a static graph among the active nodes, which are pairs of the form (node of the temporal network, time of interaction), it enables the use of embedding techniques for static networks. We choose to use DeepWalk, as it is a simple and paradigmatic algorithm based on random walks and thus particularly suited to explore the neighborhood of the nodes of the supra-adjacency representation in a way relevant to the dynamical process on the network. We finally frame the inference of the dynamical state of all active nodes from a set of observations as a classification task.

We have shown the performance of our method on the concrete case of an epidemic-like model on empirical temporal networks and compared it with other state of the art methods. Our method consistently yields very good classification performance in a robust way across data sets and process parameters, without fine-tuning hyper-parameters.

Our results show that it is possible, without any knowledge of the precise nature of the process nor of its parameters, to recover crucial information on its outcome. Note in particular that our method assumes no knowledge of which transitions between states actually occur in the real dynamics: this means that the predicted sequence of states of each individual node might yield "forbidden" transitions (e.g., in the SIR example, transitions from I to S or from R to I). Nevertheless, we have shown that the outcome of the classification task gives a good estimation of the actual dynamics.

Our method has however the clear limitation that we assume the whole temporal network to be known. Although a full observation of the contact patterns of individuals could be envisioned in some specific controlled settings such as hospitals, this is not generally the case. Further work will address this limitation by considering the effect of noise and errors in the temporal network data, and by considering the case in which only a (more or less detailed) set of statistics of the temporal network is known. Noise could also impact the quality of the sampling (e.g., observational errors), and we will check its impact on our method's performance. Further work will also address different sampling strategies such as a sampling concentrated at early times, or focused on few specific "sentinel" nodes followed at all times, or of a whole snapshot of the system but only at a specific time. This could yield crucial insights on how to optimize surveillance strategies in concrete settings.

Finally, since our method is largely agnostic with respect to the specific dynamical process, we will consider other processes such as other models of disease propagation, complex contagion phenomena or opinion formation.

Figure 1 :

 1 Figure 1: Proposed supra-adjacency representation (dynsupra). The original temporal network (top), whose state is shown at three different times, is mapped to a static representation (bottom) where nodes are (node,time) pairs of the original network.

Figure 2 :Figure 3 :

 23 Figure 2: Prediction performance of each method, for each data set and spreading parameter set. The top and bottom row indicate results of Macro-F1 and Micro-F1, respectively.

Figure 4 :

 4 Figure 4: Effect of the variations in the supra-adjacency representation. Top: effect of using directed edges. Bottom: effect of introducing weights depending on time difference.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :Figure 5 :

 12345 Figure 1: One example of predicted timeline of the number of active nodes in the infectious state, for dyn-supra+DeepWalk, for each SIR parameter set and each data set. The blue, orange and gray lines are respectively the number of actual active nodes in state I in the test data, the number of predicted active nodes in state I and the number of active nodes in the test data at time t. Note that the number of active nodes in the test data is almost the same as the total number of active nodes, as the training data is of small size (ρ = 1, i.e., |D|= |V |).

Figure 6 :

 6 Figure 6: Effect on the reconstruction performance of introducing weights depending on time difference. These results are for (β, µ) = (0.1250, 0.002).

Table 1 :

 1 Empirical temporal networks. Columns, from leftmost to rightmost: data set name, number of active nodes, number of nodes, number of timestamps, number of temporal edges, average weight of temporal edges, average fraction of timestamps in which a node is active.

	Name InVS15 LH10 SFHH Thiers13 LyonSchool 17174 242 104 89640 2.806 |V| |V | |T | |E| 1 |E| 22451 217 699 37582 4.164 4880 76 342 14870 4.448 10815 403 127 34446 4.079 32546 327 246 71724 5.256	e∈E w(e)	1 |V | |T | 0.148 0.188 0.211 0.405 0.682	v∈V |V v |

Table 2 :

 2 Proportion of the three possible states S, I and R among the active nodes, for each data set and each parameter set of the SIR model. "-" indicates the cases for which the epidemic did not spread sufficiently (i.e., |I |T |/2 |= 0).

	β = 0.25, µ = 0.002 P(S) P(I) P(R) 0.171 0.0500 0.778 0.103 0.0534 0.843 0.154 0.0457 0.799 -β = 0.125, µ = 0.004 β = 0.125, µ = 0.002 β = 0.125, µ = 0.001 P(S) P(I) P(R) P(S) P(I) P(R) P(S) P(I) P(R) --0.0801 0.152 0.767 0.292 0.0975 0.609 0.197 0.120 0.681 ---0.0488 0.259 0.692 0.337 0.195 0.467 0.653 0.155 0.191 0.0737 0.151 0.774 0.163 β = 0.0625, µ = 0.002 P(S) P(I) P(R) 0.123 0.0769 0.799 0.0891 0.168 0.742 0.333 0.502 0.0340 0.0908 0.875 0.139 0.0959 0.764 0.183 0.0923 0.723 0.240 0.051 0.707 0.111 0.164 0.723 LyonSchool 0.0955 0.155 Data set InVS15 LH10 SFHH Thiers13 0.748 0.104 0.191 0.703 0.128 0.156 0.715 0.102 0.0908 0.806 0.107 0.311 0.580

http://www.sociopatterns.org/

https://github.com/tangjianpku/LINE

https://github.com/luckiezhou/DynamicTriad

http://www-scf.usc.edu/˜nkamra/

https://github.com/palash1992/GEM

https://snap.stanford.edu/node2vec/


Lolita Lecompte

Pierre Peterlongo

Dominique Lavenier

Claire Lemaitre

Genotyping Structural Variations using Long Read Data

Background

Structural variations (SV) are characterized as genomic segments of a least 50 base pairs (bp) long, that are rearranged in the genome. There are several types of SV such as deletions, insertions, duplications, inversions, translocations. This kind of polymorphism have been shown involved in many biological processes, particularly diseases or evolution [START_REF] James R Lupski | Structural variation mutagenesis of the human genome: Impact on disease and evolution[END_REF]. Databases referencing such variants grow as new variants are discovered, at this time dbVar, the reference database of human genomic SVs [START_REF] Phan | dbvar structural variant cluster set for data analysis and variant comparison[END_REF], contains 35,428,724 variant calls, illustrating that many SVs have already been discovered and characterized in the human population. In this context, it becomes very interesting and informative to evaluate for a given newly sequenced individual if its genome holds already known SVs. This is commonly known as the SV genotyping problem.

Such genotyping methods already exist for short reads data: for instance, SVtyper [START_REF] Chiang | Speedseq: ultra-fast personal genome analysis and interpretation[END_REF], SV 2 [START_REF] Antaki | Sv2: accurate structural variation genotyping and de novo mutation detection from whole genomes[END_REF]. Though short reads are often used to discover and genotype SVs, this is well known that their short size make them illadapted for predicting large SVs or SVs located in repeated regions. Third generation sequencing technology, such as Pacific Biosciences (PB) and Oxford Nanopore Technologies (ONT), can produce long reads data compared to Next Generation Sequencing technologies. Despite their higher error rate, long reads are crucial in the study of SVs. Indeed, the size range of this data can reach a few kilobases to megabases, thus long reads can extend over rearranged SV sequences as well as over the repeated sequences often present at SV's breakpoint regions.

Following long reads technology's development, many SV discovery tools have emerged, such as Sniffles [START_REF] Fritz | Accurate detection of complex structural variations using single-molecule sequencing[END_REF]. To our knowledge there is currently no tool that can perform genotyping from a set of known SVs with long reads data. Thus, there is a need to develop accurate and efficient methods to genotype SVs with long reads data, especially in the context of clinical diagnoses.

Results

Method We propose a novel method that aims at assigning a genotype for a set of already known SVs in a given individual sample sequenced with long reads data. In other words, the method assesses if each SV is present in the given individual, and if so, how many variant alleles it holds, ie. whether the individual is heterozygous or homozygous for the particular variant. The method is described and implemented here for only one type of SV, the deletions, but the principle can be easily generalized to other types of SVs. We also provide an implementation of this method in the tool named SVJedi.

The principle of the method is based on: 1) Generating reference sequences that represent the two possible alleles of each SV. The reference allele (allele 0) is therefore the sequence of the deletion with adjacent sequences at each side, and the alternative allele (allele 1) consists in the joining of the two previous adjacent sequences. 2) Then, sequenced long reads are aligned on all previously generated references, using Minimap2 [START_REF] Li | Minimap2: pairwise alignment for nucleotide sequences[END_REF], specifically designed for long erroneous reads. 3) An important step of our method consists in selecting informative alignments, in order to remove i) uninformative alignments, that is those not discriminating between the two possible alleles, and ii) spurious false positive alignments, that are mainly due to repeated sequences. 4) Finally, for each SV, the allele frequency is measured based on the number of supporting alignments, in order to estimate genotype.

Evaluation on simulated data SVJedi was assessed on PB simulated long reads for the human chromosome 1, with 1,000 real characterized deletions found in dbVar [START_REF] Phan | dbvar structural variant cluster set for data analysis and variant comparison[END_REF], ranging from 50 to 10,000 bp, equally distributed among the three different genotypes (0/0, 0/1, 1/1). SVJedi achieved 95.8 % precision, it correctly assigned genotypes to 942 over 987 predicted deletions. Most erroneous genotypes concern deletions of small size (less than 100 bp), as expected these are harder to genotype than longest deletions. As a matter of fact, the precision is of 85.4 % for deletions smaller than 100 bp versus 97.9 % for deletions greater than 500 bp. The remaining false positive deletions of size ≥ 100 bp, were manually investigated, and most of them occur in regions with a high density of mobile elements.

Comparison with SV discovery approaches Then we assessed if these simulated deletions could be easily detected and genotyped by a long read SV discovery tool. We applied here the best to date such tool, Sniffles [START_REF] Fritz | Accurate detection of complex structural variations using single-molecule sequencing[END_REF] to the chromosome 1 simulated read dataset. As expected, none of the 333 simulated deletions with 0/0 genotypes were assigned a genotype in the Sniffles output call set, since a discovery tool naturally only reports present variants. Surprisingly, among the 667 deletions simulated with either a 0/1 or 1/1 genotype, only 406 were discovered by Sniffles, which gives a recall of only 60.9 %. Interestingly, Sniffles also mis-predicts the genotype of the discovered deletions, assigning most of the 1/1 discovered deletions (n = 254, 81 %) as heterozygous. This highlights the fact that Sniffles, a SV discovery tool, is much less precise for the genotyping task than a dedicated genotyping tool.

Application to real human data SVJedi was also applied on real ONT data [START_REF] Jain | Nanopore sequencing and assembly of a human genome with ultra-long reads[END_REF] for the whole human genome of NA12878 individual. As the set of deletions to genotype, we used the merged SV call set provided by the Genome in a Bottle (GiAB) consortium for NA12878 (Mt. Sinai School of Medicine dataset), where only SVs predicted by all methods were kept. This set of known variants contains 1,685 deletions.

SVJedi assigned a genotype to 1,684 deletions, of which 1,514 (90 %) were genotyped exactly as in GiAB. SVJedi took 1h46m on this dataset, including 1h42 for the alignment with Minimap2 parallelized on 40 cpu and with a maximum RAM memory of 6.5 Gbytes.

Conclusions

In this work, we provide a novel SV genotyping approach for long reads data, that is fast and accurate on both simulated and real datasets. This work also demonstrated that this is crucial to develop dedicated SV genotyping methods, since SV discovery methods are not as efficient and precise to genotype variants once SVs have been discovered. The approach is implemented for the moment only for deletion variants in the SVJedi software. However, this proof of principle on deletion variants is a first step before generalizing the approach for all types of SVs. Insertion variants are simply the counterpart of deletions, and inversions and translocations are SVs even more balanced than insertions/deletions regarding the number of breakpoints (with exactly two breakpoints per allele). Therefore, for all these types of SVs, the method will be easily generalized. Our method fills a gap and now enables SV genotyping using long reads for clinical diagnosis or population genotyping. SVJedi is available at https://data-access.cesgo.org/index.php/s/6EhOdOBsVNRr72n, under GNU Affero GPL licence.