Developing a Spatial-Temporal Contextual and Semantic Trajectory Clustering Framework

This paper reports on ongoing research investigating more expressive approaches to spatial-temporal trajectory clustering. Spatial-temporal data is increasingly becoming universal as a result of widespread use of GPS and mobile devices, which makes mining and predictive analyses based on trajectories a critical activity in many domains. Trajectory analysis methods based on clustering techniques heavily often rely on a similarity definition to properly provide insights. However, although trajectories are currently described in terms of its two dimensions (space and time), their representation is limited in that it is not expressive enough to capture, in a combined way, the structure of space and time as well as the contextual and semantic trajectory properties. Moreover, the massive amounts of available trajectory data make trajectory mining and analyses very challenging. In this paper, we briefly discuss (i) an improved trajectory representation that takes into consideration space-time structures, context and semantic properties of trajectories; (ii) new forms of relations between the dimensions of a pair of trajectories; and (iii) big data approaches that can be used to develop a novel spatial-temporal clustering framework.

I. INTRODUCTION
A spatial-temporal trajectory is defined as the recording of the position and timestamp of an object at specific times [1]. The widespread use of the GPS devices (e.g. in cars and mobile phones) has enabled the generation of vast amounts of spatial-temporal data about the movement of people, goods, and objects. Trajectory analysis then emerge as the research area that focuses on manipulating, processing, and analyzing trajectory data to discover valuable hidden information, such as patterns and novel insights. Today, trajectory analysis is used, for example, to recommend new routes to travellers [2], or faster ways to deliver goods [3].
It is important to distinguish the dimensions that make up trajectory data [4]. One of these dimensions is the spatial dimension, which relates to the location of objects in the space, such as their latitude and longitude. Another dimension is the temporal dimension, which describes the rate at which the spatial information about the object changes as it moves.
One of the ways to analyze trajectories is using clustering techniques. Trajectory clustering [5] is an unsupervised method whose goal is to group trajectories based on their dimensions (spatial, temporal) and reveal patterns, commonalities, or ease predictions. Clustering algorithms rely on the definition of similarity between elements, or its inverse: a distance function [6]. In terms of trajectories, similarities may be described based on their dimensions. Similarities based on the spatial dimension take into consideration the length and the path followed by a trajectory [7], whereas similarities based on the temporal dimension take into consideration the relationship between the time duration of the trajectories being compared (e.g. whether they overlap) [8].
Although some similarity definitions have been proposed in the literature, their descriptions still remain limited. The structure space and time as well as contextual and semantic properties can be used to improve the expressiveness of trajectory definitions and generate new similarity metrics for trajectory clustering techniques [9]. Similarity definitions can also be based on trajectory context and semantic of movement [10], which takes into consideration the surrounding elements and reasons related to the moving object (e.g. number of passengers in a vehicle, or going to work). Therefore, context and semantics can be used as additional trajectory dimensions. Moreover, there is a need for implementation framekworks to process the large amounts of data produced in the trajectory domain [11].
In summary, three problems are identified that guide our ongoing research work. They are the lack of: (i) similarity metrics that take into account improved representations of trajectory data, including its contextual and semantic dimensions; (ii) trajectory clustering techniques that benefit from improved similarity relations in each trajectory dimension; (iii) and big data frameworks that supports trajectory analysis using new, improved, and more expressive similarity functions and clustering techniques.
The overarching goal of the research is to improve trajectory similarity models by (i) taking into consideration spatial, temporal, contextual, and semantics information; (ii) creating new ways to enrich clustering techniques; and (iii) developing a novel supporting framework for new trajectory analysis clustering techniques, applications, and evaluation studies. In this way, Data and Machine Learning scientists will be provided new ways of comparing trajectories, calculating outliers, predictions, and drawing data analysis conclusions using clustering techniques. This paper is strucutred as the following. Section II shows background research on the areas of trajectory definition, similarity, clustering, and big data support. Section III discusses the main challenges that this research is addressing. Section IV describes our proposed approach to solve the problems previously described. Lastly, Section V presents our final comments and conclusions.

II. BACKGROUND
This section presents current approaches to trajectory description, similarity definition, and big data framework development, which are the main research areas ongoing research is inserted. Each of the areas has limitations, which are discussed in section III.

A. Trajectories and Spatial-Temporal Data
Spatial-temporal data relates to two dimensions of application data in applications: the spatial and the temporal dimensions. The data describes the spatial properties of objects as a function of time [12]. The occurrence of tornadoes in a country or people walking in a mall are examples of spatialtemporal data. More formally, spatial-temporal data describes the location x of an element at a particular time t.
where x ∈ R n in a theoretical multidimensional world, but is usually described in terms of latitude, longitude, and altitude (or simply x, y, and z) in the R 3 . Some researchers [13] describe the spatial and the temporal representation of this type of data and the following paragraphs review them.
In the spatial representation, objects may be points, lines, regions, or polygons, depending on the dimension that they are represented (zero, one, two, or three, respectively). Although objects in higher dimensions can be represented, their applicability in the real world are limited. Another representation of spatial-temporal objects is based on their edges (end points) or the points in their interior (such as pixels in a screen). The former is the vector representation while the latter is the raster representation.
The spatial representation of the relationship between objects can be divided into topological, distance, and direction, and measurement relations. Topological relations are usually based on objects' boundaries, interior, or complements. Topological relations are, assuming that A and B are spatialtemporal

objects, A disjoint B, A meets B, A overlaps B, A equals B, A covers B, A covered by B, A contains B, A inside B.
Distance relations consider two points of comparison and calculates the distance between two objects. It heavily depends on the definition of the points of comparison (e.g. edges, centroids). Direction relations assume that an object A is in a virtual coordinate system and assess where all, the majority, or a specific point of comparison of object B is in relation to object A. Examples of direction relations are A to the north of B, A below B, or A to the right B. Measurement relations take into consideration properties of objects (e.g. length, perimeter, distance) to specify comparisons such as A bigger than B and A longer than B.
The temporal representation of data describes the time in which objects exist. Time may be represented as a point or an interval. Another classification of the time representation deals with the way it is associated with the spatial-temporal objects. Some objects have a location that does not change over time (e.g. occurrence of volcano eruptions). This time representation is referred to as time snapshots. Updated snapshots are temporal descriptions of objects that move over time, but scientists and experts do not keep a history of this movement, only having access to the most recent information. Lastly, when the history of an object's movement is being captured and stored for analysis, then this time description is referred to as a time series. Some properties of time representations that are considered when representing time are its granularity (dense or coarse), density (discrete or continuous) or the representation of the lifespan of an object (whether a discrete time representation or by the temporal difference between its start and end times). The relationship between two time representations are described in [14] and includes, assuming X and Y are time intervals with length, such that 0 ≤ length < ∞, X before Y, X equal Y, X meets Y, X overlaps Y, X during Y, X starts Y, X finishes Y.
A trajectory is, in simple terms, the sequence of positions that a moving spatial-temporal object has taken during a specific time [15]. A trajectory is modeled as a finite discrete sequence of snapshots alongside the spatial-temporal object's position in space, as in and m is the length of the trajectory. Although objects can move in an arbitrary dimension, it is common to limit the number of spatial dimensions to three for real world applications. Moreover, details about the shape of the spatial-temporal object are omitted in this definition, but certainly relevant for some domains [16].
The inclusion of semantic data into trajectories has been investigated [4], with reasonings about the goals of the movement, or the semantic meaning of stops. However, this is an area of ongoing reasearch and more studies about data representation and relationship are required. In addition, trajectory data is volumous and as a consequence rich for analyses. Some approaches described in the literature provide various methods in this domain were provided [5]. These methods can be mainly classified into clustering or classification methods. They are usually applied to perform pattern mining, outlier detection, or prediction.

B. Similarity and Clustering
Trajectory clustering techniques are used to analyze trajectory data, trying to group them based on their similarities or differences in spatial and temporal dimensions [13]. According to [7], clustering techniques can be hierarchical, partitionbased, density-based, and grid-based. Hierarchical clustering methods start with a basic set of clusters and merges or splits them based on a stopping criteria. The result is a tree of clusters, called a dendogram. A popular hierarchical clustering algorithm is the balanced iterative reducing and clustering using hierarchies (BIRCH). Partition-based clustering methods start with each element as a single cluster and iteratively merge or reallocate them until a stopping criteria is met. Algorithms such as the K-Means or K-Medoids are partitionbased methods. Density-based clustering methods examine the density of the data points and treat clusters as dense regions of the data space. A very popular algorithm is the density-based spatial clustering of applications with noise (DBSCAN). Gridbased clustering algorithms divides the data space into a finite number of cells before inspecting the density of data in each cell. Denser cells are connected to form clusters. Grid-based clustering algorithms are primarily developed for analyzing large spatial datasets. A well-known algorithm is the clustering in quest (CLIQUE).
A fundamental attribute of clustering algorithms is the similarity function (or its inverse, the distance function) that they use to assess data elements. Some studies [17], [6] review the most common similarity metrics used with trajectories. Among the popular metrics are the Euclidean distance, based on the spatial distance between trajectories; the Fréchet metric, based on the minimal spatial distance between any points in the two trajectories being compared; the dynamic time warping (DTW), where trajectories are undergo a nonlinear transformation before comparison with another distance function; the longest common subsequence (LCSS), in which trajectories are stretched while other points remain unmatched in an attempt to provide an accurate similarity analysis; and the edit distance, which counts the minimum number of edits required to make the two trajectories equivalent.
Some researchers [10] have investigated ways to calculate the similarity between the semantic trajectories, in which inferences about the nature of the trajectory are made. However, the research in this field is still in the initial stages and many challenges still need to be addressed.

C. Big Data Processing Support
Big Data relates to the phenomenon observed in the last decades, in which current digital technologies produce increasingly larger amounts of generated data, and as a consequence, changed the way data is captured, stored, analyzed, and visualized [18]. This area is usually described in terms of three V's: Volume (amount of data), Variety (diverse structure of the data) and Velocity (the speed of data). Some of the wellknown Big Data support tools include Spark, YARN, Hadoop, and MapReduce.
The trajectory domain also generates large amounts of data owning to the widespread use of GPS devices [19]. Therefore, new data capture, storage, processing, and visualization techniques are developed to handle the new reality in the domain.
Big spatial-temporal frameworks have been developed to address some of these concerns. For example, the work in [20] proposes an extension to the Hadoop framework for spatialtemporal data called ST-Hadoop, that includes contributions from indexing, to processing operations, and a SQL-like language to manipulate data. Sipresk [21] is a framework to perform analyses involving urban transportation data. It integrates spatial-temporal and trajectory data from many different sources and leverages traditional big data technologies to provide analytics. Lastly, Simba [22] extends Spark to provide a fast, scalable solution with high throughput to data processing in the trajectory domain. The framework optimizes memory management and compares the results with other traditional spatial-temporal frameworks.

III. STATE OF THE ART CHALLENGES
The need for similarity metrics based on context and semantics: Trajectory data representation is described in terms of their most basic dimensions: spatial and temporal. For that reason, it is also referred to as raw trajectory. However, data representation can be improved with the addition of trajectory contextual and semantic dimensions. The context of a trajectory includes information such as the vehicle model, the driver, or other elements along the path created by the trajectory. Trajectory semantics are the reasons for the movement [23] (e.g. going home, or going to eat). Capturing new dimensions means having a richer trajectory description to analyze. As a consequence, new similarity metrics leverage the improved representation, creating new ways of comparing trajectories.
The lack of spatial-temporal clustering techniques that leverage the improved trajectory similarity: Similarity definitions are usually based on a distance function between trajectories. Some trajectory similarity algorithms, such as the Dynamic Time Warping [24], are based on and limited to only the spatial-temporal properties of each point of the trajectory. However, the relationship between two trajectories can be described in new forms, based on how close they are, and wether their paths overlap. As a consequence, important analysis conclusions may be missing, and clustering techniques are not expressive enough [25].
The need for an implemented big data spatial-temporal clustering framework: Since the trajectory domain generates large amounts of data, hence big spatial-temporal data, any handling of this data becomes a challenging task. In addition, new trajectory data description and relationship modeling opens up space for new strategies in analysis. Several studies still point to the need for improvements in the integration of [9], analysis of [11], and infrastructure support for [25] trajectory data. This further demonstrates that a big data framework to process improved trajectory data in novel ways is still lacking.

IV. SPATIAL-TEMPORAL CLUSTERING FRAMEWORK
Our work in progress is based on three objectives: (i) to improve trajectory description with new contextual and semantic dimensions, so that novel forms of comparison can be calculated; (ii) to propose new trajectory clustering techniques that leverage new similarity modeling in trajectory data; and (iii) to present a framework that handles analysis in richer trajectory data. The activities associated with each of these goals are described in the following paragraphs.
The first objective is to investigate current spatial-temporal data representation and to propose a richer trajectory data description. To accomplish this objective, ontologies and other studies in the literature are investigated. The main impact is on the trajectory data description. Our work currently investigates an augmented description of trajectory data with the addition of two dimensions: context and semantic. The context of a trajectory relates to the information that surrounds and relates to it, but are not spatial or temporal. An example is a vehicle on different weather conditions during a trip. The weather temperature is a dynamic contextual information that can be different at each timestamp of the trajectory.
The semantic of a trajectory relates to the reasons or goals that motivated an object to move. A simple example is a person who is going to work in the morning. More complex examples are going to lunch, or countourning a mountain. The semantics of a trajectory usually involves associating semantic attributes to segments of the trajectory itself.
The creation of new similarity relations is the second objective of this paper. The main activities to accomplish this objective involve exploring the expressiveness of the novel trajectory representations to define new similarity functions. It starts with an observation of the new trajectory description proposed in the previous goal, an investigation of how trajectory relationships can be described in terms of point to point relationships, and a comparison of small, point to point relationships to improve the overall trajectory comparison. For example, trajectories that share longer and continuous number of points (an overlap) may be scored higher than trajectories that share the same amount of points but scattered along their paths. As a consequence two pairs of trajectories that scored the same value by a similarity algorithm can be further analyzed and separated, based on new relationships. The main impact of this goal is on the trajectory clustering techniques. Clustering analyses will be richer, allowing novel inferences to be derived in the domain.
Lastly, the third objective addresses the development of a software framework to support novel and richer clustering techniques, and demonstrates the benefits of improved representation and similarity calculation.

V. CONCLUSION
This paper describes ongoing research towards an improved description of trajectory data, including contextual and semantic dimensions, novel similarity functions for trajectory clustering, and a framework to support the new forms of spatial-temporal clustering.


extfieldsofstudy:
Computer Science
Mathematics

text:
A novel metaheuristic method for solving constrained engineering optimization problems: Drone Squadron Optimization

Several constrained optimization problems have been adequately solved over the years thanks to advances in the metaheuristics area. In this paper, we evaluate a novel self-adaptive and auto-constructive metaheuristic called Drone Squadron Optimization (DSO) in solving constrained engineering design problems. This paper evaluates DSO with death penalty on three widely tested engineering design problems. Results show that the proposed approach is competitive with some very popular metaheuristics.

INTRODUCTION
Several real-world engineering design problems can be formulated in a nonlinear programming way, where one wants to find a solution x that optimizes f ( x) subject to hi( x) = 0 i = 1, 2, ..., m gi( x) 0 i = 1, 2, ..., P where f ( x) is the objective function to be optimized, and x ∈ ℜ n is an n-dimensional vector x = [x1, x2, ..., xn] T . Each x k , k = 1, ..., n can be bounded by lower and upper limits Li x k Ui; hi( x) and gi( x) are the equality and inequality constraints, respectively; m is the number of equality constraints and p is the number of inequality constraints, where both can be linear or nonlinear. Constraints reduce the feasible search-space of the problem and, instead of making it easier, make it more difficult because feasible solutions can be hard to find. Thus, algorithms able to solve this kind of task are welcome in engineering and manufacturing processes.
In this work, we investigated Drone Squadron Optimization (DSO 1 [6]), a recently proposed self-adaptive metaheuristic which is self-improved online by a hyper-heuristic. DSO is an artifact-inspired technique, as opposed to many algorithms used nowadays, which are nature-inspired. DSO is very flexible because it is not related to behaviors or natural phenomena. Therefore, it can mimic any behavior.
The paper is organized as follows: In Section 2, we briefly introduce the DSO algorithm. Section 3 provides the description of the idea to handle constraints. Section 4 presents the numerical examples (engineering problems), details of the experiments, the results obtained and the discussion. Finally, in Section 5 some conclusions are drawn about the results.

DRONE SQUADRON OPTIMIZATION
Drones can navigate remotely o completely autonomously. They have sensors, can communicate over large distances and, one of the most important features: can be upgraded/ improved not only in terms of hardware but also by changing their software (the firmware). Therefore, as a software controls their behavior, researchers are free to add any kind of mechanism to the algorithm as a regular software upgrade. Thus, there is no need to look for a natural phenomena to justify the improvement.
The Drone Squadron Optimization (DSO) is based on the movement of entities on the search-space. However, as explained before, the movement of the squadron is not necessarily based on behavior observed in nature. DSO's approach allows it to automatically choose to use recombination and/or perturbation of solutions with distinct procedures, making it act as an evolutionary algorithm, swarm algorithm, probabilistic algorithm, or other, according to how it performs on the search landscape. Moreover, those procedures may have their actual code updated during the search.
DSO has two core parts: the semi-autonomous drones that fly over a landscape to explore, and the Command Center that processes the retrieved data and updates the drones' firmware whenever necessary. The self-adaptive aspect of DSO in this work is the perturbation/movement scheme, which is the function used to generate target coordinates (solutions). This function is evolved by the Command Center during the global optimization process in order to automatically adapt DSO to the search landscape, trying to increase the search efficacy.
The DSO algorithm presented here is composed of one Drone Squadron with different teams and a Command Center, which uses information collected from the drones to maintain partial control of the search, and to develop new firmware to control the drones. A drone is not a solution; it moves to a coordinate which is a solution. A drone has a firmware containing the functions (codes) and configurations used by the teams to search the landscape. All drones in the same team share a firmware, but they can be located in different regions of the search-space. In this work, the perturbation function is an actual source code; it is a string to be parsed and executed by the drone.
In [6], DSO was proposed to solve unconstrained (box-constrained) numerical optimization problems. To solve constrained optimization problems, DSO must employ a constraint handling mechanism.

CONSTRAINTS HANDLING
Constraints handling is an important issue in constrained optimization. Such mechanism must guide the optimization technique into feasible regions and be able to reach the bounds of the search-space. A general, but usually not recommended, approach when metaheuristics are used to solve constrained problems is the adoption of penalties [13]. A penalty function (see Equation 2) can be applied to unfeasible solutions to generate a poor function value. If the solution ( x) is feasible (F ), then the penalty is not applied.
In minimization problems, we add a penalty. Otherwise, in maximization problems, we subtract a penalty.
Using this approach, an unfeasible solution can be dropped from the population in the next iteration of the algorithm, justifying the common name of Death Penalty [13]. This allows the constrained problem to be treated as an unconstrained one. However, it does not allow to differentiate two unfeasible solutions as both get the same f ( x). While this characteristic turns unfeasible regions into plateaus, it is the simplest constraint handling mechanism and may be useful in some problems.

EXPERIMENTAL ANALYSIS
In this paper, we investigate three well-explored engineering design problems: the design of a Welded Beam, a Speed Reducer, and a Three-bar truss. The definitions of these problems can be seen in related work [2].

DSO was implemented in Matlab (R) 2010, compatible with
Octave. The experiments were run on an Intel (R) i7 6700k, Arch Linux 4.11.9-1-ARCH.

Configuration
As the problems investigated in this work are minimization ones, the penalty function simply returns the maximum value accepted by Matlab: realmax = 1.79769313486232e + 308. Thus, all unfeasible solutions have f ( x) = realmax.

Results
Tables 1, 2, and 3 have statistics comparing DSO and related methods on the investigated problems. As one may notice, DSO found the same as or better solutions than the other methods. The average solution was not as good, probably because DSO performed much fewer evaluations and had outliers or because of the simple death penalty approach. Nevertheless, it is important to remember that DSO evolves the firmware, but one cannot guarantee that the new functions are useful. Therefore, poor-quality or invalid functions may be generated.

CONCLUSIONS
In this paper, we evaluated Drone Squadron Optimization with a death penalty function to solve three well-known constrained engineering design problems. Experiments were conducted on the design of: a welded beam, a pressure vessel, and a three-bar truss. Results show that DSO was able to achieve the best known solution of each problem after a relatively small number of function evaluations.
When compared to nature-inspired approaches, DSO with a simple penalty function found equal or better solutions. We intend to improve the technique using a better constraint handling mechanism to reduce the average solution quality.

ACKNOWLEDGMENTS
I'm still trying to get a grant...


Analysis of the Impact of Negative Sampling on Link Prediction in Knowledge Graphs

Knowledge graphs are large, useful, but incomplete knowledge repositories. They encode knowledge through entities and relations which define each other through the connective structure of the graph. This has inspired methods for the joint embedding of entities and relations in continuous low-dimensional vector spaces, that can be used to induce new edges in the graph, i.e., link prediction in knowledge graphs. Learning these representations relies on contrasting positive instances with negative ones. Knowledge graphs include only positive relation instances, leaving the door open for a variety of methods for selecting negative examples. In this paper we present an empirical study on the impact of negative sampling on the learned embeddings, assessed through the task of link prediction. We use state-of-the-art knowledge graph embeddings -- \rescal , TransE, DistMult and ComplEX -- and evaluate on benchmark datasets -- FB15k and WN18. We compare well known methods for negative sampling and additionally propose embedding based sampling methods. We note a marked difference in the impact of these sampling methods on the two datasets, with the"traditional"corrupting positives method leading to best results on WN18, while embedding based methods benefiting the task on FB15k.

INTRODUCTION
Much of human knowledge can be formalized in terms of real world entities, abstract concepts, categories and the relations between them. A graph structure -a knowledge graph (KG) -is a natural candidate for representing this. NELL [5], Freebase [3] and  [25] are examples of large knowledge graphs that contain millions of entities and facts. Facts are represented as triples, each consisting of two entities connected by a binary relation, e.g., (concept:city:London, relation:country capital, concept:country:UK). Here entities such as London and UK are represented as nodes and the relation country capital is represented as a binary link that connects these nodes. e same two nodes may be connected by more than one type of relation, making the KG a multi-graph. KGs have found applications in question answering systems [15], evaluating trustworthiness of web content [8], and web search [7].
Although KGs such as Freebase consist of millions of entities and billions of facts, they are still incomplete [28] which limits their application. However, it is possible to infer new (missing) facts from known facts. Recently, latent factor models that capture global pa erns from the KG have received considerable a ention. ey learn a representation of the graph in a continuous vector space by inducing embeddings that capture the graph structure.
Predicting new edges to automatically add new facts to a KG helps bypass the text analysis stage and bootstrap new knowledge based on what is already captured in the KG. Similar to other problems in processing natural language, such as parsing, data consists (almost) exclusively of positive instances. A solution to this issue is using implicit negative evidence, whereby instances that have not been observed are considered negatives, and are used for contrastive estimation [23], where the aim is to rank observed instances higher than negative (unobserved) ones. Negative instances can be generated using a variety of methods.
In this article we present the results of our investigation on the impact of several negative sampling methods on state-of-the-art knowledge graph embedding models. Additionally we propose two negative sampling strategies for ne tuning the model. Understanding the impact of negative instance sampling will have at least two uses: providing the basis for choosing the negative sampling method to build the best model for a given method, and allowing us to place in the right context results reported in the literature that were produced while using di erent negative sampling methods.

LINK PREDICTION IN KNOWLEDGE GRAPHS
Knowledge graphs KG = (E, R) contain knowledge in the form of relation triples (s, r, t), where s, t ∈ E are entities, and r ∈ R is a relation. ese knowledge graphs are not complete, and additional links (facts) can be inferred, based on the idea that similar nodes have similar relations -e.g. all countries have a capital city. e KG can be encoded using di erent modeling techniques, which results in encodings for both the entities and the relations.
ese methods learn a model for the processed KG as a large set of parameters, induced based on optimizing a loss function with respect to positive and negative instances of links representing di erent relations. Methods such as R [21] and Neural Tensor Networks [24] learn millions of parameters that makes them more exible, enabling them to model well a variety of relations, but at the cost of increased computational complexity and potential over ing. TransE [4], DistMult [29] learn simpler models (with far fewer parameters) and are easier to train but are unable to model certain types of relations such as many-to-one (TransE) and asymmetric relations (DistMult). Recent work such as [20] achieve the modeling power of R with a smaller number of parameters by compressing the tensor product. Complex valued embeddings (ComplEx) [27] extend the DistMult to model antisymmetric relations by using complex valued embeddings. [12] showed that most latent factor models can be modi ed to learn from paths rather than individual triples which improves performance. Recurrent Neural Networks that learn path representations have also been used for link prediction [6,18]. All these models require negative samples during training.
We focus our analysis on four state-of-the-art methods with respect to link prediction in knowledge graphs: ComplEx, DistMult, R , TransE. ComplEx performs as well as the Holographic Embedding (HolE) model, so HolE was not included 1 .

R
e R model [21,22] weighs the interaction of all pairwise latent factors between the source and target entity for predicting a relation. It represents every entity as a d dimensional vector (x ∈ R d ), and every relation as a d × d matrix W ∈ R d ×d .
is model represents the triple (s, r, t) as a score given by s c (s, r , t) = x T s W r x t ese vectors and matrices are learned using a loss function that contrasts the score of a correct triple to incorrect ones. Commonly used loss functions include cross-entropy loss [26], binary negative log likelihood [27], and max-margin loss [12,20] which we use here: is the set of incorrect targets. Similar triples are used where the relation and target are shared, but the source entity is incorrect.

TransE
TransE [4] interprets relations as a translation operation from the source to the target mediated by the relation. More speci cally, it embeds a triple spatially such that the source vector can travel to the target vector through the relation vector, i.e., x s + x r ≈ x t . e scoring function s c (s, r , t) for TransE is given by 1 And also because HolE is very similar to ComplEx. is was veri ed through personal correspondence with an author of the ComplEx paper.
where x s , x r , x t are d dimensional vectors, and d(x) is either the L 1 or L 2 -norm of x. We use TransE with L 2 -norm. For learning embeddings, we use max-margin loss (1). Compared to R , TransE has much fewer parameters, but it is more limited in the variety of relations it can model, as the translation operation assumes 1 : 1 relations.

DistMult
DistMult [29] is a special case of the R model, where the relation matrix is assumed to be diagonal. is results in a sparse relation matrix and consequently fewer parameters. However this simplicity results in the reduction of modeling power. e DistMult model is symmetric and hence can only model symmetric relations. However, DistMult performs well on FB15K benchmark dataset, since the test data contains only a few instances of asymmetric triples. e DistMult scoring function is given by x t is can also be wri en as a three way inner product As before we use the margin loss (1) for learning these vectors.

ComplEx
e ComplEx model [27] performs sparse tensor factorization of the KG in the complex domain. Nodes and relations are modeled by d dimensional vectors with a real and imaginary part (Re(x), Im(x)).
is allows ComplEx to model anti-symmetric relations since the three way dot product (inner product) in the complex domain is not symmetric. ComplEx can be seen as DistMult with complex embeddings. e score function of ComplEx is given by: [27] trained ComplEx with negative log-likelihood. To maintain the same experimental conditions for assessing the e cacy of negative sampling, we train ComplEx with max margin loss (1).

NEGATIVE SAMPLING
Knowledge Graphs capture knowledge as <entity, relation, entity> triples, with entities mapped to nodes, and relations to edges. KGs contain only positive instances. While one-class classi cation solutions have been around for some time [17], for inducing KG embeddings, using negative instances leads to be er models.
Negative instances are not marked in a knowledge graph. e task of link prediction has much in common with other tasks in NLP where (most of) the observed data consists of positive instances. [23] proposed contrastive estimation, whereby instances that were produced by perturbing the observed ones (and that themselves have not been observed) will serve as negative instances, and the aim is to rank observed instances higher than the unobserved ("negative") ones. In neural probabilistic language models, negative sampling was rst proposed in [1] as importance sampling. A sampling solution that was more stable than importance sampling was introduced by [16], who built upon the noise-contrastive estimation [10]. In these approaches negative samples are drawn from a non-parametric noise distribution.
For knowledge graphs in particular there are many di erent ways to produce negative instances based on the graph structure. We present an overview of techniques for producing negative instances from a knowledge graph, and we evaluate their impact on knowledge graph completion, or link prediction.
3.1 Random sampling : R e simplest form of sampling negative instances is to assume a closed world hypothesis and consider any triple that does not appear in the KG as a negative instance. Let , · · · , N } denote the complete knowledge graph, where i = 1 represents the presence of a triple (s i , r i , t i ) (a positive instance) and i = 0 represents absence. According to the closed world assumption, the set of negatives K − is given by Since the KG is incomplete this set contains positive triples not present in the KG. Furthermore this set might be very large because the incorrect facts (O(N 2 )) far outnumber the correct ones.
A simple solution to the scalability problem is randomly sampling a small number of samples from K − . Given a positive triple (s, r, t) we generate n s negative triples by sampling n s target entities from the entity set E. Since the sampling is random, we do not check whether the sampled triples are present in the train and development set, because the probability they are present in K + is negligible. e same procedure is used to generate negative source entities. e negatives produced by random sampling may not be very useful: for the positive triple (Tom Cruise, starred in, Top Gun), negative targets such as London or Mount Everest seem irrelevant. Relevant negative targets should include entities that are movies, such as Terminator, Inception. To obtain such negatives it is necessary to constrain the set of entities from which samples are drawn. We explore such constraints in the following sections.

Corrupting positive instances : C
We use a method described in [24] that generates negative instances by corrupting positive instances: for every relation r , Socher et al. [24] collect the sets S = {s |(s, r, * ) ∈ K + } and T = {t |( * , r, t) ∈ K + }, and produce sets of corrupted triples During training K + consists of triples from training and development set. We sample a number n s of negative samples from S and T . Such a method produces negative instances that are closer to the positive ones than those produced through random sampling.
An issue with this method is that for relations with very few positive instances, there will not be a large enough pool of source and target candidates to corrupt the positive instances. e data analysis shows that this is an issue for the FB15k dataset. For relations where not enough corrupted negative instances can be produced, we supplement this set with randomly produced negative samples.

Typed Sampling : T
Knowledge graphs such as FreeBase and NELL [5] have strongly typed relations. For example, a relation born in holds between entities of type person and entities of type cit . Relevant negative candidates (sources or targets) can be mined by constraining the entities to belong to the same type as that of the source (or target).
is can help bypass the problem mentioned for the corrupt method, when some relations in the dataset have very few instances.
For every relation r : S → T , if S r,t = {s |s has type S t } and T r,t = {t |t has type T t }, with S t and R t the domain and range respectively of r , negative instances will consist of triples (s , r, t), s ∈ S and (s, r , t ), t ∈ T , such that (s , r , t) R and (s, r , t ) K + . We then sample n s number of negative samples from these triples.
If an entity has more than one type (e.g. Albert Einstein has types person, scientist), we include it in S r,t (or T r,t ) if one of its types matches S t (or T t ). We obtain category data for the Freebase dataset from Freebase relation metadata released in [9], and the entity type by mapping the Freebase entity identi er to the Freebase category.
is results in 101,353 instances of the category relation which is used in the training stage to produce typed negative samples. Domain and range types for Freebase relations are provided by Freebase itself. A few examples of entities and types are included in Table 1.
We do not use typed sampling for Wordnet. e hypernym/hyponym relations are the de facto type relations in WordNet, but are hierarchical rather than a mapping onto a given small set of predetermined types as in Freebase.

Relational Sampling : REL
Although typed or corrupt relation sampling can generate relevant negative candidates, due to the incompleteness of the KG, some of these candidates could be unknown positives. If we assume that source target pairs participate in only one relation, then sampling targets (sources) that are connected to the current source (target) through relations other than the current relation can yield true negatives. is is a common procedure in multi-class learning.
More formally, for positive triple (s, r , t) the negative candidate source set is S − = {s |(s, r , t ), ∀ r ∈ R, r r } and target set As before, a er computing S and T we lter out positive triples from train and development set and sample a number n s of negative samples.

Nearest Neighbor sampling : NN
Most negative sampling methods generate negative samples based on either the closed world assumption, functional constraints such as type constraints, and triple perturbation [19]. We introduce a negative sampling method which uses a pre-trained embedding model for generating negative samples. We name this pre-trained embedding model the 'negative sampling model'. We use the negative sampling model to generate negative targets (sources) that are Source Type Source Relation Target  Target Type  f ilm  star wars episode IV produced b  eor e lucas  f ilm producer  person alexandre dumas people pro f ession writer pro f ession academic post pro f essor pro f ession people albert einstein award winner For a positive triple (s, r , t), with x t the vector representation of t obtained from the negative sampling model, the set of negative samples are the top n s nearest neighbors of x t (that are not positive) obtained from the negative sampling model. e negative sampling model may be di erent than the model that is being trained. We use the R model trained with 100 typed (T) negative samples as a negative sampling model for the FB15K dataset. Note that the R model parameters are frozen (not updated), it is simply used for generating negatives that are used for training another model. Algorithm 1 describes the procedure for a single triple. In practice we use a batch of triples and the nearest neighbor search is performed using the Ball Tree algorithm which is built only once since the negative sampling model is not updated.

Algorithm 1: Algorithm 1 Nearest Neighbor Sampling
Input : Triple (s,r,t), Entity Set E, Positive source and targets P s and P t , Negative Sampling Embedding Model f n , Number of negative samples n s Output : Set of n s negative samples N s ← E\P s , N t ← E\P t ; X s n ← f (N s ), X t n ← f (N t ) ; Initialize the K ball tree with X s n and X t n ; x t ← f n (t) ; x s ← f n (s) ; S ← nearest neighbors(x s ,num=n s ); T ← nearest neighbors(x t ,num=n s ); return S,T Nearest neighbor sampling is computationally expensive compared to the methods discussed in previous sections. is is because a search over all entities needs to be performed for source and target entities for every triple. erefore we use a model trained using typed negative sampling methods for Freebase and corrupted sampling for Wordnet to initialize the parameters and then ne tune the model using nearest neighbor sampling for 5 epochs.
3.6 Near Miss sampling : nmiss e nearest neighbor sampler generates negatives that are similar to positives in vector space. Some of those negatives may be ranked higher than the positives. Exposing such highly ranked negatives to the classi er can help the model learn a be er discriminator. We name this se ing as near miss sampling, because the generated negatives are top ranked candidates which makes it di cult for the model to classify them as negatives (near misses). To generate highly ranked negatives, we collect the top n s targets (sources) closest to the predicted target (source) vector. Like the nearest neighbor sampler, we use the negative sampling model for obtaining the predicted vector and entity embeddings. e negative sampling model is not updated.
Given a positive triple (s, r , t) we obtain the predicted vector t = x T s W r where x s , W r are entity and relation embeddings of source s and relation r obtained using the negative sampling model. Note that t may not be the same as x t , the target entity representation. e set of (target) negative samples are the top n s nearest neighbors of the predicted vector t . Algorithm 2 describes the procedure for a single triple, in practice we use a batch and the Ball Tree is built only once.
; Initialize the K ball tree with X s n and X t n ; x s ← f n (s), x t ← f n (r ), W r ← f n (r ) ; s ← x T s W r , t ← W r x t ; S ← nearest neighbors( s ,num=n s ); T ← nearest neighbors( t ,num=n s ); return S,T Like nearest neighbor sampling, near miss sampling is also computationally expensive, so instead of learning from randomly initialized parameters we tune a pre-trained model for 5 epochs.

DATA
We evaluate the impact of negative sampling on the Freebase dataset (FB15k) and on the WordNet dataset (WN18) introduced by [4].
ey are very di erent in coverage -FB15k contains mostly named entities connected through strongly typed relations, while WN18 contains mostly common nouns connected through lexical and semantic relations. Dataset details are included in Table 2   is disparity is also re ected in the distribution of node degrees -12% of the entities have degree equal or less than 10 (appear in at most 10 instances). e average degree of a node in FB15k is approximately 13.2 overall, and 32.4 on the training data. e distribution of relations and node degrees is presented in Figure 1. e type of relations included in Freebase connect named entities. ey are extrinsic relations, in that they do not hold based on the intrinsic properties of the connected entities, but are due to external circumstances. For example, the people profession relation connecting people and their professions are not determined by intrinsic properties of people and professions. Relations in FreeBase are strongly typed -the domain and range of the relations are types, e.g. the country capital relation connects countries and cities.

WN18
is dataset consists of a subset of relations from the WordNet lexical database 3 , split into training, development and testing: 141442/ 5000/ 5000. ere are 18 relations. ere is less variation in the number of instances per relation compared to the FB15k, as can be seen in Figure 2. ere is one relation with less than 100 instances (similar to), while the most frequent relations (hypernym, hyponym) have approximately 35,000. is translates into sparser adjacency matrices for factorization, compared to Freebase.
WordNet contains lexical and semantic relations. Lexical relations -such as derivationally related form connect lemmas from di erent parts of speech that are morphologically connected. e semantic relations cover is a relations (hypernym / hyponym, instance hypernym/hyponym), three types of part of relations (member, substance and part). e semantic relations in WordNet are intrinsic, as they re ect or arise from intrinsic properties of the connected entities. For example, a cat is a animal, and cat has part paws not because of external circumstances, but because of what a cat is. Compared to FreeBase, WordNet relations are not typedthere is no clear domain and range for the WordNet relations.

EXPERIMENTS 5.1 Implementation
For fair comparison we reimplemented R , TransE, DistMult, ComplEx using PyTorch, and tested them using the same experimental se ing: same loss (max-margin loss), embedding size (100), and data. We use the Adam [13] SGD optimizer for training because it addresses the problem of decreasing learning rate in AdaGrad. We ensure that entity embeddings for all the models have unit norm. We performed exhaustive randomized grid search [2] for the L 2 regularizer on the validation set for all models and we tuned the  Table 3: Parameter values training duration using early stopping. e learning rate (lr ) and λ (the L 2 norm coe cient) are presented in Table 3. e code is available in Github 4 . e di erent methods for negative sampling described in Section 3 were used to produce negative instances for training. In FB15K some relations do not have enough sources or targets to generate negative triples by corrupting positive triples. If the number of generated triples are less than the required (n s ), we complete the set of negative samples with randomly generated triples.
For the nearest neighbor and near miss se ings, we used the best performing model for initializing the parameters, and used the R model tuned on typed negative samples (100 negative samples) as the negative sampling model for FB15K and R trained by corrupting positive samples (100 negative samples) for WN18.

Test data
e test data is the same across all experiments. e negative instances for the test data were generated as described in [4] corrupting positive instances using all entities of the dictionary instead of the correct source and target, without sampling.
Also following the procedure of [4], we use the ltered se ing: the negative samples added to the training data are ltered with respect to the test data to avoid (known) false negatives in training.

Evaluation metrics
For evaluation we use the mean reciprocal rank (MRR) and hits@K that are commonly used for link prediction.
For a list of N answers for link prediction, the mean reciprocal rank (MRR) and hits@k are de ned as: where rank i is the rank of the positive instance i predicted by the model with respect to the negative samples. For FB15k we use hits@10, for WN18, hits@1. 4 h ps://github.com/bhushank/kge-rl

Results
We present the results of link prediction on FB15k and WN18 in terms of MRR in Figures 3 and 4 for n s ∈ {1, 2, 5, 10, 20, 50, 100} for each positive instance. e results show that the di erent sampling methods have different e ects on the two datasets. Since link prediction is based exclusively on the embedding of the graphs, di erences in performance are caused by the di erent structure (e.g. di erent node degrees which are re ected in the sparsity of the relation adjacency matrices) and the di erent nature of the relations -typed and extrinsic in FB15k, not typed and (mostly) intrinsic in WordNet.
As suggested by work on learning statistical models through noise contrastive estimation [11], selecting di cult negative instances produces be er models: near miss sampling leads to be er results on FB15k for most embeddings methods. e reason embedding based sampling works well on FreeBase is primarily because the negative samples generated by the pre-trained embedding model are very close to the discriminator boundary. For example, the near miss sampling involves generating negative target entities that are highly ranked by the embedding model. ese entities are likely to be highly ranked by the model that is being trained. erefore providing these entities as negatives allows the system to learn a model that ranks them below the positive target using the max-margin loss. Note that the samples generated by the embedding model are close to each other in vector space due to the ability of the embedding model to cluster entities. erefore almost all the generated negative samples are close to the discriminator boundary. We treated the negative sampling model (pre-trained model) as a hyper parameter. We found that the RESCAL model worked best. We speculate that this might be due to the superior ability of RESCAL model to cluster similar entities.
Corrupting positive instances, the method most frequently used for link prediction, is the least competitive on FB15k, but ts Word-Net well, particularly for R . DistMult is not very sensitive to the type of negative sampling on WN18, except for the nearest neighbor method with which it does not perform well.
To understand why corrupting positive instances works best on WordNet, we look at the data and the graph statistics. e WN18 dataset has 18 relations while with FB15k has about 1495 relations. Due to per relation data sparsity in FB15K, see Fig. 1 and 2, negative sampling using corrupted triples works poorly for FB15K, as it o en has to fall back on random sampling when not enough positive instances with a shared source/target are available for "corruption". Corrupt sampling works be er in an instance rich environment.
Apart from data sparsity, the nature of WordNet and Freebase relations may also a ect the performance of negative sampling methods. WordNet relations have open ended ranges and domains while Freebase relations have typed ranges and domains. Embedding based methods, such as the near miss sampling method we implemented, work on the basis of clustering similar entities, and do not function well for WordNet where the relations do not have domains and ranges that re ect conceptual/semantic clusters.
We have discussed the di erences in performance of sampling methods for the two KGs used. ere are also di erences with respect to the link prediction methods. Random sampling works best for TransE. is may be surprising at rst, but is understandable considering that the theoretical model behind TransE assumes 1 : 1 relations. Providing it with negative entities that are close (using typed, corrupted or embedding methods) does not result in improvement because the negative entities generated using typed, corrupt or embeddings are close to each other in vector space and the model will ultimately be unable to distinguish between them. is is not the case when doing random sampling, when TransE is not perturbed by too close negatives. ComplEx and DistMult perform well with both near miss and nearest neighbour sampling on FB15k. R performs best with near miss sampling on this data, and with corrupting positive samples for WordNet. For middle-range n s relational sampling performs best.
As described in Section 4, the training data for both methods varies quite a bit in terms of the frequency of the relations covered. Freebase is more extreme, in that approximately 39% of the relations have at most 10 positive instances to train on. We analyzed the e ects of negative sampling on di erent slices of the data, split by the order of magnitude (oom) of the frequency of the relations in the training data. More precisely, we group relations into sets G n indexed by the order of magnitude n: G n = {r |10 n < f req(n, training data) <= 10 (n+1) } 5 . Freebase has 5 slices (0..4) and WordNet 4 (1..4). e results (as MRR and hits@K) for slices representing relations with OOM 2 or more closely mirror the overall results. e results for the low frequency relations are shown in Figures 5 and 6. e hits@K score are similar to the MRR ones, so we do not include them 6 .
While the results on the low frequency relations cannot be analyzed separately from the other relations because the embeddings process relies on processing and inducing jointly all relation and 5 We include relations that have only one instance in G 0 . 6 e complete set of plots accompanies the code and will be shared.
Yang et al. [29] Negative  Table 4: SotA results using a max-margin loss function and corrupting positive instances vs. the best performing negative sampling.
entity representations, we can note that the performance on link prediction for these relations with very few instances varies much with the negative sampling method. Overall, the best results are obtained with the same sampling method as for their more populous counterparts, but for speci c ranges of the number of generated negative samples other methods would work best (e.g. nearest neighbor and relational sampling for WordNet data). e reported experiments were performed using the max margin loss function. In Table 4 we include the state of the art results on DistMult, R and TransE obtained with a max margin loss function reported in [29] and corrupting tripes, to compare with the results obtained with the best negative sampling method for the dataset. Slight di erences in the learning rate and λ account for the di erences in performance when using corrupt positive instances as negative samples for the WN18 dataset.
Recently, [27] used the log-likelihood objective, which leads to improvements over the published results for the methods they compared (TransE, ComplEx, HolE, DistMult). We plan to analyze the negative sampling methods while using this new loss function.

CONCLUSION
We report an analysis of the impact of six negative sampling methods on the performance of link prediction in knowledge graphs, for four methods for graph embedding -ComplEx, DistMult, R , TransE. e analysis is performed with respect to two datasets -a subset of Freebase (FB15k) and a subset of WordNet (WN18) -that are very di erent in the type of knowledge they cover.
e results indicate that di erent approaches to negative sampling work best for the two resources. sampling worked best for Freebase with most of the graph embedding methods, while corrupting positive triples leads to best results on WordNet. e newly proposed near miss and nearest neighbor negative sampling work best for Freebase, for three out of the four graph embeddings methods. From analysis of datasets, we further concluded that embedding based negative sampling is very useful for combating data sparsity, while corrupt sampling works best in the data rich scenario. e nature of the relations in these graphs (