Guillaume

Paul

Jonathan Kilian

Antoine Valérian

Les Vincent

Josselin Sébastien

Romain Valentin

Florent Guil- Laume Louis

Université de Caen Normandie et ne doit pas être copié ni diffusé sans autorisation. Toute utilisation en dehors de l'objet expressément prévu est interdite. Il est strictement interdit de reproduire, distribuer et utiliser le contenu de ce document sans l'autorisation préalable de l'auteur. Les contrefacteurs seront jugés responsables pour le paiement des dommages.

CHAPTER 1 Introduction

How to efficiently monitor maritime activities and anticipate abnormal behaviors from vessels that travel the world and the seven seas? Well, everybody is looking for something, and that is the question I want to answer. This quest leads to a very interesting research field that combines operational data, time-series, knowledge graphs and machine learning. This manuscript is made of these, and presents how we use the data transmitted by vessels to predict interactions between them.

To start with a bit of context, this PhD thesis was done in collaboration with Airbus Defence and Space (Elancourt, France) and the GREYC laboratory located in the University of Caen Normandy (Caen, France) in the scope of the CIFRE program (Industrial Research Training Agreements). Led by the French National Agency for Research and Technology (ANRT), it supports French companies that are willing to hire a PhD student and create a research collaboration with a public laboratory, thus facilitating the exchange of knowledge and technologies between the industrial and the academic world.

The core topic of this work is the representation of evolving situations to extract new information. The monitoring of such situations is of particular interest for intelligence or surveillance operators, because they need to know as much as possible about an area or person of interest. This knowledge of situation is also called Situational Awareness. Situational Awareness is critical in many cases such as the protection of human life and property, law enforcement, aviation, air traffic control, ship navigation, health care, emergency response, military command and control operations. It needs three pillars to be effective: perception of the elements in the environment, understanding of the situation, and projection of future status.

The first one focuses on the gathering of heterogeneous data about the area and entities of interest. This data can be hard data, i.e. coming from physical sensors (quantitative, Figure A.1), or soft data, i.e. linguistic data produced by humans (qualitative). The second pillar makes use of this data to extract knowledge about the situation and get all the ins and outs from it. It usually comes as events or interactions between entities of the situation. At last, the third one uses what we grasped from the current situation to predict what may happen in the future. Such inference from the current knowledge provides foresight to the operators,who can better anticipate problems or threats.

CHAPTER 1. INTRODUCTION

Thanks to Situational Awareness, the intelligence operator can perform an analysis to have a better situation understanding. During this analysis, she will establish links between entities of the situation to represent their interaction (for instance, links of affiliation, commandment, subordination, conflict) and create new entities. As of today, this analysis has a very low level of automation and covers a small part of the available data. With the rising number of entities to monitor (persons, vehicles, devices...) and of deployed sensors that massively produce data, it has become nearly impossible for an operator to analyze and assess a situation by hand. There is a need for automation in the monitoring process, so that the operators and experts may look at events of interests proposed by an automated system rather than browsing the large flow of data by hand. To this end, the representation of the knowledge is of uttermost importance and faces several challenges. The data structure must be dynamic to follow the evolution of the situation, contain the attributes and characteristics of each entity and model their interactions with their environment. Since there is always a human in the loop, the information should be easy to visualize, understand and browse. Moreover, any decision taken by an automated system must be interpretable or explainable to win the trust of the human operator., i.e. the operator using it needs to know why the system has taken a decision. In a context of defense and surveillance, it is not possible for decision-makers to accept and use the output of such a system if it is not reliable and justified. And in addition to the uncertainty of the projections, the quality of the data must also be taken into account: an intelligence report may have a typo, sensors have a range and an accuracy (e.g. +/-500 meters), or data loss may happen when satellites receive signals. At last, the monitoring of a situation must be continuous and the forecasts feasible at all times: the perception of the situation (i.e. the addition of new information on the environment) must ideally be made in real-time and its processing for projections made in a reasonable time so that the appropriate reaction can be deployed as early as possible.

CHAPTER 1. INTRODUCTION

Knowledge graphs are increasingly used to represent fields of knowledge: some pairs of nodes in the graph are linked by an edge, thus forming a relation between the two nodes in the form of a triple (subject, relation, object). This network of relations constitutes the knowledge graph, and models information such as (RMS Titanic, :builtBy, WhiteStarLine). Most often, this knowledge is static and does not evolve over time. It can also indicates the time when the events happened (e.g. (RMS Titanic, :builtBy, WhiteStarLine, 1909)). With dynamic graphs, new links can be inferred using temporal dependency learning. This helps to understand the behavior of entities over time.

Additionally, the nodes of dynamic graphs can be enriched with attributes, which characterize each entity. Usually, static attributes are attached to the nodes, such as (RMS Titanic, :size, 269.1), and give more information about the entities. Dynamicity also applies to attributes, especially when dealing with moving entities such as planes, boats or people, e.g., (RMS Titanic, :latitude, 40.963, 23:40 1912/04/14).

From such graphs, relational learning aims at reasoning and inferring new or unseen links between entities, leading to applications such as knowledge graph completion and recommender systems. Generating new links in a graph is now a common AI application, but many state-of-the art techniques mainly focus on static links and attributes, or on dynamic links, but rarely on dynamic links and attributes. When there are only a few relations between entities, the evolution of their attributes can greatly help to characterize them.

With this in mind, vessels, ports, countries, and maritime companies have various interactions, and the status of vessels evolves rapidly. Various data, such as positions, speed, course or destination can be gathered. This data can give more precise knowledge on the ongoing events: a vessel is entering a port, two boats are meeting, or the pattern of a vessel is indicating a fishing activity. Knowing this, a surveillance operator may want to know when and where two vessels will meet, or when a vessel will come back to port given the surrounding context. This also applies to piracy, smuggling or illegal fishing. Such maritime situations can be modelled by dynamic attributed knowledge graphs. The objective is to use such a graph to infer new relations between maritime entities, and hence to improve the maritime situational awareness of the operator by detecting new facts earlier.

The contributions of this work address this task: we propose a dynamic attributed knowledge graph structure to represent evolving situations, and apply a deep learning-based framework made of two temporal neural networks that learn representations of the entities of the situation to predict their future behavior based on past information. Our main usecase is the maritime context, since maritime situations involve moving entities, environmental changes, interactions, sensors, uncertainty and human operators. This work is also fitted to social network analysis, and we will test it on a well-known citation network, DBLP, to see if it generalizes well.

The first part of this manuscript is dedicated to the state of the art made on this topic and is divided in three chapters describing respectively the current methods used to improve Maritime Situational Awareness, the knowledge graph structures, and how to create representation for these graphs and perform link prediction on them. The second part presents our contributions. The first chapter formalizes the link prediction problem on dynamic attributed knowledge graphs. The second one introduces our framework, JointEvolution, and how we designed it. The third part is dedicated to experiments on both academic and operational datasets, and comments on the results. The last part sums up the work done and concludes

Part I

State of the art

CHAPTER 2

Maritime Situational Awareness

The field of maritime surveillance is strongly linked to Situational Awareness, produces large amounts of heterogeneous data and is in need of automated processing. It will thus be the main application domain for our work.

Introduction to Maritime Situational Awareness

Maritime Situational Awareness

Maritime transportation provides the most energy efficient means of transporting large quantities of goods over large distances [START_REF] Kaluza | The complex network of global cargo ship movements[END_REF]. In fact, approximately 90% of all international trade is carried out by sea, which represents more than 50.000 vessels each day for 7.5 billion tons of goods transported across the oceans each year (Figure 2.1). However, the maritime environment might be hazardous: shipwrecks, collision or other life-threatening dangers are to happen with such a dense traffic. Apart from these events, more unlawful ones such as terrorism, piracy, drug/arms smuggling and illegal immigration dampen traffic security and efficiency. To illustrate this, in Africa, Asia, Latin America and the Caribbean, 1,455 piracy or robbery incidents occurred and 25,091 seafarers were impacted between 2015 and 2019. 350 of them were kidnapped or held hostages in 2019 [Joubert, 2020].

Maritime Situational Awareness (MSA) is defined by the International Maritime Organization as "the effective understanding of anything associated with the global maritime environment that could impact the security, safety, economy or environment". The purpose is to establish a picture of the maritime situation at a given moment by perceiving the different elements acting in the considered environment and understanding their significance in order to perform efficient decision making and to forecast what is next.

To be effective, MSA needs an accurate, fresh and constant data stream, trained operators with expert knowledge and explainable decisions. Thus, for efficient MSA, the following challenges must be overcome:

• Fusion of heterogeneous data: to have the best view of a situation, data from various sources must be aggregated into a common data structure. These sources can include CHAPTER 2. MARITIME SITUATIONAL AWARENESS navigational data, sensors data such as temperature, weather, currents or acoustic, images from satellites or Synthetic Aperture Radar (SAR), reports from port authorities... Trajectories, images, texts and sounds must be assembled to create the most complete picture for the surveillance operator.

• Evolution of entities: a maritime situation is a fast evolving world with very little time between two events. In MSA, a good evolutionary model is needed for change detection and the granularity depends on the task. For a change in the position/course/speed of a vessel (dynamic attributes), the information must be given within minutes (e.g. rapid response needed in case of piracy). But to detect a change in a vessel particulars (identifier, name...), the granularity needed can be in hours or days.

• Event and threat detection: an event can be represented by a new relation between two entities or an above-mentioned attribute evolution. If event mining is for fact detection, threat detection is a task highly related to its context and definition. A nation will not consider a transshipping between two fishing vessels as a threat since they are more likely to exchange fish than warheads, but an Non-Governmental Organization (NGO) for ocean conservation can suspect illicit fishing of an endangered species. Performing this task requires either expert knowledge or labeled events.

• Streaming: MSA requires a constant monitoring of maritime areas, meaning that a surveillance model must deal with a continuous flow of data.

• Uncertainty: maritime data often results from hard (sensors) and soft (websites, intelligence) data fusion. However, this data is not always 100% certain: an intelligence report may have a typo, sensors have a range and precision (e.g. +/-500 meters), or collisions may happen when satellites receive signals. This uncertainty must be taken into account when making decisions.

• Explainability: AI-based models are often black boxes when it comes to the origin of an alert. However, a surveillance operator needs to know why a prediction was made in order to understand it and justify any upcoming response to an event. Because operators still do not trust AI-based systems to make decisions, explainability is needed to use automated models for MSA [START_REF] Adadi | Peeking inside the blackbox: A survey on explainable artificial intelligence (xai)[END_REF], but also in general. 1CHAPTER 2. MARITIME SITUATIONAL AWARENESS

AIS/S-AIS data

Maritime navigation relies on AIS (Automatic Identification System), a short range ship-toship and ship-to-shore navigational data exchange system (Figures 2.2 and 2.3). Created as an anti-collision and traffic management system, it is now the main source of data to monitor the maritime traffic. There are two kinds of AIS messages: those received by coastal stations and those received by satellites.

AIS messages

AIS is currently the main source of information available in support of maritime surveillance (Figure 2.3). It uses two VHF frequencies, Channel 87 -131.975 MHz and Channel 88 -162.025 MHz that are dedicated to this system worldwide. AIS messages are collaborative and depends on how the captain of the vessel configured the AIS system that emits the messages. They provide the following information about ships [START_REF] Bigoceandata | The definitive ais handbook[END_REF],Berger, 2018]. Static data is set up during the AIS system installation and only needs to change when the vessel changes its name or is converted to another vessel type:

• The Maritime Mobile Service Identity (MMSI) of the vessel;

• Call sign and name of vessel;

• The International Maritime Organization (IMO) number of the vessel;

• Length and beam;

• Type of ship;

• Location of position fixing antenna.

Dynamic data (or position report) is sent every 2 to 10 seconds depending on the speed of the vessel when moving, and 3 minutes while at anchor. It is automatically updated from the ship's sensors connected to the AIS and includes:

• The MMSI of the vessel;

• The IMO number of the vessel;

• The longitude: in 1/10 000 min (±180°, East = positive, West = negative. 181 = not available);

• The latitude: in 1/10 000 min (±90°, North = positive, South = negative. 91 = not available);

• The course over ground (COG): in 1/10°(0-3599). 3600 = not available);

• The speed over ground (SOG): in 1/10 knot steps (0-102.2 knots. 1 023 = not available);

• The heading (0-360°);

• The type of ship (and the type of cargo).

Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

CHAPTER 2. MARITIME SITUATIONAL AWARENESS

Voyage related data is broadcast every 6 minutes and needs to be manually entered and updated:

• Ship's draught;

• Hazardous cargo (type) (e.g. DG (Dangerous goods), HS (Harmful substances) or MP (Marine pollutants);

• Destination and ETA.

Figure 2.2: AIS communication [START_REF] Bigoceandata | The definitive ais handbook[END_REF] There are two classes of AIS equipment, class A and class B. According to the International Maritime Organisation (IMO), AIS class A equipment is compulsory for:

• 300 or more gross tonnage engaged on international voyages,

• All cargo ships of 500 or more gross tonnage not engaged on international voyages,

• All passenger ships and tankers regardless of their size.

AIS class A currently represents about 60.000 ships. But since the introduction of AIS class B in 2007, hundreds of thousands of vessels now have AIS equipment. Class B messages have a range limited to 10 nautical miles (1 NM = 1852m) to avoid overloading the bandwidth. They also withhold less information than class A, being limited to:

• MMSI (Maritime Mobile Service Identity);

• Call sign and name of vessel ; CHAPTER 2. MARITIME SITUATIONAL AWARENESS CHAPTER 2. MARITIME SITUATIONAL AWARENESS

S-AIS messages

Despite a near ten-meters precision, AIS has a very limited range (37-74 km): this is the reason why AIS is often coupled with S-AIS, which is the same but with satellites instead of coastal stations. The precision is not as good as AIS in dense areas but we have a huge gain in range: sensors from an AIS satellite can reach 5000 km at 650/850km altitude [Le [START_REF] Guillarme | [END_REF].

The problem with S-AIS data is the message collisions due to the uncoordinated emission of messages from ships belonging to different areas but in the scope of the same satellite: these interferences are the main limitation of this detection equipment. That is why both AIS and S-AIS data are needed to achieve complete maritime domain awareness, as well as having several AIS data providers.

Usecases

With AIS, maritime authorities have access to navigation information to monitor their Regions of Interest (ROI). It also facilitate voice communication and the exchange of vital information such as speed, position and heading. Now that it is well developed and widespread, it is used to assess activities and detect anomalies thanks to a better access to information. A deviant trajectory can be spotted without having a visual on the vessel, dangerous cargoes in an unusual maneuver can be spotted and ports can manage the traffic better in their vicinity.

Since it is easy to get unnoticed in the immensity of the ocean, the maritime domain is the theater of many illicit activities such as illegal immigration, smuggling, piracy or terrorism, but also environmental threats like oil spilling or illicit craft discharge [START_REF] Serry | Le système d'identification automatique (AIS). Une source de données pour étudier la circulation maritime[END_REF]. AIS provides information to detect such behaviors thanks to anomaly detection systems, rule-based engines or learned models but being a collaborative source, it also has its limitations and other sources are needed to achieve MSA.

Limitations

The collaborative nature of AIS is its main weakness: the reliability of the information mainly depends on the users of the vessel. The captain can turn it off or forget to update an information (destination), installation errors may provide faulty values (MMSI) or not precise enough vessel's type categories [START_REF] Harati-Mokhtari | Automatic Identification System (AIS): A Human Factors Approach[END_REF]. Technical difficulties are also to be considered. The range of traditional AIS is rather limited (20-40 nautical miles) and S-AIS can operate further from the coastline but at the cost of precision due to the uncoordinated emission of messages from ships belonging to different coverage regions [Le [START_REF] Guillarme | [END_REF]. The latency induced by the transmissions also degrades the quality of the data and the theoretical 2 to 10 sec when underway is rarely found. Indeed, the observed gaps between two observations of the same vessel are often of several minutes or hours, meaning that we may have no information on the vessel's whereabouts for a large period of time. Moreover, small vessels cannot be followed since AIS is not mandatory for them and hence other techniques are required, such as detection from spaceborne images [START_REF] Kanjir | Vessel detection and classification from spaceborne optical images: A literature survey[END_REF]. At last, AIS can also be tampered with to falsify information and deceive the authorities [START_REF] Iphar | Risk Analysis of falsified Automatic Identification System for the improvement of maritime traffic safety[END_REF]: a smuggler may change its identity, or the presence of vessels on a coastline can be simulated with false transmitted positions. There exist ways to detect such forgery, such as AIS/radar comparison [START_REF] Katsilieris | Detection of malicious AIS position spoofing by exploiting radar information[END_REF], but this often requires other data sources. The Long Range Identification and Tracking system (LRIT) is a complementary system that also provides positional data, but it is meant for long-CHAPTER 2. MARITIME SITUATIONAL AWARENESS range tracking and is only accessible to concerned parties. With only one emission every 6 hours,2 it is not suitable to replace AIS in MSA, at least not for swift responses.

In a nutshell:

• MSA is required to monitor the maritime traffic;

• A streaming flow of heterogeneous data is needed for this;

• AIS is the main source of information but is not sufficient;

• Anomaly/event detection can be performed on AIS.

Anomaly and event detection

Maritime Situational Awareness often focuses on anomaly detection [START_REF] Riveiro | Maritime anomaly detection: A review[END_REF]. Anomalies or unexpected behaviors (e.g. unusual fishing pattern) are the main center of interest for surveillance operators, along with the search for specific events such as an encounter between two vessels.

What is an anomaly?

The concept of anomaly is ill-defined and can vary depending on the domain in which it is used. A common definition of anomaly (or outlier) is the one quoted in [START_REF] Hodge | A survey of outlier detection methodologies[END_REF]:

An outlying observation, or outlier, is one that appears to deviate markedly from other members of the sample in which it occurs.

A more behavior-driven definition is given by [START_REF] Khatkhate | Modelling and system identification of an experimental apparatus for anomaly detection in mechanical systems[END_REF]:

An anomaly is defined as deviation from the nominal behavior of a dynamical system and is often associated with parametric and non-parametric changes that may gradually evolve in time.

In the case of maritime awareness, normalcy and context must both be taken into account to define an anomaly. With AIS data, it is relatively easy to extract the main maritime routes and to spot any vessel that deviates from these "normal" routes. However, the context is important to explain this deviation. One may think that this vessel is engaging in illicit activities, when the real reason for the deviation is strong winds and currents, or a damage that put the vessel out of control. In either case, the reported position is still an anomaly compared to the majority of observations and should not be discarded. If the weather should not raise an alert for danger on the deviation, the ship may require assistance if it is damaged. For this reason, each anomaly must be put into context before reaching a conclusion on its nature.

The characteristics of an anomaly are inherent to the system in which it occurs. In maritime situation, we can distinguish two kinds of anomalies [Roy, 2008]:

CHAPTER 2. MARITIME SITUATIONAL AWARENESS
• Static anomalies which are related to static information about a given vessel: its name, its MMSI, the type of the ship. . . A static anomaly can be a change or a lack in information that prevents vessel identification.

• Dynamic anomalies, split up in two subcategories:

-Kinematic anomalies related to information such as location, speed and course, -Non-kinematic anomalies related to information such as passengers, cargo and crew.

The dynamic anomalies are more detailed in Figures 2.6 and 2.7. The most common detected anomalies are kinetic anomalies thanks to AIS messages. Non-kinematic anomalies are much more difficult to detect because the data is not easily accessible. But lists exist for crew, cargo and passengers and can be wrong, on purpose or not. Such data can reinforce other anomaly detection, for instance when a vessel deviated from its course and a convicted felon is on board. At last, static anomalies, also visible with AIS, can reflect illegal behavior through identity fraud or incompatibility between current activity and vessel type. In this work, we will focus on ship positions, proximity and speed to detect events.

Figure 2.6: Taxonomy of dynamic, kinematic anomalies [Roy, 2008] Figure 2.7: Taxonomy of dynamic, non-kinematic anomalies [Roy, 2008] CHAPTER 2. MARITIME SITUATIONAL AWARENESS

An overview of anomaly detection techniques

To spot the outliers, anomaly detection techniques must be devised. In most cases, normal data is used to generate a normalcy model to discriminate the samples that diverge too much from it, as stated in [START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF]:

Anomaly detection approaches build models of normal data and then attempt to detect deviations from the normal model in observed data.

Commonly, there are three anomaly detection techniques:

• Supervised techniques, using both normalcy and abnormality models to create a learning base. The two classes must be represented equally and encompass a wide range of examples in order to achieve good classification performance.

• Semi-supervised techniques, using only a normalcy model. As they require only the normal instances, they are more widely applicable than supervised techniques.

• Unsupervised techniques, which can detect outliers without any model assuming the majority of the studied instances is normal. With the massive presence of unlabeled data in the maritime ecosystem, the choice to generate a model based on the assumption that most observations are normal is the most frequent [START_REF] Riveiro | Maritime anomaly detection: A review[END_REF].

The choice of a technique mainly depends on the availability of labeled data. For an exhaustive review of anomaly detection techniques see [START_REF] Chandola | Anomaly Detection: A Survey[END_REF], Mao et al., 2016].

Maritime events

When we look globally at the maritime traffic, the dangerous or illicit events are considered to be rare and unusual and thus fit the definition of an anomaly. Detecting them is an arduous task because we have lots of data from which we have to extract significant elements, hence the need for an automated detection tool for anomalous events.

Those events have root causes that can be identified with the available positional data. Each fishing method has its own pattern [START_REF] Souza | Improving Fishing Pattern Detection from Satellite AIS Using Data Mining and Machine Learning[END_REF], a transshipment between two vessels means that they are very close and moving slowly or stopped, and a go-fast for smuggling can be spotted with an unusual speed (although they rarely have an AIS system). These causes are known by experts, who can use their knowledge to create rule-based systems to detect these events or look for known patterns. Without expert knowledge, datadriven approaches can learn these causes by correlating them with the consequences during the learning of a sequence of events.

Here is a non-exhaustive list of maritime events that can be detected from positional data and context: • Fishing in a restricted area;

• ...

In a nutshell:

• An anomaly is an observation whose behavior is different from the others;

• Anomaly detection can be supervised, semi-supervised or unsupervised;

• Maritime events can be extracted from position data or contextual information.

Previous works

Maritime Situational Awareness has already been the subject of extended research works, and many systems have been devised to improved it. They tackle anomaly detection, but also route estimation and event detection. We present here some of the works that exist pertaining to these tasks, but this is not an exhaustive list given the large number of works.

Anomaly detection

Anomaly detection has been subject to a lot of research, even in the maritime domain. In [START_REF] Mao | An automatic identification system (AIS) database for maritime trajectory prediction and data mining[END_REF] and [START_REF] Riveiro | Maritime anomaly detection: A review[END_REF], the authors made a survey of existing techniques. We present below some of these techniques that use AIS data:

Positional and kinematic anomalies

Positional and kinematic anomalies can be directly extracted from AIS. They are related to the normalcy of the trajectories.

Trajectory Cluster Modelling (TCM) TCM [START_REF] Riveiro | Supporting Maritime Situation Awareness Using Self Organizing Maps and Gaussian Mixture Models[END_REF] clusters the trajectories, represented by (lat, lon, speed, velocity) vectors, using a self-organizing map [Kohonen, 1998] and apply a Gaussian Mixture Model (GMM) to model the characteristics of the clusters. The probability for a new sample to be anomalous is obtained by applying Bayes' rule on GMM probabilities.

Another clustering approach is proposed by Le [START_REF] Guillarme | [END_REF]. They first separate trajectories into two categories: Move and Stop trajectories. The trajectories are then cut into several parts using a sliding window algorithm that detects direction changes. These parts are then clustered using the OPTICS algorithm, and patterns are created from them. Using the distributions of the positions, speeds and courses of each pattern, it is possible to evaluate the normalcy of an observation (= an AIS) with a chi-squared test. At last, using the patterns as states, a Hidden Markov Model can represent the transition between the patterns and predict the most probable new pattern.

CHAPTER 2. MARITIME SITUATIONAL AWARENESS

• Pros: handles static and kinematic anomalies, good performance.

• Cons: high computational cost, not easy to update with new samples.

Normalcy Box (NB) The Normalcy Box method [START_REF] Rhodes | Maritime situation monitoring and awareness using learning mechanisms[END_REF] defines a series of nesting regions over a port area. After being presented with a labeled historical motion of a set of vessels, the system learns the acceptable maximum and minimum speed for vessels in each region. Once these normalcy models are learned, any observation that does not fit its box is considered as unusual.

• Pros: Online learning ability.

• Cons: Needs expert knowledge, cannot detect static anomalies.

Holst Model The Holst model [A. Holst and Ekman, 2005] defines a grid over a port area. It then attempts to model the velocity distribution in each grid cell by a GMM, whose parameters are estimated using Maximum Likelihood optimized with an Expectation Maximisation algorithm. Anomalous instances can be detected by thresholding over the probability distribution obtained.

• Pros: unsupervised learning, good performance.

• Cons: lot of normalcy training, high computational cost.

Adaptive mixture based Neural Network This method is presented in [START_REF] Garagic | Adaptive mixture-based neural network approach for higher-level fusion and automated behavior monitoring[END_REF]. It consists in neural networks that detect deviations from normalcy and the number of components and the parameters are estimated from the data. The network utilizes a recursive version of the Expectation Maximization algorithm to minimize the Kullback-Leibler information metric.

• Pros: unsupervised, online, robust to noise and operator error.

• Cons: no real performance test provided, high number of false positives.

Bayesian Networks To build a maritime Bayesian network [Mascaro et al., 2014, Johansson and[START_REF] Johansson | [END_REF], the variables (or states) must represent the maritime situation. States can represent the ship type (cargo, passenger, tanker...) or the speed in a discrete manner (0-10 knots, 10-20 knots...). The directed edges between the states are then defined using expert knowledge and the training data. Once the network is trained, the probability of a succession of states (or behavior) is computed. If this joint probability is below a defined threshold, then the behavior is anomalous. [START_REF] Mascaro | Anomaly detection in vessel tracks using Bayesian networks[END_REF] extended this model with contextual information such as weather or the hour of the day to create a more complex (and precise) representation.

• Pros: easy to include expert knowledge, easily verified by non-experts, very powerful in modeling cause and effect.

• Cons: performance very sensitive to modeling assumptions, a lot of expert knowledge required.

CHAPTER 2. MARITIME SITUATIONAL AWARENESS

Complex anomalies

Complex anomalies can be assimilated to illegal events, such as smuggling or spoofing. [START_REF] Kowalska | Maritime anomaly detection using Gaussian Process active learning[END_REF] used Gaussian processes to detect anomalies by computing the distance between the predictions of the model and the actual positions. This was successfully applied on scenarii involving smuggling and terrorism, and can also be used to detect spoofing.

Spoofing can be used to conceal the entrance in a forbidden zone or an illegal transaction. [START_REF] Katsilieris | Detection of malicious AIS position spoofing by exploiting radar information[END_REF] uses Gaussian probability density function to formulate the spoofing detection problem in the context of hypothesis testing (true AIS or spoofed). The hypothesis are then tested with a varying number of radars and spoofing distance. Mazarella et al. [START_REF] Mazzarella | A novel anomaly detection approach to identify intentional AIS on-off switching[END_REF] tackles the AIS on-off switching problem. To make the difference between not received AIS and intentional transmission termination, the authors created two normalcy models: one for the vessel tracks and one for the AIS Base Stations that receive the messages. A risk level is computed with both models and triggers an alert from a certain threshold. The drawbacks of these works is that anomalies have to be classified using expert knowledge or to be specifically looked for.

Route estimation

Route estimation is the task of creating a model that captures the kinematic behavior of vessel and can estimate their future position. [START_REF] Perera | Ocean Vessel Trajectory Estimation and Prediction Based on Extended Kalman Filter. 2nd International Conference on Adaptive and Self-adaptive Systems and Applications[END_REF] opted for an Extended Kalman filter: this filter uses a dynamic model (like the laws of physics) and applies it to a system. Knowing the control inputs on that system and with multiple sequential measurements, the next state of the system can be estimated. [START_REF] Zissis | Real-time vessel behavior prediction[END_REF] uses an Artificial Neural Network, while Forti et al. [START_REF] Forti | Prediction oof Vessel Trajectories From AIS Data Via Sequence-To-Sequence Recurrent Neural Networks[END_REF] applied a more complex neural network that works with sequences (recurrent network). These data-driven approaches are effective and require little to no expert knowledge, but their main drawback resides in its absence of explainable decisions for a surveillance operator.

Event detection

Events are consequences with causes: the proximity between two vessels is related to a similar position, fishing activities can be detected with a speed and course pattern, and the disappearance of AIS positions can be caused by human intervention or bad atmospheric conditions. To detect these events, Alvarez et al. [START_REF] Alvarez | AIS event-based knowledge discovery for Maritime Situational Awareness[END_REF] discretize the studied area into a grid of 0.25 × 0.25 nautical miles cells and set triggers for event detection, e.g. a proximity event when two vessels are in the same cell or the entrance in an area of interest. [START_REF] Artikis | An Event Calculus for Event Recognition[END_REF] chose a symbolic approach with predicates made to recognize patterns. The rule-based systems are very effective at finding events when their causes are known, but they require extensive expert knowledge, and the systems can become very complex with hundreds of rules.

CHAPTER 2. MARITIME SITUATIONAL AWARENESS

In a nutshell:

• A lot of AIS-based anomaly detection techniques are available;

• Complex anomalies require contextual information such as weather or AIS base stations behavior;

• Data-driven models exist for route estimation and are effective;

• However, event detection is more complex and still requires hand-crafted rules.

Conclusion

The widespread availability of AIS data in large quantities made data analysis and mining for Maritime Situational Awareness possible. Automated anomaly detection became available and anomalous observations can now be spotted without mandatory human intervention.

Still, the collaborative nature of AIS makes it prone to error or manipulation, and corrective techniques are required to ensure the completeness and trustworthiness of the data. From the correctly preprocessed AIS and contextual information, it is possible to extract complex events such as transshipping or smuggling. However, this requires either a discretization of the situation states or the hand-crafting of expert rules. At last, automated models often focus on one type of events.

Goal of our thesis

This work is focused on event detection and prediction: our goal is to create a model that learns the behavior of vessels using labeled events between entities of the situation (vessels, ports, companies...) and automatically detects the causes of these events to look for similar patterns elsewhere in the data. So instead of telling the model how to find the events, we feed it with events, AIS data and contextual information, so that it can learn the causes by itself.

CHAPTER 3

A formal framework and background for graphs

Representing a maritime situation requires some tools to characterize the entities, so we naturally turned to knowledge graphs for their effectiveness to describe objects and interactions. This chapter introduces the concept of a knowledge graph, and the notation framework and definitions that we will use through the manuscript.

Introduction to knowledge graphs

Resource Description Format

RDF stands for Resource Description Format. According to [Yu, 2007], it is:

• the basic building block for supporting the Semantic Web,

• to the Semantic Web what HTML has been to the Web,

• capable of describing any fact (resource) independent of any domain,

• structured i.e. machine-understandable. Machines can do useful operations with the knowledge expressed in RDF.

RDF works with triplets (Figure 3.1) of the form (Resource, Property, Object). A resource can be anything, described by an RDF expression. Whether it is a web page, an animal, an object, a person, it can be identified using a Uniform Resource Identifier (URI) that can be used to name the resource. This name is unique to avoid ambiguity between two RDF resources. A property is also a resource and can be described as such, but its purpose is to describe another resource: its attributes, its relation to other resources... At last, the object is the value of the property given to the resource. It can be the value of a characteristic (e.g. "blond" for the property "hair color") or the second member of a relation (e.g. a family link). The property value can be a string literal or a resource. Therefore, in general, an RDF triplet indicates that a resource (the subject) is linked to another resource (the object) via an arc labeled by a relation (the predicate) [Yu, 2007]. It can be interpreted as follow:

The RMS Titanic was built by The White Star Line Subject Property Object

Ontologies

An ontology is the descriptive schema of a field of knowledge. It defines the properties of each resource, whether they describe an attribute of the resource or how it can interact with others. Figure 3.2 shows the schema for the writer and humorist Douglas Adams. The shown property is educated at, which describes his education. The object (or value) of this property is St John's College. If we follow the link to St John's College, we will also find a schema for this resource. Note that Douglas Adams is an instance of the class human and person, and that the property educated at is relevant to these classes and not only to Douglas Adams. We can also note that the property educated at has several qualifiers since it is also a resource. We thus learn that Mr Adams' education took place from 1971 to 1974, which introduces the notion of duration for an event (or at least, a starting date and an ending date). Many other properties are not shown here, such as his place and date of birth, his relatives, etc.

Figure 3.3 brings us back to the maritime application. It describes a part of the dat-ACRON ontology [START_REF] Vouros | The datacron ontology for the specification of semantic trajectories[END_REF] that specifies semantic trajectories. For instance, a Trajectory is composed of Trajectory Parts that have spatial and temporal features, and events such as Move, Stop, Fishing or Loitering occur during a specific part of a trajectory. These trajectories apply to a moving object, generally a vessel in our case (but it could be a . Such an ontology is a great help to define a maritime situation.

Knowledge graph

A knowledge graph (KG) represents the interactions between entities using the RDF standard. The nodes of the graph are entities and its edges are the facts that the relationships represent. [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF] call an event of a KG a Subject-Predicate-Object (SPO) triplet. This type of graph is oriented to know which node is the Subject and which one is the Object. [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF] With this structure, it becomes easier to get knowledge from the set of RDF triplets thanks to classical graph analysis tools. We can use the neighborhood of a node (e.g. find all Science Fiction movies), find a path between two entities to see if they are linked (is Alec Guiness related to Science Fiction?) or more generally perform question answering.

Closed and open world assumptions

Two assumptions can be made about the world we are trying to describe: the closed and open world assumptions [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF]. The closed world assumption (CWA) tells that if a triplet does not exist in the KG, then it is a false relationship, i.e., what happened is exclusively restricted to the available triplets. This assumption is convenient because it allows us to generate false events without a risk for them to be actually true. It is often used [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF]. Nodes represent entities, edge labels represent types of relations, and edges represent existing relationships as a reduction of real-world problems where we consider that the observer is omniscient. On the contrary, the open world assumption (OWA) considers the existing triplets to be true, but assumes nothing about the missing ones. Thus, a missing triplet could be a missed observation as well as a false fact.

The RDF standard makes the OWA [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF]. Since most KGs are incomplete, this is the safer option. It is also the best option for MSA: as stated in chapter 2, AIS observations can be missed and vessels can go under the radar. Missing observations will however be a difficult problem to solve, and one of our pain point in Chapter 6 when dealing with positive and negative events.

Schema-based and schema-free knowledge base

A knowledge base can have a strict way of describing entities or give more latitude to name them and their properties. We can thus define two main types of KGs [START_REF] Nickel | A Review of Relational Machine Learning for Knowledge Graphs[END_REF]]:

• Schema-based KGs: each entity is referred to using a unique ID. For instance, the fact that Barack Obama is born in Honolulu is represented in Freebase by the triplet (/m/02mjmr, /people/person/born-in, /m/03gh4). The ID /m/02mjmr is the unique way to refer to Barack Obama, and /people/person/born-in is the unique property to tell a person's place of birth. Such a schema applies hierarchy and constraints on the KG, visible on the previous property: Barack Obama belongs to the class "person" which is a subclass of "people" (and then "human" and so on). At the same time, this property "born-in" can only apply to a person, and the object must be a place. In the MSA case, a schema-based KG would mean to rely exclusively on the definitions presented in the datACRON ontology.

• Schema-free KGs: in a schema-free KG, the same fact about Barack Obama can be described as ("Obama", "born in", "Hawaii"), as well as ("Barack Obama", "place of birth", "Honolulu"). The entities, properties and objects are not disambiguated and may have different identifiers (although here, "Honolulu" is more precise than "Hawaii"). It is easier to add information to a schema-free KG but also more difficult to keep it consistent and avoid information loss: if the same vessel is identified in two different ways, it could be considered as two distinct entities resulting in an incomplete analysis of the vessel. There are ways to identify a duplicated vessel (attributes and tracks comparison, name, captain...), but entity discovery is a field of research on its own between Natural Language Processing (NLP) and Data Fusion, and is not in the scope of this work.

CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS Some KGs can be hybrid and use both systems: a schema defines the core structure of the KG, but any information can be added to it. This is the case for graph and document oriented databases such as OrientDB1 that are specialized in representing KGs and semantic information.

Homogeneous and heterogeneous graphs

We have seen that the edges of a KG are the properties of the SPO triplets, and there are multiple types of properties. In the same way, nodes can be of different natures: such a KG is called a heterogeneous graph. Examples of such networks are those in the medical domain that describe patients, a bibliographic network that deals with authors, publications and organizations (like DBLP)2 or event-based networks (like GDELT [START_REF] Leetaru | GDELT: Global Data on Events, Location and Tone[END_REF]).

However, some simpler networks have a single type of nodes and edges. Those are homogeneous networks and are largely represented by social networks (an edge = a friendship link) and the World Wide Web. According to [START_REF] Getoor | Link mining: a survey[END_REF], learning on homogeneous graphs is "consistent with the classical statistical inference problem of trying to identify a model given an independent, identically distributed sample". But applying such techniques to heterogeneous graphs can give misleading conclusions on the data since the different types of relations and nodes are not taken into account. The semantic information around the network must be used to improve the accuracy of the learned models. A KG build for MSA is obviously a heterogeneous network given the complexity and the variety of the possible interactions.

An introduction to dynamicity and attributes

All the KGs presented until now are static graphs. Each SPO triplet is considered to be valid, but there is no indication as to when it happened. Of course, properties can introduce dates, for instance ("The RMS Titanic", "built_in", "1912"). But what to do with the triplet ("Vessel1", "enter_in", "Port2")? A surveillance operator will indeed know that a specific vessel has entered a designated port, but when? The quadruplet ("Vessel1", "enter_in", "Port2", "24 November 2020, 16:34:22") is much more useful to follow the whereabouts of the vessels. A set of such quadruplets forms a dynamic (or temporal) knowledge graph.

Moreover, the current SPO format does not distinguish the relational triplets from the descriptive ones. The ("Vessel1", "enter_in", "Port2") triplet refers to an event, but ("Vessel1", "has_size", "125m") defines how Vessel1 is. Structurally, it is an SPO triplet like another, but the type of information it gives is different. From now on, we call the first type of triplets relational and the second attributional. To give a more formal definition, the Object of an attributional triplet is not considered as an entity (e.g. "125m", which is a value). However, the line between the two can sometimes be blurry. If we consider the triplet ("Vessel1", "has_flag", "France"), what is "France"? It can either be the entity France with its own relations to other entities, or a part of the set of discrete possible values for the attribute "flag". It depends of the context of the situation, but generally, if the Object is used as an entity elsewhere, then it is a relation. These choices must be reflected by the schema used to build the KG. Our choices will be detailed for each dataset under study in Chapter 7.

CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS

Embeddings

Embeddings are continuous vector representations that have been popularized in NLP tasks by word2vec [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF], and in knowledge graph processing by TransE [START_REF] Bordes | Translating Embeddings for Modeling Multi-relational Data[END_REF]. An embedding represents an object by projecting it to a latent vector space, so as to retain its features and make it comparable to the others. The figure also shows that books are grouped by genre, meaning that the embeddings retain the features of the books well. These embeddings can be used to run nearest neighbors algorithms (e.g. for recommendations like above), to compute similarity measures or as input for downstream machine learning tasks. The same process can be applied to entities of a maritime situation (Table 3.2: features and movements of vessels can be projected into an embedding and be used to learn how two of them interact). We will use embeddings as feature vectors that can be regularly updated, and we will use one-hot vectors to access them from the matrix they are stored in. In a nutshell:

• The RDF standard describes facts as (Resource, Property, Object) triplets;

• An ontology is a schema that defines how the Resources and Properties work and generally represents a field of study;

• A knowledge graph (KG) is a set of RDF triplets that represents interactions between entities of a situation;

• The close world assumption considers all absent triplets to be false while the open world assumption tells nothing about them;

• A schema (or ontology) is not mandatory for a KG, but it is advised;

• KGs with node and edge types are more difficult to use but are more precise;

• KGs can include temporal information and attributes for nodes;

• Embeddings can hold the features of the entities for further analysis.

CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS

Framework

In this section, we present the notation we will use through this manuscript to describe knowledge graphs and their representations. A large part of the works in the literature does not use the same notation and our goal is to have a unified writing when presenting them. We consider three settings for KG: static, dynamic, and attributive. Note that a KG can be static and attributive, or dynamic and attributive.

Static Knowledge Graphs

A static knowledge graph refers to a graph with no temporal information, as described in Section 3.1.3. From now on, we will refer to the components of an SPO triplet as entities and relations that respectively define the nodes (or vertices) and edges of the KG.

Definition 1 (static relational KG). Let E and R be two finite sets of entities and relations, respectively. A static relational knowledge graph KG R is a finite subset of E × R × E. For a triplet p R = (e s , r, e o ) ∈ KG R , e s is called the subject of p R , r its relation, e o its object.

In some settings, a static KG can be composed of a relational KG and an attributive KG. This KG describes the attributes given to each entity using a network just like the relational one.

Definition 2 (static attributive KG). Let A be a finite set of attributes, and D be a function assigning a domain D a ⊆ R to each attribute a ∈ A. An attributive graph KG A is a finite subset of E × A × R such that for all triplets p A = (e, a, v) ∈ KG A , v ∈ D a holds. For a triplet p, e is called its entity, a its attribute type and v its attribute value.

Note that the function D of Definition 2 is for continuous values, but some domains can also be discrete. In this case, we have D a ⊆ V ⊆ R, with V a set of discrete values.

Dynamic Knowledge Graphs

When time is taken into account, the static KG becomes a dynamic (or temporal) KG, written DKG. Time-aware quadruplets are defined as follows.

Definition 3 (relational DKG). Let E and R be two finite sets of entities and relations, respectively, and let T be a set of time points. A dynamic relational knowledge graph DKG R is a finite subset of E × R × E × T. For a quadruplet q R = (e s , r, e o , t ) ∈ DKG R , e s is called the subject of q R , r its relation, e o its object and t its timestamp.

Definition 4 (attributive DKG). Let A be a finite set of attributes, and D be a function assigning a domain D a ⊆ R to each attribute a ∈ A. An dynamic attributive knowledge graph DKG A is a finite subset of E × A × R × T such that for all quadruplets q A = (e, a, v, t ) ∈ DKG A , v ∈ D a holds.

We will refer to a pair DKG = (DKG R , DKG A ) as a (full) knowledge graph, whose relational (resp. attributive) part will always be written DKG R (resp. DKG A ). This is also valid for KG, KG R and KG A . For notational brevity, we will often simply write (s, r, o, t ) for a relational quadruplet, and we will use q instead of q R , q A when the type of quadruplet is clear from the context. Figure 3.6 gives an example DKG. The nodes e i ∈ E are entities and the nodes a j ∈ A are attributes. The relations r n ∈ R are written on the edges between two CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS entities. The values v k , written on the edges between an entity and an attribute, belong to the domain D a of the attribute they are attached to, and notation t ℓ denotes the timestamp of an edge. Attributes of entities can change their value over time (e.g., e 3 and a 2 ), and two entities can share attributes (e 4 , e 1 and a 1 ), but not necessarily with the same value. The blue nodes and edges together make DKG R , and the red edges with all the nodes together make DKG A . In a static context, the same notation applies with KG in place of Sliced DKG Definitions 3 and 4 refers to a streamed DKG, where the timestamps are not fixed in advance and where each timestamp is the timestamp of a quadruplet (or observation). In the case of a sliced DKG, the graph is a sequence of snapshots from the dynamic graph. A sliced DKG (S-DKG) is formally defined by S-DKG = {DKG 1 , DKG 2 , . . . , DKG τ }, where DKG t is the state of the graph at time t ∈ T = [1, τ]. For instance, slicing applied to MSA means that we create a snapshot of the situation every 5 minutes, while streaming means that we update the situation each time we receive a new observation. The use of snapshots may induce a loss of information but creating models on them is generally easier [START_REF] Kazemi | Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey[END_REF]. In this work, we use streaming DKG since dealing with streaming data is one of the requirements to achieve MSA.

Embeddings and history

As mentioned in Section 3.1.8, entities can be represented by embeddings. In a static setting, the embedding models all the known triplets of the KG. It can be defined as follows for attributes and relations.

Definition 5 (static embedding of attributive history). A static attributive embedding function is a function which maps an entity e and a set of timestamped attributive triplets KG A e for e to a vector in R m , written α e and called the attributive embedding of e.

Definition 6 (static embedding of relational history). A static relational embedding function is a function which maps an entity e and a set of timestamped relational triplets KG R e for e to a vector in R n , written ρ e and called the relational embedding of e.

In a dynamic context, the entities of a DKG evolves over time and the embedding can change accordingly. An embedding set at time t takes into account the history of its entity until time t and is defined as follows:

Definition 7 (embedding of attributive history). Let DKG A,<t e be the restriction of the DKG to the attributive quadruplets of entity e in A before time t and let α t - e be the embedding of CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS the history of all the attributes of entity e ∈ E before time t. The function f :

DKG A,<t e → R m
is the function that maps the history to an embedding of size m.

Definition 8 (embedding of relational history). Let DKG R,<t e be the restriction of the DKG to the relational quadruplets of entity e in R before time t and let ρ t - e = f (DKG R,<t e ) be the embedding of the history of all the relations/events involving entity e ∈ E before time t. The function f : DKG R,<t e → R n is the function that map the history to an embedding of size n. [START_REF] Feng | GAKE: Graph Aware Knowledge Embedding[END_REF] characterizes three types of graph context:

• The first is the neighbor context, or the set of triplets in KG;

• The second is path context: a path is a sequence of relations that connects two entities;

• The last and third is edge context, i.e. the set of relation types the entity has with others. For instance, Douglas Adams is likely to be included in relations such as :bornIn, :diedIn, :hasWife or :isAuthorOf, all indicating that he is a Person.

These three contexts are the main ones that are used in the literature and they are often used in embedding techniques to define what is taken into account in the embedding.

Conclusion

We laid out the theoretical context for knowledge graphs and entity embeddings. We define the prediction problem at hand as a link and attribute values prediction problem in a dynamic graph, both relational and attributive (DKG R , DKG A ). Observed events will be formalized as relational and attributive quadruplets, and each entity will be given a relational embedding and an attributive embedding. Using the notation we just defined (summed up in Table 3.3), we will now review the literature for embedding and link prediction in static (attributed) and dynamic (attributed) Embedding and link prediction in knowledge graphs

This chapter is dedicated to the state of the art of embedding and prediction techniques for (knowledge) graphs. We first describe how the knowledge graphs can be used to get new information, and then tackle the different embedding techniques by types of graphs: static, attributed, and dynamic. The last section is dedicated to the addition of semantic information in the processing of the graph. Everything in this section will be presented using the notation defined in Chapter 3.

Knowledge graphs applications

Knowledge discovery in graphs can take several shapes and work at different levels, such as edge level, entity, triplet/quadruplet or timestamp. Figure 4.1 sums up the different tasks. In this work, we will focus on the link prediction task and, to a lesser extent, on the attribute value prediction problem. Parameters of models are learnt on data with loss functions, which depend on the usecases. Each reasonable training technique can be used, and we will make precise which ones suit our model.

Link prediction

The link prediction task consists of finding an edge between two nodes that was missing from the graph. In the case of dynamic graphs, it can refer to a link in the future, which is a more difficult task since we generally have little information about the future in the graph, whereas predicting missing values can be performed using past timestamps and ground truth.

Definition 9 (Link prediction). Let KG R be a relational knowledge graph and p R = (s, r, o) ∈ KG R be a relational triplet, with s, r ∈ E and r ∈ R. Given two out of the three components of p R and KG R , the link prediction task aims at finding the third component so that p R is true. For instance, for subject prediction, it comes down to finding the function

f : KG R , r, o → (s, r, o).
An application could be to answer "Which vessel is currently transshipping fish (r) with vessel o"?, and the prediction would be "Vessel s is currently transshipping fish (r ) with o". Link prediction models are often specialized, either in subject and object prediction [START_REF] Bordes | Translating Embeddings for Modeling Multi-relational Data[END_REF], [START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF], [START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF], [START_REF] Nickel | Holographic Embeddings of Knowledge Graphs[END_REF] or in relation prediction [START_REF] Xie | Representation Learning of Knowledge Graphs with Entity Descriptions[END_REF], [Lin et al., 2015a].

Attribute value prediction

Most KGs are incomplete and a missing value for an attribute is not unusual. A common task in KGs is to find these values using other attributes.

Definition 10 (Attribute value prediction). Let KG A be an attributive knowledge graph and p A = (e, a, v) ∈ KG A be an attributive triplet, with e ∈ E, a ∈ A and v ∈ D(A). Given e and a of p A and KG A , the attribute value prediction task aims at finding v so that p A is true. It comes down to finding the function f : KG A , e, a → (e, a, v).

A straightforward example is the prediction of a vessel speed in a dynamic setting, or its length if it is missing in a static context.

Triplet classification

Triplet classification takes the triplet as a whole and determines if it is true or false. This is generally done by computing a score for the triplet with a thresholding step [START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF][START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF].

Definition 11 (Triplet classification). The triplet classification problem takes as input a part of a relational graph KG R and a relational triplet p R = (s, r, o), and asks whether (s, r, o) is in KG R .

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

This is usually done by estimating a likelihood f (KG R , p R ), and answering p R ∈ KG R if and only if f (KG R , p R ) ≥ λ for a given threshold λ. This problem models questions such as "Is boat s currently performing illegal fishing (r ) in the Mediterranean Sea (o)?".

Other applications

Other applications exist, though less connected to our usecase. Entity classification is when the class of an entity e is not known, but can be deduced from the information in the graph. It boils down to solving the triplet (e, : i sA, x) where x is a type of entity, e.g. (Vessel1, :isA, fishingVessel) [START_REF] Nickel | A Three-Way Model for Collective Learning on Multi-Relational Data[END_REF], Nickel et al., 2012].

Resolving an entity, as mentioned in Section 3.1.5, is the task that de-duplicates nodes written in different ways [START_REF] Nickel | A Three-Way Model for Collective Learning on Multi-Relational Data[END_REF], Bordes et al., 2014].

Most of the tasks aim to find an entity or a relation type, but sometimes it is the time associated to the edge that is important. To find this timestamp, a triplet and the DKG are presented to the model that will output the most probable timestamp for this edge.

Static graphs

This section describes the state of the art on methods that deal with static graphs (KGs). This is not an exhaustive presentation of the static graph bibliography, and more details can be found in the surveys by [START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF] and [START_REF] Cai | A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications[END_REF].

Translational models

In a static setting, each node is represented by a single vector. This field is largely covered with a broad range of techniques. Translational models evaluate the likelihood of a fact (subject, relation, object) by measuring the distance between the two entities, typically using the relation during the translation. TransE [START_REF] Bordes | Translating Embeddings for Modeling Multi-relational Data[END_REF] is the most representative translational distance model and has been extended multiple times. A summary of all methods is presented in Figure 4.2.

TransE TransE represents both entities and relations as vectors in the same space R n . Given a fact p R = (s, r, o), the objective is to create a vector for r so that the embeddings of s and o are connected by r with low error. This comes down to minimizing the distance between ρ s + ρ r and ρ o . The scoring function is then defined as the (negative) distance between s + r and o, i.e.,

f r (s, o) = -ρ s + ρ r -ρ o 1/2
The score is expected to be large if (s, r, o) holds, i.e. is an existing triplet in KG R . But this method has problems dealing with 1-to-N, N-to-1 and N-to-N relations.

TransE improvements Several enhanced versions of TransE have been proposed by different authors. To overcome the problems of TransE, [START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF] propose a model which enables an entity to have distributed representations when involved in different relations: Translating on Hyperplanes (TransH). By introducing relation-specific hyperplanes, TransH can identify the interactions between entities better. TransR [START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF] is very similar to TransH but it introduces relation-specific spaces rather than hyperplanes. Its [START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF]. The figures are adapted from [START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF], [START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF] main issue is the loss of simplicity and the higher number of parameters per relation due to the use of a matrix instead of a vector. TransD [START_REF] Ji | Knowledge Graph Embedding via Dynamic Mapping Matrix[END_REF] simplifies TransR by replacing the projection matrix by a product of two vectors. TransSparse [START_REF] Ji | Knowledge Graph Completion with Adaptive Sparse Transfer Matrix[END_REF]] also simplifies TransR by enforcing sparseness on the projection matrix. Some other extensions make improvements by relaxing the translational constraint, i.e. ρ s +ρ r ≈ ρ o [START_REF] Fan | Transition-based knowledge graph embedding with relational mapping proper-ties[END_REF],Xiao et al., 2016, Feng et al., 2016a, Xiao et al., 2015]. Overall, the upgrades on TransE aim to deal with different types of relations while keeping the complexity to a minimum.

Semantic matching models

Semantic matching models use scores to compare the embeddings of entities and relation types, based on their similarity. An illustration of several methods is presented in Figure 4.3.

RESCAL and its extensions

RESCAL [START_REF] Nickel | A Three-Way Model for Collective Learning on Multi-Relational Data[END_REF] was the first semantic matching method and has been extended multiple times [START_REF] Nickel | Holographic Embeddings of Knowledge Graphs[END_REF], Liu et al., 2017].

RESCAL RESCAL [START_REF] Nickel | A Three-Way Model for Collective Learning on Multi-Relational Data[END_REF] assigns an embedding vector to each entity and a matrix to each relation type, which models the interaction between two entities. The score of a fact (s, r, o) is defined by a bilinear function

f r (s, o) = ρ ⊺ s M r ρ o = n-1 i =0 n-1 j =0 [M r ] i j * [ρ s ] i * [ρ o ] j
where M r ∈ R n * n is the matrix associated with the relation type. This score captures how the entities interact by multiplying the latent features of the entities and relations. It requires O(n 2 ) parameters per relation.

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Extensions of RESCAL Like TransE, RESCAL has been extended multiple times. TATEC [START_REF] García-Durán | Effective Blending of Two and Three-way Interactions for Modeling Multi-relational Data[END_REF] models the three-way interactions like RESCAL (entity-relationentity), but also the two-way interactions, i.e. each entity with the relation type. DistMult [START_REF] Yang | Embedding Entities and Relations for Learning and Inference in Knowledge Bases[END_REF] simplifies RESCAL by reducing the number of parameters. HolE [START_REF] Nickel | Holographic Embeddings of Knowledge Graphs[END_REF] takes the best of RESCAL and DistMult to be simple and efficient. Com-plEx [START_REF] Trouillon | Complex Embeddings for Simple Link Prediction[END_REF] extends DistMult by creating the embeddings in the complex space C d . ANALOGY [START_REF] Liu | Analogical Inference for Multirelational Embeddings[END_REF] creates representations that model analogical properties of entities and relations, for instance "Douglas Adams" is to "Hitchhiker's Guide to the Galaxy" what "Georges Lucas" is to "Star Wars". It uses the same bilinear score as RESCAL but requires the matrices M r to be normal and mutually commutative.

Matching with neural networks

Neural Tensor Network NTN [START_REF] Socher | Reasoning With Neural Tensor Networks for Knowledge Base Completion[END_REF] is one of the best-known neural network architecture for graphs. The input layer of the network project the entities into their embedding space, that are then combined using a tensor M r ∈ R n×n×k that is relation specific. It resembles TATEC insofar the subject and object are combined using the relation type representation, but it also has the two-ways interactions subject-relation and object-relation. These interactions are then given to a non-linear hidden layer and then to a relation specific layer that outputs the following score:

f r (s, o) = ρ ⊺ r t anh(ρ ⊺ s M r ρ o + M 1 r ρ s + M 2 r ρ o + b r ) with M r ∈ R n×n×k and M 1 r , M 2
r ∈ R k×n relation-specific weight matrices and b r ∈ R k a bias vector (also relation-specific). It is one of the most expressive models to date but it has two main drawbacks: it overfits on small and medium datasets which leads to not so good scores, and it requires O(n 2 k) parameters per relation, which makes it too computationally expensive for large-scale KGs.

Multi-layer Perceptron MLP [START_REF] Dong | Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion[END_REF] is simpler than NTN: it concatenates the embeddings of each member of the triplet in the input layer and then passes them through a non-linear hidden layer:

f r (s, o) = w ⊺ t anh(W s ρ s ⊕ W r ρ r ⊕ W o ρ o ) with W s , W r , W o ∈ R n×n
the weights of the first layer, w ∈ R 3n the weights of the second layer and ⊕ the concatenation operator.

RDFDNN RDFDNN [START_REF] Murata | Predicting Relations Between RDF Entities by Deep Neural Network[END_REF]] is a neural-based system that predicts the relation r of a triplet p R . It first processes the embeddings of the subject and the object through the same layer and concatenates them. It then goes through a second hidden layer and a softmax layer that gives the predicted relation type for the triplet.

h r (s, o) = t anh(W 1 ρ s ) ⊕ t anh(W 1 ρ o ) f r (s, o) = so f t max(W 3 t anh(W 2 h r (s, o)))
with W 1 ∈ R n×n , W 2 ∈ R ℓ×2n and W ℓ×|R|×ℓ 3 the weight matrices of the network, with |R| the number of relation types. RDFDNN has better results than the methods it compares itself to (TransE, TransR), but it is only good at predicting r , not s and o.

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Graph Convolutional Network Graph Convolutional Network (GCN) [START_REF] Kipf | Semi-Supervised Classification with Graph Convolutional Networks[END_REF] encodes both the local graph structure and the features of nodes into embeddings. The use of the adjacency matrix of the graph allows it to make use of each node neighborhood when building its representation. It performs well on node classification and its time complexity grows linearly in the size of the dataset, but it does not naturally support edge features and is limited to undirected graphs. A simple version of the convolutional model, a two-layer GCN for semi-supervised node classification, can be represented as follows:

f (X, A) = softmax( A ReLU( AXW (0) )W (1) )
with X ∈ R n×|E| the matrix of node features, W 0 ∈ R n×c and W 1 ∈ R c×d the weight matrices of the network with c the number of features for the first layer and d the number of labels for node classes, A the adjacency matrix, D the degree matrix and

A = D -1 2 Ã D -1
2 . The GCN model is extended by [START_REF] Schlichtkrull | Modeling Relational Data with Graph Convolutional Networks[END_REF] to add relation types (R-GCN). The forward-pass update of an entity is expressed as:

h (ℓ+1) i = ReLU( r ∈R j ∈N r i 1 c i ,r W (ℓ) r h (ℓ) j + W (ℓ) 0 h (ℓ) i )
with N i r is the set of neighbor indices of node i under relation r ∈ R, c i ,r the problemspecific normalization constant and h (ℓ) j and h (ℓ) i the hidden representations of nodes j and i at layer ℓ. W r is a relation-specific weight matrix and W 0 a transverse weight matrix.

Walking through a graph

The following methods uses random walks to generate node features. These methods are less node-centered and allow the exploration of a node neighborhood, i.e. its context. node2vec node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF]] is a semi-supervised algorithm that learns embeddings for nodes that maximizes the likelihood of preserving network neighborhoods of nodes. The approach is flexible and explores diverse neighborhoods of a given node using 2 nd order random walks to generate the neighborhood. By interpolating between breadthfirst and depth-first sampling, node2vec can learn local graph structures but also explore further with higher variance in the creation of the paths. Once the neighborhood extracted as a set of paths, a Skip-gram architecture [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] is used to learn the representation with nodes as the vocabulary and paths as sequences of words.

The 2 nd order random walk is defined as follows: for a walk that went from node e t to node e v , the transition probabilities π v x between node e v and nodes e x with x ∈ E is set to

π v x = β pq (e t , e x ) • w v x , where β pq (e t , e x ) =      1 p if d t x = 0 1 if d t x = 1 1 q if d t x = 2
w v x is the static edge weight and d t x denotes the shortest path between nodes e t and e v . The parameter p controls the likelihood of immediately revisiting a node: a high value will mostly lead to an unseen node while a low value fosters backtracking. On the other hand, the parameter q sets the stance of the walk towards breadth-first (high value) or depthfirst (low value) sampling. This sampling strategy is flexible and efficient in time and space complexity. It is used for multi-label node classification and link prediction, but only works on homogeneous graphs.

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

LINE LINE [START_REF] Tang | LINE: Large-scale Information Network Embedding[END_REF] minimizes the first-order and second-order proximities of node embeddings to learn the representations. The first-order proximity, or pairwise connection through an edge, is defined through the following joint probability:

p 1 (e i , e j ) = 1 1+exp(-ρ ⊺ i •ρ j )
The second-order proximity looks for nodes which have the same neighborhood or context. To do so, it computes the sets of first-order proximities between a node and all the other nodes and compares the obtained distributions. A new embedding ρ ′ e , the representation vector of the entity when treated as a context, is introduced. For a directed edge (e i , e j ), the probability of "context" e j generated by vertex e i is defined as:

p 2 (e j |e i ) = exp(ρ ′ ⊺ j •ρ i ) |E| k=1 exp(ρ ′ ⊺ k •ρ i )
The first-order proximity works only on undirected graphs and the second-order one with both directed and undirected. It is possible to use both orders by training the models separately and concatenating the resulting vectors.

GraphSAGE GraphSAGE [START_REF] Hamilton | Inductive Representation Learning on Large Graphs[END_REF] is an inductive embedding method that samples and aggregates features form the local neighborhood of a node so that it can generalize to unseen nodes. The embedding generation unfolds as follows:

• Get node neighborhood;

• Aggregate embeddings of the neighborhood;

• Concatenate node embedding with neighborhood embedding;

• Process the concatenated vectors with a fully connected layer and a nonlinear activation function;

• Normalize;

• Repeat for K steps, with K the depth of the model.

The neighborhood is uniformly sampled from E with a fixed size to reduce the neighborhood space. The authors test three types of aggregators. The mean aggregator takes the elementwise mean of vectors in the neighborhood N(e v ). It is close to the convolutional propagation rule used in GCN [START_REF] Kipf | Semi-Supervised Classification with Graph Convolutional Networks[END_REF].

ρ k e v ← σ(W • MEAN({ρ k-1 e u , ∀e u ∈ N(e v )}))
The LSTM aggregator is the second tested type. It takes the input in a sequential manner, meaning that the neighborhood is processed sequentially in a random order. It takes advantage of the expressiveness of LSTMs. The last one is the pooling aggregator: each vector is processed by a fully-connected layer, then an element-wise max operator is applied (max pooling).

AGGREGATE pool k = max({σ(W pool ρ k e u + b ∪ {ρ k-1 e u }, ∀e u ∈ N(e v )}) CHAPTER 4.

EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

The LSTM and pooling are the best ones, with LSTM being slower than pooling. The initial features ρ 0 e v are taken from the node attributes. In the setting of citation networks, it can be the degrees of the nodes or the word vector of the abstract obtained by word2vec [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] or GloVe [START_REF] Pennington | Glove: Global vectors for word representation[END_REF], commonly used for word embedding in NLP tasks. GraphSAGE performs well on node classification but works only on homogeneous, undirected graphs.

Conclusion

There are two main categories of techniques to embed static graphs: translational methods, based on the distance between feature vectors, and semantic matching based on scores. The semantic matching models are divided between RESCAL and its by-products, neural networks and random walks.

Attributed graphs

A knowledge graph links entities via relations, and in many of them the word "relations" refers indifferently to relations between two entities or between an entity and one of its attributes. Most KG models regard all these relations equally and do not take into account the added value of these attributes. Moreover, the frontier between relation and attribute can sometimes be blurry: is the flag of a vessel one of its attribute or a direct relation to a country? On top of that, relations and attributes behave differently: relations connect entities from a large set with only a few other entities, while attributes have properties from a discrete set of entries (e.g. gender has two possible values) or a continuous set of values. Hence, entities and attributes should then not be represented the same way. In the MSA context, we need to use the attributes of our entities such as position or speed to infer new relations. Since this type of networks is more adequated to our needs, we will in this section describe fewer approaches but with more depth.

KR-EAR

Knowledge Representation Learning with Entities, Attributes and Relations (KR-EAR) [START_REF] Lin | Knowledge Representation Learning with Entities[END_REF] is one of the first models do explicitly distinguish the relations and attributes of a KG (Figure 4.4). Attributes are the main source of one-to-many and many-to-one relations. For instance, the property Male of the attribute Gender is related to millions of human entities. According to [START_REF] Lin | Knowledge Representation Learning with Entities[END_REF], TransE [START_REF] Bordes | Translating Embeddings for Modeling Multi-relational Data[END_REF] and its extensions like TransH [START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF] and TransR [START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF]] "cannot sufficiently build translation between entities and their attribute properties".

In KR-EAR, both entities and relations are represented by low-dimensional vectors ρ e and α e . The embeddings are learnt by building translations between entities using relations, like a classic translational method (e.g., TransE), and by inferring attribute properties based on the embedding of the entity.

Problem formulation

The relations are still represented in the shape of SPO triplets (s, r, o): the novelty comes from the attributional triplets p A . The objective is to learn embeddings X = (ρ e , ρ r , α e ) of entities, relations and attributes to predict relations between entities and attributes of entities. The objective function is defined by maximizing the joint probability of relational and attributional triples given the embeddings X, i.e. P(p R , p A |X). Both types of triplets are assumed to be conditionally independent, i.e. the relations are predicted without the attributes and vice versa:

P(KG R , KG A |X) = P(KG R |X)P(KG A |X) = (s,r,o)∈KG R P((s, r, o)|X) (e,a,v)∈KG A P((e, a, v)|X)
where P((s, r, o)|X) denotes the conditional probability of relational triples and P((e, a, v)|X) the conditional probability of the attributional ones. Hence, there are two components in KR-EAR: the Relational Triple Encoder and the Attributional Triple Encoder.

Relational Triplet Encoder

The goal of the Relational Triplet Encoder is to capture correlations between entities and relations. Usually, we optimize P(s|r, o, X),P(r |s, o, X) and P(o|s, p, X) instead of P(s, r, o|X). The encoding of a relational triplet is made using TransE and TransR.

P(s|r, o, X) = exp(g (s,r,o)) ŝ∈E exp(g ( ŝ,r,o))
where g is the energy function indicating the correlation between the relation and the two entities. With TransE, g (s, r, o) translates as:

g (s, r, o) = -ρ s + ρ r -ρ o L1/L2 + b 1
where b 1 is a bias constant.

Attributional Triplet Encoder

Intuitively, a classification model should be used to capture correlations between entities and their attributes. Therefore, the conditional probability P(v|e, a, X) for each triplet (e, a, v) is considered and described as follows:

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

where h is the scoring function that computes the semantic similarity between the embedding of the entity in the attribute space and the embedding of the attribute value:

h(e, a, v) = -f (ρ e W a + b a ) -α av L1/L2 + b 2
where f () is a non-linear function such as tanh, α av is the embedding of attribute value v and b 2 is a bias constant.

KR-EAR improves the results of TransE/H/R by using the attributes, but can only do so with discrete values. It can predict an entity, a relation type or an attribute value out of an incomplete triplet.

MT-KGNN

In Multi-Task Neural Network for Non-discrete Attribute Prediction in Knowledge Graphs (MT-KGNN) [START_REF] Tay | Multi-Task Neural Network for Non-discrete Attribute Prediction in Knowledge Graphs[END_REF], the authors observe that many relational learning models do not consider attributes despite their efficiency to alleviate the sparsity of KGs. This is because dealing with non-discrete data types is difficult due to the binary nature of knowledge graphs. That model trains a neural network for triplet prediction along with a separate network for attribute value regression (Figure 4.5). The objective is to improve relational learning and enable prediction of non-discrete attributes.

Motivation

Non-discrete attributes such as the price of a product are often present in knowledge graphs. They:

• help in relational learning: missing data, such as gender, could be retrieved using, for instance, the height attribute. More, attributes can characterize entities: the products phone and car could be distinguished using their height.

• can be predicted and thus complete missing values in the KG,

• represent 33% of the triplets (in Easy Freebase),

• are difficult to handle because they are not binary truths, common to knowledge graphs. More, the feature vectors of attributes can be extremely sparse and casting attributes as entities causes the size of the KG to blow up.

Problem formulation

The main objective is to produce a score that denotes the probability or strength of a fact or triplet:

h(s, r, o) ∈ [0, 1]
This can be seen as a simple binary classification problem in which a sigmoid or 2-class softmax layer can be used. The attributes triplets are defined as e, a, v as before, but this time v is a normalized continuous value ∈ [0, 1]. The range of each attribute is deduced from the training data and any new value below or above min-max will be casted to 0 or 1. During training, the objective is to maximize the score of positive triplets.

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Multi-task Knowledge Graph Neural Network

There are two networks in the model: the Relational Network (RelNet) and the Attribute Network (AttrNet).

Relational Network (RelNet) The inputs of the RelNet are [ρ s , ρ r , ρ o , t ] with:

• ρ s , ρ r , ρ o ∈ R n
• t the target of classification, either 0 or 1.

RelNet is a simple concatenation of the triplet through a nonlinear transform and finally a linear transform with sigmoid activation.

g r (s, r, o) = σ(w ⊺ d f (W ⊺ d [ρ s ; ρ o ; ρ r ]) + b r )
where f is t anh, σ is the sigmoid function and b r is a scalar bias. w d ∈ R h×1 and W d ∈ R 3n×h are parameters of the network.

The function to minimize is a cross-entropy loss:

L r el = -N i =1 t i l og (g r (p R i )) + (1 -t i )l og (1 -g r el (p R i ))
where ρ R i denotes triplet i in batch of size N and t i a value of 0, 1. Cross-entropy is common for non-continuous targets and commonly used in binary classification problems. At this point, RelNet is equivalent to the ER-MLP model [START_REF] Dong | Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion[END_REF]] and performs triplet classification (i.e., tells if a given triplet is true or false).

Attribute Network (AttrNet) The inputs of the AttrNet are

[α s , v s , α o , v o ] with: • α s , α o ∈ R n • v s , v o ∈ [0, 1]
A single layer network is trained by concatenating the embeddings of the attribute and entity to predict the continuous value (∈ [0, 1]). The input includes the attributes of the subject and of the object entities. Moreover, the network takes into account the positon of an entity as subject or object. Hence, AttrNet will optimize a joint loss function for both regression tasks. The score function is thus defined as follows:

g s (a s ) = σ(w ⊺ s f (B ⊺ [α s ; ρ s ]) + b z 1 ) (4.1) g o (a o ) = σ(w ⊺ o f (C ⊺ [α o ; ρe o ]) + b z 2 ) (4.2)
where w s , w o ∈ R h a and B, C ∈ R 2n×h a are parameters of AttrNet. h a is the size of the hidden layer and b z 1 , b z 2 ∈ R are scalar biases. The final output of each side of the AttrNet is a scalar value, as for RelNet. As this is a regression problem, the mean squared error (MSE) is used:

MSE(x, x * ) = 1 N N i =1 (x i -x * i ) 2 L at t r = L sub j ec t + L ob j ec t L head = MSE(g s (a s ), (a s ) * ) L t ai l = MSE(g o ((a o ), (a o ) * )
where (a s ) * , (a o ) * are ground truth labels. AttrNet can thus infer missing attribute values.

Other techniques

attri2vec [START_REF] Zhang | Attributed network embedding via subspace discovery[END_REF] extends the DeepWalk model [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF] (close to node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF]) to capture both network structure and node content features. Co-embedding Attributed Networks (CAN) [START_REF] Meng | Co-Embedding Attributed Networks[END_REF] embeds each node and attribute with the mean and variance of a Gaussian distribution using a variational autoencoder.

Conclusion

KR-EAR and MT-KGNN are two frameworks that extend existing relational techniques by dealing with attributes. The first one cannot handle non-discrete value, while the second can handle non-discrete data types and perform triplet classification instead of link prediction (but the two are close). But it is not clear that the latter can handle discrete data types. The common feature is the separation of the entity and attribute models.

Dynamic graphs

In a dynamic setting, each node is represented by a time series of vectors modelling its evolution. With the rise of tempral datasets (such as GDELT [START_REF] Leetaru | GDELT: Global Data on Events, Location and Tone[END_REF] and ICEWS [START_REF] Boschee | ICEWS Coded Event Data[END_REF], this topic is emerging and has fewer contributions than static graphs, but advances have already been made. The models of KGs are now dynamic and become DKGs.

Predicting the Co-Evolution of Event and Knowledge Graphs

This temporal model is proposed by [START_REF] Esteban | Predicting the Co-Evolution of Event and Knowledge Graphs[END_REF] and deals with the graph at the event level, i.e. what happens to entities over time. The authors model the DKG with two tensors: the tensor representing the DKG itself and an event tensor. They assume that changes . in a DKG arrive in the form of events, and that for a given timestep, events can be described by a very sparse event triple graph. The events contain facts that change the DKG, e.g. from True to False and vice versa (Figure 4.6). The triples in the KG that do not appear in the event graph are assumed to remain unchanged. Then, a separate prediction model is trained using the latent representations of both the previous events and the involved entities in the DKG.

Know-Evolve: Deep Temporal Reasoning for Temporal Knowledge Graphs

This model was presented by Trivedi et al. [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF] during the 34 st International Conference on Machine Learning. It will be our main inspiration for a streaming, dynamic relational model.

The concept

The authors use a temporal point process framework for temporal reasoning over dynamically evolving knowledge graphs; this process models the occurrence of a fact. They propose a novel deep learning architecture that evolves over time based on the availability of new facts. The dynamically evolving network ingests the incoming new facts, learn from them and updates the embeddings of involved entities based on their recent relationships and temporal behavior. Their model can predict the occurrence of a fact, but also the time when a fact may potentially occur. It supports the Open World Assumption and can predict over unseen entities. The main purpose is to predict new relations.

The evolutionary knowledge network has three components:

• A temporal point process that models the occurrence of a fact,

• A bilinear relationship score that captures relational interactions between entities and modulates the intensity function of the point process,

• A deep recurrent network that learns non-linearly and mutually evolving latent representations of entities based on their interactions with other entities in the multirelational space over time.

Temporal Point Process

A temporal point process [START_REF] Cox | Multivariate point processes[END_REF]] is a random process whose realization consists of a list of events localized in time, {t i }, with t i ∈ R + . It is characterized via the conditional intensity function λ(t ). Formally, λ(t )d t is the conditional probability of observing an event in a small window [t , t + d t ) given the history τ(t

) := {t k |t k < t }.
In this paper, the functional form of the intensity λ(t ) is a Rayleigh Process, which is well adapted when event likelihood drops rapidly after rising to a peak. Its intensity function is λ(t ) = α.(t ) where α > 0 is the weight parameter and the log survival function is l og

S(t |α) = -α.(t ) 2 2
. The log survival function gives the probability that the event of interest has not occurred by duration t.

Evolutionary Knowledge Network

In Know-Evolve, time is modeled as a random variable and the temporal point process models the occurrence of a fact. It uses a bilinear score function and dynamically evolves the embeddings of the entities, and then computes the conditional intensity function of the temporal point process. Figure 4.7 illustrates the network.

• Conditional intensity function:

λ s,o r (t | t ) = exp(g s,o r ( t )) * (t -t )
where t > t is the time of the current event and t = max(t e s -, t e o -) is the most recent time point where the subject or object entity was involved in an event before t ,

• g s,o r = ρ t -⊺ s . R r .ρ t -
o is the relational compatibility score between the involved entities in that specific relationship, with R r ∈ R n×n the relationship weight matrix and t -the time point just before time t .

The embeddings are updated using a recurrent neural network (RNN), with different parameters W s and W o depending on the status of the updated entity: subject or object.

Subject embeddings

ρ s (t a ) = σ(w s t (t a -t a-1 ) + W hh . h s (t a -)) h s (t a -) = σ(W h . [ρ t a-1 s ⊕ ρ t a - o ⊕ r a-1 s ])
Object embeddings

ρ o (t b ) = σ(w o t (t b -t b-1 ) + W hh . h e o (t b -)) h o (t b -) = σ(W h . [ρ t b-1 o ⊕ ρ t b-1 s ⊕ r t b-1 o ])
CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF]]. Here t ", t ′ and t may or may not be consecutive.

Training procedure

After applying the conditional intensity function on both scores, they maximize the probability of these events using the joint negative log likelihood of the intensity function [START_REF] Daley | An Introduction to the Theory of Point Processes: Volume II: General Theory and Structure. Probability and Its Applications, An Introduction to the Theory of Point Processes[END_REF], defined for a batch of events of size N as:

L = - N i =1 l og (λ s i ,o i r i (t ′ |t )) + S (4.3)
This loss function maximizes the probability of happened events, but nothing prevents it to maximize all events. To counterbalance the positive examples, negatives ones must be included. The naive method is to compute the conditional probability of all non-happened events in a given time window around the happened event, but this would be computationally intractable because of the complexity in O(|E| 2 |R|).

S = |R| r =1 |E| s=1 |E| o=1 T 0 λ s,o r (τ|τ)d τ
To reduce the complexity, the authors only sample negative examples from the entities of the current batch. It is thus based on the Closed World Assumption, since all events outside of the current batch are considered to be false. Know-Evolve performs well on link and time prediction tasks.

CTDNE

Continuous-Time Dynamic Network Embeddings [START_REF] Nguyen | Continuous-Time Dynamic Network Embeddings[END_REF]] is an embedding method on dynamic, homogeneous graphs using temporal random walks in continuous time. The temporal random walk N t v of a node v at time t in the triplet p R = (e x , e y , t ) is defined as1 :

N t v = {(e z , t ′ |q R = (e y , e z , t ′ ) ∈ DKG R ∧ t ′ > t }
Here in this case, DKG R is the special case where |R| = 1 (homogeneous graph). The selection of the neighbors can be unbiased (equal probabilities), or with a linear (closer in time) or exponential (decaying probability of consecutive contact) bias.

After the creation of a set of temporal random walks of a given length, the Skip-Gram architecture is used to generate embeddings as in [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF] and is generalized to continuous-time dynamic networks. Given a temporal walk S t , the optimization problem for the learning of the embeddings is:

max f l og Pr (W T = {e i -ω , . . . , i +ω }|ρ e i )
where ω is the context window size and W T ⊆ S t is an arbitrary context window. Conditional independence is assumed between the nodes of W T , that is:

Pr (W T |ρ e i ) = e i +k ∈W T Pr (e i +k |ρ e i )
Learning is done through stochastic gradient descent, and several hyperparameters need to be tuned: walk length, size and number of context windows, sampling strategy. The learned embeddings can then be used for downstream machine learning task, and improves the results of static random walks methods on link prediction in temporal datasets such as Enron [START_REF] Klimt | The Enron Corpus: A New Dataset for Email Classification Research[END_REF].

Other models

Although we described the main methods, other models have been tried to deal with dynamic graphs. DyRep [START_REF] Trivedi | DyRep: Learning Representations over Dynamic Graphs[END_REF] deals separately with the topological evolution of the graph and the activities between the nodes and then aggregates the two scales. It also define a temporal attention mechanism. Streaming Graph Neural Network [START_REF] Ma | Streaming Graph Neural Networks[END_REF] updates the node representations using LSTMs and propagates the new events to neighbor nodes on homogeneous graphs. DynamicTriad [START_REF] Zhou | Dynamic Network Embedding by Modeling Triadic Closure Process[END_REF] is based on triads which are groups of three vertices. It tries to close a triad by finding the third vertice to connect to a group of two in a weighted homogeneous sliced DKG. Sequence encoder [START_REF] García-Durán | Learning Sequence Encoders for Temporal Knowledge Graph Completion[END_REF] uses LSTMs to learn the sequences and represents time using year, month, day tokens. A more complete survey on relational representation learning on dynamic graphs can be found in [START_REF] Kazemi | Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey[END_REF] and [START_REF] Divakaran | Temporal Link Prediction: A Survey[END_REF].

Conclusion

Although these models are time-aware, they do not include attribute information in the prediction task, and most of them use snapshots of graphs that are not suitable to process streaming sequences. They form a solid basis to learn on DKG, but to deal with the situational awareness constraints on maritime situations requires the dynamic learning of attributes. We thus aim at add a dynamic attribute model to the dynamic relational one.

Dynamic attributed graphs

So far we reviewed techniques that deal with static relational and attributed graphs as well as dynamic relational graphs. However, the dynamic attributed graphs seem the most suited techniques to use graphs for MSA. This field is relatively new and only a few models exist.

DANE

DANE [START_REF] Li | Attributed Network Embedding for Learning in a Dynamic Environment[END_REF] is an embedding technique that uses both the network structure (relational) and node attributes. Their hypothesis is that the available information on attributes can mitigate the network sparsity and help find better embeddings, since sparse graphs provide less proximity information. DANE first performs spectral embedding separately on both the network structure and the node attributes (Figure 4.9).

To learn from the structure, the adjacency matrix A (t ) ∈ R n×n is used at time t to optimize the following loss function:

1 2 i , j A (t ) (i , j ) y i -y j 2 2
where y i , y j ∈ R n are the embeddings of the nodes i and j connected by edge (i , j ). It should be noted that DANE works with undirected, unlabeled edges (homogeneous graph). This objective function boils down to the following eigen-problem:

L (t ) A a = λD (t ) A a
where L (t ) A is the Laplacian matrix of A (t ) and D (t ) A its diagonal matrix. Let ρ 1 , ρ 2 , . . . , ρ n be the eigenvectors of the corresponding eigenvalues

0 = λ 1 ≤ λ 2 ≤ • • • ≤ λ n , then the k- dimensional embedding Y (t )
A ∈ R n×k of the network structure is given by the top-k eigenvectors starting from ρ 2 , i.e.

Y (t ) A = [ρ 2 , . . . , k , ρ k+1 ].
The same thing is done with the feature matrix of attributes X. Additionally, they normalize the attributes of each node to obtain the cosine similarity matrix W (t ) . Thus, they obtain the top-k eigenvectors Y (t ) X = [α 2 , . . . , α k+1 ] of the generalized eigen-problem corresponding to W (t ) .

The two embeddings Y X and Y A are then fused into a consensus embedding by maximizing their correlation. After this initial step of offline learning, the embeddings are then continuously updated via the matrix perturbation theory. An online update system is required since computation from scratch is very expensive. To do so, a modification in the network structure or node attributes is reflected in the associated matrices, and the embeddings are updated in an online fashion. The timescale in the experiments goes from 10 to 16 timesteps. This setting seems to indicate computations with a sliced DKG, but the authors do not say if the complexity may allow for a lot more timesteps as in a streaming DKG setting. [START_REF] Li | Attributed Network Embedding for Learning in a Dynamic Environment[END_REF].The first is the offline phase that leverages the adjacency matrix A for network structure and the features of nodes represented by the matrix X to generate embeddings. Then, the online phase updates the embeddings according to changes in the matrices.

CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

CDAN

The Co-embedding model for Dynamic Attributed Networks (CDAN) [START_REF] Meng | Jointly Learning Representations of Nodes and Attributes for Attributed Networks[END_REF] is similar to DANE in the way it deals with relations and attributes. It also uses an adjacency matrix for relations and a feature matrix for attributes. However, the matrix perturbation order is of several orders, while DANE only uses first order perturbation. Moreover, CDAN is more neural network oriented, while DANE uses Laplacians and eigenvalues. The first order perturbation for node i and attribute a between time t and (t -1) is defined by:

∆ 1 Fn (t ) i = t anh(Wn 1 • (Fn (t ) i -Fn (t -1) i )) ∆ 1 Fa (t ) a = t anh(Wa 1 • (Fa (t ) a -Fa (t -1) i ))
where Wn 1 ∈ R (|E|+|A|)×H p and Wa 1 ∈ R N×H p are weight matrices with H p < |E|, H p < |A| being the dimension of the perturbation features, and Fn (t ) i , Fa (t ) a the features of node i and attribute a at time t . The k-th order perturbation is then obtained by learning the aggregation of the lower order perturbations from its neighborhood, using the mean aggregation function.

These perturbations are then fed to a Dynamic Variational Autoencoder that outputs Gaussian embeddings for all nodes and attributes of the network. Figure 4.10 illustrates the global architecture of CDAN.

In CDAN settings, the attributes are dynamic but can be considered as entities (discrete). For instance, in the DBLP dataset, they use the conferences and the key terms as attributes. As for time, the method seems suited for a sequence of graph snapshots G t and its capacity to deal with continuous time is unclear. The method is tested for node classification and link prediction and only works on homogeneous networks. [START_REF] Li | Streaming Link Prediction on Dynamic Attributed Networks[END_REF] propose a streaming model (SLIDE) on dynamic attributed networks, using a sketching matrix that summarizes the currently observed links and node attributes. When a change occurs in the network, the sketching matrix is updated to include the changes in the network representation. This update is performed using the frequent directions algorithm, which is able to operate in a streaming fashion and makes only one pass of the data. To feed the dynamic attributed network to this algorithm, it must first be converted to a feature representation based on the observed links. For each edge in the graph, and when a new edge is created or an attribute value has changed, a feature vector is added to the matrix as a new [START_REF] Li | Streaming Link Prediction on Dynamic Attributed Networks[END_REF] column in the data stream. But this matrix is still too large to be held in memory, hence the sketching matrix to represent the stream of data. With the updated sketching matrix, missing links can be inferred. If the features of the candidate link y ∈ R 2d , with d the size of the node features, is close to the space composed of the columns of the matrix U t , this link is most likely existing. The residual error of the reconstruction is I -U t (U t ) ⊺ y 2 2 . To know if the link exists, the residual error must be below a threshold automatically obtained from the data stream by picking the largest error among the columns in the stream (of existing links). The global architecture of SLIDE is presented in Figure 4.11. SLIDE works with cold start nodes, i.e. new nodes that have not been seen before, since it leverages the attributes of the node to perform a prediction and not only its history. It is efficient for link prediction in a streaming fashion. However, it only applies to homogeneous graphs and to discrete attribute features. The performed experiments were made on a restricted number of timesteps (~20), which suggests a discrete time setting, but the streaming capabilities of the framework should make it work in continuous time with much more timesteps. In their conclusion, the authors observe that the structure of the network is more important than features to predict new links, but features do help in the prediction.

SLIDE

Conclusion

The three reviewed techniques are matrix based and have the advantage to work in a streaming fashion. They deal with both relations and attributes in a dynamic setting by summarizing the network features. However, they only deal with homogeneous graphs and the choice of attributes is discrete. We are looking for a model for heterogeneous graphs that can handle continuous attributes (positions, speeds...). Our research line is reinforced by the survey on dynamic graphs by [START_REF] Kazemi | Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey[END_REF], that indicates that "while some initial steps have been taken to extend [existing encoders] to other types of graphs, the best way of extending these approaches to the case of attributed graphs and knowledge graphs (KGs) is still not clear."

Addition of semantic information

This section presents briefly some additional ways to include or extract knowledge in/from graphs based on semantic information. More details can be found in the survey by [START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF].

Entity types (in embeddings)

When working with nodes only, the class of the node is generally not known by the embedding model. Including this information may help to guide the learning phase, since knowing what the nodes are makes the prediction of links between them easier (e.g. a vessel is more likely to enter a port than a parking lot).

A straightforward method to model such information, as investigated in [START_REF] Nickel | Factorizing YAGO: scalable machine learning for linked data[END_REF], is to take :isA as an ordinary relation and the corresponding triples as ordinary training examples. Guo et al. [START_REF] Guo | SSE: Semantically Smooth Embedding for Knowledge Graphs[END_REF] proposed semantically smooth embedding (SSE), which requires entities of the same type to stay close to each other in the embedding space. SSE employs two manifold learning algorithms, i.e., Laplacian eigenmaps [START_REF] Belkin | Laplacian eigenmaps and spectral techniques for embedding and clustering[END_REF] and locally linear embeddings [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] to model this smoothness assumption.

Xie et al. [START_REF] Xie | Representation Learning of Knowledge Graphs with Entity Descriptions[END_REF] devised type-embodied knowledge representation learning (TKRL), which can handle hierarchical entity categories and multiple category labels. It achieves good performance in downstream tasks such as link prediction and triple classification, but at the cost of a high space complexity.

Logical rules

Logical rules can represent expert knowledge, and thus give a priori information on the graph. They make the learning easier by automatically extracting the known patterns. For instance, first-order Horn clauses such as ∀x, y : HasWi f e(x, y) ⇒ HasSpouse(x, y), state obvious knowledge like the fact that two entities linked by the relation HasWife should also be linked by the relation HasSpouse.

To do so, Markov logic networks [START_REF] Richardson | Markov logic networks[END_REF], [START_REF] Kimmig | A Short Introduction to Probabilistic Soft Logic[END_REF], [START_REF] Pujara | Using Semantics and Statistics to Turn Data into Knowledge[END_REF]] can be used. There are also systems such as AMIE [START_REF] Galárraga | AMIE: association rule mining under incomplete evidence in ontological knowledge bases[END_REF], [START_REF] Galárraga | Fast rule mining in ontological knowledge bases with AMIE $$+$$ +[END_REF] which can extract logical rules automatically from KGs to apply them later. Wang et al. [START_REF] Wang | Knowledge Base Completion Using Embeddings and Rules[END_REF] uses rules to refine embedding models during KG completion. Guo et al. [START_REF] Guo | Jointly Embedding Knowledge Graphs and Logical Rules[END_REF] embed KG facts and logical rules simultaneously. RUGE [START_REF] Guo | Knowledge Graph Embedding with Iterative Guidance from Soft Rules[END_REF] learns embeddings from observed labeled triplets, unlabeled triplets whose labels are going to be predicted iteratively, and soft rules extracted from the KG that guide the learning.

Conclusion

We reviewed the main models used for static (attributed), dynamic (attributed) graphs. While static graphs are obviously out of scope for the problem at hand (MSA), they lay the basis and give some insight on how to create meaningful graph representations. If a few techniques exist for dynamic attributed graphs, they are not completely adequated to our needs since they deal only with homogeneous graphs. Still, we can get inspired by these on the inclusion of attributes in a dynamic setting and to work in a streaming fashion. Our main objective is thus to create an embedding model working on heterogeneous dynamic attributed graphs, ideally in a streaming fashion, to maintain up-to-date the current state of knowledge about a situation and make prediction on future possible links to raise automated alerts on what could happen.

Part II

Contributions

CHAPTER 5

Problem statement for MSA

In this chapter, we first formalize the link prediction problem in heterogeneous dynamic attributed knowledge graphs, and then present the global architecture of our model, Joint Evolution. Chapter 6 describes the model in detail.

Problem statement

In this section, we formalize the concepts used to model Dynamic Attributed Knowledge Graphs, and the associated link prediction problem.

Prediction Problems with Knowledge Graphs

Motivated by our application to situation monitoring, we tacitly assume that the relations between entities and attribute values of entities at some timestep t , can be predicted using only the past relations and attribute values, that is, using those quadruplets with a timestamp τ < t .1 Moreover, because our application scenarios involve very long periods of surveillance with rapidly changing attributes and relations, we cannot afford storing all observations in memory. Hence, we focus on a constant-size representation per entity, namely, its attributive and relational embeddings. At each timestep t and for each entity e, we have an attributive embedding α τ e (where τ ≤ t denotes the last timestep when the attributive embedding of e was updated) and a relational embedding ρ τ ′ e (where we have τ ′ ≤ t , and in general τ = τ ′ ).

The problems of interest are thus the following:

• given an attributive quadruple q = (e, a, v, t ) observed at time t (called an attributive event) and the previous embedding • at any timestep t , predict the value of a given attribute a for a given entity e at some given, present or future timestep t ′ ≥ t , that is, the value v ∈ D a such that the quadruple q = (e, a, v, t ′ ) is most likely to be in DKG A ;

• similarly, at any timestep t , given two out of s, r, o and some timestep t ′ ≥ t , predict the most likely value(s) for the third one (for instance, given s, o, t ′ , predict the relation(s) r such that q = (s, r, o, t ′ ) is most likely to be in DKG R .

Observe that we restrict our attention to predictions at given timesteps, that is, we want to be able to predict what will occur at a given timestep, but do not address the prediction of when a given event will occur. This is left for future work, but that restriction is also motivated by the fact that surveillance typically requires to predict what will happen at the next timesteps (e.g., suspicious or dangerous events). To this end, we will predict the most probable object for a quadruple q = (s, r, ?, t ) to answer questions such as "in which port will this vessel enter next?" or "which social network community will this person join?". This is also valid for subject and relation prediction, as in "which vessel will tug this upcoming vessel?" and "how will these two vessels interact?", i.e. (?, r, o, t ) and (s, ?, o, t ). These operations constitute the inference phase, that is, the production phase when the system is used for online situation assessment. Thus, we are interested in predicting the missing relations between entities and values of attributes in knowledge graphs. Recall our assumption that for some timestep, they can be predicted from the values of a subset of the relations and attributes at previous timesteps. We thus make the two following assumptions: Assumption 5.1.1 (determined relation). Let DKG = 〈E, R, A, D〉 be a frame be a dynamic knowledge graph. We assume that the relation r * is determined by DKG in the sense that for all timesteps t * , function f : DKG → 2 E×E provides the next relational event with

{(e s , e o ) | (e s , r * , e o , t * ) ∈ DKG R } = f (DKG <t * )
where DKG <t * denotes the restriction of DKG to those quadruplets with a relation with a timestamp less than t * . Note that DKG <t * means that we use both relations and attributes.

Assumption 5.1.2 (determined attribute). Let DKG A = 〈E, A, D〉 be an attributive dynamic knowledge graph. We assume that the attribute a * is determined by DKG A in the sense that for all timesteps t * , the function g : DKG A → 2 E×D provides the next attributive event for

DKG A with {(e, v) | (e, a * , v, t * ) ∈ DKG A } = g (DKG A,<t * )
where DKG A,<t * denotes the restriction of DKG to those quadruplets with an attribute in A and with a timestamp less that t * .

With this in hand, the learning problem which we tackle consists, for a given knowledge graph DKG * (unknown to the learner), and given all the information up to timestep t * together with some information at timestep t * , of inducing a given target relation r * at time t * . This is also valid for a given target attribute a * , value v * , subject s * or object o * . CHAPTER 5. PROBLEM STATEMENT FOR MSA

The ideal graph model for maritime applications

After defining formally the settings of our graph, we apply it to the maritime usecase. "Realworld" datasets often have more constraints than the academic ones because of their specificities. Maritime datasets are no exception and the following challenges, presented in more details in Section 2.1, must be overcome: evolution of attributes, event and threat detection, streaming data, uncertainty of data and their sources, explainability of the decision. To answer this, we propose the graph structure illustrated in Figure 5.1 (best viewed in color). Events in red represent DKG A and the other events DKG R . Ship A and Ship B are vessels from different countries, moving in the Mediterranean Sea. They have a static attribute (vessel type) setting them as cargos and dynamic attributes (latitude and longitude) revealing their positions. Before t * , the two vessels were moving in the Mediterranean Sea and had different positions, but now (at t * ) they have stopped and are close to each other. A possible link prediction from DKG <t * is that the two vessels are performing transhipping. Note that the :stoppedIn relation can be deduced from the speed attribute going to zero, not represented here for the sake of clarity. If relations such as CountryA having a shore on the Mediterranean Sea are 100% sure, some are more uncertain: the position of Ship B is only 89% sure because the signal was picked up by a satellite in an area with high ship density. Moreover, the uncertainty of predicted relations (:transhipping) depends on the uncertainty of the root events. Finally, to predict the transhipping action in time, the model must be updated with the root causes as soon as they are available, hence the need for streaming link prediction. Ideally, the model will have to handle both discrete (port of call, flag...) and continuous data (position, time, wind speed...).

A first restricted model

We will work on a restricted version of the DKG presented in Figure 5.1, because several components are research leads on their own to explore. Using a time interval for edges boils down to consider not only the edge addition problem, but also the edge deletion one since an edge with a duration becomes invalid as soon as the current timestamp is not in the time interval. At the time of [START_REF] Kazemi | Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey[END_REF] survey publication, there is no significant work towards the edge deletion task for DKG.

Dealing with the uncertainty of the data or its sources is also a problem on its own. Although some work already exists on this topic [START_REF] Chekol | Uncertain Temporal Knowledge Graphs[END_REF], Chekol et al., 2017, Hajiramezanali et al., 2019], it makes the problem more complex and will be CHAPTER 5. PROBLEM STATEMENT FOR MSA considered in future work. At last, explainability is also left for future work, for which surveys like [START_REF] Adadi | Peeking inside the blackbox: A survey on explainable artificial intelligence (xai)[END_REF]] can be a good starting point.

A two-headed model

We introduce JointEvolution, a double encoder-decoder system. The global architecture is presented in Figure 5.2 and will be detailed in this section. Note that this is an overview of the model, the full extent of the mechanics of JointEvolution being developed in Chapter 6.

An encoder-decoder system

As stated before, the goal of JointEvolution is to create projections of the entities in an embedding space and make prediction on future links or attribute values from them. The sequence of events, used as input, is processed by an encoder. Each time an entity is met within a quadruplet, a one-hot vector projects it to its embedding space. A one-hot vector is a vector filled with zeroes and ones, where the ones are the index we want to select (each entity is mapped to a unique index). This vector is multiplied by the embedding matrix to access the embedding of the desired entity i.e. the line of the matrix whose index in the one-hot vector has a value of one. The obtained feature vector is then aggregated with the other components of the quadruplet within the encoder and a new, up-to-date embedding is produced.

This new embedding serves two purposes: maintaining the current state of knowledge as complete as possible by including each event received about an entity in its representation, and making hypotheses on what could happen next using the decoder. Since one system is dedicated to DKG A (AttrNet) and the other to DKG R (RelNet), we will now detail the specifics of each encoder and decoder.

AttrNet

The input of AttrNet is a sequence of attributive quadruplets q A ∈ DKG A . The goal of the network is to learn the behavior of the attributes, so the objective function is set to predict in an accurate manner the next value of the attribute type a given as input. For instance, for the input q A = (e 4 , a 1 , 42.654, t 1 ), AttrNet will try to predict q ′A = (e 4 , a 1 , 43.294, t 3 ) using α t 1 e 4 with a 1 the latitude of the vessel e 4 .

To do so, we first include the value of the input q A = (e, a, v, t ) in α t - e using the encoder. This new embedding is processed through the decoder, that outputs a scalar value: the prediction for the next value. This process learns representations able to predict the next values for attributes.

RelNet

For RelNet, we use an encoder structure similar to AttrNet, but with a version for the subject and another slightly different for the object. This is done to consider the position of the entity in the quadruplet during the learning. Indeed, the effect of an event on an entity is not the same whether it is the subject or the object: while some relations are symmetric (e.g. an exchange of goods), others like "entering a place" will most often involve a vessel as its subject and a port or an area as its object. Moreover, learning the right position in the CHAPTER 5. PROBLEM STATEMENT FOR MSA quadruplet is essential for prediction since the candidate entities are different whether we try to predict a subject or an object. The position of an entity is thus an important feature that must be considered. To be used as input, an event is represented by the concatenation of s, r and o embeddings (from q R ), and is given to the encoder to update ρ t - s and ρ t - o . After the update of the embeddings, we compute the compatibility of the entities for a relation type. Here, the representation of an entity e is the concatenation of ρ t e and α t e . The knowledge acquired by AttrNet will then help RelNet to make predictions on future relational edges. Indeed, as stated in Assumption 5.1.1, the attributive behavior of an entity is an additional information that makes relational prediction more precise. For instance, the successive positions of a vessel give clues on its destination, or its speed is an indicator of its current activity (slow while transhipping, fast if under way...). Moreover, the attributive embedding may be the only source of information if no event including an entity happened. Static attributes are also an indicator if no attributive event has happened either. However, as stated in Assumption 5.1.2, we do not use relations to predict the next attribute: since those are mostly time series, we assume that adding the event may unnecessarily complexify the learning process. Of course, there are some cases where relational events may help to predict attributes: entering a port means that the speed is low, or tugging another vessel implies that the two vessels are close. These predictions are not in the scope of Joint Evolution and we focus on the relation prediction problem assisted by attributive knowledge.

Note that both networks work differently during the training and inference phases, about what more details are given in Section 5.2.3.

Input data

As stated before, we use DKG A and DKG R to train two encoder-decoder systems. The events are sorted by timestamp and we use challenges to guide the learning (challenges correspond to ground truths in classification). For an attributive quadruplet q A = (e i , a j , v x , t m ) ∈ DKG A , its challenge is the next change of value of the attribute type a j for entity e i in the training data, e.g. q ′A = (e i , a j , v y , t n ) with t m < t n and v x , v y ∈ D(a j ). The challenge of a relational quadruplet q R = (e i , r a , e j , t x ), i = j , is composed of two events: the next relational event for e i and the next relational event for e j (which can be the same if they are both involved in their respective challenges). This time, challenges are not dependent of the type of relation, so q ′R = ((e i , r b , e k , t y ), (e j , r c , e ℓ , t z )), with t x < t y and t y < t z . Note that e i and/or e j could also be object in their challenge. This way, we learn representation vectors that are tailored to predict the next event that will happen to an entity.

Training and inference

Joint Evolution behaves differently when in training phase or in inference phase. The training phase defines the model and its parameters. It is then used to update the embeddings when new data arrives. These updated embeddings are then used to make predictions (Figure 5.2).

During the training phase, the network is fed with both inputs and their challenges. At-trNet is trained to predict the next value of an attribute as close as possible to the challenge value. For RelNet, we try to increase the compatibility of the entities w.r.t. to the challenge events.

During the inference phase, we distinguish two usecases: streaming and prediction. During the streaming phase, only the encoder is used to update the embeddings with new events. Then, when a prediction is required, we can ask the model to answer the question (s, r, ?, t ) (or (s, ?, o, t ), or (?, r, o, t )), and it will output the most compatible entity. In a nutshell:

• We use two encoder-decoder systems: one for DKG A and one for DKG R ;

• Embeddings are used to predict attribute values and event scores;

• Both embeddings (ρ t e and α t e ) are used to predict new relations;

• The state of knowledge can be updated in a streaming fashion.

Preparing the data: challenges and sequence ordering

To learn accurate representations of the behavior of entities, not only must the data be ordered by timestamp, but also the events occurring at the same time for the same entity must be processed independently. Extracting independent sequences for multi-relational data is not a trivial task and requires some preparation. We will start with the challenging process, followed by the ordering in independent sequences.

Mixing up attributes and relations

One important thing is that AttrNet and RelNet must be trained simultaneously. If an attribute gets a new value between two relational events, this must be taken into account (Figure 5.3).

To do that, we need to put attributes and relations in the same sequence of events, even if their quadruplet structures and their encoders are different.

Assigning challenges

Our input data is the knowledge graph DKG. To make it easily readable, we write it as a sequence of quadruplets q R and q A . Each entity, each relation and attribute type is referenced by an integer, and attribute values are floating numbers. Thus, we have input data that looks like q R = (2, 1, 23, 1614626755) and q A = (2, 5, 36.283, 1614626235).

As previously mentioned, the challenge of an event is its direct successor in the timeline for the involved entity. It should be noted that even if a relational event happens between two attribute updates, it will not be used as the challenge of the first one: DKG A and DKG R are clearly separated here. This is straightforward for q A , but what about q R that includes two entities?

Challenges for DKG R

Events in DKG R involve two entities, s and o. Then, what should their challenges be? The next event including s would be a nice candidate since it is the main actor in the relation (if r is not symmetric), but this completely excludes the future of o. We thus choose to use two challenges per input, one for each entity. A sample of the input data will thus look like this: {"data": (s, r, o, t ), "challenges":{(s,r ′ , o ′ , t ′ ), (s ′′ , r ′′ , o, t ′′ )}, "type":"relation"} Note that s and o can be either subject or object in their respective challenges, and that r, r' and r" are not necessarily the same relation. We keep track of the type of the quadruplet to tell the difference between relation and attributes when both will be mixed in the event sequence. The challenge of s is the closest event in DKG R that involves s, with t < t ′ . It means that by construction, no relational event between t and t ′ happens.

Challenges for DKG A

Challenging the attributive graph is easier since only one entity is involved each time. Since we want to learn how an entity behaves, we need to learn how its attributes evolve. Thus, a straightforward way to do this is to learn the time series of each attribute type. For each quadruplet q A = (e, a, v, t ), we assign as challenge the next event in the timeline changing the value of a. A sample of the input data will thus look like this: {"data": (e, a, v, t ), "challenges":(e, a, v ′ , t ′ ), "type":"attribute"} with v, v ′ ∈ D(a) and t < t ′ with t ′ the smallest timestamp > t where e changed for value of a.

Precedence graph

We now have defined challenges for all our inputs, but we still do not know in which order to process them. This is important because events must be included in an embedding in the order in which they happen, and dependencies exist between events.

Our solution is to generate a precedence graph of events, where events are nodes and each directed edge adds a precedence constraint between two nodes, i.e., the target node cannot be processed until all its parents nodes are. This graph is illustrated in Figure 5.4.

The precedence graph is defined as follows:

Definition 12 (precedence graph). Let DKG be a set of attributive and relational quadruplets, and for each quadruplet q ∈ Q, write t q for the timestamp of q and ent (q) for the entities involved (i.e., ent (s, r, o, t ) = s, o and ent (e, a, v, t ) = e). We define G by: ∀v x , v y ∈ V, (v x , v y ) ∈ E if t x < t y and ent (v x ) ∩ ent (v y ) = ∅, and the precedence graph of the set of quadruplets to be the transitive reduction of G.2

The precedence graph generates a link between an event and its direct successor(s). There can be several successors if there are several candidate events with the same timestamp. The dependencies between the events can now be used to extract the events ready to be processed.

With the precedence graph, we can now know which events can be included in the input sequence while meeting the requirements on event ordering. We use a topological sort on the precedence graph to get each node which does not possess any parent node. When a node is taken for processing, the constraint it applies to its target node(s) is lifted and, if all their parents have been processed, they can now be chosen too.

In a nutshell:

• Attributes and relations must be present in the same stream of data;

• The challenge of an event is the closest one in the timeline with a common entity;

• Creating a precedence graph provides the available samples with a topologic sort;

CHAPTER 5. PROBLEM STATEMENT FOR MSA

Conclusion

We presented a formalization of the link prediction problem for MSA and a general architecture for a solution based on a double encoder-decoder system. In the next chapter, we will describe each part in more details and explain how we ended up making these choices.

CHAPTER 6

Joint Evolution, a network pair for link prediction on DAKG

The choice of recurrent networks

To learn on sequential data (dynamic knowledge graphs in our case), recurrent neural networks (RNNs) may prove useful. RNNs are made of non-linear units with recurrent connections and are able to learn features and long-term dependencies. Our model is inspired by [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF] which use RNNs, it is thus a natural choice for Joint Evolution. Besides, many recent models are using these networks to deal with DKGs [START_REF] Ma | Streaming Graph Neural Networks[END_REF], Dai et al., 2016, Goyal et al., 2018, Trivedi et al., 2019, Zhao et al., 2020, Hajiramezanali et al., 2019].

RNNs

Popularized by [Elman, 1990], RNNs are neural networks that can process sequences by having a "memory" of the previous computations. Figure 6.1 shows the structure of an RNN: the input is a sequence of vectors, and each vector is a timestep processed by a cell. The black square represents the recurrent step where the previous hidden state is used to compute the current one. Depending on the objective, the output may be taken for each element of the sequence (e.g. for translation) or only at the end of the sequence (e.g. for embeddings). RNNs are formaly defined as follows:

• Let X = x 0 ...x t ...x n be a sequence of size n ∈ N with t ∈ [0, n] the current timestep,

• Let U, V and W be weight matrices of the network,

• Let s t be the cell state at timestep t ,

• Let o t be the output of the cell at timestep t ,

• Let b h be the bias vector of the hidden units and b o the bias vector of the output layer,

• Let f be a non-linear activation function.

s t = f (Ux t + Ws t -1 + b h ) o t = so f t max(Vs t + b o )
Note that U, V and W are the same matrices throughout the recurrent process. Therefore, such a network can handle input sequences of different lengths because the number of weight matrices is not varying.

However, RNNs have a major drawback: during backpropagation, the gradient often vanishes and sometimes explodes [START_REF] Bengio | Learning long-term dependencies with gradient descent is difficult[END_REF], making the learning step harder. And because it fails to propagate the error through deep layers, long-term dependencies are overshadowed by short-term dependencies. The non-linear f function is often a t anh (Equation 6.1) or a ReLU (Equation 6.2) function. t anh is in the range [-1,1] and since only near-zero values are mapped to near-zero outputs, it solves the vanishing gradients problem to some extent. ReLU is more efficient regarding the vanishing gradients but is has no upper bound and is not differentiable at 0, nor zero-centered.

t anh(x) = (e xe -x )/(e x + e -x ) (6.1)

ReLU(x) = x + = max(0, x) (6.2)

LSTMs

Hochreiter and Schimdhuber [START_REF] Hochreiter | Long Short-Term Memory[END_REF] introduced in 1997 the Long Short-Term Memory (LSTM) model to cope with the vanishing gradient problem. The classic RNN cells are replaced by memory cells whose inputs and outputs are controlled by gates (input, output, reset). These gates manage the flow of information to preserve or erase the features and states of the previous steps. A chain with only a few linear interactions, the cell state, is introduced, allowing the information to travel along it unchanged if needed. The information within it is regulated by the gates.

The major drawback of LSTMs is the computational complexity in the hidden layers: a standard LSTM requires four times more parameters than a vanilla RNN [START_REF] Mikolov | Learning longer memory in recurrent neural networks[END_REF].

Gated Recurrent Units

To reduce the complexity of LSTMs, Cho et al. [Cho et al., 2014a] proposed the Gated Recurrent Units (GRUs). Like the LSTMs, GRUs have gating units that modulate the flow of information inside the unit, however without having separate memory cells [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF]. Figure 6.2 illustrates how a GRU cell works1 .

The gates

The input and block gate are replaced by a single update gate that determines how much of the past information needs to be passed along to the future:

z t = σ(W z x t + U z h t -1 + b z ) (6.3)
with W and U weight matrices, b z the bias, x t the input and h t -1 the previous hidden state.

The forget gate becomes a reset gate that decides how much of the past information to forget. It is written like the update gate but its weights and usage differ:

r t = σ(W r x t + U r h t -1 ) (6.4)
While LSTMs have a cell state and a hidden state, GRUs only keep the hidden state. To compute the current memory content, the previous hidden state is processed through the reset gate, then added to the input and squashed through a t anh activation function:

h ′ t = t anh(Wx t + r t ⊙ U t h t -1 )
(6.5) CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG with ⊙ the pointwise multiplication. Note that writing U t (r t ⊙t t -1 ) gives the same results as (r t ⊙ U t h t -1 ) [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF].

At last, the final memory at the current time stem processes the previous hidden step h t -1 and the current memory content through the update gate:

h t = z t ⊙ h t -1 + (1 -z t ) ⊙ h ′ t (6.6)
The higher the values of the update gate z t ∈ [0, 1], the more the previous hidden state h t -1 is kept and the current memory content h ′ t is forgotten (i.e. the more past information is passed along to the future).

Performances

If GRUs simplify the LSTM model, this does not mean that they are less efficient: [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF] show that both models perform better than the other only in certain tasks, which suggests that they can, on average, output a result of the same quality. Since it is not clear which one is better suited to our usecase, we chose the simplest model, namely, GRUs.

Other models

In [START_REF] Salehinejad | Recent Advances in Recurrent Neural Networks[END_REF], the authors make a list of major RNN architectures. Some recent models seem to be promising but require more research and comparative studies and are thus risky to use for our work. In the context of this thesis, we are looking for a recurrent model to use Know-Evolve [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF] and improve it. GRUs are the choice of simplicity and should perform better than the vanilla RNNs used in [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF].

In a nutshell:

• Recurrent neural networks are often used with DKGs;

• They are present in [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF], our base model;

• Gated Recurrent Units provide a good trade-off between complexity and performance.

Batch creation

Training a neural network requires to feed it with batches of data. A batch is a set of samples that is processed simultaneously through the network to speed up the learning process. Indeed, the backpropagation is thus done only every X samples (with X the size of the batch), which improves the error reduction and is faster than backpropagating for each sample. However, some constraints must be respected: to ensure that we process the events in the correct order and that two events about the same entity are not processed at the same time, an entity cannot be present two times in a batch. Such a situation would result in a loss of information since only one ρ t e would be kept for two updated ρ t - e . To create such batches, we could create a slice of the graph for each timestamp, but this would demand too many slices because of the update frequency of AIS. We could also create batches of samples sorted by timestamp and add a unicity constraint on the presence of an entity in the batch. But doing so would require storing in memory all unprocessed samples and do several passes over them until they are all consumed, which is a time-consuming task. Our solution is to use the precedence graph presented in Section 5.3.3. Using topological sort, we can extract a chosen number of independent samples. The only requirement is to set the maximum batch size, since they are created during the preprocessing step. This system introduces dynamicity in the batch size, because there are no guarantees that the same number of events will be without constraints each time. This generally means that there will be fewer and fewer constraint-free events as the graph is parsed, leading to a decreasing batch size over time. Figure 6.3 is a perfect example of this: this extract from the datAcron dataset (detailed in Section 7.1) has 364 entities, 764 relational quadruplets and more than 4M attributive quadruplets. Since there are not a lot of entities, they occur more frequently, resulting in more sequences shorter than the fixed maximum batch size. However, this is not the case when there are a lot of entities: our DBLP extract (Section 7.2) has 6.147 entities, 261,324 relational quadruplets and 139,152 attributive quadruplets. DBLP is a lot sparser than datAcron, resulting in a constant batch size since there are always enough unconstrained events to sample, excepted for the last batch (Figure 6.4). CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG

AttrNet

The objective of AttrNet is to capture the evolution of an entity's attributes. To do so, we build a recurrent neural network that learns the time series of the attributive events.

A first version

We started with an RNN version of AttrNet based on the Know-Evolve relational network.

Once adapted, the encoder-decoder structure of AttrNet is defined as:

α e (t p ) = σ(w t (t p -t p-1 ) + W emb a . α t p-1 e + w i n a . v + b i n a ) (6.7) v ′ (t p+1 ) = σ(w a . α t p e + b a )
(6.8) Equation 6.7 updates the attributive embedding of entity e (encoder) and Equation 6.8 predicts the value of the attribute a at time t p+1 (decoder). t p-1 is the last time entity e was involved in an event before the current event (at time t p ). (t pt p-1 ) is the temporal drift between the last and the new event, α t p-1 e ∈ R m is the last state of the dynamic attributive embedding, w t , w i n a ∈ R m and W emb a , w a ∈ R 1×m are weight parameters of the model, v is the value of the attribute and b i n a , b a ∈ R m are biases. w t captures variation in temporal drift and is shared across all attributes. w i n a is a weight matrix different for each a: it captures specifically how the values evolve for this attribute over all the entities, along with b i n a and b a which are also attribute related. w a considers which part of the embedding is required to predict the attribute value of type a. σ denotes the nonlinear activation function, that will be tanh here.

Once the prediction is made, the network must be trained and optimized to be as close as possible from the challenge value. An obvious objective function for this prediction task is Mean Squared Error:

Loss = 1 N N i =1 (v(t p+1 ) i -v(t p+1 ) * i ) 2 (6.9)
where v(t p+1 ) * i is the ground truth challenge, i.e. the value in the quadruplet given as challenge and N is the size of the batch. Figure 6.5 shows how the attribute network is trained. Given a new observed value at time t , the old embedding α t -1 e is updated using the network parameters W and the new value. With the freshly updated embedding α t e , the value v for time t + 1 is predicted and compared to the ground-truth value at time t +1. In Equations 6.7 and 6.8, W emb a and w t are the parameters that learn how to embed the new information and w i n a learns how to make a prediction value from this new embedding. Thus, the model is trained to update embeddings that can be used to predict next values, creating a representation of the entity behavior. Note that each W emb a is different for each a, the attribute type.

Room for improvement

The presented version of AttrNet is well suited for training but has a problem during the prediction phase: we can predict the next value of an attribute from the embedding of the entity at hand, but we have no input for the timestamp of the prediction. Thus, we must add CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG the temporal drift between the last attribute value change t p and the time of the prediction t p+1 (the drift in the encoder is between t p-1 and t p ).

v ′ (t p+1 ) = σ((t p+1 -t p )w t + w a • α t e + b a )
(6.10)

In Section 6.1, we discussed the advantages of GRsU over RNNs. The encoder was an RNN, so we switched it to a GRU (Equations 6.11 to 6.14). This solved the vanishing gradient problem that was occurring on long trainings and speeded up the learning (same loss reached in fewer epochs).

z t = σ((t p -t p-1 )w z t + v w a z + U z α t p-1 e + b z ) (6.11) r t = σ((t p -t p-1 )w r t + v w a r + U r α t p-1 e
) (6.12)

h ′ t = t anh(v w a t + r t ⊙ U t α t p-1 e
) (6.13)

α t e = z t ⊙ α t p-1 e + (1 -z t ) ⊙ h ′ t (6.14)
The last improvement is about the decoder. Predicting the next value directly from the embedding can be a tedious task for a single fully connected layer, especially if the dimension of the embedding is large. To add more expressivity to the model and improve the prediction, we add another hidden layer in the decoder, projecting the embedding to half its size before making the prediction (Equation 6.15). This layer improves the results on attribute value prediction.

hi d d en(α t e ) = t anh(w x α t p e + b x )) (6.15) v = σ((t p+1 -t p )w t + w a v • hi d d en(α t p e ) + b a )
(6.16)

Asynchronous GRUs

GRUs are usually used with long sequences, and only the output of these sequences is kept.

Inpuiting data in a GRU sample by sample is generally less efficient, because predictions are made only with a window of size one in the past (i.e. the last sample), while current methods use more previous samples to predict the next value. However, given our setting, we cannot process the sequence as a whole since it is dependent on other events that happen in between (e.g. the time series of a vessel speed). Since we are using the embeddings as the memory CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG of the network, we can consider that we process the time series asynchronously: the samples are processed one by one, but with the memory associated to the entity. It may have changed because of another happened event between two samples of the same type, but it will still be more similar to a normal sequence processing than a shared memory between entities. In a nutshell:

• AttrNet is also inspired from Know-Evolve RNN;

• We use Mean Squared Error to train the network;

• A temporal drift is added to the decoder to enable the choice of the prediction time during inference;

• Some parameters of the decoder are attribute type specific;

• The use of GRUs improves learning;

• More hidden layers improve the prediction results in the decoder.

RelNet

The architecture of RelNet is inspired by [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF]], but we had to do a lot of modifications. For instance, Know-Evolve maximizes the conditional intensity of the input event. In Joint Evolution, we assign challenges to events and try to maximize the conditional intensity of the future event (the challenge). In this section, we will present the architecture of RelNet and how it was designed.

A first version

As a basis for RelNet, we transposed the encoder-decoder system from [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF] to our setting.

• Subject embedding:

ρ t p s = σ(w s t (t p -t p-1 ) + W hh .h t p- s )
(6.17)

h t p- s = σ(W h [ρ t p-1 s ⊕ ρ t p - o ⊕ r p ]) (6.18)
• Object embedding:

ρ t q o = σ(w o t (t q -t q-1 ) + W hh .h t q-) o (6.19) h t q- o = σ(W h [ρ t q-1 o ⊕ ρ t q- s ⊕ r q ]) (6.20)
• With the score computation defined as:

g s,o r (t u ) = σ(W r [ρ t p s ⊕ α t x s ⊕ ρ t q o ⊕ α t v o ]) (6.21) where ρ s , ρ o ∈ R n , α s , α o ∈ R m , r p , r q ∈ R c , w s t , w o t ∈ R n×1 , W hh ∈ R n×ℓ , W h ∈ R ℓ×(2n+c)
and W r ∈ R 2n+2m . The encoder is pretty much the same (Equation 6.17 to 6.19). In the computation of the bilinear score, we want to include information from AttrNet, and we do so by concatenating CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG the relational and attributive embeddings of the entities before computing the score. Indeed, as stated in Section 5.2.1.2, we assume that the attributive knowledge will help the prediction of missing or future relations.

Inclusion of challenges

We now add challenges for each input. We start with three challenges: one for the subject, one for the relation type and one for the object. The objective is to be able to predict either of the three members of the quadruplet, and thus to have an objective for each. For subject and object, we do as stated in Section 5.3. For the relation type, we take the input itself as challenge, since it would make no sense to take the next event with this relation type: the way the relation type interacts with the entities does not depend on the time series. Of course, some relationships may have different temporalities, e.g. a vessel will enter a port more often than it changes of owner. But what is more important is how the relation type links the two entities. Figure 6.6 illustrates the learning process with challenges. With the three challenges, there are now three computations of the bilinear score (Equations 6.22 to 6.24).

R e

g r (t u ) = σ(W r r [ρ t p s ⊕ α t x s ⊕ ρ t q o ⊕ α t v o ]) (6.22) g e s (t u ) = σ(W s r [ρ t p s ⊕ α t x s ⊕ ρ t q o ′ ⊕ α t v o ′ ]) (6.23) g e o (t u ) = σ(W o r [ρ t p s ′ ⊕ α t x s ′ ⊕ ρ t q o ⊕ α t v o ]) (6.24)
We can note that here, ρ

t q o ′ = ρ t q-
o ′ since o ′ was not involved in the input event. However, it can be processed elsewhere in the batch since the precedence constraint does not apply to challenges, only to input events. Depending on the order in which the events are processed, there is a probability that o ′ is also updated at t q , but that the change is not included when CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG (s, r, o, t ) is processed. We currently have no solution for this, and this will be a matter for future work in the input data ordering.

Training loss

Now that we have a score for the predictions, we must find a way to propagate the error and optimize the parameters of the network. We discuss here several solutions to tell the network what a good prediction is.

Softmax based

We consider a softmax function to deal with the prediction as a classification problem: we describe here the setting to cast the link prediction problem as a classification one.

Predictions For each part of the quadruple, different predictions need to be made. Thus, each event (e 1 , r, e 2 , t ) has three challenges:

• The next event for e 1 , (e 1 , r ′ , e 3 , t ′ ). Note that it could also be (e 3 , r ′ , e 1 , t ′ );

• The next event for e 2 , (e 2 , r ′′ , e 4 , t ′′ ) or (e 4 , r ′′ , e 2 , t ′′ );

• The challenge for the relation is the current event (e 1 , r, e 2 , t ).

Now, for each of these challenges, a softmax must be performed to predict the other members of the quadruple. For e 1 , e 1 is fixed and the two other members of the triple (time is left aside for now) are removed alternatively before doing the softmax, because this is what we will have during inference.

Prediction for the next event involving e 1 Equations 6.25 and 6.26 represent the softmax layer. Note that we added time as an additional information to the embedding, with a trainable parameter to modulate the temporal drift.

pr ed o = so f t max(W e so f t [(ρ t e 1 ⊕ r ′ ′ ′ e ) + w e t • (t ′ -t )]) (6.25) pr ed r = so f t max(W r so f t [(ρ t e 1 ⊕ ρ t e 3 ) + w r t • (t ′ -t )]) (6.26)
where W r so f t ∈ R |R|×2n and W e so f t ∈ R |E|×(ℓ+n) are the parameters to cast the information to the number of classes, and w e t ∈ R 2n , w r t ∈ R 2n , pr ed o ∈ [0, 1] |E| and pr ed r ∈ [0, 1] |R| . are the predictions made. The predicted class is the one with the highest value, and can be used to complete the quadruplet given as input (e.g. (e 1 , r ′ , ?, t ′ ) with pr ed o ). Note that we omit α t e for the sake of clarity in this section.

Prediction for r The prediction for r is based on the current event to learn the dynamics of the relation type with the entities (Equations 6.27 and 6.28). The time is not required since we work on the same event, and we just want to learn the dynamics of the relation type, not its evolution over time. We then fix r and try to predict s and o. (6.28)

One problem here is that we are using the same parameters than for the prediction of future events. But we do not want to learn the same thing since learning the relation type is to learn on the current event. Moreover, the parts with s and o learn to predict future events, not how two entities interact depending on the relation type. Thus, it may have no sense to use the same weights for these two different tasks.

Prediction for the next event involving e 2 The prediction for the next event of e 2 is very similar to e 1 (Equations 6.29 and 6.30):

pr ed s = so f t max(W e so f t [(ρ t e 4 ⊕ ρ t r ′′ ) + W e t • (t ′′ -t )])
(6.29)

pr ed r = so f t max(W r so f t [(ρ t e 1 ⊕ ρ t e 2 ) + W r t • (t ′′ -t )])
(6.30)

Score based

This method is based on Know-Evolve decoder system. From the updated embeddings, we compute the bilinear relational score g s,o r (Equation 6.31), then the conditional intensity function λ s,o r (Equation 6.32). At last, the negative log likelihood loss is applied (Equation 6.33) with N the number of events in the batch.

g s,o r = ρ t s ⊺ . R r . ρ t o (6.31) λ s,o r (t | t ) = exp(g s,o r ( t ))(t -t ) (6.32) - N p=1 log(λ s,o r (t p | tp )) (6.33)
The conditional intensity λ s,o r represents how likely it is for the event to occur. Thus, with the negative log likelihood, we maximize the probability that positive events (i.e. challenges) are predicted as likely.

Score computation If we take the previous example but with a score instead of a softmax, we have:

g e 1 ,e 3 r ′ (t ′ ) = ρ t e 1 ⊺ • R r ′ • ρ e 3 g e 1 ,e 2 r (t ) = ρ ⊺ e 1 • R r • ρ e 2 g e 4 ,e 2 r ′′ (t ′′ ) = ρ ⊺ e 4 • R r ′′ • ρ e 2 (6.34)
with R x ∈ R n×n . Then, we apply Equation 6.32 and 6.33 with t the time of the predicted events (t, t' and t" in Equations 6.25 to 6.30) and t is the time of the input event (t in Equations 6.25 to 6.30).

One potential issue when predicting pr ed r is that t may be equal to t and the time delta in the conditional intensity g e 1 ,e 2 r (t ) is thus equal to 0. We could remove the temporal drift from CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG the conditional intensity when we predict from r, but this would be inconsistent with the other loss computations. This cannot happen with pr ed s and pr ed o since t > t by construction of the challenges.

Softmax or score

The softmax method is less intuitive to use and has no defined process for time, while the score-based prediction uses a temporal point process. Both methods suffer from a lack of clarity when predicting on the current event (for the relation type).

For these reasons, we choose to work with a score and not with a classifier. Also, the challenge used for the relation type is tricky to implement and is not consistent with the two others. Since the relation type is already represented in the encoder (r p , r q in Equations 6.18 and 6.20) and in the decoder (R r in Equation 6.31) as trainable parameters, a third challenge is not needed to model the interaction type. We thus remove this challenge to only keep the ones for subject and object, consistently with what is presented in Section 5.3.

Survivance

The current loss term maximizes the score of each happened event, but nothing prevents it to maximize each event and still reach its goal. To balance the positive events, we add negative events whose scores must be minimized (as in [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF]). A negative event is an event that did not happen in a timeframe [T, T+t[.

The problem is that computing all possible examples is very expensive, with a complexity of O(|R||E| 2 ) (Equation 6.35). [ [START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF] propose a solution to reduce the complexity to O(|E||R| j ) with j the size of the batch:

• For each event e in the batch, compute the survivance of the subject (resp. object)

• To do so, compute the survivance for the subject (resp. object) with every possible object (resp. subject) within the batch, but the resulting triple must not exist in the batch. The relation type may or may not be fixed.

• Add the survivances together. This is possible because their batches are sliding windows on the temporal sequence and represent all events in the timeframe [T, T+t[ of the batch. With our batching system, it is not possible to do so since in general, a batch does not contain all the events happened during its time frame.

To bypass this issue, we propose our own sampling strategy for negative events. Let (s, r, o, t ) be an input event and (s, r ′ , o ′ , t ′ ) or (s ′ , r ′ , s, t ′ ) its challenge for s. We set the time frame of each event in the batch between its own timestamp t and the timestamp of its challenge t', since no events involving s happens in ]t , t ′ [ by construction of the batches. Then, we sample events with a random timestamp t ′′ ∈]t , t ′ [ by fixing s as it is in the challenge (subject or object) and replacing the two other slots by all possible values. This sets the CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG complexity of the sampling strategy to O(|E||R|) for each event of the batch, or O(|E||R|B) if we sample B timestamp(s) in ]t , t ′ [. The survivance for s is thus generated using Equation 6.36.

S s = r ∈R o ′ /s ′ ∈E τ f (τ)l og (λ r (τ|t )) |R| × |E| × B (6.36)
with τ the set of sampled timestamps from ]t , t ′ [ and λ r stands for λ s,o ′ r or λ s ′ ,s r depending on whether the challenge has s as its subject or object.

We add a term f (τ) that depends on the sampled time τ, based on the following hypothesis: the ground truth events at t and t' are based on observations, meaning that it is less likely that we missed an event around these timestamps. In other words, a negative event happening near t or t ′ is "falser" than an event happening far from them since an observation was made around it and it was not found. Thus, the survivance is lower the furthest t ′′ is from t and t ′ , as stated in Equation 6.37:

f (τ) = M t t a ∆ mi n(|τ -t |, |τ -t ′ |) (6.37)
where M ∆ τ is the mean delta between t ′ and t over the whole dataset (acting as a normalizer).

To sum it up, S s penalizes the events including entity s which did not occur in the dataset but could be predicted by RelNet: the higher the rank of the negative event, the higher the penalty in the loss. However, we mitigate this by penalizing less the negative samples that are far from events actually occurring in the dataset (the farthest being t ′ -t

2 ), so that, for instance, if the dataset is likely to have missing events for some long periods of time, the approach is not penalized too much.

For a batch, the negative log likelihood loss with survivance is thus defined by:

L = - N i =1 l og (λ s i ,o i r i (t ′ |t )) -S s i -S o i (6.38)

GRU

As for AttrNet, we replace the RNN version of the encoder with the GRU version. Given q, ρ - s , and ρ - o , the new encoder is defined as follows for updating ρ e on input (e, r, o, t ):

v s = t anh(W h s .[ρ - o ⊕ w r ])
(6.39)

z s t = σ((t -τ - s )w s z + W v z .v s + W hh z .ρ - s + b z ) (6.40) r s t = σ((t -τ - s )w s r + W v r .v s + W hh r .ρ - s )
(6.41)

h s t = t anh(W v t .v s + r s t ⊙ W t .ρ - s ) (6.42) ρ t s = z s t ⊙ ρ - s + (1 -z s t ) ⊙ h s t (6.43)
• ⊕ denotes concatenation of one-dimensional vectors, and ⊙ the Hadamard product (pointwise matrix multiplication),

• v s is the input value representing the event q, z s t is the update gate, r s t is the reset gate, and h s t is the current memory, CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG

• vectors w s z , w s r ∈ R n weigh the temporal drift between two events, and w r ∈ R d is a parameter specific to the relation type r ,

• matrix W h s ∈ R n×(n+d ) captures the current relation in the history of the entities, • vector b z ∈ R n is the bias vector of the update gate,

• W hh z , W hh r , W hh t ∈ R n×n are parameters governing which part of the embedding should be kept in the gate,

• W v z , W v r , W v t ∈ R n×n monitor the input value.
The embedding of o is updated similarly, swapping s and o in Equations 6.39-6.43. Equation 6.39 encodes the input event, but we excluded the subject on purpose because it is already included in the memory of the network.

6.3.6 Temporal point process [START_REF] Mei | The neural hawkes process: a neurally self-modulating multivariate point process[END_REF] proposes a Neural Hawkes Process based on Hawkes process. With this one, a happened event can excite the probability for other events, which suits our usecase better. For instance, a vessel entering a port should increase the probability for the exit event.

In [START_REF] Mei | The neural hawkes process: a neurally self-modulating multivariate point process[END_REF], the intensity function of the Hawkes process is defined by: λ r (t ) = µ r + q:t q <t α r q ,r exp(-δ r q ,r (tt q )) (

"where µ r ≥ 0 is the base intensity of event type r, α j ,r ≥ 0 is the degree to which an event of type j initially excites type r, and δ j ,r ≥ 0 is the decay rate of that excitation. When an event occurs, all intensities are elevated to various degrees, but then will decay toward their base rates µ". However, though more adapted to the problem at hand, this process will be left for future work since it is not trivial to add and implement, in particular with the parameters to tune. Still, we make some changes to the intensity function in Equation 6.45:

λ s,o r (t ′ |t ) = w t r (t -t ′ )(log(1 + exp(g s,o r )) (6.45)
We replace the exponential by a softplus function as suggested in [START_REF] Mei | The neural hawkes process: a neurally self-modulating multivariate point process[END_REF]. This approximates the ReLU function f (x) = max(0, x) while being strictly greater than zero. We also add a parameter w t r ∈ R 1 on the temporal drift to use it differently depending on the type of relation r , since different relations may have different temporal processes. This is done to consider that, for instance, the dynamic of a vessel entering a port is very different from a vessel exchanging goods or engaged in fishing activities.

Another loss

We devised another possible loss function for Joint Evolution. Our objective is to have the maximum conditional intensity for the challenge event compared to all possible events. To do so, we compute the conditional intensity for all possible negative event (as we do for the survivance) and keep the maximum value. We then subtract the conditional intensity of the ground truth event (the challenge) and try to minimize the difference between the two, i.e., to make the conditional intensity of the challenge higher than the conditional intensity of the negative events (Equation 6.46):

CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG L = (max(λ s ) -λ s ′ ) + (max(λ o ) -λ o ′ ) (6.46)
with s ∈ N s where N s is the negative sampling for subject and o ∈ N s where N o is the negative sampling for object. We can choose to bound this loss positively.

Streaming and unseen nodes

Maritime Situational Awareness requires constant surveillance and a continuous stream of information. As new AIS and events are coming, they must be included in the entity representations, even after the model is trained. Thanks to the encoder, upcoming events can be added to update the embeddings as they arrive. The decoder is only used when a prediction needs to be made.

Joint Evolution is also able to deal with unseen nodes. If an entity e ∈ E is encountered, it is added to |E| with an embedding initialized with zeroes. Prediction will not be accurate at first because the model has no prior information on the entity (cold start), but it gets better when it is encountered multiple times in an event.

6.5 Wrapping up: Joint Evolution 6.5.1 The framework Joint Evolution is composed of two specialized neural networks, AttrEmb and RelEmb, which respectively deal with DKG A and DKG R . We assume that attribute values for an entity e can be predicted from the attributional history of e only, so that AttrEmb receives input only from DKG A (that is, only the observed changes of attribute values for e are fed into AttrEmb).

On the other hand, one specificity of our approach is to use values of attributes for predicting relations, so that RelEmb receives both input from DKG R (the observed relational events involving the entities at hand) and the attributional features generated by AttrEmb to make its predictions. The global architecture is illustrated on Figure 6.7.

The input of the model consists of events q A ∈ DKG A and q R ∈ DKG R , arriving in a timely manner. Each network is composed of an encoder and a decoder. The encoder updates an embedding for each entity involved in the processed event, so as to capture the behavior of these entities given the past events involving them. When a prediction is requested, these embeddings are fed into the decoder of AttrEmb (resp. RelEmb), which uses this information to predict the attribute value (resp. the subject, relation, or object).

AttrNet

The network AttrEmb encodes DKG A to make predictions on the future values of attributes.

Encoder

When a new attributional event q = (e, a, v, t ) is observed, the encoder of AttrEmb takes as input both q and the current attributional embedding α - e of e, and produces the new attributional embedding α t e of e. To keep track of the chronological order of the changes of attribute values, we use a GRU neural network as this encoder [START_REF] Cho | On the Properties of Neural Machine Translation: Encoder-Decoder Approaches[END_REF]. Given q = (e, a, v, t ) and α t - e , the encoder is defined as follows:

z t = σ((t -τ -)w z t + v w a z + U z α t - e + b z )
(6.47)

r t = σ((t -τ -)w r t + v w a r + U r α t - e )
(6.48)

h ′ t = t anh(v w a t + r t ⊙ U t α t - e )
(6.49)

α t e = z t ⊙ α - e + (1 -z t ) ⊙ h ′ t ) (6.50)
In words, the new embedding for e is obtained as a function of the temporal drift (with a parameter w t which is shared by all attributes), of the new observed value (with a parameter specific to the attribute type), and of the previous embedding (with a parameter specific to the attribute type). Figure 6.8 illustrates Equations 6.47 to 6.50.

Here z t is called the update gate, r t the reset gate, h ′ t the current memory, and σ is the sigmoid function; v ∈ D a is the scalar value of the attribute a, ⊙ denotes the Hadamard product, and σ and z t → 1 -z t are applied coordinatewise.

Vectors w a z , w a r , w a t ∈ R m are attribute-specific parameters of the network. Matrices U z , U r , U t ∈ R m×m are parameters governing which part of the embedding should be kept in the gate. Finally, b z ∈ R m is the bias layer of the update gate.

Decoder

When at timestep t a prediction is required for the value of attribute a for entity e at some timestep t ′ ≥ t , the decoder is given as input the attributional embedding α t e of entity e, and is required to predict the most likely value v such that (e, a, v, t ′ ) is the real quadruple. We use a fully connected layer to predict the value v as follows: (6.51)

v = t anh((t ′ -t )w t + w a • hi d d en(α t e ) + b a )
(6.52) Figure 6.8 (right) illustrates this step.

Here, w t ∈ R is a parameter that modulates the prediction according to the time elapsed since the last change of value, w a ∈ R m is an attribute-specific parameter, and b a ∈ R is the bias. CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG 6.5.3 RelNet

Encoder

When a new relational event q = (s, r, o, t ) is observed, the encoder of RelEmb takes as input q and the current relational embeddings ρ t - s and ρ t - o of s, o, and produces the new relational embeddings ρ t s and ρ t o of s, o. Given the event q and the current embeddings ρ t - s , ρ t - o , we update the embeddings as follows:

v s = t anh(W h s .[ρ t - o ⊕ w r ])
(6.53)

z s t = σ((t -τ - s )w s z + W v z .v s + W hh z .ρ - s + b z ) (6.54) r s t = σ((t -τ - s )w s r + W v r .v s + W hh r .ρ t - s )
(6.55)

h s t = t anh(W v t .v s + r s t ⊙ W t .ρ t - s )
(6.56)

ρ t s = z s t ⊙ ρ - s + (1 -z s t ) ⊙ h s t (6.57)

Decoder

When at timestep t a relational prediction is required for some timestep t ′ ≥ t , recall that we assume that two out of s, r, o are given, and the prediction concerns the third component. Whatever the missing component, we explore all candidates and rank them, so that prediction amounts to computing a score for a number of quadruples

(s ′ , r ′ , o ′ , t ′ ).
We compute the bilinear relational score g s ′ ,o ′ r (Equation 6.58) from the updated embeddings for a challenge event q ′ = (s ′ , r ′ , o ′ , t ′ ) that involves one of the two entities from q.

g s ′ ,o ′ r ′ = (ρ t s ′ ⊕ α t s ′ ) T . R r ′ . (ρ t o ′ ⊕ α t o ′ ) (6.58)
where R r ′ ∈ R (n+m)×(n+m) is a relation specific matrix learnt during training. This score is then used to compute a conditional intensity function λ (Equation 6.59), that will be used to rank the possible events during the prediction step (the higher λ, the more likely the quadruple (s, r, o, t ′ )):

λ s,o r (t ′ |t ) = w r t (t -t ′ )(log(1 + exp(g s,o r )) (6.59)
This is an adaptation of the modified softplus function found in [START_REF] Trivedi | DyRep: Learning Representations over Dynamic Graphs[END_REF]] and [START_REF] Mei | The neural hawkes process: a neurally self-modulating multivariate point process[END_REF]. Using the representation of the current event, Joint Evolution will thus learn which event to predict next. The delta of time (tt ′ ) illustrates the Rayleigh process used in Know-Evolve: the longer an event has not happened, the more probable its occurrence is.

Usage

Update

During training, the networks learn how to build embeddings that can be used to make predictions. Once trained, all parameters are frozen but the embeddings are continuously updated as new events happen. By using the embeddings of the members of the current event (time t ) in the encoder, the new knowledge is directly included in ρ e and α e , so that the model has all available data to perform a prediction at a time t ′ > t . It can thus be fed with a stream of data, update the embeddings continuously, and at any time be ready to predict next events. CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG

Prediction

The prediction of the next value for an attribute is done directly at the output of AttrEmb: this is a scalar value computed using α e (Equation 6.52). To predict the next relational event for an entity, we set the time and two of the three other components, e.g., (s, r, ?, t ), and we look for the most probable object for relation r with subject s and time t . We thus replace the object by each possible entity, compute their bilinear score and conditional intensity with Equations 6.58 and 6.59, and rank them. The most probable events are those with the highest conditional intensities.

Losses

The loss used for AttrNet is a Mean Squared Error, a common loss for regression:

Loss = 1 N N i =1 (v(t p+1 ) i -v(t p+1 ) * i ) 2 (6.60)
As for RelNet, we kept the second presented loss:

L = (max(λ s ) -λ s ′ ) + (max(λ o ) -λ o ′ )
(6.61)

Conclusion

We presented Joint Evolution, a double recurrent network encoder-decoder system for Dynamic Attributed Knowledge Graphs. During its construction, we made the choices that are the more suited to MSA, namely, a representation for each entity, a decoder that can get the likeliness of an event on-the-fly and a continuous update of the representations as new data comes through the encoder. With its two recurrent networks, Joint Evolution can deal with both relations and attributes. We are thus able to test our hypothesis on the impact of the attributes on link prediction. In Part III, we present the experiments run to evaluate Joint Evolution.

Part III Experiments CHAPTER 7. DATASETS because it is in degrees, and values such as 2 and 350 may be considered to be far apart from each other by the network while there are in fact very close. An option is to use the cosine and the sine instead, but this means that the course has to be learned from two dependent values. It would make the task more difficult, and this problem already arises with position (but position is mandatory to get the movements of the vessels).

In these 4,405 events, there are only 363 unique MMSI and the subjects and objects are two separate sets: there are 174 unique subjects and 189 unique objects (and 174 + 189 = 363). Since we are interested in the link prediction task, we have no use for vessels that are only involved in attributive events. We can thus only use these 363 MMSI and discard the rest.

A major issue is that we do not have any AIS for object vessels. The AIS of the 174 subject vessels include 10,735,097 observations (one observation contains the four attributes), i.e. 56,39% of all the observations (from 5,055 vessels). We hence have a lot of information for these subjects, but only a little for the objects. Once we exclude the course over ground, we have 32,205,291 attributional events.

About our datAcron version

For scalability reasons, and because it is the only part manually verified by experts, we only use the first month of the dataset. Among all detected events, we only consider those which include two different entities (pilotBoarding, rendezVous, tugging). In terms of dynamic attributes, we consider the latitude, the longitude, and the speed of the vessels. Some statistics about this projection of the dataset are reported in Table 7.1.

The relation/attribute ratio of datAcron is very unbalanced with more than 4M attributives event for only 764 relational ones. Though it might seem problematic, it is an opportunity to test AttrNet capability to improve an entity representation and the subsequent relation prediction. DBLP (Section 7.2) allows us to evaluate Joint Evolution on a different setting.

DBLP

To test JointEvolution, we use the Digital Bibliography & Library Project (DBLP) to learn and predict citation and co-autorship between two authors. Specifically, we use the DBLP v12 dataset from AMiner [START_REF] Tang | Arnetminer: Extraction and mining of academic social networks[END_REF]. It contains 4,894,081 papers and 45,564,149 citation relationships as of 2020-04-09. The detailed content of the dataset can be found on the website1 .

Our objective is to predict new relations between authors: citation or co-authorship relations. To do so, we need to preprocess the dataset since these links are not explicitely formatted. Since the file is very large (12GB), we filter out the irrelevant information to save some space. First, we only keep the field of study (FoS) of the article, its id, its authors, its title, its year of publication and its references. Then, we extract several dictionaries from the file so that we can construct the graph:

• Author information id_author: [name, org]

• Organization name_org: id_org • Article information id_article: [title, year, author_list] CHAPTER 7. DATASETS so many relational quadruplets. Moreover, we came to the conclusion that these attributes can be derived from the relational dataset and do not add valuable information to the learning. Moreover, if the publication behavior of an author helps to characterize the entity, it is not straightforwardly clear that it can help to predict a citation or co-authorship link between two authors. To consider the scalability and attribute usefulness issues better, we designed a second version of the dataset.

Second version

Since the first dataset is too large, we extract authors and articles only between 1995 and 2000 in the field of Artificial Intelligence, and only authors that have at least 5 publications. We made this choice based on the rapidly evolving nature of this field, and we did not take more recent years into account due to the too large number of publications and authors that would throw us back to our previous issue. In this setup, we consider two relation types, :cite and :coauthor. We discard the :citedBy relation type, because it is the symmetric relation of :cite and doubles the number of edges for :cite. Concerning the attributes, we completely change the previous selection: since scalar values that describe the publication rate and impact are not that useful to predict citation and co-authorship relations, we use the articles themselves as attributes.

Indeed, an article contains useful information on the field of study and the specific notions an author is working on. Of course, the field of study is already known, but it is not a discriminant factor here since we restricted ourselves to Artificial Intelligence. Thus, we link articles to authors as attribute values using two attribute types, :write and :cite. The first one provides information on the current work of the author, and the second one on the related works.

The problem is that an article is not represented by a value as it is. There exist several ways to get a representation for an article: [START_REF] Liu | Link prediction in paper citation network to construct paper correlation graph[END_REF], Meng et al., 2020, Meng et al., 2019] and [START_REF] Li | Streaming Link Prediction on Dynamic Attributed Networks[END_REF] use the keyterms extracted from the titles or abstracts as attributes (bag-of-words), and [START_REF] Meng | Jointly Learning Representations of Nodes and Attributes for Attributed Networks[END_REF]] also uses the conferences.

Since the abstracts of the articles were not always available, we used the title of the articles. We try to go further than keyterms by projecting the whole title into 512-dimensional embeddings created with Google's Universal Sentence Encoder [START_REF] Cer | Universal Sentence Encoder[END_REF]. Each time an author cites or write an article, an associated attributional event is created with this embedding as a value. Thus, the attributional embedding of an author will reflect his/her field of publication by aggregating the titles.

About the dataset

The final version of the dataset has 6,147 authors, 37,097 articles, 351,365 relations divided between :coauthor (40,786) and :cite (310,579), and 139,152 attributes divided between :write (43,648) and :cite (95,504). Regarding the link prediction problem on dynamic attributed graphs, DBLP is a reduction of it since the time scale is year by year, which is equivalent to a sequence of static graphs of reasonable length (5 slices). With a maritime dataset that contains AIS data, the timescale is the second and it would be much harder to use such a sequence, hence the streaming scenario. But Joint Evolution can still be applied since it can work with any timescale. CHAPTER 7. DATASETS

Adaptation of Joint Evolution

AttrNet takes scalar values as input to update the attributive embeddings of entities, but DBLP provides embeddings. To adapt AttrNet, we cast this embedding to the size of the embeddings of the entities, i.e. m. The encoder thus becomes:

v ′ ′ ′ = W c ast v (7.1) z t = σ((t -τ -)w z t + W a z v ′ ′ ′ + U z α t - e + b z ) (7.2) r t = σ((t -τ -)w r t + W a r v ′ ′ ′ + U r α t - e ) (7.3) h ′ t = t anh(v w a t + r t ⊙ U t α t - e ) (7.4)
α t e = z t ⊙ α - e + (1 -z t ) ⊙ h ′ t ) (7.5) with v ∈ R 512 , v ′ ′ ′ ∈ R m , W c ast ∈ R m×512 and W a z , W a r ∈ R m×m .
Thus, each embedding of a title is included in the attributive embedding of the entity. However, a new issue arise: we formerly predicted the next attribute value to train AttrNet, but what are we going to predict now? Predicting the embedding or title of the next article an author will write or cite makes no sense and these attributes are only here to characterize an author field and help the relational prediction. So instead of decoding α e to train AttrNet, we only use RelNet to train AttrNet encoder. When a link prediction is made and the loss is computed by RelNet, it backpropagates to the RelNet encoder and decoder, but also to AttrNet encoder. To sum it up, we train AttrNet encoder directly on the RelNet decoder that uses α e to predict new links.

Conclusion

We test Joint Evolution on two datasets, datAcron and DBLP. datAcron has less entities and relations but has a lot of fast evolving attributes. It is useful to test Joint Evolution dynamic capacity as well as the effect of attributes on link prediction, especially when there a only a few relations to learn. Our hypothesis is that the large number of attributes will compensate the lack of relations. On the other side, DBLP has less attributes than datAcron but the dataset is more balanced. However, its dynamicity is at the scale of a year where datAcron can work at the scale of a second. DBLP is thus closer to a sliced DKG than to a streamed DKG.

CHAPTER 8

Experimental settings

Dataset settings

Preparing the data for the experiments requires several preparatory steps. The major ones are described in Section 5.3: assigning the challenges, generating the precedence graph and extracting the batches. In addition to this, we normalize all values of datAcron attributes to [-1, 1], which is the range of the tanh function we use in AttrNet. The preprocessing of the datasets is not a trivial task and requires several hours of computing because of the complexity of relational data. To train Joint Evolution, we use 90% of the dataset as the training set and the remaining 10% as the validation set. Since we build batches of independent sequences, the training set is always the same (namely, the 90% earliest events) since we cannot perform a cross-validation: this would shuffle the events and negate the benefit of the precedence graph.

Learning task

We train Joint Evolution to predict the new entity in the challenge, i.e. the one that is not in the input (as described in Section 5.1). By doing so, the model will be able to answer questions such as (s, r, ?, t ). However, datAcron does not contains any AIS message for the object entities, and there is no intersection between the sets of subject ( 174) and object entities (189). The model thus runs essentially without α t o . We test both datAcron and DBLP with and without attributional embeddings so as to determine whether the addition of α t e improves the prediction results. The tests that use only RelEmb are thus our baseline to evaluate the addition of attributes. Note that during validation, embeddings are still updated with incoming events. When training with relations only, AttrEmb is not used and all α e stay at zero, thus negating any parameter associated to them during the computation of the scores.

Since DBLP uses embeddings and not scalars as attributional values, there is no task on AttrNet for prediction. Thus, we learn AttrNet directly from the link prediction task of RelNet, i.e. we only train and use the encoder of AttrNet by feeding RelNet.

Model comparison

To compare our method, we use two models implemented with the StellarGraph library [Data61, 2018]. It offers state-of-the-art methods for graph machine learning and supports many kinds of graphs: homogeneous, heterogeneous, graphs with or without data associated to nodes (the attributes), and graphs with edge weights.

node2vec

node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF]] is an embedding method on static, homogeneous graphs that we already presented in Section 4.2.2.3. We test against node2vec for two reasons: it is a largely known and used model, and it allows to evaluate the gain of performance provided by dynamic models over static models on dynamic relational data.

CTDNE

CTDNE [START_REF] Nguyen | Continuous-Time Dynamic Network Embeddings[END_REF] is an embedding method on dynamic, homogeneous graphs using temporal random walks without slicing the graph. We presented this model in Section 4.4.3. It allows us to test Joint Evolution against a dynamic method. The embeddings are generated through temporal random nodes and can be used for downstream machine learning tasks.

Adaptations

Both node2vec and CTDNE learn embeddings that cannot be easily updated: they are created by a selection of random walks, and incorporating new data implies to perform the walks selection again. It means that with these two techniques, the embeddings are learned once and for all. On a long-term use, this may requires to generate new embeddings to update the behavior of the entities.

As these methods cannot update the embeddings in a streaming fashion, we create the embeddings using 75% of the datasets. The next 15% are then used to train link prediction using the RelNet decoder and the last 10% to test the learning. Moreover, they both deal only with homogeneous data when learning the embeddings. However, the decoder of RelNet takes the relation type into account when using the embeddings, which allows a fairer comparison with our embedding method since node2vec and CTDNE initially cannot. Also, we removed all timestamps when using node2vec and did not use deltas of time in the decoder since it is static.

Measures of performance

To evaluate the performance of Joint Evolution, we watch the score of the ground truth event compared to other events.

Score and rank

The output of Joint Evolution provides a score for a given event, that allows to measure the capability of the model to predict correctly. The score predicted for the ground truth is compared to the score predicted for negative (generated) events. This way, we can evaluate CHAPTER 8. EXPERIMENTAL SETTINGS how the model fares to give the best possible score to the ground truth. By sorting the event scores by descending order, we obtain a ranking for the ground truth. Our objective is thus to optimize the rank of the true event to get better prediction during inference.

8.4.2 MAR and Hits@X Two measures are commonly used for link prediction: Mean Average Rank (MAR) and Hits@X. The first one is the mean rank of the ground truth value for all events in the set. It tells how good the model is on average, but what defines a good value depends of the number of candidate entities. The Hits@X measures how many ground truths are ranked in the top X scores. For instance, Hits@10 is the proportion of true events that are in the top 10 in terms of score. It should be noted that the better rank is 1 and that Hits@X is in [0, 1] (hence the higher the better: @Hits10 = 1 means that all samples are classified in the top ten, and none if Hits@10 = 0). We thus look for low values of MAR and high values of Hits@X.

MAR is representative of how the model fares in general, but Hits@X is more about the proportion of useful predictions: in an operational use such as MSA, it is better to have a good Hits@10 rather than a good MAR -though the two are linked. This is because it is easier to verify the 10 best predictions manually by browsing the suggested vessels than to verify 50 or 100 predictions.

In these experiments, we report Hits@1, Hits@10, Hits@30, Hits@100 and Mean Average Rank (MAR) for object prediction. Given a quadruplet (s, r, ?, t ), we compute the score of all possible quadruplets by replacing the object by all possible entities. We then rank the quadruplet by score and report the mean rank for the ground truth quadruplet as the MAR score (hence the lower the better).

Software and hardware

Joint Evolution was implemented from scratch using the PyTorch1 library. It is an open source machine learning framework whose two main features are tensor computing with strong acceleration via graphics processing units (GPU) and deep neural networks built on a type-based automatic differentiation system.

To preprocess the DKG, we use OrientDB. It is a graph and document-oriented database made to manage relational data. It allows easy storage and manipulation of entities and edges, and can create visualizations of the graph such as Figure 5.4 to navigate through it. For the precedence graph, we used networkX, a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

As for hardware, preprocessing of the data and trainings are done on a server at the GREYC laboratory. The machine is built with two Intel Xeon E5-2620 v4 at 2.10GHz that totalizes 32 cores, 512GB RAM, 4 GeForce GTX 1080 Ti as GPUs with 11GB of memory each to contain the models. A single GPU is sufficient to run the experiments, but we can run several experiments at the same time with more GPUs.

Parameters

We present here the parameters used for training and their effect: CHAPTER 8. EXPERIMENTAL SETTINGS

• Batch size: The size of the batches of input data. We set it to 100 and did not make many changes because the sequence of batches is precomputed from the precedence graph. Unlike many machine learning input pipelines, we cannot change the size of batches on-the-fly.

• Training set: The percentage of the dataset used for training. As usually done, we use 90% for training and 10% for validation. It should be noted that since we work with specifically ordered sequence (thus with no cross-validation), the test and validation sets are the same set.

• Epochs: the number of times the full dataset is processed. The embeddings are set to full zeroes at initialization and between two epochs: we train the weights, not the embeddings, and the history must be reset at each new start.

• Embedding size: the size of α e and ρ e .

• Learning rates: the learning rates for AttrNet and RelNet.

• Schedulers: a scheduler decreases the learning rate every X epochs and has two parameters: the number of epochs X and the multiplier for the learning rate (γ ∈ [0, 1]).

• Weight decay: how much the weights decay between epochs. Decaying prevents the network from being stuck in a local optimum, but can also negate the learning if too high (which happens in particular with a decaying learning rate).

• Dropout: the percentage of neurons deactivated in the dense layer of the AttrNet decoder. This forces the network to use different paths and not to always reinforce the same neurons.

• Gradient clipping: sometimes, the gradient can explode during training. To avoid this and not end up with infinite or NaN (Not a Number) values, we clip the gradient to a maximum value to keep it stable.

We did not perform a grid search to find the best set of parameters for two reasons: there are too many of them, and the computing time for one run is high. In Chapter 9, we empirically test several combinations of these parameters.

Conclusion

We train Joint Evolution to predict the missing entity in a quadruplet (s, r, ?, t ) or (?, r, o, t ) and compare the results with the two other models, node2vec and CTDNE. The performances of all models is measure using Mean Average Rank and Hits@X metrics, and various sets of parameters. In the next chapter, we present the results of these experiments.

CHAPTER 9

Results and discussion

In this chapter, we present the results of the experiments and discuss them. Section 9.1 successively presents the results for each method with different sets of parameters to deduce what are the best results for the method. Section 9.2 makes the comparison between the methods and their best results to deduce which one works better overall. To understand the curves, the x-axis reads the number of epochs and the y-axis reads the value of the metric. The type of the metric is written above the curves. For instance, in Figure 9.1, the blue curve of Hits@10 reaches 0.15 at the epoch number 15.

Final results

We present here the results for Joint Evolution, node2vec and CTDNE on datAcron and DBLP. The tests are performed with and without attributes. We report the MAR and the Hits@1, 10, 20, 30 and 100 to get an accurate view of the performances of the models. We chose several values of Hits@X because a model could fail in the top 10 but be very good on the top 100, which is still a good result if there are thousands of entities. The resulting curves represent the metrics over the number of epochs. We also report the loss during training and validation.

Joint Evolution

All runs are done with an embedding size of 50 for both attributes and relations: with a higher embedding size, the space is too large and the features are not learned properly.

datAcron

Full set The results for datAcron are a little unstable due to the low number of samples but they stay within the same range. In Figure 9.1, the blue curve starts well but the results decrease dramatically after 10 epochs. On the other hand, the green and pink curves are more stable despite having lower results (if we do not consider the spike at the beginning). We remark that the model performs equally at Hits@10 and Hits@100, meaning that there are few results ranked between 10 and 100. The main difference between the two behaviors is the weight decay: it is set at 0.005 for the blue curve and respectively at 0.2 and 0.3 for the green and pink ones. The model may require a higher weight decay to not overfit, especially with the low number of relational samples.

In Equation 6.61, we positively define the loss by choosing the maximum between the loss and zero. Blocking it at zero may prevent the model to learn further, so we remove this constraint to see if it improves the results. According to Table 9.1, the results are indeed improved. Looking at the blue line, the metrics are doubled. Surprisingly, it is this time the lower weight decay that gives the better results (0.005 opposed to 0.2 and 0.3). As a final result, we keep the blue curve for its stability. The chosen parameters are reported in Table 9.1 and the results in Table 9.2.

Relation only

We then test Joint Evolution on datAcron, but without DKG A . Only RelNet is trained here using the 764 relational quadruplets. We report the curves in Table 9.3. This version of the dataset is less sensitive to parameters since all the runs are rather close in terms of metrics. Hits@1 is still unstable due to the low number of samples. This time, we keep the positivity constraint from Equation 6.61 since it gives good results and is also used on DBLP. We report the results of the blue curve in Table 9.4.

With and without attributes

We now make the comparison between the two version of the dataset and check our hypothesis about the role of attributes in the learning process (Figure 9.2). On each metric, the version without the attributes outperforms the one that uses them. Our intuition is that the four million attributive quadruplets add too much information compared to the raw relational quadruplets and disrupt the learning. 9.1: Curves and parameters used for Joint Evolution on datAcron, but the loss is not positively defined MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 16.21 0.3504 0.748 0.939 0.9528 0.9685 MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 7.58 0.8784 0.9662 0.9764 0.9764 0.9831 Full set On the full set of DBLP, Joint Evolution has almost the same behavior with different parameters: it always reaches the same plateau, the difference being the time taken to reach it. In the curves of Table 9.5, the plateau is reached from the first epoch, then the metrics decrease to then reach the plateau again. This is due to the high value of learning rate (parameters in Table 9.5). For instance, the red curve takes more time to get better because the learning rate stays higher during a longer time (higher multiplier). Since the learning rate needs to decrease over time to reach an optimum without diverging, it is slower than the other runs. The weight decay is set at 0.005 for all runs because higher values will erase what has been learned too much. In Table 9.6, we present other runs with a lower learning rate. The learning is more stable with a natural progression and reaches the same maximum values as the previous runs. Because of this stability, we choose to retain these curves. Note that the orange and blue curves have the same parameters but a different seed for the training (the seed impacts the random initialization of the weights).

The results for Joint Evolution on the full set of DBLP are reported in Table 9.7.

Relations only

We now test Joint Evolution on the DKG R of DBLP only and report the curves and parameters in Table 9.8 and the results in Table 9.9. The learning rate has the same effect as on the full dataset, and we retain the pink curve for this very reason.

With and without attributes We now make the comparison between the two versions of DBLP, with and without the attributive part (Figure 9.3). The difference between the two seems large on Hits@1, but it is negligible given how close to zero both metrics are. Idem for the MAR which shows little difference. However, the gap is more significant on other Hits@X metrics, in favor of the strictly relational dataset. Thus, our hypothesis is false on the two datasets. MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 517.6 6.6466e-3 0.0629 0.0958 0.2187 0.488 Table 9.9: Results for Joint Evolution on DBLP relational quadruplets (pink curve)

CTDNE

We now apply CTDNE to the two datasets. Since it does not deal with attributes, we only test it on DKG R .

datAcron

Since the embedding does not evolve in this setting and because there are no attributes to learn, the training of CTDNE is very quick (a few seconds per epoch) and reaches its optimal points in a few epochs (6). We report the curves and parameters in Table 9.10. The effects of the parameters is hard to evaluate on CTDNE. The most discriminant one is the learning rate since the two best overall curves, the red and dark blue ones, have the same, higher learning rate. However, the differences between the blue and orange ones are not explainable and require more experiments to clarify. We chose the red curve as the best one over the blue one because despite the large advantage on Hits@1 for the latter, this result is not stable and the performance is not as good on other metrics. Lastly, we chose the red over the dark blue one for its behavior regarding the loss: it is better on the red one even if the metrics are the same. This can be explained by the use of a scheduler on the dark blue one while there is none on the red. We can clearly see that the loss stops improving after five epochs, meaning that the learning rate becomes too low to improve the model further. This would also explain the lesser performance of the blue and orange settings.

We report the best results, represented by the red curve, in Table 9.11. It seems that there are no results between Hits@10 and Hits@100, meaning that 92.21% of the predictions fall between 2 and 10 and the remaining 7.79% between 101 and 363. MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 2.117 0.8312 0.987 0.987 0.987 1 Table 9.15: Results for node2vec on datAcron relational quadruplets (blue curve)

datAcron

As for CTDNE, the training of node2vec on datAcron takes only a few seconds per epoch. However, we must this time wait 30 epochs to reach the optimum, but this is not a problem since it remains a matter of minutes. We report the curves and parameters in Table 9.14. Undoubtedly, the determining parameter to train node2vec is the weight decay. The higher it is, the worse are the results: the decay of the weight must be too strong compared to the learning and the best setting is with no decay at all. The learning rate seems to have little effect: orange and pink have the same value and are diametrically opposed, while the blue one is in between while having a different value. Looking at the curve, the motto here is the lower the weight decay, the better the results. We report them for the orange curve in Table 9.15.

DBLP

The training on DBLP is longer than on datAcron (one hour/epoch), but still faster than CTDNE on the same dataset, and it takes 13 epochs to reach its optimum. We report the curves and parameters in Table 9. 16.

Apart from the pink and grey curves, all settings behave similarly. In the grey case, the metrics do not evolve at all: the only differences laying in the gradient clipping and weight decay, further experiments are needed to see which one (or maybe both) is responsible for the learning impediment. The difference between the pink and blue curves, that have exactly the same setting, cannot be explained with the current experiments and requires further testing too. The most unsettling result is the decreasing values for Hits@1, 10, 20 and 30 over time

datAcron

We report the results for datAcron on Figure 9.4 and Table 9.18. The best method overall is node2vec, closely followed by Joint Evolution without the attributes. Still, all methods have similar performances in all metrics excepted for Hits@1, which suffers of instability caused by the low number of samples. We also noticed lower results for Joint Evolution on Hits@10.

Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 MAR node2vec 0.

DBLP

We report the results for DBLP on Figure 9.5 and Table 9.19. Joint Evolution without attributes has the best overall results, followed by Joint Evolution, then CTDNE and node2vec. CTDNE is close to Joint Evolution on Hits@10 and Hits@30 and even surpasses it on Hits@20, but the large gap on MAR in favor of Joint Evolution makes it better. node2vec, CHAPTER 9. RESULTS AND DISCUSSION Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 MAR node2vec 0

1.145e -4 7.252e -4 1.603e

Analysis

We ran our experiments on two datasets: one adapted to our usecase (MSA) and the other one more suited to an academic evaluation and comparison to other models.

Datasets

The first one, datAcron, is a small dataset, easier to learn. All models were able to learn well on it, probably due to its small size. We need to run more experiments on a larger dataset of this kind to evaluate if the models can generalize well. Joint Evolution (with attributes) is the model that struggled the most on datAcron: our hypothesis is that the dataset is too simple compared to what Joint Evolution is made to handle regarding the number of entities, relations and relation types, hence the difficulties to learn. The number of parameters is too large for the model to be trained correctly. Another possibility, given that Joint Evolution without attributes comes in second place, is that the attributive embeddings add noise and do not help the learning. For all datasets, the Hits@1 is unstable and not very representative of the model performances because of the limited dataset size. This metric should have more sense with a larger dataset. On the second dataset, DBLP, the ratio between relational and attributive links is far more balanced. Joint Evolution has the best results on this dataset, with a small advantage for the CHAPTER 9. RESULTS AND DISCUSSION version without attributes. Despite the size of the dataset being more adequate, the version with attributes may suffer from its large number of parameters: a 512×50 matrix is needed to scale the title embeddings to the size of the attributive embeddings. Also, Google's sentence encoder is trained to output vectors of size 512, which is a lot considering that we only embed the titles of the articles (the embedding may actually be longer than the title itself). It may have been better to embed the abstracts, but they were not always available. The easiest option here would be to reduce the output size of the sentence encoder.

CTDNE has results close to Joint Evolution, apart from its higher value of MAR. It status of dynamic model allows it to learn more efficiently than node2vec, but the results might be impeded by the absence of update for embeddings and the homogeneous learning of embeddings. At last, node2vec cannot learn because the larger dataset size implies more temporal dependencies. node2vec being a static method, it cannot capture the evolving interactions between entities.

On the use of attributes

Since Joint Evolution with RelNet always has better results than Joint Evolution, our hypothesis that attributes improve results on link prediction is rejected. Unfortunately, the addition of attributes in the link prediction task degrades the results compared to a purely relational approach. However, Joint Evolution without attributes still performs better than CTDNE and node2vec, and Joint Evolution has streaming capabilities with embeddings that can be updated over time, which is an important requirement regarding MSA.

Despite these results, we still hope that attributes can improve the prediction of new relations, since additional information should always be beneficial to infer new links. Here are several leads on why we did not get the expected results:

• The training of Joint Evolution involves a large set of hyperparameters, and every combination of them could not be tested because of the computation time it would require. Thus, we may have missed the perfect set of parameters that would have made Joint Evolution work better with attributes;

• datAcron is an unbalanced dataset, and its main purpose was thus to check if a large number of attributes can alleviate the lack of relational links. However, maybe a minimum number of links is needed and we did not reach this minimum with datAcron. Since we will always have more AIS than relational events, this experiment should be run again on a larger set of events;

• In datAcron, the dynamic attributes were natural and straightforward: a vessel has a position and a speed that evolve over time. In DBLP, the notion of attribute is a little more farfetched: the articles used as attributes can also be considered as entities, and they can be represented by multiple values. We chose to encode the title because it was the most straightforward way to do it and it represents the article field, but other values may have worked better. By wanting to be more precise in the information given to Joint Evolution, we may have made learning noisy. Using the conference of publication is another lead than can be explored, although some conference themes can be large and not give enough information about the theme of the publications;

Conclusion

We tested four methods on datAcron and DBLP: Joint Evolution, Joint Evolution without the attributive network, CTDNE and node2vec. The two datasets are very different in nature and make the results of the four methods different. All methods perform well on datAcron while only dynamic methods work on DBLP. The best overall method is Joint Evolution without attributes, which dismisses our hypothesis on the benefits of attributes in the relation prediction process. We presented possible causes and leads to improve the results, and still hope that, in the correct setting, we can use attributes to improve the prediction of relational links.

CHAPTER 10

Summary and perspectives

Summary

Since this thesis is in the scope of the CIFRE program with GREYC and Airbus Defence and Space, we started by presenting the industrial problem this thesis aims to solve. The main objective is to improve Maritime Situational Awareness and provide a decision aid to surveillance operator who have to navigate through a lot of incoming hard and soft data. To improve the understanding of a situation, we analyze historical data to predict next events and raise early alerts. In order to do this, we needed to create a representation of the past and current maritime situation and turned to knowledge graphs to do so. Their semantic descriptive capabilities coupled with the graph-based interactions make them a great tool for this purpose. We then started by assessing the state-of-the-art on two topics: how to improve maritime situational awareness and link prediction methods on dynamic attributed graphs. In the first one, we found many approaches on route generation and anomaly detection. Some deal with events, but mostly with rule-based engines. The field of MSA improvement using event-based link prediction methods on knowledge graphs is thus not actively studied and that is where we position this work. On the second topic, we found out that there are many contributions about link prediction in static, static attributed and dynamic graphs, but fewer in dynamic attributed graphs. We thus take inspiration from the dynamic methods to adapt them to a new setting including attributes, while making the hypothesis that attributes can improve the results of link prediction.

Based on this, we proposed Joint Evolution, an encoder-decoder system composed of two parts: one that learns embeddings from changes of values for attributes to predict the next ones, and the other that learns relational embeddings to predict new relations in the graph using both types of embeddings. We designed a preprocessing pipeline to create independent sequences of events that ensure that events happening to an entity are processed in the correct order. We then made the choice to use Gated Recurrent Units to process these sequences and generate two embeddings for each entity: the attributive one and the relational one. Once the model is trained to update embeddings that can be used to predict the next event, embeddings can be updated on the fly as new events are observed using only the encoder parts of Joint Evolution. When a prediction is needed, only the decoder parts are used to answer the question at hand, generally in the shape of a quadruplet like (subject, relation, ?, timestamp).

CHAPTER 10. SUMMARY AND PERSPECTIVES

The decoder will then find the object that best fits the quadruplet by computing a score for each possibility.

We tested Joint Evolution on two datasets, datAcron and DBLP. datAcron is a set of events and AIS messages from vessels in the Bay of Biscay near Brest, and DBLP is a citation network that links authors and articles with authorship and co-authorship relations. The main differences between the two datasets lie in the number of events and in the type of the attributes, which gives us two settings to experiment with. We compared Joint Evolution with two other methods: node2vec, a well-known random walk approach to embed static graphs and CTDNE, its dynamic version. We also ran experiments with a version of Joint Evolution that considers relations only to evaluate the effect of attribute inclusion. In the end, Joint Evolution without the attributes is overall the best out of the four models, which rejects our hypothesis that the addition of attributes can improve the results on relational link prediction. Still, Joint Evolution has better results than node2vec and CTDNE and can deal with heterogeneous graphs in a streaming fashion. We still hope that any addition of information may be valuable to the learning and explain these results with several factors, the main ones being the large set of possible parameters and the configuration of the datasets.

Perspectives

With these results at hand, we now describe the limitations of Joint Evolution and pave the way for future work.

Limitations

We defined five essential items for MSA: follow the evolution of entities, detect events and threats, process streaming data, deal with uncertainty and make the output of the model explainable. Unfortunately, we did not have the time to work on uncertainty and explainability, which are left for future works. About the link prediction itself, Joint Evolution is limited to subject and object prediction. We are not able to predict when an event will happen, only which entity will connect with another at a given time. We focused on this because it is the main usecase for MSA but being able to predict time may also be a useful feature. The other prediction we are not able to make is the relation type: as stated in Section 6.3.3, training Joint Evolution to predict a relation type is different because the notion of challenge is not the same. We do take the relation type into account with the specific weights, but it does not give the capability to predict it. To be able to predict the time and relation type of an event, a new training setup must be devised.

Another problem in our setting is that the update is only performed on the entities involved in an event, while this event could have an effect on other entities. For instance, a conflict between two countries (entities c and c ′ ) cannot influence the relation between a vessel from country c (entity v) and a vessel from country c ′ (entity v ′ ) since the embeddings of v, v ′ are not updated when the conflict arises. Methods that take neighborhood and context into account in the knowledge graph could bridge this gap [Jin et al., 2019, Heidari andPapagelis, 2019].

The last limitation worth mentioning is the nature of the attributes we use. The attributes in datAcron are scalar values while DBLP uses vectors. It required an adaptation of Joint Evolution between the two. If a dataset were to mix both types of attributes, we would have to find a way to deal with both, for instance by deactivating the AttrNet decoder when vector attributes is encountered.

Short term perspectives

Our short term perspectives are mainly about the datasets and the experiments. To assess in a larger extent the effect of attributes, we would like to train Joint Evolution on a larger version of datAcron with more events and entities. We may also rethink the way we create attributes for DBLP in a more straightforward, easy to learn manner. This could start with the reduction of the sentence encoder dimensionality, the addition of the conferences where the articles are published and the organization the authors come from (though the latter implies dealing with static attributes).

Finding an evaluation dataset for dynamic attributed graphs is not easy since there is no dataset of reference in this field like MNIST1 is in image analysis. Some known graph datasets such as Epinions [START_REF] Richardson | Trust management for the semantic web[END_REF], Freebase or WordNet2 are often used to evaluate static graphs and are either undirected or homogeneous. Citation networks such as Citeseer [START_REF] Bhattacharya | Collective entity resolution in relational data[END_REF] and Cora [Getoor, 2005] are either static, homogeneous or without attributes, and are mainly used for article classification. Some well-known dynamic datasets are GDELT [START_REF] Leetaru | GDELT: Global Data on Events, Location and Tone[END_REF] and ICEWS [START_REF] Boschee | ICEWS Coded Event Data[END_REF] but it is difficult to find dynamic attributes in them. Enron [START_REF] Klimt | The Enron Corpus: A New Dataset for Email Classification Research[END_REF]] could be used as we used DBLP since it is an email exchange network, but it only has 150 entities and is homogeneous. Moreover, the complexity of the email contents may not help to predict a mail exchange between two employees. The creation of a reference dataset for dynamic attributed graphs would be of great help in this field of study.

Our last short-term perspective is to run more experiments on the current settings, especially regarding the sets of parameters. With more time, we could improve the choice of parameters and find the best setting for each method. We could also do better to evaluate the effectiveness of AttrNet, which was not extensively tested apart from optimizing its loss.

Long term perspectives

On the longer term, the objective is to fill the void in the requirements for MSA, namely uncertainty and explainability. Our major lead on uncertainty is the use of Markov Logic Networks and Probabilistic Soft Logics [START_REF] Chekol | Marrying Uncertainty and Time in Knowledge Graphs[END_REF][START_REF] Chekol | [END_REF]. About explainability, the study by [START_REF] Adadi | Peeking inside the blackbox: A survey on explainable artificial intelligence (xai)[END_REF] is a solid basis to find solutions adapted to our setting.

Another envisioned addition to Joint Evolution is a true semantic description of the entities and their interactions. We now have relation types, but currently no way to tell the system that an entity is a vessel or a port, which may play an important role in the learning process. Knowing in advance what an entity is, what its full set of attributes is, and what interactions it can have, reduces the number of possibilities when making prediction and could make the generation of new links more accurate. We would then have to find a way to include full ontologies within the model to provide their descriptive power to the service of the learning process.

Part IV Appendices I APPENDIX A. RÉSUMÉ ation (i.e. l'ajout de nouvelles informations sur l'environnement) doit idéalement être faite en temps réel et le temps de calcul des prédictions fait en un temps raisonnable pour que la réaction appropriée puisse être déployée aussi vite que possible.

Les graphes de connaissance sont de plus en plus utilisés pour représenter un champ de connaissances: des paires de noeuds dans le graphe sont reliées par un arc, formant une relation entre les deux noeuds sous la forme de triplets (sujet, relation, objet). Ce réseau de relations constitue un graphe de connaissance, et modélise des informations telles que (RMS TItanic, :construitPar, WhiteStarLine). Le plus souvent, cette connaissance est statique et n'évolue pas au cours du temps. Mais le graphe peut également indiquer à quel moment un événement s'est produit, e.g. (RMS Titanic, :construitPar, WhiteStarLine, 1909). Avec les graphes dynamiques, de nouveaux liens peuvent être inférés grâce à l'apprentissage de dépendances temporelles, et aider à comprendre le comportement des entités au cours du temps.

De plus, les noeuds des graphes dynamiques peuvent être entichis avec des attributs qui caractérisent chaque entité. Généralement, les attributs sont attachés aux noeuds, comme par exemple (RMS Titanic, :taille, 269.1), et donnent plus d'informations sur les entités. La dynamicité s'applique également aux attributs, et tout particulièrement lorsque l'on s'intéresse à des entités mouvantes telles que des avions, des bateaux ou des personnes, e.g. (RMS Titanic, :latitude, 40.963, 23:40 1912/04/14).

A partir de tels graphes, l'apprentissage relationnel vise à raisonner et à inférer de nouveaux liens entre les entités, ou des liens qui ont été manqués dans le passé. Les applications directes sont la complétion de graphes de connaissance et les systèmes de recommandation. Générer de nouveaux liens dans un graphe est maintenant un usage commun de l'IA, mais beaucoup de méthodes de l'état de l'art se concentrent sur les liens statiques (avec ou sans attributs) ou sur les liens dynamiques. En revanche, peu d'entre elles traitent des liens dynamiques et des attributs. Quand il n'y a que quelques relations entre des entités, l'évolution de leurs attributs peut être d'une grande aide pour les caractériser.

En gardant ceci à l'esprit, les bateaux, ports, pays et compagnies maritimes ont des interactions variées, et l'état des bateaux évolue rapidement. Une variété de données, telles que les positions, vitesses, directions ou destinations peuvent être collectées. Ces données peuvent donner des connaissances plus précises sur ce qui est en train de se passer: un bateau entre dans un port, deux navires se rencontrent, ou un motif de déplacement indique une activité de pêche. Sachant cela, un opérateur de surveillance voudrait savoir à quel moment les deux bateaux vont se rencontrer, ou l'heure d'arrivée au port d'un bateau en fonction du contexte environnant. Cela s'applique également à la piraterie, à la contrebande et à la pêche illégale. De telles situations maritimes peuvent être représentées par un graphe de connaissance dynamique avec attributs. L'objectif est d'utiliser ce graphe pour inférer de nouvelles relations entre les entités maritimes, et donc d'améliorer la Situational Awareness de l'opérateur en détectant en avance de nouveaux événements.

C'est sur cette tâche que ce concentrent les contributions de ces travaux: nous proposons une structure de graphe de connaissance dynamique avec attributs qui représente une situation en évolution, et y appliquons un système d'apprentissage profond composé de deux réseaux de neurones temporels. Ces réseaux apprennent des représentations pour chaque entité et prédisent leur comportement futur en se basant sur les informations passées. Puisque les situations maritimes impliquent des entités mouvantes, des changements environnemen-Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

V APPENDIX A. RÉSUMÉ taux, des interactions, des capteurs, de l'incertitude et des opérateurs humains, notre cas d'usage principal est le contexte maritime. Ces travaux peuvent aussi s'appliquer à l'analyse de réseaux sociaux et nous les testerons également sur un réseau de citations bien connu, DBLP, pour s'assurer qu'ils sont généralisables.

La première partie de ce manuscrit est dédiée à l'état de l'art et est divisée en trois chapitres décrivant respectivement les méthodes pour améliorer la Situational Awareness maritime, les structures de graphes de connaissance ainsi que comment créer des représentations pour ces graphes et en prédire de nouveaux liens. La deuxième partie présente nos contributions. Le premier chapitre formalise le problème de prédiction de liens dans les graphes de connaissance dynamiques avec attributs. Le second introduit notre système, Joint Evolution et comment nous l'avons construit. La troisième partie est dédiée à nos expérimentations sur des jeux de données académiques et opérationnels. La dernière partie résume le travail effectué et conclut avec des perspectives.

A.2 Introduction à la Situational Awareness maritime

La surveillance maritime est fortement liée à la Situational Awareness, produit de grands volumes de données hétérgènes et a besoin de traitements automatisés. Ce sera donc notre cas d'application principal.

La Situational Awareness maritime (SAM) est définie par l'Organisation Maritime Internationale comme étant "la compréhension de tout ce qui est associé avec l'ensemble de l'environnement maritime qui pourrait impacter la sécurité, la sûreté, l'économie ou l'environnement". Le but est d'établir une image de la situation maritime à un moment donné, en percevant les différents éléments qui agissent dans l'environnement et en comprenant leur signification, pour prendre les bonnes décisions et prévoir ce qui va arriver.

Pour être efficace, la SAM a besoin d'un flux constant de données récentes, d'opérateurs formés et ayant de la connaissance experte ainsi que d'une prise de décision efficace. Ainsi, les défis suivant doivent être relevés pour une SAM efficace:

• Fusion de données hétérogènes: pour avoir la meilleure vue d'une situation, des données de diverses sources doivent être aggregées dans une structure de données commune. Ces sources peuvent inclure des données de navigation, des données de capteurs comme la température, les courants ou des sons, des images satellite ou radar, des rapports des autorités portuaires... Les trajectoires, images, textes et sons doivent être assemblés pour créer la photographie la plus complète possible pour l'opérateur de surveillance.

• Evolution des entités: une situation maritime est un monde en constante évolution avec peu de temps entre deux événements. Un bon modèle d'évolution est donc requis pour détecter les changements.

• Détection d'événements et de menaces: un événement peut être représenté par une relation entre deux entités ou une évolution d'attributs. la définition de menace dépend des faits mais aussi du contexte: une nation peut ne pas considérer un échange entre deux navires de pêche comme une menace, mais une ONG traitant de la conservation des océans pourra y voir de la pêche illégale, et donc une menace. Faire la distinction nécessite de la connaissance experte, éventuellement sous la forme d'étiquettes sur les données. A.3 Etat de l'art

A.3.1 Graphes statiques

Cette section décrit l'état de l'art sur les graphes statiques. Pour plus de détails sur ces méthodes, voir les études de [START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF] et [START_REF] Cai | A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications[END_REF].

A.

A.3.4 Graphes dynamiques avec attributs

Jusqu'à présent nous avons examiné les techniques qui traitent des graphes statiques relationnels et attributifs ainsi que des graphes relationnels dynamiques. Cependant, les graphes dynamiques attributifs sont ceux qui correspondent le mieux à la SAM. Ce domaine est relativement nouveau et peu de modèles existent. DANE [START_REF] Li | Attributed Network Embedding for Learning in a Dynamic Environment[END_REF] est une technique de plongement qui utilise la structure du graphe (relations) et les attributs des noeuds. Le Co-embedding model for Dynamic Attributed Networks (CDAN) [START_REF] Meng | Jointly Learning Representations of Nodes and Attributes for Attributed Networks[END_REF] est similaire à DANE dans sa façon de traiter les relations et les attributs. [START_REF] Li | Streaming Link Prediction on Dynamic Attributed Networks[END_REF] proposent un modèle de streaming (SLIDE) sur les graphes dynamiques avec attributs en utilisant une matrice d'esquisse (sketching matrix) qui résume les liens et attributs observés.

A.4 Formalisation du problème

Nous formalisons maintenant le problème de prédiction de liens dans un graphe dynamique hétérogène avec attributs et présentons l'achitecture globale de notre modèle, Joint Evolution.

Les problèmes d'intérêt sont les suivants:

• étant donné un quadruplet attributif q = (e, a, v, t ) observé à l'instant t et le plongement précédent α t - e , calculer le nouveau plongement attributif de e, α t e ;

• étant donné le quadruplet relationnel q = (s, r, o, t ) observé à l'instant t et les plongements précédents ρ

A.7 Comparaison des modèles

Nous comparons Joint Evolution avec deux modèles implémentés avec la bibliothèque Stel-larGraph [Data61, 2018]. Elle propose des modèles de l'état de l'art sur étagère et peut traiter toutes sortes de graphes: homogènes, hétérogènes, graphes avec ou sans attributs, graphes avec arcs pondérés.

A.7.1 node2vec

node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF] est une méthode de plongement sur les graphes statiques et homogènes que nous avons évoquée dans l'état de l'art. Elle a l'avantage d'être très utilisée, et nous permet d'évaluer l'avantage qu'ont les méthodes dynamiques sur les méthodes statiques pour traiter des données temporelles.

A.7.2 CTDNE

CTDNE [START_REF] Nguyen | Continuous-Time Dynamic Network Embeddings[END_REF] est une méthode de plongement sur les graphes dynamiques et homogènes, utilisant des marches aléatoires temporelles. Elle nous permet de comparer Joint Evolution à une méthode dynamique.

A.8 Comparaison de scores

Nous comparons maintenant les résultats de Joint Evolution, Joint Evolution relations seules, node2vec et CTDNE.

A.8.1 datAcron

Nous rapportons les résultats de datAcron sur la Figure A.8 et la Table A.2. La meilleure méthode est ici node2vec, suivie de près par Joint Evolution sans les attributs. Cependant, toutes les autres méthodes ont des résultats similaires sur toutes les métriques sauf pour le Hits@1 qui souffre de l'instabilité causée par le faible échantillon de données. Nous remarquons aussi des résultats plus faibles sur le Hits@10 pour Joint Evolution. A.9 Bilan et perspectives A.9.1 Bilan Puisque cette thèse se déroule dans le cadre d'un programme CIFRE entre le GREYC et Airbus Defence and Space, nous avons commencé par présenter le problème industriel que cette thèse vise à résoudre. L'objectif principal est d'améliorer la Situational Awareness et de fournir une aide à la décision aux opérateurs de surveillance qui doivent parcourir de grande quantité de données hard et soft. Pour améliorer la compréhension de la situation, nous analysons les données historiques pour prédire les prochains événements et lever des alertes. Pour ce faire, nous avions besoin de créer une représentation des situations maritimes passées et présentes et avons choisi d'utiliser les graphes de connaissance. Leur capacité de description sémantique couplée à la modélisation des interactions entre entités en fait un outil adapté. Nous avons ensuite commencé par faire l'état de l'art sur deux principaux sujets: comment améliorer la Situational Awareness et comment prédire des liens dans des graphes dynamiques avec attributs. Sur le premier, nous avons trouvé beaucoup d'approches sur la génération de routes et la détection d'anomalies. Certaines traitent des événements, mais la plupart sont des moteurs de règles. L'utilisation de graphes et de prédictions d'événements pour la Situational Awareness maritime n'est donc pas un domaine très étudié et c'est sur ce point que nous positionnons nos travaux. Sur le second sujet, nous avons remarqué qu'il y a beaucoup de contributions sur les graphes statiques avec et sans attributs ainsi que sur les graphes dynamiques, mais peu sur les graphes dynamiques avec attributs. Nous nous sommes donc inspirés des méthodes de graphes dynamiques pour les adapter à l'inclusion d'attributs, en faisant l'hypothèse que les attributs peuvent améliorer les résultats de la prédiction de liens.

APPENDIX A. RÉSUMÉ Sur ce constat, nous proposons Joint Evolution, un système encodeur-décodeur en deux parties: une qui apprend des plongements à partir des changements de valeur d'attributs pour prédire les suivants, et l'autre qui apprend des plongements relationnels pour prédire de nouvelles relations en utilisant les deux types de plongements. Nous aovns conçu un pipeline de pré-traitement pour créer des séquences d'événements indépendants qui respectent l'ordre dans lequel les événements s'appliquent à une entité. Nous avons ensuite fait le choix d'utiliser des GRU pour traiter ces séquences et générer deux plongements pour chaque entité: celui sur les attributs et celui sur les relations. Une fois que le modèle est entraîné à mettre à jour les plongements qui peuvent ensuite être utilisés pour prédire le prochain événement, les plongements peuvent être mis à jour à la volée lorsque de nouveaux événements sont reçus en utilisant la partie encodeur de Joint Evolution. Quand il est nécessaire de faire une prédiction, nous utilisons uniquement la partie décodeur pour répondre à la question posée, généralement sous la forme d'un quadruplet tel que (sujet, relation, ?, timestamp). Le décodeur va ensuite trouver l'objet qui correspond le mieux au quadruplet en calculant un score pour chaque possibilité.

Nous avons testé joint Evolution sur deux jeux de données, datAcron et DBLP. dat-Acron est un ensemble d'événements et de messages AIS provenant de bateaux dans la baie de Biscay, proche de Brest, et DBLP est un réseau de citation qui relie des auteurs et des articles avec des liens d'auteurs et de co-auteurs. La principale différence entre les deux jeux de données repose dans le nombre d'événements et le type des attributs, ce qui nous donne deux contextes d'expérimentation différents. Nous avons comparé Joint Evolution avec deux autres méthodes: node2vec, une approche connue de random walk pour représenter les graphes statiques, et CTDNE, sa version dynamique. Nous avons également testé une version de Joint Evolution qui utilise seulement les relations pour évaluer l'impact des attributs sur le résultat. Au final, le modèle qui donne les meilleurs résultats est Joint Evolution sans les attributs, ce qui rejette notre hyptohèse que les attributs peuvent améliorer la prédiction de liens. Cependant, Joint Evolution a tout de même de meilleurs résultats que node2vec et CTDNE dans les deux cas et peut traiter des graphes hétérogènes en streaming. Nous espérons toujours que l'ajout d'informations peut être utile à l'apprentissage et expliquons les résultats obtenus avec plusieurs facteurs, notamment le nombre élevés de combinaisons pour les hyperparamètres et la structure des jeux de données.

A.9.2 Perspectives

Avec ces résultats, nous décrivons maintenant les limites de Joint Evolution et les travaux futurs envisagés.

A.9.2.1 Limites

Nous définissons cinq critères pour la Situational Awareness maritime: suivre l'évolution des entités, détecter les événements et menaces, pouvoir traiter un flux de données, gérer l'incertitude et rendre la sortie du modèle explicable. Malheureusement, nous n'avons pas eu le temps de travailler sur l'incertitude et l'explicabilité, qui seront traités lors de travaux futurs.

Sur la prédiction de liens, Joint Evolution est limité à la prédiction de sujets et d'objets. Nous ne pouvons pas prédire quand un événement va arriver, seulement quelle entité va interagir avec une autre à un moment donné. Nous nous sommes concentrés sur ce cas car il s'agit de la principale utilisation dans notre contexte, mais pouvoir prédire la date d'un APPENDIX A. RÉSUMÉ événement pourrait également être utile. Il nous est également impossible de prédire le type de relation: entraîner Joint Evolution à prédire un type de relation est différent car la notion de challenge n'est pas la même. Nous prenons en compte le type de relation en utilisant des paramètres spécifiques dans le réseau, mais cela ne nous donne pas la possibilité de les prédire. Pour prédire la date et le type d'un événement, un nouveau cadre d'entraînement doit être défini.

Un autre problème rencontré est la mise à jour d'une entité qui ne s'effectue que lorsqu'un événement la concernant est rencontré. Cependant, d'autres événements peuvent influer sur ces entités sans pour autant l'inclure directement. Par exemple, un conflit entre deux pays (entités c et c ′ ) ne peut pas influencer la relation entre un navire du pays c (entité v) et un navire du pays c ′ (entité v ′ ) puisque les plongements des entités v et v ′ ne sont pas mis à jour lorsque le conflit survient. Les méthodes qui prennent en compte le voisinage et le contexte dans les graphes de connaissance pourraient combler ce vide [Jin et al., 2019, Heidari andPapagelis, 2019].

La dernière limite qui mérite d'être mentionnée est la nature des attributs utilisés. Les attributs de datAcron sont des scalaires alors que DBLP utilise des vecteurs. Cela requiert une adaptation de Joint Evolution suivant le cadre. Si un jeu de données devait contenir les deux types d'attributs, il faudrait trouver un moyen des traiter les deux types, par exemple en désactivant AttrNet lorsqu'un attribut vectoriel est rencontré.

A.9.2.2 Perspectives à court terme Nos perspectives à court terme concernent principalement les jeux de données et les expérimentations. Pour évaluer dans une plus large mesure l'effet des attributs, nous souhaitons entraîner Joint Evolution sur une version plus grande de datAcron, avec plus d'événements et d'entités. Nous souhaitons également repenser la façon dont les attributs de DBLP sont créés, d'une manière plus directe et facile à apprendre. Cela pourrait commencer par une dimension réduite pour l'encodeur de titres, l'ajout des conférences dans lesquelles les articles sont publiés et l'organisation auxquelles les auteurs appartiennent (bien que cette dernière implique de gérer les attributs statiques).

Trouver un jeu de données d'évaluation pour les graphes dynamiques avec attributs n'est pas facile puisqu'il n'y a pas de jeu de données de référence dans ce domaine comme l'est MNIST2 pour l'analyse d'images. Certains graphes comme Epinions [START_REF] Richardson | Trust management for the semantic web[END_REF], Freebase ou WordNet3 sont souvent utilisés pour évaluer les graphes statiques et sont soit non-orientés soit homogènes. Les réseaux de citation tels que Citeseer [START_REF] Bhattacharya | Collective entity resolution in relational data[END_REF] et Cora [Getoor, 2005] sont soit statiques, soit sans attributs, et sont principalement utilisés pour de la classification d'articles. GDELT [START_REF] Leetaru | GDELT: Global Data on Events, Location and Tone[END_REF] et ICEWS [START_REF] Boschee | ICEWS Coded Event Data[END_REF] sont des jeux de données dynamiques connus, mais il est difficile d'y trouver des attributs dynamiques. Enron [START_REF] Klimt | The Enron Corpus: A New Dataset for Email Classification Research[END_REF] pourrait être utilisé comme DBLP puisque c'est un réseau d'échange de mails, mais il ne possède que 150 entités et est homogène. De plus, la complexité du contenu des emails pourrait ne pas aider à prédire un échange de mail entre deux employés. la création d'un jeu de données de référence pour les graphes dynamiques avec attributs serait d'une grande aide dans ce domaine.

Notre dernière perspective à court terme est de faire plus d'expériences dans le cadre actuel, notamment à propos du jeu d'hyperparamètres. Avec plus de temps, nous pourrions

Figure 1 . 1 :

 11 Figure 1.1: One day of vessel positional data in the Strait of Gibraltar. The traffic is dense and difficult to analyze.

Figure 2 . 1 :

 21 Figure 2.1: Maritime traffic density (source: Luxspace 2010)

Figure 2

 2 Figure 2.3: AIS used to display position and name of vessels -Source: AIS/wikipedia.org

Figure 2

 2 Figure 2.4: An example of AIS message [Le[START_REF] Guillarme | [END_REF]

Figure

  Figure 3.1: A RDF statement

Figure 3 . 3 :

 33 Figure 3.3: The maritime ontology from the datACRON project

  CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS

Figure 3 . 4 :

 34 Figure 3.4: Sample knowledge graph [Nickel et al., 2016]. Nodes represent entities, edge labels represent types of relations, and edges represent existing relationships

Figure 3

 3 Figure 3.5: Embeddings of book for a recommendation system (TowardsDataScience)

Figure 3

 3 Figure 3.6: Example of a knowledge graph DKG.

Figure 4

 4 Figure 4.1: Summary of main knowledge graphs applications (edges in color are the one to predict)

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4 . 2 :

 42 Figure 4.2: Simple illustrations of TransE, TransH, and TransR from[START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF]. The figures are adapted from[START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF],[START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF]

Figure 4

 4 Figure 4.3: Simple illustrations of RESCAL, DistMult, and HolE adapted from [Wang et al., 2017].

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4

 4 Figure 4.4: An illustration of the difference between a traditional KR model and KR-EAR [Lin et al., 2016]. Here, A 1 and A 2 are two attributes with respective sets of values V 1 and V 2 . In the KR model, attributes are seen as relations r a and r b while KR-EAR considers their prediction as a classification problem.

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4

 4 Figure 4.5: Illustration of the architecture of MT-KGNN [Tay et al., 2017]. Relational embeddings are used to predict attribute values.

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4

 4 Figure 4.6: The figure shows an example where the event tensor is predicted from the representations of the events in the last two time steps and from the KG representation. The dotted line indicate the transfer of observed events into the DKG[START_REF] Esteban | Predicting the Co-Evolution of Event and Knowledge Graphs[END_REF]

Figure 4 . 7 :

 47 Figure 4.7: Realization of Evolutionary Knowledge Network Architecture over a timeline[START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF]]. Here t ", t ′ and t may or may not be consecutive. t a-1 = t ′ and t b-1 = t ". t e s

  Figure 4.7: Realization of Evolutionary Knowledge Network Architecture over a timeline[START_REF] Trivedi | Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs[END_REF]. Here t ", t ′ and t may or may not be consecutive. t a-1 = t ′ and t b-1 = t ". t e s pr ev , t e o pr ev

Figure 4

 4 Figure 4.8: One step visualization of Know-Evolve computations done in Figure 4.7 after observing an event at time t [Trivedi et al., 2017]. (Best viewed in color)

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4 . 9 :

 49 Figure 4.9: The two steps of DANE[START_REF] Li | Attributed Network Embedding for Learning in a Dynamic Environment[END_REF].The first is the offline phase that leverages the adjacency matrix A for network structure and the features of nodes represented by the matrix X to generate embeddings. Then, the online phase updates the embeddings according to changes in the matrices.

Figure 4 .

 4 Figure 4.10: CDAN global architecture[START_REF] Meng | Jointly Learning Representations of Nodes and Attributes for Attributed Networks[END_REF]

  CHAPTER 4. EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 4 .

 4 Figure 4.11: SLIDE workflow[START_REF] Li | Streaming Link Prediction on Dynamic Attributed Networks[END_REF]

CHAPTER 4 .

 4 EMBEDDING AND LINK PREDICTION IN KNOWLEDGE GRAPHS

Figure 5

 5 Figure 5.2: Training, streaming and prediction phases.

CHAPTER 5 .

 5 Figure 5.3: If an attribute change occurs between t-1 and t, it must be considered when predicting an event at time t. Here, G refers to a DKG.

  Figure 5.4: Sample of the precedence graph. Each node is a quadruplet and each edge a precedence constraint to resolve before accessing the target node.

Figure 6

 6 Figure 6.1: A folded and an unfoldedRNN [LeCun et al., 2015]

  Figure 6.2: A GRU cell

  Figure 6.3: Evolution of batch size for datAcron (max size 100)

Figure 6 . 5 :

 65 Figure 6.5: Attribute learning process. Note that a 1 and a 2 can be different.

Figure 6 . 7 :

 67 Figure 6.7: Joint Evolution global architecture

  Figure 6.8: Inference with AttrEmb

Figure 9 .

 9 Figure 9.1: Joint Evolution on datAcron

CHAPTER 9 .

 9 RESULTS AND DISCUSSION Curve LR Sched. steps LR multiplier γ Grad. clipping Weight decay Blue 0

CHAPTER 9 .

 9 RESULTS AND DISCUSSION Curve LR Sched. steps LR multiplier γ Grad. clipping Weight decay Red 0

Figure 9 .

 9 Figure 9.4: Comparison of Joint Evolution (red), Joint Evolution without attributes (grey), CTDNE (orange) and node2vec (blue) for datAcron

Figure 9 .

 9 Figure 9.5: Comparison of Joint Evolution (dark blue), Joint Evolution without attributes (blue), CTDNE (red) and node2vec (orange) for DBLP

Figure A. 2 :

 2 Figure A.2: Illustrations simples de TransE, TransH, et TransR de[START_REF] Wang | Knowledge Graph Embedding: A Survey of Approaches and Applications[END_REF]. Les figures sont adaptées de[START_REF] Wang | Knowledge Graph Embedding by Translating on Hyperplanes[END_REF],[START_REF]Learning Entity and Relation Embeddings for Knowledge Graph Completion[END_REF]

Figure A. 9 :

 9 Figure A.9: Comparaison de Joint Evolution (bleu foncé), Joint Evolution sans attributs (bleu), CTDNE (rouge) et node2vec (orange) pour DBLP

Table 3

 3

	.1 shows several examples of SPO triplets. It defines several predicates for the actor
	Leonard Nimoy, the fictional character Spock and the movie Star Trek. In Figure 3.4, this
	stack of SPO triplets is put into a graph and this makes clear that these three resources are
	linked. Similarly to RDF, the edges/predicates have labels that show the nature of the link.
	subject	predicate	object
	(LeonardNimoy, profession, Actor)
	(LeonardNimoy, starredIn,	starTrek)
	(LeonardNimoy, played,	Spock)
	(Spock,	characterIn, StarTrek)
	(StarTrek,	genre,	ScienceFiction)

Table 3

 3

	.1: SPO triplets examples from

  graphs to find what is better suited to improve MSA.

	CHAPTER 3. A FORMAL FRAMEWORK AND BACKGROUND FOR GRAPHS
	Symbol(s) or abbreviation Meaning
	E, R, A, D a , T	The sets of entities, relations, attribute types, domains for
		attributes, timestamps
	e, r, a, t	An entity(or a node) from the graph, a relation type, an at-
		tribute type and a timestamp
	e s , e o , s, o	Subject and object entities and their abbreviated notations
	p R , p A	Relational and attributive triplets
	q R , q A	Relational and attributive quadruplets
	(D)KG R , (D)KG A	Sets of relational and attributive triplets (quadruplets) of a
		(dynamic) KG.
	DKG, S-DKG	Streamed DKG and sliced DKG
	τ	The number of snapshots in an S-DKG
	α e , ρ e	Relational and attributive embeddings of e in a KG
	α t e , ρ t e	Relational and attributive embeddings of e in a DKG at time
		t
	m, n	The sizes of attributive and relational embeddings (resp.)
	l	The size of the relation type embeddings

Table 3

 3

	.3: Summary of the notation

  CHAPTER 5. PROBLEM STATEMENT FOR MSA• given a relational quadruple q = (s, r, o, t ) observed at time t (relational event) and the previous embeddings ρ t - s and ρ t - o , compute the new relational embeddings ρ t s and ρ t

α t - e , compute the new attributive embedding of e, α t e ; o of s and o;

  CHAPTER 6. JOINT EVOLUTION, A NETWORK PAIR FOR LINK PREDICTION ON DAKG pr ed o = so f t max(W e so f t [ρ e 1 ⊕ ρ r ])

pr ed s = so f t max(W e so f t [r e ⊕ ρ t e 2 ]) (6.27)

Table 7 .

 7

1: Statistics for DBLP and datAcron

Table 9 .

 9 2: Results for Joint Evolution on datAcron (blue curve)

	CHAPTER 9. RESULTS AND DISCUSSION

Table 9 .

 9 3: Curves and parameters for Joint Evolution on relational datAcron

Table 9 .

 9 Curve LR Sched. steps LR multiplier γ Grad. clipping Weight decay

	Green 0.1	2	0.5	0.1	0.005
	Pink 0.01	2	0.5	0.1	0.005
	Red	0.01	1	0.8	0.1	0.005

4: Results for Joint Evolution on relational datAcron (blue curve) Figure 9.2: Joint Evolution comparison on datAcron with (blue) and without (pink) attributes CHAPTER 9. RESULTS AND DISCUSSION

Table 9 .

 9 5: Curves and parameters for Joint Evolution on DBLP -Part 1

	9.1.1.2 DBLP

Table 9 .

 9 8: Parameters for Joint Evolution on relational DBLP

Table 9 .

 9 14: Curves and parameters for node2vec on relational datAcron

Table 9 .

 9 18: Hits@ and MAR results on datAcron

		831	0.987	0.987	0.987	1	2.117
	CTDNE	0	0.9221	0.9221	0.9221	0.9221	15.3
	JE (RelNet) 0.8784	0.9662	0.9764	0.9764	0.9831	7.58
	JE	0.3504	0.748	0.939	0.9528	0.9685	16.21

Table 9 .

 9

	-3	0.0335	1,676

19: Hits@ and MAR results on DBLP

  CHAPTER 9. RESULTS AND DISCUSSIONor thousands of relations and attributes types. It would have been more interesting to compare Joint Evolution and other methods on such a graph, but dynamic attributed graph datasets are not easy to come by.

• The two datasets we used have a limited number of relation and attribute types: we only have three of each in datAcron and two of each in DBLP. A knowledge graph is the most extreme case of heterogeneous graph that exists, with possibly hundreds

  3.1.1 Modèles translationnels Dans un contexte statique, chaque noeud est représenté par un seul vecteur. Une grande variété de techniques existent, dont les modèles translationnels qui évaluent la probabilité d'un événement (sujet, relation, objet) en mesurant la distance entre les deux entités. TransE [Bordes et al., 2013] en est le représentant le plus connu et a fait l'objet de plusieurs extensions. Un résumé de ces méthodes est présenté en Figure A.2. A.3.1.2 Modèles de correspondance sémantique Les modèles de correspondance sémantique utilisent des scores pour comparer les plongements des entités et des types de relations en se basant sur leur similarité. Une illustration de ces méthodes est donnée en Figure A.3.RESCAL et ses extensions RESCAL[START_REF] Nickel | A Three-Way Model for Collective Learning on Multi-Relational Data[END_REF] a été le premier modèle de correspondance sémantique. Il affecte un plongement à chaque entité et une matrice à chaque type de relation, qui représente l'interaction entre deux entités. Le score d'un fait (sujet, relation, objet) est défini par une fonction bilinéaire. Comme TransE, RESCAL a été étendu plusieurs fois[START_REF] Nickel | Holographic Embeddings of Knowledge Graphs[END_REF], Liu et al., 2017].

  t - s et ρ t - o , calculer les nouveaux plongements relationnels ρ t s et ρ t o de s et o; • à l'instant t , prédire la valeur d'un attribut a pour une entité e à un instant t ′ ≥ t présent ou futur, c'est-à-dire, la valeur v ∈ D a telle que le quadruplet q = (e, a, v, t ′ ) a de fortes chances d'appartenir à la partie attributive du graphe; • de façon similaire, à chaque instant t , avec deux éléments de s, r, o et un instant t ′ ≥ t , prédire la valeur la plus probable pour le troisième élément. A.4.1 Le modèle idéal de graphe pour les applications maritimes Exemple de graphe à l'instant t * = t 4 APPENDIX A. RÉSUMÉ d'intelligence artificielle entre 1995 et 2000 et seulement les auteurs ayant publié au moins cinq fois. Les caractéristiques des deux jeux de données sont récapitulées en Figure A.1. A.1: Caractéristiques de DBLP et datAcron Nous testons Joint Evolution sur ces deux jeux de données. datAcron a peu d'entités et peu de relations et servira à vérifier si son grand nombre d'attributs peut compenser ce manque. DBLP est plus équilibré mais moins dynamique car à l'échelle des années et non des secondes.

	Ship A : s t o p p e d I n ; 0 . 9 8 ; [ t 4 :isCloseOf ; 0.86 ; [t4, t4] :transhipping ; 0.76 ; [t4, t4] Mediterranean Sea , t 4 ] : s t o p p e d I n ; 0 .9 5 ; [ Ship B t 3 , t 4 ] :hasShoreIn ; 1.0 ; [t-∞, t+∞] : a f fi l i a t e d T o ; 0 . 9 8 ; [ t 0 , t 4 ] Vessel type c a r g o ; 0 . 9 8 ; [ t 0 , t 4 ] c a r g o ; 0 . 9 9 ; [ t 0 , t 4 ] Longitude Country A Latitude 43.547 ; 0.94 ; [t4, t4] 3 1 .5 7 9 ; 0 .9 4 ; [ t 4 , t 4 ] datAcron 363 3 3 Figure A.4: Dataset Entités Rel types Attr types Nb Rel Country B : a f fi l i a t e d T o ; 0 . 9 7 ; [ t 0 , t 4 ] Latitude Longitude 43.549 ; 0.89 ; [t3, t4] 3 1 .5 7 3 ; 0 .8 9 ; [ t 3 , t 4 ] Nb Attr X ; 0.97 Uncertainty of X Entities Attributes :isIn Relation type [ti , t j ] Interval of validity → Relation → Attribute value → Predicted 764 4,596,204 DBLP 6,147 2 2 261,324 139,152

Table

Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

https://ec.europa.eu/futurium/en/ai-alliance-consultation

http://blog.exactearth.com/blog/bid/275363/comparing-satellite-ais-tolrit Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

< sub j ec t > has a property < pr ed i c at e >, whose value is < ob j ec t >.

https://www.orientdb.org/

https://dblp.org/ Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

P(v|e, a, X) = exp(h(e,a,v))v∈D a exp(h(e,a, v))Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

We omit r since the graph is homogeneous

As opposed to tasks where we would like to retrieve what the situation was likely to be at some point in the past.

That is, if (v x , v y ), (v y , v z ) ∈ E, then (v x , v z ) ∈ E despite meeting the requirements (direct successor(s) condition).

https://towardsdatascience.com/understanding-gru-networks-2ef37df6c9beCopyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

https://www.aminer.cn/citation

https://pytorch.org/ Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.CHAPTER 10. SUMMARY AND PERSPECTIVES

http://yann.lecun.com/exdb/mnist/

https://everest.hds.utc.fr/doku.php?id=en:transeCopyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

https://www.aminer.cn/citation Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.XV

http://yann.lecun.com/exdb/mnist/

https://everest.hds.utc.fr/doku.php?id=en:transe

Remerciements

CHAPTER 7 Datasets

Our work focuses on Maritime Situational Awareness and as such, we test JointEvolution on a maritime dataset. This experiment is a proof of concept on real data, which aims to demonstrate the effectiveness of involving dynamic attributes in the task of link prediction. However, to test JointEvolution in a more academic context and make a better comparison with other state-of-the-art techniques, we try JointEvolution against DBLP, a citation network frequently used in graph analysis.

datAcron

The first dataset we use contains maritime data, the objective being to predict future interactions between vessels. As a basis, we use the dataset given by [START_REF] Ray | Heterogeneous integrated dataset for Maritime Intelligence, surveillance, and reconnaissance[END_REF] and part of the datAcron project, which contains ship information collected through AIS. The dataset extends over six months, from October 1st, 2015 to March 31st, 2016, and covers the Celtic sea, the North Atlantic Ocean, the English Channel and the Bay of Biscay (France). Along with this dataset, we use the Composite Maritime Events dataset [START_REF] Pitsikalis | Composite maritime events[END_REF], extracted from the AIS of [START_REF] Ray | Heterogeneous integrated dataset for Maritime Intelligence, surveillance, and reconnaissance[END_REF] using a rule-based engine.

Dataset breakdown

Within all the available data in the dataset, we are particularly interested in the AIS positions and the composite events. There are 3,970,370 events, but only 4,405 events involving two entities: :pilotBoarding (730), :rendezVous (3,548) and :tugging (127). The others are selfcentered events, e.g. when a vessel makes a sudden change of speed or when it stops. The pilot boarding event occurs when a vessel enters a port: it is not its pilot that makes the maneuver but a pilot from the destination port that boards the vessel. A rendez-vous between two vessels is a meeting, usually for transshipping, and tugging is when a tug boat is towing another vessel.

The dataset contains 19,035,630 AIS messages which refer to 5.055 vessels. The vessels are the only type of entity under study, and they are identified by their MMSI. From this identifier, it is straightforward to map the vessels to their attributes using the AIS values. We only keep the latitude, the longitude, the speed and the timestamp. The course is left out CHAPTER 7. DATASETS

• Co-authorship id_author: [(coauthor_id, year), (coauthor_id, year),...]

• Write article id_author: [(id_article, year), (id_article, year),...]

• Cite article id_author: [(id_ref, year), (id_ref, year),...]

• Cite author id_author: [(id_author, year), (id_author, year),...]

First version

In our first version of the DBLP dataset, we take the subset between 1995 and 2011 restricted to authors with at least three publications.

Relations

We consider three types of relations: (author, :cite, author, t) that happens when an author cites the article of another author ; (author, :citedBy, author, t) when an author is cited by another author ; and (author, :coauthor, author, t) when two authors write the same paper.

Attributes

We consider three kinds of attribute events. The first one is the number of citations of an author, (author, : nbCi t at i ons, x). For each year where the author is cited at least once, we compute the total number of citations at time t. Note that this number of citations is the number of articles that cite the author, not the number of authors unlike the : ci t ed By relational event. The second one is the number of publications of the author, (author, : nbPubl i , x, t). It is incremented each time the author writes a new paper. Finally we have the h_i nd ex of the author, (author, : h-i nd ex, x, t), which is computed each time the author is cited in an article or has published a new paper. These attributes are chosen because they reflect the authors' characteristics regarding publication.

Overview and discussion

With the selected relations and attributes in the selected timeframe, we obtain the following numbers of edges: MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 542.1 2.2322e-3 0.035 0.061 0.1537 0.4379 MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 15.3 0 0.9221 0.9221 0.9221 0.9221 MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 822.6 7.5e-4 0.0339 0.0826 0.1545 0.3061

DBLP

The training on DBLP is much longer due to the larger number of relational quadruplets (two hours per epochs). Still, the optimum is also reached in a few epochs. We report the curves and parameters in Table 9.12. We first notice that the three curves end up with the same result despite some differences in the evolution of their learning rate and in the weight decay. The weight decay does not seem to have much effect given the similarity between the red and pink curves between which it is the only difference. More frequent learning rate reductions stabilize the learning as observed on the blue curve: we do not see the same oscillations with the two others. For these reasons, we retain the blue curve and report its results in Table 9.13.

Summary

The only parameter CTDNE seems sensitive to is the learning rate. Otherwise, all other settings give the same results. This may be because we only train the decoder part from pre-trained embeddings: there are fewer parameters to train for link prediction.

node2vec

At last, we train a decoder on node2vec embeddings. With this experiment, we have a reference for static methods. MAR Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 1676 0 1.145e-4 7.252e-4 1.603e-3 0.0335 for blue, dark blue and orange curves. While Hits@100, MAR and loss behave as expected, the other four are not supposed to drop. This leads to poor results on these metrics, but we still focus on these three settings since grey and pink have an awful MAR.

Out of these three, we exclude the blue one for having a higher loss, and orange and dark blue are basically the same curve going at different speeds (directly linked to their learning rate). We thus stick with orange as best result since it learns faster, and we report the results in Table 9.17.

Summary

node2vec is much more sensitive to parameters than CTDNE, mainly to the weight decay. It captures very well the interactions in datAcron but fails to do so on DBLP. This difference may come from the low number of samples in datAcron that makes a static method still efficient since there are not a lot of changes. Regarding DBLP, the large number of entities and relations over time makes the task more difficult for a static model.

Score comparison

We now compare all four methods on both datasets to evaluate both the results of Joint Evolution over the two other methods and the effect of the addition of attributes on the link Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

Conclusion APPENDIX A Résumé

A.1 Contexte

Comment surveiller efficacement les activités maritimes et anticiper les comportements anormaux des bateaux qui naviguent à travers le monde contre vents et marées? C'est la question à laquelle j'apporte une réponse dans ce manuscrit qui parle aussi bien de données opérationnelles et de séries temporelles que de graphes de connaissance et de machine learning. Il présente également comment utiliser les données transmises par les bateaux afin de prédire leurs interactions, présentes ou futures.

Ces travaux s'effectuent dans le cadre d'une collaboration CIFRE entre Airbus Defence and Space (Elancourt, France) et le laboratoire GREYC de l'Université de Caen Normandie. Ce dispositif est géré par l'Agence Nationale de la Recherche et de la Technologie (ANRT), qui soutient les entreprises françaises souhaitant embaucher un doctorant et créer une collaboration de recherche avec un laboratoire public. Ceci a pour but de faciliter les échanges entre les mondes industriel et académique.

Le sujet principal de ces travaux est la représentation de l'évolution de situations afin d'extraire de nouvelles informations. Pouvoir représenter une situation et sa dynamique est très intéressant pour les opérateurs de surveillance et de renseignement, car ils ont besoin d'en savoir le plus possible sur une zone ou une personne d'intérêt. Cette connaissance d'une situation est également appelée Situational Awareness, et est un élément critique dans de nombreux domaines, tels que la protection de la vie humaine et de la propriété, le respect de la loi, l'aviation, le contrôle du trafic aérien, la navigation, la santé, les urgences ainsi que les opérations militaires. Trois piliers sont nécessaires à son efficacité: la perception de l'environnement, la comprehension de la situation et la prédiction des états futurs.

Le premier pilier se concentre sur la collecte de données hétérogènes concernant une zone ou des entités d'intérêt. Elles peuvent être des données "hard" venant de capteurs physiques (quantitatives, Figure A.1) ou des données "soft", i.e. des données linguistiques produites par des humains (qualitatives). Le second pilier utilise ces données pour en extraire des informations sur la situation étudiée et en connaître tous les tenants et aboutissants. Enfin, le troisième utilise ce qui a été compris de la situation actuelle pour prédire ce qui pourrait arriver ensuite. Pouvoir inférer la suite des événements à partir des connaissances courantes III APPENDIX A. RÉSUMÉ procure une capacité de prévision aux opérateurs, qui pourront alors mieux anticiper les problèmes et menaces.

Grâce à la Situational Awareness, un opérateur de surveillance peut analyser la situation pour mieux la comprendre. Durant cette analyse, il pourra établir des liens entre les entitiés représentant leurs interactions (par exemple, des liens d'affiliation, de commandement, de subordination ou de conflit) mais aussi créer de nouvelles entités. Actuellement, cette analyse est très peu automatisée et ne couvre qu'une petite partie des données disponibles. Avec l'augmentation du nombre d'entités à surveiller (personnes, véhicules, appareils...) et le déploiement de plus en plus de capteurs qui produisent massivement des données, il est devenu presque impossible pour un opérateur d'analyser et d'évaluer manuellement une situation. Il y a ici un besoin d'automatisation du processus de surveillance, pour que les opérateurs et experts n'aient qu'à regarder les événements d'intérêt proposés par un système automatisé, plutôt que de parcourir l'ensemble des données à la main. Pour ce faire, la représentation de la connaissance est de la plus grande importance et nécessite de relever plusieurs défis. La structure de données doit être dynamique pour suivre l'évolution de la situation, contenir les attributs et caractéristiques de chaque entité et représenter leurs interactions avec leur environnement. Puisqu'il y a toujours un humain dans la boucle, l'information doit être facile à visualiser, comprendre et parcourir. De plus, toute décision prise par un système automatisé doit être interprétable ou explicable pour avoir la confiance de ses utilisateurs, i.e. l'opérateur qui l'utilise doit connaître les raisons de sa décision. Dans un contexte de défense et de surveillance, il n'est pas possible pour les décideurs d'accepter et d'utiliser les résultats d'un tel système s'il n'est pas fiable et expliqué. De plus, l'incertitude est présente à plusieurs niveaux: les prédictions ont un degré de fiabilité, et les données elles-mêmes sont sujettes à des erreurs: un rapport peut contenir une faute de frappe, les capteurs ont une portée et une précision, ou des collisions de messages peuvent perturber leur réception par des satellites. Enfin, la surveillance d'une situation donnée doit être continue et les prédictions faisables à n'importe quel moment: la perception de la situ-APPENDIX A. RÉSUMÉ

• Streaming: la SAM a besoin d'une surveillance constante des zones maritimes, ce qui veut dire que le modèle de surveillance doit être capable de traiter un flux continu de données.

• Incertitude: les données maritimes proviennent souvent de la fusion de données capteurs hard (capteurs) et soft (sites web, renseignement). Cependant, cette donnée est rarement précise à 100 %: l'incertitude doit être prise en compte pour prendre une décision.

• Explicabilité: les modèles d'IA sont souvent des boîtes noires, rendant difficile l'explicitation des causes d'une alerte. Cependant, un opérateur a besoin d'une justification pour sa décision. Puisque les opérateurs ne font pas complètement confiance aux systèmes d'IA, l'explicabilité des modèles d'aide à la décision est un critère déterminant pour la SAM [START_REF] Adadi | Peeking inside the blackbox: A survey on explainable artificial intelligence (xai)[END_REF].

Lorsque l'on regarde le trafic maritime dans sa globalité, les événements dangereux ou illégaux sont considérés comme rares et inhabituels et correspondent donc à la définition d'anomalie. Les détecter n'est pas aisé car il y a beaucoup de données dont il faut extraire les éléments importants, d'où le besoin d'un outil de détection automatique pour les événements anormaux. Voici une liste non-exhaustive des événements pouvant être détectés à partir des données de positions et de contexte:

• Navire endommagé ou immobilisé;

• Perte de cargaison;

• Pollution marine;

• Des tempêtes ou toute météo qui pourrait ralentir le voyage;

• Une collision;

• Echange de marchandises/d'équipage;

• Direction ou vitesse inhabituelle;

• Pêche dans une zone protégée;

• ...

Objectif de la thèse

Ces travaux se concentrent sur la détection et la prédiction d'événements: notre objectif est de créer un modèle qui apprend le comportement des navires en utilisant des événements étiquetés entre des entités de la situation (navires, ports, compagnies maritimes...) et qui détecte automatiquement les causes de ces évenements afin de trouver des patterns similaires ailleurs dans les données. Au lieu d'indiquer au modèle comment trouver les événements, nous lui donnons des événements, de l'AIS et des informations sur l'environnement pour qu'il puisse apprendre les causes par lui-même.

APPENDIX A. RÉSUMÉ

A.3.1.3 Correspondance par réseaux de neurones

Plusieurs modèles utilisent les réseaux de neurones pour calculer la correspondance entre des entités: NTN [START_REF] Socher | Reasoning With Neural Tensor Networks for Knowledge Base Completion[END_REF], MLP [START_REF] Dong | Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion[END_REF], RDFDNN [START_REF] Murata | Predicting Relations Between RDF Entities by Deep Neural Network[END_REF], Graph Convolutional Network (GCN) [START_REF] Kipf | Semi-Supervised Classification with Graph Convolutional Networks[END_REF].

A.3.1.4 Marches à travers le graphe

Les méthodes suivantes utilisent des marches aléatoires pour générer les caractéristiques des noeuds. Ces techniques sont moins centrées sur les entités et explorent également le voisinage i.e. le contexte. Les modèles les plus représentatifs sont node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF], GraphSAGE [START_REF] Hamilton | Inductive Representation Learning on Large Graphs[END_REF] et LINE [START_REF] Tang | LINE: Large-scale Information Network Embedding[END_REF]

A.3.2 Graphes avec attributs

Dans le cadre de la SAM, nous avons besoin d'utiliser les attributs des entités tels que la position ou la vitesse pour inférer de nouvelles relations. Puisque les graphes avec attributs sont plus adaptés à nos besoins, voici comment ils sont traités dans la littérature.

L'approche de Lin et al. [START_REF] Lin | Knowledge Representation Learning with Entities[END_REF] peut prédire les valeurs d'attributs discrets et trouver des corrélations entre eux. En revanche, les attributs ne sont pas inclus lors de l'apprentissage des relations, et les relations ne sont pas incluses dans l'apprentissage des attributs. Tay et al. [START_REF] Tay | Multi-Task Neural Network for Non-discrete Attribute Prediction in Knowledge Graphs[END_REF] proposent un modèle qui apprend de manière jointe les relations et les attributs grâce à un réseau de neurones, et prédit des valeurs continues d'attributs avec une tâche de régression. attri2vec [START_REF] Zhang | Attributed network embedding via subspace discovery[END_REF] étend le modèle Deepwalk [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF] (proche de node2vec [START_REF] Grover | node2vec: Scalable Feature Learning for Networks[END_REF]) pour capturer la structure du graphe ainsi que le contenu des noeuds. Co-embedding Attributed Networks (CAN) [START_REF] Meng | Co-Embedding Attributed Networks[END_REF] produit un plongement pour chaque événement relationnel et attributif en utilisant la moyenne et la variance d'une distribution gaussienne grâce à un autoencodeur variationnel. Cependant, aucun de ces modèles ne peut traiter les données temporelles.

APPENDIX A. RÉSUMÉ

Pour répondre aux défis posés par la SAM, nous proposons la structure de graphe illutrée en Figure A.4. Les événements en rouge représentent la partie attributive et les autres la partie relationnelle. Le navire A et le navire B sont de différents pays et se déplacent dans la mer Méditerranée. Ils ont des attributs statiques (type de bateau) qui les définissent comme des cargos ainsi que des attributs dynamiques (latitude et longitude) qui révèlent leurs positions. Avant t * , les deux navires se déplaçaient dans la mer Méditerranée et avaient différentes positions mais maintenant (à t * ), ils sont à l'arrêt et proches l'un de l'autre. Une prédiction de lien possible est que les deux bateaux sont en train d'effectuer un échange de marchandises. Notez que la relation :stoppedIn peut être déduite de l'attribut speed (vitesse) qui est alors proche de 0, non représenté ici pour plus de clarté.

Si les relations telle que le pays A ayant une côte sur la mer Méditerranée est sûre à 100 %, certaines sont moins évidentes: la position d'un navire est seulement sûre à 89 % car le signal a été capté par un satellite dans une zone avec un trafic important. De plus, l'incertitude des relations prédites (e.g. l'échange de marchandises) dépend également de l'incertitude des informations à la source. Enfin, pour prédire l'échange à temps, le modèle doit être mis à jour avec les causes de l'événement dès que possible, d'où le besoin d'une prédiction de liens en flux constant. Idéalement, le modèle doit pouvoir gérer les données discrètes (port d'arrivée, drapeau...) et les données continues (positions, date, vitesse du vent...). L'entrée du modèle est composée d'événements relationnels et attributifs arrivant dans l'ordre de leur timestamp. Chaque réseau est composé d'un encodeur et d'un décodeur. L'encodeur met à jour le plongement de chaque entité impliquée dans l'événement traité afin de saisir le comportement de ces entités en fonction de leurs événements passés. Quand une prédiction est demandée, ces plongements sont donnés au décodeur qui va utiliser ces informations pour prédire la prochaine valeur d'un attribut (AttrNet) ou le sujet (ou l'objet) d'un événement (RelNet).

A.5 Joint Evolution

A.5.2 AttrNet

Le réseau AttrNet encode les événements attributifs pour faire des prédictions sur les valeurs des attributs.

A.5.2.1 Encodeur

Lorsqu'un nouvel événement attributif q = (e, a, v, t ) est observé, l'encodeur d'AttrEmb prend en entrée q ainsi que le plongement actuel de e, α - e , et produit un nouveau plongement α t e . Pour prendre en compte la séquence d'événements sur les attributs, nous utilisons un réseau de neurones GRU comme encodeur [START_REF] Cho | On the Properties of Neural Machine Translation: Encoder-Decoder Approaches[END_REF]. Etant donné q = (e, a, v, t ) et

Autrement dit, le nouveau plongement pour e est obtenu en fonction du décalage temporel (avec un paramètre w t partagé par tous les attributs), de la nouvelle valeur observée (avec un paramètre spécifique au type d'attribut) et du plongement précédent (également avec un paramètre lié au type d'attribut). La Figure A.6 illustre les Equations A.1 à A.4.

Ici, z t est appelé l'update gate, r t la reset gate, h ′ t la mémoire courante, et σ est la fonction sigmoïde; v ∈ D a est la valeur scalaire de l'attribut a, ⊙ est le produit d'Hadamard, et σ et z t → 1 -z t sont appliqués coordonnée par coordonnée.

Les vecteurs w a z , w a r , w a t ∈ R m sont des paramètres du réseau qui dépendent du type d'attribut. Les matrices U z , U r , U t ∈ R m×m sont des paramètres qui indiquent quelle partie du plongement doit être gardée dans les gates. Enfin, b z ∈ R m est la couche de biais de l'update gate.

A.5.2.2 Décodeur

Le décodeur d'AttNet est défini comme suit:

XII

Copyright ©2021 -AIRBUS DEFENCE AND SPACE SAS -Université de Caen Normandie -All rights reserved.

APPENDIX A. RÉSUMÉ Ici, w t ∈ R est un paramètre qui module la prédiction suivant le temps écoulé depuis le dernier changement de valeur, w a ∈ R m est un paramètre spécifique au type d'attribut et b a ∈ R est le biais.

A.5.3 RelNet

A.5.3.1 Encodeur

Lorsqu'un nouvel événement q = (s, r, o, t ) est observé, l'encodeur de RelEmb prend en entrée q et les plongements courants de s et o, ρ

(A.9)

Décodeur

Nous calculons le score relationnel bilinéaire g s ′ ,o ′ r (Equation A.12) du plongement qui vient d'être mis à jour. Nous utilisons pour cela un challenge q ′ = (s ′ , r ′ , o ′ , t ′ ) qui implique une des deux entités de q. n+m) est une matrice spécifique au type de relation apprise durant l'entraînement. Ce score est ensuite utilisé pour calculer une fonction conditionnelle d'intensité λ (Equation A.13), qui sera utilisée pour classer les événements possibles durant la phase de prédiction (plus λ est élevé, plus le quadruplet (s, r, o, t ) est probable).

Ceci est une adaptation de la fonction softplus décrite par [START_REF] Trivedi | DyRep: Learning Representations over Dynamic Graphs[END_REF] et [START_REF] Mei | The neural hawkes process: a neurally self-modulating multivariate point process[END_REF]. En utilisant la représentation de l'événement courant, Joint Evolution va ainsi apprendre quel événement prédire ensuite. Le delta de temps (tt ′ ) illustre le processus de Rayleigh utilisé dans Know-Evolve: plus le temps passe sans qu'un événement ne se produise, plus il y a de chances qu'il arrive.

A.5.4 Utilisation

A.5.4.1 Mise à jour Durant l'entraînement, les réseaux apprennent comment construire des plongements qui peuvent être utilisés pour faire des prédictions. Une fois entraînés, tous les paramètres sont gelés, mais les plongements sont toujours mis à jour au fur et à mesure que les événements arrivent. En utilisant les plongements des entités d'un événement (à l'instant t ) dans l'encodeur, la connaissance obtenue est directement incluse dans ρ e et α e pour que le modèle ait toutes les informations nécessaires pour faire une prédiction à un moment t ′ ≥ t . Le modèle peut ainsi recevoir un flux de données, mettre continuellement à jour les plongements et être prêt à prédire les prochains événements à n'importe quel moment.

A.5.4.2 Prédiction

La prédiction de la valeur suivante d'un attribut est faite directement en sortie d'AttrNet: c'est une valeur scalaire calculée en utilisant α e (Equation A.6). Pour prédire le prochain événement relationnel pour une entité, nous fixons le moment ainsi que deux de ses trois composants, e.g.

A.5.5 Fonctions de coût

La fonction de coût pour AttrNet est l'erreur quadratique moyenne, commune pour les tâches de régression:

Pour RelNet, nous cherchons à avoir la plus grande intensité conditionnelle pour le challenge comparé à tous les événements possibles. Nous calculons donc l'intensité conditionnelle de tous les événements "négatifs" (qui ne sont pas arrivés) et en gardons la valeur maximale. Nous cherchons ensuite à minimiser la différence entre cette valeur et l'intensité conditionnelle du challenge, i.e. nous faisons en sorte que celle du challenge soit plus élevée que toutes celles des événements négatifs (Equation A.15.

A.6 Expérimentations

Nos travaux se concentrent sur la SAM et nous testons donc Joint Evolution sur un jeu de données maritimes. Cette expérimentation est une preuve de concept sur des données réelles qui vise à démontrer l'efficacité des attributs dynamiques dans la prédiction de liens. Cependant, pour tester Joint Evolution dans un contexte plus académique et pouvoir le comparer à d'autres méthodes, nous l'appliquons également à DBLP, un graphe de citations fréquemment utilisé en analyse de graphes.

A.6.1 datAcron

Ce premier jeu de données contient des données maritimes, l'objectif étant de prédire les futures interactions entre navires. Nous utilisons le jeu de données fourni par [START_REF] Ray | Heterogeneous integrated dataset for Maritime Intelligence, surveillance, and reconnaissance[END_REF] Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 MAR node2vec . CTDNE est proche de Joint Evolution sur le Hits@10 et le Hits@30 et le surpasse même sur le Hits@20, mais le grand écart sur le MAR en faveur de Joint Evolution le rend plus efficace. node2vec, auparavant capable de tenir tête aux autres méthodes, échoue complètement à prédire des liens sur DBLP.

Hits@1 Hits@10 Hits@20 Hits@30 Hits@100 MAR node2vec 0

1.145e -4 7.252e -4 1.603e

XVII

APPENDIX A. RÉSUMÉ améliorer le choix des hyperparamètres et trouver le meilleur ensemble pour chaque méthode. Nous pourrions aussi évaluer avec plus de détail l'efficacité d'AttrNet, qui n'a pas été beaucoup testé en dehors de l'optimisation de sa fonction d'erreur.

A.9.2.3 Perspectives à long terme Sur le plus long terme, l'objectif est de combler le vide laissé par l'incertitude et l'explicabilité dans les critères de Situational Awareness. Notre piste principale sur l'incertitude est l'utilisation des Markov Logic Networks et des Probabilistic Soft Logics [Chekol et al., 2017,Chekol and[START_REF] Chekol | [END_REF]. Pour l'explicabilité, l'étude d 'Adadi et Berrade [Adadi and Berrada, 2018] est une base solide pour trouver des solutions adaptées à notre cas.

Un autre ajout envisagé pour Joint Evolution est une vraie description sémantique des entités et de leurs interactions. Nous avons des types de relations, mais nous n'avons aucun moyen d'indiquer au modèle qu'une entité est un navire ou un port, ce qui peut jouer un rôle important dans le processus d'apprentissage. Savoir à l'avance le type d'une entité, les attributs qu'elle peut avoir et quels interactions sont possibles devrait rendre la création de nouveaux liens plus précise. Il faudrait alors trouver un moyen d'inclure des ontologies complètes dans le modèle pour mettre leurs capacités descriptives au bénéfice de l'apprentissage.