CoLAKE: Contextualized Language and Knowledge Embedding

With the emerging branch of incorporating factual knowledge into pre-trained language models such as BERT, most existing models consider shallow, static, and separately pre-trained entity embeddings, which limits the performance gains of these models. Few works explore the potential of deep contextualized knowledge representation when injecting knowledge. In this paper, we propose the Contextualized Language and Knowledge Embedding (CoLAKE), which jointly learns contextualized representation for both language and knowledge with the extended MLM objective. Instead of injecting only entity embeddings, CoLAKE extracts the knowledge context of an entity from large-scale knowledge bases. To handle the heterogeneity of knowledge context and language context, we integrate them in a unified data structure, word-knowledge graph (WK graph). CoLAKE is pre-trained on large-scale WK graphs with the modified Transformer encoder. We conduct experiments on knowledge-driven tasks, knowledge probing tasks, and language understanding tasks. Experimental results show that CoLAKE outperforms previous counterparts on most of the tasks. Besides, CoLAKE achieves surprisingly high performance on our synthetic task called word-knowledge graph completion, which shows the superiority of simultaneously contextualizing language and knowledge representation.

Introduction
Deep contextualized language models pre-trained on large-scale unlabeled corpora have achieved significant improvement on a wide range of NLP tasks (Peters et al., 2018;Devlin et al., 2019;Yang et al., 2019). However, they are shown to have difficulty capturing factual knowledge .
Recently, there is a growing interest in combining pre-trained language models (PLMs) with structured knowledge. A popular approach is to inject pre-trained entity embeddings into PLMs to better capture factual knowledge, such as ERNIE (Zhang et al., 2019) and KnowBERT . The shortcomings of these models can be summarized as follows: (1) The entity embeddings are separately pre-trained with some knowledge embedding (KE) models (e.g., TransE (Bordes et al., 2013)), and fixed during training PLMs. Thus they are not real joint models to learn the knowledge embedding and language embedding simultaneously. (2) The previous models only take entity embeddings to enhance PLMs, which are hard to fully capture the rich contextual information of an entity in the knowledge graph (KG). Thus their performance gains are limited by the quality of pre-trained entity embeddings. (3) The pre-trained entity embeddings are static and need to be re-trained when the KG is slightly changed.
In this paper, we propose the Contextualized Language And Knowledge Embedding (CoLAKE), which jointly learns language representation and knowledge representation in a common representation space. Different from the previous models, CoLAKE dynamically represents an entity according to its knowledge context and language context. For each entity, CoLAKE considers a sub-graph surrounding   Figure 1: (a) When injecting knowledge, CoLAKE considers the knowledge context about the entity while previous semi-contextualized joint models only consider a single entity embedding. By contextualizing the entity, CoLAKE is able to directly access (Harry Potter, enemy of, Lord Voldemort) to help understand sentence (1) and access (Harry Potter, mother, Lily Poter) to help understand sentence (2). (b) The word-knowledge graph (WK graph) is a unified structure to represent both language context and knowledge context, which is composed of two parts: the fully-connected word graph and knowledge sub-graphs extracted from large KGs.
it as its knowledge context that contains the facts (triplets) about the entity. In this way, CoLAKE can dynamically access different facts as background knowledge to help understand the current text. As shown in Figure 1(a), to understand different sentences, CoLAKE can utilize different facts about the linked entity Harry Potter. The knowledge context of Harry Potter is a sub-graph containing the triplets about it. According to whether or not to utilize entities' knowledge context, our proposed CoLAKE can be distinguished from previous models, which we call semi-contextualized joint models since they only contextualize language representation.
To deal with the heterogeneous structure of language and KG, we build a graph to integrate them into a unified data structure, called word-knowledge graph (WK graph). Most recent successful PLMs use Transformer architecture (Vaswani et al., 2017), which treats input sequences as fully-connected word graphs. WK graph is knowledge-augmented word graph. Using entities mentioned in the sentence, we extract sub-graphs centered on those mentioned entities from KGs. Then we mosaic such sub-graphs and the word graph in a unified heterogeneous graph, i.e. WK graph. An instance of the WK graph can be found in Figure 1(b). The constructed WK graph is fed into CoLAKE along with its adjacency matrix to control the information flow to reflect the graph structure. CoLAKE is based on the Transformer encoder, with the embedding layer and the encoder layers slightly modified to adapt to input in the form of WK graph. Besides, we extend the masked language model (MLM) objective (Devlin et al., 2019) to the whole input graph. That is, apply the same masking strategy to word, entity, and relation nodes and training the model to predict the masked nodes based on the rest of the graph.
We evaluate CoLAKE on several knowledge-required tasks and GLUE (Wang et al., 2019a). Experimental results demonstrate that CoLAKE outperforms previous semi-contextualized counterparts on most of the tasks. To explore potential applications of CoLAKE, we design a synthetic task called wordknowledge graph completion. Our evaluation on this task shows that CoLAKE outperforms several KE models by a large margin, in transductive setting and inductive setting.
In summary, CoLAKE can be characterized in three-fold: (1) CoLAKE learns contextualized language representation and contextualized knowledge representation simultaneously with the extended MLM objective. (2) CoLAKE adopts the WK graph to integrate the heterogeneous input for language and knowledge. (3) CoLAKE is essentially a pre-trained graph neural network (GNN), thereby being structure-aware and easy to extend.

Related Work
Language Representation Learning. The past decade has witnessed the great success of pre-trained language representation. Initially, word representation pre-trained using multi-task objectives (Collobert and Weston, 2008) or co-occurrence statistics (Mikolov et al., 2013;Pennington et al., 2014) are static and non-contextual. Recently, contextualized word representation pre-trained on large-scale unlabeled corpora with deep neural networks has dominated across a wide range of NLP tasks (Peters et al., 2018;Devlin et al., 2019;Yang et al., 2019;Qiu et al., 2020).
Knowledge Representation Learning. Knowledge Representation Learning (KRL) is also termed as Knowledge Embedding (KE), which is to map entities and relations into low-dimensional continuous vectors. Most existing methods use triplets as training samples to learn static, non-contextual embeddings for entities and relations (Bordes et al., 2013;Lin et al., 2015). Recent advances focusing on contextualized representation, which use subgraphs or paths as training samples, have achieved new state-of-the-art results on KG tasks (Wang et al., 2019b;Wang et al., 2020a).
Joint Language and Knowledge Models. Due to the mutual information existing in language and KGs, joint models often benefit both sides. Besides, tasks such as entity linking also require entity embeddings that are compatible with word embeddings. Combining the success of Mikolov et al. (2013) and Bordes et al. (2013), Wang et al. (2014) jointly learn embeddings for language and KG. Targeting mention-entity matching in entity linking, Yamada et al. (2016), Ganea and Hofmann (2017) also proposed joint methods to map entities and words into the same vector space. Inspired by the recent success of contextualized language representation, much effort has been devoted to injecting entity embeddings into PLMs (Zhang et al., 2019;. Despite their success, the knowledge gains are limited by the expressivity of their used pre-trained entity embeddings, which is static and inflexible. In contrast, KEPLER (Wang et al., 2019c) aims to benefit both sides so jointly learn language model and knowledge embedding. However, KEPLER does not directly learn embeddings for each entity but learns to generate entity embeddings with PLMs from entity descriptions. Besides, none of these work exploits the potential of contextualized knowledge representation, which makes them different from our proposed CoLAKE. A brief comparison can be found in Table 1. CoLAKE is conceptually similar to K-BERT (Liu et al., 2020) and BERT-MK (He et al., 2019). CoLAKE differs from K-BERT in that, instead of injecting triplets during fine-tuning, CoLAKE jointly learns embeddings for entities and relations during pretraining LMs. Besides, CoLAKE places language and knowledge representation learning into a unified pre-training task, masked language model, which makes it more concise than BERT-MK. In addition, CoLAKE is a general-purpose joint model while BERT-MK mainly focuses on medical domain.

CoLAKE
CoLAKE jointly learns contextualized representation for language and knowledge by pre-training on structured, unlabeled word-knowledge graphs (WK graphs). We first introduce how to construct such WK graphs, then we describe the model architecture and the implementation details.

Graph Construction
Typically, language embedding models take sequences as input while knowledge embedding (KE) models take triplets or knowledge sub-graphs as input. Recent successful PLMs take Transformer (Vaswani et al., 2017) as their backbone architecture, which actually processes sequences as fully-connected word graphs. Thus, graph is a common data structure to represent language and knowledge. In this section, we show how to integrate word graph and knowledge sub-graphs into the unified WK graph.
We first tokenize a sentence into a sequence of tokens and fully connect them as a word graph. Then we recognize the mentions in the sentence and use an entity linker to find the corresponding entities in a certain KG. The mention nodes are then replaced by their linked entities, which are called anchor nodes. By this replacement, the model is encouraged to map the injected entities and mention words near one another in the vector space. Centered on the anchor nodes {e i } i , we can extract their knowledge contexts {{e i , r ij , e ij } j } i to form sub-graphs, in which relations are also transformed into graph nodes. The extracted sub-graphs and the word graph are then concatenated with anchor nodes to obtain the WK graph. Figure 2 shows the process of constructing a WK graph. In practice, for each anchor node we randomly select up to 15 neighboring relations and entities to construct a sub-graph to be injected into the WK graph. We only consider triplets in which anchor node is head (subject) instead of tail (object). In the WK graph, entities are unique but relations are allowed to repeat.

Model Architecture
The constructed WK graphs are then fed into the Transformer (Vaswani et al., 2017) encoder. We modify the embedding and encoder layers of vanilla Transformer to adapt to input in the form of WK graph.
Embedding Layer. The input embedding is the sum of token embedding, type embedding, and position embedding. For token embedding, we maintain three lookup tables for words, entities, and relations respectively. For word embedding, we follow RoBERTa  which uses Byte-Pair Encoding (BPE) (Sennrich et al., 2016) to transform sequence into subwords units to handle the large vocabulary. In contrast, we directly learn embeddings for each unique entity and relation as common knowledge embedding methods do. The token embeddings are obtained by concatenating word, entity, and relation embeddings, which are of the same dimensionality. There are different types of nodes so the WK graph is heterogeneous. To handle this, we simply use type embedding to indicate the node types, i.e. word, entity, and relation. For position embedding, we need to assign each injected entity and relation a position index. Inspired by Liu et al. (2020), we adopt the soft-position index which allows repeated position indices and keeps tokens in the same triplet continuous. Figure 2 shows an intuitive example of how to assign position index to graph nodes.  Masked Transformer Encoder. We use masked multi-head self-attention to control the information flow to reflect the structure of WK graph. Given the representation of graph nodes X ∈ R n×d , where n is the number of nodes and d is the dimension for each node, the representation after masked self-attention is obtained by where W Q , W K , W V ∈ R d×d k are learnable parameters. M ∈ R n×n is the mask matrix given by With the masked Transformer encoder, each node can only gather information from its 1-hop neighbor at each layer. Masked Transformer encoder works similar to GAT (Velickovic et al., 2018).

Pre-Training Objective
The Masked Language Model (MLM) objective is to randomly mask some of tokens from the input and train the model to predict the original vocabulary id of the masked tokens based on their contexts. In this section, we extend the MLM from word sequences to WK graphs.
In particular, we mask 15% of graph nodes at random. When a node is masked, we replace it with (1) the [MASK] token 80% of time, (2) a randomly sampled node with the same type as the original node 10% of time, (3) the unchanged node 10% of time. As different types of nodes are masked, we encourage CoLAKE to learn different aspects of capabilities: • Masking word nodes. When words are masked, the objective is similar to traditional MLM. The difference is, CoLAKE can predict masked words based on not only the context words but also the entities and relations in the WK graph. Masking words helps CoLAKE learn linguistic knowledge.
• Masking entity nodes. If the masked entity is an anchor node, the objective, which is to predict the anchor node based on its context, helps to align the representation spaces of language and knowledge. Take the instance in Figure 1(b), the embedding of entity Harry Potter will be learned to be similar to its textual form, Harry Potter. If the masked entity is not an anchor node, the MLM objective is similar to that used in semantic matching-based KE methods such as ConvE (Dettmers et al., 2018) and CoKE (Wang et al., 2019b), which enables CoLAKE to learn a large number of entity embeddings. Masking entity nodes helps CoLAKE (a) map words and entities into a common representation space, and (b) learn contextualized representation for entities.
• Masking relation nodes. If the masked relation is between two unique anchor nodes, the objective is similar to distantly supervised relation extraction (Craven and Kumlien, 1999), which requires the model to classify the relationship between two entities mentioned in the text. Otherwise, the objective is to predict the relationship between its two neighboring entities, which is similar to traditional KE methods. Masking relation nodes helps CoLAKE (a) learn to do relation extraction, and (b) learn contextualized representation for relations.
However, the pre-training task of predicting masked anchor nodes could be trivial because the model is easy to accomplish this task only based on the knowledge context instead of the language context, which is more varied than knowledge context. To mitigate this, we discard neighbors of anchor nodes in 50% of time during pre-training.

Model Training
CoLAKE is trained with cross-entropy loss. We use three classification heads to predict three types of nodes. In practice, however, the large number of entities brings challenges to training and predicting.
Mixed CPU-GPU Training. Due to the large number of entities in KG, training the whole model in GPU is intractable. To handle this, we asynchronously update entity embeddings in CPU memory while keeping the rest of our model updated in GPU. In particular, we store and update entity embeddings in CPU memory which is shared among multiple trainer processes. During pre-training, the trainer processes read the entity embeddings from the shared CPU memory and write the gradients back to CPU. Our implementation is based on the distributed key-value store (KVStore) from Zheng et al. (2020).
Negative Sampling. Applying the Softmax function to the huge number of entities is very timeconsuming. CoLAKE uses negative sampling to conduct prediction for each entity over one positive entity and k(k n) negative entities instead of all n entities in KG. Following Mikolov et al. (2013), we sample negative entities from the 3/4 powered entity frequency distribution.

Experiments
In this section, we present the details of pre-training and fine-tuning CoLAKE, and its experimental results on knowledge-driven tasks, knowledge probing tasks, and language understanding tasks.

Pre-Training Data and Implementation Details
CoLAKE uses English Wikipedia (2020/03/01) 2 as pre-training data and uses WikiExtractor 3 to process the downloaded Wikipedia dump. We use Wikipedia anchors to align text to Wikidata5M (Wang et al., 2019c), which is a newly proposed large-scale KG containing 21M fact triplets. We construct WK graphs as training samples and filter out graph samples without entity nodes and relation nodes. Finally, CoLAKE pre-trained the Transformer encoder along with 3,085,345 entity embeddings and 822 relation embeddings on 26M training samples.
The Transformer encoder of CoLAKE is initialized with RoBERTa BASE . We use the implementation from HuggingFace's Transformer (Wolf et al., 2019). The entity embeddings and relation embeddings are initialized with the average of the RoBERTa BASE BPE embeddings of entity and relation aliases provided by Wang et al. (2019c). AdamW with β 1 = 0.9, β 2 = 0.98 is used in pre-training. We train CoLAKE with the batch size of 2048 and the learning rate of 1e-4 for 1 epoch. For each anchor node, we sample k = 200 negative entities. CoLAKE is trained on 8 32G NVIDIA V100 GPUs for 38 hours.

Knowledge-Driven Tasks
We first fine-tune and evaluate CoLAKE on knowledge-driven tasks. To annotate entities in the sentence, we use TAGME (Ferragina and Scaiella, 2010) to link mentions to entities in KGs. Instead of replacing the textual mention with its symbolic entity, we follow Pörner et al. (2019) and concatenate the two forms of tokens, e.g. Jean Mara ##is Jean Marais. Concretely, we conduct experiments on two knowledge-driven tasks: entity typing and relation extraction.
Entity Typing. The entity typing task is to classify the semantic type of a given entity mention based on its surface form and context. We add two special tokens, [ENT] and [/ENT], before and after the entity mentions to be classified and use the final representation of the [CLS] token as the feature to conduct classification 4 . We evaluate CoLAKE on Open Entity (Choi et al., 2018). To compare with ERNIE, KnowBERT, and KEPLER, we adopt the same experiment setting which considers nine general types. To be consistent with previous work, we adopt micro precision, recall, and F1 score as evaluation metrics. The experimental results are shown in Table 2.
Relation Extraction. The relation extraction task is to classify the relationship between two entities mentioned in a given sentence. During fine-tuning, we add four special tokens, [HD], [/HD], [TL] and [/TL] to identify the head entity and the tail entity. Also, we use the final representation of the [CLS] token as the feature to be fed into the classifier. We evaluate CoLAKE on FewRel (Han et al., 2018) that is rearranged by Zhang et al. (2019). Since FewRel is built with Wikidata, we discard triplets in the FewRel test set from pre-training data to avoid information leakage. Following previous work, we report macro precision, recall and F1 score on FewRel. The experimental results can be found in Table 2.

Model
Open Entity

Knowledge Probing
LAMA (LAnguage Model Analysis) probe (Petroni et al., 2019) aims to measure factual knowledge stored in language models via cloze-style statement like: Dante was born in [MASK]. Subsequently, a more "factual" subset of LAMA, LAMA-UHN (Pörner et al., 2019), is constructed by filtering out easy-to-answer samples. We evaluate CoLAKE on these two probes and report the mean precision at one (P@1) macro-averaged over relations.
For fair comparision, we use the intersection of the vocabularies for all considered models and construct a common vocabulary of ∼18K case-sensitive tokens. In this experiment, considered models include ELMo (Peters et al., 2018), ELMo5.5B (Peters et al., 2018), BERT BASE (Devlin et al., 2019), RoBERTa BASE , and K-Adapter (Wang et al., 2020b).
The results of LAMA and LAMA-UHN are shown in Table 3. It is worth noticing that BERT outperforms RoBERTa by a large margin. Wang et al. (2020b) reported the same phenomenon in their  Table 3: P@1 on LAMA and LAMA-UHN. * K-Adapter is based on RoBERTa LARGE while other Transformer-based LMs are of BASE size. Besides, K-Adapter uses a subset of T-REx as its training data, which may contribute to its superiority over CoLAKE on LAMA-T-REx and LAMA-UHN-T-REx.
paper. We conjecture that the main reason behind this is the larger and byte-level BPE vocabulary used by RoBERTa. Though, CoLAKE outperforms its baseline, RoBERTa BASE , by a significant margin. Besides, CoLAKE even improves over the LARGE size of model, K-Adapter, by 2.5% and 1.2% on LAMA-Google-RE and LAMA-UHN-Google-RE respectively.

Language Understanding Tasks
We also evaluate CoLAKE on the General Language Understanding Evaluation (GLUE) (Wang et al., 2019a), which provides a collection of diverse NLU tasks. Since these tasks require little factual knowledge, we attempt to explore whether CoLAKE degenerates the performance on these NLU tasks.
The experimental results on GLUE dev set are shown in Table 4. CoLAKE is slightly degraded from RoBERTa but improves over KEPLER by 1.4% on average. We conclude that CoLAKE is able to simultaneously model text and knowledge via the heterogeneous WK graph. In summary, our experiments demonstrate that CoLAKE significantly improves the performance on knowledge-required tasks and at the same time achieves comparable results on language understanding tasks.

Word-Knowledge Graph Completion
Note that CoLAKE is essentially a GNN pre-trained on large-scale WK graphs, which makes it structureaware and easy to generalize to unseen entities. To probe CoLAKE's capability of modeling both structural and semantic features, we design a task named word-knowledge graph completion. In particular, we use the FewRel test set to construct two experimental settings: transductive setting and inductive setting. In both settings, each sample provides a triplet (h, r, t) and a sentence that expresses the triplet. The considered models are required to predict the relation r. For each sample in transductive setting, the two entities, h and t, and their relation r are seen in training phase. But the triplet (h, r, t) has not appeared in the training data. We collect 10K samples from the FewRel test set to construct the transductive setting. For each sample in inductive setting, at least one entity is unseen during training. This setting requires the model to be inductive so that it can generalize to unseen entities. We collect 1K samples from the FewRel test set to construct the inductive setting. We directly evaluate CoLAKE in the two settings without further training on the FewRel training set. The forms of word-knowledge graph are depicted in Figure 4. For inductive setting, we encourage CoLAKE to infer the unseen entity by aggregating messages from its neighbors.
We take several well-known models for link prediction as our baselines 5 . For transductive setting, we compare CoLAKE with four widely-used models, i.e. TransE (Bordes et al., 2013) Figure 4: Illustration of the input word-knowledge graph for transductive setting and inductive setting. In transductive setting, Harry Potter and Lord Voldemort are seen during training. In inductive setting, Harry Potter is unknown but its neighboring entities are seen in training data.

Conclusion
In this paper, we propose CoLAKE to jointly learn contextualized representation for language and knowledge. We integrate the language context and knowledge context in a unified data structure, wordknowledge graph. The experimental results show the effectiveness of CoLAKE on knowledge-required tasks. Besides, to explore the potential application of the WK graph, we design a task named WK graph completion, which shows that CoLAKE is essentially a powerful GNN that is structure-aware and inductive. The surprisingly high performance on WK graph completion inspires the potential applications of WK graph, for example, (a) CoLAKE may help to denoise distantly annotated samples of relation extraction (Craven and Kumlien, 1999;Mintz et al., 2009), (b) CoLAKE can be used to measure the quality of graph-to-text templates (Davison et al., 2019;Bouraoui et al., 2020) due to its capability of preserving the original graph structure. We leave these applications as future work.


extfieldsofstudy:
Computer Science
Physics

s2fieldsofstudy:
Computer Science
Physics

text:
Constructing PineAPPL grids on hardware accelerators

In this proceedings we demonstrate how to implement and construct the PineAPPL grids, designed for fast-interpolation of Monte Carlo simulation with electroweak and QCD corrections, using the VegasFlow framework for Monte Carlo simulation on hardware accelerators. We provide an example of synchronous and asynchronous filling operations of PineAPPL grids from Monte Carlo events generated by VegasFlow. We compare the performance of this procedure on multithreading CPU and GPU.

Introduction and implementation
The fast evaluation of theoretical predictions for a generic set of parton distribution functions [1] and scale variation choices is a common request that has been addressed by generic tools such as APPLGRID [2], FastNLO [3] and more recently PineAPPL [4,5]. In particular, the technology developed by the PineAPPL library provides the possibility to produce fast-interpolation grids of physical cross sections, computed with a general-purpose Monte Carlo generator, accurate to fixed order in the strong, electroweak, and combined strong-electroweak couplings.
In order to construct and use PineAPPL grids we need to interface the code to a Monte Carlo simulation library that generates event weights and kinematics configurations for the grid filling procedure. In this proceedings we use VegasFlow [6,7], a Monte Carlo simulation framework with support for multithreading CPU, single-GPU and multi-GPU setups. The choice of VegasFlow relies on high efficiency when performing simulation thanks to its flexibility to distribute event generation across multiple hardware accelerators. Furthermore, when combined to PDFFlow [8,9], it is possible to perform a full simulation of physical processes with quite competitive performance in comparison to specialized codes.
However, the integration of PineAPPL, or any other external library that expects input from VegasFlow, may generate a natural performance deterioration of the Monte Carlo simulation thanks to operations that may not benefit from the multithreading paradigm of VegasFlow on hardware accelerators. PineAPPL is designed for CPUs and provides to the developer the possibility to be distributed in a multithreading configuration, however it does not provide a GPU implementation and methods for asynchronous grid filling.
In order to provide a solution for such a problem, in Figure 1 we represent schematically the approach proposed here. The Monte Carlo simulation is driven by the VegasFlow framework, which takes care of generating events and distributing them among available devices such as CPUs and/or GPUs. Each batch of events evaluates a large number of matrix element weights and phase space configurations which are subsequently sent to the PineAPPL library for the construction of fast-evaluation grids. In a multithreading CPU and GPU environment, a sequential synchronous fill operation may reduce drastically the performance of the Monte Carlo simulation, by increasing the total amount of time needed to achieve precise predictions. In order to avoid such a performance deterioration, we propose to detach the computation between the VegasFlow Monte Carlo event simulation from the PineAPPL grid filling operation by creating a CPU thread pool that asynchronously queues and executes the operations required by PineAPPL.
From a technical perspective all steps presented in the previous paragraph can be achieved using the Python interfaces of VegasFlow and PineAPPL. In particular, we can generate Monte Carlo events using the eager mode feature in VegasFlow and including an asynchronous job execution CPU thread pool using the standard Python multiprocessing module1.

Measuring performance
In order to test the asynchronous approach proposed in the previous section, we use VegasFlow with a simplified simulation of Drell-Yan, which only calculates the leading-order matrix element for the photon-induced process, γγ → ¯ . The simple structure of the corresponding matrix element and phase space allows to easily test a wide range of phase-space points. Furthermore, the evaluation is cheap enough to highlight the overhead of filling a PineAPPL grid, which is basically a constant of the number of partonic processes; when simulating more complex processes, we therefore expect the relative overhead to be much lower.
At the end of each batch of events, we compute a PineAPPL grid for the |y ¯ | observable. In terms of physical cuts we consider a single invariant-mass slice of a CMS 8 TeV analysis [10], which requires 60 < m ¯ < 120 GeV, p T > 14 GeV, |y ¯ | < 2.4 and |y | < 2.4. From the VegasFlow point of view we tested the performance by increasing number of events before cuts from 10 3 to 10 9 , using the default maximum number of events per device of 10 6 .
In the left plot of Figure 2 we show the total computing time of the Monte Carlo simulation for an increasing number of events. We compare runs without PineAPPL (green) to the synchronous (blue) and asynchronous (orange) approaches with PineAPPL. Similarly, on the right plot of Figure 2, we present performance results on GPU. The synchronous approach produces a performance deterioration up to ≈ 30% on CPU and ≈ 80% on GPU, while the asynchronous approach reduces the overall deterioration by ≈ 10%. The main advantage of the asynchronous approach is the possibility to detach the Monte Carlo event simulation from the operations related to the construction of PineAPPL grids. From the Monte Carlo simulation perspective we observe a negligible overhead due to the submission of asynchronous jobs. On the other hand, the CPU thread pool, used by the asynchronous job, can be further optimized depending on the available system resources. Note that the system used for the performance measurement in Figure 2 has a fast clock CPU thus the expect larger performance deteriorations on average professional grade hardware.  VegasFlow and PineAPPL on CPU (left) and GPU (right). The synchronous approach produces a performance deterioration up to ≈ 30% on CPU and ≈ 80% on GPU, while the asynchronous approach reduces the overall deterioration by ≈ 10%. Note that the asynchronous approach detaches the Monte Carlo integration from the grid filling operations providing further options for optimization.

Outlook
The example presented in this proceedings shows that an asynchronous approach to filling fastinterpolation grids using PineAPPL is feasible and provides a useful interface to detach Monte Carlo event simulation from sequential operations without introducing a strong performance deterioration.
We have compared the performance of synchronous and asynchronous approaches on CPU and GPU for a leading-order Drell-Yan photon-induced simulation. As expected, the performance from an asynchronous approach outperforms the sequential synchronous mechanism and does not introduce overheads to the Monte Carlo event simulation.
The code for the exercise presented in this manuscript is public available at the VegasFlow repository [6,7] inside the examples folder.


Adaptive Density Graph-Based Manifold Alignment for Fingerprinting Indoor Localization

The received signal strength (RSS) fingerprint-based indoor localization has been considered as a promising solution, due to its relatively high localization accuracy and its ease of use in widespread Wireless Local Area Network (WLAN) infrastructure. A major bottleneck is that the offline fingerprint calibration is time consuming and labor intensive. In this study, inspired by our analysis that multi-density is inherent to the RSS distribution, we present a new radio map construction scheme, called Adaptive Density Graph-based Manifold Alignment (ADG-MA), which can reduce the number of Reference Points (RPs) in offline phase. In particular, it utilizes the density features to capture the exact neighborhood relations of RSS. Furthermore, the approach labels the RSS from user traces to construct the radio map. The extensive experiments demonstrate that the proposed method can construct an accurate radio map at a low deployment cost, as well as achieve a high localization accuracy.

I. INTRODUCTION
With the unceasing development of wireless communication technology, computer technology and the demand of Location-based Services (LBSs), the indoor wireless localization techniques are of growing interest and becoming increasingly prevalent [1]. Indoor localization has a wide range of applications in indoor navigation and localization, industrial goods management, fixed-point market advertising delivery, game development and smart home. So far, many techniques have been applied to indoor localization, such as infrared ray, ultrasound, radio frequency identification device (RFID) [2], Bluetooth, ultra-wideband (UWB), magnetic field and Wireless Local Area Network (WLAN) [3]. At present, the localization technology based on WLAN mainly includes localization based on Time of Arrival (TOA) [4], Time Difference of Arrival (TDOA) [5], Angle of Arrival (AOA) [6] and Received Signal Strength (RSS) [7]. Compared with other localization algorithms, WLAN fingerprint-based localization scheme is widely used The associate editor coordinating the review of this manuscript and approving it for publication was Jenny Mahoney.
because of its advantages such as low transmission bandwidth requirements, high localization accuracy and no need for additional hardware deployment.
The WLAN fingerprint-based localization approach mainly involves two phases, namely offline phase and online phase [8]. In offline phase, several Reference Points (RPs) are selected uniformly or randomly in the survey area. Then, a survey is conducted and multiple copies of RSS measurements are read at each RP from available Access Points (APs) to construct the radio map. Due to the complexity of wireless Wi-Fi signal propagation and the effect of multi-path fading and shadow effect, the RSS signal of the same AP at a certain RP usually has complex time-changing characteristics, so it needs to collect data repeatedly at the RP to improve the accuracy of the radio map. In the online phase, the newlycollected RSS signals are matched against the signals in the radio map by matching algorithms (e.g. KNN [9]) to calculate the location of the user.
It is obvious that it needs to collect and train numerous labeled RSS data in the offline process. For example, in the process of constructing radio map of a 3.6 m × 7.2 m small office area using the traditional radio map construction algorithm, in order to ensure the localization accuracy of the traditional radio map, it needs to collect 72 RPs in total, which are evenly distributed with 0.6-m intervals as usual [10]. It needs to collect data from four directions, one minute in each direction. So it takes 4.8 hours to construct the radio map. In this situation, the huge consumption of data acquisition restricts the popularity of fingerprint-based localization scheme. Therefore, how to propose a radio map construction algorithm with less manual cost and higher precision has attracted more and more attention.
Moreover, recent indoor localization application scenarios tend to be large-scale, and the high-dimensional RSS data distribution presents multiple densities features. It is mainly caused by the following two reasons. The first reason is that the indoor layout is complex. Due to the different uses of indoor areas, indoor structures are often complex and diverse in a localization scene. The location of AP is the other reason. Under normal circumstances, the wireless AP arrangement in the indoor scene is to meet the demands of the users communication, rather than the need of indoor localization. These two indoor characteristics lead to uneven distribution of RSS data, and different parts of the data exhibit the characteristic of multi-density. Multi-density RSS data have a great impact on the construction of the radio map and the final localization accuracy. To the best of our knowledge, this issue has not been noticed by the related researchers.
In this paper, considering the inherent multi-density distribution characteristics of indoor RSS data, we design the new Adaptive Density Graph-based Manifold Alignment (ADG-MA) method to calibrate the locations of plenty of unlabeled data by a small number of labeled RSS for the construction of radio map. The basic idea of this paper is to reduce the ratio of labeled data by constructing a weighted graph that can better show the RSS neighbor connections and capture the inherent relationships of different RSS data.
Due to the adaptation of RSS data density in complex scenes, the algorithm in this paper has a more extensive application scenario. The three main contributions are summarized as follows. First of all, we analyze the distribution characteristics of high-dimensional RSS data in multiple scenes by data density and visualization analysis methods. Second, we propose a novel method to create the neighborhood weight matrix of RSS, which can capture the multi-density characteristics of RSS. Third, we utilize the correlation relations of RSS implied by area labels to optimize weight matrix, which is used by the newly-design ADG-MA to construct an accurate radio map with only a small number of labeled RSS.
The main contribution of this paper is as follows.

·
We analyse different datasets in the localization scenes and find out that density parameters of different RPs are quite different. Then, we get the projection of RSS samples in 2D space. The clusters show a significant density difference. We summarize it as the characteristics of multi-density distribution of RSS.

·
In this paper, inspired by our analysis that multi-density is inherent to the RSS distribution, we present a new radio map construction scheme, called Adaptive Density Graph-based Manifold Alignment (ADG-MA), which can reduce the number of Reference Points (RPs) in offline phase. · We design the experiments to verify the efficiency and effectiveness of the proposed ADG-MA. The proposed scheme can improve the localization accuracy and reduce the time cost in offline phase.
The structure of this paper is as follows. In Section II, we review the previous related work. In Section III, the characteristics of multi-density distribution of RSS in the localization scenes are analyzed. In Section IV, the algorithm of constructing adaptive weighted graph for multi-density data is proposed, and it applies to constructing radio map with manifold alignment. In Section V, the analysis based on experiments is used to verify the performance of the proposed radio map construction approach. In Section VI, we give the conclusion of this paper.

II. RELATED WORK A. THE CONSTRUCTION APPROACHES FOR RADIO MAP
Generally, the radio map stores the mathematical characteristics of RSS collected at the certain RP. The deterministic approaches usually store the mean value, maximum value, etc. Probabilistic algorithms usually store the statistical characteristics of the RSS at RP, and they are mainly divided into two types, parametric and non-parametric estimation. For instance, the radio map in [11] stores histogram of whole data. The radio map in [12] stores the Gaussian distribution parameters. Because the indoor environment is complex and varied, in order to improve the accuracy of localization, many researchers have put forward different forms of radio map based on empirical statistics. The authors in [13] propose that the RSS distribution is non-Gaussian and left-skewed. The radio map stores the corresponding parameters of the distribution characteristics. However, no matter what features are stored in the radio map, in the offline phase, it requires to collect numerous RSS data from plenty of RPs, which needs a huge manual cost.
For this disadvantage of fingerprint-based localization, the researchers proposed propagation model-based construction algorithms [14], dynamic radio map construction [15], crowdsourcing approaches [16]- [18] and the construction methods based on semi-supervised manifold learning [19]- [22]. The crowdsourcing approaches use many nonprofessional users to contribute locations and RSS data information, and build a radio map through a server. However, due to the introduction of non-professional data, this method introduces a large number of abnormal data. In addition, the system also needs to filter the malicious users interference. It may increase the processing burden of the system and reduce the accuracy of the radio map. VOLUME 8, 2020

B. THE SEMI-SUPERVISED LEARNING APPROACHES FOR LOCALIZATION
The semi-supervised learning method achieves the calibration of a large number of unlabeled data through a limited number of labeled RSS. During the construction of the radio map, the unlabeled RSS data can be easily collected through random traces creating by users. Based on this advantage, the authors in [19] use semi-supervised learning to construct the radio map. The idea is to obtain the coordinates of the unlabeled data by the positions of a limited number of labeled RSS data, and to realize the construction of the hybrid radio map. The semi-supervised manifold learning method not only utilizes the distance information represented by the RSS value to locate the user, but also considers the manifold geometry features of the RSS data. At the same time, the prior information of the labeled RSS data can be fully utilized. And the manifold learning can capture the nonlinear features of RSS for localization. Therefore, due to these potential characteristics of manifold learning methods and their advantages in localization accuracy, they have received a lot of attention in recent years.
The authors in [20] propose a method of using the manifold regularization to obtain the positions of mobile nodes and APs through joint collaborative filtering, while the experiment is only based on the Line-of-sight (LOS) condition. The authors in [21] use the manifold learning to introduce coordinate dataset and RSS dataset. Through the correspondence between the data in two datasets, the corresponding low-dimensional eigenvectors are calculated, and the position of unlabeled data can be obtained through the similarity of eigenvectors. However, the coordinate dataset in this method needs to accurately reflect the indoor layout structure. In general, the semi-supervised manifold alignment method considers Laplacian graph as a discrete approximation of RSS manifold structure [23]. The authors in [22] propose a hybrid semi-supervised manifold alignment radio map construction method, and meanwhile utilize RSS data to construct Laplacian graph. It preserves the similarities of high-dimensional RSS by the timestamp information of unlabeled data, and completes construction of the radio map through manifold alignment.
However, Laplacian graph used in [20], [22] usually utilizes the k-Nearest Neighbor graph (k-NN graph) to build the weight matrix without considering the effect of data density. Due to the nearest neighbor number k, it is a global fixed factor. When the data is sparse, the data vertices in the weighted graph are over-connected [24]. In this situation, the distance between the neighbor points is quite large and it cannot accurately reflect the neighbor relationship of the data points. It is not conducive to the spread of labeled coordinates in the process of manifold alignment, and it affects the performance of indoor localization. Instead of using k-NN graph by conventional methods, the proposed ADG-MA utilizes local density of RSS and shared nearest neighbor similarity to construct the Laplacian graph. Meanwhile, this paper uses area labels of all RSS data to weaken neighbor connections of dissimilar data, ensuring that the weighted graph can accurately reflect the neighborhood relations of all RSS data, which can improve the accuracy of the radio map.

III. THE FEATURE ANALYSIS OF RSS DATA DISTRIBUTION A. THE FEATURE ANALYSIS
The application scenarios of indoor localization tend to be complicated. In this type of scenarios, there are numerous APs and the wireless communication environment is changeable. The dimension of the RSS vector in the localization process is equal to the number of APs, which indicates that the high dimension RSS data is stored in the radio map. However, the features of the high-dimensional data are complex, and it is difficult to select an appropriate algorithm to extract the RSS features. In this section, the density parameter method and the data dimension reduction algorithm called Linear Discriminant Analysis (LDA) [25] are used to analyze the RSS data in the complex scenarios, and the distribution characteristics of the high dimension RSS data are obtained.
According to the data density parameter proposed by [26], the ρ i is defined as where χ (x) = 1 if x < 0 and χ (x) = 0 otherwise. d ij represents the distances between RSS data points. d c represents the cutoff distance. The data density ρ i denotes the number of data that are closer than d c to the data point i. d c is an empirical parameter, which has good robustness to adapt to large data sets. We utilize d c to calculate the data density ρ i which is a standard of the distributions of RSS density about different datasets. We first analyze the TUT dataset [27], UJIindoorLoc dataset [28] and RSS fingerprint data in our experiment scene of an office building. Then, we calculate the distribution of data density and the results are as shown in Fig. 1. The values of inter-quartile range are 25,16,13 respectively, which presents the span of the data density is large. Fig. 2 shows the data density of 120 RPs in TUT dataset. It can be seen that the density parameters of different RPs are quite different. Further, the distribution characteristics of the projection in 2D of high-dimensional RSS data are analyzed. The RSS data of 2 rooms on the second floor of UJIindoorLoc dataset are processed by LDA. LDA is a fundamental data analysis approach based on Fisher's criterion, which is also a supervised method. It can obtain projections of high-dimensional data in the low-dimensional space by minimizing the withinclass scatter and the maximum between-class scatter during the dimensionality reduction process. The between-class S W and within-class S B scatter matrices are defined as where N represents the number of RPs, n represents the number of APs. P represents the number of all RSS vectors, r i and r represent the mean of RSS at i-th fingerprint point and the mean value of all RSS vectors respectively. r i (m) represents the m-th RSS vector of i-th RP. Then, it can reduce the dimension of data to a chosen L = 2 by projecting onto the linear subspace. The optimal result can be obtained by computing the following objective function: where is the basis vector of subspace. Then, we can get the LDA projection of RSS samples in 2D space as shown in Fig. 3. As we can see, the RSS data are divided into two clusters, and the clusters show a significant density difference.
In summary, the RSS data in the localization scene show obvious multi-density distribution characteristics in high dimension space and low dimension projection space. The uneven density of RSS data is common in multiple localization scenes, which affects the accuracy of the localization. This paper aims to design a weighted graph construction algorithm adapted to the multi-density distribution of RSS data to improve the accuracy of labeling the data in the manifold alignment process.

B. THE MULTI-DENSITY FEATURE
The RSS multi-density feature is used to characterize the non-uniformity of the distribution of RSS vectors in high-dimensional data space. Specifically, in the same distance range, RSS vectors in dense regions have more neighbors. Similarly, in the sparse regions, there is a big difference in the distances between neighbors. The multi-density feature of RSS distribution is shown as Fig. 4. Different points in the figure represent different types of RSS vectors. The thickness of the lines between points indicates the similarity of points in the weight graph. Fig. 4(a) shows three types of RSS points with uneven distribution in the high-dimensional space. The points in the same type are closer than the points in different types, it means that the connections between RSS vectors of same type are stronger than that between RSS vectors of different type. Fig. 4(b) is the result of the weight graph which is created in the conventional method [29]. As the dotted line shows, only considering the distance metric and ignoring the RSS multi-density feature would result in a tighter connection between different types of RSS data, which in turn would affect the accuracy of the weight graph.

IV. ADG-MA FOR RADIO MAP CONSTRUCTION A. THE WORKFLOW
In this paper, we propose to use the local RSS density factor, shared nearest neighbor similarity and area information to create the neighbor weight matrix. Then, the manifold alignment is performed for the construction of radio map. The architecture of the proposed system is shown in Fig. 5. In the offline phase, we use a mobile phone to measure RSS from n APs, and the number of RPs in target environment is N , the number of RSS collected by multiple VOLUME 8, 2020 user traces is M . Less APs lead to the decrease of positioning accuracy and more APs result in the increase of positioning complexity. This paper mainly analyzes the performance under reasonable APs distribution. The total collected RSS can be represented as R = (r 1 , r 2 , · · · , r N +M ) T , where r i = (r i1 , r i2 , · · · , r in ) (i ∈ [1, N + M ]) represents all RSS data at the i-th point. R f = (r 1 , r 2 , · · · , r N ) T represents the labeled RSS data collected at a certain RP and R u = (r N +1 , r N +2 , · · · , r M ) T represents the unlabeled RSS data of users traces respectively. The coordinates can be represented as P = p 1 , p 2 , · · · , p N +M T , where P f = p 1 , p 2 , · · · , p N T stands for the coordinates of RPs corresponding to R f , and P u represents the coordinates of unlabeled data. We initially set the random values to P u . Firstly, the mixed data matrix R is made up of the labeled data R f and the unlabeled data R u . According to the multi-density characteristics of the RSS data and the area information, the adaptive local density matrix W d is constructed, and the geometric structure model of the RSS manifold is obtained as G = {R, W d }. Secondly, the multi-density graph Laplacian is constructed on the basis of W d . The locations of unlabeled data are calibrated by manifold alignment, and the radio map is constructed with the whole RSS data. Finally, the user location estimation can be realized by KNN.

B. ADAPTIVE LOCAL DENSITY WEIGHTED GRAPH CONSTRUCTION 1) LOCAL DENSITY SIMILARITY MATRIX CONSTRUCTION
According to Section III, the RSS data in the localization scene have different local density characteristics. The local density factor is calculated by the distance statistics of the neighbor points, and the local density factor [30] is calculated by where δ i represents the Sorensen distance [29] of r i to its k-th nearest neighbor point r k . Considering the impact of local density, the distance from r i to r j is defined as Normally, the square distance is calculated as d 2 s r i , r j δ i δ j , and the similarity of r i and r j can be represented by the radial basis function (RBF) where α is the user control factor of the RBF. Only when the adjusted d ij and d ji are both small, it can obtain the bigger value. When d s is smaller than δ i and δ j , r i is more similar to r j . Then, (5) can ensure that the similar r i and r j in the high-dimensional space have the same magnitude of density.

2) SHARED NEAREST NEIGHBOR SIMILARITY
Similar RSS vectors in high-dimensional space have more common neighbors. In order to further prevent excessive connections between dissimilar RSS vectors, the similarity is calculated by where N k (r i ) ⊆ R. Substituting the above equation into (6), the similarity of r i and r j can be defined aŝ

3) THE WEIGHTED GRAPH CONSTRUCTION OF AREA INFORMATION OPTIMIZATION
In the offline phase, different data are collected from different areas. Therefore, area information stands for the potential labeled messages. Although the samples that in the same physical sub-region are not necessary belong to the same cluster after clustered in the signal space. The RSS data in different areas are more likely to have less similarity. We can divide different areas by k-means. We can set the area label of r i as area (r i ) and compute weight matrix by where θ r i , r j is area weighting factor, which is defined to reduce the connection weight of data from different areas.
If r i and r j have the same area label, θ r i , r j = γ 1 = 1; if not, θ r i , r j = γ 2 < 1. Finally, we can get adaptive local density neighborhood weighted graph G = {R, W d } and weight matrix W d = W ij (N +M )×(N +M ) . Fig. 6 provides the effect of the proposed method. x, y and z indicate three sets of RSS points in two clusters which satisfy 4948 VOLUME 8, 2020 d s (x, y) = d s (x, z). We use lines to connect the neighbors of points, x and y have common neighbors which are connected by them. In Fig. 6(a), two clusters of RSS data have the similar densities. S r x , r y > S (r x , r z ), which indicates that x and y have more common neighbors. We can get that x and y have larger connecting weight according to (8). In Fig. 6(b), the RSS data have a huge density difference. Fig. 6b shows that δ z < δ x and δ x ≈ δ y . We can get that the weight between x and z is smaller than the weight between x and y according to (8), so the connection between x and z is weaker.

C. ADG-MA LOCALIZATION
In offline phase, the low-dimensional mapping coordinates of the collected high-dimensional RSS data R are assumed to be C = (c 1 , c 2 , · · · , c N +M ). In order to maintain the manifold structure and calculate the low dimensional mapping coordinates of unlabeled RSS data, the Laplacian Eigenmap [31] is introduced. Then we get optimal mapping by: where tr (•) presents the trace of the matrix, L d = D d − W d is the Laplacian matrix [32], which is also a positive semidefinite matrix, and D d is a diagonal matrix with Considering the RSS manifold, the prior low dimensional manifold coordinates of subset R f are known. It means that pairwise correspondences between R f and P f are known. We construct the following convex differentiable objective function as The first part in (10) is the fitting error, which penalizes the difference between the low-dimensional embedding coordinates of RSS and the location coordinates. And the second one is the regularized manifold constraint, which can preserve the structure of the RSS manifold in the low-dimensional space to enforce smoothness along the manifold. µ is a tradeoff parameter.
Notice that ∂C T L d C ∂C = L d + L d T C, the above problems can be solved by standard linear algebra, and we can get the optimal solution by taking the derivative of the right side of (10) is the joint graph Laplacian matrix.
is the multi-density weight matrix obtained in Section IV-B. The first N -th rows and Nth columns of W d indicate the neighborhood weight with respect to labeled RSS data. The last M -th rows and M -th columns of W d indicate the neighbor connection weight with respect to RSS data which is collected through random traces. W lu indicates the neighborhood weight between labeled RSS data and unlabeled RSS data collected through random traces.
is an indication matrix, where ϕ i = 1 if the coordinate of the r i is given and otherwise ϕ i = 0. At last, the latter M rows of mapping matrix C are the low dimensional mapping coordinates of unlabeled RSS data.
D. DETAILED PROCESS OF THE ADG-MA step 1 Calculate Sorensen distance between all RSS vectors. Compute δ of the whole RSS by N k . step 2 Calculate the shared nearest neighbor similarity of RSS which are represented as S r i , r j according to (6). Combining with the result of step 1 to obtain the similarity matrixÂ = Â ij (N +M )×(N +M ) .
step 3 Use area information to determine γ 2 . Adjust the similarity matrix in step 2 and obtain weight matrix W d . Construct the weight graph G = {R, W d }. step 4 Calculate the non-normalized Laplacian matrix Construct joint Laplacian graph to reflect RSS manifold connection structure. step 5 According to (10), optimize the manifold alignment objective function which contains L d to obtain physical locations C. step 6 Joint R f , P f and the corresponding parts of C and R u to complete the construction of the radio map.

A. EXPERIMENT SETTING
To evaluate the performance of the proposed algorithm in real environments, the test bed is setup in a building located in China University of Petroleum (East China) as VOLUME 8, 2020 shown in Fig. 7

B. LOCALIZATION PERFORMANCE
In this section, we focus on the localization performance by using the proposed manifold radio map and other four radio maps constructed by RADAR [9], KNN-graph-based Manifold Alignment (KG-MA) [33], Locally Linear Embeddingbased Manifold Alignment (LLE-MA) [21] and LE-MA [22]. Fig. 8 depicts the corresponding cumulative distribution function (CDF) of localization errors for each radio maps. When the localization error is 3.5m, the cumulative probability of ADG-MA, KG-MA, LLE-MA, LE-MA and Radar are 74.2%, 57.5%, 57.0%, 66.0% and 52.0% respectively. From this result, we can find that the proposed radio map outperforms the other methods in localization accuracy. As discussed above, the proposed algorithm could capture the potential multi-density feature of RSS data to construct graph Laplacian which reduces the effect of density on the RSS similarity in a complex indoor environment. The conventional manifold alignment approaches only utilize global parameter k to compute the neighborhood weight matrices. Thus, the negative influence of density causes a decline in the localization accuracy. Fig. 9 compares the CDFs of localization errors by using the proposed algorithm with and without area labels. From this figure, it can be seen that the localization accuracy with area labels is at least 5% higher than the one without area labels. It can be inferred that the area labels contain the inherent neighborhood relations of RSS samples, which is beneficial to calculate the coordinate of unlabeled RSS data.     10 depicts the percentage degradation in mean localization errors performance, compared to the reference of localization accuracy with full fingerprints. In comparison with the full fingerprints performance, the results show that our proposed algorithm can achieve a degradation in localization error of 28% as the ratio of labeled RSS is reduced by 80%, while the one by the RADAR,LLE-MA and LE-MA achieve degradations of 103%,50% and 33% respectively. The ADG-MA algorithm is more robust to the reduction of the ratio of labeled RPs and can ensure the localization accuracy. Fig. 11 shows the contrast of the manual time cost of the three radio map construction methods with the ratio of the labeled RPs increasing. When the ratio of labeled RPs is 1, in order to capture RSS variation property, the traditional radio map construction requires collecting 360 RSS samples at each one of 412 labeled RPs from four orientations, the time cost for the RADAR radio map construction is 41.2 (=412 × 360/3600)h. However, the proposed method only requires 20 RSS samples each RP, and the total time cost is 2.6 (=(412 × 20 + 1145)/3600)h. Meanwhile, the computational time for the manifold algorithm is approximately 42 seconds, and it can be ignored for the reason that it is too small relative to the manual time cost.  Fig. 12 shows the mean localization errors with respect to γ 2 . As can be seen from this figure, the mean localization error reaches minimum when γ 2 = 0.8, therefore, the weight of area label is selected to be 0.8 in our system.   error reaches 3.12 m when the value of k grows to 20. The figure clearly shows that the number of shared nearest neighbors in multi-density weight calculation is a significant factor in determining the localization error level. This result can be interpreted by the fact that the influence of RSS density is powerful when the number of shared nearest neighbors is small. When the number of shared nearest neighbors become too large, the RSS neighbors may span a significant distance. Thus, the constructed neighborhood weight graph fails to reflect the RSS connection relations.

VI. CONCLUSION
In this paper, a new approach of reducing the cost of radio map construction has been proposed. We present the novel neighborhood weight matrix to capture the multi-density feature and connection relations of RSS. In addition, we utilize it to obtain the coordinates of the unlabeled RSS to construct the radio map through manifold alignment. And it is confirmed that the proposed method can cut down the deployment cost for the offline radio map construction and guarantee the localization accuracy. The experiments verify the efficiency and effectiveness of the proposed ADG-MA. In future, we will also characterize the local RSS geometries using the other manifold approaches to further improve the precision and stability of radio map. SHIBAO


Proactive DDoS Attack Mitigation in Cloud-Fog Environment using Moving Target Defense

Distributed Denial of Service (DDoS) attacks are serious cyber attacks and mitigating DDoS attacks in cloud is a topic of ongoing research interest which remains a major security challenge. Fog computing is an extension of cloud computing which has been used to secure cloud. Moving Target Defense (MTD) is a newly recognized, proactive security defense that can be used to mitigate DDoS attacks on cloud. MTD intends to make a system dynamic in nature and uncertain by changing attack surface continuously to confuse attackers. In this paper, a novel DDoS mitigation framework is presented to support Cloud-Fog Platform using MTD technique (CFPM). CFPM applies migration MTD technique at fog layer to mitigate DDoS attacks in cloud. It detects attacker among all the legitimate clients proactively at the fog layer and isolate it from innocent clients. CFPM uses an effective request handling procedure for load balancing and attacker isolation procedure which aims to minimize disruption to cloud server as well as serving fog servers. In addition, effectiveness of CFPM is evaluated by analyzing the behavior of the system before and after attack, considering different possible scenarios. This approach is effective as it uses the advantage of both MTD technique and Fog computing paradigm supporting cloud environment.

INTRODUCTION
Amongst the diverse threats to cyber security Distributed denial-of-service (DDoS) attack [1]- [3] is most prevailing nowadays. In DDoS attacks, target is overloaded with enormous traffic by a large number of connected devices that are distributed across the Internet. This results in loss of equipment resources and network bandwidth.
Securing cloud from these attacks has become a big challenge [4]- [6]. Cloud servers have the potential to perform computing and storage tasks, without the direct involvement of user. But as they are faraway, it is required to send all the raw data (could be sensitive) to the cloud servers over the internet which may have some privacy and security issues. Various DDoS attack handling techniques in cloud [7]- [9] are proposed.
Fog computing or fogging [10], is a decentralized computing infrastructure that distributes data, services of computing, storage, networking and communications between the cloud and the data source. Fog computing is basically an extension of cloud computing. In order to provide faster ICT services to the end users, it brings cloud computing capabilities to the edge of the network. The goal of fogging is to enhance efficiency by reducing the total amount of sensitive data that is transported to the cloud for analysis, storage and processing [11].
Though fog computing conserves network bandwidth and improves system response time but at the same time it is also prone to cyber attacks such as DDoS attacks. As the capacity of each fog node is restricted, these attacks can be detrimental to fog computing's availability also [12]. As of now it is critical to secure cloud with additional measures as fog layer alone is not sufficient enough.
One newly recognized cyber defense strategy, which helps in mitigating DDoS attacks is introduced i.e. Moving Target Defense (MTD) [13]- [15]. MTD keeps the network environment less deterministic and unpredictable by continuously changing the attack surface. This uncertainity induces confusion for attackers, simultaneously increasing the attacker's time, efforts, and cost while decreasing the cost of defensive strategies. MTD has its potential applications in various areas. In the literature Fog computing and MTD has been used separately for cloud security. Also MTD techniques have not been applied to fog computing paradigm.
In this paper an approach CFPM is presented, which mitigates DDoS attacks in Cloud-Fog Platform using Moving Target Defense(MTD) as the underlying tech-nique. CFPM monitors the traffic generated from all the connected users to look for abnormalities. It handles the DDoS attack at fog layer using the concept of migration MTD. Migration MTD is a dynamic platform diversification MTD technique. This approach is effective as it takes the advantage of both Fog computing and MTD to secure cloud.

RELATED WORK
Several techniques have been developed to mitigate the impact of DDoS attacks in cloud [7], [8]. Ahmed et al. [9] investigated such mitigation techniques and compared them in cloud environment. Fog computing [10] is one of the promising way to deal with such attacks in cloud. Decoy information technology called Fog computing has been used by the authors in [11] to secure the cloud. But fog computing itself is susceptible to such attacks, which is investigated by the authors in [12] as fog devices work at the bottom/edge of networks.
MTD emerged as a promising approach to network security. Li Jason et al. [15] productized MTD research technology, called Self-shielding Dynamic Network Architecture (SDNA) technology, now known as Cryptonite NXT. MTD intends to create asymmetric uncertainty on the attacker's side by constantly changing the attack surface. Zheng et al. [16] presented a comprehensive survey on MTD and its implementation strategies from architectural perspective.
Based on the kind of changes MTD is making to the system it has been classified into four categories i.e., Software based diversification , Runtime based diversification, Communication diversification and Dynamic Platform diversification by the authors in [17]. MTD has its potential applications in various areas. Different MTD techniques have been applied in different domains. Authors in [18], [19] have applied runtime based diversification MTD techniques i.e., instruction-set randomization and address-space randomization to counter attack. Jackson et al. [20] have used software based diversification MTD techniques i.e., software diversity and compiler generated diversity and evaluated their effectiveness. Al-Saher et al. [21] presented a MTD architecture called mutable networks(MUTE) which uses communication diversification MTD technique i.e., IP address randomization. Thompson et al. [22] proposes an approach that applies rotation of multiple operating systems to enhance security i.e. diversity technique has been used which comes under dynamic platform diversification MTD.
Zhuang et al. [23] applied simulation-based experiments to explain enhanced efficiency due to the introduction of diversification and randomization in the system. Comparison of different MTD techniques has been proposed by the authors in [24]. Authors in [25], [26] studied the effectiveness of MTD using security models and investigated applications of MTD to network security. Okhravi et al. [27], [28] has applied dynamic platform diversification MTD technique as defense mechansim on critical infrastructure. MTD has been used for mitigation of DDoS attacks against a proxy based architecture by the authors in [29]- [32]. Authors in [33], [34] have used dynamic platform diversification i.e. shuffle MTD as the underlying MTD technique to mitigate DDoS attack proactively at proxy layer.
Peng et al. [35] ascertained whether MTD is effective in protecting Cloud-based services and if yes, upto what extent, with heterogeneous and dynamic attack surfaces. Wang et al. [36] proposed a cost effective defense against DDoS and Covert channel attacks using MTD. Authors in [37] have used IP address randomization as MTD technique for cloud computing platform. The authors in [38], [39] have combined differnt dynamic platform diversification MTD techniques i.e, Shuffle and Diversity and evaluated it for cloud computing. This combined approach is very efficient as it amplifies randomization. So due to its promising capabilities MTD is a suitable strategy for addressing cloud computing security issues. But MTD has not been applied to fog paradigm in the field of research in past. Bazm et al. [40] evaluated that MTD can be applied to both multi-cloud and decentralized cloud infrastructures such as Fog.
This paper presents an approach CFPM that mitigates DDoS attack in a combined Cloud-Fog Platform using dynamic platform diversification MTD technique i.e., migration MTD technique.

Overview
The proposed approach CFPM, mitigates DDoS attacks in the cloud by using the concept of fog computing with migration moving target defense technique. Fig.  1 shows the proposed architecture, which consists of 3 components: 1) (a) cloud servers 2) (b) fog layer comprising of many fog servers 3) (c) users (both innocent and malicious) Fog servers present in the fog layer are in two modes i.e. sleep mode or active mode. Active fog servers are used for serving the users and the grey colored fog server i.e., sleeping fog server is activated only if any attacker is detected so sleeping fog server is named as Attack Fog server. Number of sleeping fog servers are very less compared to active fog servers.
This architecture permits the user to access the services provided by fog servers only after successful authentication. User before connecting to any fog server mention the maximum requests it can send per second and at the time of requesting it passes its current need.
A fog server can serve many users and a user can request any number of times in a second until or unless it has reached its limit i.e., it has requested the maximum number of requests in total that it has mentioned at the time of connection. If the request can not be handled at the fog layer i.e., all fog servers are fully occupied, then only the request is passed to the cloud server.  Table 1 shows various notations used in the CFPM approach presented in this paper.  Fig. 2 shows the structure of Flag[ ] variable, which defines the state of each fog server using 3 fields as follows:

Preliminaries
1) Mode Bit: • If set to 0, then it signifies the fog server is in sleep mode.
• If set to 1, then it signifies the fog server is in active mode. 2) Free Bit: • If set to 0, then it signifies the fog server is fully occupied. • If set to 1, then it signifies the fog server can serve more requests. 3) Sum: It is the sum of the entries in countfid[ ] array maintained for each fog server i.e., the total number of requests served by a fog server.

PROPOSED SCHEME
In this section details of the proposed scheme are discussed.

Initial Assignment
For the initial assignment of all the local and global variables used in CFPM approach, Algorithm 1 is executed. end for 11: end function 12: function LOCAL-ASSIGN 13: for every fid do 14: for int i = 1 to do 15: countfid[i] = 0; 16: end for 17: end for 18: end function After each second GLOBAL-ASSIGN() and LOCAL-ASSIGN() functions are called to initialize the variables. For all fog servers mode bit in Flag[ ] variable is initialized at the time of fog server creation.

Request Sending Procedure
Whenever any user sends a request to a fog server or a fog server sends a request to another fog server, then Algorithm 2 is executed. Firstly it is checked whether there is any active free fog server available or not by accessing the mode bit and free bit of Flag[ ] variable for all fog servers. If for all fog servers free bit is 0 i.e., no fog server is free to serve the request, then the request is send to the cloud server.
Otherwise if for any fog server mode bit and free bit is 1, then it is checked whether the request is from user or neighboring fog server. If request is from user, then HANDLE-REQUEST(uid, need) function is called in which the user id of the user to be served is passed along with its current need. Otherwise if the request is from another fog server, then SERVE(uid, rem) function is called and, the user id of the user is passed for which the requested fog server was unable to serve along with the remaining need of the user.

Request Handling Procedure
Whenever any fog server receives a request from a user or any other neighboring fog server it runs Algorithm 3.
If the request is from user, then HANDLE-REQUEST(uid, need) function is called otherwise if the request is from another fog server, then only SERVE(uid, need) function is called.
In HANDLE-REQUEST(uid, need) function the account[uid] value of the user to be served is accessed. If the value is not null i.e, the user is not present in blacklist, then the fog server updates the account [uid] value by adding the current need of the user into it. Then it calculate the score[uid] value using Eq. 1. value, then ACTIVATE-ATTACKFOG(uid) function is called by the fog server to deal with the attacker who is trying to send more requests than its maximum requests. Otherwise if score[uid] value is less than or equal to the limit[uid] value, then fog server accepts the user request and calls SERVE(uid, need) function.
In SERVE(uid, need) function fog server updates the count[uid] value by adding the need value. It then calculates the total number of requests it is currently serving i.e., sum of the entries of its countfid[ ] variable.
All the fog servers have the same data processing speed so maximum requests it can serve per second i.e., would also be same that can be calculated using Eq.

2.
= ℎ ℎ A fog server is performing many functions so to prevent it from getting overloaded, the number of requests that it can serve should be restricted to a certain number. We are assuming that all the fog servers have a certain capacity depicting the number of requests it can serve in total. Using this constraint the CFPM approach balances the load among all the available fog servers. Further, the fog server compares its capacity with the total requests it has served. If its capacity has reached to its limit value i.e., if sum value is equal to , then it updates Flag[fid].sum equal to sum and sets its Flag[fid].free value to 0 and exit.
Otherwise if sum value is greater than , then it means the fog server is unable to serve the user completely. It then calculate the remaining number of requests and updates the count[uid] value equal to the number of requests it has served for the user. It updates Flag[fid].sum equal to and sets its Flag[fid].free value to 0. Further, it calls the SEND-REQUEST(uid, rem) function to request to another available fog server to serve the remaining need of the user.
But if sum is less than , then it signifies the normal execution where the fog server is able to serve the user completely or serves its remaining need completely. So in this it only updates Flag[fid].sum equal to sum.

Attacker Isolation Procedure
The proposed approach CFPM, uses Attack Fog servers to handle attack. Algorithm 4 is executed if ACTIVATE-ATTACKFOG(uid) function is called by any fog server. .mode value to 1. Further, ATTACKER-ISOLATION(uid, fid) function is called in which user id received in the function is declared as attacker and is added to the blacklist. The account value of the attacker is set to NULL to signify that it would no longer be served by any fog server.

Algorithm 4 Attack Fog Activation and Attacker Isola-
After that the attacker is migrated to the attack fog server and the activated fog server again sets its Flag [fid].mode value to 0, which results in isolation of the attacker.

RESULT AND ANALYSIS
In this paper a conceptual approach CFPM is proposed, in which DDoS attack is mitigated at fog layer using migration MTD technique with the aim of minimizing disruption to serving fog servers.
Various cases are possible based on the need of the users and current capability of the fog servers which are handled using the proposed algorithms. MATLAB is used to experimentally evaluate the CFPM approach.

Possible Scenarios
Considering a system with 'n', as the total number of clients where each client is allowed to send maximum 100 requests per second, assuming Reqsize to be 10 Mb. So max[i] entry and limit[i] for all users "i" would be 100 and 1000 respectively.
The network parameters that are used during the simulation are listed in Table 2. F1, F2 and F3 are the fog servers present at fog layer in which F1 and F3 are active fog servers while F2 is a sleeping fog server. All the fog servers are having data processing speed as 5 Gbps. So using (2) we can calculate maximum number of requests that a fog server can handle efficiently i.e., = 500.
For a user "i" the value of account[i] is updated at the time of request generation and further using (1) score[i] is calculated. Then score[i] is compared to limit[i], which results in following two possible cases 1 and 2: (1) Case 1: It is executed when the score[i] value is either equal to or less than limit[i] value. In this case SERVE() function is called which further compares sum value and value resulting in four possible cases -A, B, C and D: (a) Case A: Fig. 4 shows the case when the total number of requests served by a fog server is less than capacity of fog server. Fig. 5 Fig. 6 shows the case when the total number of requests served by a fog server is equal to capacity of fog server.  Table 4 depicting that it has reached its limit and can no longer serve any user.  (c) Case C: Fig. 8 shows the case when the total number of requests served by a fog server is greater than the capacity of fog server so the requests are served by some active fog servers collectively. In this case after serving users U1,U2,U3,U4 and U5, fog server F1 serves 450 requests in total and updates the variables accordingly and their comparison is as shown in Fig. 9. When U6 generates 100 requests then sum value is incremented to 550 which is greater than the capacity of fog server. So F1 server calculates the remaining need of user U6 which it was unable to serve and update its count [U6] value to the number of requests it has served for user U6. It then updates its Flag[F1].sum value to and Flag [F1].free value to 0 as shown in Table 5, which signifies that it has reached to its limit. Further, to serve the remaining need of the user U6 it calls SEND-REQUEST(U6, 50) function and sends request to another available fog server F3. F3 then serve user U6. In this case F1 and F3 fog servers collectively serves the need of user U6 as shown in Fig. 8.  (d) Case D: Fig. 10 shows the case when the total number of requests served by a fog server is greater than the capacity of fog server and all the active fog servers collectively are unable to serve the requests of the user completely. So to handle the case request is forwarded to cloud server. Fig. 11 shows the comparison of all the variables for all users. Final value of Flag[ ] variable for all fog servers is shown in Table 6 . This case is executed when the score[i] value is greater than limit[i] value for any user "i". Fig. 12 shows how the attacker isolation procedure works. Fig. 13     and number of fog servers needed (for case C, two fog servers would be needed and for case D even two fog servers would not suffice. Therefore remaining need is forwarded to cloud server).  Fig. 15 shows the evaluation of the system on implementation of CFPM approach before and after attack. A fog server can handle 500 requests per second so in one second 1000 requests can be served by two fog servers. In case there is no attacker present, after every second same number of requests are handled.

Evaluation
But if there is an attacker present in the system, say the attacker arrives at 4th second, then the fog server detect it by comparing certain values and call ACTIVATE-ATTACKFOG function.
Detection and function calling will take very less time (fraction of seconds), so for only that amount of time there would be a minor decrease in the number of requests served by fog server. After that fog server can process the request in the usual manner. As after detection of attacker, attack fog server is responsible for handling the attacker without any involvement of the detecting fog server. This evaluation proves that the proposed approach CFPM is very effective. Figure 15: Evaluation of the system before and after attack

CONCLUSION
For mitigating DDoS attacks in the cloud, different approaches were proposed in the literature. Fog computing and MTD has been used separately to address the security issues in cloud. MTD has never been applied to fog paradigm. After evaluating the effectiveness of MTD it has been observed that MTD can be applied to decentralized cloud infrastructure such as fog. This paper presents a proactive novel approach CFPM, that mitigates DDoS attacks in cloud using fog layer with applied migration MTD technique. CFPM detects and isolate the attacker based on certain network parameters at fog layer. By using migration MTD technique it migrates the attacker to attack fog server minimizing disruption to serving fog servers and requiring no involvement of cloud server. Attack fog server is an activated fog server which after migration of attacker again goes into the sleep mode resulting in the isolation of the attacker. CFPM approach is analyzed under different cases and performance of the system before and after attack is evaluated. CFPM uses the idea of load balancing to prevent fog servers from getting overloaded.